再谈\(E_{\rm in}\)与\(E_{\rm out}\)
上回提到，如果有足够多的根据统计方法生成的数据，而且\(\mathcal{H}\)是有限集，那么问题是可学习的。即如果假设集\(\mathcal{H}\)的基数是有限的，记为\(M\)，而且有样本量\(N\)足够大，那么对任意算法\(\mathcal{A}\)选出来的\(g\)，都会有\(E_{\rm out}(g) \approx E_{\rm in}(g)\)。同样的道理，如果\(\mathcal{A}\)找到的\(g\)满足了\(E_{\rm in}(g) \approx 0\)，那么有PAC地\(E_{\rm out}(g) \approx 0\)，也就是说此时学习是可能的。需要注意的是，要想单纯地通过训练让\(E_{\rm in}(g) \approx 0\)是很容易的，只需要把每条数据对应的标签记住就好。但是研究机器学习算法的目的是在于要让模型在未知的数据上一样表现良好，因此才需要有测试的过程来验证是否有\(E_{\rm in} \approx E_{\rm out}\)。
这里再回顾一下之前几讲讲过的东西：
- 第一讲主要是强调，我们希望机器学习能够找到一个\(g\)使得其接近目标函数\(f\)。这个目标可以改写为\(E_{\rm out}(g) \approx 0\)。
- 第二讲讲的是，如何寻找一个\(g\)，使得\(E_{\rm in}(g) \approx 0\)
- 第三讲施加了一个前提条件，即主要讨论批处理、有监督的二元分类问题
- 第四讲则证明在假设集有限、样本量足够的情况下，有\(E_{\rm out}(g) \approx E_{\rm in}(g)\)。这样第二讲做的工作可以联结到第一讲提出的目标
实际上核心是两个问题
- 到底\(E_{\rm out}(g)\)和\(E_{\rm in}(g)\)会不会接近。如果答案是否定的，那么第一讲和第二讲的内容就无法连接
- 能否让\(E_{\rm in}(g)\)尽可能小
那么\(|\mathcal{H}|=M\)跟这两个问题有什么关系呢？可以分两个情况讨论：
- \(M\)比较小的时候，第一个问题能够满足，因为“坏事情”发生的概率（即\(E_{\rm in}\)和\(E_{\rm out}\)不接近的概率）有上界\(2M\exp(−2\epsilon^2N)\)。\(M\)小意味着上界小，即\(E_{\rm in}\)和\(E_{\rm out}\)大部分情况下会接近。但是此时算法的选择有限，很难找到一个让\(E_{\rm in}\)接近0的\(g\)。
- \(M\)比较大的时候，由于有足够的选择，因此可以找到\(g\)让\(E_{\rm in}\)尽量小，但是“坏事情”发生的概率会大大增加，对两者接近的把握变弱
如果就这么看，那么\(M = \infty\)是不是一件特别不好的事？感知机会不会并不可用？回顾之前\(E_{\rm in}\)和\(E_{\rm out}\)不接近这一事件概率的上界，有 \[ P[|E_{\rm in}(g) - E_{\rm out}(g)| > \epsilon] \le 2M\exp(-2\epsilon^2 N) \] 这里可以先把无穷大的数\(M\)替换为一个有穷的数\(m_{\mathcal{H}}\)看看，即 \[ P[|E_{\rm in}(g) - E_{\rm out}(g)| > \epsilon] \le^? 2m_{\mathcal{H}}\exp(-2\epsilon^2 N) \] 如果换完以后之前的性质仍然成立，那么就可以用有穷的\(m_\mathcal{H}\)来替换无穷的\(M\)。这样就可以证明在无限假设集上学习的可行性，并为之后决定如何选择正确的假设集提供支持
有效线性分类器的数量
重新回顾一下对假设\(h_m\)所谓”坏事情“这一定义的概念。如果对分类器\(h_m\)有\(|E_{\rm in}(h_m) - E_{\rm out}(h_m)| > \epsilon\)，就称为坏事件\(\mathcal{B}_m\)会发生。由于假设集合比较大，为了让算法\(\mathcal{A}\)能自由选择，需要计算任一坏事件发生的概率，即求出\(P[\mathcal{B}_1{\rm\ or\ }\mathcal{B}_2{\rm\ or\ }\ldots{\rm\ or\ }\mathcal{B}_M]\)的上界。在最坏的情况下，每个\(\mathcal{B}_m\)都不互相交叠，所以由事件并的概率上界定理，有 \[ P[\mathcal{B}_1{\rm\ or\ }\mathcal{B}_2{\rm\ or\ }\ldots{\rm\ or\ }\mathcal{B}_M] \le P[\mathcal{B}_1] + P[\mathcal{B}_2] + \ldots + P[\mathcal{B}_M] \] 当\(M = \infty\)时，由于是无限多个概率连加，因此这个上界有可能也是无限大的值，至少会是一个很大的值，会大于1，所以这个上界就没有实际意义了。
问题出在哪儿呢？回顾上界定理中取到上界的条件，是所有子事件互不交叠。但是这个现象在当前讨论的问题中很难出现。相反地，对于相似的假设\(h_1 \approx h_2\)，其\(E_{\rm out}\)是相似的，而对大部分\(\mathcal{D}\)甚至其\(E_{\rm in}\)是相等的。可以通过考虑之前提到的感知机的例子来理解这个结论。对于一个已知的感知机，如果将其稍微旋转或平移一点，就会得到一个新的感知机。这两个感知机只会对那些处于旋转或平移经过的区域中的点给出不同的分类结果，而由于这些区域非常小，\(\mathcal{D}\)中数据落在这些区域里的概率也会非常小。因此很显然，之前给出的概率上界是被过分估计了的。那么，接下来，就要找出这些”坏事情“重叠的事情
一种自然的想法是，能否把\(\mathcal{H}\)中所有的\(h\)做一个归类，来分析重叠的状况。对\(\mathbb{R}^2\)上的所有线\(\mathcal{H}\)，尽管有无限多种可能性，但是可以分类讨论
只有一个数据点
如果数据点只有一个，即输入向量\({\bf x}_1\)只有一个，那么尽管线有无限多条，但是总体来讲只需要分成两类：\(h_1\)类的线把\({\bf x}_1\)判为正例，\(h_2\)类的线把\({\bf x}_1\)判为负例，如图所示
有两个数据点
如果输入向量有两个，所有线可以分为四类，这四类线对数据集的分类结果可以如下图所示
有三个数据点
如果输入向量有三个，大概率情况下，所有线可以分为八类。但是需要注意的是，这种情况并不总是成立的！如果输入的向量三点共线，那么所有分类器只能分成六类（其中有两类情况是线性不可分的，如下图所示）
有四个数据点
如果输入向量有四个，所有线最多可以分为14种（当然如果共线或者正负例交叠，分类器的种类就会更少）。
这里就不再放图占用篇幅了，不过可以参考所谓的”异或分类问题“
总结
之前所枚举的例子，实际上是指出了对\(N\)个不同的输入\({\bf x}_1, {\bf x}_2 ,\ldots, {\bf x}_N\)，将其分开的线性分类器最多可以分为几类。这称之为有效线性分类器的数量（effective number of lines），可以简记为\({\rm effective}(N)\)。当\(N \in \{1,2,3,4\}\)时，\({\rm effective(N)}\)对应为2、4、8、14。可以看出一个很重要的结论：对线性分类器，有 \[ {\rm effective}(N) \le 2^N \] 这样，可以做如下猜想：尽管\(\mathbb{R}^2\)上的直线数量\(M\)是无限的，但是对有限的输入\(N\)，其有效线性分类器的数量\({\rm effective}(N)\)是有限的，那么在之前Hoeffding不等式中就可以用\({\rm effective}(N)\)来取代\(M\)，这样可以得到一个有限的上界。特别的，如果还能满足\({\rm effective}(N) <\!\!< 2^N\)，那么Hoeffding不等式的上界可以再次减小，而且有效线性分类器的数量也会变得很小。这说明即便假设集是无限集，学习也是可能的
假设集的有效大小与成长函数
考虑更加宽泛的情况，即分类器不是一个线性分类器时的情况。如果分类器\(h\)在数据集\({\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N\)上的结果只可能是\(\times\)或\(\circ\)，即 \[ h({\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N) = (h({\bf x}_1), h({\bf x}_2) , \ldots, h({\bf x}_N)) \in \{\times, \circ\}^N \] 那么称\(h\)是一个二分法（dichotomy）分类器。我们要看的是一个假设集\(\mathcal{H}\)可以做出多少个不同的二分法分类器，可以将\(\mathcal{H}\)用作\({\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N\)上得到的所有不同的二分法分类器组成的集合记做\({\mathcal{H}}({\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N)\)。例如，如果\(\mathcal{H}\)是\(\mathbb{R}^2\)上所有的直线，那么当\(N=4\)时，\(\mathcal{H}({\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N)\)是类似\(\{\circ \circ \circ \circ , \circ \circ \circ \times, \circ \circ \times \times, \ldots\}\)这样的集合。接下来要做的是，看能否用\(|\mathcal{H}({\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N)|\)取代之前Hoeffding不等式里的\(M\)
然而这里有一点不妥，就是\(|\mathcal{H}({\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N)|\)与输入的形式关系紧密。例如，还是回到前一节中所举的例子，当\(N=3\)，\(\mathcal{H}\)为\(\mathbb{R}^2\)上的所有直线时，如果输入三点共线，则\(|\mathcal{H}({\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N)|=6\)。如果两两共线，三足鼎立，则\(|\mathcal{H}({\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N)|=8\)。为了摆脱其对输入的依赖，可以对所有不同输入进行考虑，选出最大的\(|\mathcal{H}({\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N)|\)值，记其为\(m_\mathcal{H}(N)\)，就有 \[ m_\mathcal{H}(N) = \max_{ {\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N \in \mathcal{X}}|\mathcal{H}({\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N)| \] 实际上\(m_\mathcal{H}(N)\)是一个关于\(N\)的函数，其中\(N\)是输入的点的个数。如果回到前一讲的例子，可以看出来在这种情况下\(m_\mathcal{H}(N)\)实际上就是前一讲中的\({\rm effective}(N)\)。我们把这个函数起一个更通用的名字，叫做成长函数（grow function）。成长函数的上限确定存在，其上界为\(2^N\)（\(N\)个样本每个有两种取值）。
对不同的假设集，确定其成长函数具体值的难易程度有不同。如果是之前感知机的问题，那么确定成长函数的具体值是很难的。但是接下来可以看一些相对简单的例子：
正射线（Positive Rays）的成长函数
如果输入就是一维实数，即\(\mathcal{X} = \mathbb{R}\)，假设集集合\(\mathcal{H}\)中的每个\(h\)都会定义一个阈值\(a\)，其分类方法为 \[ h(x) = {\rm sign}(x-a) \] 所以每个不一样的阈值\(a\)就会定义一个不一样的假设函数\(h\)
如果给定了\(N\)个数据点，那么对该\(\mathcal{H}\)，有\(m_\mathcal{H}(N) = N+1\)。因为\(N\)个点可以把一条直线切成\(N+1\)个不同的区间，任何落在同一个区间内的阈值\(a\)其决定的\(h\)效果都一样。注意当\(N\)很大时，会有\((N+1) <\!\!< 2^N\)
正区间（Positive Interval）的成长函数
接下来，输入不变，对\(\mathcal{H}\)的定义稍作变化：不再让大于某个阈值\(\ell\)的所有\(x\)都被分为+1，而是施加一个上限\(r\)，将所有\(x\in [\ell, r)\)分为+1，即此时对\(h \in \mathcal{H}\)有 \[ h(x) = +1 {\rm\ iff\ }x \in [\ell, r), -1{\rm\ otherwise} \] 此时，\(N\)个点还是可以把一条直线切成\(N+1\)个不同的区间。如果\(\ell\)和\(r\)都落在不同的区间，那么一部分\(x\)会被标为+1，另一部分被标为-1。这样的\(\ell\)和\(r\)的选法共有\(N+1 \choose 2\)种。还有一种情况，就是\(\ell\)和\(r\)都落在同一个区间，此时所有\(x\)都会被标为-1。因此对于这样的\(\mathcal{H}\)，其成长函数为 \[ \begin{align*} m_\mathcal{H}(N) &= {N+1 \choose 2} + 1 \\ &= \frac{1}{2}N^2 + \frac{1}{2} N+ 1 \end{align*} \] 注意此时，仍然有\(N\)很大时，\(m_{\mathcal{H}}(N) <\!\!< 2^N\)
凸集合的成长函数
接下来，考虑一个稍微复杂点的情况，即输入空间\(\mathcal{X} \in \mathbb{R}^2\)，对\(h\in \mathcal{H}\)，如果\(\bf x\)在一个凸集合里（可以看做是二元平面上的凸多边形），则\(h({\bf x}) = +1\)，否则\(h({\bf x}) = -1\)，计算\(\mathcal{H}\)的成长函数
可以先看最极端的情况，即所有\({\bf x}_1, {\bf x}_2 , \ldots, {\bf x}_N\)都放在一个大的圆上。此时，任何可能的二分法分类器都可以通过如下方法得到：找出所有标记为+1的点，所有相邻的点（跳过它们中间的负例点）以线相连，这样会得到一个凸多边形，凸多边形上（及其内部）的点都标记为+1，其外的点都标记为-1。下图给出了一个例子
因此，无论输入的\(N\)有多大，总可以做出来\(\mathcal{H}\)上的全部二分法分类器，即此时\(m_\mathcal{H}(N) = 2^N\)。此时称这\(N\)个点可以被假设集合\(\mathcal{H}\)打散（shatter）
停止点（break point）
回到最开始提出\(m_\mathcal{H}(N)\)的目的，是为了取代Hoeffding不等式上界中的\(M\)值。从前面的讨论可以发现，成长函数有两种复杂度：一种是以正射线为代表的多项式复杂度，一种是以凸集合为代表的指数复杂度。由于原有的不等式上界里有一个指数为负的指数项，因此如果成长函数是多项式的，那么随着\(N\)的增大，指数项衰减的速度远快于成长函数增长的速度，可以保证\(N\)很大的时候\(E_{\rm in}(g)\)与\(E_{\rm out}(g)\)之间相差很大的概率趋近0。但如果成长函数是指数的，就没有这样的性质
那么感知机的成长函数是“好的”（多项式复杂度）还是“不好的”（指数复杂度）呢？正规证明在下讲给出，不过这里给出一个辅助概念。由前面的分析，可以得知，只有在对某个规模的输入，不能做出全部二分法分类器，使得\(m_\mathcal{H}(N)\)不能等于\(2^N\)时，才有可能避免指数复杂度的成长函数。例如，对线性分类器，当输入的数据大小为4时，不可能找出\(2^4=16\)种不同的线性分类器来完全区分所有情况（只能找到14种）。称这样的点叫做停止点，即
如果任意\(k\)个输入都不能被\(\mathcal{H}\)打散，就称\(k\)为\(\mathcal{H}\)的停止点。即若\(k\)是\(\mathcal{H}\)的停止点，就有 \[ m_\mathcal{H}(k - 1) = 2^{k-1},\hspace{1ex} m_\mathcal{H}(k) < 2^k \]
这里需要注意停止点的任意性。还是以线性分类器为例，尽管之前例子证明在\(N=3\)时，如果三点共线，也无法找到\(2^3 = 8\)种线性分类器，但是仍然存在3个输入被\(\mathcal{H}\)打散的情况（三点不共线），因此还是有\(m_\mathcal{H}(3) = 8\)，即3不是\(\mathcal{H}\)的停止点
停止点有一个很好的性质：如果\(k\)是\(\mathcal{H}\)的停止点，那么\(k+1, k+2, \ldots\)都是停止点。所以我们尤其感兴趣\(\mathcal{H}\)的第一个停止点（在不引起混淆的情况下，可以直接简记为“\(\mathcal{H}\)的停止点”）。根据之前的介绍有
- 正射线的停止点为2
- 正区间的停止点为3
- 二维平面感知机的停止点为4
- 凸集合没有停止点
从上面的停止点值可知，显然当\(\mathcal{H}\)没有停止点时，\(m_\mathcal{H}(N) = 2^N\)。但是似乎还有一个性质，就是如果\(\mathcal{H}\)的停止点为\(k\)，那么是不是有\(m_\mathcal{H}(N) = O(N^{k-1})\)？这个问题留待接下来的课程中证明。
