《机器学习导论.pdf》由会员分享，可在线阅读，更多相关《机器学习导论.pdf（331页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 ? ? ? ? ? ? ? ? ? ? ? ? ? “ “ ? ? ? ? ? ? ? ? ? ? ? ? 、 ? ? 、 ? “ ? ? ? ? “ ? ? ? ? ? ? ? ? ? ? ? ? 、 ? ? ? 、 ? ? ? ? ? ? “ ? ? ? ? ? ? ? ? ? “ ? ? ? “ ? ? ? “ ? ? 、 ? ? ? ? ? ? 、 ? ? ? ? ? ? 。 ? ? ? “ ? 、 ? ? ? ? 。 、 ? ? ? ? “ ” ? ? ? ? ? ? ? ? ” ? ? ? ? ? ? ? ? ? ? ? ? 、 ? “ ? 、 ? ? 。 ? ? ? ? ? ?
2、 ? ? ? ? 、 ? ? ? ? ? ? ? ? ? ? ” ? ? ? ? ? ? ? ? ? ? ? 、 ? “ ? 、 ? ? 。 ? ? ? ? ? ? ? ? ? ? ” 、 ? ? ?“ ? ? ” ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 、 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ” ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
3、“ ? 、 ? ? ? ? 。 、 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? “ ? ? ? “ ? ? ? “ ? ? 、 ? ? ? ? ? ? 、 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
4、? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ” 。 “ “ ? “ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 。 “ ? “
5、? ? ? ” ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ” ? ? ? ? “ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? “ ? ? ? ? 。 “ “ ? ? “ ? 献给我的妻子， 瓦卢卡 （Verunka） 推荐序 机器学习是人工智能领域的一个重要分支， 其研究涉及代数、 几何、 概率统 计、 优化、 泛函分析、 图论、 信息论、 算法、 认知计算等多个学科的知识， 其应 用不仅仅限于模式识别、 计算机视觉、 数据挖掘、 生物信息学、 智能控制等科学 和工程领域， 甚至在社会科学领域的研究中
6、也有应用， 如管理学、 经济学和历史 学等。 目前， 随着计算机科学和智能科学技术的进步， 机器学习得到了快速发展， 其方法被广泛应用到了各个领域。 尤其是近些年， 深度学习方法快速发展并在多 个领域展示出优异性能， 使机器学习和整个人工智能领域受到极大的关注。 机器学习是基于已有数据、 知识或经验来设计模型或发现新知识的一个研究领 域。 20 世纪50 70 年代是机器学习研究的初期， 人们基于逻辑知识表示试图给机器 赋予逻辑推理能力， 取得了很多振奋人心的成果； 20 世纪80 年代， 专家系统受到高 度重视， 为专家系统获取知识成为一个重要方向。 20 世纪80 年代中后期， 人工神经
7、网络由于误差反向传播 （BP） 算法的重新提出和广泛应用而形成一股热潮， 但其地 位在90 年代后期被以支持向量机为核心的统计学习理论所取代。 20 世纪 90 年代以 后， 受重视的机器学习方法还有集成学习、 概率图模型、 半监督学习、 迁移学习等。 2006 年， 以加拿大多伦多大学的 G. Hinton 教授为代表的几位研究人员在深度学习 方面取得巨大突破， 在 Google、 Microsoft、 Facebook 等科技公司的推动下， 深度学习 借助于大数据和高性能计算的有利条件得到了广泛应用和高度关注。 目前， 搜索引 擎、 机器人、 无人驾驶汽车等高科技产品都依赖于机器学习技术。
8、 机器学习， 特别 是深度学习， 在语音识别、 人脸识别、 围棋、 游戏等方面已经超过了人类水平， 可 以想象机器学习与人类的生产、 生活之间的关系将会越来越紧密。 过去几十年， 机器学习领域也出现了一些经典的著作或教材。 1983 年， R. Michalski、 J. Carbonell 和 T. Mitchell 主编的 机器学习： 一种人工智能方法 一 书出版， 标志着机器学习成为人工智能的一个独立研究领域。Machine Learning 期刊创刊于 1986 年， 目前依然是机器学习领域的顶级期刊。 1990 年， J. Carbonell 主编的 机器学习： 范式与方法 对归纳学
9、习、 基于解释的学习、 遗传算法和连 接主义学习等机器学习范式及方法进行了深入探讨。 T. Mitchell 于 1997 年出版的 机器学习 是一本经典的机器学习教材， 其中文版已于 2003 年由机械工业出版 社出版， 但因为出版年限较早， 许多内容已没有时效性。 1998 年， V. Vapnik 出 版的 统计学习理论 是一本完整阐述统计机器学习思想的名著。 2001 年出版、 2009 年再版的 统计学习基础： 数据挖掘， 推理和预测 是美国斯坦福大学教授 T. Hastie， R. Tibshirani 和 J. Friedman 的一部力作， 其中对最为流行的机器学习 方法进行了
10、全面而深入的介绍， 因其严谨的数学推导， 该书不失为机器学习研究 进阶的很好的读物。 E. Alpaydin 所著的 机器学习导论 出版于 2004 年并于 2010 年再版， 书中对基础的机器学习方法进行了介绍， 是一本机器学习入门的很 好的教材。 C. Bishop 所著的 模式识别与机器学习 和 K. Murphy 所著的 机器 学习： 一个概率的视角 分别于 2006 年和 2012 年出版， 两本书都从概率的角度 全面而细致地介绍了许多经典的机器学习模型。 C. Bishop 的 模式识别与机器学 习 可帮助读者打下坚实的机器学习基础， 而 K. Murphy 的书则相对介绍了更多
11、较新的机器学习算法， 甚至有一章专门介绍了深度学习方法。 2012 年， 李航老师 出版了 统计学习方法， 2016 年， 周志华老师出版了 机器学习。 这两本书 中， 统计学习方法 主要集中于几种重要机器学习模型的介绍， 而 机器学习 内容相对更加全面， 深入浅出， 堪称机器学习的中文经典著作。 相对于以上这些 机器学习书籍， M. Kubat 所写的这本 机器学习导论 更像是一本科普性质的读 物， 作者尽量避开复杂的数学公式， 用生动形象的方式介绍机器学习算法， 而且 本书篇幅适当， 又涵盖了几乎所有基本的机器学习方法， 使得本书不仅适合作为 本科学生机器学习课程的教材， 也适合于想了解机
12、器学习入门知识的普通读者。 本书的译者都是工作在机器学习教学与研究第一线的年轻老师， 其中仲国强 副教授过去是我的博士研究生， 在模式识别和机器学习领域都有很扎实的研究基 础。 相信本书的中译本对于国内机器学习的教学和研究都会有所裨益， 也为更多 的人， 尤其是初学者了解机器学习打开一扇门。 中国科学院自动化研究所副所长、 模式识别国家重点实验室主任 刘成林 前 言 目前， 机器学习慢慢走向成熟。 你可能觉得这只是老生常谈， 请让我做一个 详细说明。 人们希望机器某一天能够自己学习， 这个梦想几乎在计算机出现时就有了， 也许更早。 不过， 长久以来， 这仅仅是一个想象而已。 罗森布拉特 （Ro
13、senblatt） 感知器的提出曾经掀起过一股热潮， 但是现在回想起来， 这股热潮没能持续很长 的时间。 至于接下来的尝试， 使情况发展得更糟糕， 这个领域甚至没有再引起人 们的注意， 长期被忽视， 因而无法取得重大突破， 也没有这一类的软件公司， 后 续研究寥寥无几且得到的资金支持也不多。 这个阶段， 机器学习一直不被看好， 像进入休眠期一样， 在其他成功学科的阴影里生存。 然而， 接下来发生的一切使这些颓势彻底改变了。 一群有识之士指出， 在 20 世纪 70 年代的人工智能领域， 基于知识的系统曾 经风靡一时， 但它们有一个弱点： “知识” 从哪里来？ 当时主流的观点认为， 应 该让工程
14、师和领域专家合作， 用 if-then 的形式表示出来。 但是实际情况差强人意， 专家们发现很难把掌握的知识表达给工程师。 反过来， 工程师也不知道该问什么 问题以及如何表示答案。 尽管有几个广为人知的成功案例， 但是其他大多数研究 都试图建立知识库， 并且成千上万的规则令人沮丧。 这些有识之士主张简单和直接的操作。 如果难以准确地告诉机器如何处理某 个问题， 那么为什么不间接地给出指令， 通过例子展示所需要的技能， 计算机将 通过这些例子来学习！ 当然， 这必须要有能够进行学习的算法才有意义， 这也是困难所在。 无论是 罗森布拉特的感知器还是后来出现的技术都不太管用。 然而， 机器学习在技术
15、方 面的缺乏算不上是障碍， 相反是一个挑战， 并激发出了很多绝妙的点子。 其中， 使计算机有学习能力这个想法开创了一个激动人心的新领域， 并引起了世人的 关注。 这一想法在 1983 年爆发了。 一卷很厚的论文集 机器学习： 人工智能的 米切尔斯基 （R. Michalski）， 卡波内尔 （J. Carbonell）， 米切尔 （T. Mitchell） 编辑。 T. Mitchell. Machine Learning M. New YorkV McGraw-Hill， 1997. 方法 中提出了很多各式各样的方法来求解这个谜题。 在它的影响下， 几乎一夜 之间一个新的学科诞生了。 3 年
16、后， 后续著作一本接一本地出现。 相关学术刊物 也很快被创立， 有着巨大影响力的年度学术会议相继召开。 几十、 或许是几百篇 博士论文完成并通过答辩。 早期阶段， 问题不仅是如何学习， 而是学什么和为什么学。 这段充满创造力 的岁月让人难以忘怀， 唯一有些遗憾的是很多非常好的想法后来被放弃了。 实用 主义占了上风， 资源都被投向那些最有希望的方向。 经过一段时间的发展， 具体 研究基本成形： 知识系统 if-then 规则的归纳， 分类归纳， 程序基于经验来提高技 能， Prolog 程序自动调优， 以及其他方面。 相关的研究方向非常多， 一些知名学 者希望通过写书来引领未来的发展， 这其中有
17、些人做得很成功。 机器学习发展的一个重要的转折点是汤姆米切尔 （Tom Mitchell） 的传奇教 科书。 该书向博士生和科学家们总结了该领域的发展现状， 慢慢地大学也用这 本书作为研究生的教材。 同时， 研究方法也变得更加系统化。 大量机器学习测试 库被建立起来， 用于比较性能或者学习算法的优劣。 统计评估方法也被广泛地使 用在评估过程中。 相关流行程序的公开版本很容易获得， 从事这个学科的人数增 至数千， 甚至更多。 现在， 到了很多大学都为本科生开设机器学习课程的阶段。 通常这些课程需 要不同类型的教材。 除了掌握基本技术以外， 学生还需要了解不同方法的优点和 缺点， 以及不同情况下每
18、种方法的独特之处。 最重要的是， 他们需要理解在特定 情况下， 哪些技术是可行的， 哪些是不可行的。 只有这样才能在解决具体问题时 做出正确的选择。 一本教材除了满足以上的各项要求外， 还应该介绍一些数学概 念， 多包括一些实用的建议。 关于教材， 还要考虑材料的多少、 结构以及风格， 以便能够支持一个学期的 导论课程。 第一个问题是材料的选择。 当高科技公司准备成立机器学习研究团队时， 大 学就要向学生传授相应的知识和技能， 以及对有关行业需求的理解。 出于这个原 因， 本书重点介绍了贝叶斯分类器， 最近邻分类器， 线性和多项式分类器， 决策 树， 神经网络的基础， 以及提升 （Boosti
19、ng） 算法的原理。 本书用很大篇幅来描述 具体应用的典型特征。 在现实中， 当面对有一定难度的任务时， 一些基本方法和 老师在实验环境下演示的结果可能不完全一样。 因此在学习过程中， 学生必须知 道每种方法会发生什么。 本书共包括 14 章， 每章覆盖一个专题。 各章分成很多个小节， 每节介绍一个 关键问题。 建议学生在做完每一节后面的 2 4 个 “控制问题” 后再学习下一节。 这些问题用来帮助检查学生对学习材料的掌握情况。 如果不会做这些题， 则有必 要重新阅读相关内容。 俗话说， 实践出真知。 每章结尾安排了必要的练习用于实际操作。 如果接下 来的思考实验能够全部完成， 将有助于更深入
20、地理解所学内容的各个方面。 不过 这些实验难度较大， 只有付出很大努力才能获得正确的答案。 所学的知识在上机 实验中可被进一步巩固。 编程对于学习同样也很重要。 现在， 人们都习惯从网上 下载所需的程序， 这是捷径， 但本书不建议这样做， 因为只有具体实现了程序的 全部细节， 才能领会机器学习技术的精妙之处。 目 录 推荐序 前言 第 1 章 一个简单的机器学习任务 / / 001 1. 1 训练集和分类器 / / 002 1. 2 一点题外话： 爬山搜索 / / 005 1. 3 机器学习中的爬山法 / / 009 1. 4 分类器的性能 / / 012 1. 5 可用数据的困难 / / 0
21、14 1. 6 总结和历史简评 / / 016 1. 7 巩固你的知识 / / 017 第 2 章 概率： 贝叶斯分类器 / / 021 2. 1 单属性的情况 / / 022 2. 2 离散属性值的向量 / / 026 2. 3 稀少事件的概率： 利用专家的直觉 / / 030 2. 4 如何处理连续属性 / / 032 2. 5 高斯钟形函数： 一个标准的概率密度函数 / / 036 2. 6 用高斯函数的集合近似概率密度函数 / / 037 2. 7 总结和历史简评 / / 042 2. 8 巩固你的知识 / / 043 第 3 章 相似性： 最近邻分类器 / / 047 3. 1 k
22、近邻法则 / / 048 3. 2 度量相似性 / / 051 3. 3 不相关属性与尺度缩放问题 / / 054 3. 4 性能方面的考虑 / / 057 3. 5 加权最近邻 / / 060 3. 6 移除危险的样例 / / 062 3. 7 移除多余的样例 / / 064 3. 8 总结和历史简评 / / 066 3. 9 巩固你的知识 / / 067 第 4 章 类间边界： 线性和多项式分类器 / / 071 4. 1 本质 / / 072 4. 2 加法规则： 感知机学习 / / 075 4. 3 乘法规则： WINNOW / / 081 4. 4 多于两个类的域 / / 084 4
23、. 5 多项式分类器 / / 086 4. 6 多项式分类器的特殊方面 / / 089 4. 7 数值域和支持向量机 / / 091 4. 8 总结和历史简评 / / 094 4. 9 巩固你的知识 / / 095 第 5 章 人工神经网络 / / 099 5. 1 作为分类器的多层感知机 / / 100 5. 2 神经网络的误差 / / 103 5. 3 误差的反向传播 / / 105 5. 4 多层感知机的特殊方面 / / 110 5. 5 结构问题 / / 113 5. 6 径向基函数网络 / / 115 5. 7 总结和历史简评 / / 117 5. 8 巩固你的知识 / / 119
24、第 6 章 决策树 / / 121 6. 1 作为分类器的决策树 / / 122 6. 2 决策树的归纳学习 / / 126 6. 3 一个属性承载了多少信息 / / 129 6. 4 数值属性的二元划分 / / 133 6. 5 剪枝 / / 135 6. 6 将决策树转换为规则 / / 140 6. 7 总结和历史简评 / / 143 6. 8 巩固你的知识 / / 144 第 7 章 计算学习理论 / / 147 7. 1 PAC 学习 / / 148 7. 2 PAC 可学习性的实例 / / 151 7. 3 一些实践和理论结果 / / 154 7. 4 VC 维与可学习性 / / 1
25、56 7. 5 总结和历史简评 / / 159 7. 6 巩固你的知识 / / 160 第 8 章 几个有帮助的案例 / / 163 8. 1 字符识别 / / 164 8. 2 溢油检测 / / 168 8. 3 睡眠分类 / / 172 8. 4 脑机界面 / / 175 8. 5 医疗诊断 / / 178 8. 6 文本分类 / / 181 8. 7 总结和历史简评 / / 183 8. 8 巩固你的知识 / / 184 第 9 章 投票组合简介 / / 187 9. 1 “装袋” 方法 （Bagging） / / 188 9. 2 夏皮尔提升 （Schapires Boosting）
26、/ / 190 9. 3 Adaboost Boosting 的实用版本 / / 194 9. 4 Boosting 方法的变种 / / 198 9. 5 Boosting 方法的计算优势 / / 200 9. 6 总结和历史简评 / / 202 9. 7 巩固你的知识 / / 203 第 10 章 了解一些实践知识 / / 207 10. 1 学习器的偏好 / / 208 10. 2 不平衡训练集 / / 211 10. 3 语境相关域 / / 215 10. 4 未知属性值 / / 219 10. 5 属性选择 / / 221 10. 6 杂项 / / 223 10. 7 总结和历史简评
27、/ / 226 10. 8 巩固你的知识 / / 227 第 11 章 性能评估 / / 231 11. 1 基本性能标准 / / 232 11. 2 精度和查全率 / / 235 11. 3 测量性能的其他方法 / / 240 11. 4 多标签域内的性能 / / 243 11. 5 学习曲线和计算开销 / / 244 11. 6 实验评估的方法 / / 246 11. 7 总结和历史简评 / / 249 11. 8 巩固你的知识 / / 250 第 12 章 统计显著性 / / 253 12. 1 总体抽样 / / 254 12. 2 从正态分布中获益 / / 258 12. 3 置信区间
28、 / / 261 12. 4 一个分类器的统计评价 / / 264 12. 5 另外一种统计评价 / / 266 12. 6 机器学习技术的比较 / / 268 12. 7 总结和历史简评 / / 270 12. 8 巩固你的知识 / / 271 第 13 章 遗传算法 / / 273 13. 1 基本遗传算法 / / 274 13. 2 单个模块的实现 / / 276 13. 3 为什么能起作用 / / 279 13. 4 过早退化的危险 / / 282 13. 5 其他遗传算子 / / 284 13. 6 高级版本 / / 286 13. 7 k-NN 分类器的选择 / / 289 13.
29、 8 总结和历史简评 / / 292 13. 9 巩固你的知识 / / 292 第 14 章 增强学习 / / 295 14. 1 如何选出最高奖励的动作 / / 296 14. 2 游戏的状态和动作 / / 299 14. 3 SARSA 方法 / / 302 14. 4 总结和历史简评 / / 303 14. 5 巩固你的知识 / / 303 参考文献/ / 305 第 1 章 一个简单的机器学习任务 001 机器学习导论 第 1 章 一个简单的机器学习任务 002 机器学习导论 你会发现精确地描述你母亲的相貌， 让朋友能在超市里认出她， 是很难的。 但如果你给他看几张你母亲的照片， 他就
30、能立刻找出所需要的特征。 这就是人们 常说的， 一张图片， 也就是一个样例， 胜过千言万语。 这就是我们希望用技术去实现的。 当不能足够精确地定义某些事物或概念时， 我们希望以样例的方式把它们传输给机器。 然而， 计算机必须能将样例转换成知 识才能奏效。 所以， 我们的兴趣在于机器学习 （machine learning） 的算法和技术， 也是这本书的主题。 第 1 章将任务表示为一个搜索问题， 并介绍了爬山搜索算法。 爬山搜索算法 不仅是我们解决机器学习任务的初步尝试， 而且也为解决后面几章中的一些辅助 问题提供便利的工具。 在这些基础上， 我们将继续探索一些能使学习过程苦中带 乐的问题，
31、包括性能标准、 实验方法以及其他方面。 1. 1 训练集和分类器 让我们首先介绍一些贯穿全书的问题和基本概念。 预分类训练样例。 图 1. 1 展示了 6 种乔尼 （Johnny） 喜欢和不喜欢的派。 这 些正例 （positive examples） 和负例 （negative examples） 的基本概念构成了一个训 练集 （training set）， 并以此由机器归纳出一个分类器 （classifier） 一种能将 今后任何的派归为正、 负两个类别之一的算法。 图 1. 1 一个简单的机器学习任务： 归纳学习出一个能将今后任何派归类为正 例和负例的分类器， 如归纳学习一个 “乔尼喜欢
32、的派” 的分类器 第 1 章 一个简单的机器学习任务 003 毫无疑问， 分类的数量可以更多。 例如， 一个分类器要有春、 夏、 秋、 冬 4 个分类， 才能辨别出一张风景照拍摄于哪个季节。 iPad 上识别手写字迹的软件则 至少需要 36 个分类： 26 个字母和 10 个阿拉伯数字， 文件分类系统可以识别成百 上千种不同的主题。 我们之所以只选择二分类域， 只是因为它简单。 属性向量。 为将训练样例 （example） 发送给机器， 我们必须用恰当的方法描 述它们。 最常见的方法是使用所谓的属性 （attributes）。 在 “派” 问题域中， 共有 5 种属性： 形状 （shape），
33、 取值包括圆形 （circle）、 三角形 （triangle） 和方形 （square）； 外壳尺寸 （crust size）， 取值包括厚 （thick） 和薄 （thin）； 外壳色度 （curst shade）， 取值包括白色 （white）、 灰色 （gray） 和深色 （dark）； 馅料尺寸 （filling size）， 取值包括厚 （thick） 和薄 （thin）； 馅料色度 （filling shade）， 取值 包括白色 （white）、 灰色 （gray） 和深色 （dark）。 表 1. 1 指定了图 1. 1 中 12 个训 练样例的属性值。 例如， 图1. 1
34、中左上角的派 （在表1. 1 中称之为 ex1） 可用下列 组合属性描述： （shape = circle）AND（crust - size = thick）AND（crust - shade = gray） AND（filling - size = thick）AND（filling - shade = dark） 表 1. 1 以矩阵形式表示的 12 个训练样例 样例 形状 （shape） 外壳 （crust）馅料 （filling） 尺寸 （size） 色度 （shade） 尺寸 （size） 色度 （shade） 类别 ex1circlethickgraythickdarkpos ex
35、2circlethickwhitethickdarkpos ex3trianglethickdarkthickgraypos ex4circlethinwhitethindarkpos ex5squarethickdarkthinwhitepos ex6circlethickwhitethindarkpos ex7circlethickgraythickwhiteneg ex8squarethickwhitethickgrayneg ex9trianglethingraythindarkneg 004 机器学习导论 （续） 样例 形状 （shape） 外壳 （crust）馅料 （filling
36、） 尺寸 （size） 色度 （shade） 尺寸 （size） 色度 （shade） 类别 ex10circlethickdarkthickwhiteneg ex11squarethickwhitethickdarkneg ex12trianglethickwhitethickgrayneg 归纳分类器。 我们用训练集组成的输入来归纳分类器， 但这是什么形式的分 类器呢？ 假定我们让它符合布尔函数的形式， 正例为真 （true）， 负例为假 （false）。 当用训练集来检查表达式 （shape = circle） AND （filling-shade = dark） 时， 我们会发现， 所
37、有的负例值都为假： 因为在负例中， 当样例形状为圆形时， 没有灰色的馅。 然而在正例中， 有 4 个为真， 其余两个为假。 这说明分类器犯了 两个我们可能无法容忍的错误， 从而我们猜测存在更好的解决办法。 事实上， 读者很容易证明下面的表达式在整个训练集中都不会出错： （shape = circle）AND（filling - shade = dark）OR NOT（shape = circle）AND（crust - shade = dark） 蛮力方法的问题。 机器发现这种分类器会如何？ 蛮力 （计算机最擅长的事 情） 在这里行不通。 设想一下， 用 “派” 问题中特定的属性可以识别出多少
38、个不 同的样例？ 对于 3 种不同的形状， 每种形状就有两个不同的外壳尺寸可供选择， 那么其组合数量为 3 2 =6。 对这 6 种组合的每一种的下一个属性， 即外壳色度， 有 3 种不同的值， 此时组合数量变为 3 2 3 =18。 将所有属性以此类推， 会发现 样例空间包含 3 2 3 2 3 =108 个不同的样例。 这些样例的每个子集 一共有 2108个子集！ 可能包含了代表某些人 “好的 派” 概念的正例列表， 且每个子集至少由一个布尔表达式来描述。 显而易见， 用 训练集来检验每一个分类器是天方夜谭。 人工方法及搜索。 虽然我们不确定如何创造出一个归纳分类器算法， 但是可 以尝试
39、“手动地” 发明一种分类器， 并通过古老但好用的纸笔测试法来寻找灵 第 1 章 一个简单的机器学习任务 005 感。 在这个过程中， 我们先从试探性的初始版本入手， 例如， shape = circle。 用训 练集检验该表达式后， 我们发现 4 个正例和两个负例为真。 显然， 分类器需要 “缩小” （特殊化） 来排除那两个负例。 特殊化的一个方法是添加连接词， 例如， 把 shape = circle 变成 （shape = circle）AND（filling - shade = dark）。 新的表达式 虽然使所有负例都为假， 但依旧有缺点， 因为它只包含了 6 个正例中的 4 个 （即
40、 ex1、 ex2、 ex4、 ex6）。 因此， 下一步应尝试一般化， 如添加分离词： （shape = circle）AND（filling - shade = dark）OR （crust - size = thick）。 我们不停地重复这 个过程， 直到找到一个 100%准确的分类器为止 （如果存在）。 这种自省法告诉我们， 分类器可以通过一系列特殊化以及一般化的步骤， 通 过逐步调整一个给定的分类器来创建， 直到符合某个预定义的要求。 这对后期的 研究极具鼓励意义。 了解人工智能的读者会把这个过程看作在布尔表达式空间里 的搜索。 人工智能发展和探索了很多这样的搜索算法， 建议对其中一
41、些算法做一 个初步了解。 为确保你已经理解了本节的内容， 请试着回答以下问题。 如果在解答过程中 有任何困难， 请回顾本节的相关内容。 在刚才的讨论中， 什么是学习问题的输入和输出？ 我们是如何描述训练样例的？ 什么是样例空间？ 可以计算它的大小吗？ 在 “派” 域中找出一个布尔表达式， 将表 1. 1 中的所有训练样例正确 分类。 1. 2 一点题外话： 爬山搜索 现在， 我们把讨论过的搜索问题形式化， 并介绍一种流行的算法， 也就是所 谓的爬山法 （hill climbing）。 人工智能将搜索定义为： 从初态 （initial state） 开 始， 找到一系列步骤， 通过一组中间的搜索
42、状态 （search states）， 到达预定义的 006 机器学习导论 终态 （final state）。 从一种搜索状态过渡到另一种， 每一步都由程序员预设的搜索 算符 （search operators） 来完成。 搜索算符应用的步骤遵循特定的搜索策略 （search strategy）， 图 1. 2 描述了这一原理。 图 1. 2 由初态、 终态、 搜索算符和搜索策略形式化的搜索问题 爬山法 一个示例。 爬山法是一种流行的搜索策略。 我们要用著名的脑筋 急转弯游戏， 也就是数字滑块拼图来说明爬山法的本质。 该游戏通常的玩法是： 木板上有排成 3 行 3 列的 9 个方格， 其中 8
43、 个放有用数字编号的滑块 （整数 1 8）， 最后一个方格没有放置数字滑块。 通过滑动邻近滑块到空方格里来转变搜索 状态。 游戏的最终结果是达到一个预指定的滑块排列。 在图 1. 3 所示的流程图中， 我们从一个具体的初态开始， 并在两个搜索算符里进行选择：“上移滑块 6” 和 “左移滑块 2”。 此时， 可以借助评估函数 （evaluation function）， 通过估计每个状 态与目标的距离来指导选择。 最简单的评价形式可能是数出滑块在到达最终目的 地时所要滑过的方格数。 在初态中， 滑块 2、 4 和 5 已经处于正确的位置； 滑块 3 必须滑过 4 个方格； 滑块 1、 6、 7、
44、 8 每个均要滑过两个方格。 因此， 距离总和为 d =4 +4 2 =12。 在图 1. 3 中， 两种搜索算符都能使初态到达一个距离终态 d = 13 的状态。 在 缺乏其他的指导时， 我们随机选择左移， 使得空方格在第一行的中间位置。 这时 有 3 种移动可能， 其中一种只能让我们返回初态， 因此可以忽略掉。 第 1 章 一个简单的机器学习任务 007 图 1. 3 爬山法。 圈出的整数代表搜索状态改变的顺序， d 是用特 定评估函数计算出的该状态距终态的距离。 遇到多选项 （此处为两选项） 则随机进行选择 至于剩下的两种可能性， 一种能达到 d =14 的状态， 另一种能达到 d =1
45、2 的 状态。 我们选择数值较小的后者。 下一步很简单， 只有一种移动方式能到达一个 新的状态。 之后， 我们又面临着两种选择持续这个搜索过程直到达到终态 为止。 可选的终止标准和评估函数。 我们也可以考虑其他的终止标准 （termination criteria）。 当超过最大期限时 （我们不想让计算机一直运行下去）、 当已知状态 数量超过了某个界限时、 当我们已经发现某种十分接近终态的状态时、 当我们 发现所有的状态都出现过时， 诸如此类， 这些标准都可以用来终止搜索过程。 008 机器学习导论 实际的终止公式能反映特定应用的决定因素， 并且有时需要结合上述的两个或 多个标准。 另外， 在
46、数字滑块例子中用到的评估函数十分简单， 刚够完成任务： 让使 用者把自己对问题的理解转化成一些概念， 给那些需要的解决问题者提供线索。 为了顺利解决实际问题， 我们不得不想出一个更加缜密的函数。 通常， 人们可 以设计出各种各样的方案， 每个方案的步骤次序都不尽相同。 有些很快就能找 到解决办法， 其他的则绕了远路。 此时， 搜索程序的性能取决于程序员正确选 择搜索方案的能力。 爬山算法。 表 1. 2 中的伪代码总结了爬山算法。 当然， 细节部分取决于每个 人设计程序的风格， 但不同风格的代码几乎总会不约而同地包含一些经典的函数。 其中一个是比较两种状态， 如果相同则返回真； 这便是程序确定
47、达到终态与否的 方法。 另一个函数选取一个特定的搜索状态， 并将其应用到所有搜索算符中， 因 此创造了一套完整的 “子状态”。 为避免无限循环， 要有第三个函数来检验一个 状态是否已经测试过了； 第四个函数则负责计算给定状态距终态的距离； 第五个 会根据计算出的距离分类 “子” 状态； 并把它们放在列表 L 的前端； 最后一个函 简单来说， 伪代码忽视了终止条件， 因而没有达到终态。 数检验状态是否符合终止条件。 表 1. 2 爬山搜索算法 1. 创建两个列表， L 和 Lseen。 最初， L 只包含初态， Lseen是空的 2. 令 n 是表 L 中的第一个元素， 并与终态进行比较， 不停地比较直到两者一