今天要探讨的问题是Feasibility of Learning，即Learning是不是可行的。我们上次埋了一个梗，说Learning搞不好是做不到的。我们先讨论这个问题，再研究即使Learning是做不到的，我们能否加上一些假设或者使用一些方法，使Learning是做得到的。

Learning is Impossible?

老师首先展示了一个有趣的Human Learning的小例子：

这里老师是想通过例子告诉大家，如果机器学习问题没有限制的话，那么无论你学到什么东西，你的“敌人”永远可以说你是没有学到东西。这样看起来，学习是一件不可能的任务。

这里还有一个简单的二元分类的问题：

那就算我们找到的\(g\)在\(D\)中提供的5组3-bit\((x, y)\)上和\(f\)上完全相同，在\(D\)以外，我们却仍相当于没有学到任何东西：

也就是说，如果任何“未知”的\(f\)都有可能发生的话，从已知资料\(D\)中进行学习将注定失败。

Probability to the rescue

刚才我们说到，在非常严格的环境下，learning是做不到的。但是我们可以想一些办法，用一些工具，去对未知的东西做一些推论。

想象我们有一个大大的罐子，其中有很多橘色的弹珠和绿色的弹珠。如果我们想要知道罐子中橘色弹珠占的比例。如果我们没有办法一颗一颗拿出来数，我们可以怎么做呢？或者说，我们怎么来估计一下橘色弹珠的比例呢？

当然有办法，我们可以使用抽样的方法：

那in-sample的比例\(\nu\)会不会告诉我们一些关于out-sample的比例\(\mu\)的信息呢？

• 不会
  • 因为即使罐子里大部分是橘色弹珠，你也有可能拿到一把绿色弹珠。（虽然几率很小，但有可能发生）
• 会
  • 因为有很大可能in-sample \(\nu\) 会和未知的\(\mu\)相近。

那么在数学上，我们怎么正式地表达这件事呢？

在一个很大的样本里，大致上来说\(\nu\)和\(\mu\)很接近： \[ P[|\nu - \mu| > \epsilon] \le 2exp(-2\epsilon^2N)\]

这被称为Hoeffding不等式，用在弹珠比例估计，丢硬币的正反面出现概率估计，利用民意调查估计民意等。通俗点说，\(\nu = \mu\)”大概、差不多“是对的（Probably Approximately Correct, PAC）。”大概“表示概率大，”差不多“表示值相差不大。

Hoeffding不等式：

• 对所有\(N\)和\(\epsilon\)成立
• 不需要知道\(\mu\)，也没有任何关于\(\mu\)的假设
• \(N\)越大，\(\epsilon\)越大，\(\nu \approx \mu\)的几率越大

也就是说，当\(N\)够大的话，我们是可以从已知的\(\nu\)推论未知的\(\mu\)的。

Connection to Learning

那我们前面说的这些，和learning有什么关系呢？下面是bin model和machine learning中元素的一一对应：

这样，我们就得到了这么一个推论：当\(N\)够大而且\(\mathbf{x}_n\)是从\(X\)中i.i.d.地抽出时，我们可以大概地通过已知\(D\)上\([h(\mathbf{x}_n) \ne f(\mathbf{x}_n)]\)的比例推断出未知的整个\(X\)上\([h(\mathbf{x}) \ne f(\mathbf{x})]\)的概率。

这幅图展示了在机器学习的流程中一些附加的要素：

其中的概率分布\(P\)决定了我们的数据集\(D\)中的\(\mathbf{x}_n\)是如何从\(X\)中产生的，就像决定了我们在从罐子里抓弹珠时，抓的是哪一把弹珠。我们并不需要知道它。

根据上图，对任意一个固定的\(h\)，我们可以大概地推测：

• 未知的 \(E_{out}(h) = \varepsilon_{\mathbf{x} \sim P} [h(\mathbf{x}) \ne f(\mathbf{x})]\)
• 通过已知的 \(E_{in}(h) = \frac{1}{N} \sum_{n=1}^{N} \|h(\mathbf{x}_n) \ne y_n \|\)

其中out是指out-sample，是指在未知的数据点；in是指in-sample，是指在已知的数据集中。

把Hoeffding定理代过来，我们有：对任意固定的\(h\)，在“大量”数据中，我们有：in-sample的误差\(E_{in}(h)\)大概和out-sample的误差\(E_{out}(h)\)接近（误差在\(\epsilon\)以内）： \[ P[|E_{in}(h) - E_{out}(h)| > \epsilon] \le 2exp(-2\epsilon^2N)\]

和“罐子”比喻相同，这里也有：

• 对所有\(N\)和\(\epsilon\)成立
• 不需要知道\(E_{out}(h)\)，也没有任何关于\(E_{out}(h)\)的假设
  • 不需要知道\(f\)和\(P\)
• “$ E_{in}(h) = E_{out}(h) $”是“大概、差不多”正确（PAC）

也就是说，如果”$ E_{in}(h) E_{out}(h) \(“而且”\)E_{in}(h)\(比较小“，那么可以推出\)E_{out}(h)也比较小\(。也就是在同一个\)P\(产生的数据点上，\)h f$。

那么对于任意固定的\(h\)，当数据够多的时候： \[ E_{in}(h) \approx E_{out}(h) \] 我们可以说我们学到了好的结果吗？

• 一个回答是可以
  • 当\(E_{in}(h)\)对一个固定的\(h\)很小的时候，而且算法\(A\)恰好选择了\(h\)作为输出\(g\)，那么”$ g = f$“ PAC。
• 另一个回答是不可以
  • 因为我们的定理只是针对某一个固定的\(h\)有bound，对不同的\(h\)之间并没有约束。所以这就造成了对不同的数据集，算法\(A\)总是会选择\(h\)作为\(g\)，然而：
    • \(E_{in}(h)\)几乎总是不小的
    • 恰恰使得”$ g f$“ PAC。

因此，真正的学习是：\(A\)应该能够自己从\(H\)中做选择，而不是被强迫去选哪一个\(h\)。

因此，我们现在做到的不能说是learning，只能说是verification：

也就是说，我们现在只能够做到验证某个\(h\)的好坏，但还不能做到从\(H\)中选出最好的那个\(h\)出来。

Connection to Real Learning

前面我们说到一个\(h\)时我们可以做verification，那多个hypothesis时我们怎么办呢？

如果每一个hypothesis我们让它对应一个罐子，假设其中一个罐子中抽出来的弹珠全是绿色的，也就是说其中一个hypothesis在我们的\(D\)上全对，那么我们要不要选它呢？

假设在台大ML课上，150个同学每个同学都丢5次硬币，其中一位同学的硬币\(g\)出现了连续5次正面。那么这就说明这位同学的\(g\)真的比其他同学的好吗？

从概率论的角度解释，显然不是：至少有一个硬币出现连续5次正面的概率为\(1 - (\frac{31}{32})^{150} > 0.99\)。

这件事告诉我们：在我们做选择时，”bad sample“的影响可能会恶化。所谓bad sample，就是Hoeffding定理中的例外情况，即\(E_{in}\)和\(E_{out}\)差的比较多的情况。比如在丢一个硬币时，你以为它比别的硬币好的概率是\(\frac{1}{32}\)，但是有150颗硬币时，你找到一颗你认为比别的更好的硬币的概率却大于0.99。

从不好的硬币，我们来看不好的数据：

• 不好的硬币：\(E_{out} = \frac{1}{2}, E_{in} = 0\)
• 不好的数据：\(E_{out}\)和\(E_{in}\)差的很远：
  • 例如\(E_{out}\)很大，而\(E_{in}\)却很小（在很多例子中成立）， 例如： 其中的\(D_{n}\)表示第\(n\)把抽出来的数据。

那如果有很多的\(h\)，所谓的不好的数据是怎么样呢？其实就是，它阻碍了算法\(A\)“自由”地做选择。而好的数据，则是可以让算法\(A\)自由地做选择，选什么都是对的。通俗一点讲，不好的数据是有可能让\(A\)踩到雷。而”有雷“，就是指至少存在一个\(h\)使得\(E_{out}(h)\)和\(E_{in}(h)\)差的很远：

因此，我们想在有\(M\)个hypothesis的情况下，为\(P_{D}[BAD \, D]\)找出一个bound。

\[ \begin{align} & P_{D}[BAD\,D] \\ = & P_{D}[BAD \, D \, for \, h_1 \, or \, BAD \, D \, for \, h_2 \, or \, \cdots \, or \, BAD \, D \, for \, h_M] \\ \le & P_{D}[BAD \, D \, for \, h_1] + P_{D}[BAD \, D \, for \, h_2] + \cdots + P_{D}[BAD \, D \, for \, h_M] (union \, bound) \\ \le & 2exp(-2\epsilon^2N) + 2exp(-2\epsilon^2N) + \cdots + 2exp(-2\epsilon^2N) \\ = & 2Mexp(-2\epsilon^2N) \end{align} \]

如同bin model的Hoeffding定理一样，这里finite-bin版本的Hoeffding定理有：

• 对所有的\(M, N, \epsilon\)成立
• 不依赖于任何一个\(E_{out}(h_m)\)，不需要知道\(E_{out}(h_m)\)，因此也就不需要知道\(f\)和\(P\)
• 可以说\(E_{in}(g) = E_{out}(g)\) PAC，对任何一个算法\(A\)都成立

那么看起来，最合理的演算法就是选一个\(E_{in}\)最小的\(g\)。

那么当\(|H| = M\)且有限时，\(N\)够大时，对\(A\)挑选的任意\(g\)，有\(E_{in}(g) \approx E_{out}(g)\)。那么如果\(A\)找到了一个\(E_{in}(g) \approx 0\)， PAC可以保证\(E_{out} \approx 0\)。那么更新之后的learning flow如下：

但是很多hypothesis set都是无限大的，例如perceptron中的无限条线。因此，现在问题还是没有完全解决。但是这里的有限的hypothesis set给了我们一个一个很好的出发点，让我们知道了learning可以做到一些事情。而无限的情况有一些困难，可能还要花费两到三节课的时间来解决这个问题。

本节的测验题非常有趣，值得一看：

Summary