林轩田机器学习基石Lecture 6: Theory of Generalization

@Lecture 6: Theory of Generalization

Restriction of Break Point

确定假设H的成长函数是限定的，也就是H关于样本个数N的成长函数，如果mH(N)<2N,则存在break point

H的个数要满足任意k个point不能完全shatter的条件

Bounding Function: Basic Cases

扩展到无论分类规则是什么，证明B（N,K)都远小于N的多项式
B（N,K）满足:B(N,1）=1， 当N<K时，B（N,K）=2的N次方，当N=K时，B（N,K）=2的N次方-1
注意，B是mH的上限，不一定相等

Bounding Function: Inductive Cases

继续填表，求B（4，3），看B(4,3)和B（3，？）的关系

分开看a+beta 和a的限制
因此，放缩后就可以得到B（N,K）的上界

相当于经过上述证明，我们找到了H的成长函数mH的上限函数的上限，由此证明出来mH是远小于2的N次方的，会被N的多次项函数bound住

A Pictorial Proof

把mH会被N的多项式bound住代到坏事情发生的公式里面

第一步，因为上图公式里面的Eout(h)是一个未知的，需要替换掉，思路，拿在in的数据里面的再次取样得到的E’in代换Eout，因为Ein的概率期望为Eout

第二步，使用mH来衡量坏事发生概率的重叠度

第三步通过抽样还替换

到这里就证明了随着在2维空间的判别问题上，只要存在break point,H的个数会被bound住，Ein和Eout的差距也会被bound住，也就是说N的个数足够大时，Ein和Eout的值相差不会太大，选看到的样本上的Ein最小的h,在看不到的数据上的表现应该也是比较好的,机器学习算法PLA可行。