不可能学习的情况
首先来看一个例子：给定下图，你是否能判断最后的图形应该属于哪个类别，是-1还是+1
可以说\(g({\bf x})=+1\)，因为所有已知\(y_n = +1\)的图形都是对称的。也可以说\(g({\bf x}) = -1\)，因为所有已知\(y_n = -1\)的图形左上角都是黑的。甚至可以找出更加复杂的规则，让\(g({\bf x})\)取得+1或-1。可以说，这是一道公说公有理，婆说婆有理的问题，无论怎么样都可以说得到的答案是错误的。即，这个问题不可学习。
接下来看一个更加数学一些的例子：假设输入空间\({\mathcal{X}} = \{0, 1\}^3, \mathcal{Y} = \{\circ, \times\}\)，已知的数据集\(\mathcal{D}\)如下表所示
| \({\bf x}_n\) | \(y_n = f({\bf x}_n)\) |
|---|---|
| 0 0 0 | \(\circ\) |
| 0 0 1 | \(\times\) |
| 0 1 0 | \(\times\) |
| 0 1 1 | \(\circ\) |
| 1 0 0 | \(\times\) |
由于输入情况比较简单，可以列举所有可能的\(h\)，也就是\(\mathcal{H}\)是一个有限集。我们能否学习到一个\(g \in \mathcal{H}\)，使得\(g \approx f\)？答案是，我们只能保证\(g\)在\(\mathcal{D}\)中跟\(f\)一样。但是对于那些在\(\mathcal{D}\)外的数据，类似于上面黑白格的例子，总可以找到一个\(f\)使其与\(g\)给出的答案不尽相同（甚至完全不同）。但是，机器学习的目的就是要看算法在未知数据上的表现情况。因此可以说，如果\(f\)可以取任何形式，那么从\(\mathcal{D}\)中学习模型以对\(\mathcal{D}\)外的元素做判断，这件事是注定要失败的
概率成为救世主
事已至此，需要开动脑筋，想一想是否有工具可以帮助我们从已知推断未知。这里再看一个例子：假设有一个很大的罐子，里面装了不计其数的橙球和绿球，则是否有可能知道橙球的比例？由于无法一颗一颗地数，因此直接求这个问题很难，但是可以通过随机取样的方法来推断这个比例。例如假设从里面抓了10颗球出来，里面有3颗是橙色的，那么橙球的比例就可以估计为30%。
推而广之，假设罐子中橙球的比例为\(\mu\)，绿球的比例为\(1-\mu\)，这里\(\mu\)是一个未知数。通过某种随机独立程序取样后观测到橙球的比例为\(\nu\)，绿球的比例为\(1-\nu\)，这里\(\nu\)是一个已知数，那么\(\mu\)和\(\nu\)有没有联系？这时，无法确定的说\(\nu\)就是\(\mu\)，因为也许罐子里只有5颗绿球，却有几百颗橙球，而这次随机抽样只拿到了这5颗绿球——这种情况是可能发生的。但是可以退而求其次地说，\(\mu\)和\(\nu\)在大部分情况下非常接近。准确地说，两者之间的关系可以用Hoeffding不等式来描述。即假设采样大小为\(N\)，\(\epsilon\)为一个比较小的数，那么有 \[ P[|\nu - \mu| > \epsilon] \le 2\exp(-2\epsilon^2 N) \] 即"\(\nu = \mu\)"这个结论“大概差不多是对的”（probably approximately correct, PAC）
Hoeffding不等式对任何\(N\)和\(\epsilon\)都成立，而且不需要知道真实的\(\mu\)值。抽样样本越多（即\(N\)越大），或者界限越松（即\(\epsilon\)越大），则\(\mu \approx \nu\)的概率越大
Fun time中，已知\(\mu = 0.4\)，取样数\(N=10\)，求取样后\(\nu \le 0.1\)的概率上界。这时可以把\(\epsilon\)设为0.3，代入Hoeffding不等式右侧可知上界为\(2\exp(-2 \times 0.3^2 \times 10) \approx 0.3306\)。但是如果实际计算可知这个概率应该为\(0.6 ^ {10} + 10 \times 0.6 ^ 9 \times 0.4 \approx 0.04636\)。即Hoeffding不等式只能提供一个上界，并不能对概率做出准确预估
概率与机器学习的联系
我们可以把“罐中取球”的问题与机器学习问题建立联系，即
- 未知的橙球比例\(\mu\)对应于学习问题中未知的目标函数\(f({\bf x})\)，或者也可以对应于，对给定新样本（测试数据）\(\bf x\)，假设函数值\(h({\bf x})\)是否等于目标函数值\(f({\bf x})\)
- 罐中的所有球对应于学习问题中的数据点\({\bf x} \in \mathcal{X}\)
- 取出橙球对应于\(h\)判断错误，即\(h({\bf x}) \not= f({\bf x})\)。注意，这里\(h\)是给定的，对下一条也如此
- 取出绿球对应于\(h\)判断正确，即\(h({\bf x}) = f({\bf x})\)
- 从罐中做大小为\(N\)的取样对应于学习问题中从数据集\(\mathcal{D} = \{({\bf x}_n, \underbrace{y_n}_{f({\bf x}_n)}\}\)学习
因此，同样的道理，如果\(N\)足够大而且\({\bf x}_n\)满足独立同分布假设（iid），那么根据已知的错分情况\([\![h({\bf x}_n) \not= y_n]\!]\)，就可以推断假设函数\(h\)在整个数据集上的错分概率\([\![h({\bf x}) \not= f({\bf x})]\!]\)。如果记\(h\)对已知数据的错分情况（样本内错误率）为\(E_{\rm in}\)，全集上的错分情况（样本外错误率）为\(E_{\rm out}\)，就会有 \[ \begin{align*} E_{\rm in}(h) &= \frac{1}{N}\sum_{n=1}^N [\![h({\bf x}_n) \not= y_n]\!] \\ E_{\rm out}(h) &= \mathcal{E}_{ {\bf x} \sim P}[\![h({\bf x}) \not= f({\bf x})]\!] \end{align*} \] 同理套用Hoeffding不等式，在\(N\)足够大的情况下，\(E_{\rm in}(h)\)和\(E_{\rm out}(h)\)之间相差超过\(\epsilon\)的概率为 \[ P[|E_{\rm in}(h) - E_{\rm out}(h)| > \epsilon] \le 2\exp(-2\epsilon^2 N) \] 即也可以说\(h\)的样本内错误率“大概差不多”相当于其样本外错误率，\(E_{\rm in}(h) \approx E_{\rm out}(h)\)。因此，如果\(h\)的样本内错误率很小，其样本外错误率也不会很大。在\(\bf x\)全都是通过分布\(P\)产生的前提下，可以说\(h \approx f\)。那么，如果算法\(\mathcal{A}\)能够从\(\mathcal{H}\)中选择到了\(E_{\rm in}\)足够小的\(h\)，其返回为\(g\)，那么我们能否说\(g \approx f\)？如果对给定的\(h\)，\(E_{\rm in}\)足够小，而且\(\mathcal{A}\)真的把\(h\)当做\(g\)返回，那么\(g = f\)是PAC的。但是如果\(\mathcal{A}\)被写死了，无论给定什么数据集都要返回\(h\)作为\(g\)，那么\(E_{\rm in}(h)\)其实往往并不是最小的，此时\(g \not= f\)反而是PAC的。这意味着真正的学习不是让\(\mathcal{A}\)返回固定的\(h\)，而是要让\(\mathcal{A}\)在解空间\(\mathcal{H}\)中搜索。不过这提供了一个验证的思路，即可以选出一些未在训练过程中使用的历史数据送给某个候选模型\(h\)，在这之上观测其表现如何。
概率与真正学习的联系
真正的学习过程中，我们不会只有一个\(h\)来验证，而是要在\(\mathcal{H} = \{h_1, \ldots, h_M\}\)中做出选择。假设找到了一个\(h_i\)在训练集上表现完全正确，是否应该把它选择为\(g\)？
先不考虑这个问题。假设有150个人，每个人掷同一枚硬币5次，如果有一个人能连续扔出5个正面，那么这是否意味着这枚硬币不是均匀的？答案是不可能。因为假设硬币均匀，由150人每人掷5次，至少有一个人扔出连续5个正面的概率是\(1 - (\frac{31}{32})^{150} > 99%\)。那么返回刚才的例子，这意味着\(h_i\)即便在训练集上全对，也不能确定它就比其它的\(h'\)好（可能大家都是瞎猜）。假设将造成\(E_{\rm in}\)和\(E_{\rm out}\)相差比较大的取样称为“不好的采样”，可以看到当存在选择的时候，选择会恶化不好的采样（即让你选到错误\(h\)的概率变得很大）。
同样的道理，也可以把\(E_{\rm in}(h)\)和\(E_{\rm out}(h)\)差得特别大的数据称为“不好的数据”。注意Hoeffding不等式只能保证\(h\)遇到“不好的数据”的概率不是很大。事实上，每个\(h_i\)都会有对应的一些数据\(\mathcal{D}'\)成为“不好的数据”，例如下表
| \(\mathcal{D}_1\) | \(\mathcal{D}_2\) | \(\ldots\) | \(\mathcal{D}_{1126}\) | \(\ldots\) | \(\mathcal{D}_{5678}\) | |
|---|---|---|---|---|---|---|
| \(h_1\) | BAD | BAD | ||||
| \(h_2\) | BAD | |||||
| \(h_3\) | BAD | BAD | BAD | |||
| \(\ldots\) | ||||||
| \(h_M\) | BAD | BAD |
从上表可以看到，给出的这四条数据里，只有第1126条是“好的”数据，其余的都会给不同的\(h\)带来麻烦。接下来的问题是，如果对某条数据\(\mathcal{D}_i\)，只要存在\(h_i \in \mathcal{H}\)使得\(\mathcal{D}_i\)是\(h_i\)“不好的数据”，那就称该数据为“不好的数据”，那么对所有\(\mathcal{D}\)，如果算法\(\mathcal{A}\)能够自由选择数据，则算法遇上“不好的数据”的概率有没有上界
答案是有的。使用事件的并的概率的不等式，假设\(|\mathcal{H}| = M\) ，可以做如下推导 \[ \begin{align*} &P_{\mathcal{D}}[{\rm BAD\ }\mathcal{D}] \\ = &P_{\mathcal{D}}[{\rm BAD\ }\mathcal{D} {\rm\ for\ }h_1 {\rm\ or\ }{\rm BAD\ }\mathcal{D} {\rm\ for\ }h_2 {\rm\ or\ }\ldots {\rm\ or\ }{\rm BAD\ }\mathcal{D} {\rm\ for\ }h_M] \\ \le &P_\mathcal{D}[{\rm BAD\ }\mathcal{D} {\rm\ for\ }h_1] + P_\mathcal{D}[{\rm BAD\ }\mathcal{D} {\rm\ for\ }h_2] + \ldots + P_\mathcal{D}[{\rm BAD\ }\mathcal{D} {\rm\ for\ }h_M] \\ \le &2\exp(-2\epsilon^2N) + 2\exp(-2\epsilon^2N) + \ldots + 2\exp(-2\epsilon^2N) \\ = &2M\exp(-2\epsilon^2N) \end{align*} \] 即在假设集\(\mathcal{H}\)为有限集，数据量足够的情况下，每个\(h\)都是安全的，即无论\(\mathcal{A}\)如何选，其返回的\(g\)都会有\(E_{\rm in}(g) = E_{\rm out}(g)\)是PAC的。所以，最理性的\(\mathcal{A}\)会选择\(E_{\rm in}(h_m)\)的那个假设函数返回为\(g\)
但是当\(M\)无限大时，如何证明机器学习是可行的？这个问题留在接下来的课程中解决
到此为止，台大机器学习课的第一个部分已全部结束。这一部分解决的是机器何时能够学习的问题
