5-Training versus Testing

以期末考试为例子，我们考试前做了大量的习题以及校对答案（training），就是为了在期末考试取得好的成绩（testing）。Ein指的是我们的成绩， Eout是我们对课程的理解， 我们希望这两者的偏差不要太大。 稍微不同的是平时的训练有M个hypothesis， 我们一直在微调，矫正我们的hypothesis， 而到了期末考试的时候我们的hypothesis已经fixed了。

对错误的hypothesis， 它们是存在很大的overlapping 的， 直接相加来确定上界其实是最大的上界

在分类问题中。 Eout就是分界线与实际的分界线夹成的面积的大小， Ein就是统计这两个区域中的point占所有的point的占比。 并且， 稍微改动hypothesis（从蓝线到绿线）， 对error的影响是比较小的， 因为也只有很少的点会落到从蓝线到绿线的变化区域（黄色）上面。

之前假设输入空间是无穷的， 但是我们希望考虑有限的输入空间， 并且计算处dichotomy的数量(Hypothesis) ， 它也不再是无穷的了， 而是2^N（对于二分类的情况来说）。 我们用growth function来衡量hypothesis的数量。

在没有共线的情况下， N=3 的话所有情况都能被一根线划分， 因此是8. 在N=4的情况下， 图中阐述了一种不能被一根线划分的情况， 同样的，将蓝圈与红点置换可以得到另外一种不能被划分的情况， 所以总共是2^4 - 2 = 14.

接下来， 三个例子。 第一个是一维的线上， -1类在左边， +1类在右边， a可能的放置位置是N+1；第二个是在一维的线上， +1类在中间， -1类在两边，除了(N+1)选2， 还得考虑interval为空的情况； 第三个是一个凸集， 在凸集里面的点为+1， 外边的点为-1， 我们可以将+1的点两两连接，就构成了分界面， 这就意味着所有情况都是可分的， 因此是2^N。 Note： 如果H能产生所有能划分数据X的hypothesis h， 称H能打散X (X = x1, x2, x3...)。

break point. 一个大小为k的数据集不能被H打散， k就是H的break point。事实上， 估计growth function是很困难的， 而break point提供了另外的便利。对于二维的perception， break point就是4.

没有break point意味着hypothesis能够拟合所有的data， 但是可能意味着generalize的能力差； 而拥有break point意味着growth function是polynomial的， Hoeffding 不等式的右边是在一个小的范围内的， 模型泛化能力好。

Puzzle， 一个例子。x是0/1，用不同的点来表示。这个Puzzle的限制是对于其中任意的两个column的break point是2， 这意味着不能枚举完全的4中情况00, 01, 10, 11, 否则2就不是它的break point了。 所以对x1, x2, x3我们必须比较两两的column来符合这种constraint， 最终只有4个column符合。