机器学习基石-Noise and Error

Noise and Error

回顾

通过lecture7的学习，我们知道当我们的hypothesis set拥有有限的dVC，我们拥有足够多的资料，并且能设计一个演算法找到一个足够小的Ein,那么学习是可行的，本节课我们看看杂讯的加入会带来什么改变。

Noise and Probabilistic Target

首先，必须承认的是现实生活中杂讯是客观普遍存在的，结合我们的学习流程，输入输出等多个环节都可能导致杂讯的产生。接着我们回顾下学习的流程，在之前的基础上我们考虑加入杂讯，然后看看杂讯是否对我们推导的VC bound有什么不良影响。

说到VC bound，我们回到关于其的最重要的模型—推测罐子中橘色弹珠的占比。我们将其中的每一个弹珠看成一笔资料，通过某个分布P我们将其取出，然后如果f(x) ̸= h(x)成立，则将其漆成橘色。

现在我们想象有一种特殊的弹珠，这种弹珠的颜色一直在变化（比如一天60%的时间是橘色，40%的时间是绿色），我们通过记录抽样瞬间弹珠的颜色来推测整体的弹珠占比。这种会变色的弹珠对应到学习的问题就是可能的杂讯。当我们的x取样来自某个P(x)，y取样来自于某个P(y|x)(y在是一个弹珠的前提下颜色的概率），并且两者都是i.i.d的，那么我们的VC bound理论还是成立的。

我们一般把P(y|x)称为target distribution，他实际告诉对某一个点做的预测。比如，现有一个点，他有70%的概率是1，有30%的概率是0。我们一般都会选择将其预测成1，那么我们范的30%的错误可以看成是选1这个最好的选择下存在的杂讯，这是对target distribution的一中理解。

第二种理解就是预测100%成立带着0%的杂讯。加入这部分内容后，我们的学习流程可进一步细化如下：

Error Measure

学习进行到最后一步，我们总是要评估我们学习效果的好坏，我们使用的主要评价指标是Eout，实际上更本质的是我们需要给出g和f相似性的打分标准。

我们使用的g有以下三个特征：额外的资料上看效果；逐个资料看效果；分类效果(二元)，分类效果又被称为0/1错误。

我们定义Pointwise Error，然后在此基础上给出两种常见的

Pointwise Error Measures，分别是0/1error和square error，计算方式如上图，下面给出一个具体的例子，计算两种错误衡量方式下的结果，会得到不同的结论。

进一步，我们在前面的学习流程上告诉我们的错误衡量方式来看看我们选择的g的f间的差距。这一块还需要说明的是，VC对于非分类非监督学习的很多hypothesis和理论能得到VC bound类似的结论。

Algorithmic Error Measure

我们结合超市指纹识别的例子来看看error的具体情形，我们的f和g可能情形有四种，其中的两种错误是false reject和false accept，对于超市来说两种错误发生造成的影响是不同，前者的影响可能是后者的十倍甚至更多，因此给出的错误惩罚理应给更高的权重。

但是如果实际的场景是CIA的场景，他们对应的成本矩阵就截然不同，有可能如下图。

由此可见错误衡量方式的选择是比较重要的，我们要根据实际场景和需求选择合适的错误衡量方式。

Weighted Classification

我们定义一个新的概念weighted classification：对不同的资料给予不同的重要性的分类方式，然后我们来看看怎么解决这样的问题。

在VC理论成立的情况下，我们主要目的转化为最小化Ein,我们回顾我们之前学习的pocket演算法，然后在思考是否加权变形后的pocket也能有理论保证呢？

我们来看原始的问题，我们现在有一笔带有标签的资料集；我们做另一个资料集：当资料标签为+1的时候，我们复制这些资料，资料标签为-1的时候，我们复制这些资料1000次，然后我们将同权重的损失矩阵给到创建的这笔资料。这样，两者最后的error是一致的。也即我们证明了加权变形后的pocket是有理论保证的。

于是结合我们上面的证明，我们可以定义Weighted Pocket Algorithm，我们可以按上面替换的思路去实现这个想法，考虑到实际问题的实现难度，我们更多在算法层面进行实现。

主要的修正是我们将pocket中均衡概率查找+1和-1的点改成给与-1的点1000倍以上于+1的概率，然后其他的操作与pocket一致。

小结

本节课我们首先思考在有杂讯的前提下用P(y|x)代替

f(x)的方式，然后我们看了指纹识别的具体场景并介绍了两个错误衡量方式，具体场景的错误衡量方式应具体问题具体分析，最后我们给出了Weighted Classification的定义及相关理论证明。