1.2.2 如何在机器学习场景中应用大数定律

回顾一下大数定律的数学表达，即霍夫丁不等式P[|v-u|＞ϵ]≤2exp(-2ϵ2N)。在机器学习场景中应用该公式时，需要对其略做改变。

首先，观测样本的统计值v对应到机器学习场景，是模型在训练样本上取得的效果E_in（训练误差）。真实世界的统计值u可以认为是模型在预测样本上的表现E_out（真实误差）。任何模型的训练误差和真实误差的差距均应满足霍夫丁不等式的限制：

P[|E_in-E_out|＞ϵ]≤2exp(-2ϵ2N)

这是因为机器学习模型并不是随意指定的函数关系，它是在M大小的假设空间中选择能最佳拟合训练数据的函数，如图1-9所示。这个选择过程（优化）会对上述不等式造成何种影响呢？

图1-9 在M个函数中进行最优选择的过程，使得E_in和E_out满足某个差距的概率增大了M倍

可以这样思考，在训练数据集上，E_in表现得非常优秀（E_in很小）的可能有两种：第一种是模型捕捉到了正确的关系函数；第二种是模型捕捉到了一个虚假的关系函数，只是该函数凑巧在收集到的有限训练样本上表现得不错，而实际并不是正确的（应用到未知样本上的预测错误很多）。一旦发生后一种情况，我们称犯了“小概率事件”错误（E_in和E_out的差距很大）。假设出现这种情况的概率为P，如果仅仅随机指定一种关系，出现“小概率事件”错误的概率是满足霍夫丁不等式的。但从M种关系可能中选择表现最好的，会使“小概率事件”错误的概率增大M倍。假设M个函数中有M-个在训练数据上表现良好（M-≤M），因为每个关系均以P的概率为“小概率事件”错误，且一旦某个关系出现“小概率事件”错误，我们肯定会选择它（因为它在训练样本上表现好），所以最终结果为“小概率事件”错误的概率增大M-倍。考虑到M-最多可以等于M，所以在M大小的假设空间中做优化学习，最多会使得E_in和E_out满足某个差距的概率增大M倍，即需要在上述不等式的右侧乘以M。

P[|E_in-E_out|＞ϵ]≤2Mexp(-2ϵ2N)

可见，模型的假设空间大小M极大地影响了大数定律在机器学习过程中的作用，它究竟和什么因素有关？让我们从两个实际案例来感受一下。

M函数的两个案例

假设空间的大小M究竟和什么因素有关呢？对于分类问题，给定样本数量，假设空间代表存在多少种样本分布，分类函数能正确地将每个类别的样本区分开。例如，对于二分类问题，若有两个样本，则共有4种样本分布（正正、正负、负正、负负），如果模型能将这四种情况均正确地分类，它的假设空间大小为4。换句话说，假设空间是一个模型的函数表示能力——能够完美地拟合多少种关系。假设空间越大，模型的表示能力越强，也就能更好地学习那些现实世界中的复杂关系。

案例6 线性二元分类

线性二元分类是使用一条直线区分两种可能或正或负的样本。形象地说，就是对散布在一张纸上的圆圈和叉叉，尝试画一条直线将两者分开。

对于N个样本，每个样本有正负两种分类可能，最理想的假设空间M有2N种分布，即正确地划分每种样本分布。但线性分类模型能够达到这个极限吗？

先来看看样本数量较少的简单场景，通过观察来猜测规律。

1）1个样本点：共有2种样本分布的可能（样本分布：该样本为正样本或负样本），全部可以用一条直线分割。

2）2个样本点：共有4种样本分布的可能（样本分布：正正、正负、负正、负负），全部可以用一条直线分割。

3）3个样本点：共有8种样本分布的可能（样本分布：在2个样本点的4种分布上，再加入一种新样本为正和一种新样本为负的情况），全部可以用一条直线分割。

4）4个样本点：共有16种样本分布的可能，其中有2种情况无法用一条直线分割，可分割的情况有14种，如下图所示。

通过观察，我们发现4个样本点不能全部可分。这仅仅是故事的开始，随着样本数量越来越多，不可分割的情况也越来越多。也就是说，线性二元分类的假设空间M随着样本量N的增长是小于2的指数次幂的。

P[|E_in-E_out|＞ϵ]≤2Mexp(-2ϵ2N)

其中，M达不到2的指数次幂增长。

因为霍夫丁不等式右侧有一个e指数次幂，如果M的增长达不到2的指数次幂，随着N的增大，不等式右侧依然会趋近于0（只是需要的样本量N更多）。也就是说，线性二元分类模型是满足大数定律的。如果基于大量数据学习出一个线性二分类模型，且它在训练数据上表现良好，那么它大概率是真实的（在未知数据上也会表现良好）。

案例7 二元凸多边形的分类模型

与案例6一样，样本或为正或为负，但可用凸多边形对样本做出分类。下面在一种略极端的样本分布场景下探讨凸多边形假设空间M的大小。

假设有n个数据点，它们分布在一个圆上，每个样本点均可为正样本或负样本，共有2n种可能。无论哪种可能，均可以用凸多边形将正负样本分开。如图所示，只要将所有的正样本用一个多边形连接起来，然后将该多边形略微外扩一点（从每个正样本点的位置略向外延展），它就会将所有的正样本点圈进来，而把所有的负样本点排除在外，即完美地区分开正负样本。

P[|E_in-E_out|＞ϵ]≤2Mexp(-2ϵ2N)

其中，M以2的指数次幂增长。

由此可见，凸多边形的分类模型的假设空间M的增长速度是2n。在这种情况下，大数定律的限制失效了。霍夫丁不等式的右侧并不会随着样本量N的增长而减少。也就是说，我们永远无法用这种假设空间学习到一种可从统计上相信的规律。无论真实的关系如何，均可以用凸多边形学习出一种将训练数据拟合得很好的关系，但它往往是虚假的。

由上述两个案例可见，假设空间的大小与两个因素相关，即假设H和样本量N，可以写成两者的函数M(H,N)，这称为增长函数。我们喜欢那些增长函数小于2的指数次幂的假设，因为在这种时候，学习才是可能的！