2.2 核心推导

2.2.1 机器学习可行条件

可能读者对于本章引言中的案例会存在以下两个疑惑。

疑惑1：既然胡峦才和孟凡田的模型期望表现相同，那么机器还有什么可学习的？

疑惑2：目标函数是未知的，完美地预测样本内数据不算什么，只有在样本外数据上表现好才称得上是真正的学习，但样本外数据又是未知的，机器能学习到吗？机器学习是一种骗局吗？

疑惑1好解释。根据NFL定理，假设所有目标函数发生的可能性都相同，但是，实际上并非如此。比如某组数据呈现出明显的线性关系，那么其目标函数最有可能为线性函数，而几乎不可能为十阶多项式函数。由此可知，每个具体问题都有一个最有可能的目标函数，以及最优算法，而脱离具体问题空谈算法毫无意义。

解决疑惑2才是本章的重点。我们的最终目的就是找到一个可以将任意数据都能正确分类的目标函数c。但是，这是不可能的，因为任意数据中都包括模型还没有见过的数据，数据是未知的，那么又如何能学习到作用在未知数据上的目标函数c呢？这时我们做一些退让，既然不可能找到c，那么就来找c的“影子”g。

机器学习的流程图如左图所示。

机器学习就是将算法A用在训练集上，并从假设函数集合H={h₁，h₂，…，h_M} 中选取最逼近目标函数c的最优假设函数g。

(x⁽¹⁾,y⁽¹⁾),(x⁽²⁾,y⁽²⁾),…,(x^(m),y^(m))

既然g是c的“影子”，那么g≈c。

有一个重要假设：“所有数据特征x都来自相同概率分布P，即便P是未知的”。没有它，机器学习无法进行。让在训练集（正态分布）中学习过的模型在未见过的数据上（泊松分布）做分类，模型表现无参考价值。加上概率分布P的机器学习流程图如右图所示。至此，已经有一个机器学习的框架了，下面的目标是找一个g，并且g≈c。

● 如果找到g，则机器学习可行。

● 如果找不到g，则机器学习不可行。

从误差角度看，在机器学习过程中：

● 当找到c（理想世界）时，真实误差为零。

● 当找到g（努力目标）时，真实误差很小。

● 当没找到g时，真实误差很大。

要证明机器学习是可行的，需要完成下图所示的逻辑链。

下表中总结了逻辑链中的步骤和涉及的问题。

上表中的两个“如果”（条件）分别对应了“上天眷顾”（运气）和“自身实力”（实力）：

当两个条件成真时，那么真实误差也很小，机器学习可行。“上天是眷顾机器学习者的”。下面会证明“真实误差和训练误差在某些条件下会很接近”；而最小化训练误差要通过自身实力来实现，因此你只有努力学习各种算法了。学完本章，至少你会得到“上天眷顾”，有了理论支持，从此可以钻研各种算法。后面会介绍以下内容。

● 从已知推未知：将已知的通过民意调查得到的特朗普的支持率和未知的全体选民支持特朗普的概率联系起来。

● 从民意调查到机器学习：类比民意调查和机器学习，在只能选择单一假设函数的情况下，根据已知的样本内误差（训练误差）推测出未知的样本外误差（真实误差）。

● 从单一到有限：使用单一假设函数并根据训练误差推测出真实误差不算学习，顶多算验证；而从有限多假设函数中选取最优假设函数，并根据训练误差推测出真实误差才算学习。

● 从有限到无限：假设函数通常有无限多个，因此，上面证明的结论不适用。

● 从无限到有限：通过增长函数和突破点等概念，将无限个假设转换成有限个假设。

此时，看完上面的内容你可能会一头雾水，但看完本节的内容后保证你会茅塞顿开。

2.2.2 从已知推未知

民意调查就是做统计采样。比如在美国的加州做民意调查，从全部选民中随机挑选一批选民，记录他们的投票倾向，将结果综合起来就得到加州选民的意向了。

● 随便找一个加州人调查，只能得到“一边倒”的结论，这种民意调查的结果没有任何意义。

● 调查了上万个选民后，综合后的结果就相当准了，这种民意调查的结果可以作为总体选民意向。

上面加粗的文字只能说是“概率上近似正确”（Probably Approximately Correct，PAC）。这种说法是不是很难理解？先看下图。

右图的左半部分代表总体，用特朗普的头像个数除以总头像个数，就得到特朗普的真实支持率u：

● u是一个未知量（因为人太多，计算起来费财又费力）。

● u是一个确定量（不会变，客观存在于全体选民结果中）。右图的右半部分代表样本，从总体选民中随机选出选民并记录支持特朗普的数据。在样本中，特朗普的头像个数除以样本的总头像个数就是特朗普的调查支持率v：

● v是一个已知量（样本数少，便于计算）。

● v是一个随机量（随着每次民意调查采样的不同而变化）。

通过民意调查之后，我们计算出v，但是了解v对于了解u有帮助吗？

你看，这就是斯蒂文与霍夫丁的差距。斯蒂文自作聪明地以为举了一个反例就能推翻“从样本v不能推断总体u”这个结论；而大师霍夫丁则从“概率上近似正确”上做文章，称“当样本足够多时，v≈u”，并且还给出严谨的数学公式证明。

霍夫丁不等式^[2]（Hoeffding's Inequality）就量化了v与u的关系。

其中，

ε是任意正数。

n是样本个数。

|v-u|＞ε指的是v和u相差大于ε。

P是事件|v-u|＞ε的概率。

上面两个不等式是等价的，通常我们会用第一个。不要被它吓住，其实它很直观：如果选一个很小的ε（言外之意就是想让v和u的值接近），那么为了让不等式右边的很小，只能调大n值。

举一个实际例子，如果你希望特朗普真实的支持率v和民意调查的支持率u相差不超过2%，那么在调查5000个人后（n=5000），计算出，换句话说就是在98.16%的情况下，

v -0.02≤u≤v+0.02

这时，如果用v来代替u，在98.16%的情况下是没问题的。上面的公式和例子简单地说就是：

如果n很大，则v≈u这个说法在概率上近似正确。

这时容易计算的v是难计算的u的一个很好的逼近。这个不等式的更厉害之处是：

（1）右边的概率上界与u完全无关。

（2）n是样本个数，不是总体个数，容易计算。

不管总体个数是多少，不管总体变量u的未知程度如何，给定一个n就能计算一个“从已知到未知”的概率上界。到现在，经过“从已知推未知”这一步，我们应该学习到了一些知识，比如通过v了解u。

2.2.3 从民意调查到机器学习

民意调查的原理我们已经弄清楚了，可本书讲的是机器学习，与它有什么关系？通过对比可以发现两者的本质是一样的，这样我们就可以把用在民意调查的那一套方法用在机器学习上。

根据霍夫丁不等式，证得民意调查不等式，下表将其进行类比，将v、u用e_in（h）、e_out（h）替换，得到机器学习不等式

对于上面的不等式：

● 对所有n和ε都成立。

● 与e_out（h）无关，因此目标函数c仍然可以保持未知。

● e_out（h）≈e_in（h）在概率上近似正确。

换一句话说，当数据足够多（n足够大）时，训练误差和真实误差的差别非常小（ε很小），只要你有能力找到好的算法，使得训练误差很小，那么真实误差也会很小。

更通俗一点地说，把“训练误差和真实误差差别大的h”当成“坏h”，因为这时我们无法通过h很小的训练误差推出h很小的真实误差，那么将上面的不等式（机器学习版本）可以写成

为了证明机器学习是可行的，我们希望证明h不是“坏”的，以及“P（坏h）”很小，进而要证明很小。这样看，只要增大n就可以证明以上结果。难道这样就已经证完了学习是可行的？还没有……

2.2.4 从单一到有限

2.2.3节中的结论只用了一个固定的假设函数h，而不是一组假设函数h₁，h₂，…，h_M，机器没有学习到任何东西，最多只能说验证了固定h和目标函数c的差距，验证的结果有两种（现在已经知道e_out（h）≈e_in（h）而e_out（c）=0）：

（1）如果e_out（h）≈0，那么e_in（h）≈0，h学到c，用h来预测的真实误差接近于0，h就预测准了。

（2）如果e_out（h）≫0，那么e_in（h）≫0，h没学到c，用h来预测的真实误差远大于0，h预测不准。

如果e_out（h）≈1，那么e_in（h）≈1，h完全没学到c，但是每次反过来，h就能学到c。因此，当e_out（h）=0.5时，才是最坏的情况，上述验证过程的流程图如下图所示。

与前面机器学习过程的流程图相比，本图不同之处在于把h用到新数据中计算误差。

● 如果误差很小，则验证出h学到了c。

● 如果误差很大，则验证出h没学到c。

记住，该过程只是验证，和学习无关！因为当只有一个h时，它的训练误差就是客观存在的，我们只能验证它是大还是小，却不能减小它（减小误差才和学习挂钩）。

现在所有问题都集中到如何用一个机制使得e_in（h）≈0。很简单，从一组假设函数h₁，h₂，…，h_M中选出一个使得e_in（h）最小，并将这个最优假设函数设定为g，只要满足

P（|e_in（g）-e_out（g）|＞ε）≤很小的数

那么e_out（g）≈0，g真的学到了c。上面不等式成立吗？成立——霍夫丁。

● 从数学公式到通俗说法的转换。

● 如果g是“坏”的，那么至少有一个h是“坏”的。

● 联合上界。

● 将霍夫丁不等式用在每一个h_m上。

● 简单加总。

从h升级到g，唯一的改变就是不等式的右边多出一个M（假设函数的个数）：

为了证明机器学习是可行的，我们希望证明g不是“坏”的，从而要证明“P（坏g）”很小，进而要证明很小。这样看，只要增大n就可以证明以上结果。现在我们应该证完了机器学习是可行的了。

2.2.5 从有限到无限

在实际问题中，假设函数的个数M真的是有限个吗？看一看下图。

图中的所有黑线都可以将红心和绿圆线性分开，但是这种黑线有无数条。假如每一条黑线对应着一个假设函数，那么M是正无穷的。下面代入2.2.4节证出的不等式看一看：

即便增大n，当M是正无穷时，我们只能证出“P（坏g） ≤ 很大的数”，显而易见，一般人都知道“P（坏g）”是一个概率，而且小于或等于1。问题到底出在哪儿呢？

2.2.6 从无限到有限

问题出在坏事情是相互重合的，“坏h₁”和“坏h₂”可能基本是一样的，而使用联合上界会使得上界过松，也就是下面的不等式的右边的数值过大。

P（坏g） ≤P（坏h₁）+P（坏h₂）+…+P（坏h_M）

既然找到了问题的根源，现在就要解决问题，看是否能将无限值M变成一个有限值。答案是可以，但首先得介绍一下等效假设函数，如下图所示。

图中的h₁、h₂和h₃是等效的，被归结为等效的一类（等效类），而增长函数m_H（n）是计算等效类的个数。因为增长函数的上界是2ⁿ，所以用m_H（n）来替代上面不等式里的M，得到

在≤比1大的数这一步中，分子和分母都可写成e^an的形式，这样它们是等阶无穷大的（当n趋近无穷大时，分子和分母趋近无穷大的速率一样），因为ln2通常会比2ε²大，因此，最后的结果会比1大。但是，一般人都知道概率小于或等于1。

问题就出在增长函数的上界2ⁿ过大，如果能证明m_H（n）是的低阶无穷大就好了（即当n趋近无穷大时，分母趋近无穷大的速率比分子快）。还记得2.1.3节最后对m_H（n）是多项式的猜测吗？多项式函数的确是指数函数的低阶无穷大，如果该猜测成立，则机器学习的可行性就得到证明了。

事实上，增长函数的确有一个更小的上界，那就是多项式^[3]，

这时再来看一看“坏g”的概率是否能被限制为一个很小的数。

最后一步是由洛必达法则得到的，对k-1阶多项式函数和指数函数分别求k-1次导数后，分子为常数，而分母还是与n相关的指数函数，这样，当n很大时，整个商会很小。于是我们得到

再回到2.2.1节证明机器学习可行的两个必要条件：

● 证明在某种条件下e_in（g）≈e_out（g）。[上天眷顾]

● 使用不同算法使得训练误差e_in（g）很小。[自身实力]

“上天眷顾”这个条件已被上面的不等式证明了，“自身实力”这个条件要看个人运气。