机器学习和数据挖掘（6）：雷蒙保罗MAPA泛化理论

本文主要是介绍机器学习和数据挖掘（6）：雷蒙保罗MAPA泛化理论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

泛化理论

上一章中提到的生长函数 $m_{\mathcal H}(N)$ 的定义：假设空间在 $N$ 个样本点上能产生的最大二分（dichotomy）数量，其中二分是样本点在二元分类情况下的排列组合。

上一章还介绍了突破点（break point）的概念，即不能满足完全分类情形的样本点个数。不存在 $k$ 个样本点能够满足完全分类情形，完全二分类情形（shattered）是可分出 $2^N$ 种二分类（dichotomy）的情形。

关于突破点可以举一个例子。

$N=3，k=2$ 的生长函数值。

如图a)表示在三个样本点时，可以随意选择一种二分的情况，不会违反任意两个样本点出现四种不同的二分类情况（因为突破点是2）；

如图b)表示在a)的基础上，添加不与之前重复的一种二分类，出现了两种不冲突的二分类，也没有违反任意两个样本点出现四种不同的二分类情况；

如图c) 表示在b)的基础上，再添加不与之前重复的一种二分类，出现了三种不冲突的二分类；

如图d) 表示在c)的基础上，再添加不与之前重复的一种二分类，问题出现了，样本 $x_2x_3$ 出现了四种不同的二分情况，和已知条件中突破点 $k=2$ 矛盾（即，对于任意 $2$ 个样本，不能得到完全二分类，最多只能出现三种二分类），因此将其删去。

如图e) 表示在c)的基础上，再添加不与之前重复的一种二分类，此时同样也没有任何问题，不会违反任意两个样本点出现四种不同的二分类情况；

如f) 表示在e)的基础上，再添加不与之前重复的一种二分类，问题又出现了，样本 $x_1x_3$ 出现了四种不同的二分情况，和已知条件中k=2的条件不符（最多只能出现三种二分类），因此将其删去。

a) b)

c) d)

e) f)

当 $N=3，k=3$ 时，则只有当 $x_1,x_2,x_3=\times\times\times$ 的时候，存在三个样本得到完全二分类的情况，那么他的生长函数 $m_{\mathcal H}(3)=7$ 。

还有一个更简单的例子，假设突破点 $k=1$ ，在样本数为3时，最大的二分类个数是多少？答案是1，可以想象，在样本为1时，只有一种分类情形，假设这种情形是正，则以后所有样本也为正，才能满足上述条件，所以样本N不论为多少，其最大二分类数都是1。

上限函数

在考虑替换基于Hoeffding不等式的 $P_D[BAD_i]\leq 2M·exp(·)$ 中的M的时候，由于后半部分是指数级的下降，我们只要证明替换M的生长函数 $m_{\mathcal H}(N)$ 是一个多项式，那么指数级的下降就可以抵消掉多项式M的作用了。

为了证明这个，我们也没有必要找出 $m_{\mathcal H}(N)$ 的具体表达式，我们只需要证明 $m_{\mathcal H}(N) \leq\dots\leq polynomial$ 即可。

所以我们提出了一个函数，上限函数(bounding function)， $B(N,k)$ 。其定义为在最小突破点为k时，表示成长函数 $m_{\mathcal H}(N)$ 最大值的函数。此函数将成长函数从各种假设空间的关系中解放出来，不用再去关心具体的假设，只需了解此假设的突破点，突破点相同的假设视为一类，抽象化成长函数与假设的关系。