机器学习:泛化理论

| 研究学术  | 机器学习理论 

本节的主要内容来自Hsuan-Tien Lin的机器学习基石课程[1]

泛化是指在训练集上得到的模型可以推广到整个数据集,也就是EoutEin,就是要使坏事|Ein(h)Eout(h)|>ϵ发生的概率足够小。

Generelization: EoutEin possible, if mH(N) breaks somewhere and N large enough.

最大可能的mH(N)

如何通过断点k限定mH(N)的值?

由前文可得,正射线的断点是2mH(2)3;正区间的断点是3mH(3)7;2维感知器的断点是4mH(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=33个点中任取2个点都不能被打碎时,最多可能的二分法有多少种?
  • ……

N=3,k=2时,如果mH(3)3,可以肯定从3个点中任意抽取2个都不会被打碎,因为打碎2个点至少要4种二分类方法,因此mH(3)最少为3,可以从4开始考察。

4个二分类的情况
图 1: 4个二分类的情况 [PNG]

对于4个二分类的情况,如上图所示。上图左的二分类使得x2x3被打碎了;上图右修改了最后一种分类方法,任意两个点都没有被打碎,因此mH(3)最少为4。

还需考察mH(3)=5的情况。结果表明,mH(3)=5时总会让其中的2个点被打碎。因此,若N=3,k=2,最多可能的二分法只有4种。

上限函数

期望对mH(N)进一步进行限定, mH(N)maximum possible mH(N) given kpoly(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)

上限函数计算表
图 2: 上限函数计算表 [PNG]

NkB(N,k)的计算公式容易推导,当N>kB(N,k)的计算比较复杂, B(N,k)={2NN<k2N1N=kk1i=1(Ni)N>k

VC界

通过 P[hH s.t. |Ein(h)Eout(h)|>ϵ]2mH(N)exp(2ϵ2N) 证明VC界(Vapnik-Chervonenkis bound) P[hH s.t. |Ein(h)Eout(h)|>ϵ]4mH(2N)exp(18ϵ2N) 分三步,对应着3个常数的变化。

第一步:用Ein替换Eout

替换掉out-sample误差
图 3: 替换掉out-sample误差 [PNG]

另抽取N个点的数据集D计算Ein来估计Eout的值,EinEin的取值如上图,以Eout为中心分布。12P[hH s.t. |Ein(h)Eout(h)|>ϵ]对应着上图粉色区域的面积(取12是忽略对称的左半区域),在满足该条件下,上图淡绿区域对应着P[hH s.t. |Ein(h)Ein(h)|>ϵ],于是显然有

12P[hH s.t. |Ein(h)Eout(h)|>ϵ]P[hH s.t. |Ein(h)Ein(h)|>ϵ]P[hH s.t. |Ein(h)Ein(h)|>ϵ2]

第二步:利用成长函数约束二分类情况的数量

上一步将问题转化为只考虑N个点数据集DN个点数据集D的问题,最多有mH(2N)种二分类情况,可进一步得到坏事儿发生概率的上界

P[hH s.t. |Ein(h)Eout(h)|>ϵ]2P[hH s.t. |Ein(h)Ein(h)|>ϵ2]2mH(2N)P[fixed h s.t. |Ein(h)Ein(h)|>ϵ2]

第三步:利用Hoeffding without Replacement约束

易知|Ein(h)Ein(h)|>ϵ2|Ein(h)Ein(h)+Ein(h)2|>ϵ4等价,Ein(h)+Ein(h)2可以认为是out-sample数据的误差估计,所以直接利用Hoeffding可得

P[hH s.t. |Ein(h)Eout(h)|>ϵ]2mH(2N)P[fixed h s.t. |Ein(h)Ein(h)|>ϵ2]=2mH(2N)P[fixed h s.t. |Ein(h)Ein(h)+Ein(h)2|>ϵ4]2mH(2N)2exp(2(ϵ4)2N)=4mH(2N)exp(18ϵ2N)

参考资料

  1. [1]H.-T. Lin, “Lecture 6: Theory of Generalization.” Coursera, 2014. [Online]

脚注


打赏作者


上一篇:机器学习:训练与测试     下一篇:机器学习:VC维