我们今天的话题是，training和testing到底有什么不同。要解决的根本问题是：机器学习究竟为什么是可行的，当hypothesis set是无限大时，究竟发生了什么事情。

Recap and Preview

从上节课中，我们知道机器学习的流程已经是这样：

其中\(P\)表示，我们的训练数据和测试数据都是由\(P\)控制产生的。

光在训练数据上表现好还不够，我们希望在没有看过的资料上表现好才是我们想要的。

现在我们来回顾前四节课的重点：

于是，我们把learning拆成了两个重要的问题：

• 我们能否保证\(E_{out}(g)\)和\(E_{in}(g)\)是足够接近的
• 我们能否使\(E_{in}(g)\)足够小

而且前面我们主要关注hypothesis set \(H\)是有限大的情况，那么\(H\)的大小\(M\)在以上这两个问题中究竟扮演什么角色呢？

上面的两个问题在\(M\)上的trade-off如下：

我们能够看出，\(M\)的选择对learning是非常重要的，太大或太小都不好。那么这样一来\(M = \infty\)的情形不是注定效果很差吗？

我们这里要想办法解决无限大的\(M\)发生什么事。我们这里的思路是，用一个有限的数量\(m_{H}\)来代替\(M\)，这里用\(m\)表示比原来的\(M\)小，而下标\(H\)表示是跟\(H\)的性质是有一定关系的：

这里打一个问号，是因为我们还不知道可不可行。倘若我们能够找到这样一个\(m_{H}\)的话，我们就能：

• 证明当\(M\)无限大时，learning是可行的
• 利用\(m_{H}\)来帮助我们选择\(H\)，就像\(M\)一样

这是一个偏理论性的问题，我们要花差不多3节课的课程来证明PLA是完全合理的。

这节课的测验题是：

这里，我们可以推导出\(N\)关于其他变量的公式： \[ N = \frac{1}{2\epsilon^2} ln{\frac{2M}{\delta}}\]

Effective Number of Lines

现在我们从finite bin model出发，讨论一下，为什么\(M = \infty\)时没办法做。

因此，如果每一个\(P[B_{m}]\)都大于0的话，那么这无限个概率加起来，会远远超过1，那么这个bound也就不会有任何意义。

所以这个bound到底出了什么问题？我们用union bound的出发点是：对不同的hypothesis来讲，坏事不重叠（或者说不怎么重叠）。但是实际上，对两个相似的hypothesis，其\(BAD\,DATASET\)其实是重叠的：

图中，右边是对不同的hypothesis重叠的bad event的一种形象的表示。因此，在这种情况下，union-bound是对真实bound的一种过分估计（over-estimating）。

那为了对付这种重叠的情况，第一步就是把无限的hypothesis分成有限多类，每一类里是差不多的hypothesis。

我们先举个例子，我们假设平面上所有的线、所有的perceptron就是我们的hypothesis set。那么：

• 有无限多条线（\(\infty\)）
• 但是如果只有1个输入向量\(\mathbf{x}_1\)，那么显然在我们的眼中只有两种线：
• 那有2个点的时候呢？按照我们之前的推理方法，一共有4种：
• 那么有3个点的时候呢？
  • 如果是三角形的情形，也就是OX的每一种组合都线性可分的情况下，是有8种组合的。
  • 如果是三点共线的情形，则只有6种线：（在共线或重叠的情况下，都会少于8种）
• 那么4个点的时候呢？
  • 如果是四边形的情形，会有1种及其对称的做不到：
    之所以乘2，是因为其他那7种是OX完全对称的，将直线两侧调换一下即可。

从前面的推导，我们知道，如果从有限的数据看出去，我们的线的种类是有限的。这个种类的个数，我们称之为“effective number of lines”：

我们可以知道，这个effective number of lines一定是不会超过\(2^N\)的，表示这个数字是有限的。如果我们可以用这个数字取代\(M\)： \[ P[|E_{in}(g) - E_{out}(g)| > \epsilon] \le 2*effective(N)exp(-2\epsilon^2N) \]
那么当：

• \(effective(N)\)可以代替\(M\)
• 且\(effective(N) << 2^N\)时，

当N增大到很大时，上式右面的bound就会趋向于0。这样即使是无限条线，我们也可以说我们学到了东西。这暂时只是我们的猜想，我们要花一些力气，才能证明这是对的。

Effective Number of Hypotheses

接下来我们来看，如果我们用线的话，究竟有几种不一样的线。如果我们将来用高维度的hyperplane等的话，又应该怎么说明究竟有几种hypothesis这种事。

我们称： \[ h(\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N) = (h(\mathbf{x}_1), h(\mathbf{x}_2), \ldots, h(\mathbf{x}_N)) \in \{x, o\}^N\] 为一个dichotomy（二分，意为把数据集分成两半），相当于只从\(\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N\)的角度来看hypothesis的不同。

而\(H(\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N)\)则表示H能在\(\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N\)上实现的所有dichotomy。下表是hypothesis和dichotomy的一个对比：

于是，\(|H(\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N)|\)就是我们用来替代M的一个选项。

我们可以看到，我们的\(|H(\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N)|\)其实是依赖于我们的输入\(\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N\)的。为了消除这个影响，我们选择dichotomy set最大的那一个就好了： \[m_H(N) = \max_{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N \in X}{|H(\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N)|}\] 我们称这个函数为growth function（成长函数），是跟我们的hypothesis set有关的。通过前面，我们知道，这个函数的输出一定是有限的，即\(\le 2^N\)。

对perceptron的hypothesis set来说，写出来这个growth function会有点难，我们先来看一些简单的例子：

• Positive Ray (1-D perceptron的一半)：\(m_H(N) = N+1 << 2^N\)
• Positive Interval：\(m_H(N) = {N+1 \choose 2} + 1 = \frac{1}{2}N^2 + \frac{1}{2}N + 1 << 2^N\)
• Convex Set：\(m_H(N) = 2^N\) 我们称我们的N个输入被H shattered（击倒），当且仅当我们能找到N个点（可能是特别的N个点），其上的\(2^N\)个dichotomy都可以被H做出来，那么此时\(m_H(N) = 2^N\)。

Break Point

我们现在已知的growth function有：

• Positive Ray: \(m_H(N) = N+1\)
• Positive Interval: \(m_H(N) = {N+1 \choose 2} + 1\)
• Convex Set: \(m_H(N) = 2^N\)
• 2D Perceptron: \(m_H(N) < 2^N\)在某些情况下

如果我们现在用\(m_H(N)\)取代\(M\)的话，会怎样呢？ \[ P[|E_{in}(g) - E_{out}(g)| > \epsilon] \le 2*m_{H}(N)exp(-2\epsilon^2N) \] 我们可以得知，如果\(m_H(N)\)是多项式的话，就是好的，因为其增长速度小于后面那一项；而如果\(m_H(N)\)是指数式的话，就是不好的，因为和后面那一项的增长速度一个量级，我们不能确保N够大时，\(E_{in}\)和\(E_{out}\)很接近。那么2D Perceptron到底是好的，还是不好的呢？

我们再对growth function多做一个小小的定义。对一个hypothesis set H，我们定义k为它的break point，当且仅当k使得\(m_{H}(k)<2^k\)。可想而知，k+1, k+2, …也都是break point。我们只关注minimum break point。对2d perceptron， min break point就是4.

对于之前讨论过的一些growth function，它们对应的break point分别是：

从上面图中，我们产生了一个猜想：

• 当没有break point时，\(m_H(N) = 2^N\)
• 当有break point时，\(m_H(N) = O(N^{k-1})\)

那我们的猜想究竟对不对呢？且看下次课程。

Summary