机器学习基石第六讲继续讨论“学习是否可行的问题”。

Restriction of Break Point

继续前面的讨论，我们看$m_H(N)$是否会有一个很小的增长速度。回顾前面的四种成长函数及其break point。我们知道k是一个成长函数的break point，那比k大的值全是break point。

$m_H(N)$是一个hypothesis在N个数据点上可以产生的dichotomy的数量的最大值。现在假设一个hypothesis最小的break point是2，那我们能从中得到什么信息。

当N=1时，有定义得$m_H(N)=2$，这没有问题；当N=2时，由定义得$m_H(N) < 4$（最大值可能是3）。那当N=3时呢？当hypothesis从三个数据点产生一个dichotomy（比如ooo）、两个dichotomy（比如ooo和xoo）、三个dichotomy（比如ooo、xoo、oxo）、四个dichotomy（ooo、oox、oxo、xoo）时，可以存在一种情况，三个数据点中任意两个都不会被shatter；而当hypothesis试图从三个数据点产生五个dichotomy时，无论怎样都会有两个点被shatter。

现在知道了break point k会在很大程度上限制$m_H(N)$，那我们猜测$m_H(N)$会有一个跟k相关的最大值，而其又小于多项式，那我们就可以说$m_H(N)$是一个多项式。如果证明了这个猜测，那我们就可以将$m_H(N)$带进前面的Hoeffding’s inequality，进一步就可以证明学习是可行的。

本小节测试：

Bounding Function: Basic Cases

定义一个叫作bound function的函数B(N,k)，表示当break point为k时$m_H(N)$可能取到的最大值，且满足下图中的两点。现在我们的新目标是证明B(N,k)小于一个多项式。

现在我们将B(N,k)的值写在一张表里面，那我们首先可以先将表的上三角先填好（因为当k>N时，$B(N,k)=2^N$）。

当k=N时，有$B(N,k)=2^N-1$。

省下的那一部分表格，我们在下一小节继续填写。下面本小节测试：

Bounding Function: Inductive Cases

我们观察表格，看看$B(4,3)$是不是和$B(3,?)$有什么关系呢？我们尝试着去求解出B(4,3)对应的一组dichotomy，如下图左侧所示。将这11个dichotomy重新排列一下，如下图右侧所示，前八个又分成了四对（每一对的$x_1$、$x_2$、$x_3$标记相同，$x_4$分别是圈圈和叉叉），后三个都是“单个”的。

然后将B(4,3)写成
$$B(4,3)=11=2\alpha+\beta$$
而其中的$\alpha+\beta$则正好是$(x_1,x_2,x_3)$的一组不会被shatter的dichotomy（橘色的四对里边每队拿出一个，加上下面的三个，这7个dichotomy不考虑$x_4$）。所以肯定有
$$\alpha+\beta \leq B(3,3)$$

然后我们只看橘色的部分（不考虑$x_4$，那橘色的8个就变成了4个），我们说要保证三个点不被shatter，那我们还得保证其中任意两个点不被shatter，所以有
$$\alpha<B(3,2)$$

现在得到了

一直做这样的推导，我们就可以得到这样一个规律：

然后我们就可以像上图那样填写表格，得到了每个bounding function的上限（或者上限的上限……知道这些就够了）。

现在我们知道了B(N,k)有一个多项式上限，而B(N,k)又是$m_H(N)$在break point存在时的上限。实际上，这里的“$\leq$”可以改成“=”。前面介绍的那几个成长函数就有了上限，如下图。

然后是本小节测试：

A Pictorial Proof

之前我们尝试用$m_H(N)$来代替原来Hoeffding's inequality中的M，而实际上这样替换是有问题的。因为$E_{in}$的取值是有限的，而$E_{out}$的可能取值是无限的。这里用hypothesis在验证集上的犯错率$E_{in}^{'}$来代替$E_{out}$，下面给出了大概的推导过程。

步骤1：

步骤2：

步骤3：

这里实际上完成了Vapnik-Chervonekis(VC) bound的推导证明。当然，我也没听懂这三个步骤的推导，有需要的同学再去查其他资料吧。

现在我们可以说2D perceptrons的学习是可行的（但还没有证明任意维度的perceptron会发生什么事）。

最后是本小节测试：