深度译文：机器学习那些事

【原题】A Few Useful Things to Know About Machine Learning

【译题】机器学习的那些事

【作者】Pedro Domingos

【

【说明】译文载于《中国计算机学会通讯》 第 8 卷 第 11 期 2012 年 11 月 ，本文译自Communications of the ACM 2012年第10期的“A Few Useful Things to Know About Machine Learning”一文。

机器学习系统自动地从数据中学习程序。与手工编程相比，这非常吸引人。在过去的20年中，机器学习已经迅速地在计算机科学等领域普及。机器学习被用于网络搜索、垃圾邮件过滤、推荐系统、广告投放、信用评价、欺诈检测、股票交易和药物设计等应用。

麦肯锡全球研究院（the McKinsey Global Institute）最近一份报告指出，机器学习（又称数据挖掘或者预测分析）将驱动下一轮创新【15】。现在已经有几本优秀的机器学习教材书可以供感兴趣的研究者和实践者使用（例如米切尔（Mitchell）和维滕（Witten）等人的教材【16,24】）。但是，成功使用机器学习所应掌握的大量“民间知识”并没有出现在这些教材中。因此，很多机器学习项目浪费了大量时间，甚深入了解所需的“民间知识”可推进机器学习的应用。至最终也没有得到理想的结果。其实这些“民间知识”非常容易理解。本文的目的就是介绍这些知识。

机器学习有许多不同的类型，但为了展示方便，本文将主要介绍其中最常用的类型：分类。但是，本文所探讨的问题适用于所有的机器学习类型。一个分类器（classifier）是一个系统，系统输入是一个包括若干离散或连续的特征值（feature values）的向量，系统输出是一个离散值，代表分类的类别（class）。例如，一个垃圾邮件过滤器会将邮件信息分类到“是垃圾邮件”和“不是垃圾邮件”两个类别中。它的输入可以是一个布尔向量 x=(x1,…,xj,…,xd) ，其中如果词典中的第 j 个词出现在该邮件中，则 xj=1，否则 xj=0 。一个学习器将一个训练集（trainingset）样例 (xi,yi) 作为输入，其中xi=(xi,1,…,xi,d) 是观察到的输入，yi 是相应的输出，学习器的输出是一个分类器。对学习器的检验就是判断它输出的分类器是否能够对将来的输入样例 xt 输出正确的 yt（例如，垃圾邮件过滤器是否能够将训练时没有见过的邮件信息正确分类）。

学习=表示 + 评价+ 优化

假设有一个应用，你认为机器学习有可能在其中发挥作用。那么，你面临的第一个问题是各种机器学习算法令人眼花缭乱。应挑选使用哪一个？现在有成千上万的机器学习算法，每年还有成百上千的新算法发表出来。免迷失在这么多算法中的关键是，要认识到这些算法都是由三个部分组成的，分别是：

表示（Representation）

一个分类器必须用计算机可以处理的某种形式语言来表示。反过来讲，为学习器选择一种表示，就意味选择一个特定的分类器集合。学习器可能学出的分类器只能在这个集合中。这个集合被称为学习器的假设空间（hypothesis space）。如果某个分类器不在该空间中，它就不可能被该学习器学到。与此相关的一个问题是如何表示输入，即使用哪些特征，本文稍后介绍。

评价（Evaluation）

我们需要一个评价函数（亦称为目标函数或打分函数）来判断分类器的优劣。机器学习算法内部使用的评价函数和我们希望分类器进行优化的外部评价函数有所不同。这是为了便于优化，接下来会讨论。

优化（Optimization）

最后，我们需要一个搜索方法，能够在假设空间中找到评价函数得分最高的那个分类器。优化技术的选择对学习器效率至关重要；而当评价函数有多个最优结果时，优化技术也有助于从中选择。初学者通常会采用现成的优化方法，之后再用定制专门的优化方法来替代。表 1 展示了三个组成部分常见的例子。例如，对一个测试样例， k-近邻方法会寻找它的 k 个最相似的训练样例，并将这些样例中出现最多的类别作为该测试样例的类别。超平面方法会为每一个类别构造一个特征的线性组合，并将得分最高的组合所对应的类别作为预测结果。决策树方法会在树上的每个内部节点测试一个特征，每个特征值会对应一个分支，而不同的叶子节点会对应不同的类别。算法 1 展示了一个极简单的二分类决策树学习器，其中使用了信息增益（informationgain）和贪心搜索（greedysearch）【20】。InfoGain(xj,y ) 表示特征 xj 与类别 y 之间的互信息（mutualinformation）。 MakeNode(x,c0,c1 ) 会返回一个测试特征 x 的节点，该节点以 c0 作为 x

= 0 时的孩子节点，以 c1 作为 x = 1 时的孩子节点。

当然，并不是表 1 中从各列选出元素的相互组合都同样有意义。例如，离散表示很自然地与组合优化相结合；而连续表示则与连续优化相结合。然而，很多学习器同时包含离散和连续的部分。实际上，所有可能的组合也都快被实现过了。

大部分教科书是以表示为视角组织内容的。这通常会让人忽略掉一个事实，即其他部分也同样重要。虽然对如何在每个部分做出选择并没有简单的秘诀，但本文将涉及其中几个重要的问题。正如我们以后会看到的那样，机器学习项目中的某些选择甚至比学习器的选择更加重要。

泛化（Generalization）很重要

机器学习的基本目标是对训练集合中样例的泛化。这是因为，不管我们有多少训练数据，在测试阶段这些数据都不太可能会重复出现。（注意，如果在词典中有 100000个词，前述垃圾邮件过滤器将会有种 2100000 种可能的不同输入）。

在训练集上表现出色其实很简单（只要记住这些训练样例即可）。机器学习初学者最常犯的错误是在训练数据上做测试，从而产生胜利的错觉。如果这时将选中的分类器在新数据上测试，它往往还不如随机猜测准确。因此，如果你雇人来训练分类器，一定要自己保存一些数据，来测试他们给你的分类器的性能。相反，如果你被人雇来训练分类器，一开始就应该将一部分数据取出来，只用它们来测试你选择的分类器性能，接下来再在整个数据上学习你最终的分类器。

你的分类器可能会在不知不觉中受到测试数据的影响，例如你可能会使用测试数据来调节参数并做了很多调节（机器学习算法有很多参数，算法成功往往源自对这些参数的精细调节，因此这是非常值得关注的问题）。当然，保留一部分数据用于测试会减少训练数据的数量。这个问题可以通过交叉验证（cross – validation）来解决：将训练数据随机地等分为若干份（如 10份），其中的每一份均可用作测试，而剩下的数据用作训练，然后将每个学习的分类器在它没见过的样例上进行测试，将测试结果取平均后，就可用来评价不同参数设置的性能。

仅有数据还不够

将泛化作为目标带来的另外一个重要结果是，仅有数据还不够，无论你有多少。考虑要从100万样例中学习一个包含 100个变量的布尔函数。此时将有2100  – 106 个样例的类别是不知道的（注：这里2100 表示 100个布尔变量的所有可能情况的个数，而106表示已经看到的100万样例，因此有 2100 -106 个可能情况是没有看到过的，因此也不知道它们的类别）。你如何确定那些样例的类别呢？在没有更进一步信息的情况下，除了抛硬币随机猜之外将束手无策。哲学家大卫 ·休谟（David Hume）在 200多年前首次指出这一问题（以某种不同的形式），但直到今天机器学习中的很多错误仍是由于没有意识到这一问题造成的。每个学习器都必须包含一些数据之外的知识或假设（assumption），才能够将数据泛化。这一概念被沃尔伯特（Wolpert）形式化为“没有免费的午餐”定理。根据该定理，没有学习器能够比在所有可能的布尔函数中随机猜测的结果更优【25】。

这似乎是一个非常让人失望的消息。那我们还能指望能学到什么东西吗？幸运的是，在真实世界中，我们要学习的函数并非均匀地来自所有可能的函数！实际上，一些非常泛泛的假设——比如平滑（smoothness），相似的样例有相似的类别，有限依赖，或者有限复杂度——通常足够起很大作用，这也是机器学习能够如此成功的重要原因。如同演绎（deduction）一样，归纳（induction，正是学习器所做的） 起到知识杠杆的作用 —— 它将少量的输入知识转化成为大量的输出知识。归纳是比演绎强大得多的杠杆，只要求很少的输入知识就可以产生有用的结果，但是它终归不能在没有知识的情况下工作。而且就像任何杠杆一样，输入越多，我们得到的输出就越多。

从中可以得到的一个推论是，选择表示的关键标准之一是，它比较易于表达什么类型的知识。例如，如果我们拥有大量关于在我们的领域是什么造成样例相似的知识，基于实例的方法也许就是合适的选择。如果我们拥有概率依赖的知识，图模型则比较适合。如果我们拥有每个类别要求的先决条件的知识，“ If…Then…（如果…那么…）”规则的表示也许是最好的选择。在这一点上，最有用的学习器是那些并非将假设固化在其中，而是允许我们用显式规定假设，在大范围改变假设，并自动将其体现在学习中（例如采用一阶逻辑 【21】或者语法 【6】）的学习器。

说到这里，学习需要知识，这并不让人惊讶。机器学习不是魔术，它无法凭空变出东西。它所做的是由少变多。编程就像所有的工程技术那样，意味着大量的工作，必须从头开始建造一切。而机器学习更像是种田，它让大自然做大部分工作。农夫将种子与肥料混合种出庄稼。学习器将知识和数据结合“种出”程序。

过拟合（Overfitting）有多张面孔

如果我们拥有的知识和数据并不足以学习出正确的分类器，将会怎样呢？我们就得冒风险构建一个分类器（或者其中一部分），这个分类器并非建立在现实基础上，而是将数据随机表现加以解读。这个问题称为过拟合，它是机器学习中的棘手问题。当你的学习器输出的分类器在训练数据上准确率为 100%，而在测试数据上仅有 50% 的时候（而本来可以学到一个分类器能够在两个数据上均达到 75% 的准确率），说明这个分类器发生过拟合了。

机器学习领域的每个人都了解过拟合，但过拟合会以多种并不明显的形式出现。一种理解过拟合的方式是将泛化误差（generalization error）分解为偏置（bias）和方差（ variance）【9】。偏置度量了学习器倾向于一直学习相同错误的程度。方差则度量了学习器倾向于忽略真实信号、学习随机事物的程度。图 1用朝板子扔飞镖作为类比进行了直观说明。

一个线性学习器有较高的偏置，因为当两个类别的交界不是超平面的时候，这个学习器就无法进行归纳（摘注：原文 A linear learner has high bias, because when the frontier between two classes is not a hyper-plane the learner is unable to induce it）。决策树就不会有这个问题，因为它可以表示任意的布尔函数，但在另一方面，决策树会面临高方差的问题：在同一现象所产生的不同训练数据上学习的决策树往往差异巨大，而实际上它们应当是相同的。类似道理也适用于优化方法的选择上：与贪心搜索相比，柱搜索的偏置较低，但方差较高，原因是柱搜索会尝试搜索更多的假设。因此，与直觉相反，一个学习能力更强的学习器并不见得比学习能力弱的效果更好。

图 2 示例说明了这一点（注：训练样例含有 64 个布尔类型特征和 1 个根据一个集合的“如果…那么…”的规则集合计算得到的布尔类型的类别。图中的曲线是对 100 次运行结果的平均，每次对应不同的随机产生的规则集合。误差条（error bar）代表两个标准方差。具体细节请参考论文【10】）。即使真正的分类器是一个规则集合，但根据 1000个样例学习的朴素贝叶斯学习器（摘注：原文 Naive Bayes）仍比一个规则学习器的准确率更高。甚至当朴素贝叶斯错误地假设分类面是线性的，也依然如此。这种情形在机器学习领域很常见：一个强错误假设比那些弱正确假设更好，这是因为后者需要更多的数据才能避免过拟合。

交叉验证可以帮助避免过拟合，例如通过交叉验证来选择决策树的最佳大小。但这不能彻底解决问题，因为假如我们利用交叉验证做太多的参数选择，它本身就会开始过拟合【17】。

除了交叉验证以外，还有很多方法可以避免过拟合。最常用的方法是对评价函数增加一个正则项（regularization term）。这样做可以惩罚那些包含更多结构的分类器，偏好更小的分类器，从而降低过拟合的可能性。另一个方案是在决定是否增加新的结构时进行诸如卡方测试（chi-squre）等统计显著性检验（statistical significance test），用来决定类别分布是否会因为增加这个结构而不同。当数据非常缺乏时，这些技术非常有用。然而，你应该对那些宣称某项技术“解决”了过拟合问题的说法持怀疑态度。我们会很容易在避免过拟合（或者说“方差”）时，造成另外一个相反的错误—— 欠拟合（ underfitting，或者说“偏置”）。要学习一个完美的分类器来同时避免过拟合和欠拟合，事先又没有足够知识，这种情形下没有任何单一技术能够总是表现最好（没有免费的午餐）。

对过拟合的一个常见误解是认为它是由噪音造成的，例如有些训练样例的标注类别是错误的。这的确会加剧过拟合，因为分类器会调整分类面让那些样例保持在分类器认为正确的一侧。但是即使没有噪音依然会发生严重的过拟合。例如，假如我们学习一个布尔类型分类器，它是训练数据中所有标为“true”的样例的析取（disjunction）。（换句话说，这个分类器是一个析取范式（disjunctive normal form）的布尔类型公式，其中每一项是某个特定训练样例的所有特征值的合取（conjunction）。）这个分类器对所有的训练样例都分类正确，但对测试样例中的每个正例都分类错误，不管训练数据是否有噪音。

多重检验（multiple testing）【13】问题与过拟合密切相关。标准的统计检验中只有一个假设被检验，而现代学习器在结束学习前会轻易地检验上百万个假设。因此，那些看上去很显著的结论实际并不如此。例如，一个连续十年跑赢市场的共同基金（mutual fund）看上去很引人注目。但当你发现，如果有1000家基金，每家都有50%的概率在某年跑赢市场，在这种情况下，极有可能会有一家基金能够凭侥幸而连续10次都跑赢市场。这个问题可以通过在显著性检验中将假设的个数考虑进去来解决，但这样也会导致欠拟合。更好的途径是控制错误接受的非零假设（non-null hypotheses）的比率，该方法通常被称为错误发现率（false dis-covery rate）方法【3】。

直觉不适用于高维空间

机器学习中紧接过拟合之后的最大问题就是维度灾难（curse of dimensionality）。这一概念是由贝尔曼（Bellman）在1961年首先提出的，用来描述以下事实：许多在低维空间表现很好的算法，当输入是高维度的时候，就变得计算不可行（intractable）了。但在机器学习领域，这有更多的意义。随着样例维度（即特征数目）的增长，正确泛化的难度会以指数级增加，原因是同等规模的训练集只能覆盖越来越少的输入空间比例。即使对于中等大小的 100维布尔空间，一个包含 1 万亿样例的大型数据集合也只能覆盖输入空间的 10-18 左右(译注：这里作者指的是输入为布尔量时的情形)。这体现了机器学习存在的必要性，也是它的难点所在。

更严格地讲，机器学习算法所（显式或隐式）依赖的基于相似度的推理在高维空间不再有效。现在考虑一个采用汉明距离（hamming distance）作为相似度度量的最近邻分类器，并设定样例的分类类别是 x1∧x2 。如果没有其他特征，这是一个很容易的问题。但是当增加 98 个不相关的特征 x3,…,x100 的时候，来自这些特征的噪音会淹没来自 x1 和 x2 的信号，导致所找到的最近邻相当于做出随机预测。

更多的困扰是，即使所有的100个特征都是相关的，最近邻方法依然会有问题。这是因为在高维空间所有的样例都变得很相似。例如，假设所有样例分布在规则的网格上，现在考虑一个测试样例 xt。如果网格是 d-维的，会有个 2d 个 xt 最近邻样例与 xt 的距离相等。因此，随着维数的增加，越来越多的样例会变成 xt 的最近邻，以致最后最近邻的选择实际上变成随机的（类别选择也因此变成随机的）。

这只是高维空间上更广泛问题的一个实例。我们的来自三维世界的直觉在高维空间通常并不奏效(摘注：原文our intuitions, which come from a three dimensional world, often do not apply in high-dimensional ones.)。在高维空间，多元高斯分布（multivariate Gaussian distribution）的大部分质量（mass）并不分布在均值附近，而是在逐渐远离均值的一层“壳”上；打个比方，一个高维的橘子的大部分质量不在瓤上，而是在皮上。如果数量一定的样例均匀分布在一个（维数不断增加的）高维的超立方体中，那么超出某个维数后，大部分样例与超立方体的某一面的距离要小于与它们最近邻的距离。如果我们在超立方体中内接一个超球面，那么超立方体的几乎所有质量都会分布在超球面之外。这对机器学习是一个坏消息，因为机器学习常常用一种类型的形状来近似另一种类型的形状。

在二维或三维空间构建分类器很简单，我们可以仅通过肉眼观察发现不同类别样例的分界线（甚至可以说，假如人们有在高维空间中观察的能力，机器学习就没有存在的必要了）。但是在高维空间中很难理解正在发生什么。因此也就很难设计一个好的分类器。人们也许会天真地认为收集更多的特征永远不会有什么坏处，因为最坏的情况也不过是没有提供关于类别的新信息而已。但实际上这样做的好处可能要远小于维度灾难带来的问题。

幸运的是，有一个效应可以在一定程度上抵消维度灾难，那就是所谓的“非均匀性的祝福”（blessing of nonuniformity）。在大多数应用中，样例在空间中并非均匀分布，而是集中在一个低维流形（manifold）上面或附近。例如在手写体数字识别任务中，即使数字图片的每个像素都单独作为一个特征，近邻方法在该任务上表现依然良好，这是因为数字图片的空间要远小于整个可能的空间。学习器可以隐式地充分利用这个有效的更低维空间，也可以显式地进行降维（例如特南鲍姆（Tenenbaum）的工作【22】）。

理论保证（Theoretical Guarantees）与看上去的不一样

机器学习论文充满了理论保证。最常见的类型是能保证泛化所需样例数目的边界（bound）。你应当如何理解这些保证呢？首先，需要注意的是它们是否可行。归纳与演绎相反：在演绎中你可以保证结论是对的；在归纳中就难说了。这是很多世纪以来的普遍共识。最近几十年的一个重要进展是我们认识到可以有归纳结果正确性的保证，特别是如果我们愿意接受概率保证（摘注：原文One of the major developments of recent decades has been the realization that in fact we can have guarantees on the results of induction, particularly if we’re willing to settle for probabilistic guarantees.）。