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

Myth丶恋晨 2022-06-12 12:00 167阅读 0赞

# 泛化理论 #

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

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

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

> N=3，k=2的生长函数值。
> 
> 如图a)表示在三个样本点时，可以随意选择一种二分的情况，不会违反任意两个样本点出现四种不同的二分类情况（因为突破点是2）；
> 
> 如图b)表示在a)的基础上，添加不与之前重复的一种二分类，出现了两种不冲突的二分类，也没有违反任意两个样本点出现四种不同的二分类情况；
> 
> 如图c) 表示在b)的基础上，再添加不与之前重复的一种二分类，出现了三种不冲突的二分类；
> 
> 如图d) 表示在c)的基础上，再添加不与之前重复的一种二分类，问题出现了，样本x2x3出现了四种不同的二分情况，和已知条件中突破点k=2矛盾（即，对于任意2个样本，不能得到完全二分类，最多只能出现三种二分类），因此将其删去。
> 
> 如图e) 表示在c)的基础上，再添加不与之前重复的一种二分类，此时同样也没有任何问题，不会违反任意两个样本点出现四种不同的二分类情况；
> 
> 如f) 表示在e)的基础上，再添加不与之前重复的一种二分类，问题又出现了，样本x1x3出现了四种不同的二分情况，和已知条件中k=2的条件不符（最多只能出现三种二分类），因此将其删去。
> 
> ![a][] ![b][]  
> a) b)
> 
> ![c][] ![d][]  
> c) d)
> 
> ![e][] ![f][]  
> e) f)
> 
> 当N=3，k=3时，则只有当x1,x2,x3=×××的时候，存在三个样本得到完全二分类的情况，那么他的生长函数mH(3)=7。

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

## 上限函数 ##

在考虑替换基于Hoeffding不等式的PD\[BADi\]≤2M⋅exp(⋅)中的M的时候，由于后半部分是指数级的下降，我们只要证明替换M的生长函数mH(N)是一个**多项式**，那么指数级的下降就可以抵消掉多项式M的作用了。

为了证明这个，我们也没有必要找出mH(N)的具体表达式，我们只需要证明mH(N)≤⋯≤polynomial即可。

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

加州理工的视频中用一种更加抽象的说法来证明，而台大的似乎用的是一种更加具体的方式来解释。

我们可以举一个例子，但是我并不打算把它推广到更广泛的地步。

先列出N=4,k=3的所有二分类情况，如下图所示。

![132240126833418.png][]

将之重新排列之后，我们为了得到一种通过递归的方式来计算B(N,k)的算法，我们将x4分割开来，从而可以观察x1∼x3与整个矩阵的关系。

![132240159489885.png][]

上图紫色部分中x1∼x3的表示方法仅出现一次，假设些二分类的个数为α。  
上图橙色部分中x1∼x3由两对两对出现，只保留x4的不同。假设其中有β对。

那么我们就可以得到总行数

B(4,3)=α\+2β=3\+2×4=11

注意，k=3意味着在样本点为3时，不能满足完全二分的情形。那么我们观察在样本数为3时，这11种分类会有何变化，不妨假设这三个样本是x1∼x3，于是只剩如下图所示的7种二分类情形。

![132240167765999.png][]

其中橙色部分，进行去重后，就合并成了4种二分类情况，紫色部分不变依然为3种二分情况。因为该图是从N=4,k=3获得，在样本数为3时，其一定不能满足完全二分（因为若是满足完全二分，则N=4,k=3的情况也是不合法的），因此α与β一定满足：

α\+β≤B(N−1,k)=B(3,3)

继续观察橙色部分的区域，如图所示。

![132240189958355.png][]

相似上面的证明方式。  
假设x1∼x3三个样本在如上图所示的四种二分类情况下，满足任意两个样本都可完全二分类。  
将其中任意两列取出，同之前被删除的x4列相结合，一定可得到一种三个样本都满足完全二分类的情形（因为不论是哪两列与x4相结合都会得到8种二分类，每一行二分类都对应两个不同标记的x4，因此为8种。且两列四行的二分类是全完二分的，在此基础上加上不同属性的列，应该也不会重复，因此一定也是全完二分的）。  
但是此结论和原始矩阵中任意三个样本不能完全二分冲突了，因此假设不成立，即在图中一定存在某两个样本点不能完全二分的情况，因此得出如公式：

β≤B(N−1,k−1)=B(3,2)

结合公式(1)(2)(3)，我们可以得到

B(N,k)==≤α\+2β(α\+β)\+βB(N−1,k)\+B(N−1,k−1)

我们没法证明小于的情况是不存在的，但是好在我们只需要得到一个上限就足够了。

![132240219485853.png][]

那么我们可以明显地看出来这是一个二项式系数，那么也可以得到通项公式：

B(N,k)≤∑i=0k−1CiN

我们再通过数学归纳法对通项公式进行一番证明。

在k=1的时候，公式成立：

B(N,1)=1=CiN≤∑0i=0CiN

那么我们假设在k(≥2)的时候，结果成立：

B(N−1,k)≤∑i=0k−1CiN−1B(N−1,k−1)≤∑i=0k−2CiN−1

结合公式(4)(5)，则有

B(N,k)≤≤====B(N−1,k)\+B(N−1,k−1)∑i=0k−1CiN−1\+∑i=0k−2CiN−11\+∑i=1k−1CiN−1\+∑i=1k−1Ci−1N−11\+∑i=1k−1\[CiN−1\+Ci−1N−1\]1\+∑i=1k−1CiN∑i=0k−1CiN

结果成立。

那么我们就已经证明了mH(N)的上限是一个Nk−1的多项式。

## 替换M之后 ##

我们原本的公式为

P\[|Ein(g)−Eout(g)|>ϵ\]≤2 M e−2ϵ2N

我们想要将之替换为

P\[|Ein(g)−Eout(g)|>ϵ\]≤2 mH(N) e−2ϵ2N

#### 坏数据的重叠 ####

如下图(a)所示，整个矩阵表示的是输入空间，小点表示一个输入样本，彩色图像表示通过Hoeffding不等式得到的坏数据。  
如下图(b)所示，用的是联合边界得到的坏数据，因为从来不考虑坏数据的重叠性，它非常迅速地沾满了整个输入空间。  
如下图(c)所示，采用的是生长函数代替联合上限对坏的数据进行处理。相比于联合边界，生长函数通过二分类的去重等方式将一个输入空间的变化情况减少，从而使得对于一个坏数据而言可能会被若干个假设所占用。

![SouthEast][] ![SouthEast 1][] ![SouthEast 2][]

但是这又引发了一个问题，对于一个坏数据而言，它不仅仅与我们的采样有关，而与整个输入空间有关。坏数据意味着，这个样本点偏离了Eout(g)，而Eout(g)与整个输入空间有关，我们是没有办法通过采样的点计算Eout(g)的。

#### 如何处理Eout ####

我们采用的是将N扩大两倍的方法。

P\[|Ein(g)−Eout(g)|>ϵ\]≤2 2mH(2N) e−2⋅116ϵ2N

按先后循序，分三步简单说明一下这些变化的原因。

1.  用E′in代替Eout。
    
    因为Ein是训练样本，所以可能性是有限的，因为假设空间的种类被生长函数约束了，而样本大小基本固定，所以错误样本也最多只有mH(h)种；但是对于Eout(h)的可能性还是无限多，因为总体的样本是无限大的，错误样本也自然是无限多。
    
    为了解决这个问题，提出了影子数据的概念(ghost data)，我们将样本数扩大两倍，用其中新的样本取代整个样本去近似求解在无限大的数据中Eout的值，记作E′in。（我不是很懂为什么这样做，下面的解释是摘抄的）
    
    > 下图表示![132240328546689.png][]和![132240335114088.png][]的分布情况，其中![132240342612459.png][]为它俩的分布中心，假设数据D的情况下![132240345117915.png][]很大，从图中不难看出，再抽取一次数据![132240348545344.png][]得到的![132240351512086.png][]很大的几率，最多只有条件![132240354017542.png][]很大的一半概率，意味着![132240356202243.png][]和![132240358395943.png][]很接近的几率最多只有![132240361515913.png][]很大这个条件的一半（因为从该图中得知![132240365265099.png][]和![132240368088014.png][]只可能变得小于![132240370421242.png][]），即![132240373089928.png][]很小的几率最多只有![132240375898141.png][]很大这一几率的一半。
    > 
    > ![132240383084756.png][]
    > 
    > 换句话说![132240377928612.png][]很大的几率至少是![132240380113313.png][]很大这一几率的一半：
    
    12P\[|Ein(h)−Eout(h)|>ϵ\]≤P\[|Ein(h)−E′in(h)|>ϵ\]
    
    增加一个更强的约束条件（我也不懂这个是怎么就加上去的）：
    
    P\[|Ein(h)−Eout(h)|>ϵ\]≤2P\[|Ein(h)−E′in(h)|>ϵ2\]
2.  分解假设空间的种类
    
    可以知道Ein的可能性与样本D有关，而E′in的可能性与样本D′有关，因此整个假设空间的种类可以写成|H(x1,…,xN,x′1,…,x′N)|，由上几章的说明可以知道，其上限最大为生长函数mH(2N)。  
    因此坏事情的发生概率就变成了:
    
    BAD≤2P\[|Ein(h)−E′in(h)|>ϵ2\]≤2⋅mH(2N)2P\[|Ein(h)−E′in(h)|>ϵ2\]
3.  使用无取回的霍夫丁。
    
    还是用小球和罐子的那个例子解释，罐子中不再是无限多个小球，而是2N个小球，选择N个小球而留下另外N个，可以通过得出:
    
    |Ein−E′in|>ϵ2⇔|Ein−E′in\+Ein2|>ϵ4
    
    最终得到公式
    
    BAD≤=≤2⋅mH(2N)2P\[|Ein(h)−E′in(h)|>ϵ2\]2⋅mH(2N)2P\[|Ein−E′in\+Ein2|>ϵ4\]2⋅2mmathcalH(2N)e−2⋅(ϵ4)2N
    
    至此说明了一个在机器学习领域很著名的理论——V-C上界制（Vapnik-Chervonenkis bound）。

[a]: http://images.cnitblog.com/blog/489652/201502/132240036834967.png
[b]: /images/20220612/909c99fecd6a4fca91e0488d7516fa81.png
[c]: http://images.cnitblog.com/blog/489652/201502/132240045268608.png
[d]: /images/20220612/6330853f2cbb4eafbf3085187ed698d2.png
[e]: http://images.cnitblog.com/blog/489652/201502/132240054019707.png
[f]: /images/20220612/f824629048d7411489eb56d219478663.png
[132240126833418.png]: /images/20220612/c5cfa0e3fab648eab42b34b694834b39.png
[132240159489885.png]: /images/20220612/d9d270ed66634a7d8139d63807191ca4.png
[132240167765999.png]: /images/20220612/dee104d457e3417c9c2bc9fb088570f2.png
[132240189958355.png]: /images/20220612/30b8c90cea8f40168c3fc8a30bb2d937.png
[132240219485853.png]: /images/20220612/1effbdc646384f23ab5d5cd3ec977107.png
[SouthEast]: https://img-blog.csdn.net/20170722205651786?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzAwNzkwMA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: https://img-blog.csdn.net/20170722210043720?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzAwNzkwMA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: /images/20220612/f9a4f49469554bc8a19a472edaaa377d.png
[132240328546689.png]: http://images.cnitblog.com/blog/489652/201502/132240328546689.png
[132240335114088.png]: http://images.cnitblog.com/blog/489652/201502/132240335114088.png
[132240342612459.png]: http://images.cnitblog.com/blog/489652/201502/132240342612459.png
[132240345117915.png]: http://images.cnitblog.com/blog/489652/201502/132240345117915.png
[132240348545344.png]: http://images.cnitblog.com/blog/489652/201502/132240348545344.png
[132240351512086.png]: http://images.cnitblog.com/blog/489652/201502/132240351512086.png
[132240354017542.png]: http://images.cnitblog.com/blog/489652/201502/132240354017542.png
[132240356202243.png]: http://images.cnitblog.com/blog/489652/201502/132240356202243.png
[132240358395943.png]: http://images.cnitblog.com/blog/489652/201502/132240358395943.png
[132240361515913.png]: http://images.cnitblog.com/blog/489652/201502/132240361515913.png
[132240365265099.png]: http://images.cnitblog.com/blog/489652/201502/132240365265099.png
[132240368088014.png]: http://images.cnitblog.com/blog/489652/201502/132240368088014.png
[132240370421242.png]: http://images.cnitblog.com/blog/489652/201502/132240370421242.png
[132240373089928.png]: http://images.cnitblog.com/blog/489652/201502/132240373089928.png
[132240375898141.png]: /images/20220612/cfb62fbc95174bb6a5c48f7417961216.png
[132240383084756.png]: /images/20220612/51071426d1884298a74dbb0e027bfc68.png
[132240377928612.png]: http://images.cnitblog.com/blog/489652/201502/132240377928612.png
[132240380113313.png]: /images/20220612/9c2fd8f5131d487f86a1028f1764afb2.png