理解机器学习：从理论到算法

Boyajian’s Star Dimmings Follow 782-Day Orbital Clock, New Bayesian Study Finds

理解机器学习：从理论到算法

https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf=1.00&gsr=0

前言

术语“机器学习”指的是对数据中有意义模式的自动检测。在过去的几十年里，它已成为几乎所有需要从大型数据集中提取信息的任务中的常用工具。我们被基于机器学习的技术所包围：搜索引擎学习如何为我们带来最佳结果（同时放置有利可图的广告），反垃圾邮件软件学习过滤我们的电子邮件，信用卡交易由学习如何检测欺诈的软件来保障安全。数码相机学习检测人脸，智能手机上的智能个人助理应用学习识别语音命令。汽车配备了使用机器学习算法构建的防事故系统。机器学习也广泛用于科学应用，如生物信息学、医学和天文学。

所有这些应用的一个共同特点是，与计算机更传统的用途相比，在这些情况下，由于需要检测的模式的复杂性，人类程序员无法提供关于应如何执行此类任务的明确、细致的规范。以智能生物为例，我们的许多技能是通过从经验中“学习”获得或完善的（而不是遵循给我们的明确指示）。机器学习工具关注的是赋予程序“学习”和适应的能力。

本书的第一个目标是提供一个严谨但易于遵循的介绍，涵盖机器学习背后的主要概念：什么是学习？机器如何学习？我们如何量化学习给定概念所需的资源？学习总是可能的吗？我们能知道学习过程是成功还是失败了吗？

本书的第二个目标是介绍几种关键的机器学习算法。我们选择介绍的算法，一方面在实践中被成功使用，另一方面给出了不同学习技术的广泛范围。此外，我们特别关注适用于大规模学习（又称“大数据”）的算法，因为近年来，我们的世界变得越来越“数字化”，可用于学习的数据量急剧增加。因此，在许多应用中数据充足，而计算时间是主要瓶颈。因此，我们明确量化了学习给定概念所需的数据量和计算时间量。

本书分为四个部分。第一部分旨在对学习的基本问题给出初步的严谨回答。我们描述了瓦利安特（Valiant）的“可能近似正确”（PAC）学习模型的泛化，这是对“什么是学习？”问题的第一个坚实回答。我们描述了经验风险最小化（ERM）、结构风险最小化（SRM）和最小描述长度（MDL）学习规则，这些展示了“机器如何学习”。我们使用ERM、SRM和MDL规则量化了学习所需的数据量，并通过推导“没有免费午餐”（no-free-lunch）定理展示了学习可能如何失败。我们还讨论了学习需要多少计算时间。在本书的第二部分，我们描述了各种学习算法。对于其中一些算法，我们首先提出一个更通用的学习原理，然后展示该算法如何遵循该原理。虽然本书的前两部分侧重于PAC模型，但第三部分通过呈现更广泛的学习模型扩展了范围。最后，本书的最后一部分致力于高级理论。

我们努力使本书尽可能自成一体的。然而，假设读者熟悉概率、线性代数、分析和算法的基本概念。本书的前三部分面向计算机科学、工程学、数学或统计学的一年级研究生。具备足够背景的本科生也可以理解。更高级的章节可供打算收集更深入理论理解的研究人员使用。

1 引言

本书的主题是自动化学习，或者我们将更常称之为机器学习（ML）。也就是说，我们希望为计算机编程，使它们能够从可用的输入中“学习”。粗略地说，学习是将经验转化为专业知识或知识的过程。学习算法的输入是代表经验的训练数据，输出是某种专业知识，通常采取另一个可以执行某些任务的计算机程序的形式。为了寻求对这一概念的形式化数学理解，我们必须更明确地说明所涉及的每个术语的含义：我们的程序将访问的训练数据是什么？学习过程如何被自动化？我们如何评估这样一个过程的成功（即学习程序输出的质量）？

1.1 什么是学习？

让我们首先考虑几个来自自然界动物学习的例子。机器学习中一些最基本的议题已经在这种我们都很熟悉的背景中出现了。

诱饵恐惧——老鼠学会避开毒饵：当老鼠遇到外观或气味新奇的食物时，它们会首先吃非常少的量，随后的进食将取决于食物的味道及其生理效应。如果食物产生不良效应，这种新奇食物通常会与疾病相关联，随后老鼠就不会吃它。显然，这里有一种学习机制在起作用——动物利用过去对某种食物的经验来获得检测该食物安全性的专业知识。如果过去对该食物的经验被标记为负面的，动物就会预测它在未来遇到时也会产生负面效应。

受前面成功学习的例子启发，让我们演示一个典型的机器学习任务。假设我们想编写一台学习如何过滤垃圾邮件的机器。一个朴素的解决方案表面上可能类似于老鼠学习如何避开毒饵的方式。机器将简单地记住所有先前被人类用户标记为垃圾邮件的电子邮件。当新邮件到达时，机器将在先前垃圾邮件的集合中搜索它。如果它与其中一封匹配，它将被丢弃。否则，它将被移到用户的收件箱文件夹中。

虽然前面的“通过记忆学习”方法有时是有用的，但它缺乏学习系统的一个重要方面——标记未见过的电子邮件消息的能力。一个成功的学习者应该能够从个别例子进展到更广泛的泛化。这也被称为归纳推理或归纳推断。在前面提出的诱饵恐惧例子中，在老鼠遇到某种类型食物的例子后，它们将对该食物的态度应用于具有相似气味和味道的新鲜、未见过的食物例子。为了在垃圾邮件过滤任务中实现泛化，学习者可以扫描先前见过的电子邮件，并提取一组单词，这些单词在电子邮件消息中的出现表明了垃圾邮件。然后，当新邮件到达时，机器可以检查其中是否出现了可疑单词之一，并相应地预测其标签。这样的系统将有可能正确预测未见过电子邮件的标签。

然而，归纳推理可能导致我们得出错误的结论。为了说明这一点，让我们再次考虑一个来自动物学习的例子。

鸽子迷信：在心理学家B. F. 斯金纳进行的一项实验中，他将一群饥饿的鸽子放在笼子里。一个自动装置被连接到笼子上，定期向鸽子投递食物，完全不参考鸟类的行为。饥饿的鸽子在笼子里走来走去，当食物第一次投递时，发现每只鸽子都从事着某种活动（啄食、转头等）。食物的到来强化了每只鸟的具体动作，因此，每只鸟倾向于花更多时间做同样的动作。这反过来又增加了下一次随机投递食物时发现每只鸟再次从事该活动的机会。结果是一连串事件，强化了鸽子将食物投递与它们在食物第一次投递时碰巧正在进行的任何动作联系起来。它们随后继续勤奋地执行这些相同的动作。¹

是什么区分了导致迷信的学习机制和有用的学习？这个问题对于自动化学习者的开发至关重要。虽然人类学习者可以依靠常识来过滤掉随机的无意义学习结论，但一旦我们将学习任务输出给机器，我们必须提供定义明确的清晰原则，以保护程序不得出无意义或无用的结论。此类原则的开发是机器学习理论的一个核心目标。

那么，是什么使老鼠的学习比鸽子的学习更成功？作为回答这个问题的第一步，让我们更仔细地看看老鼠的诱饵恐惧现象。

重访诱饵恐惧——老鼠无法在食物与电击之间或声音与恶心之间建立条件反射：老鼠的诱饵恐惧机制结果比人们可能预期的更复杂。在加西亚（Garcia）（Garcia & Koelling 1996）进行的实验中，证明了如果跟随食物消费的不愉快刺激被替换为，比如说，电击（而不是恶心），那么不会发生条件反射。即使在重复试验中，某些食物的消费之后伴随不愉快电击的施加，老鼠也不倾向于避开那种食物。当暗示恶心的食物特征（如味道或气味）被声音信号替换时，也会发生类似的条件反射失败。老鼠似乎有一些“内置的”先验知识告诉它们，虽然食物与恶心之间的时间相关性可能是因果性的，但食物消费与电击之间或声音与恶心之间不太可能存在因果关系。

我们得出结论，诱饵恐惧学习和鸽子迷信之间的一个区别特征是先验知识的融入，它使学习机制产生偏差。这也被称为归纳偏置。实验中的鸽子愿意对食物的出现采取任何解释。然而，老鼠“知道”食物不可能引起电击，并且噪音与某些食物的同时出现不太可能影响该食物的营养价值。老鼠的学习过程偏向于检测某种模式，同时忽略事件之间的其他时间相关性。

事实证明，融入先验知识，使学习过程产生偏差，对于学习算法的成功是不可避免的（这被正式陈述并证明为第5章中的“没有免费午餐定理”）。开发表达领域专业知识的工具，将其转化为学习偏置，并量化这种偏置对学习成功的影响，是机器学习理论的一个中心主题。粗略地说，开始学习过程时先验知识（或先验假设）越强，从更多例子中学习就越容易。然而，这些先验假设越强，学习的灵活性就越低——它被对这些假设的承诺先验地束缚住了。我们将在第5章中明确讨论这些问题。

理解机器学习

机器学习是计算机科学中增长最快的领域之一，具有影响深远的应用。本教材的目的是以有条理的方式介绍机器学习及其提供的算法范式。本书对机器学习背后的基本思想以及将这些原理转化为实用算法的数学推导，提供了详尽的理论阐述。在介绍了该领域的基础知识之后，本书涵盖了以往教科书未曾涉及的大量核心主题。这些包括对学习的计算复杂性以及凸性和稳定性概念的讨论；重要的算法范式，包括随机梯度下降、神经网络和结构化输出学习；以及新兴的理论概念，如PAC-贝叶斯方法和基于压缩的界限。本书专为高年级本科生或初级研究生课程设计，使统计学、计算机科学、数学和工程学的学生及非专业读者能够理解机器学习的基础知识和算法。

我们何时需要机器学习？

我们何时需要机器学习，而不是直接对我们的计算机进行编程来执行手头的任务？一个给定问题的两个方面可能要求使用基于其“经验”来学习和改进的程序：问题的复杂性和对适应性的需求。

过于复杂而无法编程的任务。

• 由动物/人类执行的任务：我们人类日常执行的许多任务，然而我们关于如何执行它们的自省（内省）并不足以详尽到提取出一个定义明确的程序。此类任务的例子包括驾驶、语音识别和图像理解。在所有这些任务中，最先进的机器学习程序——即“从经验中学习”的程序——一旦接触到足够多的训练样本，就能取得相当令人满意的结果。

• 超出人类能力的任务：另一大类受益于机器学习技术的任务与非常大且复杂的数据集的分析有关：天文数据、将医疗档案转化为医学知识、天气预测、基因组数据分析、网络搜索引擎和电子商务。随着越来越多可用的数字化记录数据，显而易见，在数据档案中埋藏着大量有意义的信息宝藏，而这些档案太大、太复杂，人类无法理解。学习检测大型复杂数据集中的有意义模式是一个充满前景的领域，在这个领域中，学习程序与计算机几乎无限的记忆容量和日益增长的处理速度相结合，开辟了新的视野。

适应性。已编程工具的一个局限特征是其刚性——一旦程序被编写并安装，它就保持不变。然而，许多任务会随时间推移或从一个用户到另一个用户发生变化。机器学习工具——其行为适应其输入数据的程序——为这类问题提供了解决方案；它们本质上能够适应与其交互的环境中的变化。机器学习在此类问题上的典型成功应用包括解码手写文本的程序，其中固定的程序可以适应不同用户手写之间的差异；垃圾邮件检测程序，自动适应垃圾邮件性质的变化；以及语音识别程序。

1.3 学习类型

当然，学习是一个非常广阔的领域。因此，机器学习领域已经分支为几个处理不同类型学习任务的子领域。我们给出学习范式的一个粗略分类，旨在提供一些视角，说明本书的内容在广泛的机器学习领域中处于什么位置。

我们描述了可以沿着其对学习范式进行分类的四个参数。

监督与无监督由于学习涉及学习者与环境之间的交互，人们可以根据这种交互的性质来划分学习任务。首先要注意的区别是监督学习和无监督学习之间的差异。作为一个说明性的例子，考虑学习检测垃圾邮件与异常检测任务。对于垃圾邮件检测任务，我们考虑这样一种设置：学习者收到训练电子邮件，其中提供了垃圾邮件/非垃圾邮件的标签。基于这样的训练，学习者应该找出一个规则，用于标记新到达的电子邮件消息。相比之下，对于异常检测任务，学习者作为训练得到的全部内容是一大堆电子邮件消息（没有标签），学习者的任务是检测“不寻常的”消息。

更抽象地说，将学习视为“利用经验获得专业知识”的过程，监督学习描述了一种场景，其中“经验”（一个训练示例）包含重要信息（例如，垃圾邮件/非垃圾邮件标签），而这些信息在所学专业知识将要应用的未见过的“测试示例”中是缺失的。在这种设置中，获得的专业知识旨在预测测试数据中缺失的信息。在这种情况下，我们可以将环境视为一位“监督”学习者的老师，提供额外信息（标签）。然而，在无监督学习中，训练数据和测试数据之间没有区别。学习者处理输入数据，目的是得出该数据的一些摘要或压缩版本。将数据集聚类成相似对象的子集是此类任务的一个典型例子。

还有一种中间学习设置，其中，虽然训练示例比测试示例包含更多信息，但学习者被要求为测试示例预测甚至更多的信息。例如，人们可能尝试学习一个价值函数，该函数描述对于棋盘上的每种设置，白方的位置比黑方好多少。然而，学习者在训练时唯一可用的信息是在实际国际象棋对局中出现的局面，并标注了最终谁赢得了那场比赛。此类学习框架主要在强化学习的标题下进行研究。

主动与被动学习者学习范式可能因学习者所扮演的角色而不同。我们区分“主动”和“被动”学习者。主动学习者在训练时与环境交互，例如，通过提出查询或进行实验，而被动学习者仅观察环境（或老师）提供的信息，而不影响或指导它。请注意，垃圾邮件过滤器的学习者通常是被动的——等待用户标记发送给他们的电子邮件。在主动设置中，人们可以想象要求用户标记由学习者选择的特定电子邮件，甚至由学习者撰写的邮件，以增强其对什么是垃圾邮件的理解。

教师的有用性当人们想到人类学习时，无论是家里的婴儿还是学校的学生，这个过程通常涉及一位有帮助的老师，他试图向学习者喂送对实现学习目标最有用的信息。相比之下，当科学家了解自然时，环境扮演老师的角色，最好被认为是被动的——苹果掉落、星星闪耀、雨落下来，都不顾及学习者的需求。我们通过假设训练数据（或学习者的经验）是由某种随机过程生成的，来对此类学习场景进行建模。这是“统计学习”分支的基本构建块。最后，当学习者的输入由对抗性“老师”生成时，学习也会发生。在垃圾邮件过滤例子中（如果垃圾邮件发送者努力误导垃圾邮件过滤设计者）或在学习检测欺诈中，情况可能如此。人们也使用对抗性教师模型作为最坏情况场景，当不能安全地假设更温和的设置时。如果你能对抗对抗性老师进行学习，你就能保证在与任何奇怪的老师交互时取得成功。

在线与批量学习协议我们提到的最后一个参数是学习者必须在整个学习过程中在线响应的情况，与学习者只有在有机会处理大量数据后才能运用所学专业知识的情况之间的区别。例如，股票经纪人必须根据迄今为止收集的经验做出日常决策。随着时间的推移，他可能会成为专家，但在此过程中可能犯了代价高昂的错误。相比之下，在许多数据挖掘设置中，学习者——数据挖掘者——在必须输出结论之前有大量的训练数据可供使用。

在本书中，我们将只讨论可能学习范式的一个子集。我们的主要关注点是带有被动学习者的监督统计批量学习（例如，尝试基于独立收集且已由记录患者的命运标记的大量患者记录档案，学习如何生成患者的预后）。我们还将简要讨论在线学习和批量无监督学习（特别是聚类）。

1.4 与其他领域的关系

作为一个跨学科领域，机器学习与统计学、信息论、博弈论和优化等数学领域有着共同的脉络。它自然是计算机科学的一个子领域，因为我们的目标是编写机器程序以便它们能够学习。在某种意义上，机器学习可以被视为人工智能（AI）的一个分支，毕竟，将经验转化为专业知识或在复杂感官数据中检测有意义模式的能力，是人类（和动物）智能的基石。然而，人们应该注意到，与传统人工智能相比，机器学习并不是试图建立对智能行为的自动模仿，而是利用计算机的优势和特殊能力来补充人类智能，通常执行远远超出人类能力的任务。例如，扫描和处理巨大数据库的能力使机器学习程序能够检测出超出人类感知范围的模式。

机器学习中的经验或训练成分通常指的是随机生成的数据。学习者的任务是处理这些随机生成的示例，以得出对这些示例所来自的环境成立的结论。这种对机器学习的描述突出了它与统计学的密切关系。事实上，这两个学科在目标和所用技术方面都有很多共同之处。然而，也有一些显著的侧重点差异；如果一位医生提出吸烟与心脏病之间存在相关性的假设，统计学家的作用是查看患者样本并检验该假设的有效性（这是假设检验的常见统计任务）。相比之下，机器学习旨在利用从患者样本中收集的数据，得出对心脏病病因的描述。希望在于，自动化技术可能能够找出可能被人类观察者遗漏的有意义的模式（或假设）。

与传统统计学相比，在机器学习中，特别是在本书中，算法考量起着主要作用。机器学习是关于由计算机执行学习；因此算法问题至关重要。我们开发算法来执行学习任务，并关注其计算效率。另一个区别是，虽然统计学通常对渐近行为感兴趣（例如随着样本量增长到无穷大，基于样本的统计估计的收敛性），但机器学习理论侧重于有限样本界限。也就是说，给定可用样本的大小，机器学习理论旨在弄清楚学习者基于此类样本可以期望达到的准确度。

这两个学科之间还有进一步的差异，我们在此只再提及一个。虽然在统计学中，通常在某种预先假定的数据模型假设下工作（例如假设数据生成分布的正态性，或函数依赖的线性），但在机器学习中，重点是在“无分布”的设置下工作，即学习者对数据分布的性质假设尽可能少，并让学习算法找出哪些模型最能近似数据生成过程。对这个问题进行精确讨论需要一些技术性预备知识，我们将在本书后面，特别是第5章中回到这个问题。

1.5 如何阅读本书

本书的第一部分提供了支撑机器学习（ML）的基本理论原则。在某种意义上，这是构建本书其余部分的基础。这一部分可以作为机器学习理论基础迷你课程的基础。

本书的第二部分介绍了监督机器学习最常用的算法方法。其中章节的一个子集也可以用于在面向计算机科学、数学或工程专业学生的通用人工智能课程中介绍机器学习。

本书的第三部分将讨论范围从统计分类扩展到其他学习模型。它涵盖了在线学习、无监督学习、降维、生成模型和特征学习。

本书的第四部分“高级理论”，面向对研究感兴趣的读者，并提供了用于分析和推动理论机器学习领域发展的更专业的数学技术。

附录提供了本书中使用的一些技术工具。特别是，我们列出了测度集中和线性代数的一些基本结果。

少数章节用星号标记，这意味着它们面向更高级的学生。每章末尾都附有练习列表。课程网站上提供了解答手册。

1.6 符号表示

我们在整本书中使用的大部分符号要么是标准的，要么是当场定义的。在本节中，我们描述我们的主要约定，并提供一张总结我们符号的表格（表1.1）。鼓励读者跳过本节，如果在阅读本书过程中某些符号不清楚，再回到本节。

第一部分 基础

2 温和的开端

让我们通过展示如何在相对简化的环境中实现成功的学习，来开始我们的数学分析。想象你刚刚到达某个太平洋小岛。你很快发现木瓜是当地饮食的重要组成部分。然而，你以前从未品尝过木瓜。你必须学会如何预测你在市场上看到的木瓜是否好吃。首先，你需要决定你的预测应该基于木瓜的哪些特征。基于你以前对其他水果的经验，你决定使用两个特征：木瓜的颜色，范围从深绿色、橙色、红色到深棕色，以及木瓜的软硬度，范围从硬如石头到软烂。你用来找出预测规则的输入是你检查过颜色和软硬度，然后品尝并发现它们是否好吃的一系列木瓜样本。让我们分析这个任务，以展示学习问题中涉及的考量。

我们的第一步是描述一个旨在捕捉此类学习任务的形式化模型。

2.1 一个形式化模型——统计学习框架

2.2 经验风险最小化

2.2.1 可能出错的地方——过拟合

尽管 ERM 规则看起来非常自然，但如果不小心，这种方法可能会惨败。

为了演示这种失败，让我们回到基于木瓜的软硬度和颜色来学习预测其味道的问题。考虑如下所示的样本：

假设概率分布 D 使得实例均匀分布在灰色正方形内，并且标记函数 f 确定如果实例位于内部蓝色正方形内则标签为 1，否则为 0。图中灰色正方形的面积是 2，蓝色正方形的面积是 1。考虑以下预测器：

2.3 带归纳偏置的经验风险最小化

我们刚刚证明了ERM规则可能导致过拟合。与其放弃ERM范式，我们将寻找纠正它的方法。我们将寻找保证ERM不会过拟合的条件，即，在这些条件下，当ERM预测器相对于训练数据表现良好时，它也很可能在底层数据分布上表现良好。

直观地说，选择更受限的假设类能更好地保护我们免受过拟合，但同时可能导致我们产生更强的归纳偏置。我们稍后将回到这个基本的权衡问题。

2.3.1 有限假设类

图2.1给出了一个图形化的说明，解释了我们是如何使用联合界（union bound）的。

2.4 练习

注意，这是一个无限大小的假设类。在整个本练习中，我们依赖可实现性假设。

。。。。。。。。。

原文链接：https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf=1.00&gsr=0