《机器学习基石》8-Noise and Error

这一节主要讨论在有噪声的情况下，VC维理论是否仍适用。

Noise and Probabilistic Target

回顾之前提到的机器学习的流程图，学习的目的，就是找到一个函数 g$g$，使得它与目标函数 f$f$ 差不多。

然而在现实生活中，往往伴随着噪声：

这些噪声的类别是多种多样的

• noise in y$y$：如标签标错了
• noise in x$x$：如原本的数据就存在噪声

没有噪音时，x$x$ 服从同一个概率分布 P$P$，y=f(x)$y=f(x)$ 是一个固定的值；有噪声时，x$x$ 仍然服从同一个概率分布 P$P$，y∼P(y|x)$y\sim P(y|x)$ 不再是一个固定的值。

以之前提到的珠子为例子，珠子的两种颜色分别表示了 h(x)$h(x)$ 与 f(x)$f(x)$ 相等或者不等的情况。我们通过抽样，利用珠子属于某种颜色的频率来估计 h(x)=f(x)$h(x)=f(x)$ 的概率。

在没有噪声的情况下，y$y$ 是固定的，因此珠子的颜色是确定的。在有噪声的情况下，y$y$ 不是固定的，因此珠子的颜色是变化的，此时我们仍然可以进行抽样的实验，只不过在进行统计的时候，我们记录的是珠子在抽出来那一刻的颜色。这样，我们就可以跟以前一样，通过频率来估计概率。

因此，只要 x∼P$x\sim P$ 并且 y∼P(y|x)$y\sim P(y|x)$，也就是说 (x,y)∼P(x,y)$(x,y)\sim P(x,y)$，VC维理论仍然适用。于是，学习的目的，从预测 f$f$ 变成了预测 p(y|x)$p(y|x)$，其中 p(y|x)$p(y|x)$ 由 f(x)$f(x)$ 以及噪声构成。

对于 f$f$，我们可以将其想象为分布 P(y|x)$P(y|x)$ 的一种特殊形式。

• y=f(x)$y=f(x)$时，P(y|x)=1$P(y|x)=1$
• y≠f(x)$y\ne f(x)$时，P(y|x)=0$P(y|x)=0$

这样就可以将无噪声以及有噪声的情况统一起来，学习的流程图更新成以下形式：

Error Measure

我们需要有一个准则来衡量所选择的假设函数 g$g$ 与目标函数 f$f$ 相似程度，通常的方法是定义一个错误函数（也叫做代价函数） E(g,f)$E(g,f)$。

这个错误函数描述的是在整个样本空间（不只是训练样本）中，g$g$ 与 f$f$ 的相似程度，并且通常来讲，是 g$g$ 与 f$f$ 在每个样本点上的错误的平均。

常用的两种错误衡量方式 err(g(x),f(x))=err(y~,y)$err(g(x),f(x))=err(\tilde{y},y)$：

• 0/1 error for classification：err(y~,y)=[y~≠y]$err(\tilde{y},y)=[\tilde{y}\ne y]$
• squared error for regression：err(y~,y)=(y~−y)2$err(\tilde{y},y)=(\tilde{y}-y{)}^2$

错误衡量准则会对学习过程起到指导作用，因此对于同一个问题，使用不同的错误衡量准则，得到的结果可能不一样。

对机器学习流程图进一步修改，加入了错误衡量的模块，该模块对算法和最终的假设选择都起着很大影响。

Algorithmic Error Measure

在现实中，要设计出真正的错误衡量有时候会很困难，在设计错误衡量方式时，常常使用替代的方式 err^$\widehat{err}$：

• 有意义的错误衡量
  例如 0/1 error，表示的是 flipping 的噪声，如果 0/1 error 很小，说明出错的样本数很少；
  例如 squared error，表示的是噪声是高斯的分布，如果 squared error 很小，说明高斯噪声很少；
• 对设计算法容易的错误衡量
  例如有闭式解的算法对应的错误衡量方式；
  例如具有凸函数性质的错误衡量方式。

于是，学习的流程图改为下面的形式，其中 err$err$ 表示的是真正的错误衡量方式，而err^$\widehat{err}$ 表示的是我们用在算法中的错误衡量方式，我们使用 err^$\widehat{err}$ 来替代 err$err$ 进行算法中的优化以及假设函数的选择。

Weighted Classification

我们可以使用 cost matrix 表示 0/1 error

其中 false reject 表示的是把 y=+1$y=+1$ 预测为 y=−1$y=-1$，false accept 表示的是把 y=−1$y=-1$ 预测为 y=+1$y=+1$。

当这两类错误的 cost 相等时，表示这两类错误的重要性一致，当这两类错误的 cost 不相等时，表示其中一种错误更加严重，代价更高。

于是我们可以根据实际的需要，赋予两种错误不同的代价，这叫做 weighted classification。

下面是一个 cost matrix 的例子，在这个例子中，把 y=+1$y=+1$ 预测为 y=−1$y=-1$ 的代价是 1$1$，而把 y=−1$y=-1$ 预测为 y=+1$y=+1$ 的代价是 1000$1000$，因此算法会惩罚后一种错误分类的情况。

通过改变样本的数目，可以将 weighted classification 转化为一般的 classification。用上一个例子来说明，我们可以将数据集中 y=−1$y=-1$ 的样本复制 1000 份，这样就相当于在没有加权的 0/1 error 下进行实验。于是可以使用之前用于 0/1 error 的算法，比如 pocket 算法。

将上面 cost matrix 的转化嵌入到算法中，便得到了 weighted pocket 算法