重磅！Francis Bach新书《(机器)学习理论:第一性原理》，488页pdf

这本书由MIT Press出版，属于我所编辑的系列（正如预期，他们在整个过程中给予了我极大的支持）。它可以从我的个人网页上免费在线阅读，但当然，您也可以从您喜欢的在线商店购买纸质版（请查看这里的链接），这样您就可以为我下一辆公路自行车的购买做出贡献（对于法国的读者，amazon.fr 和 fnac.com 也有售，许多国家的主要在线商店也应该有销售）。 除了PDF和纸质版外，所有图形都可以通过Python和Matlab代码进行复现，相关代码可以在这里找到（我计划未来加入Julia版本）。我已经开始收集涵盖所有章节的练习题解答（在这里可以找到，注意：工作进行中）。如果您想贡献解答、指出错别字或提出改进建议，我将不胜感激（请给我发电子邮件）。未来，我可能会加入一些历史部分，这些内容我决定暂时放弃，因为这会花费我更多的时间（如果您有相关的指引或建议，欢迎告知我）。

为什么要再写一本关于学习理论的书？

市面上已经有很多优秀的学习理论书籍了。为什么我还要写一本新书呢？请阅读书的前言（在文章的末尾会展示），那里列出了几个原因，但主要的原因是，我觉得当前机器学习数学分析的趋势导致了一些过于复杂的论证和结果，这些内容往往对实践者并不直接相关。因此，我的目标是提出从基本原理出发，能够推导出来的最简单的表述，尽量保持严谨，但又不让读者感到被更多的高深结果淹没，这些结果需要过多的数学复杂性。我已经尽力而为，但我相信总有一些地方可以提出更简洁的论证；如果您发现了，欢迎告知我。此外，我还尝试通过一系列简单的实验，将理论结果与实际性能结合起来。

这本书的一个重要特色是它专注于实值预测函数：即使在预测离散值输出时，实值预测函数已经成为现代机器学习技术的事实标准。因此，尽管Vapnik-Chervonenkis维度在历史上有着举足轻重的地位，我决定不在书中呈现它，而是直接基于Rademacher复杂度推导我的通用界限。专注于实值预测函数使得最小二乘回归成为理论的核心部分，这对于学生来说非常重要，因为许多机器学习中的重要概念（如正则化、随机算法）已经在简化的形式中得到了体现。

在我所涉及的众多主题中，一些采用了标准的处理方式，但有些可能值得引起有经验的读者的注意（我可能会在未来写一些博客文章来进一步探讨这些内容）。下面是我对每一章的几点印象： 第一章（数学预备知识）：这一章没有什么特别复杂的内容，主要介绍了一些有用的计算技巧和主要的浓度不等式。一些内容已经在博客中讨论过，例如Jensen不等式、矩阵的浓度不等式，或者将在未来发布（如矩阵逆定理）。 第二章（监督学习简介）：本章集中讨论了监督学习的传统决策理论表述，包括损失、风险等内容。我加入了Luc Devroye（1982）提出的“无免费午餐定理”，因为我认为它很好地展示了没有假设的情况下，学习是无法实现的。 第三章（线性最小二乘回归）：无论这个古老的方法起源于Legendre还是Gauss，这并不重要。我认为它仍然非常重要，因为它已经囊括了许多经典的机器学习概念，尤其是正则化的需求，以避免在d/nd/nd/n（其中n是观测数，d是参数数目）中出现收敛率。因此，这已经能传达一个信息：参数的数量通常不是衡量学习方法泛化能力的最佳方式。 第四章（经验风险最小化）：本章首先广泛（但传统地）讨论了用于二分类问题的凸代理函数（这将在第十三章中扩展为结构化预测）。对于凸损失函数，首先采用约束优化方法进行正则化估计（因为这较为简单），但为了避免理论与实践之间的显著差异，我专门添加了一节关于惩罚估计的方法，其中包含了一些简单的（其中一些是新的）通用界限。 第五章（优化）：将所有内容压缩进一章很困难（不过我有些许“作弊”，因为我在第十一章中关于在线学习的内容留下了一些精彩的部分！）。从二次问题开始，通过线性代数推导梯度下降的收敛性，接着介绍了凸优化的标准工具，然后统一呈现了随机逼近法，并重点讨论了随机梯度下降的自然测试误差性能。同时也介绍了方差减少方法，提供了我所能找到的最简单证明。 第六章（局部平均方法）：k近邻预测方法有些过时，但它是可以适应任何预测函数的最简单方法（也最容易向您的祖父母解释）。在这一部分，我重新使用了Gérard Biau和Luc Devroye在2015年书中的交换性论证方法，得到了简单的界限，且假设条件很少。对于Nadaraya-Watson估计量（例如，核回归），我用Bernstein不等式给出了一个简单的证明。 第七章（核方法）：这也是一个相对密集的章节，我主要关注Sobolev空间，以便能够刻画对平滑性的适应性。对于Lipschitz连续的损失函数，只需要刻画逼近误差，我成功避免了积分算子。对于平方损失，我复用了Jaouad Mourtada和Lorenzo Rosasco的优美证明方法，得出了特别简单的期望值界限。 第八章（稀疏方法）：在这一章中，我特别关注平方损失，并复用了Philippe Rigollet和Sacha Tsybakov的证明技术，这些方法适用于约束或惩罚估计，从而得到了著名的σ2klog⁡dn\frac{\sigma^2 k \log d}{n}nσ2klogd结果。在简要介绍了统计文献中常见的固定设计处理（并列举了设计矩阵的各种条件）后，我专注于随机设计方法，通过强凸性可以合理简单地获得较快的收敛速度。 第九章（神经网络）：我选择只介绍单隐层神经网络，在这种设置下，估计误差和优化误差的性质可以得到精确的表述，特别关注其对线性潜变量的适应性。同样，隐藏神经元的数量不是潜在的泛化能力的关键驱动因素。我还明确地将神经网络与核方法和随机特征的联系（即只优化最后一层权重）做了联系。这一“经典”的处理方法在后面一章关于过参数化模型的讨论中得到了补充。 第十章（集成学习）：这一章基本上分为两个独立部分，第一部分讨论了bagging和随机投影，介绍了经典的高斯随机投影，并扩展到非线性预测。第二部分讨论了boosting，试图统一不同领域的算法，如匹配追踪和Adaboost，并给出了boosting性能的显式新证明，而没有额外的正则化假设。虽然速率不是最优的，但这与实践中采用的（通过早期停止进行的）正则化方法更加接近。这里可能还有更锋利的结果。 第十一章（从在线学习到强盗问题）：这一章仅涉及了更广泛主题的皮毛，但对于在线学习，我明确展示了其与经典随机优化的区别，并采用统一符号表示（这也是我插入镜像下降法的地方）。我用十页自包含的内容描述了多臂强盗问题；虽然简短，但足以捕捉主要思想，以及它与更经典监督学习方法的相似性和不同之处。 第十二章（过参数化模型）：这一章更接近研究方向，我尝试以最简明的方式描述关于过参数化模型的最新重要成果，如梯度下降的全局收敛性、凸问题和非凸问题的隐性偏差（对于对角线线性网络），双重下降（分别提供了关于高斯数据和随机投影的简单和不那么简单的论证），以及懒学习。 第十三章（结构化预测）：这一章包含了最近的研究成果，首先讨论了多类别分类，重点是多变量预测函数及其关联的泛化性质（在此，随机梯度下降比通过Rademacher平均得到的经验风险最小化结果给出了更好的界限）。接着，我以统一的方式呈现了关于预测复杂输出的最新文献，采用凸代理函数，从二次、平滑到非平滑代理函数依次讨论。 第十四章（概率方法）：我首先回顾了几种学习方法的概率建模解释，主要关注通过识别损失和先验与对数密度之间的关系，明确区分了这种类比带来的优势与其局限性（特别是，像ℓ1\ell_1ℓ1-最小化这样的稀疏方法不适用于来自其负对数密度为ℓ1\ell_1ℓ1-范数的分布的数据）。接着，我们展示了贝叶斯推断如何自然地引导模型选择标准，并以描述PAC-贝叶斯分析结束本章，引用了Pierre Alquier的最新专著。 第十五章（泛化和优化误差的下界）：从研究的角度来看，我更倾向于通过设计和分析快速算法来贡献性能的上界，但我不得不承认，下界同样重要（特别是当它们与上界一致时）。本章讨论了优化下界（通常呈现了难以优化的函数，主要来源于Yurii Nesterov的工作），以及统计下界（其中我使用了信息论的论证）。对于随机梯度下降，我复用了Agarwal等人（2012）提出的优美证明技巧。

前言

**为什么学习学习理论？

数据已经渗透到科学、工程、工业和个人生活的各个领域，带来了对自动化处理的需求。机器学习致力于从训练样本中进行预测，广泛应用于各个领域，包括大大小小的问题，并使用从简单的线性模型到深度神经网络等多种学习模型。如今，它已经成为算法工具箱中的一个重要部分。 如何理解这些实际成功的背后？我们能否提炼出一些原则，以理解当前的学习方法，并指导新技术的设计，适应新应用或新的计算环境？这正是学习理论的目标。除了已经非常丰富且有趣的数学性质（因为它引入了许多数学领域的内容），大多数在实践中观察到的行为，原则上都可以通过足够的努力和理想化来理解。反过来，一旦理解了这些行为，我们可以做出适当的修改，获得更大的成功。

**为什么要读这本书？

本教材的目标是呈现学习理论中的旧有和最新成果，专注于目前最广泛使用的学习架构。通过这种方式，本书阐述了几项原则，帮助读者理解过拟合和欠拟合现象，并系统地展示了分析中的三个组成部分：估计误差、逼近误差和优化误差。此外，本书的目标不仅仅是展示学习方法在足够的数据下能够进行学习，还力图理解它们学习的速度（或慢速），特别关注如何通过适应特定结构加速学习过程（例如预测函数的平滑性或对低维子空间的依赖）。 本书适合理论导向的学生，以及那些希望获得机器学习及其相关领域（如计算机视觉和自然语言处理）所使用算法的基本数学理解的学生。此外，对于那些来自应用数学或计算机科学其他领域的学生和研究人员，也非常适合他们学习机器学习背后的理论。最后，由于本书汇集了许多简单的证明，它还可以作为理论机器学习研究人员的参考书。 本书将特别努力从第一原理证明许多结果，同时尽可能保持内容的简洁。这自然会导致选择一些关键结果，以展示学习理论中最重要的概念，并通过简单但相关的实例进行说明。书中也会呈现一些没有证明的通用结果。当然，第一原理的概念是主观的，我假设读者已经掌握了线性代数、概率论和微积分等基本知识。 此外，我将专注于学习理论中的一部分，特别是那些可以在实践中运行的算法。因此，本书中描述的所有算法框架都是日常使用的。由于许多现代学习方法基于优化，书中的第五章专门讨论这一主题。对于大多数学习方法，我展示了一些简单的示范实验，并提供了相应的代码（目前是MATLAB和Python，未来将包含Julia），以便学生自己查看这些算法在合成实验中的简洁性和有效性。书中的习题目前没有提供解答，目的是帮助学生更好地理解相关的材料。 最后，书的第三部分将深入讨论现代专题，如在线学习、集成学习、结构化预测和过参数化模型。

**本书的目标读者

请注意，这本书并不是一本机器学习的入门教材。市面上已经有几本优秀的教材（例如，Alpaydin 2020年、Lindholm等 2022年、Azencott 2019年、Alpaydin 2022年）。本书侧重于学习理论——即为最广泛使用的学习算法推导数学保证，并刻画使特定算法框架成功的因素。特别是鉴于许多现代方法基于优化算法，本书对基于梯度的方法及其与机器学习的关系给予了较大关注。 本书的一个关键目标是，从最简单的结果入手，使其更易理解，而不是集中于更高级的材料，这些内容在初学时可能过于复杂，且提供的理解提升可能非常有限。在整本书中，我们提供了许多现代研究工作的参考，供读者深入了解。

**本书结构

本书分为三大部分：导言、核心部分和专题部分。读者应当先阅读前两部分，以全面理解主要概念，之后可以根据需要在第二次阅读时选择性阅读专题部分的章节，或者在两学期的课程中学习。 每章都以概述将要讨论的主要概念和结果开始。所有的模拟实验可以在https://www.di.ens.fr/~fbach/ltfp/上找到，并提供MATLAB和Python代码。书中提供了大量的习题，嵌入在正文中，并用专门的段落标出，个别习题在文中提到（例如，“证明留作练习”）。这些习题旨在帮助学生加深对相关材料的理解，提出扩展或应用。 本书并未涵盖所有主题，也没有对许多其他内容进行深入探讨。市面上已有许多优秀的学习理论教材，涵盖更广泛或更深入的内容（例如，Christmann 和 Steinwart 2008年；Koltchinskii 2011年；Mohri等 2018年；Shalev-Shwartz 和 Ben-David 2014年）。同时，还可以参考Alexander Rakhlin 和 Karthik Sridharan，以及Michael Wolf的精彩笔记。 特别地，本书主要聚焦于实值预测函数，因为它已成为现代机器学习技术的事实标准，即使在预测离散值输出时也适用。因此，尽管Vapnik-Chervonenkis维度在历史上的重要性和影响至关重要，我决定不在本书中介绍它，而是基于Rademacher复杂性直接推导通用界限。专注于实值预测函数使得最小二乘回归成为本书理论的核心内容，这对于学生来说非常有意义。此外，这也为与相关的统计学文献建立联系提供了便利。 一些领域，如在线学习或概率方法，在本书中被简要描述，以便与经典理论建立联系，并鼓励读者通过专门的书籍进一步学习。在本书中，我还包括了第12章关于过参数化模型和第13章关于结构化预测，这些内容介绍了机器学习中的现代专题。更广泛地讲，第三部分（专题部分）的目标是，在每一章中介绍新概念，同时保持与核心内容的联系，并使用统一的符号表示。

**如何使用本书？

前九章（按顺序，不包括“钻石部分”）适合于一学期的高年级本科或研究生课程，在进行过机器学习的入门课程后阅读。接下来的六章大多可以按任意顺序阅读，用于加深对某些专题的理解；它们可以作为作业（通过习题）阅读，或在较长的（例如两学期）课程中教授。本书的设计也便于自学，前九章按顺序阅读，最后六章则可以随机阅读。在任何情况下，第1章关于数学预备知识的部分可以快速阅读，之后在相关章节需要时深入学习相关概念。