如果数据存在噪声，对机器学习可学习理论推导有何影响？
噪声起源
对于$f:\mathcal X\rightarrow \mathcal Y$，噪声即可能来源于$\mathcal X$，也可能来源于$\mathcal Y$。以信用卡申办信息为例说明（$\mathcal X$为客户资料，$\mathcal Y$为是否办理信用卡）：
- $y$的噪声：良好纪录的用户，被标记为Bad；
- $y$的噪声：同样资料的用户，标记却不同（不同专家评价有差异）；
- $\mathbf x$的噪声：不准确的客户资料。
目标分布1
由于噪声的存在，弹珠模型的弹珠不再是确定的颜色，而是会随时变色，但是通过记录抽出瞬间弹珠的颜色，仍可以对罐中弹珠颜色概率做估计。$y=f(\mathbf x) + \mbox{noise}$，$y$用目标分布表示 \begin{equation} y\sim P(y|\mathbf x)。 \end{equation} 对于满足$(\mathbf x,y)\sim P(\mathbf x,y)$的噪声数据，VC界仍成立，通过$E_{in}$仍然可以估计$E_{out}$。 如果$P(\circ|\mathbf x)=0.7$，$P(\times|\mathbf x)=0.3$，理想最小目标函数（ideal mini-target）为$f(\mathbf x)=\circ$，在最佳选择下噪声水平是$0.3$。对于确定的（无噪声）的目标函数$f$，也可用目标分布（target distribution）表示 \[ P(y|\mathbf x)= \left\{ \begin{aligned} 1&\quad\mbox{for }y=f(\mathbf x)\\ 0&\quad\mbox{for }y\neq f(\mathbf x)。 \end{aligned} \right. \]
机器学习的目标就是预测常见数据（w.r.t. $P(\mathbf x)$）的理想最小目标函数（w.r.t. $P(y|\mathbf x)$）。
由于噪声的存在，并且$\mathcal D$也是通过采样得到的，从数据$\mathcal D$无法得出目标函数$f$是线性还是非线性等特征。
误差度量
回顾out-of-sample误差度量\[E_{out} = \varepsilon_{\mathbf x\sim P}[[g(\mathbf x)\neq f(\mathbf x)]]，\]它是基于每个点的误差度量（pointwise error measure），$[[\mbox{prediction}\neq\mbox{targe}]]$度量的分类错误称为0/1错误。基于每个点的in-sample误差度量为\[E_{in} = {1\over N}\sum_{n=1}^Nerr\left(g\left(\mathbf x_n\right),f\left(\mathbf x_n\right)\right)。\]
令$\tilde y=g(\mathbf x)，y=f(\mathbf x)$，0/1误差和平方误差分别定义为\[err(\tilde y,y)=[[\tilde y\neq y]]\qquad err(\tilde y,y)=(\tilde y- y)^2。\]
误差是如何影响学习算法的呢？
下面示例展示了不同度量方式下误差的差异：
$P(y|\mathbf x)$和$err$确定了理想最小目标函数$f(\mathbf x)$。在0/1误差和平方误差度量方式下，理想最小目标函数分别为 \[ f(\mathbf x)=\arg\max_{y\in\mathcal Y}P(y|\mathbf x)\qquad f(\mathbf x)=\sum_{y\in\mathcal Y}yP(y|\mathbf x)。 \] 若采用平方误差度度量方式，上例中$f(\mathbf x)=1.9$。
根据具体应用场景，选择相应的错误（误差）衡量方法，对机器学习至关重要。
VC理论的推导不一定依赖于目标函数$f(\mathbf x)$，只需目标分布。VC理论对很多假设集$\mathcal H$和误差衡量$err$都有效，比如将定义稍作修改可将VC理论推广到回归分析可得到类似的结果。
误差度量范例
以指纹识别为例，介绍误差度量。$+1$表示合法用户，$-1$表示入侵者。指纹识别犯的两种错误：
- false reject：合法用户识别为非法；
- false accept：非法用户识别为合法。
在不同的应用场景下，两种错误导致的损失不一样。在设计算法的时候，须考虑将误差的度量方式。设计算法的时候，不仅要考虑误差定义的合理性，还要考虑算法$\mathcal A$是否容易优化（比如：闭式解或者凸目标函数）。误差的度量是算法的关键。
对于错分的不同损失，可根据犯错误所属的不同类别定义如下的加权误差度量方式
\[ E_{in}^w(h)={1\over N}\sum_{n=1}^N \left\{ \begin{aligned} &1 &\quad\mbox{if }y_n=+1\\ &1000 &\quad\mbox{if }y_n=-1 \end{aligned} \right\} \cdot \left[\left[y_n\neq h(\mathbf x_n)\right]\right]。 \] 对于线性可分数据的PLA，这种定义并无影响。对于pocket算法，假设将$-1$样本复制$1000$倍，在新的数据上仍用$E_{in}^{0/1}$度量误差，就和在原数据上用$E_{in}^{w}$度量一致。
实际使用中，不会真的复制数据，采取虚拟复制（virtual copying）的策略。
####加权pocket算法
- 以$1000$倍的概率检查$-1$样本犯的错误；
- 当$\mathbf w_{t+1}$犯的错误$E_{in}^w$比$\hat{\mathbf w}$小时，用$\hat{\mathbf w}$更新$\mathbf w_{t+1}$。
参考资料
脚注
-
不太明白这节的意思…… ↩
