2023人工智能机器算法样例学习

人工智能机器算法

样例学习

目录

1学习的形式............................................................................5

1.1监督学习............................................................................8

1.2决策树学习.........................................................................14

1.2.1决策树的表达能力.................................................................15

1.2.2从样例中学习决策树...............................................................15

1.2.3选择测试属性.....................................................................19

124泛化与过拟合......................................................................22

1.2.5拓展决策树的适用范围.............................................................24

1.3模型选择与模型优化................................................................26

1.3.1模型选择..........................................................................28

1.3.2从错误率到损失函数...............................................................30

1.3.3正则化............................................................................33

134超参数调整........................................................................34

1.4学习理论...........................................................................36

1.5线性回归与分类....................................................................42

1.5.1单变量线性回归...................................................................42

1.5.2梯度下降.........................................................................44

153多变量线性回归....................................................................47

1.5.4带有硬阈值的线性分类器..........................................................50

155基于逻辑斯谛回归的线性分类器.....................................................54

1.6非参数模型.........................................................................58

1.6.1最近邻模型........................................................................58

163局部敏感哈希......................................................................62

1.6.4非参数回归.......................................................................63

1.6.5支持向量机.......................................................................65

166核技巧............................................................................70

1.7集成学习...........................................................................72

1.7.1自助聚合法........................................................................73

1.7.2随机森林法.......................................................................74

1.7.3堆叠法...........................................................................76

1.7.4自适应提升法.....................................................................76

2

1.7.5梯度提升法.......................................................................81

1.7.6在线学习.........................................................................82

1.8开发机器学习系统....................................................................85

1.8.1问题形式化........................................................................85

1.8.2数据收集、评估和管理............................................................86

183模型选择与训练....................................................................91

184信任、可解释性、可说明性.........................................................93

1.8.5操作、监控和维护.................................................................95

小结...................................................................................98

3

我们用样例学习来描述智能体通过不断学习自己以往的经验从而改

善自己的行为，并对未来进行预测的过程。

如果一个智能体通过对世界进行观测来提高它的性能，我们称其为

智能体学习(learning)o学习可以是简单的，例如记录一个购物清

单，也可以是复杂的，例如爱因斯坦推断关于宇宙的新理论。当智能体

是一台计算机时，我们称之为机器学习(machinelearning)：一台计算

机观测到一些数据，基于这些数据构建一个模型(model),并将这个

模型作为关于世界的一个假设(hypothesis)以及用于求解问题的软件

的一部分。

为什么我们希望一台机器进行学习？为什么不通过合适的方式;编程

然后让它运行呢？这里有两个主要的原因。其一，程序的设计者无法预

见未来所有可能发生的情形。举例来说，一个被设计用来导航迷宫的机

器人必须掌握每一个它可能遇到的新迷宫的布局；一个用于预测股市价

格的程序必须能适应各种股票涨跌的情形。其二，有时候设计者并不知

道如何设计一个程序来求解目标问题。大多数人都能辨认自己家人的面

孔，但是他们实现这一点利用的是潜意识，所以即使能力再强的程序员

也不知道如何编写计算机程序来完成这项任务，除非他使用机器学习算

法。

4

1学习的形式

一个智能体程序的各个组件都可以通过机器学习进行改进。改进及

用于改进的技巧取决于下面几个因素：

•哪些组件可以被改进；

•智能体有哪些先验知识，这将影响模型构建；

•有哪些数据，以及关于这些数据的反馈。

第2章中描述了一些智能体的设计。这些智能体的组件包括：

（1）从当前状态条件到动作的直接映射；

（2）用于从感知序列推断世界相关性质的方法；

（3）关于世界演化方式的信息，以及关于智能体可以采取的可能

动作所导致的结果的信息；

（4）表示状态意向的效用信息；

（5）表示动作意向的动作-价值信息；

（6）最希望达到的状态，即目标；

（7）问题生成器、评判标准和使系统得以改进的学习元素。

这些组件中的任何一个都可以被学习到。我们设想一个可以通过观

测人类司机行为来学习自动驾驶的汽车智能体。每次司机刹车时，这个

智能体可以学习到一个关于什么时候该踩刹车的条件-动作规则（组件

1）o通过观察大量包含公共汽车的照相机图像，它可以学习到如何辨

认公共汽车（组件2）。通过尝试不同动作以及观测相应的结果（例如

在潮湿的道路上艰难地刹车），它可以学习到动作相应的结果（组件

3）o接着，如果它收到在旅途中被剧烈颠簸吓坏了的乘客们的抱怨，

它可以学习到关于其总体效用函数的一个有效组件（组件4）。

5

机器学习技术已经成为软件工程的标准组成部分。无论何时你想搭

建一个软件系统，即使你不认为它是一个人工智能主体，这个系统的组

件也可能可以用机器学习的方式加以改进。例如，一个用于分析星系在

引力透镜下的图像的软件可以通过机器学习的模型加速一千万倍

(HezavehetaLy2017)；通过采用另一种机器学习的模型可以将数据

中心冷却的能耗降低40%(Gao,2014)o图灵奖得主大卫・帕特森

(DavidPatterson)和谷歌AI的掌门人杰夫・迪安(JeffDean)宣称，计

算机体系结构的“黄金时代'’的到来正归功于机器学习(Deanetal.,

2018)o

我们已经见过了一些关于智能体组件的模型示例：原子模型、因子

化模型，以及基于逻辑的关系模型或基于概率的关系模型等。人们针对

所有这些模型设计了广泛的学习算法。

本文中我们假设不存在关于这个智能体的先验知识(prior

knowledge)：它从零开始，从数据中学习。在2172节中，我们将考虑

迁移学习(transferlearning),在这种情形下，一个领域的知识被迁移

到一个新的领域，以更少的数据使学习过程进行得更快。我们当然还要

假设系统的设计者选取了合适的模型框架，从而让学习过程变得更加有

效。

从一组特定的观测结果得出一个普遍的规则，我们称之为归纳

(induction)o例如，我们观察到，过去的每一天太阳都会升起,因此

我们推断太阳明天也会升起。这与我们在第7章中研究的演绎

(deduction)不同，因为归纳的结论可能是不正确的,然而在演绎中,

只要前提是正确的，演绎的结论就保证是正确的。

本文将集中讨论输入为因广化表示(factoredrepresentation)------

属性值组成的向量——的问题。输入也可以是任意类型的数据结构，包

括原子表示的数据和关系数据等。

当输出是一个有限集合中的某个值时(如晴天/阴天/雨天或者正确/

错误)，我们称该学习问题为分类(classification)。当输出是一个数

值时(例如明天的温度，无论它是一个整数还是其他实数)，我们称该

学习问题为回归(regression)(这个词有些晦涩难懂山)。

111一个更好的名称是函数逼近或者数值预测。但在1886年，法国人弗朗西斯・高尔顿(Francis

Galton)写了一篇关于这一概念的富有影响力的文章regressb”始(例如，高个子父母

6

的孩子很可能身高高于平均值，但没有父母那么高）。高尔顿用他所称的“【口1归线”给出了一些球，

之后读者逐渐把“回归”一词与函数逼近这一统计技术联系起来，而不是与回归于均值的主题联

系起来。

伴随输入有3种类型的反馈（feedback）,它们决定了3种类型的学

习。

•在监督学习（supervisedlearning）中，智能体观测到输入■输出

对，并学习从输入到输出的一个函数映射。举个例子来说，输入是照相

机的图像，伴随输入的输出就是“公共汽车”或者"行人”等。诸如此类的

输出，我们称之为标签（label）。在智能体学习到一个函数之后，如果

给它一个新的图像输入，它将预测一个合适的标签。对于踩刹车这一动

作的学习（上述的组件1）,其输入是当前的状态（车的速度和行驶方

向、道路条件），输出是开始刹车到停车所需要行驶的距离。在这种情

形下，智能体可以直接从自己的感知中获得输出值（在动作结束之

后）；环境就是老师，智能体学习的是从当前状态到刹车距离的一个函

数。

•在无监督学习（unsupervisedlearning）中，智能体从没有任何显

式反馈的输入中学习模式。最常见的无监督学习任务是聚类

（clustering）：通过输入样例来检测潜在的有价值的聚类簇。例如，我

们从互联网上可以获取数百万个图像，一个计算机视觉系统可以识别一

大类相似的、被人类称为“猫'’的图像。

•在强化学习（reinforcementlearning）中，智能体从一系列的强化

-奖励与惩罚——中进行学习。举例来说，在一局国际象棋比赛结束

时，智能体会被告知它赢了（奖励）还是输了（惩罚）。智能体判断之

前采取的哪个动作该为这一结果负责，并且改变它的动作以在未来得到

更多的奖励。

7

1.1监督学习

更正式地说，监督学习的任务如下。

给定一个训练集(trainingset)含有N个“输入-输出”对样例：

(王，乂),(工2

其中每一对数据都由一个未知的函数y=/(x)生成，寻

找一个函数来近似真实的函数人

函数//被称为关于世界的假设(hypothesis)。它取自一个假设空间

(hypothesisspace)H,其中包含所有可能的函数。例如，这个限设空

间可能是最高次数为3的多项式集合、JavaScript函数的集合，也可能是

所有3-SAT布尔逻辑公式的集合。

同样地，我们可以称/2是关于数据的模型，它取自模型类(model

class)H,也可以说它取自函数类(functionclass)中的一个函数

(function)o我们称输出为为真实数据(groundtruth)----我们希望模

型能预测的正确答案。

那么，如何选择一个假设空间呢？我们可能有一些关于数据生成过

程的先验知识。如果没有的话，可以采用探索性数据分析(exploratory

dataanalysis)：通过统计检验和可视化方法——直方图、散点图、箱形

图——来探索数据以获得对数据的一些理解，以及洞察哪些假设空间可

能是合适的。或者我们可以直接尝试多种不同的假设空间，然后评估哪

个假设空间的效果最好。

有了假设空间后，如何从中选择一个好的假设呢？我们希望寻找一

个一致性假设(consistenthypothesis)：假设/?,对训练集中的任意一

个修，都有〃(看)=乃。如果输出是连续值，我们不能期望模型输出与真实

数据精确匹配；相反，我们可以寄希望于寻找一个最佳拟合函数(best-

fitfunction),使得每一个人(闻与力非常接近(我们将在19.4.2节中给出

正式表述)。

衡量一个假设的标准不是看它在训练集上的表现，而是取决于它如

8

何处理尚未观测到的输入。我们可以使用一个测试集(lestset)——第

二组样本数据对(号乃)——来评估假设。如果人准确地预测了测试集的输

出，我们称力具有很加的泛化(generalize)能力。

图19-1展示了一个学习算法所得到的函数〃依赖于假设所考虑的假

设空间H和给定的训练集。第一行的4幅图使用同一个训练集，训练集

中包含13个3)，)平面上的数据点。第二行的4幅图使用第二组由13个数

据点组成的训练集；两个训练集都代表了某个未知的函数/(x)o每一列

展示了不同假设空间中的最佳拟合假设九

•列1：直线；形如力(X)=W]X+M的函数。对于这些数据点，不存

在一致性假设的直线。

线性触正弦函数根刷MW.故而次数为12的多贩

图19/寻找拟合数据的假设。第•行：在数据集1上训练的来自4个不同假设空间的最佳拟合

函数的4个图像。第二行：同样的4个函数，但是在稍有不同的数据集上进行训练得到的结果

(数据集采样自相同的函数/«))

•列2：形如〃(x)=wj+sin(w㈤的正弦函数°这个假设并不是完全

一致的，但是将两个数据集都拟合得非常好。

•列3：分段线性函数，其中每一条线段从一个数据点连接到下一

个数据点。这类函数永远是一致的。

9

12

A(X)=VH,,X7

•列4：形如占的12次多项式。这类函数是一致的：我

们总是能找到一个12次

•多项式来准确地拟合13个不同点。但是假设是一致的并不意味着

这是一个好的预测。

分析假设空间的一个方法是分析它们带来的偏差(不考虑训练集)

和它们产生的方差(从一个训练集到另一个训练集)。

我们所说的偏差(bias)是指(不严格地)在不同的训练集上，假

设所预测的值偏离期望值的平均趋势。偏差常常是由假设空间所施加的

约束造成的。例如，当假设空间是线性函数时会导致较大的偏差：它只

允许函数图像是一条直线。如果数据中除了直线的整体斜率以外还存在

别的模式，线性函数将无法表示其他的模式。当一个假设不能找到数据

中的模式时,我们称它是欠拟合(underfitting)的。但是，分段线性函

数具有较小的偏差，其函数的形状是由数据决定的。

我们所说的方差(variance)是指由训练数据波动而导致假设的变

化量。图19-1的两行所使用的数据集采样于同一个函数/U)。两个数据

集略有不同。对前三列函数来说，数据集的略微不同导致的假设差别比

较小，我们称之为低方差的。但是第4列中的12次多项式函数则具有较

大方差：可以看到它们在x轴两端的表现差别很大。显然，这两个多项

式中至少有一个多项式对正确的函数/U)的拟合效果较差。当一个函数

过丁•关注它用来训练的特定训练数据集，进而导致它在没有见过的数据

上表现较差时，我们称该函数对数据集是过拟合(overfitting)的。

通常这其中存在一个偏差■方差权衡(bias・variancetradeoff)：在更

复杂、低偏差的能较好拟合训练集的假设与更简单、低方差的可能泛化

得更好的假设中做出选择。阿尔伯特・爱因斯坦(AlbertEinstein)曾于

1933年说过，“任何理论的终极目标都是尽可能让不可削减的基本元素

变得更加简单且更少，但也不能放弃对任何一个单一经验数据的充分阐

释，换句话说，爱因斯坦建议选择与数据相符的最简单的假设。这个

原则可以追溯到14世纪的英国哲学家奥卡姆的威廉(Williamof

Ockham⑵)，他的原则“如无必要，勿增实体”被称为奥卡姆剃刀原则

(Ockham^razor),因为它被用来“剔除”含糊的解释。

10

12］这个名字经常被错误拼写为“Occam”。奥卡姆是英国一座小镇的名字，是威廉出生的地方。

他在牛津大学注册时用的名字是“奥卡姆的威廉”，后来人们习惯性地把他提出的观点概括地称

为“奥卡姆剃刀原则一编者注

定义简单性并不容易。显然，只有两个参数的多项式比有13个参数

的多项式简单。在1934节中，我们将更加精确具体地表述这种直觉。

然而，在第21章中，我们将会看到，深度神经网络模型往往可以泛化得

非常好，尽管它们非常复杂——其中有些网络的参数达到数十亿个。所

以，仅通过参数个数本身来衡量模型的适合程度并不是一个好方法。因

此我们或许应该将目标定为选择“合适”而不是倘单”的模型类。我们将

在19.4.1节中考虑这个问题。

在图19-1中，我们并不确定哪个假设是最住的。如果我们知道数据

所表示的内容，例如，一个网站的点击量每天都在增长，并且会根据一

天的时间周期性变化，那么我们可能会更倾向于选择正弦函数。如果我

们知道数据不是周期性的并且存在较大的噪声，那么我们可能倾向于选

择线性函数。

在某些情形下，相比于仅仅判断一个假设是可能还是不可能的，分

析者更愿意给出一个假设可能发生的概率。监督学习可以通过选择假设

/z*(在数据集上〃*发生概率最大)来实现：

ht=argmaxP(h\data)

根据贝叶斯法则，上式等价于：

h*=argmaxP(data|h)P(h)

hOH

于是我们可以认为，光滑的一次或二次多项式的先验概率P(〃)是较

高的，而有较大波动的12次多项式的先验概率是较低的。当数据表示我

们确实需要使用一些不寻常的函数进行拟合时，我们也可以使用这些不

寻常的函数，但我们通过赋予它们一个较低的先验概率来尽可能避免这

种情况。

为什么我们不将H取为所有计算机程序或所有图灵机构成的类呢？

这里存在一个问题，在假设空间的表达能力与在该假设空间中寻找一

合适的假设所需的计算复杂性之间存在一种权衡。举例来说，根据数据

拟合一条直线是易于计算的；然而拟合一个高次的多项式则较为困难；

11

拟合一个图灵机则是不可判定的。我们倾向于选择简单假设空间的第二

个原因是，我们可能会在学习完力后使用它，当,是一个线性函数时，计

算/2（X）是很快的，然而计算任意的图灵机程序甚至不能保证程序终止。

基于这些原因，大多数关于学习的工作都集中在简单的表示上。近

年来，人们对深度学习产生了极大的兴趣（第21章），它对函数的表示

并不简单，但是人（幻仍然只需使用适当的硬件进行有限步的计算就可以

得到。

我们将看到，表达能力与复杂性的权衡并不简单：正如我们在第8

章一阶逻辑中所看到的，通常情况下，表达性语言使简单的假设能够与

数据相匹配，而限制语言的表达能力则意味着任何一致性假设都必定是

复杂的。

问题示例：餐厅等待问题

我们将详细描述一个监督学习问题的例子：决定是否在一家餐厅等

待位置的问题。这个问题将贯穿整章，用于比较不同的模型类。在这个

问题中，输出y是一个布尔变量，我们将其称为是否等待（死〃皿"）；

当我们决定在餐厅等待位置时它的值为真。输入x是有10个属性值的向

量，每个属性都是离散的值。

（1）候补招）：附近是否存在其他合适的可以代替的餐

厅。

（2）吧台（&W:该餐厅是否有舒适的吧台用于等待。

（3）周五/六QFri/Sat）：今天是否为周五或周六。

（4）饥饿：现在是不是饿了。

（5）顾客（Patrons）：目前餐厅有多少顾客（值为None、Some、

Full）o

（6）价格（Price）：餐厅的价格范围（$、$$,、$$$）o

12

(7)下雨(Raining)：外面是否正在下雨。

(8)预约｛Reservation｝：我们是否有预订。

(9)种类(Type)：餐厅种类(French>Italian>Thai或

Burger)。

(10)预计等待(WaitEstimate)：对等待时间的估计(0〜10分

钟、10~30分钟、30〜60分钟^>60分钟)o

图19・2给出了一组12个样例，这些样例取自本书作者罗素(SR)的

切身经历。注意，数据量是很少的：输入属性的值一共有

26X32X42=9216种可能的组合，但是我们只得到了其中12个组合的正

确输出，其他9204个结果可能为真，也可能为假，我们并不知道c这就

是归纳的关键：我们需要通过仅有的12个样例，对缺失的9204个输出值

给出最好的猜测。

输入属性输出

样例

AlternateBarFri/SatHungryPatronsPriceRainingReservationTypeWditEstimateWillWait

司YesNoNoYesSome$$$NoYesFrench0-10y产Yes

必YesNoNoYesFull$NoNoThai30〜60h=No

•0NoYesNoNoSome$NoNoBurger0-10旷Yes

YesNoYesYesFuUSYesNoThai10-30入;Yes

YesNoYesNoFuU$$sNoYesFrench>60ys=No

•XNoYesNoYesSome$$YesYesItalian0-10犷Yes

即NoYesNoNoNone$YesNoBurger0-10X=No

七NoNoNoYesSome$$YesYesThai0-10%=Yes

两NoYesYesNoFuUsNoBurger>60b=No

•VlOYesYesYesYesFuU$$$NoYesItalian10〜30

­vnNoNoNoNoNone$NoNoThai0-10Jn-No

•V12YesYesYesYesFuU$NoNoBurger30〜60加二Yes

图19・2餐厅等待问题领域的样例

13

1.2决策树学习

决策树（decisiontree）表示了这么一类函数它将属性值向量映

射到单个输出值（即“决策”）。决策树通过执行一系列测试来实现其决

策，它从根节点出发，沿着适当的分支，直到到达叶节点为止。树中的

每个内部节点对应于一个输入属性的测试，该节点的分支用该属性的所

有可能值进行标记，叶节点指定了函数要返回的值。

通常来说，一个函数的输入与输出可以是离散的或连续的，这里我

们只考虑输入为离散值，输出为真（一个正样例）或假（一个负样例）

的函数。我们称该情形为布尔分类（Booleanclassification）0我们用字

母）来标记样例（巧代表第/个样例的输入向量，为代表该样例的输出），

此外税•代表第7个样例的第，个属性。

如图19-3所示，该树代表了SR用于餐厅等待问题的决策函数，沿着

树的分支，我们可以发现，Patrons=Full与力=0~10的样例

会被分类为正（即“yes”，我们将在餐厅等待）。

14

图19・3决定是否在餐厅等待的决策树

1.2.1决策树的表达能力

一棵布尔型的决策树等价于如下形式的逻辑语句：

Output<=>（PathxVPath2V…）

其中每个出色是从根节点到true叶节点的路径上的属性.值测试形式

（“州=L八4=%八…）的合取。因此，完整的表达式为析取范式的形

式，这意味着命题逻辑中的任何函数都可以表示为决策树。

对许多问题，决策树会给出一个漂亮、简洁、容易理解的结果。实

际上，许多内容为“如何……”的指南手册（如，汽车维修）都会按决策

树形式来撰写。但有些函数并不能被简洁地表示，例如投票函数，当且

仅当超过一半的输入为真时，它的输出为真，它需要指数量级大小的决

策树来表示；奇偶性函数也有这样的问题，当且仅当偶数个输入为真

时，它的输出为真。当输入属性为实数值时，形如歹>4+4的函数很

难用决策树表示，因为该函数的决策边界为一条对角线，而所有的决策

树将空间分割为矩形，即与坐标轴平行的方框。我们需要去堆积很多矩

形方框以逼近对角线决策边界。换句话来说，决策树对一些函数来说是

好表示的，而对另一些函数来说却是不合适的。

是否存在一种表示方式使得任何函数都能被有效地表示？遗憾的

是，答案是否定的——函数的形式过多，无法用少量的位来全部表示。

甚至即使仅仅考虑含有〃个属性值的布尔函数，真值表也会有2〃行，并

且每一行的输出有真与假两种情形，因此存在2那个不同的函数。如果属

性值是20个，那么就存在21°48576=]030000。个函数，所以如果我们把表示

限制在百万位内，我们就不能表示所有的这些函数。

1.2.2从样例中学习决策树

15

我们希望找到一棵与图19・2中的样例保持一致并尽可能小的决策

树。遗憾的是，要寻找一棵理论上最小且与样本一致的树是很困难的。

但通过一些简单的启发式方法，我们可以高效地寻找一棵与最小的树接

近的树。LEARN-DECATEEE算法采用贪心与分治的策略：我们总是首先测试

当前最重要的属性，然后递归地去解决由该测试结果可能产生的更小的

子问题。我们所说的“最重要的属性”指的是对一个样例的分类结果能产

生最大影响的属性。这样的话，我们希望通过少量的测试来得到正确的

分类结果，这意味着该树中的所有路径都比较短，整棵树的层数也比较

浅。

图19-4a表明4”是一个较差的属性，因为它的输出有4种可能，并

且每种可能中含有相同数量的正样例与负样例。另外，在图19-4b中我

们发现血疗。如是一个相当重要的属性，因为如果其值为None或者Some,

那么剩余的样例将会有准确的输出(分别为No或者Yes)；如果其属性

值为Full,仍将有混合的样例集。对于这些递归子问题，我们需要考虑

以下4个方面。

(1)如果剩余的样例全为正(或全为负)，那么我们已经达成目

标，可以输出Yes或No。图19-4b给出了例子，这种情形发生于属性值为

None和Some的分支中。

(2)如果既有正样例又有负样例，那么需要继续选择最好的属性

对样例进行分割。图19-4b中所示的是“〃咫？属性被用于分割剩余的样

例。

(3)如果分割后没有剩余的样例，则表示没有观测到该属性值组

合的样例，将返回构造该节点的父节点的样例集中最常见的输出值。

(4)如果分割后没有任何其他的属性剩余，但是存在正负诙种样

例，这意味着，这些样例有完全相同的属性值组合，但分类不同°这是

可能发生的，或是因为数据中存在错误或噪声(noise),或是因为该领

域是非确定性的，再或是因为我们无法观测到可以区分样例的属性。此

时的最好的选择就是返回剩余样例中最常见的输出值。

16

图19・4通过测试属性来对样例进行分割。在每一个节点中我们给出剩余样例的正（绿色方

框）负（红色方框）情况。（a）根据7vpe分割样例，没有为我们分辨正负带来帮助。（b）根

据&/⑶处分割样例，很好地区分了正负样例。在根据Pwmw进行分类之后，从〃吆疗是相对较好

的第二个测试属性

图19-5所示为1心力侬心1^算法。注意，样例集是算法的一个输

入，但是样例不出现在算法所返回的任何树中。一棵树由内部节点上的

属性的测试、分支上的属性值和叶节点上的输出组成。在1933节中，

我们将给出重要性函数m皿刈的细节。图19-6给出了学习算法在样本训

练集上的输出结果。该树与我们在图19-3中给出的原始树截然不同。一

些读者可能会得出这样的结论：学习算法并没有很好地学习正确的函

数。事实上，这是一个错误的结论。学习算法着眼于”卬秋如，而不是

正确的函数，从现实来看，它的假设（见医19.6）不仅与所有样例一

致，而且比原始的树简单得多！对于稍有不同的输入样例，树的形状可

能会非常不同，但它所表示的函数是相似的。

17

functionLEARN-DECisiON-TREE(examp/e5,attributes,parentexamples)returns一棵树

ifexamples不为空thenreturnPLURALiTY-VALUE(pare«/examples)

elseif所有有相同的分类thenreturn分类

elseifattributes为空thenreturnPLURALITY-VALUE(examp/e5)

else

N-argmax^皿加IMPORTANCES，examples)

tree一一个以测试J为根的新的决策树

foreachA中的值”do

exs*—{e:examplesande.A=v}

LEARN-DECISION-TREE(exs,attributes-A,examples)

将一个带有标签(4=v)和子树s〃物*ee的分支加入Zree

returntree

图19・5决策树学习算法。重要性函数IMPORTANCE将在19.3.3节中给出，函数PLURAUTY-VALU将选择

样例集中最常见的输出，并随机地断开连接

图19・6根据12样例训练集推断出的决策树

学习算法不需要包含对/?〃〃〃力g与Hesw，o/2两个属性的测试，因为

它可以在没有这两个属性的情况下对所有样例进行分类。它还发现了一

个有趣的、此前未被注意到的模式：SR会在周末等待泰国菜(Thai)o

在一些没有任何样例被观测到的情形中，决策树也必然会犯一些错误。

18

例如，决策树未观测到等待时间为0〜10分钟但餐厅已客满的情况。在

这种情况下，当”〃72g?属性值为假时，决策树的输出是No,即不等

待，但SR肯定会选择等待。如果有更多的训练样例，决策树就可以在

学习过程中纠正这个错误。

我们可以用学习曲线(learningcurve)来评估学习算法的表现，如

图19-7所示。在这个图中，有100个样例可供学习使用，我们将它们随

机分割为一个训练集和一个测试集。我们使用训练集学习假设人并用

测试集来度量具准确率。我们可以从大小为1个样例的训练集开始训练

与测试的过程，每次增加1个训练样例，直到训练集包含99个样例。对

于每种大小的训练集，我们实际操作时重复随机分割训练集和测试集的

过程20次，并对这20次试验的结果取平均值。曲线的结果表明，随着训

练集大小的增加，准确率将提高。出于这个原因，学习曲线也被称为快

乐图(happygraph)o在这张图中，准确率最终达到了95%,并且从趋

势上看，如果有更多的数据，曲线可能会继续上升。

S

t

s

图19・7一个决策树的学习曲线，数据集为从餐厅等待问题领域中随机产生的100个样例。图中

每个点都是20次试验的均值

1.2.3选择测试属性

19

决策树学习算法会选择重要性IMPORTS最高的属性。我们现在将陈述

如何使用信息增益这一概念来度量重要性。信息增益是从燧(entropy)

的角度进行定义的，而燧是信息论中最基本的量(ShannonandWeaver,

1949)o

燧是随机变量不确定性的度量；信息量越多，燧越小。一个只有一

个可能值的随机变量(如一枚总是正面朝上的硬币)没有不确定性，因

此它的焙为0。一枚公平的硬币在抛掷时出现正面或反面朝上的概率相

同，我们将证明它的燧为“1位一个公平的四面骰子的病为2位，因为

它有22种可能性相同的选择。现在考虑一枚不公平的硬币，它在99%的

情况下都是正面朝上。直觉告诉我们，这枚硬币含有的不确定性比公平

硬币要少——如果我们猜测正面朝上，只会有1%的情况是错的——所

以我们希望它有一个接近于0,但为正的嫡。一般情况下，若一个随机

变量V取值为以的概率为P(%)，那么它的焙"(V)定义为

“(%)=2尸(以)唳2

我们可以验证一枚公平硬币被抛掷的燧确实是1位:

H(Fair)="(0.5log20.5+0.5log20.5)=1

而一个四面骰子的燧是2位：

H(Die4)=-(0.25log20.25+0.25log20.25+0.25log20.25+0.25log20,25)=2

对于99%的情况出现正面的硬币，有

H(Loaded)=一(0.99log20.99+0.01log20.01)^0.08位

一个布尔随机变量，如果其为真的概率是4，则该变量的端以夕)定

义为

B(q)=-(qlog2g+(l-g)log2(l-<7)]

因此，H(Loaded)=5(0.99)-0.08o现在我们回过头来看决策树的

学习。如果一个训练集包含p个正样例和〃个负样例，则在整个集合上的

输出变量的燧为

20

II{Output)=B

\p+〃)

在图19-2所示的餐厅训练集中，有p=n=6,因此相应的燧

是8(0.5),或恰好为1位。对属性A的测试结果会给我们提供一些信息，

从而减少一些整体的烯。我们可以通过观察属性测试后剩余的端来度量

这种减少。

若一个具有d个不同值的属性A将训练集取J分为子集丹,…，Ed，每

个子集既含有以个正样例与在个负样例，那么如果我们沿着该分支前

进，将需要额外的80/0+%))位的信息来处理问题。从训练集中随机

选取一个样例，它具有该属性的第2个值(即该样例在颐中的概率为

仍无+%)/3+〃))，因此在测试属性A后剩余的端的期望为

Remainder(A)=£久土风B———

普P+〃\Pk^nk)

通过测试属性A获得的信息增益(informationgain)定义为燧减少

的期望值：

Gain(A)=B———-Remainder{A}

\P^n)

事实上，Gc”〃(A)正是我们实现重要性函数IMPORTANO•:需要的。回顾图

19-4中所考虑的属性，有

Gain(Patrons)-1--B[^~+—5-^+—5b0.541位

1212UJ12

=1--2-D\一=0位

Gain(Type)12⑶

这证实了我们的直觉，即7s最适合作为优先考虑的分割属性。

事实上，在所有的属性中有最大的信息增益，因此将被决策树学

习算法选择作为树的根。

21

1.2.4泛化与过拟合

我们希望我们的学习算法找到一个能够吻合训练数据的假设，但更

重要的是，我们希望它能很好地推广到还没有被观测到的数据上。在图

19-1中我们看到，一个高阶多项式可以拟合所有数据，但它在拟合数据

时有不合理的剧烈波动：它拟合了数据，但可能发生过拟合。随着属性

数量的增加，过拟合的可能性将越来越大，而随着训练样例数量的增

加，过拟合的可能性会越来越小。较大的假设空间(例如，具有更多节

点的决策树或具有更高阶数的多项式空间)具有更强的拟合和过拟合能

力，某些模型类比其他模型类更容易过拟合。

对决策树来说，一种称为决策树剪枝(decisiontreepruning)的技

术可以用于减轻过拟合。剪枝通过删去不明显相关的节点来实现，我们

从一棵完整的树出发，它由L叩N-DK^ON-TREE生成。接着我们研究一个只有

叶节点作为子节点的测试节点，如果该节点的测试效果为不相关——它

只测试数据中的噪声——那么我们将删去该测试节点，并用它的叶节点

替换它。重复这个过程，考虑每个只有叶节点作为子节点的测试节点，

直到每个测试节点都被剪枝或按原样接受。

现在的问题是如何判断一个节点所测试的属性是否是不相关的属

性。假设我们目前所考虑的节点由〃个正样例和〃个负样例组成。如果该

节点测试的属性是不相关的，那么在我们的预期中，该测试会将样例分

割成多个子集，使得每个子集的正样例的比例与整个集合的比例〃/(〃+

〃)大致相同，因此信息增益将接近于0。团因而，低信息增益是判断属

性是否不相关的一个很好的方法。现在的问题是，我们需要多大的增益

才能在特定属性上进行分割？

1—1

131这个增益将恒为正数，除了所有的比例都完全相同的情形(不太常见)。(见习题

I9.NNGA.)

我们可以用统计学中的显著性检验(significancetest)来回答这个

问题。该检验首先假设不存在基础的模式[所谓的零假设(null

hyphothesis)],然后对实际数据进行分析，并计算它们偏离零假设的

程度。如果偏离程度在统计上不太可能发生(通常我们取5%或更低的

概率作为阈值)，那么这在一定程度上证明了数据中仍存在显著的模

式。其中概率将根据随机抽样中偏差量的标准分布计算得到。

22

在这种情况下，相应的零假设是该属性是不相关的，因此对于一个

无限大的样本集而言，信息增益将为0。我们需要计算的概率是在零假

设下，一个大小为"=〃+，的样本集所呈现的与正负样例的期望分布的

偏离状况的概率。我们可以通过比较每个子集中的正负样例的实际数量

P大和以与假设该属性不相关情形下的期望数量由f口谏衡量这一偏差：

见+%

X勺二〃x

Pk=Pp+〃

下式给出总偏差的一个简洁形式:

他-瓦A"-瓦）2

Z1—，//ATA

IAkP久

在零假设下，/将服从1个自由度的/分布（卡方分布）。我们

可以使用％2统计量来判断一个特定的八值是接受还是拒绝了零假设。例

如，餐厅的属性有4个值，因此分布有3个自由度。在5%的置信水

平下，总偏差A=7.82或更大的值将拒绝零假设（在1%的置信水平下，

4=11.35或更大的值将拒绝零假设）。低于阈值的偏差值会让我们接受

属性不相关这一零假设，因此树的相关分支应该被剪枝。这个方法被称

为"剪枝（3pruning）。

有了剪枝的技术，我们允许样例中存在噪声。样例标签中的错误

（例如，一个样例（X,No）被误标为（X,Yes））会使预测误差线性地增加，

向样例描述中的错误（例如，样例的实际属性/Vice=$$被误标记

Price对误差具有渐近的影响，随着树收缩在更小的集合上运作，

这种影响会变得更糟。当数据具有较大的噪声时，经过剪枝的树的性能

将明显优于未剪枝的树。而且经过剪枝的树通常要小得多，因此更容易

被理解，调用也更有效率。

最后一个需要提醒的地方：我们可能会认为/剪枝和信息增益看起

来很类似，那么为什么不使用一种被称为提前停止（earlystopping）的

方法将它们合并起来，即让决策树算法在没有好的属性来继续进行分割

时停止生成节点，而不是平添麻烦地生成完所有不必要的节点，然后再

将它们修剪掉呢？提前停止法的问题在于，它在我们找不出任何一个好

的属性时即停止了程序，但有一些属性需要相互组合才会含有信息并发

挥效果。例如，考虑含有两个二值属性的XOR函数，如果输入值的4种

23

组合的样例数大致相等，那么这两个属性都不具有显著的信息，但正确

的做法是先基于其中一个属性（不论是哪一个）进行分割，然后在下一

个分割阶段，我们将得到非常有信息量且效果很好的分割。提前停止法

可能会错过这一点，但是“先生成后剪枝''的方式可以正确地处理这种情

况。

1.2.5拓展决策树的适用范围

通过处理以下复杂情况，决策树可以得到更广泛的应用。

•缺失数据：在许多问题领域中，并非每个样例的所有属性都是已

知的。这些值可能没有被记录，也可能因获得它们的代价太大而无法获

得。这就产生了两个问题：首先，给定一棵完整的决策树，对于缺少一

个测试属性的样例，应该如何将它分类？其次，当一些样例的属性值未

知时，应该如何修改信息增益公式？这些问题留于习题19.MISS。

•连续属性与多值输入属性：对于连续属性（如身高、体重或时

间），可能每个样例都有不同的属性值。用信息增益来衡量属性将导致

这样的属性得到理论上最高的信息增益，最终给出一棵以该属性为根的

浅层树，其中每个可能值对应一个单样例子树。但是当我们需要对一个

新的样例进行分类，且样例的该属性值并没有被观测过时，这棵树对我

们没有帮助。

处理连续值的一个更好的方法是采用分割点（splitpoint）测试——

一个关于属性值的不等式测试。例如，在树中的一个给定节点上，体重

>160的测试可能会提供最多的信息。找到好的分割点的有效方法是：

首先对属性的值进行排序，然后只考虑将具有不同分类结果的两个相邻

样例之间的值作为可能的分割点，同时以分割点得到的正负样例作为新

样例继续算法。分割的实现是实际决策树学习应用中代价最高的部分。

对于不连续的或者排序没有意义的，但有大量可能值的属性（例如

邮政编码或者信用卡号码），可以使用一种称为信息增益比

（informationgainratio）（见习题19.GAIN）的度量方法来避免算法将

树分割成许多单样例子树。另一个有效的方法是采用形如A="的等式

进行测试。例如，测试邮政编码=10002,可以在纽约市挑选出这个邮

24

政编码下的一大群人，然后将其他所有人归并到“其他”子树中。

•连续值输出属性：如果要预测一个数值类型的输出，那么我们需

要的是一棵回归树(regressiontree),而不是一棵分类树。回归树在每

个叶节点上都有一个关于数值属性子集的线性函数，而不是一个单一的

输出值。举个例子来说，两居室公寓的价格最终可能以一个关于占地面

积和浴室数量的线性函数输出。学习算法必须能够决定何时停止对树进

行分割并开始对属性应用线性回归(见19.6节)。CART这个名字代表

分类与回归树(ClassificationAndRegressionTree),用于涵盖这两个

类别的树。

一个面向实际应用的决策树学习系统必须能够处理所有这些问题。

处理连续值变量尤其重要，因为物理过程和金融过程所提供的都是数值

数据。现实应用中已经出现了一些符合这些标准的商业软件包，并已用

于开发数千个部署系统。在工业和商业的许多领域中，决策树仍是从数

据集中寻找分类方法的首要方法。

决策树有很多优点：易于理解.，可推广到大型数据集，处理离散输

入和连续输入及分类和回归问题的多功能性。然而，它们的精确度可能

是次优的(主要是由贪心搜索导致)，并且如果树很深，那么在调用树

为一个新的样例进行预测时可能会有昂贵的运行代价。决策树也是不稳

定的(unstable),因为仅添加一个新的样例，就可能更改根上的测试

结果，从而更改整个树。在19.8.2节中，我们将看到随机森林模型

(randomforestmodel)可以解决这些问题中的一部分。

25

1.3模型选择与模型优化

在机器学习中，我们的目标是选择一个和未来的样例最佳拟合的假

设。要做到这一点，我们需要定义“未来的样例”和“最佳拟合九

首先，我们假设未来的样例类似于过去观测过的样本。我们称之为

平稳性(stationary)假设；若没有它，所有的方法都没有意义。我们假

设每个样例弓都具有相同的先验概率分布：

产(场=P(J)=尸(%2)=…

而且它与之前的样例是独立的：

尸(4)=尸闯65辱2,…)

对于满足这些等式的样例，我们称它们为独立同分布的或i.i.d.o

下一步是定义“最佳拟合我们说最佳拟合是最小化错误率(error

rate)——对于样例(x,y),万(幻左歹的比例——的假设。(稍后我们将对

此内容进行推广，以允许不同的误差具有不同的代价，实际上倾向于信

任“几乎”正确的答案。)我们可以通过对一个假设进行测试来估计其错

误率：在一组称为测试集的样例上评估它的表现。一个假设(或一个学

生)在测试前偷看答案属于作弊行为。为确保这种情况不会发生，最简

单的方法是将我们拥有的样例分割成两组：一组为用于训练从而得到假

设的训练集，另一组为用于评估假设的测试集。

如果我们只想建立一个假设，那么这个方法就足够了。但通常我们

最终会得到多个假设：我们可能想要比较两个完全不同的机器学习模

型，或者我们可能想要在同一个模型中调整不同的“旋钮例如，在％2

剪枝中我们可以尝试不同的阈值对决策树进行剪枝，或者尝试不同次数

的多项式。我们称这些“旋钮”为超参数(hyperparameter),它们是对

模型类而言的，而不是对单个模型。

假设一个研究者在一组/剪枝的超参数中训练出一个假设，并在测

试集上测试了其错误率，然后继续尝试不同的超参数。没有任何一个单

独的假设“偷看”或使月了测试集的数据，但整个过程通过研究者还是泄

26

露了测试集的信息。

避免这种依赖性的方法是将测试集完全锁定——直到你完全完成了

训练、实验、超参数调整、再训练这一系列过程。这意味着你需要3个

数据集。

(1)训练集用于训练备选模型。

(