机器学习基石-Theory of Generalization

Theory of Generalization

Lecture5我们主要目的是证明hypothesis set是无限的情形下的Hoeffding的成立问题，我们最终通过一系列定义和推导得到成长函数和break point间的猜想，本节课我们主要解决这个问题的证明。

回顾

Restriction of Break Point

首先我们回到已经研究过的四类成长函数及其相关的break point：

下面我们研究下成长函数的影响因素，我们考虑break point K=2的情形（K=2，意味着N中任意两个点都被不能被shattered，shatter的意思是对N个点，能够分解为2^N种dichotomies)。

很明显，当N=1时，mH(N)=2,；当N=2时，由break point为2可知，任意两点都不能被shattered，mH(N)最大值只能是3；当N=3时，简单绘图分析可得其mH(N)=4，即最多只有4种dichotomies。

于是我们可以总结影响成长函数大小的因素主要有两个：取样的样本集大小N和break point K的大小。

那么，给定N和K,我们的思路是证明mH(N)的最大值的上界是多项式形式的，进而达到证明机器学习可行的目的。

Bounding Function: Basic Cases

我们引入一个新的函数B(N,K)，定义是在break point为K时，成长函数mH(N)可能的最大值，即为mH(N)的上界，于是我们接下来的目标是证明这个函数是多项式形式的。

然后我们试着填一下上面这张表，当k=1时，我们容易得出B(N,1)恒为1；当N

Bounding Function: Inductive Cases

下面我们来看看N>K的情形，我们以计算B(4,3)为例来推导完成表的下半部分。

我们首先写出B(4,3)对应的所有的dichotomy共11种情形，然后我们将这11钟情形做一个分类，分成orange（x1,x2,x3存在一致的情况）和purple（x1,x2,x3均不一致的情况）。

在dichotomy中我们去掉x4,去重后得到的维数为α（orange)和β（purple）。根据定义，B(4,3)是不允许任意三点被shatter的，所以α+β

另一方面，由于orange中x4是成对存在的，所以可以推出α是不允许两个点被shatter的，所有有α

于是我们可以得到B(4,3)的上界，进而得出一般形式的B(N,k)的上界公式，于是我们可以完成表格的下半部分。

根据递推公式，我们发现B(N,K)的上界函数满足多项式分布poly(N)，他的最高次幂为K-1次，于是我们完成了整个证明过程。

A Pictorial Proof

我们通过前述的结论推导出相应的Hoeffding公式，公式的证明比较复杂，本节内容不予展示，有兴趣的可以查阅相关资料查看。

本节课我们主要证明了成长函数满足多项式分布poly(N)这件事，我们研究了break point的性质，然后引入了成长函数上界函数的概念，通过通过证明后者满足poly(N)来达到目的，最终完成整个机器学习可行性的证明。