Training vs Testing
Recap and Preview
简单回顾一下前面几节课的内容：
- 第一节课，介绍了机器学习的定义，目标是找到最好的g，使g ≈ \approx ≈f,保证 E o u t ( g ) ≈ 0 E_{out}(g)\approx0 Eout(g)≈0
- 第二节课，介绍了如何让 E i n ≈ 0 E_{in}\approx0 Ein≈0,即使用PLA、pocket algorithm来实现
- 第三节课，介绍了机器学习的分类
- 第四节课，介绍了机器学习的可行性，通过统计学知识，证明了在一些假设前提下，证明了 E i n ( g ) ≈ E o u t ( g ) E_{in}(g)\approx E_{out}(g) Ein(g)≈Eout(g)
那么总的来说机器学习就是为了使 E i n ( g ) ≈ E o u t ( g ) ≈ 0 E_{in}(g)\approx E_{out}(g)\approx 0 Ein(g)≈Eout(g)≈0
当M很小的时候，由上节课介绍的霍夫丁不等式，得到 E i n ( g ) ≈ E o u t ( g ) E_{in}(g)\approx E_{out}(g) Ein(g)≈Eout(g)，即能保证第一个核心问题成立。但M很小时，演算法A可以选择的hypothesis有限，不一定能找到使 E i n ( g ) E_{in}(g) Ein(g)足够小的hypothesis，即不能保证第二个核心问题成立。当M很大的时候，同样由霍夫丁不等式， E i n ( g ) E_{in}(g) Ein(g)与 E o u t ( g ) E_{out}(g) Eout(g)的差距可能比较大，第一个核心问题可能不成立。而M很大，使得演算法A的可以选择的hypothesis就很多，很有可能找到一个hypothesis，使 E i n ( g ) E_{in}(g) Ein(g)足够小，第二个核心问题可能成立。
从上面的分析来看，M的选择直接影响机器学习两个核心问题是否满足，M不能太大也不能太小。
Effective Number of Lines
如果平面上只有一个点x1，那么直线的种类有两种：一种将x1划为+1，一种将x1划为-1：
平面上有两个点时，直线的种类有4种：
但是在平面有三个点的情况也会出现不能用一条直线划分的情况：
也就是说，对于平面上三个点，不能保证所有的8个类别都能被一条直线划分。那如果是四个点x1、x2、x3、x4，我们发现，平面上找不到一条直线能将四个点组成的16个类别完全分开，最多只能分开其中的14类，即直线最多只有14种：
Effective Number of Hypotheses
dichotomy（二分类）就是将空间中的点（例如二维平面）用一条直线分成正类（蓝色o）和负类（红色x）。令H是将平面上的点用直线分开的所有hypothesis h的集合，dichotomy H与hypotheses H的关系是：hypotheses H是平面上所有直线的集合，个数可能是无限个，而dichotomy H是平面上能将点完全用直线分开的直线种类，它的上界是 2 N 2^N 2N。接下来，我们要做的就是尝试用dichotomy代替M。
成长函数（growth function），记为 m H ( H ) m_H(H) mH(H)。
成长函数就是让我们找最大的dichotomy。也就是找之前对应effective lines的数量最大值。
针对一维的Positive Rays：
若有N个点，则整个区域可分为N+1段，很容易得到其成长函数 m H ( N ) = N + 1 m_H(N)=N+1 mH(N)=N+1。注意当N很大时， ( N + 1 ) < < 2 N (N+1)\lt\lt2^N (N+1)<<2N，这是我们希望看到的
针对一维的Positive Intervals：
它的成长函数可以由下面推导得出：
上面的成长函数中，蓝色的表示在N+1个节点中选择两个端点进行切割，两个端点之间为+1即 C 2 N + 1 C_2^{N+1} C2N+1,红色的表示不选择端点进行切割，即所有的节点都是-1.
这种情况下， m H ( N ) = 1 2 N 2 + 1 2 N + 1 < < 2 N m_H(N)=\frac{1}{2}N^2+\frac{1}{2}N+1\lt\lt2^N mH(N)=21N2+21N+1<<2N，在N很大的时候，仍然是满足的。
再来看这个例子，假设在二维空间里，如果hypothesis是凸多边形或类圆构成的封闭曲线，如下图所示，左边是convex的，右边不是convex的。那么，它的成长函数是多少呢？
当数据集D按照如下的凸分布时，我们很容易计算得到它的成长函数 m H = 2 N m_H=2^N mH=2N。这种情况下，N个点所有可能的分类情况都能够被hypotheses set覆盖，我们把这种情形称为shattered。也就是说，如果能够找到一个数据分布集，hypotheses set对N个输入所有的分类情况都做得到，那么它的成长函数就是 2 N 2^N 2N。
Break Point
我们已经知道：
对于2D perceptrons，我们之前分析了3个点，可以做出8种所有的dichotomy，而4个点，就无法做出所有16个点的dichotomy了。所以，我们就把4称为2D perceptrons的break point（5、6、7等都是break point）。令有k个点，如果k大于等于break point时，它的成长函数一定小于2的k次方。
break point的定义就是使 M H ( k ) ≠ 2 k M_H(k)\neq2^k MH(k)̸=2k 的k的最小值。那么根据该定义，我们可以得出：
通过观察，我们猜测成长函数可能与break point存在某种关系：对于convex sets，没有break point，它的成长函数是2的N次方；对于positive rays，break point k=2，它的成长函数是O(N)；对于positive intervals，break point k=3，它的成长函数是 O ( N 2 ) O(N^2) O(N2)。则根据这种推论，我们猜测2D perceptrons，它的成长函数 m H ( N ) = O ( N k − 1 ) m_H(N)=O(N^{k-1}) mH(N)=O(Nk−1)。如果成立，那么就可以用 m H m_H mH代替M，就满足了机器能够学习的条件。
总结
本节课，我们指出针对N个训练数据，最多只有 2 N 2^N 2N个hypothesis，由此引出了成长函数。针对不同的情况，成长函数也各有不同。对于我们学习的2D perceptrons，我们发现从某点开始是少于 2 N 2^N 2N次的。由此又引出break point的概念。