本书是机器学习领域内一部具有里程碑意义的著作。包括哥伦比亚大学、北京大学在内的多个国内外名校均有以该书为基础开设的研究生课程。全书内容丰富，视野宽阔，深入浅出地介绍了目前机器学习重要的理论和关键的算法。
无
本书是关于机器学习的概述，适合作为该领域学生和研究人员的教科书。本书涵盖机器学习领域的基本内容，并且提供讨论及检验算法合理性所必需的理论基础和概念工具。不仅如此，本书还描述了应用相关算法时需要考虑的若干关键问题。
本书旨在介绍最新的理论和概念，并且对于相对先进的结果给出简要的证明。总体而言，我们尽可能使全书叙述简洁。尽管如此，我们也会讨论机器学习中出现的一些重要且复杂的主题，指出若干开放的研究问题。对于那些常常与其他主题合并或者未引起足够关注的主题，本书将单独着重讨论，例如，将多分类、排序和回归分别用一章来讲解。
尽管本书覆盖机器学习中很多重要的主题，但是出于简略且因目前缺乏针对一些方法的坚实的理论保证，未能覆盖图模型和神经网络这两个重要主题。
本书主要面向机器学习、统计和其他相关领域的学生与研究人员，适合作为研究生和高年级本科生课程的教科书，或者学术研讨会的参考资料。本书前三四章为后续材料奠定理论基础，第6章引入一些被后面章节广泛使用的概念来完善理论，第13章与第12章密切相关，而其余各章大多自成体系。我们在每章最后给出一套习题，并单独给出完整的解答。
我们假定本书的读者熟悉线性代数、概率和算法分析的基本概念。但是，为了进一步辅助学习，我们在附录中会简要回顾线性代数和概率的相关知识，给出凸优化和信息论的简介，并且汇总本书分析和讨论中常用的集中不等式。
不少著作在介绍机器学习时从贝叶斯角度或者核方法等特定主题具体展开，而本书的不同之处在于提供了适用于多个机器学习主题和领域的统一介绍。此外，本书的特色还在于对机器学习理论基础的深入剖析，并给出详细的证明。
这是本书的第2版，我们对全书内容进行了更新。主要修改之处包括：书写风格调整、示意图新增、表述简化、内容补充（特别是第6章和第17章）、章节新增等。具体而言，我们增加了一整章来介绍模型选择（第4章）这一重要主题，对上一版中的相关内容进行了拓展。我们也增加了两个全新的章节分别介绍机器学习中的两个重要主题：最大熵模型（第12章）和条件最大熵模型（第13章）。我们还对附录进行了大幅调整。在附录B中，详述了凸优化中的Fenchel对偶性。在附录D中，补充介绍了大量相关的集中不等式。在附录E中，新增了关于信息论的内容。此外，这一版对每章的习题和解答也进行了大量的更新。
这里所介绍的大部分材料来自机器学习研究生课程(机器学习基础)，在过去14年中，该课程由本书第一作者在纽约大学库朗数学科学研究所讲授。本书极大地受益于该课程的学生、朋友、同事和研究人员所提出的宝贵意见与建议，在此对他们深表感激。
我们特别感谢Corinna Cortes和Yishay Mansour对于本书第1版内容的设计与组织提出的许多重要建议，包括大量详细的注释。我们充分考虑了他们的建议，这对于改进全书帮助很大。此外，还要感谢Yishay Mansour用本书的最初版本进行教学，并向我们积极反馈。
我们还要感谢来自学术界和企业界研究实验室的同事与朋友所给予的讨论、建议和贡献，他们是：Jacob Abernethy、Cyril Allauzen、Kareem Amin、Stephen Boyd、Aldo Corbisiero、Giulia DeSalvo、Claudio Gentile、Spencer Greenberg、Lisa Hellerstein、Sanjiv Kumar、Vitaly Kuznetsov、Ryan McDonald、Andrès Muoz Medina、Tyler Neylon、Peter Norvig、Fernando Pereira、Maria Pershina、Borja de Balle Pigem、Ashish Rastogi、Michael Riley、Dmitry Storcheus、Ananda Theertha Suresh、Umar Syed、Csaba Szepesvri、Toshiyuki Tanaka、Eugene Weinstein、Jason Weston、Scott Yang和Ningshan Zhang。
最后，我们还要感谢MIT出版社对本书所给予的帮助和支持。
计算机/人工智能/机器学习
机器学习领域的里程碑式著作，介绍机器学习的重要理论和典型算法。
纽约大学库兰特数学科学研究所梅尔亚·莫里教授与两位杰出青年学者合著。
中国科学院自动化研究所人工智能与机器学习科研团队翻译作品。
“这是一本严谨、全面且自成体系的书，是涵盖众多机器学习算法和问题的集大成之作，更是企业界与学术界的研究人员、工程师及学生的必备参考书。”
——Corinna Cortes 谷歌研究院纽约分院主管
“这是一本从理论出发，对机器学习进行清晰、严谨介绍的书。书中涵盖了很多机器学习问题和模型。这个新版本有很多更新，比如模型选择和最大熵模型等内容。这是一本面向研究生的标准参考书。”
——Peter Bartlett 加州大学伯克利分校计算机科学教授
“这是一本简洁且数学严谨的书，书中提供了机器学习领域的很多基础和先进的内容。在现代机器学习理论范畴内，对于研究生而言，这也是一本极有价值的教科书。这本书在内容和风格上都独树一帜，是研究人员和学生的必备书。”
——Claudio Gentile 法国国家信息与自动化研究所、谷歌研究院
“我发现这本书的第1版在5年内都将是一个很有价值的教学资源，并且我期待着在未来的课程中使用全面改进和拓展的第2版。”
——Aryeh Kontorovich 本·古里安大学计算机科学教授
本书是机器学习领域的里程碑式著作，被哥伦比亚大学和北京大学等国内外顶尖院校用作教材。本书涵盖机器学习的基本概念和关键算法，给出了算法的理论支撑，并且指出了算法在实际应用中的关键点。通过对一些基本问题乃至前沿问题的精确证明，为读者提供了新的理念和理论工具。
本书第2版对第1版内容进行了大量修订，补充了新的三章：模型选择、最大熵模型、条件最大熵模型，还对附录进行了大幅调整，在附录B中详述了凸优化中的Fenchel对偶性，在附录D中补充介绍了大量相关的集中不等式，在附录E中新增了关于信息论的内容。此外，新版也对每章的习题和解答进行了大量更新。
纽约大学教授Mehryar Mohri是机器学习界的泰斗级人物，他与他的学生Afshin Rostamizadeh以及Ameet Talwalkar合著的Foundations of Machine Learning（即本书第1版）是机器学习领域内一部具有里程碑意义的著作。2018年，三位作者在第1版的基础上出版了第2版。包括哥伦比亚大学、北京大学在内的多个国内外顶级院校均有以本书为基础开设的研究生课程。
机器学习是人工智能研究领域中最活跃的分支之一，为信息科学领域解决实际学习问题提供了理论支撑与应用算法。机器学习又是一个多学科的交叉领域，涉及统计学、信息论、优化、博弈论、形式语言和自动机、应用心理学、生物学和神经生理学等。这种学科交叉融合带来的良性互动，无疑促进了包括机器学习在内的诸学科的发展与繁荣。
本书内容丰富，视野宽阔，深入浅出地介绍了目前机器学习中重要的理论和典型的算法。不同于常规的机器学习算法入门读物，本书试图从更高的视角和更深的层次来解读机器学习的一般性理论基础，引入对指导理论研究和实际应用都至关重要的概率近似正确(Probability Approximately Correct，PAC)学习理论。该理论旨在回答由机器学习得到的结果到底有多高的可信度与推广能力，从某种意义上来说，只有理解了这部分内容，才能对机器学习何时能学习以及为何能学习成功有更加深刻的理解。PAC理论涉及的数学基础较多，而国内关于PAC的参考资料非常少，我们的人工智能与机器学习研究团队为此进行了多方论证并多次召开专题讨论会。此外，本书的巧妙之处除了用PAC构建理论基础之外，还从间隔(margin)角度衔接各个章节，对机器学习中的诸多方面进行了完美的统一。
在第1版的基础上，本书第2版对内容进行了大量修订并补充了新的内容。除了表述更为严谨、图表更为易懂、证明更为简洁之外，还对上一版的一些章节的内容进行了必要的扩充，并针对模型选择、最大熵模型、条件最大熵模型以及信息论引入了新的章节进行详细介绍。
本书主要面向人工智能、机器学习、模式识别、数据挖掘、计算机应用、生物信息学、数学和统计学等领域的研究生及相关领域的科技人员。翻译出版中译本的目的，是希望能为国内广大从事相关研究的学者和研究生提供一本全面、系统、权威的教科书和参考书。如果能做到这一点，我们将感到十分欣慰。
必须说明的是，本书的翻译是中国科学院自动化研究所人工智能与机器学习研究团队集体努力的结果，团队成员杨雪冰副研究员对本书第2版中更新的章节进行了全面的审校与修正，吴雅婧助理研究员对新增的章节进行了细致的调研与翻译，他们付出了艰辛劳动，在此我深表感谢。感谢机械工业出版社华章分社的大力协助，倘若没有他们的热情支持，本书的中译版难以如此迅速地与大家见面。另外，本书的翻译得到了国家自然科学基金委重点项目和面上项目（61961160707、61976212等）的资助，特此感谢。
在翻译过程中，我们力求准确地反映原著内容，同时保留原著的风格。对于英文原版中的一些公式及表述错误，我们在翻译的过程中结合原作者的课程讲稿进行了校核，并以译者注的形式指出、修正了部分错误，但由于译者水平有限，书中难免有不妥之处，恳请读者批评指正。
最后，谨把本书的中译版献给我的导师王珏研究员！王珏老师生前对机器学习理论、算法和应用非常关注，对机器学习中的很多基础问题有着独到而深刻的理解，他启发并引领了我们研究团队对机器学习理论和算法的研究工作，使我们终身受益。
张文生
中国科学院自动化研究所
2021年7月于北京
译者序
前言
第1章 引言1
1.1 什么是机器学习1
1.2 机器学习可以解决什么样的问题2
1.3 一些典型的学习任务2
1.4 学习阶段3
1.5 学习情境4
1.6 泛化5
第2章 PAC学习框架7
2.1 PAC学习模型7
2.2 对有限假设集的学习保证——一致的情况11
2.3 对有限假设集的学习保证——不一致的情况14
2.4 泛化性16
2.4.1 确定性与随机性情境16
2.4.2 贝叶斯误差与噪声17
2.5 文献评注18
2.6 习题18
第3章 Rademacher复杂度和VC-维23
3.1 Rademacher复杂度23
3.2 生长函数27
3.3 VC-维28
3.4 下界34
3.5 文献评注38
3.6 习题39
第4章 模型选择46
4.1 估计误差和近似误差46
4.2 经验风险最小化47
4.3 结构风险最小化47
4.4 交叉验证50
4.5 n-折交叉验证52
4.6 基于正则化的算法53
4.7 凸替换项损失54
4.8 文献评注57
4.9 习题58
第5章 支持向量机59
5.1 线性分类59
5.2 可分情况60
5.2.1 原始优化问题60
5.2.2 支持向量61
5.2.3 对偶优化问题62
5.2.4 留一法63
5.3 不可分情况64
5.3.1 原始优化问题65
5.3.2 支持向量66
5.3.3 对偶优化问题67
5.4 间隔理论67
5.5 文献评注74
5.6 习题74
第6章 核方法77
6.1 引言77
6.2 正定对称核79
6.2.1 定义79
6.2.2 再生核希尔伯特空间81
6.2.3 性质82
6.3 基于核的算法85
6.3.1 具有PDS核的SVM85
6.3.2 表示定理86
6.3.3 学习保证87
6.4 负定对称核88
6.5 序列核90
6.5.1 加权转换器90
6.5.2 有理核93
6.6 近似核特征映射96
6.7 文献评注100
6.8 习题100
第7章 boosting106
7.1 引言106
7.2 AdaBoost算法107
7.2.1 经验误差的界109
7.2.2 与坐标下降的关系110
7.2.3 实践中的使用方式112
7.3 理论结果113
7.3.1 基于VC-维的分析113
7.3.2 L1-几何间隔113
7.3.3 基于间隔的分析115
7.3.4 间隔最大化118
7.3.5 博弈论解释119
7.4 L1-正则化120
7.5 讨论122
7.6 文献评注122
7.7 习题124
第8章 在线学习129
8.1 引言129
8.2 有专家建议的预测130
8.2.1 错误界和折半算法130
8.2.2 加权多数算法131
8.2.3 随机加权多数算法132
8.2.4 指数加权平均算法135
8.3 线性分类137
8.3.1 感知机算法137
8.3.2 Winnow算法143
8.4 在线到批处理的转换145
8.5 与博弈论的联系147
8.6 文献评注148
8.7 习题149
第9章 多分类153
9.1 多分类问题153
9.2 泛化界154
9.3 直接型多分类算法159
9.3.1 多分类SVM159
9.3.2 多分类boosting算法160
9.3.3 决策树161
9.4 类别分解型多分类算法164
9.4.1 一对多164
9.4.2 一对一165
9.4.3 纠错输出编码166
9.5 结构化预测算法168
9.6 文献评注169
9.7 习题170
第10章 排序172
10.1 排序问题172
10.2 泛化界173
10.3 使用SVM进行排序175
10.4 RankBoost176
10.4.1 经验误差界178
10.4.2 与坐标下降的关系179
10.4.3 排序问题集成算法的间隔界180
10.5 二部排序181
10.5.1 二部排序中的boosting算法182
10.5.2 ROC曲线下面积184
10.6 基于偏好的情境184
10.6.1 两阶段排序问题185
10.6.2 确定性算法186
10.6.3 随机性算法187
10.6.4 关于其他损失函数的扩展188
10.7 其他的排序准则189
10.8 文献评注189
10.9 习题190
第11章 回归191
11.1 回归问题191
11.2 泛化界192
11.2.1 有限假设集192
11.2.2 Rademacher复杂度界193
11.2.3 伪维度界194
11.3 回归算法196
11.3.1 线性回归196
11.3.2 核岭回归198
11.3.3 支持向量回归201
11.3.4 Lasso204
11.3.5 组范数回归算法206
11.3.6 在线回归算法207
11.4 文献评注207
11.5 习题208
第12章 最大熵模型210
12.1 密度估计问题210
12.1.1 最大似然解210
12.1.2 最大后验解211
12.2 添加特征的密度估计问题212
12.3 最大熵准则212
12.4 最大熵模型简介213
12.5 对偶问题213
12.6 泛化界216
12.7 坐标下降算法217
12.8 拓展218
12.9 L2-正则化220
12.10 文献评注222
12.11 习题223
第13章 条件最大熵模型224
13.1 学习问题224
13.2 条件最大熵准则224
13.3 条件最大熵模型简介225
13.4 对偶问题226
13.5 性质227
13.5.1 优化问题227
13.5.2 特征向量228
13.5.3 预测228
13.6 泛化界228
13.7 逻辑回归231
13.7.1 优化问题231
13.7.2 逻辑模型231
13.8 L2-正则232
13.9 对偶定理的证明233
13.10 文献评注235
13.11 习题235
第14章 算法稳定性237
14.1 定义237
14.2 基于稳定性的泛化保证238
14.3 基于核的正则化算法的稳定性239
14.3.1 应用于回归算法：以SVR和KRR为例242
14.3.2 应用于分类算法：以SVM为例243
14.3.3 讨论244
14.4 文献评述244
14.5 习题244
第15章 降维246
15.1 主成分分析247
15.2 核主成分分析248
15.3 KPCA和流形学习249
15.3.1 等距映射249
15.3.2 拉普拉斯特征映射249
15.3.3 局部线性嵌入250
15.4 Johnson-Lindenstrauss引理251
15.5 文献评注252
15.6 习题253
第16章 学习自动机和语言255
16.1 引言255
16.2 有限自动机256
16.3 高效精确学习257
16.3.1 被动学习257
16.3.2 通过查询学习258
16.3.3 通过查询学习自动机259
16.4 极限下的识别262
16.5 文献评注267
16.6 习题268
第17章 强化学习270
17.1 学习情境270
17.2 马尔可夫决策过程模型271
17.3 策略272
17.3.1 定义272
17.3.2 策略值272
17.3.3 最优策略273
17.3.4 策略评估274
17.4 规划算法275
17.4.1 值迭代275
17.4.2 策略迭代277
17.4.3 线性规划279
17.5 学习算法279
17.5.1 随机逼近280
17.5.2 TD（0）算法283
17.5.3 Q-学习算法283
17.5.4 SARSA算法286
17.5.5 TD（λ）算法286
17.5.6 大状态空间287
17.6 文献评注288
后记289
附录A 线性代数回顾290
附录B 凸优化295
附录C 概率论回顾308
附录D 集中不等式315
附录E 信息论回顾328
附录F 符号337
参考文献338
索引352
