本节的主要内容来自Hsuan-Tien Lin的机器学习基石课程[1]。
泛化是指在训练集上得到的模型可以推广到整个数据集,也就是Eout≈Ein,就是要使坏事|Ein(h)−Eout(h)|>ϵ发生的概率足够小。
Generelization: Eout≈Ein possible, if mH(N) breaks somewhere and N large enough.
最大可能的mH(N)
如何通过断点k限定mH(N)的值?
由前文可得,正射线的断点是2,mH(2)=3;正区间的断点是3,mH(3)=7;2维感知器的断点是4,mH(4)=14。
如果最小断点k=2,在N=1,2,3,…的情况下,对任意的H而言,可能得到的最大mH(N)是多少呢?
- 若N=1,只有1个点,永远不存在2个点能被打碎的情况,因此mH(1)=21=2;
- 若N=2,由于最小断点k=2,不能打碎2个点,因此mH(2)<22=4,最多为3;
- 若N=3,3个点中任取2个点都不能被打碎时,最多可能的二分法有多少种?
- ……
当N=3,k=2时,如果mH(3)=3,可以肯定从3个点中任意抽取2个都不会被打碎,因为打碎2个点至少要4种二分类方法,因此mH(3)最少为3,可以从4开始考察。
.png)
对于4个二分类的情况,如上图所示。上图左的二分类使得x2和x3被打碎了;上图右修改了最后一种分类方法,任意两个点都没有被打碎,因此mH(3)最少为4。
还需考察mH(3)=5的情况。结果表明,mH(3)=5时总会让其中的2个点被打碎。因此,若N=3,k=2,最多可能的二分法只有4种。
上限函数
期望对mH(N)进一步进行限定, mH(N)≤maximum possible mH(N) given k≤poly(N)。
当断点为k时,将最大可能的mH(N)定义为上限函数(bounding function)B(N,k)。该上限函数和假设集H无关,不受感知器等特定分类器的约束,它的取值是所有H中的最大值。
mH(N)受假设集(分类器)H和样本点数目N的约束;B(N,k)受样本点数目N和断点k约束,而与假设集H无关。但是,如果知道假设集H的断点k,就可以用B(N,k)对mH(N)进一步约束,mH(N)≤B(N,k)。
.png)
当N≤k时B(N,k)的计算公式容易推导,当N>k时B(N,k)的计算比较复杂, B(N,k)={2NN<k2N−1N=kk−1∑i=1(Ni)N>k。
VC界
通过 P[∃h∈H s.t. |Ein(h)−Eout(h)|>ϵ]≤2mH(N)exp(−2ϵ2N) 证明VC界(Vapnik-Chervonenkis bound) P[∃h∈H s.t. |Ein(h)−Eout(h)|>ϵ]≤4mH(2N)exp(−18ϵ2N) 分三步,对应着3个常数的变化。
第一步:用E′in替换Eout

另抽取N个点的数据集D′计算E′in来估计Eout的值,E′in和Ein的取值如上图,以Eout为中心分布。12P[∃h∈H s.t. |Ein(h)−Eout(h)|>ϵ]对应着上图粉色区域的面积(取12是忽略对称的左半区域),在满足该条件下,上图淡绿区域对应着P[∃h∈H s.t. |Ein(h)−E′in(h)|>ϵ],于是显然有
12P[∃h∈H s.t. |Ein(h)−Eout(h)|>ϵ]≤P[∃h∈H s.t. |Ein(h)−E′in(h)|>ϵ]≤P[∃h∈H s.t. |Ein(h)−E′in(h)|>ϵ2]。
第二步:利用成长函数约束二分类情况的数量
上一步将问题转化为只考虑N个点数据集D和N个点数据集D′的问题,最多有mH(2N)种二分类情况,可进一步得到坏事儿发生概率的上界
P[∃h∈H s.t. |Ein(h)−Eout(h)|>ϵ]≤2P[∃h∈H s.t. |Ein(h)−E′in(h)|>ϵ2]≤2mH(2N)P[fixed h s.t. |Ein(h)−E′in(h)|>ϵ2]。
第三步:利用Hoeffding without Replacement约束
易知|Ein(h)−E′in(h)|>ϵ2和|Ein(h)−Ein(h)+E′in(h)2|>ϵ4等价,Ein(h)+E′in(h)2可以认为是out-sample数据的误差估计,所以直接利用Hoeffding可得
P[∃h∈H s.t. |Ein(h)−Eout(h)|>ϵ]≤2mH(2N)P[fixed h s.t. |Ein(h)−E′in(h)|>ϵ2]=2mH(2N)P[fixed h s.t. |Ein(h)−Ein(h)+E′in(h)2|>ϵ4]≤2mH(2N)⋅2exp(−2(ϵ4)2N)=4mH(2N)exp(−18ϵ2N)。
参考资料
- [1]H.-T. Lin, “Lecture 6: Theory of Generalization.” Coursera, 2014. [Online]