机器学习可行性
Learning is Impossible
上节我们提到，
机器学习就是从数据出发，通过算法 ($\mathcal{A}$) 找到最符合我们数据集 ($\mathcal{D}$) 的 hypothesis $g$（$g \approx f$）.
这个时候就会有一个问题，虽然我们可以保证我们的 $g$ 在数据集 $\mathcal{D}$ 上的判断和真实的 $f$ 一致，但我们如何保证在 $\mathcal{D}$ 之外也同样如此1？
我们来看下面这个例子，
可能产生这样的 $\mathcal{D}$ 的 $f$ 有8种，而且似乎都可行。实际上，如果任何未知的 $f$ （即建立在数据 $\mathcal{D}$ 上的规则）都是有可能的，那么从这里做出有意义的推理是不可能的！
也就是说这个时候我们无法保证 $g \approx f$，在 $\mathcal{D}$ 之外的数据上.
Inferring Something Unknown
要证明机器学习可行，我们希望的是 hypothesis $g$ 在 in-sample 上表现好，同时在 out-sample 表现也要好。
类似于我们在统计学中常见的问题，通过少量的已知样本推断整个样本集的情况，也就是通过在 in-sample 上的表现，推断 out-sample 上的表现（Inferring Something Unknown）。
有一个罐子，盛放着橙色和绿色两种颜色的小球，我们如何在不查遍所有球的情况下，得知橙色球所占的比例？
常用的方法就是采样，利用样本中橙色球的比例去估计整体中橙色球的比例。
这个时候我们可能会想，有没有可能我们抽出的球全是绿色，或者说我们抽出的样本中两种球的比例跟真实情况差很远呢，这样的话我们的估计就会出错呀。
但这种事情发生的可能性大吗？不大，当我们的样本足够大时，这种事情发生的可能性会非常小。在概率论中，可以用 霍夫丁不等式(Hoeffding’s Inequality) 来描述上面这件事情的概率：
也就是说样本中橙球的比例和整体橙球的比例相等是 PAC (probably approximately correct)，这取决于我们的样本大小 ($N$) 和对误差的容忍度 ($\epsilon$)。
Connection to Learning
我们可以利用 sample 中橙球的比例来推断总体中橙球出现的概率，则同样的，我们也可以利用 sample 中 $h(x)\not=f(x)$ 的比例来推断总体中 $h(x)\not=f(x)$ 的概率。因为两者的错误率是 PAC 的，只要我们保证前者小，后者也就小了。
我们记 $h(x)$ 在 in-sample 中错误率为 $E_{in}$ (in-sample-error)，在 out-sample 中错误率为 $E_{out}$ (out-of-sample-error)。
- $\color{orange}{E_{out}(h)} = \underset{x\sim P}{\epsilon} [h(x)\neq f(x)]$，$\epsilon$ 表示数学期望
- $\color{orange}{E_{in}(h)} = \frac{1}{N}\sum_{n=1} ^ {N}[h(x_n)\neq y_n]$
根据霍夫丁不等式(Hoeffding’s Inequality)，
Real Learning
那么我们是不是直接挑选出 hypothesis set 中 $E_{in}$ 最小的 $g$ 作为我们的 final hypothesis 就行了呢？
当我们的 hypothesis set 中元素非常多的时候，全对的概率实际上也是是非常高的。就像丢硬币一样，150个同学同时丢硬币5次，有一人同时抛出五次正面的概率大于99%，我们能直接选择这种全对的 hypothesis 作为我们的 final hypothesis 吗？
霍夫丁不等式说的是对于给定的 hypothesis $h$，$E_{in}$ 和 $E_{out}$ 相等是 PAC 的，但对于我们整个 hypothesis set 而言，如同上面掷硬币的人很多的情况下，就很有可能出现 $|E_{in}(h)-E_{out}(h)|\gt \epsilon$ (Bad sample)，即 $E_{in}$ 很小，而 $E_{out}$ 很大的情况。
当我们的 hypothesis set 遇到这样 Bad sample 的时候，我们的算法 $\mathcal{A}$ 在挑选 final hypothesis 的时候就会遇到麻烦。
霍夫丁不等式保证了对于某个指定的 hypothesis $h$，我们遇到 Bad sample 的概率很小，但是对于整个 hypothesis set 呢？
在 hypothesis set 有限的情况下，我们选取选取 $E_{in}$ 最小的 hypothesis 是合理的。 M 小 N 大的情况下，出现表现好的坏数据的几率降低了，我们选择的 hypothesis 在 out-sample 也会具有好的表现。
总结
整体证明机器学习的可行性分了两个层面2，
- 对于单个 hypothesis，根据 Hoeffding 不等式，当 $\color{red}{N}$ 很大时，$\color{blue}{E_{in}}$ 和 $\color{blue}{E_{out}}$ 相等是 PAC 的 (泛化能力)；
- 当 $\color{red}{M}$ 有限，$\color{red}{N}$ 很大时，我们可以从 hypothesis set 中挑选 $\color{blue}{E_{in}}$ 最小的假设作为我们的 final hypothesis，选到泛化能力差的假设概率低 .
