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

人工智能机器算法样例学习目录1学习的形式51.1 监督学习81.2 决策树学习141.2.1 决策树的表达能力151.2.2 从样例中学习决策树151.2.3 选择测试属性191.2.4 泛化与过拟合22125拓展决策树的适用范围241.3 模型选择与模型优化261.3.1 模型选择28132从错误率到损失函数301.3.3 正则化33134超参数调整341.4 学习理论361.5 线性回归与分类421.5.1 单变量线性回归421.5.2 梯度下降441.53多变量线性回归471.1.4 带有硬阈值的线性分类器501.1.5 基于逻辑斯谛回归的线性分类器541.6 非参数模型581.6.1 最近邻模型581.6.3 局部敏感哈希62非参数回归631.6.5支持向量机651.6.6 核技巧701.7 集成学习721.7.1 自助聚合法731.7.2 随机森林法741.7.3 堆叠法761.7.4 自适应提升法761.7.5 梯度提升法811.7.6 在线学习821.8 开发机器学习系统851.8.1 问题形式化851.8.2 数据收集、评估和管理861.8.3 模型选择与训练911.8.4 信任、可解释性、可说明性931.8.5 操作、监控和维护95小结98我们用样例学习来描述智能体通过不断学习自己以往的经验从而改善自己的行为，并对未来进行预测的过程。如果一个智能体通过对世界进行观测来提高它的性能，我们称其为智能体学习(learning)0学习可以是简单的，例如记录一个购物清单，也可以是复杂的，例如爱因斯坦推断关于宇宙的新理论。当智能体是一台计算机时，我们称之为机器学习(machinelearning)：一台计算机观测到一些数据，基于这些数据构建一个模型(model),并将这个模型作为关于世界的一个假设(hypothesis)以及用于求解问题的软件的一部分。为什么我们希望一台机器进行学习？为什么不通过合适的方式编程然后让它运行呢？这里有两个主要的原因。其一，程序的设计者无法预见未来所有可能发生的情形。举例来说，一个被设计用来导航迷宫的机器人必须掌握每一个它可能遇到的新迷宫的布局；一个用于预测股市价格的程序必须能适应各种股票涨跌的情形。其二，有时候设计者并不知道如何设计一个程序来求解目标问题。大多数人都能辨认自己家人的面孔，但是他们实现这一点利用的是潜意识，所以即使能力再强的程序员也不知道如何编写计算机程序来完成这项任务，除非他使用机器学习算法。学习的形式一个智能体程序的各个组件都可以通过机器学习进行改进。改进及用于改进的技巧取决于下面几个因素：哪些组件可以被改进；智能体有哪些先验知识，这将影响模型构建；有哪些数据，以及关于这些数据的反馈。第2章中描述了一些智能体的设计。这些智能体的组件包括：（1）从当前状态条件到动作的直接映射；（2）用于从感知序列推断世界相关性质的方法；（3）关于世界演化方式的信息，以及关于智能体可以采取的可能动作所导致的结果的信息；（4）表示状态意向的效用信息；（5）表示动作意向的动作价值信息；（6）最希望达到的状态，即目标；（7）问题生成器、评判标准和使系统得以改进的学习元素。这些组件中的任何一个都可以被学习到。我们设想一个可以通过观测人类司机行为来学习自动驾驶的汽车智能体。每次司机刹车时，这个智能体可以学习到一个关于什么时候该踩刹车的条件动作规则（组件1）o通过观察大量包含公共汽车的照相机图像，它可以学习到如何辨认公共汽车（组件2）。通过尝试不同动作以及观测相应的结果（例如在潮湿的道路上艰难地刹车），它可以学习到动作相应的结果（组件3）o接着，如果它收到在旅途中被剧烈颠簸吓坏了的乘客们的抱怨，它可以学习到关于其总体效用函数的一个有效组件（组件4）。机器学习技术已经成为软件工程的标准组成部分。无论何时你想搭建一个软件系统，即使你不认为它是一个人工智能主体，这个系统的组件也可能可以用机器学习的方式加以改进。例如，一个用于分析星系在引力透镜下的图像的软件可以通过机器学习的模型加速一千万倍(HezavehGal2017)；通过采用另一种机器学习的模型可以将数据中心冷却的能耗降低40%(Gao,2014)0图灵奖得主大卫帕特森(DavidPatterson)和谷歌Al的掌门人杰夫迪安(JeffDean)宣称，计算机体系结构的“黄金时代”的到来正归功于机器学习(Deanetal.2018)0我们已经见过了一些关于智能体组件的模型示例：原子模型、因子化模型，以及基于逻辑的关系模型或基于概率的关系模型等。人们针对所有这些模型设计了广泛的学习算法。本文中我们假设不存在关于这个智能体的先验知识(Priorknowledge)：它从零开始，从数据中学习。在21.7.2节中，我们将考虑迁移学习(transferlearning),在这种情形下，一个领域的知识被迁移到一个新的领域，以更少的数据使学习过程进行得更快。我们当然还要假设系统的设计者选取了合适的模型框架，从而让学习过程变得更加有效。从一组特定的观测结果得出一个普遍的规则，我们称之为归纳(induction)o例如，我们观察到，过去的每一天太阳都会升起，因此我们推断太阳明天也会升起。这与我们在第7章中研究的演绎(deduction)不同，因为归纳的结论可能是不正确的，然而在演绎中，只要前提是正确的，演绎的结论就保证是正确的。本文将集中讨论输入为因子化表示(factoredrepresentation)属性值组成的向量的问题。输入也可以是任意类型的数据结构，包括原子表示的数据和关系数据等。当输出是一个有限集合中的某个值时(如晴天/阴天/雨天或者正确/错误)，我们称该学习问题为分类(ClaSSifiCation)。当输出是一个数值时(例如明天的温度，无论它是一个整数还是其他实数)，我们称该学习问题为回归(regression)(这个词有些晦涩难懂山)。ri一个更好的名称是函数遢近或者数值预刑。但在1886年，法国人弗朗西斯高尔顿(FranCiSGalton)写了一篇关于这一概念的富有影响力的文章regreSSiMfothemean(例如，高个子父母的孩子很可能身高高于平均值，但没有父母那么高）。高尔顿用他所称的“回归线''给出了一些困，之后读者逐渐把“回归”一词与函数逼近这一统计技术联系起来，而不是与回归于均值的主题联系起来。伴随输入有3种类型的反馈（feedback）,它们决定了3种类型的学习。在监督学习（SUPerViSedlearning）中，智能体观测到输入-输出对，并学习从输入到输出的一个函数映射。举个例子来说，输入是照相机的图像，伴随输入的输出就是“公共汽车”或者“行人”等。诸如此类的输出，我们称之为标签（Iabe1）。在智能体学习到一个函数之后，如果给它一个新的图像输入，它将预测一个合适的标签。对于踩刹车这一动作的学习（上述的组件1）,其输入是当前的状态（车的速度和行驶方向、道路条件），输出是开始刹车到停车所需要行驶的距离。在这种情形下，智能体可以直接从自己的感知中获得输出值（在动作结束之后）；环境就是老师，智能体学习的是从当前状态到刹车距离的一个函数。在无监督学习（UnSUPerViSedlearning）中，智能体从没有任何显式反馈的输入中学习模式。最常见的无监督学习任务是聚类（clustering）：通过输入样例来检测潜在的有价值的聚类簇。例如，我们从互联网上可以获取数百万个图像，一个计算机视觉系统可以识别一大类相似的、被人类称为“猫”的图像。在强化学习（reinforcementlearning）中，智能体从一系列的强化-奖励与惩罚中进行学习。举例来说，在一局国际象棋比赛结束时，智能体会被告知它赢了（奖励）还是输了（惩罚）。智能体判断之前采取的哪个动作该为这一结果负责，并且改变它的动作以在未来得到更多的奖励。1.1监督学习更正式地说，监督学习的任务如下。给定一个训练集(trainingset)含有N个“输入.输出”对样例：(再，M),(%,%),Gd其中每一对数据都由一个未知的函数N=危)生成，寻找一个函数力来近似真实的函数A函数力被称为关于世界的假设(hypothesis)。它取自一个假设空间(hypothesisspace)H,其中包含所宥可能的函数。例如，这个假设空间可能是最高次数为3的多项式集合、JaVaSCriPt函数的集合，也可能是所有3-SAT布尔逻辑公式的集合。同样地，我们可以称人是关于数据的模型，它取自模型类(modelclass)H,也可以说它取自函数类(functionclass)中的一个函数(function)。我们称输出y为真实数据(groundtruth)我们希望模型能预测的正确答案。那么，如何选择一个假设空间呢？我们可能有一些关于数据生成过程的先验知识。如果没有的话，可以采用探索性数据分析(exploratorydataanalysis)：通过统计检验和可视化方法直方图、散点图、箱形图来探索数据以获得对数据的一些理解，以及洞察哪些假设空间可能是合适的。或者我们可以直接尝试多种不同的假设空间，然后评估哪个假设空间的效果最好。有了假设空间后，如何从中选择一个好的假设呢？我们希望寻找一个一致性假设(ConSiStenthypothesis)：假设对训练集中的任意一个知都有(幻=为。如果输出是连续值，我们不能期望模型输出与真实数据精确匹配；相反，我们可以寄希望于寻找一个最佳拟合函数(best.fitfunction),使得每一个/Iaj)与力非常接近(我们将在19.4.2节中给出正式表述)。衡量一个假设的标准不是看它在训练集上的表现，而是取决于它如何处理尚未观测到的输入。我们可以使用一个测试集(testset)第二组样本数据对(修,来评估假设。如果Zz准确地预测了测试集的输出，我们称具有很好的泛化(generalize)能力。图19展示了一个学习算法所得到的函数人依赖于假设所考虑的假设空间H和给定的训练集。第一行的4幅图使用同一个训练集，训练集中包含13个(y)平面上的数据点。第二行的4幅图使用第二组由13个数据点组成的训练集；两个训练集都代表了某个未知的函数/(x)。每一列展示了不同假设空间中的最佳拟合假设鼠 列L直线；形如(X)=W$的函数。对于这些数据点，不存在一致性假设的直线。线性模型正弦函数模刷分段线性模型被而次数为12的多项式图191寻找拟合数据的假设。第一行：在数据集1上训练的来自4个不同假设空间的最佳拟合函数的4个图像。第二行：同样的4个函数，但是在稍有不同的数据集上进行训练得到的结果(数据集采样自相同的函匆口) 列2：形如MX)=WJ+sin(M)的正弦函数。这个假设并不是完全一致的，但是将两个数据集都拟合得非常好。 列3：分段线性函数，其中每一条线段从一个数据点连接到下一个数据点。这类函数永远是一致的。A(x)=Vw,x7列4：形如士的12次多项式。这类函数是一致的：我们总是能找到一个12次 多项式来准确地拟合13个不同点。但是假设是一致的并不意味着这是一个好的预测。分析假设空间的一个方法是分析它们带来的偏差(不考虑训练集)和它们产生的方差(从一个训练集到另一个训练集)。我们所说的偏差(bias)是指(不严格地)在不同的训练集上，假设所预测的值偏离期望值的平均趋势。偏差常常是由假设空间所施加的约束造成的。例如，当假设空间是线性函数时会导致较大的偏差：它只允许函数图像是一条直线。如果数据中除了直线的整体斜率以外还存在别的模式，线性函数将无法表示其他的模式。当一个假设不能找到数据中的模式时，我们称它是欠拟合(Underfitting)的。但是，分段线性函数具有较小的偏差，其函数的形状是由数据决定的。我们所说的方差(variance)是指由训练数据波动而导致假设的变化量。图19-1的两行所使用的数据集采样于同一个函数两个数据集略有不同。对前三列函数来说，数据集的略微不同导致的假设差别比较小，我们称之为低方差的。但是第4列中的12次多项式函数则具有较大方差：可以看到它们在轴两端的表现差别很大。显然，这两个多项式中至少有一个多项式对正确的函数/U)的拟合效果较差。当一个函数过于关注它用来训练的特定训练数据集，进而导致它在没有见过的数据上表现较差时，我们称该函数对数据集是过拟C(overfitting)的。通常这其中存在一个偏差方差权衡(biasvariancetradeoff)：在更复杂、低偏差的能较好拟合训练集的假设与更简单、低方差的可能泛化得更好的假设中做出选择。阿尔伯特爱因斯坦(AlbertEinstein)曾于1933年说过，“任何理论的终极目标都是尽可能让不可削减的基本元素变得更加简单且更少，但也不能放弃对任何一个单一经验数据的充分阐释换句话说，爱因斯坦建议选择与数据相符的最简单的假设。这个原则可以追溯到14世纪的英国哲学家奥卡姆的威廉(WilliamofOCkham),他的原则“如无必要，勿增实体”被称为奥卡姆剃刀原则(0ckham,srazor)，因为它被用来“剔除”含糊的解释。121这个名字经常被错误拼写为“Occam”。奥卡姆是英国一座小镇的名字，是威廉出生的地方。他在牛津大学注册时用的名字是“奥卡姆的威廉”，后来人们习惯性地把他提出的观点概括地称为“奥卡姆剃刀原则”。编者注定义简单性并不容易。显然，只有两个参数的多项式比有13个参数的多项式简单。在1934节中，我们将更加精确具体地表述这种直觉。然而，在第21章中，我们将会看到，深度神经网络模型往往可以泛化得非常好，尽管它们非常复杂其中有些网络的参数达到数十亿个。所以，仅通过参数个数本身来衡量模型的适合程度并不是一个好方法。因此我们或许应该将目标定为选择“合适”而不是“简单”的模型类。我们将在19.4.1节中考虑这个问题。在图19-1中，我们并不确定哪个假设是最佳的。如果我们知道数据所表示的内容，例如，一个网站的点击量每天都在增长，并且会根据一天的时间周期性变化，那么我们可能会更倾向于选择正弦函数。如果我们知道数据不是周期性的并且存在较大的噪声，那么我们可能倾向于选择线性函数。在某些情形下，相比于仅仅判断一个假设是可能还是不可能的，分析者更愿意给出一个假设可能发生的概率。监督学习可以通过选择假设*(在数据集上*发生概率最大)来实现：A*=argmaxP(hdata)*4=T根据贝叶斯法则，上式等价于：ft*=argmaxP(datah)P(h)于是我们可以认为，光滑的一次或二次多项式的先验概率尸)是较高的，而有较大波动的12次多项式的先验概率是较低的。当数据表示我们确实需要使用一些不寻常的函数进行拟合时，我们也可以使用这些不寻常的函数，但我们通过赋予它们一个较低的先验概率来尽可能避免这种情况。为什么我们不将H取为所有计算机程序或所有图灵机构成的类呢？这里存在一个问题，在假设空间的表达能力与在该假设空间中寻找一个合适的假设所需的计算复杂性之间存在一种权衡。举例来说，根据数据拟合一条直线是易于计算的；然而拟合一个高次的多项式则较为困难；拟合一个图灵机则是不可判定的。我们倾向于选择简单假设空间的第二个原因是，我们可能会在学习完/1后使用它，当是一个线性函数时，计算Zz(X)是很快的，然而计算任意的图灵机程序甚至不能保证程序终止。基于这些原因，大多数关于学习的工作都集中在简单的表示上。近年来，人们对深度学习产生了极大的兴趣(第21章)，它对函数的表示并不简单，但是以龙)仍然只需使用适当的硬件进行有限步的计算就可以得到。我们将看到，表达能力与复杂性的权衡并不简单：正如我们在第8章一阶逻辑中所看到的，通常情况下，表达性语言使简单的假设能够与数据相匹配，而限制语言的表达能力则意味着任何一致性假设都必定是复杂的。问题示例：餐厅等待问题我们将详细描述一个监督学习问题的例子：决定是否在一家餐厅等待位置的问题。这个问题将贯穿整章，用于比较不同的模型类。在这个问题中，输出y是一个布尔变量，我们将其称为是否等待(WV/W")；当我们决定在餐厅等待位置时它的值为真。输入冗是有10个属性值的向量，每个属性都是离散的值。(1)候补G4Ce)：附近是否存在其他合适的可以代替的餐厅。(2)吧台(r)：该餐厅是否有舒适的吧台用于等待。(3)周五/六(Fri/Sat)：今天是否为周五或周六©(4)饥饿(H忧几gry)：现在是不是饿了。(5)顾客(PeltrOnS)：目前餐厅有多少顾客(值为NOne、Some>Full)o(6)价格(PriCe):餐厅的价格范围($、$,、$)o(7)下雨(Raining)：外面是否正在下雨。(8)预约Reservation：我们是否有预订。(9)种类(TyPe)：餐厅种类(French、Italian>Thai或Burger)。(10)预计等待(WCIitEStimate)：对等待时间的估计(010分钟、1030分钟、3060分钟或>60分钟)。图192给出了一组12个样例，这些样例取自本书作者罗素(SR)的切身经历。注意，数据量是很少的：输入属性的值一共有26×32×42=9216种可能的组合，但是我们只得到了其中12个组合的正确输出，其他9204个结果可能为真，也可能为假，我们并不知道。这就是归纳的关键：我们需要通过仅有的12个样例，对缺失的9204个输出值给出最好的猜测。样例AlternateBarFri/SatHungry1Patrons输入属性PriceRainingReservationpWaitEstimate输出WillWait司NoNoSome$S$NoFrench0-10=电NoNoYesFuU$NoNoThai30-60X=No/NoYesNoNoSome$NoNoBurger0-10%二%sV4NoYesFuU$NoThai10-30JX=YesV5YesNoYesNoFullSSSNoFreth>60K=NOV6NoYesNoSome$YesItahan0-10=NoYesNoNoNone$YesNoBurger0-10X=No玉NoNoNoSome$YesYesThai0-10M=YeS两NoYesYesNoFull$YesNoBurger>60M=NoYesYesYesFuU$NoItalian10-30ho=No甬】NoNoNoNoNone$NoNoThai0-10JH=NO×nYesYesYesYesFuU$NoNoBurger30-60Jn=Yes图19-2餐厅等待问题领域的样例1.2决策树学习决策树（decisiontree）表示了这么一类函数它将属性值向量映射到单个输出值（即“决策D。决策树通过执行一系列测试来实现其决策，它从根节点出发，沿着适当的分支，直到到达叶节点为止。树中的每个内部节点对应于一个输入属性的测试，该节点的分支用该属性的所有可能值进行标记，叶节点指定了函数要返回的值。通常来说，一个函数的输入与输出可以是离散的或连续的，这里我们只考虑输入为离散值，输出为真（一个正样例）或假（一个负样例）的函数。我们称该情形为布尔分类（Booleanclassification）o我们用字母）来标记样例（弓代表第/个样例的输入向量，”代表该样例的输出），此外肛代表第/个样例的第i个属性。如图19-3所示，该树代表了SR用于餐厅等待问题的决策函数。沿着树的分支，我们可以发现，Patrons=FUII与WaifElS用&fe=010的样例会被分类为正（即“yes”，我们将在餐厅等待）。图193决定是否在餐厅等待的决策树1.2.1 决策树的表达能力一棵布尔型的决策树等价于如下形式的逻辑语句：Output<（PathxVPath1V）其中每个4也是从根节点到true叶节点的路径上的属性-值测试形式（4H=LA4=匕A）的合取。因此，完整的表达式为析取范式的形式，这意味着命题逻辑中的任何函数都可以表示为决策树。对许多问题，决策树会给出一个漂亮、简洁、容易理解的结果。实际上，许多内容为“如何”的指南手册（如，汽车维修）都会按决策树形式来撰写。但有些函数并不能被简洁地表示，例如投票函数，当且仅当超过一半的输入为真时，它的输出为真，它需要指数量级大小的决策树来表示；奇偶性函数也有这样的问题，当且仅当偶数个输入为真时，它的输出为真。当输入属性为实数值时，形如y>4+4的函数很难用决策树表示，因为该函数的决策边界为一条对角线，而所有的决策树将空间分割为矩形，即与坐标轴平行的方框。我们需要去堆积很多矩形方框以逼近对角线决策边界。换句话来说，决策树对一些函数来说是好表示的，而对另一些函数来说却是不合适的。是否存在一种表示方式使得任何函数都能被有效地表示？遗憾的是，答案是否定的函数的形式过多，无法用少量的位来全部表示。甚至即使仅仅考虑含有个属性值的布尔函数，真值表也会有2行，并且每一行的输出有真与假两种情形，因此存在2?”个不同的函数。如果属性值是20个，那么就存在204"76j03OOOM个函数，所以如果我们把表示限制在百万位内，我们就不能表示所有的这些函数。1.2.2 从样例中学习决策树我们希望找到一棵与图192中的样例保持一致并尽可能小的决策树。遗憾的是，要寻找一棵理论上最小且与样本一致的树是很困难的。但通过一些简单的启发式方法，我们可以高效地寻找一棵与最小的树接近的树。LARNQc"TREE算法采用贪心与分治的策略：我们总是首先测试当前最重要的属性，然后递归地去解决由该测试结果可能产生的更小的子问题。我们所说的“最重要的属性''指的是对一个样例的分类结果能产生最大影响的属性。这样的话，我们希望通过少量的测试来得到正确的分类结果，这意味着该树中的所有路径都比较短，整棵树的层数也比较浅。图19-4a表明TyPe是一个较差的属性，因为它的输出有4种可能，并且每种可能中含有相同数量的正样例与负样例。另外，在图19-4b中我们发现Pa次MS是一个相当重要的属性，因为如果其值为None或者Some,那么剩余的样例将会有准确的输出（分别为NO或者YeS）；如果其属性值为Full,仍将有混合的样例集。对于这些递归子问题，我们需要考虑以下4个方面。（1）如果剩余的样例全为正（或全为负），那么我们已经达成目标，可以输出YeS或No。图19-4b给出了例子，这种情形发生于属性值为None和SOme的分支中。（2）如果既有正样例又有负样例，那么需要继续选择最好的属性对样例进行分割。图19-4b中所示的是从mgy属性被用于分割剩余的样例。（3）如果分割后没有剩余的样例，则表示没有观测到该属性值组合的样例，将返回构造该节点的父节点的样例集中最常见的输出值。（4）如果分割后没有任何其他的属性剩余，但是存在正负两种样例，这意味着，这些样例有完全相同的属性值组合，但分类不同。这是可能发生的，或是因为数据中存在错误或噪声（noise）,或是因为该领域是非确定性的，再或是因为我们无法观测到可以区分样例的属性。此时的最好的选择就是返回剩余样例中最常见的输出值。DElBElISQBQElQ11(b；(a)图194通过测试屈性来对样例进行分割。在每一个节点中我们给出剩余样例的正（绿色方框）负（红色方框）情况。（a）根据TyPe分割样例，没有为我们分辨正负带来帮助。（b）根据P4"Ms分割样例，很好地区分了正负样例。在根据ParraM进行分类之后，是相对较好的第二个测试属性图195所示为LHARNDeC"TREE算法。注意，样例集是算法的一个输入，但是样例不出现在算法所返回的任何树中。一棵树由内部节点上的属性的测试、分支上的属性值和叶节点上的输出组成。在1933节中，我们将给出重要性函数5RTANCE的细节。图19-6给出了学习算法在样本训练集上的输出结果。该树与我们在图19-3中给出的原始树截然不同。些读者可能会得出这样的结论：学习算法并没有很好地学习正确的函数。事实上，这是一个错误的结论。学习算法着眼于emmp/es,而不是正确的函数，从现实来看，它的假设（见图19-6）不仅与所有样例一致，而且比原始的树简单得多！对于稍有不同的输入样例，树的形状可能会非常不同，但它所表示的函数是相似的。functionLERN-DEsN-TREE(xampeattributes,parentexamples)returns一棵树ifexamples不为空thenreturnPlurality-VALVE(pa/iezirexamples)elseif所有exmey有相同的分类thenreturn分类elseif(ItiribUteS为空thenreturnPLURALrrY-VALUE(exmpes)elseA*-argmaxenriftwejIMPORTANCE(,examples)tree一一个以加以为根的新的决策树foreach力中的值ydoexs-e:eeexamplesande.A-vSvBrree-LEARN-DECisiON-TREE(exs,attributes-A,examples)将一个带有标签(N=y)和子树S血We的分支加入夕eereturntree图19-5决策树学习算法。重要性函数IMPORTANCE将在19.3.3节中给出,函数PLURAuTY-VAwE将选择样例集中最常见的输出，并随机地断开连接图1%6根据12样例训练集推断出的决策树学习算法不需要包含对RainingReservation个属性的测试，因为它可以在没有这两个属性的情况下对所有样例进行分类。它还发现了一个有趣的、此前未被注意到的模式：SR会在周末等待泰国菜(Thai)o在一些没有任何样例被观测到的情形中，决策树也必然会犯一些错误。例如，决策树未观测到等待时间为010分钟但餐厅已客满的情况。在这种情况下，当从属性值为假时，决策树的输出是N。，即不等待，但SR肯定会选择等待。如果有更多的训练样例，决策树就可以在学习过程中纠正这个错误。我们可以用学习曲线(learningcurve)来评估学习算法的表现，如图19-7所示。在这个图中，有I(X)个样例可供学习使用，我们将它们随机分割为一个训练集和一个测试集。我们使用训练集学习假设，并用测试集来度量其准确率。我们可以从大小为1个样例的训练集开始训练与测试的过程，每次增加1个训练样例，直到训练集包含99个样例。对于每种大小的训练集，我们实际操作时重复随机分割训练集和测试集的过程20次，并对这20次试验的结果取平均值。曲线的结果表明，随着训练集大小的增加，准确率将提高。出于这个原因，学习曲线也被称为快乐图(happygraph)o在这张图中，准确率最终达到了95%,并且从趋势上看，如果有更多的数据，曲线可能会继续上升。图1%7一个决策树的学习曲线，数据集为从餐厅等待问题领域中随机产生的100个样例。图中每个点都是20次试验的均值1.23选择测试属性决策树学习算法会选择重要性U)ENCE最高的属性。我们现在将陈述如何使用信息增益这一概念来度量重要性。信息增益是从嫡(entropy)的角度进行定义的，而嫡是信息论中最基本的量(ShanrIOnandWeaver,1949)o嫡是随机变量不确定性的度量；信息量越多，皤越小。一个只有一个可能值的随机变量(如一枚总是正面朝上的硬币)没有不确定性，因此它的牖为0。一枚公平的硬币在抛掷时出现正面或反面朝上的概率相同，我们将证明它的嫡为“1位”。一个公平的四面骰子的燧为2位，因为它有22种可能性相同的选择。现在考虑一枚不公平的硬币，它在99%的情况下都是正面朝上。直觉告诉我们，这枚硬币含有的不确定性比公平硬币要少如果我们猜测正面朝上，只会有1%的情况是错的所以我们希望它有一个接近于0,但为正的嫡。一般情况下，若一个随机变量V取值为町的概率为尸(取)，那么它的燧"(V)定义为H(r)=P(vJlog2-5-=-P(v,)Iog2P(Vi)Ktvk)k我们可以验证一枚公平硬币被抛掷的炳确实是1位：H(Fair)=-(0.5log20.5+0.5log20.5)=1而一个四面骰子的燧是2位：H(DieG=-(0.25log20.25+0.25log20.25+0.25log20.25+0.25log20.25)=2对于99%的情况出现正面的硬币，有H(Loaded)=-(0.99log20.99÷0.01Iog20.01)0.08位一个布尔随机变量，如果其为真的概率是“，则该变量的嫡5(q)定义为B(q)=TqIog2+(l-<?)log2(l-(?)因此，H(Loaded)=(0.99)0.08o现在我们回过头来看决策树的学习。如果一个训练集包含P个正样例和个负样例，则在整个集合上的输出变量的焙为H(Output)=B-PkP÷wJ在图19-2所示的餐厅训练集中，有P=几=6,因此相应的嫡是8（0.5）,或恰好为1位。对属性A的测试结果会给我们提供一些信息，从而减少一些整体的嫡。我们可以通过观察属性测试后剩余的端来度量这种减少。若一个具有d个不同值的属性A将训练集石划分为子集功,每个子集线含有PZ个正样例与牲个负样例，那么如果我们沿着该分支前进，将需要额外的83/。+4）位的信息来处理问题。从训练集中随机选取一个样例，它具有该属性的第k个值（即该样例在线中的概率为S+%）（p+功），因此在测试属性A后剩余的嫡的期望为Pkm+%Remainder(J)=YPkBMP+通过测试属性A获得的信息增益（informationgain）定义为燧减少的期望值：Gain（八）=(-Remainder（八）事实上，GazMA）正是我们实现重要性函数LORnNCE需要的。回顾图19-4中所考虑的属性，有Gain Patrons) = 1-2 l0D -12 U412¼-B -I 0.541¼ 12(6Gain(Type) = I-d(2 D (4,这证实了我们的直觉，即RS最适合作为优先考虑的分割属性。事实上，PWS在所有的属性中有最大的信息增益，因此将被决策树学习算法选择作为树的根。1.2.4 泛化与过拟合我们希望我们的学习算法找到一个能够吻合训练数据的假设，但更重要的是，我们希望它能很好地推广到还没有被观测到的数据上。在图19-1中我们看到，一个高阶多项式可以拟合所有数据，但它在拟合数据时有不合理的剧烈波动：它拟合了数据，但可能发生过拟合。随着属性数量的增加，过拟合的可能性将越来越大，而随着训练样例数量的增加，过拟合的可能性会越来越小。较大的假设空间（例如，具有更多节点的决策树或具有更高阶数的多项式空间）具有更强的拟合和过拟合能力，某些模型类比其他模型类更容易过拟合。对决策树来说，一种称为决策树剪枝（decisiontreepruning）的技术可以用于减轻过拟合。剪枝通过删去不明显相关的节点来实现。我们从一棵完整的树出发，它由LEARNDec。N-Tree生成。接着我们研究一个只有叶节点作为子节点的测试节点，如果该节点的测试效果为不相关它只测试数据中的噪声那么我们将删去该测试节点，并用它的叶节点替换它。重复这个过程，考虑每个只有叶节点作为子节点的测试节点，直到每个测试节点都被剪枝或按原样接受。现在的问题是如何判断一个节点所测试的属性是否是不相关的属性。假设我们目前所考虑的节点由P个正样例和个负样例组成。如果该节点测试的属性是不相关的，那么在我们的预期中，该测试会将样例分割成多个子集，使得每个子集的正样例的比例与整个集合的比例p（p+大致相同，因此信息增益将接近于0。团因而，低信息增益是判断属性是否不相关的一个很好的方法。现在的问题是，我们需要多大的增益才能在特定属性上进行分割？3这个增益将恒为正数，除了所有的比例都完全相同的情形（不太常见）。（见习题19.NNGAo）我们可以用统计学中的显著性检验（significancetest）来回答这个问题。该检验首先假设不存在基础的模式所谓的零假设（nullhyphothesis）,然后对实际数据进行分析，并计算它们偏离零假设的程度。如果偏离程度在统计上不太可能发生（通常我们取5%或更低的概率作为阈值），那么这在一定程度上证明了数据中仍存在显著的模式。其中概率将根据随机抽样中偏差量的标准分布计算得到。在这种情况下，相应的零假设是该属性是不相关的，因此对于一个无限大的样本集而言，信息增益将为0。我们需要计算的概率是在零假设下，一个大小为y=+p的样本集所呈现的与正负样例的期望分布的偏离状况的概率。我们可以通过比较每个子集中的正负样例的实际数量Pk和敢与假设该属性不相关情形下的期望数量方和碌衡量这一偏差：apk+11k人Pk+%pk=p×-nk=n×-p+npn下式给出总偏差的一个简洁形式:在零假设下，4将服从个自由度的/分布（卡方分布）。我们可以使用/统计量来判断一个特定的/值是接受还是拒绝了零假设。例如，餐厅的TyPe属性有4个值，因此分布有3个自由度。在5%的置信水平下，总偏差A=7S2或更大的值将拒绝零假设（在1%的置信水平下，/1=11.35或更大的值将拒绝零假设）。低于阈值的偏差值会让我们接受属性不相关这一零假设，因此树的相关分支应该被剪枝。这个方法被称为/剪枝（/pruning）。有了剪枝的技术，我们允许样例中存在噪声。样例标签中的错误（例如，一个样例SNo）被误标为（Yes）会使预测误差线性地增加，而样例描述中的错误（例如，样例的实际属性PriCe=$蹦误标记Price对误差具有渐近的影响，随着树收缩在更小的集合上运作，这种影响会变得更糟。当数据具有较大的噪声时，经过剪枝的树的性能将明显优于未剪枝的树。而且经过剪枝的树通常要小得多，因此更容易被理解，调用也更有效率。最后一个需要提醒的地方：我们可能会认为/剪枝和信息增益看起来很类似，那么为什么不使用一种被称为提前停止（earlystopping）的方法将它们合并起来，即让决策树算法在没有好的属性来继续进行分割时停止生成节点，而不是平添麻烦地生成完