一、限界函数
若的断点为
，即
个数据点不能被
给shatter，那么
个数据点也不能被
给shatter，即
也是
的断点。如果给定的样本数
是大于等于
的，易得
，且随着
的增大，其小得越来越多。
图1.1 断点相关1
图1.2 断点相关2
当断点为时，记最大可能的成长函数
为bound函数，记为
，其只和
、
有关。
注意比较，发现bound函数比起成长函数消除了。如果无断点，自然没有
什么事；如果断点为
，那么
是给定
下，在
上可能的最大假设类数；
是不限
下，在
上可能的最大假设类数。
，只和样本数
和断点
有关。注意这里的
要求有相同的
。
图1.3 限界函数的定义
通过数学归纳法可证得：实际被
所框住。
图1.4 数学归纳法1
图1.5 数学归纳法2
既然成长函数的上限被的多项式给框住，易得，如果断点存在的话，成长函数是多项式型的，证明了上一节的猜想。
图1.6 常见的假设集对应的限界函数
二、VC边界
再看保证和
的不等式，可以证得：
图2.1 概率上限的最终形式
证明如下：
- 用和训练集同样大小的测试集上的表现替代整体输入空间上的表现，认为使得训练集内和整体表现差异过大的坏数据也会使得训练集和测试集上的表现差异过大；
这里做了2件事：
一是用有限的训练集+有限的测试集替代了无限的输入空间，将无限的变为数量为
的有限数据集；
二是用完美划分该有限数据集的模式代替了完美划分整个输入空间的模式
。这一步实际是进行了松弛操作，因为
图2.2 推导1
- 用有限类数
替代无限
；
图2.3 推导2
- 使用不放回的霍夫丁不等式。
对应于在取小球实验里不放回地抽取，取出的橘色小球频率和罐子里剩余的橘色小球概率依旧概率近似相等。因为 the inequalities also hold when thehave been obtained using sampling without replacement; in this case the random variables are not independent anymore.（来自维基百科）
图2.4 推导3
最终得到VC bound：
图2.5 VC边界
所以，2维感知器算法在训练集上学习到的
泛化到整个输入空间
上是概率近似可行的。
那3维及以上维数的感知器算法呢？
