本书解释自动学习方法背后的原理，考虑其广泛的应用。作者既讲述最重要的机器学习算法的工作原理和动机，还指出其固有的优势和缺点，是有兴趣了解机器学习理论和方法以及应用的学生和专业人员的良好教材或参考书。

这部精心撰写的教材不仅讲到了严谨的理论，还涵盖了机器学习的实际应用。这是一本优秀的教材，适合所有想要了解如何在数据中寻找结构的读者。
—— 伯恩哈德·史科夫（Bernhard Sch?lkopf），马克斯·普朗克智能系统研究所
这本教材非常必要，对于想要建立机器学习的数学基础的读者来说，它同时兼具深度和广度，内容严谨、直观而敏锐。本书提供了丰富的算法和分析技巧，经典而基础，还指出了最前沿的研究方向。机器学习是一项重要而迷人的领域，对于任何对其数学及计算基础感兴趣的人来说，这都是一本极佳的书。
—— 艾弗瑞·布卢姆（Avrim Blum），卡内基-梅隆大学

机器学习是计算机科学中发展最快的领域之一，实际应用广泛。这本教材的目标是从理论角度提供机器学习的入门知识和相关算法范式。本书全面地介绍了机器学习背后的基本思想和理论依据，以及将这些理论转化为实际算法的数学推导。在介绍了机器学习的基本内容后，本书还覆盖了此前的教材中一系列从未涉及过的内容。其中包括对学习的计算复杂度、凸性和稳定性的概念的讨论，以及重要的算法范式的介绍（包括随机梯度下降、神经元网络以及结构化输出学习）。同时，本书引入了最新的理论概念，包括PAC-贝叶斯方法和压缩界。本书为高等院校本科高年级和研究生入门阶段而设计，不仅计算机、电子工程、数学统计专业学生能轻松理解机器学习的基础知识和算法，其他专业的读者也能读懂。

作者简介
沙伊·沙莱夫-施瓦茨（Shai Shalev-Shwartz）　以色列希伯来大学计算机及工程学院副教授，还在Mobileye公司研究自动驾驶。2009年之前他在芝加哥的丰田技术研究所工作。他的研究方向是机器学习算法。
沙伊·本-戴维（Shai Ben-David）　加拿大滑铁卢大学计算机科学学院教授。先后在以色列理工学院、澳大利亚国立大学和康奈尔大学任教。

“机器学习”旨在从数据中自动识别有意义的模式。过去几十年中，机器学习成为一项常用工具，几乎所有需要从大量数据集合中提取信息的任务都在使用它。我们身边的许多技术都以机器学习为基础：搜索引擎学习在带给我们最佳的搜索结果的同时，植入可以盈利的广告；屏蔽软件学习过滤垃圾邮件；用于保护信用卡业务的软件学习识别欺诈。数码相机学习人脸识别，智能电话上的个人智能助手学习识别语音命令。汽车配备了用机器学习算法搭建的交通事故预警系统。同时机器学习还被广泛应用于各个科学领域，例如生物信息学、医药以及天文学等。
这些应用领域的一个共同特点在于，与相对传统的计算机应用相比，所需识别的模式更复杂。在这些情景中，对于任务应该如何执行，人类程序员无法提供明确的、细节优化的具体指令。以智能生物为例，我们人类的许多技能都是通过从经验中学习而取得并逐步提高的（而非遵从别人给我们的具体指令）。机器学习工具关注的正是赋予程序“学习”和适应不同情况的能力。
本书的第一个目标是，提供一个准确而简明易懂的导论，介绍机器学习的基本概念：什么是学习？机器怎样学习？学习某概念时，如何量化所需资源？学习始终都是可能的吗？我们如何知道学习过程是成功或失败？
本书的第二个目标是，为机器学习提供几个关键的算法。我们提供的算法，一方面已经成功投入实际应用，另一方面广泛地考虑到不同的学习技术。此外，我们特别将注意力放到了大规模学习（即俗称的“大数据”）上，因为近几年来，世界越来越“数字化”，需要学习的数据总量也在急剧增加。所以在许多应用中，数据量是充足的，而计算时间是主要瓶颈。因此，学习某一概念时，我们会明确量化数据量和计算时间这两个数值。
本书分为四部分。第一部分对于“学习”的基础性问题给出初步而准确的定义。我们会介绍Valiant提出的“概率近似正确（PAC）”可学习模型的通用形式，它将是对“何为学习”这一问题的第一个有力回答。我们还会介绍“经验风险最小化（ERM）”“结构风险最小化（SRM）”和“最小描述长度（MDL）”这几个学习规则，展现“机器是如何学习的”。我们量化使用ERM、SRM和MDL规则学习时所需的数据总量，并用“没有免费的午餐”定理说明，什么情况下学习可能会失败。此外,我们还探讨了学习需要多少计算时间。本书第二部分介绍多种算法。对于一些算法，我们先说明其主要学习原则，再介绍该算法是如何依据其原则运作的。前两部分将重点放在PAC模型上，第三部分将范围扩展到更广、更丰富的学习模型。最后，第四部分讨论最前沿的理论。
我们尽量让本书能够自成一体，不过我们假设读者熟悉概率论、线性代数、数学分析和算法设计的基本概念。前三部分为计算机科学、工程学、数学和统计学研究生一年级学生设计，具有相关背景的本科生也可以使用。高级章节适用于想要对理论有更深入理解的研究者。

计算机/人工智能/机器学习

这部精心撰写的教材不仅讲到了严谨的理论，还涵盖了机器学习的实际应用。这是一本优秀的教材，适合所有想要了解如何在数据中寻找结构的读者。
——伯恩哈德•史科夫（Bernhard Schölkopf）马克斯•普朗克智能系统研究所
这本教材非常必要，对于想要建立机器学习的数学基础的读者来说，它同时兼具深度和广度，内容严谨、直观而敏锐。本书提供了丰富的算法和分析技巧，经典而基础，还指出了最前沿的研究方向。机器学习是一项重要而迷人的领域，对于任何对其数学及计算基础感兴趣的人来说，这都是一本极佳的书。
——艾弗瑞•布卢姆（Avrim Blum） 卡内基梅隆大学

机器学习是计算机科学中发展最快的领域之一，实际应用广泛。这本教材的目标是从理论角度提供机器学习的入门知识和相关算法范式。本书全面地介绍了机器学习背后的基本思想和理论依据，以及将这些理论转化为实际算法的数学推导。在介绍了机器学习的基本内容后，本书还覆盖了此前的教材中一系列从未涉及过的内容。其中包括对学习的计算复杂度、凸性和稳定性的概念的讨论，以及重要的算法范式的介绍（包括随机梯度下降、神经元网络以及结构化输出学习）。同时，本书引入了最新的理论概念，包括PAC-贝叶斯方法和压缩界。本书为本科高年级和研究生入门阶段而设计，不仅学生能轻松理解机器学习的基础知识和算法，非统计、计算机、数学、工程专业的读者也能读懂。

[以] 沙伊·沙莱夫-施瓦茨（Shai Shalev-Shwartz）[加] 沙伊·本-戴维（Shai Ben-David） 著：Shai Shalev-Shwartz，以色列希伯来大学计算机及工程学院副教授。2009年之前在芝加哥的丰田技术研究所工作，现在Mobileye公司研究自动驾驶。
Shai Ben-David，加拿大滑铁卢大学计算机学院教授。先后在以色列理工学院、澳大利亚国立大学和康奈尔大学任教。

张文生 等译：暂无简介

以色列希伯来大学副教授Shai ShalevShwartz和加拿大滑铁卢大学教授Shai BenDavid的专著《Understanding Machine Learning:From Theory to Algorithms》是机器学习领域一部具有里程碑意义的著作。
近几年，机器学习是人工智能研究领域中最活跃的分支之一，已成为信息科学领域解决实际问题的重要方法，它的应用已遍及人工智能的各个应用领域。机器学习又是一个多学科的交叉领域，涉及数学、自动化、计算机科学、应用心理学、生物学和神经生理学等。这种学科交叉融合带来的良性互动，无疑促进了包括机器学习在内的诸学科的发展与繁荣。
本书内容十分丰富，作者以前所未有的广度和深度，介绍了目前机器学习中重要的理论和关键的算法。本书没有陷入“科普”式的堆砌材料的写作方式，由于作者是该领域的权威专家，因此在介绍各种理论和算法时，时刻不忘将不同理论、算法的对比与作者自身的研究成果传授给读者，使读者不至于对如此丰富的理论和算法无所适从。另外，特别值得指出的是，本书第一部分非常有特色，也是非常重要的一部分。这部分内容从更高的观点和更深的层次探讨机器学习的许多理论基础，引入对指导理论研究和实际应用都至关重要的概率近似正确（Probably Approximately Correct，PAC）学习理论。该理论旨在回答由机器学习得到的结果到底有多高的可信度与推广能力，从某种意义上来说，只有懂得了该部分，才可能透彻地理解和更好地运用其他章节的内容。国内关于PAC学习的资料非常少，在翻译过程中团队成员碰到了极大的困难，我们人工智能与机器学习研究团队为此进行了多方论证并多次召开专题讨论会。
本书主要面向人工智能、机器学习、模式识别、数据挖掘、计算机应用、生物信息学、数学和统计学等领域的研究生和相关领域的科技人员。翻译出版中译本的目的，是希望能为国内广大从事相关研究的学者和研究生提供一本全面、系统、权威的教科书和参考书。如果能做到这一点，译者将感到十分欣慰。
必须说明的是，本书的翻译是中国科学院自动化研究所人工智能与机器学习研究团队集体努力的结果，团队的成员杨雪冰、匡秋明、蒋晓娟、薛伟、魏波、李思园、张似衡、曾凡霞、于廷照、王鑫、李涛、杨叶辉、胡文锐、张志忠、唐永强、陈东杰、何泽文、张英华、李悟、李硕等参与了本书的翻译工作，李思园老师参与了全书的审校与修正。感谢机械工业出版社华章分社的大力协助，倘若没有他们的热情支持，本书的中译版难以如此迅速地与大家见面。另外，本书的翻译得到了国家自然科学基金委重点项目和面上项目（61472423、U1135005、61432008、61532006、61305018、61402481等）的资助，特此感谢。
在翻译过程中，我们力求准确地反映原著内容，同时保留原著的风格。但由于译者水平有限，书中难免有不妥之处，恳请读者批评指正。
最后，谨把本书的中译版献给我的博士生导师王珏研究员！王珏老师生前对机器学习理论、算法和应用非常关注，对于PAC可学习理论也有着独到而深刻的理解，他启发并引领了我们研究团队对机器学习理论和算法的研究工作，使我们终身受益。

中国科学院自动化研究所
张文生
2016年4月于北京

出版者的话
译者序
前言
致谢
第1章引论1
11什么是学习1
12什么时候需要机器学习2
13学习的种类3
14与其他领域的关系4
15如何阅读本书4
16符号6
第一部分理论基础
第2章简易入门10
21一般模型——统计学习理论框架10
22经验风险最小化11
23考虑归纳偏置的经验风险最小化12
24练习15
第3章一般学习模型17
31PAC学习理论17
32更常见的学习模型18
321放宽可实现假设——不可知PAC学习18
322学习问题建模19
33小结21
34文献评注21
35练习21
第4章学习过程的一致收敛性24
41一致收敛是可学习的充分条件24
42有限类是不可知PAC可学习的25
43小结26
44文献评注27
45练习27
第5章偏差与复杂性权衡28
51“没有免费的午餐”定理28
52误差分解31
53小结31
54文献评注32
55练习32
第6章VC维33
61无限的类也可学习33
62VC维概述34
63实例35
631阈值函数35
632区间35
633平行于轴的矩形35
634有限类36
635VC维与参数个数36
64PAC学习的基本定理36
65定理67的证明37
651Sauer引理及生长函数37
652有小的有效规模的类的一致收敛性39
66小结40
67文献评注41
68练习41
第7章不一致可学习44
71不一致可学习概述44
72结构风险最小化46
73最小描述长度和奥卡姆剃刀48
74可学习的其他概念——一致收敛性50
75探讨不同的可学习概念51
76小结53
77文献评注53
78练习54
第8章学习的运行时间56
81机器学习的计算复杂度56
82ERM规则的实现58
821有限集58
822轴对称矩形59
823布尔合取式59
824学习三项析取范式60
83高效学习，而不通过合适的ERM60
84学习的难度*61
85小结62
86文献评注62
87练习62
第二部分从理论到算法
第9章线性预测66
91半空间66
911半空间类线性规划67
912半空间感知器68
913半空间的VC维69
92线性回归70
921最小平方70
922多项式线性回归71
93逻辑斯谛回归72
94小结73
95文献评注73
96练习73
第10章boosting75
101弱可学习75
102AdaBoost78
103基础假设类的线性组合80
104AdaBoost用于人脸识别82
105小结83
106文献评注83
107练习84
第11章模型选择与验证85
111用结构风险最小化进行模型选择85
112验证法86
1121留出的样本集86
1122模型选择的验证法87
1123模型选择曲线88
1124k折交叉验证88
1125训练验证测试拆分89
113如果学习失败了应该做什么89
114小结92
115练习92
第12章凸学习问题93
121凸性、利普希茨性和光滑性93
1211凸性93
1212利普希茨性96
1213光滑性97
122凸学习问题概述98
1221凸学习问题的可学习性99
1222凸利普希茨/光滑有界学习问题100
123替代损失函数101
124小结102
125文献评注102
126练习102
第13章正则化和稳定性104
131正则损失最小化104
132稳定规则不会过拟合105
133Tikhonov正则化作为稳定剂106
1331利普希茨损失108
1332光滑和非负损失108
134控制适合与稳定性的权衡109
135小结111
136文献评注111
137练习111
第14章随机梯度下降114
141梯度下降法114
142次梯度116
1421计算次梯度117
1422利普希茨函数的次梯度118
1423次梯度下降118
143随机梯度下降118
144SGD的变型120
1441增加一个投影步120
1442变步长121
1443其他平均技巧121
1444强凸函数*121
145用SGD进行学习123
1451SGD求解风险极小化123
1452SGD求解凸光滑学习问题的分析124
1453SGD求解正则化损失极小化125
146小结125
147文献评注125
148练习126
第15章支持向量机127
151间隔与硬SVM127
1511齐次情况129
1512硬SVM的样本复杂度129
152软SVM与范数正则化130
1521软SVM的样本复杂度131
1522间隔、基于范数的界与维度131
1523斜坡损失*132
153最优化条件与“支持向量”*133
154对偶*133
155用随机梯度下降法实现软SVM134
156小结135
157文献评注135
158练习135
第16章核方法136
161特征空间映射136
162核技巧137
1621核作为表达先验的一种形式140
1622核函数的特征*141
163软SVM应用核方法141
164小结142
165文献评注143
166练习143
第17章多分类、排序与复杂预测问题145
171一对多和一对一145
172线性多分类预测147
1721如何构建Ψ147
1722对损失敏感的分类148
1723经验风险最小化149
1724泛化合页损失149
1725多分类SVM和SGD150
173结构化输出预测151
174排序153
175二分排序以及多变量性能测量157
176小结160
177文献评注160
178练习161
第18章决策树162
181采样复杂度162
182决策树算法163
1821增益测量的实现方式164
1822剪枝165
1823实值特征基于阈值的拆分规则165
183随机森林165
184小结166
185文献评注166
186练习166
第19章最近邻167
191k近邻法167
192分析168
19211NN准则的泛化界168
1922“维数灾难”170
193效率实施*171
194小结171
195文献评注171
196练习171
第20章神经元网络174
201前馈神经网络174
202神经网络学习175
203神经网络的表达力176
204神经网络样本复杂度178
205学习神经网络的运行时179
206SGD和反向传播179
207小结182
208文献评注183
209练习183
第三部分其他学习模型
第21章在线学习186
211可实现情况下的在线分类186
212不可实现情况下的在线识别191
213在线凸优化195
214在线感知器算法197
215小结199
216文献评注199
217练习199
第22章聚类201
221基于链接的聚类算法203
222k均值算法和其他代价最小聚类203
223谱聚类206
2231图割206
2232图拉普拉斯与松弛图割算法206
2233非归一化的谱聚类207
224信息瓶颈*208
225聚类的进阶观点208
226小结209
227文献评注210
228练习210
第23章维度约简212
231主成分分析212
2311当dm时一种更加有效的求解方法214
2312应用与说明214
232随机投影216
233压缩感知217
234PCA还是压缩感知223
235小结223
236文献评注223
237练习223
第24章生成模型226
241极大似然估计226
2411连续随机变量的极大似然估计227
2412极大似然与经验风险最小化228
2413泛化分析228
242朴素贝叶斯229
243线性判别分析230
244隐变量与EM算法230
2441EM是交替最大化算法232
2442混合高斯模型参数估计的EM算法233
245贝叶斯推理233
246小结235
247文献评注235
248练习235
第25章特征选择与特征生成237
251特征选择237
2511滤波器238
2512贪婪选择方法239
2513稀疏诱导范数241
252特征操作和归一化242
253特征学习244
254小结246
255文献评注246
256练习246
第四部分高级理论
第26章拉德马赫复杂度250
261拉德马赫复杂度概述250
262线性类的拉德马赫复杂度255
263SVM的泛化误差界256
264低1范数预测器的泛化误差界258
265文献评注259
第27章覆盖数260
271覆盖260
272通过链式反应从覆盖到拉德马赫复杂度261
273文献评注262
第28章学习理论基本定理的证明263
281不可知情况的上界263
282不可知情况的下界264
2821证明m(ε，δ)≥05log(1/(4δ))/ε2264
2822证明m(ε，1/8)≥8d/ε2265
283可实现情况的上界267
第29章多分类可学习性271
291纳塔拉詹维271
292多分类基本定理271
293计算纳塔拉詹维272
2931基于类的一对多272
2932一般的多分类到二分类约简273
2933线性多分类预测器273
294好的与坏的ERM274
295文献评注275
296练习276
第30章压缩界277
301压缩界概述277
302例子278
3021平行于轴的矩形278
3022半空间279
3023可分多项式279
3024间隔可分的情况279
303文献评注280
第31章PAC贝叶斯281
311PAC贝叶斯界281
312文献评注282
313练习282
附录A技术性引理284
附录B测度集中度287
附录C线性代数294
参考文献297
索引305