一、限界函数

若的断点为，即个数据点不能被给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 the have 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维及以上维数的感知器算法呢？