本书是机器学习领域内一部具有里程碑意义的著作。包括哥伦比亚大学、北京大学在内的多个国内外名校均有以该书为基础开设的研究生课程。全书内容丰富,视野宽阔,深入浅出地介绍了目前机器学习重要的理论和关键的算法。
本书是关于机器学习的概述,适合作为该领域学生和研究人员的教科书。本书涵盖机器学习领域的基本内容,并且提供讨论及检验算法合理性所必需的理论基础和概念工具。不仅如此,本书还描述了应用相关算法时需要考虑的若干关键问题。
本书旨在介绍最新的理论和概念,并且对于相对先进的结果给出简要的证明。总体而言,我们尽可能使全书叙述简洁。尽管如此,我们也会讨论机器学习中出现的一些重要且复杂的主题,指出若干开放的研究问题。对于那些常常与其他主题合并或者未引起足够关注的主题,本书将单独着重讨论,例如,将多分类、排序和回归分别用一章来讲解。
尽管本书覆盖机器学习中很多重要的主题,但是出于简略且因目前缺乏针对一些方法的坚实的理论保证,未能覆盖图模型和神经网络这两个重要主题。
本书主要面向机器学习、统计和其他相关领域的学生与研究人员,适合作为研究生和高年级本科生课程的教科书,或者学术研讨会的参考资料。本书前三四章为后续材料奠定理论基础,第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出版社对本书所给予的帮助和支持。
译者序
前言
第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 对偶定理的证明23