Algorithm 版 (精华区)

发信人: AA (积极的人生、美好的人生), 信区: Algorithm
标  题: 机器学习(TOM.M.Mitchell)：第1章(zz)
发信站: 哈工大紫丁香 (2002年05月23日20:17:23 星期四), 站内信件

第1章 　绪论
自从计算机被发明以来，人们就想知道它们能不能学习。如果我们理解了它们学
习的内在机制，即怎样使它们根据经验来自动提高，那么影响将是空前的。想象
一下，在未来，计算机能从医疗记录中学习，获取治疗新疾病的最有效方法；住
宅管理系统分析住户的用电模式，以降低能源消耗；个人软件助理跟踪用户的兴
趣，并为其选择最感兴趣的在线新闻……。对计算机学习的成功理解将开辟出全
新的应用领域，并使其计算能力和可定制性上升到新的层次。同时，透彻地理解
机器学习的信息处理算法，也会有助于更好地理解人类的学习能力。
目前，我们还不知道怎样使计算机的学习能力和人类相媲美。然而一些针对特定
学习任务的算法已经产生。关于学习的理论认识已开始逐步形成。人们开发出了
很多实践性的计算机程序来实现不同类型的学习，一些商业化的应用也已经出现
。例如对于语音识别这样的课题，至今为止，基于机器学习的算法明显胜过其他
的方法。在数据挖掘领域，机器学习算法理所当然地被用来从包含设备维护记录
、借贷申请、金融交易、医疗记录等类似信息的大型数据库中发现有价值的信息
。随着对计算机的理解的日益成熟，机器学习必将在计算机科学和技术中扮演越
来越重要的角色！
通过一些特定的成就我们可以看到这门技术的现状：计算机已经能够成功地识别
人类的讲话（Waibel 1989；Lee 1989）；预测肺炎患者的康复率（Cooper et a
l. 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）以及Rume
lhart et al.（1994）调查了机器学习的一些其他应用。
表1-1 机器学习的一些成功应用
• 学习识别人类的讲话
所有最成功的语音识别系统都使用了某种形式的机器学习技术。例如，Sphinx系
统（参见Lee 1989）可学习特定讲话者的语音识别策略，从检测到的语音信号中
识别出基本的音素（phoneme）和单词。神经网络学习方法（例如Waibel et al.
 1989）和隐式马尔可夫模型（hidden Markov model）的学习方法（例如Lee 19
89）在语音识别系统中也非常有效，它们可以让系统自动适应不同的讲话者、词
汇、麦克风特性和背景噪音等等。类似的技术在很多信号解释课题中有应用潜力
。
• 学习驾驶车辆
机器学习方法已经用于训练计算机控制的车辆，使其在各种类型的道路上正确行
驶。例如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），该定律指出对于很大范围内的学习问
题，人们的反应速度随着实践次数的幂级提高。激发人工神经网络的学习模式的
神经生物学研究。
• 统计学
在估计有限数据样本上的假设精度时出现的误差（例如偏差和方差）的刻画。置
信区间，统计检验。
1.1 学习问题的标准描述
让我们从几个学习任务开始研究机器学习。根据本书的目的，我们给学习一个宽
广的的定义，以使其包括任何计算机程序通过经验来提高某任务处理性能的行为
。更准确地讲，
定义：  如果一个计算机程序根据经验E来自我完善（用P来衡量）针对任务类T的
性能，那么我们称这个计算机程序在从经验E学习，针对一类任务T，它的性能用
P来衡量。
例如，对于学习下西洋跳棋 的计算机程序，它可以通过和自己下棋获取经验，它
担负的任务是参与西洋跳棋对弈，它的性能用它赢棋的能力来衡量。通常，为了
很好地定义一个学习问题，我们必须明确这样三个特征：任务的种类；衡量任务
提高的标准；经验的来源。
西洋跳棋学习问题：
• 任务T：下西洋跳棋
• 性能标准P：比赛中击败对手的百分比
• 训练经验E：和自己进行对弈
我们可以用以上方法定义很多学习问题，例如学习手写识别、学习自动驾驶机器人汽车
。
手写识别学习问题：
• 任务T：识别和分类图像中的手写文字
• 性能标准P：分类的正确率
• 训练经验E：已知分类的手写文字数据库
机器人驾驶学习问题：
• 任务T：通过视觉传感器在四车道高速公路上驾驶
• 性能标准P：平均无差错行驶里程（差错由人类的 喽 裁定）
• 训练经验E：注视人类驾驶时录制的一系列图像和驾驶指令
这里对学习的定义宽广到足以包括大多数惯于被称为“学习”的任务，就象我们
日常使用的这个词一样。同时，它也包括了以非常简明的方式通过经验自我提高
的计算机程序。例如，一个允许用户更新数据条目的数据库系统，也符合我们对
学习系统的定义：它根据从数据库更新得到的经验提高它回答数据查询的能力。
与其担心这种行为与“学习”这个词日常谈论的非正式含义相混淆，我们索性简
单地采用我们的科技型定义——一类计算机程序通过经验提高的过程。在这个范
畴内，我们会发现很多问题或多或少需要较复杂的解决办法。这里我们并非要分
析“学习”这个单词的日常含义。而是要精确地定义一类囊括我们感兴趣的学习
形式的问题，探索解决这类问题的方法，并理解学习问题的基础结构和过程。
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→&Acir
c; 来表示V把任何合法的棋局从集合B映射到某一个实数值（用Â来表示实
数集合）。我们打算让这个目标函数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相区别。
1.2.3   选择目标函数的表示
至此，我们已经确定了目标函数V，接下来必须选择一个表示，被学习程序用来描
述要学习的函数 。对此也有很多设计选择。例如，可以让程序使用一张大表，对
于每个惟一的棋盘状态b，表中有惟一的表项来确定它的值 (b)。或者，可以让程
序用一个规则集合来匹配棋局的特征以表示 ，或采用一个与预定义棋盘特征有关
的二次多项式函数，或者用人工神经元网络。通常，选择这个描述包含一个重要
的权衡过程。一方面，我们总希望选取一个非常有表现力的描述，以最大可能地
逼近理想的目标函数V。另一方面，越有表现力的描述需要越多的训练数据，使程
序能从它表示的多种假设中做出选择。为了简化讨论，现在选择一个简单的表示
法：对于任何给定的棋盘状态，函数 可以通过以下棋盘参数的线性组合来计算：
l   x1：棋盘上黑子的数量
l   x2：棋盘上红子的数量
l   x3：棋盘上黑王的数量
l   x4：棋盘上红王的数量
l   x5：被红子威胁的黑子数量（即会在下一次被红吃掉的子）
l   x6：被黑子威胁的红子数量
于是，学习程序把 (b)表示为一个线性函数
 (b)=w0+w1x1+w2x2+w3x3+w4x4+w5x5+w6x6
其中w0到w6为数字系数，或叫权，由学习算法来选择。在决定某一个棋盘状态的
分值时，w1 到 w6决定了不同的棋盘特征的相对重要性，而权w0为一个附加的常
量。
概括一下目前为止的设计。我们已经详细阐述了这个学习问题的原型，即为它选
择一种类型的训练经验，一个要学习的目标函数，和这个目标函数的一种表示法
。现在的学习任务是：
西洋跳棋程序的部分设计
• 任务T：下西洋跳棋
• 性能标准P：世界锦标赛上击败对手的百分比
• 训练经验E：和自己进行训练对弈
• 目标函数：V：B→Â
• 目标函数的表示： (b)=w0+w1x1+w2x2+w3x3+w4x4+w5x5+w6x6
前三条是对学习任务的说明，后两条制定了为实现这个学习程序的设计方案。注
意这个设计的关键作用是把学习西洋跳期战略的问题简化为学习目标函数描述中
系数w0到w6值的问题。
1.2.4   选择函数逼近算法
为了学习目标函数  ，需要一系列训练样例，每一个样例描述了特定的棋盘状态
b和它的训练值Vtrain(b)。换言之，每一个训练样例是形式为<b，Vtrain(b)>的
序偶。举例来说，下面的训练实例描述了一个黑棋胜利（注意x2=0表示红棋已经
没有子了）的棋盘状态b，它的目标函数值Vtrain(b)为100。
<<x1=3，x2=0，x3=1，x4=0，x5=0，x6=0>，+100>
下文描述了一个过程，它先从学习器可得的间接训练经验中导出上面的训练样例
，然后调整权值wi以最佳拟合这些训练样例。
1.2.4.1 估计训练值
根据以上的学习模型，学习器可以得到的训练信息仅是对弈最后的胜负。 另一方
面，我们需要训练样例为每个棋盘状态赋予一个分值。给对弈结束时的棋盘状态
评分是容易的，而要给对弈结束前的大量中间棋局评分就不那么容易了。因为，
一盘棋的最终输赢未必能说明这盘棋当中的每一个棋盘状态的好或坏。例如，即
使某个程序输了一盘棋，仍会有这样的情况，这盘棋前面的棋局应该给予很高的
评价，失败的原因在于后来糟糕的走法。
尽管估计中间棋局训练值具有内在的模糊性，但令人惊讶的是有一个简单的方法
却取得了良好结果。这种方法对于任何中间棋局b的训练值Vtrain(b)等于 (Succ
essor(b))，其中 是学习器采用的对V的近似，Successor(b) 表示b之后再轮到程
序走棋时的棋盘状态（也就是程序走了一步和对手回应一步后的棋局）。
这种估计训练值的方法可被归纳为：
训练值估计法则
Vtrain(b)← (Successor(b))  （1.1）
或许这看起来有点离奇，只使用当前的 来估计被用来精化同一函数的训练值，但
请注意，我们是在用后续棋局Successor(b)的估计值来估计棋局b的值。凭直觉，
我们可以看到越接近游戏结束的棋局的 越趋向精确。事实上，在特定条件下（将
在第13章讨论）这种基于对后继棋局进行估计的迭代估计训练值的方法，已被证
明可以近乎完美地收敛到Vtrain估计值。
1.2.4.2 权值调整
剩下的事情就是为这个学习算法选择最适合训练样例{<b, Vtrain(b)>}的权wi。
第一步必须定义最佳拟合（best fit）训练数据的含义。一种常用的方法是把最
佳的假设（或权值集合）定义为使训练值和假设 预测出的值间的误差平方E最小
。
至此，我们的目标就是寻找权值（等价地，寻找 ），使对于观测到的训练数据E
值最小化。第6章将讨论在什么条件下，最小化误差平方和等价于寻找给定观测训
练数据下的最可能假设。
已经知道一些算法可以得到线性函数的权使此定义的E最小化。在这里需要一个算
法，它可以在有了新的训练样例时进一步精化权值，并且它对估计的训练数据中
的差错有好的鲁棒性。一个这样的算法被称作最小均方法（least mean squares
），或叫LMS训练法则。对于每一训练样例，它把权值向减小这个训练数据误差的
方向略为调整。如第4章讨论的那样，这个算法可被看作对可能的假设（权值）空
间进行随机的梯度下降搜索，以使误差平方和E最小化。LMS算法是这样定义的：
LMS 权值更新法则
对于每一个训练样例<b，Vtrain(b)>
&#8226; 使用当前的权计算 (b)
&#8226; 对每一个权值wi进行如下更新
wi←wi+η(Vtrain(b)- (b)) xi
这里η是一个小的常数（比如0.1）用来调整权值更新的幅度。为了直观地理解这
个权值更新法则的工作原理，请注意当误差（Vtrain(b)-  (b)）为0时，权不会
被改变。当(Vtrain(b)- (b))为正时（例如，当 (b)太低时）每一个权值会根据
其对应特征值增加一定的比例。这会提升 (b)的值而减小误差。注意如果某个参
数xi为0，那么它的值不会因这个误差而改变，这样便使只有那些在训练样例的棋
局中确实出现的特征的权值才被更新。令人吃惊的是，在一定的条件下，这种简
单的权值调整方法被证明可以收敛到Vtrain 值的最小误差平方逼近（就像第4章
所讨论的）。
1.2.5   最终的设计
西洋跳棋学习系统的最终设计可以自然地用四个清楚的程序模块来描述，这些模
块在很多学习系统中是核心组件。这四个模块被归纳在图1-1中，它们是：
执行系统（Performance system），这个模块是用学会的目标函数来解决给定的
任务，在此就是对弈西洋跳棋。它把新问题（新一盘棋）的实例作为输入，产生
一组解答路线（对弈历史记录）作为输出。在这里，执行系统采用的选择下一步
走法的策略是由学到的评估函数 来决定的。所以我们期待它的性能会随着评估函
数的日益准确而提高。
插图——原书页码：  12
Experiment Generator-试验生成器
New Problem(initial game board)-新问题（初始棋局）
Performance System-执行系统
Solution trace(game history)-解答路线（对弈历史）
Critic-鉴定器
Training examples-训练样例
Generalizer-泛化器
Hypothesis-假设
图1-1 西洋跳棋学习程序的最终设计
鉴定器（Critic），它以对弈的路线或历史记录作为输入，输出目标函数的一系
列训练样例。如图所示，每一个训练样例对应路线中的某个棋盘状态和目标函数
给这个样例的评估值Vtrain。在我们的例子中，鉴定器对应式1.1给出的训练法则
。
泛化器（Generalizer），它以训练样例作为输入，输出一个假设，作为它对目标
函数的估计。它从特定的训练样例中泛化，猜测一个一般函数，使其能够覆盖这
些样例以及样例之外的情形。在我们的例子中，泛化器对应LMS算法，输出假设是
用学习到的权值w0 ,..., w6描述的函数 。
实验生成器（Experiment Generator），它以当前的假设（当前学到的函数）作
为输入，输出一个新的问题（例如，最初的棋局）供执行系统去探索。它的角色
是挑选新的练习问题，以使整个系统的学习速率最大化。在我们的例子中，实验
生成器采用了非常简单的策略：它总是给出一个同样的初始棋局来开始新的一盘
棋。更完善的策略可能致力于精心设计棋子位置以探索棋盘空间的特定区域。
总体来看，我们为西洋跳棋程序作的设计就是产生执行系统、鉴定器、泛化器和
实验生成器的特定实例。很多机器学习系统通常可以用这四个通用模块来刻画。
设计西洋跳棋程序的流程被归纳在图1-2中。这个设计已经在几方面把学习任务限
制在较小的范围内。要学习的知识类型被限制为一个单一的线性评估函数。而且
这个评估函数被限制为仅依赖于六个棋盘特征。如果目标函数真的可表示为这些
特定参数的线性组合，那么程序学到这个目标函数的可能性很大。反之，最多只
希望它学到一个好的近似，因为一个程序当然不能学会它根本不能表示的东西。
插图——原书页码：  13
Determine Type of Training Experience-  决定训练经验形式
Games against experts-                  与专家对弈
Games against self-                     与自己对弈
Table of correct moves-                 正确走子的表格
Determine Target Function-              决定目标函数
Board->move-                            棋盘&reg;走子
Board->value-                           棋盘&reg;分值
Determine Representation of Learned Function-决定目标函数的表示
Polynomial-                         多项式
Linear function of six features-            六个参数的线性函数
Artificial neural network-              人工神经网络
Determine Learning Algorithm-           决定学习算法
Gradient descent-                       梯度下降
Linear programming-                 线性规划
Completed Design-                       完成的设计
图1-2西洋跳棋学习程序的设计过程概述
我们假定真实函数V的好的近似确实可被表示为这种形式。那么问题变成这种学习
技术是否确保能发现一个。第13章提供了一种理论上分析，表明对于某些类型的
搜索问题，在相当严格的前提下，这种方法确实收敛到期望的评估函数。很幸运
，实践经验表明这种学习评估函数的途径经常是成功的，甚至在能被证明的情形
之外也是如此。
已经设计的程序能学得足够好而击败人类的西洋跳棋冠军吗？或许不能。部分地
，这是因为 的线性函数表示太简单以致于不能很好捕捉这种棋的微妙之处。然而
，如果给与一个更完善的目标函数表示法，这种通用的途径事实上可以非常成功
。例如，Tesauro(1992, 1995)报告了学习下西洋双陆棋的程序的类似设计，方法
是学习针对棋局的非常类似的评估函数。它的程序使用人工神经元网络表示学到
的评估函数，它考虑对棋局的完整描述而不是棋盘的几个参数。经历了一百万次
以上的自我生成的训练比赛后，他的程序能够和一流的人类西洋双陆棋选手一争
高下。
当然还可能为西洋跳棋学习任务设计很多其他的算法。例如，一种可能只简单地
存储训练样例，然后去寻找保存的“最接近的”情形来匹配新的情况（最近邻算
法，第8章）。或者可以产生大量候选的西洋跳棋程序，并让它们相互比赛，保留
最成功的程序并进一步用模拟进化的方式来培育或变异它们（遗传算法，第9章）
。人类似乎遵循另一种途径寻找学习策略，他们分析或向自己解释比赛中碰到的
某一次成败的原因（基于解释的学习，第11章）。上面的设计是这些种类中的一
个简单的算法，它是为了给我们今后的针对特定类别的任务的学习方法的设计奠
定基础。
1.3 机器学习的一些观点和问题
在机器学习方面，一个有效的观点是机器学习问题经常归结于搜索问题，即对一
个非常大的假设空间进行搜索，以确定一个最拟合观察到的数据和学习器已有知
识的假设。例如，考虑一下上面的西洋跳棋学习程序输出的假设空间。这个假设
空间包含所有可由权w0到w6的不同值的评估函数。于是学习器的任务就是搜索这
个大的空间来定位与训练数据最佳拟合的假设。针对拟合权值的LMS算法通过迭代
调整权值实现了这个目的，每当假设的评估函数预测出一个与训练数据有偏差的
值时就对每个权值进行校正。当学习器考虑的假设表示定义了一个连续的参数化
的潜在假设空间时，这个算法很有效。
本书的很多章节给出了对一些基本表示（例如，线性函数、逻辑描述、决策树、
人工神经元网络）定义的假设空间的搜索算法。这些不同的假设表示法适合于学
习不同的目标函数。对于其中的每一个假设表示法，对应的学习算法发挥不同内
在结构的优势来组织对假设空间的搜索。
自始至终，本书都贯穿着这种把学习问题视为搜索问题的看法，从而通过搜索策
略和学习器探索的搜索空间的内在结构来刻画学习方法。我们也会发现，这种观
点对于形式化地分析要搜索的假设空间的大小、可利用的训练样例的数量以及一
个与训练数据一致的假设能泛化到未见实例的置信度这三者之间的关系非常有用
。
1.3.1   机器学习的问题
西洋跳棋例子提出了机器学习方面很多普遍问题。机器学习这门学科，和本书的
绝大部分，都致力于回答类似下面的问题：
&#8226; 从特定的训练数据学习一般的目标函数存在什么样的算法？如果提供了
充足的训练数据，什么样的条件下会使特定的算法收敛到期望的函数？哪个算法
对哪些问题和表示的性能最好。
&#8226; 多少训练数据是充足的？怎样找到学习到假设的置信度与训练数据的数
量及提供给学习器的假设空间特性之间的一般关系？
&#8226; 学习器拥有的先验知识是怎样引导从样例进行泛化的过程的？当先验知
识仅仅是近似正确时，它们会有帮助吗？
&#8226; 对于选择有用的后续训练经验，什么样的策略最好？这个策略的选择会
怎样影响学习问题的复杂性？
&#8226; 怎样把学习任务简化为一个或多个函数逼近问题？换一种方式，系统该
试图学习哪些函数？这个过程本身能自动化吗？
&#8226; 学习器怎样自动地改变表示法来提高表示和学习目标函数的能力？
1.4 如何阅读本书
这本书介绍了机器学习的主要算法和途径；不同学习任务可行性和特定算法能力
的理论结果；以及机器学习应用于解决现实问题的例子。只要可能，各章的写作
都力争与阅读顺序无关。然而一些相互依赖性是不可避免的。如果本书被用作教
科书，我建议首先完成第一和第二章，剩下来的各章基本可以以任意顺序阅读。
长度为一个学期的机器学习课程可以包括前七章以及额外的几个最感兴趣的章节
。下面简要浏览一下各章。
&#8226; 第2章包括基于符号和逻辑表示的概念学习。也讨论了假设的一般到特殊
偏序结构，以及学习中引入归纳偏置的必要性。
&#8226; 第3章包括决策树学习和过度拟合训练数据的问题。这一章也剖析了奥坎
姆剃刀——该原则建议在与数据一致的假设中选择最短假设。
&#8226; 第4章包括人工神经网络的知识，特别是研究已久的反向传播算法，以及
梯度下降的一般方法。这一章包含一个详细的基于神经网络的人脸识别实例，该
例子需要的数据和算法可以在万维网上得到。
&#8226; 第5章给出了来自统计和估计理论的基础概念，着重于使用有限的样本数
据评估假设的精度。这一章包含了用于估计假设精度的置信空间，和对不同学习
算法的精度进行比较的方法。
&#8226; 第6章介绍机器学习的贝叶斯观点。既包括了使用贝叶斯分析刻画非贝叶
斯学习算法，又包括了直接处理概率的贝叶斯算法。这一章包括一个应用贝叶斯
分类器来分类文本文档的详细例子，所需的数据和软件可以在万维网上得到。
&#8226; 第7章覆盖了计算学习理论，包括可能近似正确（Probably Approximat
ely Correct，PAC）学习模型和出错界限（Mistake-Bound）学习模型。本章讨论
了联合多个学习方法的加权多数（Weighted Majority）算法。
&#8226; 第8章描述了基于实例的学习方法，包括最近邻学习，局部加权回归，和
基于案例的推理。
&#8226; 第9章讨论了根据生物进化建模的学习算法，包括遗传算法和遗传编程。
&#8226; 第10章覆盖了一组学习规则集合的算法，包括学习一阶Horn子句的归纳
逻辑编程方法。
&#8226; 第11章包含了基于解释的学习，即一种使用以前的知识解释观察到的实
例，然后根据这些解释泛化的学习方法。
&#8226; 第12章讨论了把以前的近似知识结合进现有的训练数据中以提高学习精
度的方法。在其中符号算法和神经网络算法都有讨论。
&#8226; 第13章讨论了增强学习。这种方法是为了处理来自训练信息的间接的或
延迟的反馈。本章前面提及的下棋学习程序是增强学习的一个简单的例子。
每章的结尾包含了所覆盖的主要概念的小结、进一步阅读的参考和习题。其他对
章节的更新，包括数据集和算法的实现，都可从网址http://www.cs.cmu.edu/~t
om/mlbook.html访问到。
1.5 小结和补充读物
机器学习致力于研究建立能够根据经验自我提高处理性能的计算机程序。本章的要点包
括：
&#8226; 机器学习算法在很多应用领域被证明有很大的实用价值。它们在以下方
面特别有用：（a）数据挖掘问题，即从大量数据中发现可能包含在其中的有价值
的规律（例如，从患者数据库中分析治疗的结果，或者从财务数据中得到信用贷
款的普遍规则）；（b）在某些困难的领域中，人们可能还不具有开发出高效的算
法所需的知识（比如，从图像库中识别出人脸）；（c）计算机程序必须动态地适
应变化的领域（例如，在原料供给变化的环境下进行生产过程控制，或适应个人
阅读兴趣的变化）。
&#8226; 机器学习从不同的学科吸收概念，包括人工智能，概率和统计，计算复
杂性，信息论，心理学和神经生物学、控制论、以及哲学。
&#8226; 一个完整定义的学习问题需要一个明确界定的任务、性能度量标准以及
训练经验的来源。
&#8226; 机器学习算法的设计过程中包含许多选择，包括选择训练经验的类型、
要学习的目标函数、该目标函数的表示形式、以及从训练样例中学习目标函数的
算法。
&#8226; 学习的过程即搜索的过程，搜索包含可能假设的空间，使得到的假设最
符合已有的训练样例和其他预先的约束或知识。本书的大部分内容围绕着搜索各
种假设空间（例如，包含数值函数、神经网络、决策树、符号规则的空间）的不
同学习方法，和理论上这些搜索方法在什么条件下会收敛到最佳假设。
有很多关于机器学习最新研究成果的优秀资源可供阅读。相关的杂志包括《机器
学习》（Machine Learning），《神经计算》（Neural Computation），《神经
网络》（Neural Networks），《美国统计协会期刊》（Journal of the Americ
an Statistical Association）和《IEEE模式识别和机器智能学报》（IEEE Tra
nsactions on Pattern Analysis and Machine Intelligence）。也有大量的年
会覆盖了机器学习的各个方面，包括国际机器学习会议(ICML)，神经信息处理系
统(NIPS)，计算学习理论会议(CCLT)，国际遗传算法会议(ICGA)，国际知识发现
和数据挖掘会议(ICKDD)，欧洲机器学习会议(ECML)等。
习题
1.1 给出三种机器学习方法适合的应用，三种不适合的应用。挑选本书未提及的
应用，并对每个应用以一句话来评价。
1.2 挑选一些本书未提到的学习任务。用英文写一段话非正式地加以描述。再尽
可能精确地描述出它的任务、性能衡量标准和训练经验。最后，给出要学习的目
标函数和它的表示。讨论这个任务设计中考虑的主要折中。
1.3 证明本章描述的LMS权更新法则采用了梯度下降方法使误差平方最小化。确切
地讲，像文中那样定义方差E。然后计算E对权wi的导数，其中假定 与文中定义的
一样，是一个线性函数。梯度下降是通过与 成比例地更新每个权值实现的。所以
，必须证明对于所遇到的每一个训练样例，LMS训练法则都是按这个比例来改变权
值。
1.4 图1-1中实验生成器模块可采用其他一些策略。确切地讲，考虑实验生成器用
下面的策略提出新的棋局：
&#8226; 产生随机的合法的棋局
&#8226; 从前面的对弈中挑选一个棋局，然后走一步上次没有走的棋而产生新的棋局
&#8226; 一种你自己设计的策略
讨论这些策略的优劣。如果训练样例的数量是固定的，哪一个效果最好？假定性
能衡量标准是在世界锦标赛上赢棋最多。
1.5使用类似于西洋跳棋问题的算法，实现一个更简单的tic-tac-toe游戏 。把学
习到的函数 表示为自选的棋局参数的线性组合。要训练这个程序，可以让它和它
的另一个拷贝反复比赛，后者使用手工建立的固定评估函数。用图表绘出你的程
序胜利的百分比，对应于训练次数。
参考文献
  
--
                人世间的事谁也无法掌握
                  该执著的  永不怨悔
                  改舍去的  不在牵挂
                  改珍惜的  好好把握

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: NLPCenter.hit.edu.cn]