机器学习基础

本书从概率近似正确（PAC）理论出发探讨机器学习的基础理论与典型算法，包括PAC学习框架、VC-维、支持向量机、核方法、在线学习、多分类、排序、回归、降维、强化学习等丰富的内容。此外，附录部分简要回顾了与机器学习密切相关的概率论、凸优化、矩阵以及范数等必要的预备知识。

本书重在介绍典型算法的理论支撑并指出算法在实际应用中的关键点，注重理论细节与证明过程，可作为高等院校机器学习、统计学等课程的教材，或作为相关领域研究人员的参考读物。

梅尔亚·莫里（Mehryar Mohri）
纽约大学库兰特数学科学研究所计算机科学与数学教授，同时任谷歌研究院的研究顾问。主要研究方向包括机器学习理论和算法、语音处理、自动机理论和算法、自然语言处理、计算生物学等。曾在AT&T实验室研究部担任部门主管和技术负责人。他是多个核心加权自动机和有限状态机算法的作者，在将加权有限状态机应用于语音识别和自然语言处理方面做了开创性的工作。


阿夫欣·罗斯塔米扎达尔（Afshin Rostamizadeh）
谷歌研究院高级研究员。他拥有纽约大学计算机科学博士学位，加州大学伯克利分校电子工程与计算机学士学位。


阿米特·塔尔沃卡尔 （Ameet Talwalkar）
卡内基·梅隆大学机器学习系助理教授，同时还是AI初创企业Determined AI的联合创始人和首席科学家。他拥有纽约大学计算机科学-机器学习博士学位，还曾是加州大学伯克利分校电子工程与计算机系博士后研究员。

本书是机器学习领域的里程碑式著作，被哥伦比亚大学和北京大学等国内外顶*院校用作教材。书中介绍机器学习的基础概念和关键算法，给出了算法的理论支撑，并且指出了算法在实际应用中的关键点。通过对这些基本问题乃至前沿问题的精确证明，为读者提供了新的理念和理论工具。

本书特色
更高的阐述视点，更重视理解深度，引入概率近似正确（PAC）学习理论，探讨机器学习结果的可信度与推广能力。
更多的理论细节，更强调证明过程，不仅涵盖常规主题，而且对一般教材中忽略的回归、多分类和排序问题做了细致讨论。
更好的章节组织，更关注知识关联，通过间隔（margin）理论构建各个章节的内在衔接，实现了机器学习诸多方面的统一。

译者序
　　Foundations of Machine Learning
　　纽约大学Mehryar Mohri教授是机器学习界的泰斗级人物，他与他的学生Afshin Rostamizadeh以及Ameet Talwalkar合著的《Foundations of Machine Learning》是机器学习领域一部具有里程碑意义的著作。包括哥伦比亚大学、北京大学在内的多所国内外顶级院校均有以该书为基础开设的研究生课程。
　　机器学习是人工智能研究领域中最活跃的分支之一，为信息科学领域解决实际学习问题提供了理论支撑与应用算法。机器学习又是一个多学科的交叉领域，涉及统计学、信息论、优化、博弈论、形式语言和自动机、应用心理学、生物学和神经生理学等。这种学科交叉融合带来的良性互动，无疑促进了包括机器学习在内的诸学科的发展与繁荣。
　　本书内容丰富，视野宽阔，深入浅出地介绍了目前机器学习的重要理论和关键算法。不同于常规的机器学习算法入门读物，本书试图从更高的视点和更深的层次来解读机器学习的理论基础，引入了对指导理论研究和实际应用都至关重要的概率近似正确(Probability Approximately Correct，PAC)学习理论。该理论旨在回答由机器学习得到的结果到底有多高的可信度与推广能力，从某种意义上来说，只有理解了这部分内容，才能对机器学习何时能学习以及为何能学习成功有更加深刻的理解。PAC理论涉及的数学基础较多，而国内关于PAC的参考资料非常少，我们人工智能与机器学习研究团队为此进行了多方论证并多次召开专题讨论会。此外，本书还巧妙地从间隔(margin)角度衔接各个章节，对机器学习中的诸多方面进行了完美的统一。
　　本书主要面向人工智能、机器学习、模式识别、数据挖掘、计算机应用、生物信息学、数学和统计学等领域的研究生和相关领域的科技人员。出版中译本的目的是希望能为国内从事相关研究的广大学者和研究生提供一本全面、系统、权威的教科书和参考书。如果能做到这一点，译者将感到十分欣慰。
　　必须说明的是，本书的翻译是中国科学院自动化研究所人工智能与机器学习研究团队集体努力的结果，团队成员杨雪冰、孙正雅、郭肇禄、张志忠、唐永强、何泽文、张似衡、牛景昊、任泽林、李明达、张晨阳、吴雅婧、黄妍、杨萌林、李定、尹彦婷等参与了本书的翻译工作，杨雪冰老师参与了全书的审校与修正，他们付出了艰辛劳动，在此我深表感谢。感谢机械工业出版社华章公司编辑的大力协助，倘若没有他们的热情支持，本书的中译版难以如此迅速地与大家见面。另外，本书的翻译得到了国家自然科学基金委重点项目和面上项目（U1636220、61472423、61432008等）的资助，特此感谢。
　　在翻译过程中，我们力求准确地反映原著内容，同时保留原著的风格。对于英文原版中的一些公式及表述错误，我们在翻译的过程中结合作者的课程讲稿进行了核校，并以译者注的形式指出和修正了部分错误。但由于译者水平有限，书中难免有不妥之处，恳请读者批评指正。
　　最后，谨把本书的中译版献给我的导师王珏研究员！王珏老师生前对机器学习理论、算法和应用非常关注，对机器学习中很多基础问题有着独到而深刻的理解，他启发并引领了我们研究团队对机器学习理论和算法的研究工作，使我们终身受益。
　　中国科学院自动化研究所
　　张文生
　　2019年3月于北京
　　前　言
　　Foundations of Machine Learning
　　本书是关于机器学习的概述，适合作为该领域学生和研究人员的教科书。书中涵盖了机器学习领域的基本内容，并且提供了讨论及检验算法合理性所必需的理论基础和概念工具。不仅如此，本书还描述了应用相关算法时需要考虑的若干关键问题。
　　本书旨在介绍新的机器学习理论和概念，并且对于相对前沿的结果给出了简要的证明。总体而言，我们尽可能在证明的过程中选择简洁的方式。尽管如此，我们会讨论机器学习中出现的一些重要且复杂的主题，指出若干开放的研究问题。对于那些常常与其他主题合并或者未引起足够关注的主题，在本书中将单独成章以着重讨论，例如多分类、排序和回归。
　　尽管本书覆盖了机器学习中很多重要的主题，但是出于论述简洁的目的且因目前缺乏针对一些方法的坚实的理论保证，图模型和神经网络两个重要主题未能覆盖。
　　本书主要面向机器学习、统计和其他相关领域的学生和研究人员，适合作为研究生和高年级本科生课程的教科书，或者学术研讨会的参考文本。本书前三章为后续内容奠定理论基础，第5章亦引入了一些概念来完善理论，并被后面章节广泛使用，而其余各章大多自成体系。每章最后给出了一套练习题，并单独给出完整的解答。
　　　关于本书的习题解答及其他教辅资源，请访问作者主页cs.nyu.edu/faculty/mohri查看和下载。——编辑注
　　我们假定本书的读者熟悉线性代数、概率和算法分析的基本概念。但是，为了进一步辅助学习，我们在附录中简要回顾了线性代数和概率的相关知识，给出了凸优化的简介，并且提供了用于证明集中界的大量有用的工具。
　　据我们所知，没有一本教科书可以涵盖本书所介绍的全部内容。我们会要求每届机器学习专业的学生对学习本书的体会进行反馈。尽管针对不同的专业领域有一些很不错的机器学习参考书，但是这些书并不涉及对其他基本内容的一般性讨论。比如，关于核方法的书并不涉及对boosting、排序、强化学习、学习自动机或者在线学习等主题的讨论。当然也存在更为一般的机器学习方面的书，与之截然不同的是，本书关注理论基础并重视证明。
　　书中所介绍的大部分材料来自机器学习研究生课程(机器学习基础)，该课程由本书第一作者在过去7年中在纽约大学库兰特数学科学研究所讲授。本书极大地受益于该课程的学生以及我们的朋友、同事和相关研究人员所提出的宝贵意见和建议，在此深表感激。
　　特别感谢Corinna Cortes和Yishay Mansour对于本书内容的设计和组织提出的许多重要建议，包括大量详细的注释。我们充分考虑了他们的建议，这对于改进全书帮助很大。此外，还要感谢Yishay Mansour用本书的最初版本进行教学，并向我们积极反馈。
　　我们还要感谢来自学术界和企业界研究实验室的同事和朋友所给予的讨论、建议和贡献，他们是：Cyril Allauzen、Stephen Boyd、Aldo Corbisiero、Spencer Greenberg、Lisa Hellerstein、Sanjiv Kumar、Ryan McDonald、Andres Muoz Medina、Tyler Neylon、Peter Norvig、Fernando Pereira、Maria Pershina、Ashish Rastogi、Michael Riley、Umar Syed、Csaba Szepesvri、Eugene Weinstein和Jason Weston。
　　最后，我们还要感谢MIT出版社对本书所给予的帮助和支持。

目　录
Foundations of Machine Learning
译者序
前言
第1章　引言1
1.1　应用与问题1
1.2　定义与术语2
1.3　交叉验证4
1.4　学习情境5
1.5　本书概览6
第2章　PAC学习框架8
2.1　PAC学习模型8
2.2　对有限假设集的学习保证——一致的情况12
2.3　对有限假设集的学习保证——不一致的情况16
2.4　泛化性18
2.4.1　确定性与随机性情境18
2.4.2　贝叶斯误差与噪声19
2.4.3　估计误差与近似误差19
2.4.4　模型选择20
2.5　文献评注21
2.6　习题22
第3章　Rademacher复杂度和VC-维25
3.1　Rademacher复杂度25
3.2　生长函数29
3.3　VC-维31
3.4　下界36
3.5　文献评注41
3.6　习题42
第4章　支持向量机47
4.1　线性分类47
4.2　可分情况下的支持向量机48
4.2.1　原始优化问题48
4.2.2　支持向量49
4.2.3　对偶优化问题50
4.2.4　留一法51
4.3　不可分情况下的支持向量机52
4.3.1　原始优化问题53
4.3.2　支持向量54
4.3.3　对偶优化问题55
4.4　间隔理论56
4.5　文献评注62
4.6　习题62
第5章　核方法65
5.1　引言65
5.2　正定对称核67
5.2.1　定义67
5.2.2　再生核希尔伯特空间69
5.2.3　性质70
5.3　基于核的算法73
5.3.1　具有PDS核的SVM73
5.3.2　表示定理74
5.3.3　学习保证75
5.4　负定对称核76
5.5　序列核78
5.5.1　加权转换器79
5.5.2　有理核82
5.6　文献评注85
5.7　习题85
第6章　boosting89
6.1　引言89
6.2　AdaBoost算法90
6.2.1　经验误差的界92
6.2.2　与坐标下降的关系93
6.2.3　与逻辑回归的关系94
6.2.4　实践中的标准使用方式95
6.3　理论结果95
6.3.1　基于VC-维的分析96
6.3.2　基于间隔的分析96
6.3.3　间隔最大化100
6.3.4　博弈论解释101
6.4　讨论103
6.5　文献评注104
6.6　习题105
第7章　在线学习108
7.1　引言108
7.2　有专家建议的预测109
7.2.1　错误界和折半算法109
7.2.2　加权多数算法110
7.2.3　随机加权多数算法111
7.2.4　指数加权平均算法114
7.3　线性分类117
7.3.1　感知机算法117
7.3.2　Winnow算法122
7.4　在线到批处理的转换124
7.5　与博弈论的联系127
7.6　文献评注127
7.7　习题128
第8章　多分类133
8.1　多分类问题133
8.2　泛化界134
8.3　直接型多分类算法139
8.3.1　多分类SVM139
8.3.2　多分类boosting算法140
8.3.3　决策树141
8.4　类别分解型多分类算法144
8.4.1　一对多144
8.4.2　一对一145
8.4.3　纠错编码146
8.5　结构化预测算法148
8.6　文献评注149
8.7　习题150
第9章　排序152
9.1　排序问题152
9.2　泛化界153
9.3　使用SVM进行排序155
9.4　RankBoost156
9.4.1　经验误差界158
9.4.2　与坐标下降的关系159
9.4.3　排序问题集成算法的间隔界160
9.5　二部排序161
9.5.1　二部排序中的boosting算法162
9.5.2　ROC曲线下面积164
9.6　基于偏好的情境165
9.6.1　两阶段排序问题166
9.6.2　确定性算法167
9.6.3　随机性算法168
9.6.4　关于其他损失函数的扩展168
9.7　讨论169
9.8　文献评注170
9.9　习题171
第10章　回归172
10.1　回归问题172
10.2　泛化界173
10.2.1　有限假设集173
10.2.2　Rademacher复杂度界174
10.2.3　伪维度界175
10.3　回归算法177
10.3.1　线性回归178
10.3.2　核岭回归179
10.3.3　支持向量回归182
10.3.4　Lasso186
10.3.5　组范数回归算法188
10.3.6　在线回归算法189
10.4　文献评注190
10.5　习题190
第11章　算法稳定性193
11.1　定义193
11.2　基于稳定性的泛化保证194
11.3　基于核的正则化算法的稳定性196
11.3.1　应用于回归算法：SVR和KRR198
11.3.2　应用于分类算法：SVM200
11.3.3　讨论200
11.4　文献评述201
11.5　习题201
第12章　降维203
12.1　主成分分析204
12.2　核主成分分析205
12.3　KPCA和流形学习206
12.3.1　等距映射206
12.3.2　拉普拉斯特征映射207
12.3.3　局部线性嵌入207
12.4　Johnson-Lindenstrauss引理208
12.5　文献评注210
12.6　习题210
第13章　学习自动机和语言212
13.1　引言212
13.2　有限自动机213
13.3　高效精确学习214
13.3.1　被动学习214
13.3.2　通过查询学习215
13.3.3　通过查询学习自动机216
13.4　极限下的识别220
13.5　文献评注224
13.6　习题225
第14章　强化学习227
14.1　学习情境227
14.2　马尔可夫决策过程模型228
14.3　策略229
14.3.1　定义229
14.3.2　策略值229
14.3.3　策略评估230
14.3.4　最优策略230
14.4　规划算法231
14.4.1　值迭代231
14.4.2　策略迭代233
14.4.3　线性规划235
14.5　学习算法235
14.5.1　随机逼近236
14.5.2　TD（0）算法239
14.5.3　Q-学习算法240
14.5.4　SARSA242
14.5.5　TD（λ）算法242
14.5.6　大状态空间243
14.6　文献评注244
结束语245
附录A　线性代数回顾246
附录B　凸优化251
附录C　概率论回顾257
附录D　集中不等式264
附录E　符号273
索引274
参考文献
　参考文献为网络资源，请访问华章网站www.hzbook.com下载。——编辑注