机器学习基石(四)：概率角度分析机器学习的可行性

一、前言

什么是机器学习的可行性&＃xff1f;
算法是否具备学习能力。衡量学习能力是通过在训练数据集之外的数据来进行验证。这个学习能力&＃xff0c;也就是算法的泛化能力。在机器学习中&＃xff0c;我们的目标是要寻找高泛化能力的模型。

二、从概率论到机器学习

构建一个弹珠罐子模型&＃xff0c;其中装满绿色和橘色弹珠&＃xff0c;从中抓一把个数为N的弹珠作为样本。如下图所示。

用数学语言来描述上图中$\nu$和$\mu$的关系&＃xff0c;就是著名的霍夫丁不等式(Hoeffding’s Inequality)

P[∣ν−μ∣>ϵ]≤2exp(−2ϵ2N)(1)P[|\nu-\mu| > \epsilon]\le 2 exp(-2\epsilon^2N) \tag 1P[∣ν−μ∣>ϵ]≤2exp(−2ϵ2N)(1)

公式(1)说明&＃xff0c;$\nu$和$\mu$是否相似&＃xff0c;与$\mu$的具体数值无关&＃xff0c;只与样本容量N&＃xff0c;容忍度$ϵ$有关。

接下来&＃xff0c;我们从弹珠罐子模型转到机器学习模型。

如上图所示的一一对应。
在罐子里&＃xff0c;我们不知道橘色真实占据全部弹珠的比例&＃xff0c;同样&＃xff0c;对于某个固定的假设$h(x)$&＃xff0c;我们不知道是否就是目标函数$f(x)$。

样本空间中的每一个样本点x∈X对应于bin中的每一个marble&＃xff0c;当假设h(x)和f(x)不一样时&＃xff0c;我们就把球漆成橘色&＃xff1b;一样时&＃xff0c;我们就把球漆成绿色。

从球罐中抽取的size-N marble对应到学习问题中的训练集D&＃xff0c;采样方式均为iid采样。

球罐模型的目的是用抽样计算出的比例估计真实的比例&＃xff0c;而学习问题中我们的目的是用样本内误差in sample error估计样本外误差out sample error。

对于某个固定的h假设&＃xff0c;我们可以将样本内外误差做如下定义&＃xff1a;

Eout(h)&＃61;εx→P[h(x)≠f(x)]E_{out}(h)&＃61;\varepsilon_{x\rightarrow P}[h(x)\ne f(x)]Eout​(h)&＃61;εx→P​[h(x)​&＃61;f(x)]

Ein(h)&＃61;1N∑n&＃61;1N[h(xn)≠yn]E_{in}(h)&＃61;\frac{1}{N}\sum_{n&＃61;1}^N[h(x_n)\ne y_n]Ein​(h)&＃61;N1​n&＃61;1∑N​[h(xn​)​&＃61;yn​]

其中EoutE_{out}Eout​表示out-of-sample Error&＃xff0c;整个P中犯错误的概率&＃xff0c;样本外误差&＃xff0c;期望损失&＃xff1b;EinE_{in}Ein​表示in-sample Error&＃xff0c;在样本空间N中犯错误的概率&＃xff0c;样本内误差。

现在&＃xff0c;我们就可以使用EoutE_{out}Eout​和EinE_{in}Ein​重写霍夫丁不等式&＃xff1a;
P[∣Ein(h)−Eout(h)∣>ϵ]≤2exp(−2ϵ2N)(2)P[|E_{in}(h)-E_{out}(h)| > \epsilon]\le 2 exp(-2\epsilon^2N) \tag 2P[∣Ein​(h)−Eout​(h)∣>ϵ]≤2exp(−2ϵ2N)(2)

同样&＃xff0c;在使用样本求出来的EinE_{in}Ein​&＃xff0c;在样本数量N足够大的情况下&＃xff0c;也能近似表示EoutE_{out}Eout​&＃xff0c;前提是都是针对该固定的h假设。

所以在手中拿着fixed的假设h的时候&＃xff0c;如果Ein(h)E_{in}(h)Ein​(h)很小的话&＃xff0c;根据公式(2)也可以PAC(probably approximately correct)的说明Eout(h)E_{out}(h)Eout​(h)也很小。也就说明&＃xff0c;这时候的h和f很接近。

但是&＃xff0c;截止目前为止&＃xff0c;我们所有推论仅仅用于验证h是否是一个好的假设。至于固定的这个$h$&＃xff0c;我们没办法保证他一定会生成很小的Ein(h)E_{in}(h)Ein​(h)

三、在假说集合中挑选h

在上一节的基础上做拓展。我们一个假说&＃xff0c;对应一个bin&＃xff0c;那么有很多假说时候&＃xff0c;就表示我们有很多bin。很容易做出推断&＃xff0c;判断某个假说是否为好的假说&＃xff0c;就是在看Ein(hi)E_{in}(h_i)Ein​(hi​)是否足够小。

真的是这样吗&＃xff1f;

如上图所示&＃xff0c;在假设hMh_MhM​下&＃xff0c;我们get到全为绿色的球&＃xff0c;说明使用该假说的话&＃xff0c;能够达到100%的准确率。但是从上帝视角来看&＃xff0c;该EinE_{in}Ein​和EoutE_{out}Eout​还差很多。

接下来&＃xff0c;我们来量化分析下&＃xff0c;在多种h假设中选取最佳h的情境&＃xff0c;对应的数学模型。

首先&＃xff0c;定义坏的sample。

如果这份样本使得EinE_{in}Ein​和EoutE_{out}Eout​相差很多&＃xff0c;我们将这份sample称为 BAD sample。

霍夫丁不等式告诉我们&＃xff0c;对于某个fixed h&＃xff0c;出现BAD sample的概率是有限的。如下图所示&＃xff1a;

但是&＃xff0c;当整个学习过程中存在选择的时候&＃xff0c;我们往往会选择对应EinE_{in}Ein​小的h&＃xff0c;这其中就有了偏见&＃xff0c;不再公平。

用铜板举例子&＃xff1a;

用铜板丢正反面&＃xff0c;一次试验(一个固定的h)的时候&＃xff0c;五次都为正面的概率为1/32&＃xff0c; 如果重复150次试验(150个h)&＃xff0c;那么其中出现五次正面的概率高达99%。如果我们在其中挑选最好的那个h&＃xff0c;基本拿到5次正面的那个h的概率就是99%以上。

我们来看在很多假设h的时候&＃xff0c;如何定义bad sample

只要存在h使得该sample属于bad sample&＃xff0c;我们就将其定义为bad sample

那么在算法可以自由在h中做挑选的时候&＃xff0c;选中的概率bad sample的概率计算方法如下&＃xff1a;

综上&＃xff0c;如果$|H|\&＃61;M$&＃xff0c;其中M有限(H假设空间的h个数有限)&＃xff0c;N足够大&＃xff0c;那么我们总能找到h&＃xff0c;使得Ein(h)E_{in}(h)Ein​(h)最接近0&＃xff0c;同样对应Eout(h)E_{out}(h)Eout​(h)也最接近0
这说明机器学习在一定范围内是可行的&＃xff0c;我们的确能够学到一些东西&＃xff0c;使得算法拥有对应的泛化能力。

四、总结

上图中黑色实线流程&＃xff0c;与之前机器学习流程没有差别。

虚线部分&＃xff0c;就是本章的重点&＃xff0c;左侧指向training examples表示产生样本的方式。右侧的x表明&＃xff0c;用于验证算法g的数据。

同样说明&＃xff0c;用于测试和用于训练的数据&＃xff0c;都是来源于同一个distribution。

最后&＃xff0c;本节面向的对象是假说集hypothesis set H中容量有限的&＃xff08;finited M&＃xff09;&＃xff0c;如果M无限多的情况怎么办&＃xff08;LPA中无限条的线&＃xff09;&＃xff0c;我们会在接下来章节重点研究解决。