机器学习基石第八讲主要介绍噪声和误差度量，笔记整理在下面。

Noise and Probabilistic Target

现实中的数据很可能含有噪声（noise），例如前面的信用卡发放问题中，有的顾客符合发放标准但没有发给，或者同样情况的顾客有人发了有人没法，再或者顾客的信息不正确等等，VC bound是否在由噪声的情况下工作呢？

继续使用前面抽弹珠的例子，罐子中每一个弹珠代表一个数据，如果$f(x) \not= h(x)$，则将弹珠漆成橘色；如果$f(x) = h(x)$，则将弹珠漆成绿色。引入了噪声之后，原来的y就不是真正的f(x)了。现在想象这样每一个弹珠，它的颜色不停变化，称为probablistic(noisy) marbles，不过罐子内橘色弹珠的比例还是一定的。现在我们记录弹珠被抽出瞬间的颜色，比如一次抽取100颗弹珠，抽出瞬间有20颗是橘色的，那我们就可以估计抽出瞬间整个罐子的橘色弹珠比例为20%。

这里说，如果x和y独立同分布（i.i.d），那么VC bound的整个架构还是适用的。这里的$P(y|x)$称为目标分布（target distribution）。一种看法是将其看作存在噪声时的‘ideal mini-target’，如$P(o|x)=0.7$，$P(x|x)=0.3$，那我们说‘ideal mini-target’应该将数据标记为圈圈，噪声水平为0.3。另外一种看法是将原来的deterministic target f看作是ideal mini-target target的一个特殊情况。

现在的学习流程图如下：

本小节测试：

Error Measure

这一小节我们更一般化地来讨论误差度量（error measure），记为$E(g,f)$，其有三个特性：

• out of sample: averaged over unknown x（我们是在未看过的数据上衡量）
• pointwise: evaluated on one x（我们可以在每一个数据点上来衡量）
• classification: [prediction $\not=$ target]（查看分类正确与否）

我们通常用平均的下图中的err来衡量$E(g,f)$，下图还给出了在样本上的错误率的计算方法。这里介绍的0/1错误（0/1 error），此外经常使用的还有平方错误（squared error）（适用于输出为实数的问题）和其他的一些错误计算方法，根据实际情况来选择。

下面给出了一个使用0/1 error和squared error的例子（图中标有星号的时错误率最低的）：

加入了误差度量的机器学习流程图如下：

然后是本小节测试：

Algorithm Error Measure

这里使用指纹识别问题（比如说电脑有了指纹识别功能，只让电脑主人使用）来介绍误差度量的选择。在这个问题中可能出现两种错误：false accept（将入侵者误认为主人而让他使用电脑）和false reject（将主人误认为入侵者，而不让其使用）。

举个例子，将指纹识别系统应用于超市，如果系统认定某位顾客为常客，则给该顾客折扣；如果系统认定某位顾客不是常客，则不给该顾客折扣。在这个问题中，系统应该尽量避免的错误是fasle reject（发生这种错误可能导致常客不再来，给超市带来的损失远远大于给非常客打折的损失）。如果将指纹识别系统应用于CIA的机密文件权限，那系统应该尽量避免的则是false accept。

可以看到不同问题应该使用不同的误差度量方法。下面介绍了几种在设计机器学习算法时可能会用到的误差度量方法(记为$\hat{err}$)：

本节小测试：

Weighted Classification

本小节介绍weighted classification，这里的权重指的是犯错所带来的损失。例如前面的CIA例子中的false reject的权重为1，而false accept的权重为1000，该问题的$E_{out}$和$E_{in}$如下图所示。

将基于损失权重的$E_{in}(h)$记为$E_{in}^w(h)$。下面介绍如何改进pocket PLA算法。一种方法如下图，是将hypothesis错误标记为-1的数据点复制1000份，这样就达到了将此类错误的损失权重记为1000的效果。

当然，我们不会真的进行复制1000份的操作，而是做下面的两点：

• weighted PLA: randomly check -1 example mistakes with 1000 times more probability
• weighted pocket replacement: if $w_{t+1}$ reaches smaller $E_{in}^w$ than $\hat{w}$, replace $\hat{w}$ by $w_{t+1}$

本小节测试：

最后是本讲总结：