机器学习基石第五讲继续讨论“学习是否可行”这一问题，这一讲比较难，建议大家多看两遍。

Recap and Preview

前面的课程得出了这样一个结论：在训练数据集足够大，H中包含的hypothesis个数有限的前提下，我们可以证明每一个hypothesis的$E_{in}$和$E_{out}$是相当的。在这样的结论下，我们就可以从H中选择一个$E_{in}(g) \approx 0$的hypothesis作为我们的g，且大概差不多（PAC）可以说$E_{out}(g) \approx 0$，也就说明了学习是可行的。

下图回顾了前面四讲的内容。第一讲，说问题会有一个未知的目标f能够完美的解决问题，我们可以找到一个g满足$E_{out}(g) \approx 0$，然后用这个很接近f的g去处理问题。第二讲，说怎么去找到g呢，我们引入$E_{in}(g) \approx 0$来衡量hypothesis，找到合适的g。第三讲，我们介绍了机器学习的分类，并指出本课程研究的问题都是基于批量的监督式二元分类。第四讲，我们尝试着去证明$E_{in} \approx E_{out}$，并证明学习是可行的。

这里将机器学习分成了两个核心的问题，见下图。第一个问题将第一讲和第二讲联系起来，而第二个问题我们在以后的课程中还会重点介绍。

上一讲的结论有一个前提，那就是H中hypotheis的个数M有限，那我们就来研究一下这个M。当M较小时，坏事情发生的几率很小，但g的选择范围又太小；当M较大时，g的选择范围够大，但坏事情发生的几率又增大了（具体什么是坏事情，请仔细阅读上一讲内容）。所以说合适的M是很重要的。下图给出了上一讲推出的一个不等式，那我们尝试将其中的M换成较小的一个数值$m_H$（当然，可能不能换，下图第二个不等式的不等号上有问号），并尝试证明在无限大的H上学习的可能性，研究$m_H$的取值及其对H的影响。下面三讲，我们会集中讨论这个问题，到时候我们就能回答“机器为什么能学习”这个问题了。

本节小测试：

Effective Number of Lines

下图回顾了得出第四讲不等式的过程。

前面使用了union bound，当时我们考虑每一个hypothesis对应的坏的data set都是彼此孤立的（彼此没有交集），而实际上应该是重叠的，如下图所示。比如，感知机中两条很接近的直线对应的hypothesis表示为$h_1$和$h_2$，在大多数的data set上应该有$E_{in}(h_1) \approx E_{in}(h_2)$，从而应该有$E_{out}(h_1) \approx E_{out}(h_2)$。所以，前面的推导太over-estimating（可以说“太小心了”吧）。

下面，我们尝试对H中的hypothesis进行分类，将相似的hypothesis归为一类，它们对应的坏的data set应该是重叠的。假设H是一个二维平面，其中的hypothesis是平面上的直线，有无限多条。对于一组数据$x_1$，我们可以把全部的hypothesis分成两类，一类如$h_1$将$x_1$标记成圈圈，一类如$h_2$将$x_1$标记为叉叉。对于两组数据呢，我们可以把全部的hypothesis分成四类，如下面第二张图所示。

那三组数据呢？很容易推出，对于不在一条直线上三组数据，我们可以将hypothesis分成8类。而对于处在一条直线上的三组数据，我们只能将hypothesis分成6类，如下面第二张图所示。

再看四组数据的情况。这时我们最多可以将hypothesis分成14类，如下图所示。注意，图中只给出了8-1=7种情况，另外8-1=7种是它们的“对称”情况，如左上的将四组数据全标记为圈圈的情况对应的是将四组数据全标记为叉叉的情况。

我们能不能得到一个一般的计算公式，来计算在N组输入数据下，我们最多可以将hypothesis分成几类呢？首先，我们发现，在N组输入数据下，hypothesis的种类不超过$2^N$种。现在我们期望能将无限多条hypothesis分成有限组，那我们或许将前面那个不等式中的M换成$effective(N)$，如下图所示：

现在，我们如果能得出一个$effective(N)$来代替M，且有$effective(x) \ll 2^N$，那我们就可以证明在无限多hypothesis上的学习是可行的。

本小节测试：

Effective Number of Hypotheses

我们定义
$$h(x_1,x_2,…,x_N) = (h(x_1),h(x_2),…,h(x_N)) \in {x,o}^N$$
来表示一个hypothesis对数据集的分类情况，称为dichotomy。那H中所有hypothesis在数据集上就会产生各种各样的dichotomies，用$H(x_1,x_2,…,x_N)$来表示。用$\left| H(x_1,x_2,…,x_N) \right|$表示其中包含的dichotomy的个数，我们尝试用其来代替M。

下面我们来计算$\left| H(x_1,x_2,…,x_N) \right|$的最大值：
$$m_H(N) = max \left| H(x_1,x_2,…,x_N) \right|$$
我们称其为成长函数（growth function），且已经知道了其上限为$2^N$。

我们先来看一个叫作positive rays的hypothesis。输入都是一维的实数，H中的hypothesis是这样的：
$$h(x) = sign(x-a)$$
其中a是一个threshold。观察下图，我们可以发现这样的hypothesis可以将N个数据切出N+1种dichotomy。下图右下角给出了4个数据时的5种dichotomy。

现在我们将hypothesis改成positive interval，这时的$m_H(x)$变成了下图所示。

再举一个例子，我们将hypothesis改成凸集（convex sets），如下图所示，左侧蓝色部分是一个凸集，右侧蓝色部分不是凸集。现在的输入数据变成了二维的，当一个数据点落在凸集内，hypothesis将其标记为+1，否则标记为-1。我们算一下此时的$m_H(x)$是多少。

考虑这样一种情况，我们的数据点全都在一个圆周上。下图中所示，可以看到一个凸多边形，如果让这个多边形外扩一点，那原来作为顶点的数据点全落在了多边形内，然后我们的hypothesis就可以将多边形内的标记为+1，多边形外的标记为-1，这样肯定就会产生多种dichotomy（这里的凸多边形就是凸集啊）。仔细想一下，现在任何一种dichotomy都可以得到，也就是此时$m_H(x)=2^N$。在这种情况下，我们称这N个数据点被H给shattered掉了（领会精神，不会翻这个词）。

最后是小测试：

Break Point

上面我们介绍了四种不同的成长函数。我们原本打算用$m_H(N)$来代替M。如果我们的$m_H(N)$像positive rays和positive intervals的那样是一个多项式，那随着N的增长，$E_{in}(g)$和$E_{out}(g)$相差很大的几率会越来越小，逐渐趋于零，这正是我们想要的；而如果我们的$m_H(N)$像convex sets的那样是指数类型的，那我们还不能确定这个几率。

现在我们来确定一下二维感知机的$m_H(N)$是那种类型的，但这个问题在这一讲还不能解决，要等到下一节。前面提到，当N=4时，我们的$m_H(N)<2^N$，我们把4这样$m_H(N)<2^N$的点称为break point。下面第二张图列出了几种问题的break point。现在我们有这样一个猜想：对于没有break point的， 其成长函数就是$2^N$；而对于有break point的，或许从break point上，成长函数就变成了$m_H(N)=O(N^{k-1})$。如果这个猜想成立，那我么就可以说二维感知机的成长函数的增长速度是$N^3$左右。

这一讲到这里，下一讲继续讨论。

本节小测试：

这一讲挺难的，希望大家能多看两遍视频