机器学习导论（原书第2版）

关于本书
本次修订包含了3章全新的内容，它们是工业界有关机器学习实际应用的重要议题。这3章分别涉及了多标签领域、无监督学习及其在深度学习中的应用、归纳的逻辑方法以及归纳逻辑编程。许多章节有所扩展，内容的展现方式也得到了增强。本书还包含了许多新的习题、已解决的实例、启发思维的实验和需要独立完成的编程作业。

本书特色
通过提供实用的建议、采用直观的例子和对相关应用进行有意义的探讨，本书以一种易于理解的方式介绍了机器学习的一些基础性概念。主要内容包括贝叶斯分类器、近邻分类器、线性与多项式分类器、决策树、神经网络和支持向量机。本书后面几章展示了如何以“提升（Boosting）”的方式将这些简单的工具组织起来、怎样将它们应用于更加复杂的领域以及如何处理各种高难度的实际问题。有一章还专门介绍了非常流行的遗传算法。

本书是一本浅显易懂的机器学习入门教材，它以理论与实际相结合的方式全面地涵盖了主流的机器学习理论与技术。全书共17章，介绍了贝叶斯分类器、近邻分类器、线性与多项式分类器、人工神经网络、决策树、基于规则集的分类器、遗传算法等经典的机器学习方法，对计算学习理论、性能评估、统计显著性等进行了讨论。讲解了集成学习、多标签学习、无监督学习和强化学习等重要的机器学习领域。本书还通过大量的应用实例，阐述了机器学习技术的许多应用技巧。每章结尾对相关机器学习工作都进行了历史简评，并附有练习、思考题和上机实验。

Miroslav Kubat 美国迈阿密大学教授，从事机器学习教学和研究超过25年。他已发表100余篇经过同行评审的论文，与人合编了两本著作，是近60个会议和研讨会的委员会委员，并担任3本学术刊物的编委。他在两个方面的前沿研究上得到了广泛赞誉：时变概念的归纳学习和在非平衡训练集上的学习。此外，在多标签样例上的归纳学习、层次组织的类别上的归纳学习、遗传算法、神经网络的初始化等问题上，他也做出了很多贡献。

译者序
原书前言
第 1章　一个简单的机器学习任务 //1
1.1　训练集和分类器 //1
1.2　题外话：爬山搜索 //4
1.3　机器学习中的爬山法 //6
1.4　分类器的性能 //8
1.5　可用数据的困难 //9
1.6　小结和历史简评 //11
1.7　巩固知识 //11
第 2章　概率：贝叶斯分类器 //14
2.1　单属性的情况 //14
2.2　离散属性值的向量 //17
2.3　稀少事件的概率：利用专家的直觉 //20
2.4　如何处理连续属性 //23
2.5　高斯钟形函数：一个标准的 pdf //24
2.6　用高斯函数的集合近似 pdf //26
2.7　小结和历史简评 //30
2.8　巩固知识 //30
第 3章　相似性：近邻分类器 //32
3.1　k近邻法则 //32
3.2　度量相似性 //34
3.3　不相关属性与尺度缩放问题 //36
3.4　性能方面的考虑 //39
3.5　加权近邻 //41 3.6　移除危险的样例 //42
3.7　移除多余的样例 //44
3.8　小结和历史简评 //46
3.9　巩固知识 //46
第 4章　类间边界：线性和多项式分类器 //49
4.1　本质 //49
4.2　加法规则：感知机学习 //51
4.3　乘法规则： WINNOW //55
4.4　多于两个类的域 //58
4.5　多项式分类器 //60
4.6　多项式分类器的特殊方面 //62
4.7　数值域和 SVM //63
4.8　小结和历史简评 //65
4.9　巩固知识 //66
第 5章　人工神经网络 //69
5.1　作为分类器的多层感知机 //69
5.2　神经网络的误差 //72
5.3　误差的反向传播 //73
5.4　多层感知机的特殊方面 //77
5.5　结构问题 //79
5.6　RBF网络 //81
5.7　小结和历史简评 //83
5.8　巩固知识 //84
第 6章　决策树 //86
6.1　作为分类器的决策树 //86
6.2　决策树的归纳学习 //89
6.3　一个属性承载的信息 //91
6.4　数值属性的二元划分 //94
6.5　剪枝 //96
6.6　将决策树转换为规则 //99
6.7　小结和历史简评 //101
6.8　巩固知识 //101
第 7章　计算学习理论 //104
7.1　PAC学习 //104
7.2　PAC可学习性的实例 //106
7.3　一些实践和理论结果 //108
7.4　VC维与可学习性 //110
7.5　小结和历史简评 //112
7.6　巩固知识 //112
第 8章　典型案例 //114
8.1　字符识别 //114
8.2　溢油检测 //117
8.3　睡眠分类 //119
8.4　脑机界面 //121
8.5　医疗诊断 //124
8.6　文本分类 //126
8.7　小结和历史简评 //127
8.8　巩固知识 //128
第 9章　投票组合简介 //130
9.1　“Bagging”方法 //130
9.2　“Schapire’s Boosting”方法 //132
9.3　“Adaboost”方法： “Boosting”方法的实用版本 //134
9.4　“Boosting”方法的变种 //138
9.5　该方法的计算优势 //139
9.6　小结和历史简评 //141
9.7　巩固知识 //141
第 10章　了解一些实践知识 //143
10.1　学习器的偏好 //143
10.2　不平衡训练集 //145
10.3　语境相关域 //148
10.4　未知属性值 //150
10.5　属性选择 //152
10.6　杂项 //154
10.7　小结和历史简评 //155
10.8　巩固知识 //156
第 11章　性能评估 //158
11.1　基本性能标准 //158
11.2　精度和查全率 //160
11.3　测量性能的其他方法 //163
11.4　学习曲线和计算开销 //166
11.5　实验评估的方法 //167
11.6　小结和历史简评 //169
11.7　巩固知识 //170
第 12章　统计显著性 //173
12.1　总体抽样 //173
12.2　从正态分布中获益 //176
12.3　置信区间 //178
12.4　一个分类器的统计评价 //180
12.5　另外一种统计评价 //182
12.6　机器学习技术的比较 //182
12.7　小结和历史简评 //184
12.8　巩固知识 //185
第 13章　多标签学习 //186
13.1　经典机器学习框架下的多标签
问题 //186
13.2　单独处理每类数据的方法：二元相关法 //188
13.3　分类器链 //190
13.4　另一种方法：层叠算法 //191
13.5　层次有序类的简介 //192
13.6　类聚合 //194
13.7　分类器性能的评价标准 //196
13.8　小结和历史简评 //198
13.9　巩固知识 //199
第 14章　无监督学习 //202
14.1　聚类分析 //202
14.2　简单算法： k均值 //204
14.3　k均值的高级版 //207
14.4　分层聚集 //209
14.5　自组织特征映射：简介 //211
14.6　一些重要的细节 //213
14.7　为什么要特征映射 //214
14.8　小结和历史简评 //215
14.9　巩固知识 //216
第 15章　规则集形式的分类器 //218
15.1　由规则描述的类别 //218
15.2　通过序列覆盖归纳规则集 //220
15.3　谓词与循环 //222
15.4　更多高级的搜索算子 //224
15.5　小结和历史简评 //225
15.6　巩固知识 //225
第 16章　遗传算法 //227
16.1　基本遗传算法 //227
16.2　个体模块的实现 //229
16.3　为什么能起作用 //231
16.4　过早退化的危险 //233
16.5　其他遗传算子 //234
16.6　高级版本 //235
16.7　kNN分类器的选择 //237
16.8　小结和历史简评 //239
16.9　巩固知识 //240
第 17章　强化学习 //241
17.1　如何选出奖励的动作 //241
17.2　游戏的状态

机器学习已走向成熟。如果读者觉得只是说说而已，请允许我做些解释。
人们希望机器某一天能够自己学习，这个梦想几乎在计算机出现时就有了，也许更早。不过，长久以来，这仅仅是一个想象而已。 Rosenblatt感知机的提出曾经掀起过一股热潮，但是现在回想起来，这股热潮没能持续很长的时间。至于接下来的尝试，使情况发展得更糕，这个领域甚至没有再引起人们的注意，长期被忽视，无法取得重大突破，也没有这一类的软件公司，后续研究寥寥无几并且得到的资金支持也不多。这个阶段，机器学习一直不被看好，像进入休眠一样，在其他成功学科的阴影里生存。
接下来一切都改变了。
一群有识之士指出，在 20世纪 70年代的人工智能领域，基于知识的系统曾经风靡一时，但它们有一个弱点：“知识”从哪里来？当时主流的观点认为，应该让工程师和领域专家合作，用 if-then的形式表示出来。但是实际情况差强人意，专家们发现很难把掌握的知识表达给工程师。反过来，工程师也不知道该问什么问题以及如何表示答案。尽管有几个广为人知的成功案例，但是其他大多数研究都试图建立知识库，并且成千上万的规则令人沮丧。
这些有识之士主张简单和直接的操作。如果难以准确地告诉机器如何处理某个问题，为什么不间接地给出指令，让计算机通过例子来学习—对，就是学习—所需要的技能？
当然，这必须要有能够进行学习的算法才有意义，这是主要的困难。结果发现无论是 Rosenblatt感知机还是后来出现的技术都不太管用。然而机器学习技术的缺乏不是障碍，相反是一个挑战，并激发出了很多绝妙的点子。其中使计算机有学习能力这个想法开创了一个激动人心的新领域，并引起了世人的关注。
这一想法在 1983年爆发了。一卷很厚的论文集——《机器学习：人工智能的方法》提出了各种方法来解决这个巨大的问题。在它的影响下，几乎一夜之间一个新的学科诞生了。 3年后，后续著作一本接一本地出现。相关学术刊物也很快被创立，有着巨大影响力的年度学术会议相继召开。几十或许是几百篇博士论文完成并通过答辩。
早期阶段，问题不仅是如何学习，而是学什么和为什么学。这段充满创造力的岁月让人难以忘怀。有些遗憾的是很多非常好的想法后来被放弃了。实用主义占了上风，资源都被投向那些有希望的方向。经过一段时间的发展，具体研究基本成形：知识系统 if-then规则的归纳、分类归纳、程序基于经验来提高技能、 Prolog程序自动调优以及其他方面。相关的研究方向非常多，一些知名学者希望通过写书引领未来的发展，这其中有些人做得很成功。
机器学习发展的一个重要的转折点是 Tom Mitchell的传奇教科书。该书向博士生和科学家们总结了该领域的发展现状，慢慢地大学也用这本书作为研究生的教材。同时，研究方法也变得更加系统化。大量机器学习测试库被建立起来，用于比较性能或者学习算法的优劣。统计评估方法也被广泛地使用在评估过程中。相关流行程序的公开版本很容易获得，从事这个学科的人数增至数千甚至更多。
现在，到了很多大学都为本科生开设机器学习课程的阶段，通常这些课程需要不同类型的教材。除了掌握基本技术以外，学生还需要了解不同方法的优点和缺点，以及不同情况下每种方法的独特之处。重要的是，他们需要理解在特定情况下，哪些技术是可行的，哪些是不可行的。只有这样才能在解决具体问题时做出正确的选择。一本教材除了满足以上各项要求外，还应该少讲一些数学概念，多包括一些实用的建议。
关于教材，还要考虑材料的多少、结构以及风格，以便能够支持一个学期的导论课程。
个问题是材料的选择。当高科技公司准备成立机器学习研究团队时，大学就要向学生传授相关的知识和技能，以及对行业当前需求的理解。为此，本书重点介绍了贝叶斯分类器、近邻分类器、线性和多项式分类器、决策树、神经网络的基础以及提升（Boosting）算法的原理。本书很大篇幅用来描述具体应用的典型特征。在现实中，当把基本技术用于真正有难度的任务上时，它们的表现可能和老师在课上的简单演示不完全一样。学生应对此有所了解。
本书共包括 17章，每章覆盖一个专题。各章分成很多节，每节介绍一个关键问题。建议学生在做完每一节后面的 2~4个问题后再学习下一节。这些问题用来帮助检查对学习材料的掌握情况。如果不会做这些题，有必要重新阅读相关内容。
俗话说熟能生巧。每章结尾安排了必要的练习用于实际操作。如果接下来的思考、实验能够全部完成，将有助于更深入理解所学内容的各个方面。不过这些实验难度较大，只有付出很大努力才能获得正确的理解。所学的知识在上机实验中可被进一步巩固。编程对于学习同样重要。现在，人们都习惯从网上下载所需的程序，这是捷径，但本书不建议这样做。因为只有强迫自己实现了程序的全部细节，才能领会本书机器学习技术的精妙之处。