机器学习：算法背后的理论与优化

本书深入浅出地介绍了机器学习的代表性算法，并揭示其背后隐含的统计学习理论，是人工智能、机器学习方向的入门和进阶专业材料

以机器学习为核心的人工智能已经成为新一代生产力发展的主要驱动因素。新的技术正在向各行各业

渗透，大有变革各个领域的趋势。传统产业向智慧产业的升级迫使原行业从业人员逐渐转型，市场上对相

关学习材料的需求也日益高涨。帮助广大学习者更好地理解和掌握机器学习，是编写本书的目的。

本书针对机器学习领域中1常见的一类问题——有监督学习，从入门、进阶、深化三个层面由浅入深

地进行了讲解。三个层面包括基础入门算法、核心理论及理论背后的数学优化。入门部分用以逻辑回归为

代表的广义线性模型为出发点，引入书中所有涉及的知识点；进阶部分的核心理论涵盖了经验风险1小、

结构风险1小、正则化及统一的分类边界理论；深化部分的数学优化则主要包括1大熵原理、拉格朗日对

偶等理论在数学上的推导，以及对模型求解的主流1优化方法的探讨等。

本书由浅入深，从个别到普便，从自然算法到优化算法，从各个角度深入剖析了机器学习，力求帮助

读者循序渐进地掌握机器学习的概念、算法和优化理论。

机器学习-算法背后的理论与优化

史春奇、卜晶祎、施智平 著

史春奇博士，毕业于日本京都大学，美国Brandeis University博士后，现为港辉金融信息Vice President， 曾任通用电气（中国）有限公司资深数据科学家。

卜晶祎，毕业于上海交通大学，现为友邦保险集团人工智能主管。曾就职于通用电气（中国）研究开发中心有限公司，任资深数据科学家；曾任飞利浦亚洲研究院高级研究员。

施智平博士，首都师范大学信息工程学院教授，院长，毕业于中科院计算技术研究所。于2012年和2017年获北京市科学技术奖二等奖两次，中国计算机学会高级会员，形式化方法专委会委员，人工智能学会会员，智能服务专委会委员，IEEE/ACM 会员。

第1 章线性回归与逻辑回归. 1

1.1 线性回归. 1

1.1.1 函数关系与统计关系.1

1.1.2 统计与机器学习. 2

1.2 最小二乘法与高斯-马尔可夫定理. 5

1.2.1 最小二乘法. . 5

1.2.2 高斯-马尔可夫定理. . 6

1.3 从线性回归到逻辑回归. 8

1.4 最大似然估计求解逻辑回归. . 9

1.5 最小二乘与最大似然. . 11

1.5.1 逻辑回归与伯努利分布. 11

1.5.2 线性回归与正态分布. 12

1.6 小结. 13

参考文献. 13

第2 章广义线性模型. 15

2.1 广义线性模型概述.15

2.1.1 广义线性模型的定义. 15

2.1.2 链接函数与指数分布簇. 17

2.2 广义线性模型求解.20

2.3 最大似然估计Ⅰ：Fisher 信息. 21

2.4 最大似然估计Ⅱ：KL 散度与Bregman 散度. 23

2.4.1 KL 散度. . 23

2.4.2 Bregman 散度. . 25

2.5 小结. 26

X

参考文献. 26

第3 章经验风险最小. 28

3.1 经验风险与泛化误差概述. .28

3.1.1 经验风险. 30

3.1.2 泛化误差. 30

3.1.3 欠拟合和过拟合. . 34

3.1.4 VC 维. . 37

3.2 经验风险最小的算法. . 40

3.3 分类边界. . 42

3.3.1 分类算法的损失函数. 42

3.3.2 分类算法的边界. . 45

3.4 小结. 48

参考文献. 48

第4 章结构风险最小. 49

4.1 经验风险最小和过拟合. . 49

4.2 结构风险最小和正则化. . 51

4.2.1 从空间角度理解SRM 52

4.2.2 从贝叶斯观点理解SRM 54

4.3 回归的正则化. 55

4.3.1 L2 正则化和岭回归. 56

4.3.2 L1 正则化和Lasso 回归. . 57

4.3.3 L1、L2 组合正则化和ElasticNet 回归. . 58

4.4 分类的正则化. 60

4.4.1 支持向量机和L2 正则化. 60

4.4.2 XGBoost 和树正则化. 62

4.4.3 神经网络和DropOut 正则化. 65

4.4.4 正则化的优缺点. . 66

4.5 小结. 67

参考文献. 67

第5 章贝叶斯统计与熵.68

5.1 统计学习的基础：参数估计. .68

5.1.1 矩估计. .68

XI

5.1.2 最大似然估计.69

5.1.3 最小二乘法. 71

5.2 概率分布与三大统计思维. .72

5.2.1 频率派和正态分布. . 72

5.2.2 经验派和正态分布. . 75

5.2.3 贝叶斯派和正态分布. 76

5.2.4 贝叶斯统计和熵的关系. 79

5.3 信息熵的理解. 79

5.3.1 信息熵简史. 79

5.3.2 信息熵定义. 80

5.3.3 期望编码长度解释. . 81

5.3.4 不确定性公理化解释. 81

5.3.5 基于熵的度量.84

5.4 最大熵原理. . 86

5.4.1 最大熵的直观理解. . 86

5.4.2 最大熵解释自然指数分布簇. . 87

5.4.3 最大熵解释最大似然估计.89

5.5 小结. 90

参考文献. 90

第6 章基于熵的Softmax. .92

6.1 二项分布和多项分布. . 92

6.2 Logistic 回归和Softmax 回归. .93

6.2.1 广义线性模型的解释. 93

6.2.2 Softmax 回归. 94

6.2.3 最大熵原理与Softmax 回归的等价性.96

6.3 最大熵条件下的Log-Linear 101

6.4 多分类界面.103

6.4.1 感知机和多分类感知机. . 104

6.4.2 多分类感知机和结构感知机. 105

6.5 概率图模型里面的Log-Linear 106

6.6 深度学习里面的Softmax 层. . 108

6.7 小结. . 109

XII

参考文献. . 109

第7 章拉格朗日乘子法. 111

7.1 凸共轭. .111

7.1.1 凸共轭的定义. 111

7.1.2 凸共轭定理. . 113

7.2 拉格朗日对偶. . 114

7.2.1 拉格朗日对偶概述.115

7.2.2 Salter 条件. . 117

7.2.3 KKT 条件. 118

7.3 Fenchel 对偶. .120

7.4 增广拉格朗日乘子法. 123

7.4.1 近端. 123

7.4.2 增广拉格朗日乘子法和对偶上升算法. .126

7.5 交替方向乘子法. . 129

7.5.1 对偶分解. . 130

7.5.2 交替方向乘子法概述. . 131

7.6 小结. . 131

参考文献. . 132

第8 章随机梯度下降法. 134

8.1 随机梯度下降法概述. 134

8.1.1 机器学习场景. 134

8.1.2 随机梯度下降法的定义. . 135

8.1.3 随机梯度下降法收敛性分析. 136

8.1.4 收敛性证明. . 139

8.2 随机梯度下降法进阶Ⅰ：方差缩减. 140

8.2.1 方差缩减的效果. 141

8.2.2 方差缩减的实现. 143

8.3 随机梯度下降法进阶Ⅱ：加速与适应. 145

8.3.1 加速. 146

8.3.2 适应. 148

8.3.3 加速￡ 适应. 151

8.4 随机梯度下降法的并行实现. . 156

XIII

8.5 小结. . 160

参考文献. . 161

第9 章常见的最优化方法. 163

9.1 最速下降算法. . 163

9.1.1 l2 范数与梯度下降法. . 164

9.1.2 l1 范数与坐标下降算法. . 165

9.1.3 二次范数与牛顿法.166

9.2 步长的设定.168

9.2.1 Armijo-Goldstein 准则. 169

9.2.2 Wolfe-Powell 准则. 170

9.2.3 回溯线搜索. . 171

9.3 收敛性分析.171

9.3.1 收敛速率. . 172

9.3.2 对目标函数的一些假设. . 173

9.4 一阶算法：梯度下降法. 177

9.5 二阶算法：牛顿法及其衍生算法. .178

9.5.1 牛顿法与梯度下降法的对比. 179

9.5.2 拟牛顿法. . 180

9.5.3 从二次范数的角度看牛顿法. 182

9.6 小结. . 183

参考文献. . 185

在当今的人工智能领域中最热门技术毫无疑问当属深度学习。深度学习在Geo?rey

Hinton、Yoshua Bengio、Yann LeCun 和Juergen Schmidhuber 等巨擘们持续不断的贡献

下，在文本、图像、自然语言等方向均取得了革命性的进展。当然，深度学习只是机器学习

的一个分支，能取得当前的成功也是建立在机器学习不断发展的基础之上。在机器学习领

域，很多著名科学家(如图1 所示) 提出了他们的理论，做出了他们的贡献。Leslie Valiant

提出的概率近似正确学习(Probably Approximately Correct Learning, PAC) 理论打下了

计算学习理论的基石，并在此后提出了自举(Boosting) 思想。Vladimir Vapnik 提出的支

持向量机(Support Vector Machine, SVM) 是一个理论和应用都十分强大的算法。与此同

时他所提出的经验风险最小与结构风险最小理论，以及背后更深层次的VC 维(Vapnik-

Chervonenkis dimension) 理论，为部分统一分类问题提供了理论基础。Judea Pearl 提出

图1 机器学习领域(支持向量机、集成学习、概率图模型) 的著名科学家

II

了贝叶斯网络，而Michael I. Jordan 则在此基础上发展了概率图模型。Leo Breiman 在集

成(Ensemble) 学习的思想下设计了随机森林(Random Forest) 算法，Robert Schapire 和

Jerome H. Friedman 则基于Boosting 分别发明了AdaBoost和Gradient Boosting算法。至

此，机器学习中最耀眼的算法|| 支持向量机、集成学习和概率图模型交相辉映，为整

个机器学习理论的发展奠定了深厚的基础。

本书首先尝试把机器学习的经典算法，包括逻辑回归(Logistic Regression)、支持

向量机和AdaBoost 等，在经验风险最小和结构风险最小的框架下进行统一，并且借助

Softmax 模型和概率图模型中的Log-Linear 模型阐述它们的内在联系；其次从熵的角度

解读概率分布、最大似然估计、指数分布族、广义线性模型等概念；最后深入剖析用于求

解的最优化算法及其背后的数学理论。

本书的主要内容

全书分为9 个章节，从单一算法到统一框架，再到一致最优化求解，各章节的设置

如下。

第1 章，首先提出并探讨几个基本问题，包括回归思想、最优模型评价标准、数理统

计与机器学习的关系等。之后介绍两个最简单最常见的有监督学习算法|| 线性回归和

逻辑回归，并从计算的角度分析两种模型内在的关联，从而为学习“广义线性模型”打下

基础。在本章的最后部分初步讲解两个模型的求解方法|| 最小二乘法和最大似然估

计。

第2 章，主要内容是线性回归的泛化形式|| 广义线性模型。本章详细介绍广义线

性模型，并在第1 章的基础上从Fisher 信息、KL 散度、Bregman 距离的角度深入讲解

最大似然估计。本章可以看作是第3 章的基础引入。

第3 章，在前两章的基础上提出泛化误差和经验风险最小等概念，并且将最小二乘

和最大似然并入损失函数的范畴。在此基础之上，我们便将逻辑回归、支持向量机和Ada

Boost 算法统一到分类界面的框架下。至此我们会看到不同的算法只是分别对应了不同

的损失函数。

第4 章，介绍经验风险最小的不足与过拟合的概念，之后引出正则化。紧接着介绍

有监督学习算法中的常见正则化方法，包括L1 和L2 正则化XG Boost 和树。本章从两

个角度对L1 和L2 正则化进行深入讲解|| 贝叶斯和距离空间。这两个观点分别对应

了本书后续的两大部分|| 熵和最优化。

第5 章，介绍贝叶斯统计和熵之间的关系，并且基于熵重新解读了最大似然估计、指

III

数分布族等概念。本章可以看作是前四章中出现的内容在熵概念下的再定义。同时也是

为下一章的Log-Linear 模型作出铺垫。

第6 章，介绍Softmax 和Log-Linear 的变化，并且将第3 章的二分类界面泛化到多

分类界面，把分类问题的思路扩展到了多分类和结构分类。在本章中通过Log-Linear 关

联了概率图模型，通过Softmax 关联了深度学习。

第7 章，承接第4 章中L1 和L2 正则化在最优化角度的解释，从凸共轭的开始递进

地推导出拉格朗日对偶、Fenchel 对偶、增广拉格朗日乘子法、交替方向乘子法。

第8 章，介绍有监督学习模型在机器学习场景下的统一求解方法|| 随机梯度下

降法及其改进算法。本章对随机梯度下降法进行了收敛性分析，并根据分析结果针对其

缺点着重介绍了两类改进策略|| 方差缩减、加速和适应。

第9 章，主要对数学意义上的最优化方法进行探讨，可以看作是连接第7 章和第8

章的桥梁。第7 章的内容是本章的理论部分，而第8 章的内容则是本章介绍的算法应用

在在机器学习场景中的特例，主要内容包括一阶、二阶最优化算法及其收敛性分析。

图2 章节结构关系图

史春奇与卜晶祎为本书的共同第一作者。书中第3?6 章主要由史春奇博士撰写，第

IV

1、2、7?9 章主要由卜晶祎撰写，施智平教授参与了本书的组织结构设计并提出了很多宝

贵意见。由于作者的能力与水平有限，本书对机器学习的探讨难免会有不全面、不深刻

等不足之处，敬请各位读者批评指正，如蒙赐教将不胜感激。

各个章节结构之间的关系如图2 所示。对于基础稍浅的读者，可以按照图示循序渐

进地阅读；对于有一定基础的读者，可以跳过部分章节直接阅读感兴趣的章节。

作者

2019 年1 月