停止点对成长函数值的限制
如果对于某个\(\mathcal{H}\)，其停止点\(k=2\)，这透露了什么信息？这意味着当\(N=1\)时，可以产生两种二分法分类器，\(m_\mathcal{H} = 2\)；但是当\(N=2\)时，由于达到了停止点，由定义必然有\(m_\mathcal{H} (N) < 2^2 = 4\)，因此最多产生三种分类器。
那么当\(N=3\)呢？我们把分类器集合先置为空集，然后一点点加入可能的分类器来看
- 第一个分类器，将\({\bf x}_1, {\bf x}_2, {\bf x}_3\)分别标记为\(\circ,\circ,\circ\)，这个分类器是合法的。因为任意取两个\({\bf x}_i\)只有一种组合，没有被\(\mathcal{H}\)打散，保持了停止点的性质
- 第二个分类器标记为\(\circ,\circ,\times\)，也合法
- 第三个分类器标记为\(\circ, \times, \circ\)，仍然合法
- 第四个分类器，此时要小心。如果标记为\(\circ,\times, \times\)，那么结合前面已经有的分类器，如果把\({\bf x}_1\)去掉，看\({\bf x}_2\)和\({\bf x}_3\)组合的情况，就会有\(\{\circ,\circ\}\)、\(\{\circ,\times\)}、\(\{\times, \circ\}\)、\(\{\times,\times\}\)四种情况，即这两个输入被\(\mathcal{H}\)打散。因此这样的分类器打破了停止点的性质，是非法的。经过分析可知第四个分类器只能标记为\(\times,\circ,\circ\)
- 第五个分类器，此时只有三个选择（因为\(\circ,\times, \times\)已经在上一步判定为不可行），可以逐个考察
- 标记为\(\times,\circ,\times\)是不行的，因为\(\mathcal{H}\)打散了\({\bf x}_1\)和\({\bf x}_3\)
- 标记为\(\times,\times,\circ\)是不行的，因为\(\mathcal{H}\)打散了\({\bf x}_1\)和\({\bf x}_2\)
- 标记为\(\times,\times,\times\)是不行的，因为\(\mathcal{H}\)还是打散了\({\bf x}_1\)和\({\bf x}_2\)
即当\(N=3\)时，最多产生四种分类器。因此我们可以初步得到一个推论，即只要出现了停止点\(k\)，它就会对所有\(N>k\)时最大可能的成长函数\(m_\mathcal{H}(N)\)施加了一些限制。这样就可以得出一个想法 \[ \begin{align*} &m_\mathcal{H}(N) \\ \le & {\rm\ maximum\ possible\ }m_\mathcal{H}(N){\rm\ given\ }k \\ \le & poly(N) \end{align*} \] 如果上述猜测能够被证明，而且\(m_\mathcal{H}\)可以取代Hoeffding不等式上界中的\(M\)，那么感知机算法就是可行的
上限函数：基本情况
由前面的讨论，在成长函数的基础上，可以定义一个上限函数（bounding function）\(B(N, k)\)，表示当停止点为\(k\)时最大可能的\(m_\mathcal{H}(N)\)值。可以通过一个更抽象的排列组合问题来研究上限函数的值：假设输入是一个长度为\(N\)的，由\(\circ\)和\(\times\)组成的向量，如果限定任意长度为\(k\)的子向量都不能被打散（即对任意长度为\(k\)的子向量，都不会出现\(\circ\)和\(\times\)的所有\(2^k\)中组合），则这个向量最多有多少种可能？
对这个问题进行抽象的好处是，抽象以后不再需要\(\mathcal{H}\)的具体形态。例如，无论\(\mathcal{H}\)是正区间还是1维感知机，它们的停止点都是3，因此上限函数都是\(B(N,3)\)
在有了上限函数的定义以后，我们想要证明 \[ B(N, k) \le poly(N) \] 首先，根据前一节的讨论，有
\[ B(2,2) = 3, B(3,2)=4 \]
然后，根据前一节最后Fun time的小题，有
\[ B(N,1) = 1 \]
再次，如果\(N<k\)，那么此时不受停止点约束，可以随意让\(\mathcal{H}\)打散，因此
\[ B(N, k) = 2^N{\rm\ for\ }N<k \]
最后，如果\(N=k\)，只需要从所有\(2^k\)种分类器中删掉一个就能满足停止点约束，因此
\[ B(N, k) = 2^N - 1{\rm\ for\ }N = k \]
注意，已经证明有二维空间中的感知机的停止点\(k=4\)，\(N=4\)时的成长函数值\(m_\mathcal{H}(4)\)为14，而\(B(4,4) = 15\)，因此上限函数实际给出的是一个宽松的上界
上限函数：其它情况的推导
\(N>k\)且\(k\not=1\)的情况比较复杂。不过经过观察，似乎\(B(4,3)\)与\(B(3,?)\)有联系：把已有的4个点去掉一个，或者向原有的3个点增加一个，问题就会互相转化。
暴力搜索以后，发现\(B(4,3) = 11\)。但是这个值怎么与前一行的值联系起来呢？可以将\(B(4,3)\)的解重新整理，归为两类，如下图所示
其中橙色部分的解都是“成双成对”的，即(1, 5)，(2, 8)，(3, 10)，(4, 11)这些分类器只是对\({\bf x}_4\)的分法不同。而紫色部分的解相对“形单影只”，没有其它组合可以对应。如果记橙色部分的数量是\(2\alpha\)，紫色部分的数量是\(\beta\)，那么首先可以立即得到\(B(4,3) = 11 = 2\alpha + \beta\)
进一步地，从输入集中去掉\({\bf x}_4\)以后，可以得到\(\alpha + \beta\)个二分法分类器。由上限函数中参数值可知，目前的假设集合\(\mathcal{H}\)停止点为3，意味着不存在能打散三个输入的假设函数，所以\(\alpha+\beta\)也不应该打散这三个输入。因此可以得到第一个推导 \[ \alpha + \beta \le B(3,3) \] 接下来，对橙色部分的分类器去掉\({\bf x}_4\)，得到去重以后在\({\bf x}_1, {\bf x}_2, {\bf x}_3\)上分类器的集合。如果这个集合里的某个分类器子集能够将任意两个\({\bf x}_i, {\bf x}_j\)组成的输入打散，则由于其处于橙色部分，对\({\bf x}_4\)可以产生完全的\(2^1 = 2\)个不同的分类结果，因此可以把\({\bf x}_i, {\bf x}_j, {\bf x}_4\)打散，与\(\mathcal{H}\)停止点\(k\)为3这一假设相悖。因此这\(\alpha\)个分类器不能打散任意两个输入，即 \[ \alpha \le B(3,2) \] 将上面的推导组合并推广，可以得到如下结论 \[ \begin{align*} B(N, k) &= 2\alpha + \beta \\ \alpha + \beta &\le B(N-1, k) \\ \alpha &\le B(N-1, k-1) \\ \Rightarrow B(N, k) &\le B(N-1, k) + B(N-1, k-1) \end{align*} \] 即得到了上限函数的上限。最后可以填出如下的表格
由上表的边界情况和递推式，有 \[ B(N, k) \le \sum_{i=0}^{k-1}{N \choose i} \] 而不等式的右边最高项为\(N^{k-1}\)。因此，对假设集合\(\mathcal{H}\)，如果其存在停止点且值为\(k\)，则其成长函数\(m_\mathcal{H}(N)\)的上限由上限函数\(B(N,k)\)决定，上限函数的上限由一个多项式函数\(O(N^{k-1})\)决定，综上所述，如果停止点存在，则\(m_\mathcal{H}(N)\)是多项式的。实际上，还可以证明\(B(N,k) \ge \sum_{i=0}^{k-1}{N \choose i}\)，即两者之间是相等的
\(\mathcal{H}\)中“坏情况”发生概率上界的证明
在证明了成长函数是多项式复杂度以后，一个自然的想法是把成长函数值放进Hoeffding不等式右侧，替换掉\(M\)。然而事情实际上并不如此遂意，直接替换的结果是不对的。尽管如此，还是可以得到一个形式差不多的上界，即在\(N\)足够大的情况下，有 \[ P[\exists h\in \mathcal{H} {\rm\ s.t.\ }|E_{\rm in}(h) - E_{\rm out}(h)| > \epsilon] \le 2\cdot 2m_{\mathcal{H}}(2N)\cdot \exp\left(-2\cdot \frac{1}{16}\epsilon^2 N\right) \] 接下来，给出一个概要的证明，主要是针对一些多出来的常数是如何发生的：
首先，在不等号左侧，有一个棘手的\(E_{\rm out}\)需要解决。因为训练集的大小总是有限的，因此\(E_{\rm in}(h)\)也是有限的。但是\(E_{\rm out}\)却是无限的。所以关键问题是怎么把这个无限值转变成有限值。如何用有限多个点知道\(E_{\rm out}\)呢？核心思想是借鉴之前训练-测试的方法，使用验证集来进行估计。可以取样出\(N\)个点构成验证集\(\mathcal{D}'\)，估计出\(E_{\rm in}'\)。由于\(E_{\rm in}\)、\(E_{\rm in}'\)的分布应该都类似于期望为\(E_{\rm out}\)的正态分布，因此如果某个假设函数\(h\)有其\(E_{\rm in}\)跟\(E_{\rm out}\)差得很远，那么有很大的概率（大于1/2）其\(E_{\rm in}\)离\(E_{\rm in}'\)也很远，所以可以用\(E_{\rm in}'\)换掉\(E_{\rm out}\)。换完以后，有（更具体的数学证明不再列出） \[ \frac{1}{2}P[\exists h\in \mathcal{H} {\rm\ s.t.\ }|E_{\rm in}(h) - E_{\rm out}(h)| > \epsilon] \le P[\exists h\in \mathcal{H} {\rm\ s.t.\ }|E_{\rm in}(h) - E_{\rm in}'(h)| > \frac{\epsilon}{2}] \] 接下来，由于\(E_{\rm in}\)有\(m_\mathcal{H}(N)\)种，\(E_{\rm in}'\)也有\(m_\mathcal{H}(N)\)种，因此综合起来，一共有\(m_\mathcal{H}(2N)\)种假设函数可以使用。使用之前事件并的概率的上界，有 \[ {\rm BAD} \le 2m_{\mathcal{H}}(2N)P[\exists h\in \mathcal{H} {\rm\ s.t.\ }|E_{\rm in}(h) - E_{\rm in}'(h)| > \frac{\epsilon}{2}] \] 最后看上述不等式中\(P\)的上界。还是使用之前类似的罐子举例子，只不过此时罐子中有\(2N\)个球，要比较的是挑出的\(N\)个球观测到的概率和罐里\(N\)个球反映的概率之间差别，由于全体观测反映的概率可以用取出球观测到的概率和罐内球反映的概率取均值得到，因此通过简单的计算，两者有以下关系 \[ |E_{\rm in} - E_{\rm in}'| > \frac{\epsilon}{2} \Leftrightarrow \left|E_{\rm in} - \frac{E_{\rm in} + E_{\rm in}'}{2}\right| > \frac{\epsilon}{4} \] 其中$ $可以看做是一个总体的概率，因此概率的上界可以用Hoeffding不等式求出（不过注意这里其实是无放回的Hoeffding不等式），即 \[ P[\exists h\in \mathcal{H} {\rm\ s.t.\ }|E_{\rm in}(h) - E_{\rm in}'(h)| > \frac{\epsilon}{2}] \le 2\exp\left(-2\left(\frac{\epsilon}{4}\right)^2N\right) \] 综上所述，证明了VC（Vapnik-Chervonenkis）上界，即 \[ P[\exists h\in \mathcal{H} {\rm\ s.t.\ }|E_{\rm in}(h) - E_{\rm out}(h)| > \epsilon] \le 4m_{\mathcal{H}}(2N)\cdot \exp\left(-\frac{1}{8}\epsilon^2 N\right) \] 最后回到感知机算法。由于二维空间感知机的停止点为4，因此\(m_\mathcal{H}(N)\)是\(O(N^3)\)的，多项式时间复杂度。当\(N\)增大时，\(m_\mathcal{H}(N)\)的增长速度小于指数函数的衰减速度，整体上“坏事情”发生的概率大幅度减小。所以如果感知机算法\(\mathcal{A}\)选出了\(E_{\rm in}\)最小的\(g\)，这个\(g\)也会有最小的\(E_{\rm out}\)，达到机器学习的效果
