Machine Learning (Tom) 中文清晰版.pdf

发布时间：2022-05-31 发布人：admin 分类：说明书资料大小：1.56M 资料格式：pdf 举报版权申诉

jiayingsong-10151842-4744302543396337020.pdf-第1页.png

第1页 / 共282页

jiayingsong-10151842-4744302543396337020.pdf-第2页.png

第2页 / 共282页

jiayingsong-10151842-4744302543396337020.pdf-第3页.png

第3页 / 共282页

jiayingsong-10151842-4744302543396337020.pdf-第4页.png

第4页 / 共282页

jiayingsong-10151842-4744302543396337020.pdf-第5页.png

第5页 / 共282页

jiayingsong-10151842-4744302543396337020.pdf-第6页.png

第6页 / 共282页

jiayingsong-10151842-4744302543396337020.pdf-第7页.png

第7页 / 共282页

jiayingsong-10151842-4744302543396337020.pdf-第8页.png

第8页 / 共282页

序言

第1章绪论

第2章概念学习和一般到特殊序

第3章决策树学习

第4章人工神经网络

第5章评估假设

第6章贝叶斯学习

第7章计算学习理论

第8章基于实例的学习

第9章遗传算法

第10章学习规则集合

第11章分析学习

第12章归纳和分析学习的结合

第13章增强学习

序言机器学习这门学科所关注的问题是：计算机程序如何随着经验积累自动提高性能？近年来，机器学习被成功地应用于很多领域，从检测信用卡交易欺诈的数据挖掘程序，到获取用户阅读兴趣的信息过滤系统，再到能在高速公路上自动行驶的汽车。同时，这个学科的基础理论和算法也有了重大的进展。这本教材的目标是展现机器学习中核心的算法和理论。机器学习从很多学科吸收了成果和概念，包括统计学、人工智能、哲学、信息论、生物学、认知科学、计算复杂性和控制论等。我相信，研究机器学习的最佳途径是从这些学科的观点看待机器学习，并且以此来理解问题的背景、算法以及其中隐含的假定。这些在以往很难做到，因为在这一领域缺少包容广泛的原始资料。这本书的主要目的就是提供这样的一份资料。由于素材的多学科性，这本书不要求读者具有相应的知识背景，而是在必要时介绍其他一些学科的基本概念，如统计学、人工智能、信息论等。介绍的重点是与机器学习关系最密切的那些概念。本书可以作为计算机科学与工程、统计学和社会科学等专业的大学生或研究生的教材，也可作为软件研究人员或从业人员的参考。指导这本书写作的两条原则为：1. 它是在校大学生可以理解的；2.它应该包含博士生在开始研究机器学习前要掌握的内容。指导这本书写作的第三条原则是：它应该体现理论和实践两者的平衡。机器学习理论致力于回答这样的问题“学习性能是怎样随着给定的训练样例的数量变化的？”和“对于不同类型的学习任务，哪个学习算法最适合？”利用来自统计学、计算复杂性和贝叶斯分析的理论成果，这本书讨论了这一类理论问题。同时本书也覆盖了很多实践方面的内容：介绍了这一领域的主要算法，并阐明了算法的运行过程。一些算法的实现和数据可以在互联网上通过网址 http://www.cs.cmu.edu/~tom/mlbook.html 得到。其中包括用于人脸识别的神经网络、用于信贷分析的决策树学习、及分析文本文档的贝叶斯分类器各自的源代码和所需数据。我很感谢那些帮助我创建这些在线资源的同事，包括 Jason Rennie、Paul Hsiung、Jeff Shufelt、 Matt Glickman、Scott Davies、Joseph O’Sullivan、Ken Lang、Andrew McCallum 和 Thorsten Joachims。致谢在写作这本书的过程中，我幸运地得到了机器学习领域很多学科分支的技术专家的帮助。没有他们的帮助这本书是不可能完成的。我深深地感激下面的科学家们，他们花时间检阅本书的草稿，并且以他们各自领域的专长对我进行了指导。（……）我也很感谢各所大学的很多讲师和学生，他们实地测试了本书的很多草稿并提出了他们的建议。尽管没有足够的版面来感谢上百名的学生、讲师和其他测试了草稿的人，我要感谢下面各位，感谢他们特别有帮助的建议和讨论。（……）

我感谢 Joan Mitchell 建立了本书的索引。我也感谢 Jean Harpley 帮助编辑了很多插图。 ETP Harrison 的 Jane Loftus 帮助整理了本书的手稿。我的编辑，McGraw Hill 出版社的 Eric Munson 在项目的整个过程中提供了鼓励和意见。通常，一个人最该感谢的是他的同事、朋友和家庭。对于我，尤其要表达自己的感激。我很难想象有人比我在 Carnegie Mellon 拥有更好的智者云集的环境和更多的鼎力相助的朋友。在这些很多帮助过我的人当中，我特别感谢 Sebastian Thrun，在这个项目的自始至终，他一直对我进行着精神鼓励、技术指导等各种支持。我的父母，与以往一样的鼓励我并在最恰当的时候问“已经完成了吗？”最后，我一定要感谢我的家人：Meghan，Shannon 和 Joan。他们在不知不觉中以各种方式对此书作出了贡献。这本书是献给他们的。 Tom M. Mitchell

第1章绪论自从计算机被发明以来，人们就想知道它们能不能学习。如果我们理解了计算机学习的内在机制，即怎样使它们根据经验来自动提高，那么影响将是空前的。想象一下，在未来，计算机能从医疗记录中学习，获取治疗新疾病的最有效方法；住宅管理系统分析住户的用电模式，以降低能源消耗；个人软件助理跟踪用户的兴趣，并为其选择最感兴趣的在线新闻……。对计算机学习的成功理解将开辟出全新的应用领域，并使其计算能力和可定制性上升到新的层次。同时，透彻地理解机器学习的信息处理算法，也会有助于更好地理解人类的学习能力。目前，我们还不知道怎样使计算机的学习能力和人类相媲美。然而一些针对特定学习任务的算法已经产生。关于学习的理论认识已开始逐步形成。人们开发出了很多实践性的计算机程序来实现不同类型的学习，一些商业化的应用也已经出现。例如对于语音识别这样的课题，至今为止，基于机器学习的算法明显胜过其他的方法。在数据挖掘领域，机器学习算法理所当然地得到应用，从包含设备维护记录、借贷申请、金融交易、医疗记录等类似信息的大型数据库中发现有价值的信息。随着对计算机的理解的日益成熟，机器学习必将在计算机科学和技术中扮演越来越重要的角色！通过一些特定的成就我们可以看到这门技术的现状：计算机已经能够成功地识别人类的讲话（Waibel 1989；Lee 1989）；预测肺炎患者的康复率（Cooper et al. 1997）；检测信用卡欺诈；在高速公路上驾驶（Pomerleau 1989）；以接近人类世界冠军的水平对弈西洋双陆棋①这样的游戏（Tesauro 1992, 1995）。已有了很多理论成果能够对训练样例数量、假设空间大小、和学得假设错误率这三者间的基本关系进行刻画。我们正在开始获取人类和动物学习的原始模型，用以理解它们和计算机的学习算法间的关系（例如，Laird et al. 1986；Anderson 1991； Qin et al. 1992；Chi & Bassock 1989；Ahn & Brewer 1993）。在过去的十年中无论是应用、算法、理论，还是生物系统的研究都取得了值得注目的进步。机器学习最近的几种应用被归纳在表 1-1 中。Langley & Simon（1995）以及 Rumelhart et al.（1994）调查了机器学习的一些其他应用。表 1-1 机器学习的一些成功应用 • 学习识别人类的讲话所有最成功的语音识别系统都使用了某种形式的机器学习技术。例如，Sphinx 系统（参见 Lee 1989）可学习特定讲话者的语音识别策略，从检测到的语音信号中识别出基本的音素（phoneme）和单词。神经网络学习方法（例如 Waibel et al. 1989）和隐式马尔可夫模型（hidden Markov model）的学习方法（例如 Lee 1989）在语音识别系统中也非常有效，它们可以让系统自动适应不同的讲话者、词汇、麦克风特性和背景噪音等等。类似的技术在很多信号解释课题中有应用潜力。 • 学习驾驶车辆 ①译注：一种类似飞行棋的游戏，双方各持十五子，通过掷骰子来决定棋子移动的步数。

机器学习方法已被用于训练计算机控制的车辆，使其在各种类型的道路上正确行驶。例如 ALVINN 系统（Pomerleau 1989）已经利用它学会的策略独自在高速公路的其他车辆之间奔驰，以 70 英里的时速共行驶了 90 英里。类似的技术可能在很多基于传感器的控制问题中得到应用。 • 学习分类新的天文结构机器学习方法已经被用于从各种大规模的数据库中发现隐藏的一般规律。例如，决策树学习算法已经被美国国家航空和航天局（NASA）用来分类天体，数据来自第二帕洛马天文台太空调查（Fayyad et al. 1995）。这一系统现在被用于自动分类太空调查中的所有天体，其中包含了 3T 字节的图像数据。 • 学习以世界级的水平对弈西洋双陆棋最成功的博弈类（如西洋双陆棋）计算机程序是基于机器学习算法的。例如，世界最好的西洋双陆棋程序 TD-Gammon（Tesauro 1992, 1995）是通过一百万次以上的和自己对弈来学习其策略的。现在它的水平能与人类的世界冠军相当。类似的技术被应用于许多实际问题，其中需要高效地搜索庞大的搜索空间。本书针对机器学习这个领域，描述了多种学习范型、算法、理论以及应用。机器学习从本质上是一个多学科的领域。它吸取了人工智能、概率统计、计算复杂性理论、控制论、信息论、哲学、生理学、神经生物学等学科的成果。表 1-2 归纳了这些学科中影响机器学习的关键思想。本书的素材基于不同学科的成果，然而读者不必精通每一个学科。来自这些学科的关键理论将使用非专业的词汇讲解，其中不熟悉的术语和概念会在需要时加以介绍。表 1-2 一些学科和它们对机器学习的影响 • 人工智能学习概念的符号表示。作为搜索问题的机器学习。作为提高问题求解能力途径的学习。使用先验的知识和训练数据一起引导学习。 • 贝叶斯方法作为计算假设概率的基础的贝叶斯法则。朴素贝叶斯分类器。估计未观测到变量的值的算法。 • 计算复杂性理论不同学习任务中固有的复杂性的理论边界，以计算量、训练样例数量、出错数量等衡量。为了优化预定目标，学习对各种处理过程进行控制，学习预测被控制的过程的下一个状态。熵和信息内容的度量。学习的最小描述长度方法。编码假设时，它的最佳编码和与最佳训练序列的关系。 • 控制论 • 信息论 • 哲学 “奥坎姆的剃刀”（Occam’s razor）①：最简单的假设是最好的。从观察到的数据泛化的理由分析。 • 心理学和神经生物学 • 统计学实践的幂定律（power law of practice），该定律指出对于很大范围内的学习问题，人们的反应速度随着实践次数的幂级提高。激发人工神经网络的学习模式的神经生物学研究。 ① 译注：也称“吝啬律（Law of Parsimony’”或“节约律（Law of Economy）”，主要思想为简单的理论（或假设）优于复杂的，因英国哲学家奥坎姆（1285~1349）频繁使用这一原则，故称为“奥坎姆剃刀”。

在估计有限数据样本上的假设精度时出现的误差（例如偏差和方差）的刻画。置信区间，统计检验。 1.1 学习问题的标准描述让我们从几个实际的学习任务开始研究机器学习。根据本书的目的，我们给学习一个宽广的定义，以使其包括任何计算机程序通过经验来提高某任务处理性能的行为。更准确地讲，定义：对于某类任务 T 和性能度量 P，如果一个计算机程序在 T 上以 P 衡量的性能随着经验 E 而自我完善，那么我们称这个计算机程序在从经验 E 学习。例如，对于学习下西洋跳棋①的计算机程序，它可以通过和自己下棋获取经验，它担负的任务是参与西洋跳棋对弈，它的性能用它赢棋的能力来衡量。通常，为了很好地定义一个学习问题，我们必须明确这样三个特征：任务的种类；衡量任务提高的标准；经验的来源。西洋跳棋学习问题： • 任务 T：下西洋跳棋 • 性能标准 P：比赛中击败对手的百分比 • 训练经验 E：和自己进行对弈我们可以用以上方法定义很多学习问题，例如学习手写识别、学习自动驾驶机器人汽车。手写识别学习问题： • 任务 T：识别和分类图像中的手写文字 • 性能标准 P：分类的正确率 • 训练经验 E：已知分类的手写文字数据库机器人驾驶学习问题： • 任务 T：通过视觉传感器在四车道高速公路上驾驶 • 性能标准 P：平均无差错行驶里程（差错由人类的监督裁定） • 训练经验 E：注视人类驾驶时录制的一系列图像和驾驶指令 ① 译注：为了更好理解本例，下面简要介绍一下这种跳棋。棋盘为 8×8 方格，深色棋格不可着子。可单步行走，亦可每步跨对方一子单跳或连跳，被跨越的子被杀出局。到达对方底线的子成为王，可回向行走（成为王前只可前行），又可隔空格飞行。下图为西洋跳棋棋盘示例（起始状态）。

这里对学习的定义很宽广，足以包括大多数惯于被称为“学习”的任务，就像我们日常使用的这个词一样。同时，它也包括了以非常简明的方式通过经验自我提高的计算机程序。例如，一个允许用户更新数据条目的数据库系统，也符合我们对学习系统的定义：它根据从数据库更新得到的经验提高它回答数据查询的能力。与其担心这种行为与“学习”这个词日常谈论的非正式含义相混淆，我们索性简单地采用我们的科技型定义——一类计算机程序通过经验提高的过程。在这个范畴内，我们会发现很多问题或多或少需要较复杂的解决办法。这里我们并非要分析“学习”这个单词的日常含义。而是要精确地定义一类囊括我们感兴趣的学习形式的问题，探索解决这类问题的方法，并理解学习问题的基础结构和过程。 1.2 设计一个学习系统为了演示一些机器学习的基本设计方法和途径，考虑设计一个学习下西洋跳棋的程序。我们的目标是让它进入西洋跳棋世界锦标赛。我们采用最显而易见的标准衡量它的性能：在世界锦标赛上打赢的比赛占总参赛次数的百分比。 1.2.1 选择训练方式我们面临的第一个设计问题是选取训练经验的类型，使系统从中进行学习。给学习器提供的训练经验对它的成败有重大的影响。一个关键属性是训练经验能否为系统的决策提供直接或间接的反馈。例如，对于学习下西洋跳棋，系统可以从直接的（direct）训练样例，即各种棋盘状态和相应的正确走子中学习。另一种情况，它可能仅有间接（indirect）的信息，包含很多过去的对弈序列和最终结局。对于后一种情况，关于博弈中较早走子的正确性必须从对弈最终的输赢来推断。这时学习器又额外面临一个信用分配（credit assignment）问题，也就是考虑每一次走子对最终结果的贡献程度。信用分配可能是一个非常难以解决的问题，因为如果后面下得很差，那么即使起初的走子是最佳的，这盘棋也会输掉。所以通常从直接的训练反馈来学习比间接的简单。训练经验的第二个重要属性是学习器可以在多大程度上控制训练样例序列。例如，学习器可能依赖施教者选取棋盘状态，和提供每一次的正确移动。或者，学习器可能自己提出它认为特别困惑的棋局并向施教者询问正确的走子。或者，学习器可以完全控制棋局和（间接的）训练分类，就像没有施教者时它和自己对弈进行学习一样。注意对于最后一种情况学习器可能选择以下两种情况中的一种：第一，试验它还未考虑过的全新棋局；第二，在它目前发现的最奏效的路线的微小变化上对弈，以磨砺它的技能。后续的章节考虑一些学习框架，包括了以下几种情况：训练经验是以超乎学习器控制的随机过程提供的；学习器可向施教者提出不同类型的查询；以及学习器通过自动探索环境来搜集训练样例。训练经验的第三个重要属性是，训练样例的分布能多好地表示实例分布，而最终系统的性能 P 是通过后者来衡量的。一般而言，当训练样例的分布和将来的测试样例的分布相似时，学习具有最大的可信度。对于我们的西洋跳棋学习，性能指标 P 是该系统在世界锦标赛上赢棋的百分比。如果它的训练经验 E 仅由和它自己对弈的训练组成，便存在一个明显的危险：这个训练可能不能充分地表示该系统以后被测试时的情形。例如，学习器可能在训练中从来未遇到过某些非常关键性的棋局，而它们又非常可能被人类世界冠军采用。实际上，学习的样例通常与最终系统被评估时的样例有一定差异，学习器必须能从中进行学习（举例来说，世界级的西洋跳棋冠军可能不会有兴趣教一个程序下棋）。这的确是一个问题，因为

掌握了样例的一种分布，不一定会导致对其他的分布也有好的性能。可以看到，目前多数机器学习理论都是基于训练样例与测试样例分布一致这一前提。尽管我们需要这样的前提以便得到理论的结果，但同样必须记住在实践中这个假设经常是不严格成立的。下面继续进行算法设计，我们决定系统将通过和自己对弈来训练。这样的好处是不需要外界的训练者，所以可以让系统产生无限多的训练数据，只要时间允许。现在有了一个完整的学习任务。西洋跳棋学习问题： • 任务 T：下西洋跳棋 • 性能标准 P：世界锦标赛上击败对手的百分比 • 训练经验 E：和自己进行对弈为了完成这个学习系统的设计，现在需要选择： 1. 要学习的知识的确切类型 2. 对于这个目标知识的表示 3. 一种学习机制 1.2.2 选择目标函数下一个设计选择是决定要学习的知识的确切类型，以及执行程序怎样使用这些知识。我们从一个对于任何棋局都能产生合法（legal）走子的西洋跳棋博弈程序开始。那么，最终的程序仅须学会从这些合法的走子中选择最佳的。这个学习任务代表了一大类任务：合法走子定义了某个先验已知的巨大搜索空间，但最佳的搜索策略未知。很多最优化问题都可归于此类，例如对于生产过程的调度和控制问题，生产中的每一步都很清楚，但调度这些步骤的最佳策略未知。为了学习从合法走子中作出选择，很明显，要学习的信息类型就是一个程序或函数，它对任何给定的棋局能选出最好的走法。可称此函数为 ChooseMove ，并用记法 ChooseMove:B→M 来表示这个函数以合法棋局集合中的棋盘状态作为输入，并从合法走子集合中产生某个走子作为输出。在关于机器学习的所有讨论中，我们发现可以把对任务 T 提高性能 P 的问题简化为学习象 ChooseMove 这样某个特定的目标函数（target function）的问题。所以目标函数的选择是一个关键的设计问题。尽管在例子中很明显应把 ChooseMove 作为目标函数，但我们会发现学习这个目标函数是非常困难的，原因是提供给系统的是间接的训练经验。另外一个可供选择的目标函数是一个评估函数，它为任何给定棋局赋予一个数字的评分。可以发现，对于本例，学习这个目标函数更简单。令这个目标函数为 V，并用 V：B→ℜ 来表示 V 把任何合法的棋局映射到某一个实数值（用ℜ来表示实数集合）。我们打算让这个目标函数 V 给好的棋局赋予较高的评分。如果系统能够成功地学会这个目标函数 V，那么它便能使用此函数轻松地找到当前棋局的最佳走法。实现的方法是，先产生每一个合法走子对应的所有后续棋局，然后使用 V 来选取其中最佳的后继棋局，从而选择最好的走子。对于任意棋局，目标函数 V 的准确值应该是多少呢？当然任何对较好的棋局赋予较高的分数的评估函数都适用。然而，最好在那些产生最佳对弈的众多方法中定义一个特定的目标函数 V。可以看到，这将使得设计一个训练算法变得简单。因此，对于集合 B 中的任意的棋局状态 b，我们如下定义目标函数 V(b)：

1. 如果 b 是一最终的胜局，那么 V(b)=100 2. 如果 b 是一最终的负局，那么 V(b)=-100 3. 如果 b 是一最终的和局，那么 V(b)=0 4. 如果 b 不是最终棋局，那么 V(b)=V(b′)，其中 b′是从 b 开始双方都采取最优对弈后可达到的终局。然而，由于这个定义的递归性，它的运算效率不高，所以这个定义对于西洋跳棋比赛者不可用。除了无关紧要的前三种终局的情况，对于某一个棋盘状态（情况 4）b 要决定它的值 V（b）需要向前搜索到达终局的所有路线！由于这个定义不能由西洋跳棋程序高效地运算，这个定义被称为不可操作的定义。当前的目标是发现一个可操作的定义 V，它能够被西洋跳棋程序用来在合理的时间内评估棋局并选取走法。这样，这种情况的学习任务被简化成发现一个理想目标函数 V 的可操作描述。通常要完美地学习这样一个 V 的可操作的形式是非常困难的。事实上，我们经常希望学习算法仅得到目标函数的某个近似（approximation），由于这个原因学习目标函数的过程常被称为函数逼近（function approximation）。在当前的讨论中，用Vˆ 来表示程序中实际学习到的函数，以区别理想目标函数 V。 1.2.3 选择目标函数的表示至此，我们已经确定了目标函数 V，接下来必须选择一个表示，被学习程序用来描述要学习的函数Vˆ 。对此也有很多设计选择。例如，可以将Vˆ 表示为一张大表，对于每个惟一的棋盘状态 b，表中有惟一的表项来确定它的状态值Vˆ (b)。或者，可以让程序用一个规则集合来匹配棋局的特征以表示Vˆ ，或采用一个与预定义棋盘特征有关的二次多项式函数，或者用人工神经元网络。通常，选择这个描述包含一个重要的权衡过程。一方面，我们总希望选取一个非常有表征力的描述，以最大可能地逼近理想的目标函数 V。另一方面，越有表征力的描述需要越多的训练数据，使程序能从它表示的多种假设中做出选择。为了简化讨论，现在选择一个简单的表示法：对于任何给定的棋盘状态，函数Vˆ 可以通过以下棋盘参数的线性组合来计算： x1：棋盘上黑子的数量 x2：棋盘上红子的数量 x3：棋盘上黑王的数量 x4：棋盘上红王的数量 x5：被红子威胁的黑子数量（即会在下一次被红吃掉的子） x6：被黑子威胁的红子数量于是，学习程序把Vˆ (b)表示为一个线性函数

分享到：

赞收藏

资料库

Machine Learning (Tom) 中文清晰版.pdf

相关推荐

人工智能

热门标签

最新资料