1 回顾

上一节我们证明了，当假设空间的大小是M时，可以得到概率上界：

即，只要训练数据量N足够大，那么训练集上的Ein与真实的预测错误率Eout是PAC（大概率）接近的。

但是，我们上面的理论只有在假设空间大小有限时才成立，如果假设空间无限大，右边的概率上界就会变成无限大。

事实上，右边的边界是一个比较弱的边界，这一节我们要找出一个更强的边界，来证明我们的机器学习算法对于假设空间无限大的情形仍然是可行的。

2 成长函数

对于一组给定的训练集x1,x2,...,xN。定义在假设空间H上面对应的二划分函数H(x1，x2，......，xN)，表示假设空间里的所有h能够把训练集做多少种的二划分（上限是2^N种）。

例如，假设空间是平面上的所有线，训练数据集是平面上的N个点，则有：

N = 1 时，有2种划分方式：

N = 2时，有4种划分方式：

N = 3 时， 有8种划分方式：

N = 4时，有14种划分方式（因为有两种是不可能用一条直线划分出来的）：

…………

另外，划分数与训练集有关，（例如N=3时，如果三个点共线，那么有两种划分就不可能产生，因此只有6种划分而不是8种）：

为了排除对于训练数据的依赖性，我们定义成长函数：

5 理解机器为什么能学习（二）

原文：http://www.cnblogs.com/coldyan/p/6245054.html