8.Noise and Error

8.1 Noise and Probabilistic Target

噪音（杂讯）和概率目标函数。

本小节主要讨论有噪音（在2.4节提到的）的情况下VC限制是否仍可用，含有噪音的机器学习流程图如下图所示。

什么是噪音，产生噪音的原因有哪些？仍然举银行发放信用卡的例子，阐述产生噪音的3种原因：

1. 标记（样本标签） $y$y 中存在的噪音，即错误的标记。如将本应该发放信用卡的用户，错误的标记为不符合规定的用户。
2. 标记 $y$y 中存在的另一种噪音，即不同的评判标准评定同一输入样本得到不同结果。如两个用户所有的属性条件都一致，判定一个发放，而另一个不发放。
3. 输入样本 $X$X 中存在的噪音，即输入信息不准确，如用户的信息录入错误。

那么，存在噪音时，VC限制还起作用吗？

再看小球的例子，之前没有噪音条件时，输入样本和整体样本均服从同一概率分布 $P(x)$P(x) 。不论是罐中的小球还是抽样取出的小球。此种情况，使用的是确定性（deterministic）的小球。其中小球的颜色类比于目标函数 $f(x)$f(x) 与假设函数 $h(x)$h(x) 是否一致。标记 $y$y 取决于目标函数 $f(x)$f(x)，此学习方法叫做 判别方法；在现实中，多数为含有噪音的情况，数据依然服从统一的概率分布，但小球颜色并不固定，可以想象为颜色在不停变色的小球，只能在某一时刻才能确定它的颜色，这种小球可以叫做概率性（probabilistic）的小球。对应到机器学习上，是含有噪音的样本，即$[y \neq h(x)]$[y​=h(x)] 并不确定，其中标记y服从概率分布 $P(y|X)$P(y∣X)，这一形式被称为目标分布（target distribution）而不是目标函数，此方法叫做生成方法。为何称为目标分布，举一个简单的例子，如一个样本点符合下式：

$P(+1|x)=0.7$P(+1∣x)=0.7
$P(-1|x)=0.3$P(−1∣x)=0.3

则一定会选择错误率小的目标（mini-target），根据此原则，该例选择标记为+1，而30%的几率标记为-1是噪音。目标函数f是一个特殊的目标分布，其概率符合下式：

$P(+1|x)=1 \Leftrightarrow y = f(x)$P(+1∣x)=1⇔y=f(x)
$P(-1|x)=0 \Leftrightarrow y \neq f(x)$P(−1∣x)=0⇔y​=f(x)

至此，有两个分布函数$P(y|X)$P(y∣X) 和$P(X)$P(X)，$P(X)$P(X)越大意味着 $X$X 被选为训练样本的概率越大；$P(y|X)$P(y∣X) 越大意味着该样本是某一类的几率越大。两者结合，即在常见的样本点上分的类尽量正确。

因此得出VC限制依然适用，因为这种含有噪音的输入样本以及标记分别服从$P(X)$P(X)，$P(y|X)$P(y∣X)，即 $(X,y)$(X,y) 服从$P(X,y)$P(X,y)的联合概率分布。

结合噪音和目标分布的概念对机器学习流程图进行修改，如下图所示，其中，目标函数f变成了目标分布$P(y|X)$P(y∣X)，它产生训练样本的标记y；同时，测试样本的标记y也服从该分布。

例题

8.2 Error Measure

错误衡量。

本小节介绍错误的衡量方式对机器学习的影响。

之前的很多章节都在描述如何使机器学到东西，即如何使得假设函数g和目标函数f接近，亦即如何使得 $E_{out}(g) $ 尽可能的小。错误衡量 $E(g,f)$E(g,f)主要考虑了以下三个因素：

1. 样本外的未知数据（out-of-sample）：所有未知样本x的平均；
2. 逐点评估（pointwise）：每个数据点 $x_i$xi​ 单独评估；
3. 分类评估（classification）：看prediction与target是否一致（$[f(x) \neq g(x)]$[f(x)​=g(x)]），classification error通常称为0/1 error。二元分类只有两个类别，相同为0，不同为1。
   
   上述这种分类误差（classification error）又称 0/1误差（0/1 error）。

可用 $err()$err() 函数表示逐点的错误衡量（pointwise error measure）。因此，训练样本和整个样本空间的错误衡量可分别用下式表示。

为了便于表述，将假设函数 $g(x)$g(x) 表示为 $\widetilde{y}$y​ ，目标函数 $f(x)$f(x)表示为 $y$y。

除了常用在分类（classification）上的 0/1误差衡量之外，还有用在回归（regression）上的平方误差（square error）衡量，它也是一种逐点（pointwise）的错误衡量方式，如下式所示。

错误衡量对机器学习有着指导作用。

在含有噪音的情况下，目标分布函数 $P(X|y)$P(X∣y)和逐点误差函数$err()$err()共同决定了理想的错误率最小目标函数（ideal mini-target）f。

目标分布函数对错误率最小目标函数$f(x)$f(x)的影响在上一节中已经阐述过了，接下来通过一个例子来说明逐点误差函数对$err()$err()其的影响。

假设3个目标分布函数 $P(y|X)$P(y∣X)，分别计算在0/1错误衡量的情况下和平方错误衡量下各标记的错误率。

由上文可知，将f(x)标记为y，由下图中公式的定义知，左图中，0/1误差为y帽≠y的概率，目标函数 $f(x)=y=argmaxP(y|X)=2$f(x)=y=argmaxP(y∣X)=2。预测标签为1的误差为 $0.7+0.1=0.8$0.7+0.1=0.8；预测标签为2的误差为 $0.2+0.1=0.3$0.2+0.1=0.3 ；预测为标签3的误差为$0.2+0.7=0.9$0.2+0.7=0.9；预测为1.9的误差为 $0.2+0.7+0.1=1$0.2+0.7+0.1=1 。右图中，目标函数$f(x)=\sum y \cdot P(y|X) = 1 \times 0.2 + 2 \times 0.7 + 3 \times 0.1 =1.9$f(x)=∑y⋅P(y∣X)=1×0.2+2×0.7+3×0.1=1.9。预测为标签1的误差为 $(1-1)^2 \times 0.2 + (2-1)^2 \times 0.7 + (4-1)^2 \times 0.1 = 1.1$(1−1)2×0.2+(2−1)2×0.7+(4−1)2×0.1=1.1，同理可求预测标签为2,3,1.9时的误差。

至此在上一节的基础上对机器学习流图做了进一步的修改，如图8-5所示，加入了错误衡量的模块，该模块对算法和最终的假设选择都起着很大影响。

例题

8.3 Algorithmic Error Measure

算法的错误衡量。

二元分类问题的错误类型也分为两类，如图所示。

错误的拒绝（false reject）：在目标函数f为+1时，假设函数g给出了-1，即误把正类当成负类。
错误的接受（false accept）：在目标函数f为-1时，假设函数g却给出了+1，误把负类当成正类。

上节中的0/1误差衡量将这两类错误的损失画上了等号，在现实中，这两种错误在不同的场景其损失不同。

举两个常见的例子，在超市给年消费额高的会员发放赠品时，如果出现了错误的接受，即该会员没有资格领取到赠品，超市依旧给他发放了赠品，该损失只是超市多发了一些赠品；但若错误的拒绝，意味着该会员有资格领取到赠品，超市却拒绝给他发放，损失的不只是超市的信誉，还可能会造成客户流失。

另一个例子是在安全部门中，员工有查看资料的权限，系统却拒绝了他的请求，这是一种错误的拒绝，员工最多也就是抱怨一下；但若一个员工没有查看资料的权限，系统却同意了，这是一种错误的接受，损失可能会非常大，甚至有可能威胁到国家的利益。这两种情况的损失可能如图所示。

以上两个错误的损失也证明了在不同的应用中需要使用不同的错误衡量。

在设计算法时，最好方式是依据各种错误损失的情况设计错误衡量，但是最大的问题是错误损失的数值如何确定（如图中这些10和1000如何定量的给出）。因此在进行算法设计时，通常采用替代的方式来进行设计，目前主要有两种替代方式的原则，如下所示：

1. 合理的：在分类错误衡量中，可以想象这种噪音的情况相对于整体一定是小的，因此只需要找到一个足够小的错误即可；在平方错误衡量中，只要认同噪音服从高斯分布，减小高斯中平方项，就如同在减少平方错误。将这种近似的错误衡量方式用$\hat{err}$err^表示。
2. 友善的：很容易设计一种算法A。如寻找最小的0/1错误是一个NP-HARD问题，而实际中设计算法时，运用错误率比前者更小的原则，即寻找越来越小的错误率。以后的章节中会提到两种方式：直接求出结果（closed-form solution）；凸求解方程（convex objective function）。

因为在设计算法时，很难知道具体的错误衡量，因此产生了近似的错误衡量 $\hat{err}$err^，这是本节的重点。在加入了$\hat{err}$err^之后，机器学习的流程图如图所示。

例题

8.4 Weighted Classification

加权分类。

上一节中提到的下图中的错误表示方式，称为成本矩阵（cost matrix）或损失矩阵（loss matrix）亦或误差矩阵（error matrix）。

使用如上的错误矩阵分别表示为如下公式：

因为VC限制可以在各种算法中起作用，因此在求解已知的算法中只需要使得$E_{in}(h)$Ein​(h)尽可能的小，但是这里使用的$E_{in}(h)$Ein​(h)和之前的提到的没有加权的是有些区别，为了有所区分，将加权的（weighted）$E_{in}(h)$Ein​(h) 表示为 $E_{in}^w(h)$Einw​(h)，如下式所示。

假设在一种不是线性可分的情况下（如果是线性可分一定会产生 $E_{in}^w(h)=0$Einw​(h)=0 的情况），比如pocked算法，先对在这一情况时算法思路进行一个猜想，大部分和原来的算法一致，即如果 $W_{t+1}$Wt+1​ 的$E_{in}^w(h)$Einw​(h)比$\hat{W}$W^ 的更小，则使用取代原来$W_{t+1}$Wt+1​ 的$\hat{W}$W^。

Pocket算法可以使用$E_{in}^{0/1}(h)$Ein0/1​(h)作为错误衡量是被证明了的，但是上述加权的方式却没有被证明，该如何寻找一种保障pocket算法在加权错误的情况下，可以使用类似以上的方式的算法流程呢？

一个简单的方式是将上述使用$E_{in}^w(h)$Einw​(h)的原始问题转变成一种使用$E_{in}^{0/1}(h)$Ein0/1​(h)且与原始问题等价的问题，如图所示。

等价问题是将原始问题中数据集D中标记为-1的所有数据样本都复制1000次，再将损失矩阵表示不含加权的损失矩阵，而这种损失矩阵正是pocket算法使用的错误衡量方式，唯一的区别，如样本$x_1$x1​出错，被复制的其他的999个$x_1$x1​也跟着一起犯错了，损失相当于是以前的1000倍。同样，算法碰到标记为-1的数据样本的几率也增大了1000。

例题：10个入侵者的样本，999990个自己的样本，假设函数h总是判定为+1，那么$E_{in}$Ein​为多少。

Summary

本节主要讲了在有noise时，即数据集按照概率分布，那么VC Dimension仍然成立，机器学习算法推导仍然有效。机器学习cost function常用的error有0/1 error和squared error两类。实际问题中，对false accept和false reject应该选择不同的权重。

参考：
https://www.cnblogs.com/ymingjingr/p/4306666.html
https://github.com/RedstoneWill/HsuanTienLin_MachineLearning