首页 > 代码库 > 加州理工学院公开课:雷蒙保罗MAPA泛化理论(第六课)

加州理工学院公开课:雷蒙保罗MAPA泛化理论(第六课)

课程简介:

本次课程主题为"泛化理论",介绍了机械学习相关课程,重点介绍与之相关的公式推导及其应用。是这一整套课程中最具理论的课程,如果读者理解了该部分内容,那么对于后面课程的理解将会有很大的帮助。

课程大纲:

1、证明 mH(N) 是多项式( Proof that mH(N) is polynomial )

2、证明 mH(N) 能够代替 M( Proof that mH(N) can replace M )


说明:以下证明均是针对二分类!


首先要弄明白的两个问题是为什么需要证明上述两个问题?

从之前的课程中我们知道根据 Hoeffdings 定理:p[|v-u|>ε] <= 2e^(-2Nε^2) 机器学习是有可能实现的,在样本数据变大的时候,我们可以利用样本内数据逼近样本外数据。然而机器学习是一个不断试错并且找到一个最符合的模型的过程,因此 Hoeffdings 定理不适用(该定理仅针对单一试验有效),根据联合界限,可以对 Hoeffdings 定理进行扩充:p[|v-u|>ε] <= 2Me^(-2Nε^2) 其中 M 是假设集的个数。由于对应一个模型,多数情况下其假设集都是无限大的,因此该公式失去了原有的意义了。然而我们通过观察可以知道,实际情况下,M 的值是有上界的,很多情况下,不同的假设都是互相重叠的。只要我们能够确定 M 的上界在一个合理的范围内,我们并可以利用机器进行学习,从而通过样本数据预测未知数据了。那么这个合理的范围是什么呢?答案是这个范围是在一个多项式的约束下的。只要能够证明 mH(N) 是多项式,那么我们并可以证明 mH(N) 能够代替 M ,所以我们需要证明上述两个问题。

1、证明 mH(N) 是多项式( Proof that mH(N) is polynomial )

为了证明 mH(N) 是多项式,我们只需要证明 mH(N) <= ... <= 多项式

首先我们定义一个函数:B(N,k) 表示有 N 个点,断点为 k 的模型的最大假设集数量。

接着我们对这个模型下的所有假设分为两类。

第一类 S1 :当前面的 N-1 个点全部归好类之后,剩下的第 N 个点唯一确定,要么是 +1 要么是 -1,因此最后一个点只能产生一种结果。

第二类 S2 :当前面的 N-1 个点全部归好类之后,剩下的第 N 个点还不能确定,可能是 +1 类,也可能是 -1 类,因此最后一个点将产生两种结果:S2+ 和 S2-。因此:B(N,k) = α + 2β。如下图所示 :

       

则有 α + β <= B( N-1, k )。根据定义,S2+ 和 S2- 是对称的关系,且只有在第 Xn 个点上出现分类不一致,其他情况下点的分类是一一对应的。

因此当除去最后一个点的时候有 S2+ 和 S2- 的分类结果是一致的。因此在只有 N-1 个点的情况下,假设集的最多数量是:α + β。又由于 只有 N-1 个点,所以必有在 N-1 个点的情况下,断点为 k 时,假设集数量 <= B(N-1,k),因此有:α + β <= B( N-1, k )

对于 S2- ,当点数减少一个的时候,必然有 β <= B(N-1,k-1) 。为什么 K 要减 1 呢,即为什么S2- 的断点是 k-1? 证明如下:

反证法:假设  S2- 的断点是 K ,那么如果 N-1 个点大于K 的话,假设集的数量将大于 2^(k-1),当加上一个点后,假设集的数量将大于 2 * 2^(k-1)即 2^k 个,由于原假设集的断点是 k,矛盾,因此 β <= B(N-1,k-1)。

因此我们有:B(N,k) <= B(N-1,k) + B(N-1,k-1)。

数值解如下图所示:

然而我们更希望能够得到该不等式的解析解,其实前人已经证明:

现在我们就利用归纳法来证明该不等式的正确性。

证:

1、当 K = 1 的时候,成立。当 N = 1 的时候,成立。

2、当 K >=1, N >= 1 的时候:

我们需要证明:

我们令 i 从 1 开始到 k -1 ,则

综上,假设成立,证毕。

于是我们有:

 

只要我们能够证明不等式右边是多项式便可以完成我们的证明了。我们知道多个多项式相加的结果仍然为多项式。而且最高次项数为和中最高次数项对应的项。观察上述不等式的右边,是由一系列的和组成的一个式子。其中每一个和的最高项次数与 i 有关,i 越大,项越大,而且最大的项次数为:(k-1) 。因此不等式右边的最高项次数是:(k-1)。所以不等式右边是一个多项式,因此B(N,k)是一个多项式,证毕。


2、证明 mH(N) 能够代替 M( Proof that mH(N) can replace M )

课程中并没有给出严格的证明,只给出了一些关键步骤,严格的证明在附录里面(找不到,希望找到的告知一声,谢谢)。

如下:

1、mH(N)与重叠的关系。

我们知道之所以 M 非常大是因为我们利用了联合界限,但是在通常情况下,不同的假设存在着重叠部分,因此我们通过 mH(N)描述重叠部分:

每一个方块表示外部数据,有颜色部分是对外部数据预测错误的点。第一幅图中是利用了 Hoeffdings 定理得出来的错误部分。第二幅图结合 Hoeffdings 定理和联合界限的概念得出来的。第三幅图是因为存在重叠,所以表示的是 mH(N) .

2、我们应该对 Eout 做点什么?如下图所示,左边的图案是我们开始时使用的方法:从外部数据中随机取出部分数据作为样本进行学习,然后根据样本的学习结果对未知的外部数据进行预测。而右边的图表示多次取样,通过两个样本来预测,从而提高了准确率。具体情况可能需要参考证明部分(没有找到...)

        

3、把上述问题综合起来我们有:

第二条公式是我们想要的,图中的红色部分说明我们对原有公式进行了改变,只要是为了方便证明,但是不影响我们的结论。


3、总结:

该课程主要从理论方面证明了只要存在一个断点,则假设集的数量便受多项式的限制,我们可以证明,当假设集的数量是多项式的时候,可以用m(H) 代替 M,从而可以得出机器学习的可行性。




加州理工学院公开课:雷蒙保罗MAPA泛化理论(第六课)