机器学习：算法视角（原书第2版）

机器学习融合了计算机科学、统计学、数学、工程学等多个学科，应用领域遍及经济、生物、医药、物理、化学等。本书针对计算机科学专业学生遇到的统计学基础知识不足的问题，聚焦于机器学习中的算法，清晰呈现算法背后的数学和统计学知识，同时提供必要的编程技巧和实验方法。
　　书中全面涵盖各类算法，如神经网络、多层感知器、径向基函数、支持向量机、进化学习、强化学习、决策树学习、无监督学习、图模型等。第2版进行了全面修订和更新，以反映机器学习的新发展，新增了两个章节来讨论深度置信网络和高斯过程，此外，还添加了随机森林、考虑精度的方法、MLP的共轭梯度优化、卡尔曼滤波和粒子滤波等内容。
　　本书的代码示例采用Python语言编写，所有代码均可从stephenmonika.net免费下载。

作者简介：

　　史蒂芬·马斯兰（Stephen Marsland）新西兰惠灵顿维多利亚大学数学与统计学院教授，兼任新西兰复杂系统卓越研究中心项目主管，负责复杂性、风险与不确定性等相关主题的研究工作。研究兴趣是几何和复杂系统的应用，主要涉及形状空间、机器学习和算法。

　　译者简介：

　　高阳 教授/博导，目前任南京大学计算机科学与技术系副主任，中国计算机学会机器学习专委会副主任。1997年开始从事人工智能、机器学习、多Agent系统、大数据、图像和视频分析等方向的学术研究。2010年入选教育部新世纪优秀人才计划。曾获2017年度中国人工智能学会吴文俊自然科学奖二等奖、2018年度江苏省科学技术奖二等奖。

　　商琳 博士／副教授，1998年起任教于南京大学计算机科学与技术系，长期从事人工智能、机器学习、计算智能、文本挖掘、图像与视频理解等领域的教学与科研工作。目前担任中国计算机学会人工智能与模式识别专委会委员，中国人工智能学会粒计算与知识发现专委会副秘书长。

CRC Press机器学习领域畅销教材
　　知名媒体推荐的十大机器学习入门教材之一。
　　新西兰惠灵顿维多利亚大学数学与统计学院史蒂芬·马斯兰教授所著
　　南京大学计算机科学与技术系高阳教授、商琳副教授联袂翻译
　　本书的核心视角是全面覆盖机器学习中的各种算法并探究其工作原理，旨在帮助读者掌握算法思想，熟悉相关的数学与统计学知识，并掌握必要的编程技巧和实验方法。书中首先介绍基础概念，然后从相对简单的监督学习方法开始讲解，同时讨论了优化和搜索问题，之后分析无监督学习算法，最后探讨更现代的基于统计的机器学习方法。本书配有大量习题，代码示例采用 Python语言编写，所有代码均可免费下载

第2版前言
　　Machine Learning: An Algorithmic Perspective, Second Edition
　　自从本书第1版出版以来，在过去的几年里，机器学习领域有了一些有意义的发展。一个是深度置信网络的崛起，这是一个真正激起了强烈研究兴趣的领域（同时也蕴含着巨大的商业利益，因为大型互联网公司都希望抢购涉足这一领域的每家小公司）；而另一个则是长期持续进行的关于机器学习统计解释的研究。后者作为一个研究领域是非常不错的，但对于计算机科学专业的学生而言，由于欠缺统计学基础知识，起步阶段是很困难的，然而，他们又非常有必要学习和关注这个领域的知识。本书专注于机器学习中的算法，希望能帮助学生掌握算法思想，并熟悉相关的数学与统计学知识，以及必要的编程技巧和实验方法。
　　此外，可用的Python库一直在不断更新，现在有更多的工具可供程序员使用。借助这些便利条件，本书提供了用于实验的支持向量机的简单实现，其他几个地方的代码也做了精简。所有示例代码都可以从http://stephenmonika.net/下载（在“Book”标签下），在学习机器学习的过程中，强烈鼓励大家根据需要随时使用这些代码进行实验。
　　本书第2版的主要修改包括：
　　●补充了关于两个新领域的新章节：深度置信网络（第17章）和高斯过程（第18章）。
　　●重新对章节进行了排序，并且增加了一些材料，使得全书更加自然、流畅。
　　●重新撰写了关于支持向量机的内容，以包含运行代码和实验建议。
　　●增加了随机森林（13.3节）、感知器收敛定理（3.4.1节）、适当考虑精度的方法（2.2.4节）、MLP的共轭梯度优化（9.3.2节）以及在第16章添加的卡尔曼滤波和粒子滤波。
　　●改进了代码，包括更好地使用Python的命名约定。
　　●贯穿全书的文字修改，使解释更清晰，细节更精准。
　　在此，我要感谢为本书出谋划策的所有人，他们阅读了不同章节，对于内容的取舍与讲解的方式提出了很多建议。还要感谢新西兰梅西大学的学生，他们与我一起研究了这些材料，无论是作为课程作业的一部分，还是作为研究工作的第一步，无论是理论研究还是机器学习应用。感谢那些为第2版做出特别贡献的人，包括：Nirosha Priyadarshani, James Curtis,Andy Gilman,rjan Ekeberg，以及Osnabrück Knowledge-Based Systems Research小组，特别是Joachim Hertzberg、Sven Albrecht和Thomas Wieman。
　　Stephen Marsland
　　于新西兰阿什赫斯特
　　第1版前言
　　Machine Learning: An Algorithmic Perspective, Second Edition
　　在传统的科学研究中，学科与学科之间的融合与交流并不多，而有一门学科则做到了融合计算机科学、统计学、数学、工程学这些学科，甚至将其应用范围扩展至经济、生物、医药、物理、化学等领域中，这就是机器学习。在过去的十年中，机器学习的这种多学科魅力逐渐被人们所理解并推崇。但是，撰写一部系统介绍机器学习的著作是非常困难的，因为这本书要满足不同科学领域的研究者想要了解机器学习的需求。
　　作为人工智能领域的重要分支，机器学习通常在大学中作为计算机科学类课程开设，但是想要真正了解机器学习算法背后的工作原理，统计学和数学基础是必不可少的。在大学任教期间，我发现其中许多内容对数学基础的要求已经超过了计算机专业学生的所学范围，于是我重新整理了课堂讲稿与笔记，形成了本书的第1版。本书的重点在于介绍机器学习中的各类算法并探究其工作原理，同时附有大量习题。此外，本书的相关网站http://stephenmonika.net/MLbook.html提供书中的示例代码，供读者下载学习。
　　对于这类实用算法，用实际语言写的例子总是好于某种形式的伪代码。因为这可以让读者马上运行程序并在数据上做实验，而不用操心所选用特定语言的某些无关实现细节。任何计算机编程语言都能用来实现机器学习算法，并且全世界有各种语言的机器学习资源。在本书中我选择的是Python，因为Python语言简单易用、支持多平台，在科学计算中Python几乎已经成为首选语言。对于有编程基础的读者，Python是极易上手的；对于没有编程基础的初学者，Python也是非常友好的，附录A中介绍了如何使用Python进行基础的数值计算。
　　目前市面上已有许多关于机器学习的优秀著作，而对于本书，我希望它能为想深入学习这门学科的读者提供一个切入点。除此之外，网络上关于机器学习的各种学习资源也颇为丰富，开源软件网站http://mloss.org/software/提供了许多可供下载的机器学习软件。
　　此外，UCI机器学习库（http://archive.ics.uci.edu/ml/）提供了大量数据集，这些数据集可以用来实现并测试不同的机器学习算法，本书中用到的许多实验数据也来源于此。需要注意的是，在实际问题中，如何获取合适的数据并对其进行预处理以供机器学习算法学习其实是一个不小的问题。
　　在此，我要对在本书编写过程中给予帮助和提供建议的朋友表示衷心的感谢。尤其感谢Zbigniew Nowicki、Joseph Marsland、Bob Hodgson、Patrick Rynhart、Gary Allen、Linda Chua、Mark Bebbington、JP Lewis、Tom Duckett以及Monika Nowicki对本书第1版的贡献。特别感谢Jonathan Shapiro在机器学习研究过程中对我的帮助。
　　Stephen Marsland
　　于新西兰阿什赫斯特

第2版前言
第1版前言
第1章　绪论1
1.1　如果数据有质量，地球将成为黑洞1
1.2　学习3
1.2.1　机器学习3
1.3　机器学习的类别4
1.4　监督学习5
1.4.1　回归5
1.4.2　分类6
1.5　机器学习过程7
1.6　关于编程的注意事项8
1.7　本书的学习路线 9
拓展阅读10
第2章　预备知识11
2.1　专业术语11
2.1.1　权重空间11
2.1.2　维度灾难12
2.2　知你所知：测试机器学习算法13
2.2.1　过拟合14
2.2.2　训练集、测试集和验证集14
2.2.3　混淆矩阵15
2.2.4　精度指标16
2.2.5　受试者工作特征曲线17
2.2.6　不平衡数据集17
2.2.7　度量精度18
2.3　数据与概率的转换19
2.3.1　最小化风险20
2.3.2　朴素贝叶斯分类21
2.4　基本统计概念22
2.4.1　平均值22
2.4.2　方差与协方差22
2.4.3　高斯分布24
2.5　权衡偏差与方差24
拓展阅读26
习题26
第3章　神经元、神经网络和线性判别27
3.1　大脑和神经元27
3.1.1　Hebb法则27
3.1.2　McCulloch和Pitts神经元28
3.1.3　McCulloch和Pitts神经元模型的局限性29
3.2　神经网络30
3.3　感知器31
3.3.1　学习速率η32
3.3.2　输入偏置32
3.3.3　感知器学习算法33
3.3.4　感知器学习示例34
3.3.5　具体实现35
3.4　线性可分性39
3.4.1　感知器收敛定理40
3.4.2　XOR函数41
3.4.3　有用的领悟42
3.4.4　另一个示例：皮马印第安人数据集43
3.4.5　数据预处理44
3.5　线性回归45
3.5.1　示例46
拓展阅读47
习题48
第4章　多层感知器49
4.1　前向50
4.1.1　偏置50
4.2　后向：误差的反向传播50
4.2.1　多层感知器算法53
4.2.2　初始化权重55
4.2.3　不同的输出激活函数56
4.2.4　顺序和批量训练57
4.2.5　局部最小57
4.2.6　利用冲量58
4.2.7　小批量和随机梯度下降58
4.2.8　其他改善方法59
4.3　实践中的MLP59
4.3.1　训练数据的量59
4.3.2　隐藏层的数目59
4.3.3　什么时候停止学习60
4.4　MLP应用示例61
4.4.1　回归问题61
4.4.2　使用MLP分类63
4.4.3　分类示例：iris数据集64
4.4.4　时间序列预测66
4.4.5　数据压缩：自动关联网络68
4.5　MLP使用指南69
4.6　反向传播的推导70
4.6.1　网络输出70
4.6.2　网络误差70
4.6.3　激活函数的要求71
4.6.4　误差的后向传播72
4.6.5　输出激活函数74
4.6.6　误差函数的另一种形式75
拓展阅读75
习题76
第5章　径向基函数和样条函数77
5.1　感受野77
5.2　径向基函数网络79
5.2.1　训练RBF网络80
5.3　插值和基函数82
5.3.1　基和基扩展83
5.3.2　三次样条函数84
5.3.3　用样条拟合数据84
5.3.4　平滑样条85
5.3.5　更高维度86
5.3.6　边界之外86
拓展阅读87
习题87
第6章　维度约简88
6.1　线性判别分析89
6.2　主成分分析91
6.2.1　PCA算法与多层感知器的关系94
6.2.2　核PCA94
6.3　因素分析96
6.4　独立成分分析97
6.5　局部线性嵌入98
6.6　ISOMAP算法100
6.6.1　多维标度法101
拓展阅读102
习题103
第7章　概率学习104
7.1　高斯混合模型104
7.1.1　期望最大化算法105
7.1.2　信息准则107
7.2　最近邻法108
7.2.1　近邻平滑109
7.2.2　有效的距离计算：KD-Tree110
7.2.3　距离度量112
拓展阅读114
习题114
第8章　支持向量机115
8.1　最优分割115
8.1.1　间隔和支持向量116
8.1.2　约束优化问题117
8.1.3　非线性可分问题的松弛变量119
8.2　核120
8.2.1　选择核121
8.2.2　示例：XOR122
8.3　支持向量机算法122
8.3.1　实现123
8.3.2　示例125
8.4　支持向量机的拓展126
8.4.1　多类分类126
8.4.2　支持向量机回归127
8.4.3　其他优势128
拓展阅读128
习题128
第9章　优化和搜索130
9.1　下山法130
9.1.1　泰勒展开132
9.2　最小二乘优化133
9.2.1　Levenberg-Marquardt算法133
9.3　共轭梯度法137
9.3.1　示例139
9.3.2　共轭梯度和MLP139
9.4　搜索：三种基本方法141
9.4.1　穷举法141
9.4.2　贪婪搜索142
9.4.3　爬山法142
9.5　开发和探索143
9.6　模拟退火法143
9.6.1　算法比较144
拓展阅读145
习题145
第10章　进化学习146
10.1　遗传算法147
10.1.1　字符串表示147
10.1.2　评价适应度148
10.1.3　种群148
10.1.4　产生后代：选择父母149
10.2　产生后代：遗传算子150
10.2.1　交叉150
10.2.2　变异151
10.2.3　精英法、比赛法和小生境151
10.3　使用遗传算法153
10.3.1　图着色153
10.3.2　间断平衡154
10.3.3　示例：背包问题155
10.3.4　示例：四峰问题155
10.3.5　遗传算法的缺陷156
10.3.6　用遗传算法训练神经网络156
10.4　遗传程序157
10.5　与采样结合的进化学习158
拓展阅读159
习题160
第11章　强化学习161
11.1　概述161
11.2　示例：迷路162
11.2.1　状态和动作空间163
11.2.2　胡萝卜和棍子：奖赏函数164
11.2.3　折扣165
11.2.4　动作选择165
11.2.5　策略166
11.3　马尔可夫决策过程166
11.3.1　马尔可夫性166
11.3.2　马尔可夫决策过程中的概率167
11.4　值167
11.5　回到迷路的示例：利用强化学习170
11.6　sarsa和Q-learning的不同171
11.7　强化学习的用处172
拓展阅读172
习题173
第12章　树的学习174
12.1　使用决策树174
12.2　构建决策树175
12.2.1　快速入门：信息论中的熵175
12.2.2　ID3176
12.2.3　基于Python的树和图的实现178
12.2.4　决策树的实现178
12.2.5　处理连续变量180
12.2.6　计算复杂度180
12.3　分类和回归树181
12.3.1　基尼不纯度181
12.3.2　树回归182
12.4　分类示例182
拓展阅读184
习题184
第13章　委员会决策：集成学习186
13.1　boosting187
13.1.1　AdaBoost187
13.1.2　掘根190
13.2　bagging190
13.2.1　subagging191
13.3　随机森林192
13.3.1　与boosting方法比较193
13.4　组合分类器的不同方法194
拓展阅读195
习题196
第14章　无监督学习197
14.1　k-means算法197
14.1.1　处理噪点200
14.1.2　k-means神经网络200
14.1.3　归一化201
14.1.4　一个更好的权重更新规则202
14.1.5　示例：iris数据203
14.1.6　使用竞争学习来聚类203
14.2　向量量化204
14.3　自组织特征映射204
14.3.1　SOM算法206
14.3.2　近邻连接207
14.3.3　自组织208
14.3.4　网络维度和边界条件208
14.3.5　SOM应用示例209
拓展阅读211
习题211
第15章　马尔可夫链蒙特卡罗方法213
15.1　采样213
15.1.1　随机数213
15.1.2　高斯随机数214
15.2　蒙特卡罗216
15.3　建议分布216
15.4　马尔可夫链蒙特卡罗219
15.4.1　马尔可夫链219
15.4.2　Metropolis-Hastings算法220
15.4.3　模拟退火222
15.4.4　Gibbs采样223
拓展阅读224
习题225
第16章　图模型226
16.1　贝叶斯网络227
16.1.1　示例：考试恐惧227
16.1.2　近似推断230
16.1.3　创建贝叶斯网络232
16.2　马尔可夫随机场233
16.3　隐马尔可夫模型234
16.3.1　前向算法236
16.3.2　Viterbi算法238
16.3.3　Baum-Welch或前向后向算法239
16.4　跟踪方法242
16.4.1　卡尔曼滤波242
16.4.2　粒子滤波247
拓展阅读249
习题250
第17章　对称权重与深度置信网络251
17.1　积极学习:Hopfield网络252
17.1.1　联想记忆252
17.1.2　实现联想记忆252
17.1.3　能量函数255
17.1.4　Hopfield网络的容量256
17.1.5　连续Hopfield网络257
17.2　随机神经元：玻尔兹曼机257
17.2.1　受限玻尔兹曼机259
17.2.2　CD算法的推导262
17.2.3　监督学习265
17.2.4　RBM作为定向置信网络267
17.3　深度学习268
17.3.1　深度置信网络270
拓展阅读273
习题273
第18章　高斯过程274
18.1　高斯过程回归275
18.1.1　添加噪声276
18.1.2　高斯过程回归的实现（一）278
18.1.3　学习参数279
18.1.4　高斯过程回归的实现（二）280
18.1.5　选择（一组）协方差函数282
18.2　高斯过程分类282
18.2.1　拉普拉斯近似283
18.2.2　计算后验283
18.2.3　高斯过程分类的实现285
拓展阅读286
习题287
附录　Python入门288