[林轩田]机器学习基石（四)

本文主要是介绍[林轩田]机器学习基石（四)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Lecture 4: Feasibility of Learning 机器学习的可行性

ppt

4.1 Learning is impossible 学习是不可能的

这一小节的主要内容是，既然假设函数 $f$ 是未知的，那么我们怎么能保证我们在数据样本中学到的 $g$ ，是越来越接近 $f$ 的呢？在没有任何限定的情况下，很有可能我们在 $D$ 中学到的知识没有任何意义，即我们不能够利用我们学到的知识在 $D$ 之外的数据中做预测。如果是这样的话，机器学习就没有可行性了。
林教授举了两个例子来论证，机器学习没有可行性的问题。
第一个例子，

输入样本是六张图片，上面三张输出是 $-1$ ，下面三张输出是 $+1$ ，请问你能根据这六张的输入输出规律，推断右边那张输出是什么吗？
这其实是一个无解的问题。因为如果我们根据上面三张左上角方格为黑色这条规律，推出未知图片输出为 $-1$ ，出题者会说，其实规律是对称性，未知图片输出应为 $+1$ ；如果我们根据对称性，推出未知图片为 $+1$ ，出题者会说，其实规律是左上方格的颜色，所以正确答案是 $-1$ 。

这就是说，我们无法保证，在数据样本 $D$ 上学到的假说 $g$ ，它在别的数据上也有很好的分类情况，因为我们在 $D$ 上学到的规律，可能它就不是真正的规律，即使它在 $D$ 上有非常好的分类效果。

说句题外话，这就有点像《三体》中的“射手与农场主”理论。

射手”假说：有一名神枪手,在一个靶子上每隔十厘米打一个洞.设想这个靶子的平面上生活着一种二维智能生物,它们中的科学家在对自己的宇宙进行观察后,发现了一个伟大的定律：“宇宙每隔十厘米,必然会有一个洞.”它们把这个神枪手一时兴起的随意行为,看成了自己宇宙中的铁律。
“农场主假说”：一个农场里有一一群火鸡,农场主每天中午十一点来给它们喂食.火鸡中的一名科学家观察这个现象,一直观察了近一年都没有例外,于是它也发现了自己宇宙中的伟大定律：“每天上午十一点,就有食物降临.”它在感恩节早晨向火鸡们公布了这个定律,但这天上午十一点食物没有降临,农场主进来把它们都捉去杀了。

总结起来，就是我们无法保证，在数据样本中学到的，具有良好分类效果的 $g$ ，它是接近于理想化函数 $f$ 的。

第二个例子，更数学一点。

是一个简单的二元分类问题。
输入 $x$ 有3位，每位有 $0,1$ 两种情况，可以想象到 $x$ 共 $2^3=8$ 种情况；
输出 $y$ 为二元的 $+1,-1$ ，分别用圈圈和叉叉表示。
可以计算出，假设空间 $H$ 中共有 $2^8 = 256$ 种假设函数，其中，可以完美分类训练样本的 $g$ 有如下几种：

这么多中 $g$ ，而且都在训练样本 $D$ 上表现很好，我们怎么知道哪个是最靠近理想化函数 $f$ 的假设函数呢？
所以，机器学习只能保证在 $D$ 上有良好的分类效果，无法保证训练好的 $g$ 在 $D$ 外接近 $f$ 。这就是机器学习NO FREE LUNCH定理。
如果机器学习无法保证在 $D$ 外也有良好的训练效果，实际上机器学习就是没有意义的一件事情，也就不存在可行性。

4.2 Probability to the Rescue 救援的可能性

上一小节说到了，机器学习在那种严格的场景下，是没有学习的可能性的。但是，有没有一些方法，可以帮助我们把未知的目标 $f$ ，弄得已知一点，从而给机器学习一条活路呢？
林老师举了个例子。
portion 份 || probability 几率、概率 || fraction 分数、分
考虑一个情景，我们有一个桶，桶内有很多橘色的和绿色的小球，橘色的小球在所有小球中的比率(portion/probability)未知，有什么方法能帮我们推理出橘色小球的比率呢？
最直观的操作就是抽样统计。
假设实际上橘色小球的比率为 $\mu$ ，抽样得到的橘色小球比率为 $\nu$ ，在样本足够的情况下， $\nu和\mu$ 是比较接近的。
下面引入 Hoeffding’s Inequality 霍夫丁不等式
设样本数为 N ，当足够大时， ν 和 μ 的接近程度是

P[|ν−μ∥>ϵ]≤2exp(−2ϵ2N)

ϵ 使我们定义的一个容忍程度。
- 该不等式对任意 $N$ 和 $\epsilon$ 都是成立的
- 该不等式不用提前知道 $\mu$

4.3 Connection to Learning 和学习的联系

上一小节讲的是抓球的案例，它和机器学习有什么联系呢？

上图左方是桶抓球案例的相关参数

有一个未知的橘色球比例 $\mu$ 。在学习中，目标函数 $f(x)$ 是未知的，更进一步，系统从假设空间 $H$ 中选择的 $h(x)$ 与 $f(x)$ 的关系也是未知的。
我们将抓到橘色球事件标记为橘色。在学习中，我们将系统选到的 $h(x)$ 与 $f(x)$ 不一致标记为橘色，意味h is wrong 。更通俗一点，就是对采样到的 $x$ ，若我们通过 $h(x)$ 预测到的 $y_h$ 与实际的 $y_f$ 不一致，标记为橘色。
我们将绿色球事件标记为绿色。在学习中，我们将系统选到的 $h(x)$ 与 $f(x)$ 一致标记为绿色，意味h is right
从桶中抽样出的 $N$ 个样本，和桶中的总体样本，是相互独立的，而且是同分布的；在学习中，训练样本集 $D$ 和所有样本，也是独立同分布的。

如果 $N$ 足够大，且是独立同分布的，我们就可以根据观察到的 $h(x_n) \ne y_n$ 的概率，来推出在我们未知的空间中， $h(x) \ne f(x)$ 的概率

林教授在机器学习的流程中加入了橘色线代表的新的组件。在训练集上误差越小，可以概率性地推出在实际空间上误差也越小。
“unknown P on X” 这个组件，代表 $X$ 的真实分布 $P$ ，根据这个分布生成了很多 $x_1,x_2,...$ 作为训练示例。（解释左上虚线）
假设hypothesis set $H$ 中有合适的 $h$ ，我们将这个 $h$ 拿出来做个验证，看看 $h是否等于f$ (解释右边实线)。
理论上说我们需要使用 $P$ 分布生成的所有 $X$ 进行验证，但是实际上我们使用的是训练数据来验证（解释剩下的那条虚线和实线）。
所以，对任意合适的 $h$ ，我们根据计算出来的

$E_{i n} (h) = \frac{1}{N} \sum_{n = 1}^{N} ‖ h (x_{n}) \neq y_{n} ‖$ $E_{in}(h) = \frac{1}{N} \sum_{n=1}^{N}\Arrowvert h(x_n) \ne y_n \Arrowvert$ ( $h(x_n)$ 与 $y_n$ 的误差)
来概率性地推出

$E o u t (h) = ε x \sim P ∥ h (x) \neq f (x) ∥$ $E_{out}(h) =\varepsilon_{x \sim P} \Arrowvert h(x) \ne f(x) \Arrowvert$
- $E_{in}(h)$ 代替 $\nu$ ， $E_{out}(h)$ 代替 $\mu$ ，我们可以根据图片这样代入霍夫丁不等式。

同理，上述等式：
对所有 $N$ 和 $\epsilon$ 成立。
不需提前知道 $E_out$ 值
$E_{in}(h) = E_{out}(h)$ 是Probably Approximately correct(PAC)。

所以，如果 $E_{in}(h) \simeq E_{out}(h)$ ，且 $E_{in}(h)$ 足够小，我们就可以得到 $E_{out}(h)$ 也是足够小的，即在P的分布下 $h \simeq f$

考虑一个问题

对任意一个已经选定好的 $h$ ，我们得到了 $E_{in}(h) \simeq E_{out}(h)$ ，那么我们可以宣称我们拿到了一个良好的学习假设函数吗？

如果我们足够幸运， $E_{in}(h)$ 足够小,那我们可以使用该 $h$ ；
但是大部分情况下我们不是那么幸运的，这个 $E_{in}(h)$ 并不小，这个时候’ $g \ne f$ ’PAC!

所以我们一般用这个流程来做验证！

4.4 Connection to Real Learning 和真实学习的联系

真实的学习中肯定不会只有一个 $h$ ，我们有多个 $h$ 。
在第二小节的抽样实验中，我们肯定会遇到一种情况，那就是抽样得到的样本分布和真实情况相去甚远，我们把这种样本叫做Bad Sample。
同理，在机器学习的领域上，也有Bad Data。对于某个 $h$ 而言，如果在一个 $D$ 上发现 $E_{in}$ 和 $E_{out}$ 相去甚远，我们认为这个 $D$ 对于这个 $h$ 是不好的。（这里深入的解释一下，我们在已知的训练数据上跑着跑着，觉得得到了一个挺小的误差 $E_{in}$ ，然后把这个 $h$ 丢进测试集里一跑，发现误差陡然大了好多，这里对于 $h$ 而言，训练数据就是Bad Data）
这张图林教授想告诉我们的是，根据霍夫丁不等式，其实训练样本不好的几率是很小的（存疑）

如果，我们有很多个 $h$ 呢？

上文讲到，之所以要有很多个 $h$ ，是因为我们需要给演算法 $A$ 以选择性，但是 $h$ 多了，碰到不好的训练样本的几率也增大了。

我们假设，对于抽样 $D_n$ ，只要有一个 $h$ ，使得 $D_n$ 是 $BAD$ 的， $D_n$ 是 $BAD$ 的。
那么这个不好的资料发生的几率到底是多少呢？

根据霍夫丁不等式的联结上限，我们得到上限是

$2 M e x p (- 2 ϵ 2 N)$ $2Mexp(-2\epsilon^2N)$

如果 $M$ 是有限的，且N足够大我们求得了上限，这个上限就是有界的。如果是这样，我们就有理由认为，我们的演算法在检索 $h$ 的过程中，存在一个好的 $h$ 。

最可能的 $h$ ，就是 $E_{in}$ 最小的。

所以当 $H$ 假设空间有限时，机器学习是可行的。

这个问题很有意思，
首先1是不对的，因为 $x_1$ 和 $x_2$ 是相互独立的，这两个假设函数本身就不一样，所以不能说 $h_1$ 和 $h_2$ 的BAD DATA是一样的。
然后2是对的，因为 $h_1$ 和 $h_3$ 的输入样本只有符号的区别。
3，4根据霍夫丁不等式都是对的，很显然吗，因为4是对的，3肯定也是对的。