本章开始对学习进行讨论，首先介绍机器学习和解释归纳范式。决策树是广泛应用的归纳学习方法，由于它们不能很好泛化，预测能力很差，因此有大约10年的时间，它们都没有得到人们的支持。但是如果采用很多树，就可以消除很多分歧。最终所谓的随机森林（或决策林）促使最近这种学习方式得以复兴。本章最后阐释了熵及其与决策树构造的关系。
教室
10.0 引言
无论是牙科领域还是小提琴演奏领域，人们都能通过学习提升专业技能。牙科学校的学生在修复牙齿方面变得日渐精通；而在纽约市茱莉亚学校学习的小提琴家，经过多年的培训，可以演奏出艺术性更强的莫扎特小提琴协奏曲。类似地，机器学习也是一个过程，在这个过程中，计算机通过阅读训练数据提炼意义。在研究早期，我们提出了一个问题：机器可以思考吗？如果发现计算机能够执行学习所需的分析推理的算法（超出了第5章中概述的演绎原理的应用），那么这将对解决这个问题大有裨益——因为大多数人认为学习是思维的一种重要组成部分。此外，毫无疑问，机器学习有助于克服人类在知识和常识方面的瓶颈，而我们认为这些瓶颈会阻碍人类层次人工智能的发展，因此许多人将机器学习视为人工智能的梦想。
10.1 机器学习：简要概述
机器学习的根源可以追溯到亚瑟·塞缪尔（Arthur Samuel）。[1] 他在IBM工作了20年（从1949年开始），教计算机玩跳棋。他所编写的程序用的是填鸭式学习，即程序将记住以前游戏中的好走法。更有趣的是，他的跳棋游戏程序中整合了策略。Samuel通过访问人类跳棋选手，获得了对跳棋的深刻见解，并将其解植入程序中。
为了能够增强在某些游戏中的博弈能力，人们会反复玩这个游戏。同样，Samuel也有不同版本的程序互相竞争。博弈的失败者将从获胜者那里学习并获得启发式（详见第16章）。
这个列表绝对不是详尽无遗的，而是作为讨论的一个切入点。机器学习这个主题内容丰富，即便用整本书，也不一定能够囊括所有内容。我们鼓励有兴趣的读者查阅关于这个主题的众多优秀文章。[3,4,5]
下面列出了五大机器学习（ML）范例。
（1）神经网络。
（2）基于案例推理。
（3）遗传算法。
（4）规则归纳。
（5）分析学习[2] 。
隐喻就是打比方，将两个事实上不同的事物进行互相对比，找出共同点。因此，第二个事物的属性就可以转移到第一个事物中。例如：“他像马一样吃饭。”
聚焦于人工神经网络的ML社区从人脑和神经系统的隐喻中获得灵感，人脑和神经系统可能是地球上最具有智慧自然智能的连接。在人工神经网络（ANN）中，人工神经元按照所规定的拓扑结构进行链接。网络的输入信号通常会导致互联强度的变化，最终超过阈值，产生输出信号。训练集是精心挑选的一组输入示例，通常用于教授神经网络某些概念。我们将用第11章一整章来讲述这种机器学习方法。
基于案例的推理与人类记忆中真正起作用的部分进行类比。这种方法维护了一个过去案例或场景的文件，人们有效地将这些案例或场景编入索引，以便即时访问。人们还用了现有案例中一些相似性的量度。例如，对于一位抱怨有严重头痛并表现出失语症、伴有周边视力丧失的患者，医生可能会回想起类似案例，进而诊断为病毒性脑膜炎。施用适当的抗癫痫药物后，患者的最终疗效良好。有了处理过的先前案例的文件，医生可以在当前的案例中更快地做出诊断。当然，医生还必须通过一些测试排除其他具有相似症状但具有非常不同的原因和（或）结果的疾病。例如，医生可以预约核磁共振MRI来确认脑肿胀，并排除肿瘤的存在，抑或通过脊椎抽液排除细菌性脑膜炎的可能。关于案例推理的进一步讨论参见第9章。
在基于遗传算法的机器学习中，自然进化是这种机器学习方法的灵感。19世纪中叶，达尔文提出了自然选择学说。无论是植物还是动物，只要物种变异产生了生存优势，那么这种变异在下一代中出现的频率就会更高。例如，在19世纪初的伦敦，浅色飞蛾比深色飞蛾具有生态优势。当时在伦敦及其周边地区，桦树盛行，树的颜色比较浅，这为浅色飞蛾提供了自然伪装，从而避免了鸟类的捕食。工业革命开始后，污染变得普遍了。结果，英国的树木变得越来越暗，深色飞蛾具有了伪装优势，它们在飞蛾种群中的比例就上升了。遗传算法和遗传程序的内容参见第12章。
规则归纳是依赖于产生式规则（见第6章）和决策树（见第7章）的机器学习分支。适用于教机器人包装杂货的一个产生式规则是：
IF[物品是冷冻食品]
THEN[在将物品放在购物袋之前，先放置在冷冻袋中][6]
我们很快就会发现产生式规则和决策树之间信息内容的相似性。图10.1描绘了杂货包装机器人决策树的一部分。
图10.1 杂货包装机器人决策树。请注意这与本文中给出的产生式规则的相似性
规则归纳的动力来自于启发式搜索。在本章中，决策树得到了广泛的研究。
10.2 机器学习系统中反馈的作用
假设有一个智能体，这个智能体希望能够在大联盟级别上打棒球。要达到这个级别，通常需要15年或更长的培训时间。尽管规则极其简单，但是一个冗长的学习周期：“扔球，抓球，击球。”
这句话引自1988年由Ron Shelton执导的电影《Bull Durham》。
在训练早期，智能体必须了解棒球比赛中的诸多可能状态。
（1）我们的团队是否领先？
（2）如果我处在防守的位置，并且球向我飞来，那么我必须知道现在跑到第一垒的跑垒者速度是不是很快？如果是，那么我必须快点抛球。
（3）对方的投手是否抛出了一个旋转球（这种球很难击中！）？如果是，那么也许今天我应该假装生病了。
这个年轻的智能体所接受的这种类型的反馈是学习过程的核心。在机器学习中，有3种反馈：监督学习、无监督学习和强化学习。
使用监督学习的方式学习功能是最直接、简单的方法。智能体在做了一些动作后，可以马上收到适当的反馈。例如，当一位敏捷的跑垒者给他一个滚地球时，如果他要花点时间将球传给第一垒，那么在这些情况下，在几分钟之内，他就会得到提醒，加快速度。第11章介绍了神经网络使用监督学习来学习布尔函数的方法。我们给网络提供了一个列表，其中列出了每种可能输入的正确输出。
在无监督的学习过程中，培训期间没有提供具体的反馈。但是，如果要学习，那么智能体必须收到一些反馈。假设智能体进攻失利，例如他没有击中垒，但是他的防守截然不同——他成功地实现了两个扑接，并截获了一个全垒打。这是一场比分接近的比赛，他所在的队赢了。比赛后，队友们向他祝贺，他由此得出结论：好的防守也是值得赞赏的。
在强化学习过程中，没有老师为智能体提供正确的答案。事实上，智能体甚至不能提前知道行动的后果。为了进一步将问题复杂化，假设即使智能体知道行动的影响，但是也不知道影响有多大，因此智能体必须通过试错法来学习。由于奖励被推迟，智能体很难确定行动效果的好坏。试图使用中指平衡伞（没打开的）的人都明白强化学习的基础，如图10.2所示。
图10.2 平衡伞，需要在x-y平面上进行小幅度的移动以保持伞的平衡
如果伞向左倾斜，那么你要向左大幅度移动，不久你会发现这是矫枉过正。让我们回到棒球智能体的例子。假设他是一名投手，当对方打出了一个全垒打时，智能体倾向于将棒球投掷给对方的击球手。当对方的投手朝他的腿投出一个时速约145千米的快球时，几局过后，他需要将酸痛的膝盖骨与可能过度激进的打法联系起来。这里我们将讨论严格限制在监督学习中。在巴拉德（Ballard）的著作中[7]，你可以找到关于非监督学习和强化学习的极好讨论。
通过监督学习，你可以看到一组有序对：
我们将这组有序对称为训练集。其中
是输入的n维空间向量，即
是这个函数在
处的值，也就是学习到的值。函数f将每个输入向量映射到正确的输出响应。一般说来，在m维的空间中
，每个分量tk(k = 1,…, m) 都来自一个事先规定的集合，例如整数集、实数集等（输入集和输出集可能有所不同）。
10.3 归纳学习
归纳学习中的任务是找到最接近真实函数f ()的函数h。我们将h称为f ()的假设。学习算法认为假设空间H是近似正确函数f ()的一个函数集。在这个学习中，目标是对于训练集中的所有点找到与f一致的h。人们将这种尝试称为曲线拟合，如图10.3所示。
图10.3 如果h在所有点上都与f符合，则认为h与f是一致的
在图10.4中，有3种不同的假设。乍一看，h3似乎是最好的假设。但是，我们要记住学习的目的（这很重要），即学习不是为了让智能体在训练集上表现得完美，而是要让智能体在验证集上表现良好。
图10.4 3种不同的假设。注意，由于只有h3通过了所有的6个点，因此只有h3与f一致
验证集是测试智能体程序的示例集。如果智能体真正学到了一些概念，那么它不应该只是记住输入和输出的对应关系，而是应该获得概括能力，例如对它还没有遇到过的输入做出适当的响应。通常来说，在训练集上表现完美的假设是过度训练了，不能很好地概括概念。实现概括能力的一种方法是交替训练和验证，并应注意，在验证期间，智能体的学习机制应该是关闭的。当验证错误最小化而不是训练错误最小化时，训练终止。在第11章中，我们将深度解析这种训练的方法。最后再说一下棒球智能体。如果他真的学到了进行棒球比赛的方法，那么即使首次遇到某种比赛情况，也应该做出合理的响应，例如首次遇到一场比赛有三人出局的三杀。
再次参考图10.4（c）。这个函数经过了所有的6个点。我们可以使用拉格朗日插值法找到具有这个属性的许多其他函数，例如阶数为7、8、9的多项式等。在学习领域（机器和人类学习）中，一个指导原则是，当对同一个观察到的现象存在多个解释时，选择最简单的解释才是明智的。这个原则就是所谓的奥卡姆剃刀（Occam’s Razor）原则。以下是这个原则的一些例子。
（1）在遥远的天空中，看见一条细小明亮的光线移动。解释一，一架飞机从附近机场起飞或准备着陆。解释二，一颗星星离开了它的星系，正准备进入我们的星系。解释一是比较可取的一个。
（2）你在圣诞节早晨醒来，看到了窗外街道上的雪——你昨晚睡觉的时候，这些雪不在那里。解释一，因为你今年的表现非常好，圣诞老人委托精灵将雪从北极带到你附近。解释二，你睡觉时下雪了。解释二更有可能。
（3）几年前，一个九月的早晨，你经过布莱克街和曼哈顿第六大道时，看到了数千名纽约人离开城市市区向北走。解释一，地铁有电气故障，列车没有运行。解释二，恐怖分子劫持了两架飞机，撞入世界贸易中心。解释一更有可能，但不幸的是，正确的是解释二。
大多数科学家都同意，当有两个理论来解释同样的现象时，更简单的理论相对较好。但是，正如我们所知，这并不总是能保证正确。这可能只是一个更好的探索起点，直到发现新证据。
2001年某个星期二上午，其中一位作者（SL）约会时迟到了，未能听到早晨的新闻播报。
还有一种特性适用于学习方法，它们要么归为懒惰（lazy），要么归为急切（eager）。懒惰的学习者被认为是懒惰的，因为其推迟了超过训练数据外的概括，直到新的查询出现。懒惰的学习者从不做出任何努力压缩数据，结果，当模型被调用时，所有的数据都可用。这与急切的学习者不同，急切的学习者在出现新询问时，已经抽象出可以应用的一般规则。但是这样一来，训练数据本身不会被保留。一般来说，训练懒惰的学习者更快，但是使用它们需要花更多时间。急切的学习者坚持单一的假设，因此比起懒惰的学习者相对更不灵活。
基于案例的推理（见第9章）被归为懒惰的学习者。在这种情况下，优点是我们可用整个案例，因此这可能具有更广泛的适用性。相反，神经网络被归类为急切的学习者。在反向传播网络（BPN）中，网络学习的是权重，并且我们认为权重是训练数据的压缩版本。为了将BPN应用于新的样本，你需要简单地将新查询作为输入应用到网络中，但是先前用于训练网络的数据就检索不到了。
10.4 利用决策树进行学习
对于概念学习，决策树是被广泛使用的归纳方法。决策树中的节点对应于关于某些属性所做出的查询。从节点发出的分支表示假定的属性值，如图10.5所示。
图10.5 描述了其中一位作者（SL）对意大利面食偏好的决策树
任何熟悉意大利餐馆的人都会很快发现，意大利面有许多形状和大小。
这棵树可能用于将意大利面实例分为两个类——SL喜欢的类和SL不喜欢的类。查询总是从树的根节点开始，终止于叶节点，在叶节点中我们找到了类标签。考虑以下意大利面食清单。
（1）Spaghetti and Meatballs——红酱肉丸意大利面。
（2）Spaghetti Arrabbiata——红酱意大利面。
（3）Linguine calm red sauce Vongole——蛤蜊红酱扁意面。
（4）Linguine calm white sauce Vongole——蛤蜊白酱扁意面。
（5）伏特加粗纹通心面。
如图10.5所示，为了从这个清单中对意大利面和肉丸进行分类，我们从根节点开始。这道菜的酱汁是红色的，所以我们选择这棵树的左分支。根的左子树问：这道菜“含”有肉吗？这当然含肉。这棵树就将Spaghetti and Meatballs归类为SL喜欢的意大利面。试使用相同的决策树追踪其他4个实例。你将会注意到，所有5种面食食谱都分为两个不同的类别。
第一类——SL喜欢的意大利面食，包含了实例1、4和5。
第二类——SL不喜欢的意大利面食，包含了实例2和3。
免责声明——其中一位作者（SL）选择了这些属性值，仅作为教学之用。SL在曼哈顿下城纽约市的“小意大利”长大，不幸的是（对于他的腰围而言），他喜欢每种面食！事实上，他品尝了最喜欢的两家餐馆的大部分菜肴，这两家餐馆分别是位于汉斯特街189号的普利亚和位于“小意大利”迈宝瑞街164号的达尼科。
如图10.5所示，从决策树根节点开始到叶节点结束的任何路径，表示的是路径上属性值的合取（AND）。例如，到达Spaghetti Arrabbiata分类的路径是（酱汁= 红色）∧（肉=否）。SL所喜欢的意大利面菜肴的概念对应于所有合取项的析取（OR），这些合取项是沿着路径到达一个回答为是（Yes）的节点。在例子中，我们有：[（酱汁=红色）∧（肉=是）]∨[（酱汁=白色）∧（海鲜=否）]∨[（酱汁=粉红色）]。
10.5 适用于决策树的问题
能够有效使用决策树进行学习的一些问题的特征如下。
（1）属性应该只有少量几个值，例如酱汁=红色、白色或粉红色；实例用一组属性值表示，例如实例=意粉和肉丸。我们为一些属性赋予某个值，例如酱汁是红色的，是否配有肉=是。
（2）一般来说，目标函数只有少量的几个离散值。在意大利面食的例子中，值为是（Yes）和否（No）。
（3）训练数据中可能存在错误。当在属性值中或是在实例分类中出现错误的情况下，决策树的表现依然优秀（可将此与第11章中神经网络学习的鲁棒性进行对比）。
这些是理想条件。通过参考这一领域的文献，你可以学到许多规避这些局限性的途径。
在训练数据过程中，可能会出现属性值缺失的情况。例如，假设决策树的用户知道Spaghetti Arrabbiata不含肉类，这个属性也就缺失了。
许多现实世界的问题满足了上一列表所施加的约束。在医疗应用中，属性对应于可见的症状或患者的描述（皮肤颜色=黄色、鼻子=流涕、出现头痛）或测试结果（体温升高、血压或血糖水平高、心脏酶异常）医疗应用中的目标函数可能表明存在某种疾病或病症：病人出现花粉症、肝炎或最近修复的心脏瓣膜有点问题。
决策树广泛应用于医疗行业。
在金融领域，从信用卡价值决定到房地产投资的有利条件，也都应用了决策树。商业界中的一个基本应用是期权交易。期权是一种合约，赋予个人以给定价格或在特定日期买卖某些资产（例如股票）的权利。
10.6 熵
熵量化了存在于样本集合中的均匀性。为了简化讨论，假设待学习的概念在本质上是二元的——例如，一个人是否喜欢面食。给定集合S，相对于这个二元分类，S的熵为
{-:-}熵= -p(+) log2 p(+)-p(-) log2 p(-)
其中，p（+）表示喜欢的部分，即喜欢面食；p（-）表示不喜欢的部分。在熵的讨论中，对数总是以2为底，即使在分类不是二元的情况下也是如此。
图10.5中的决策树描述了意大利面的首选项。假设有一个包含4种意大利面食的集合，某人都喜欢吃这4种面——我们将这种情况表示为[4（+），0（-）]，则这个集合中的熵为
熵[4（+），0（-）] = -4 / 4×log2（4/4）- 0/4×log2（0/4）
= -1×log2（1）- 0×log2（0）
= -1×0 - 0× 0
= 0
如果某人喜欢其中的两种面食，不喜欢另外两种面食，那么有
熵[2（+），2（-）] = -2/4×log2（2/4）-2/4×log2（2/4）
= -1/2×（-1）-1/2×（-1）
= 1/2 -（-1/2）
= 1
我们观察到，当所有成员属于同一组时，该集合的熵为0。这个0值表示在这个集合中没有杂质，这个示例中所有的成员均为真。在第二个例子中，有一半的成员是正值，一半的成员是负值，这种情况下熵的值最大，为1。在二元分类中，集合熵的范围是从0到1，如图10.6所示。
图10.6 二元分类中，熵函数随着正样本
比例的变化在区间[0,1]上变化
集合的熵可以视为确定所选项来自哪个类所需的比特数目。例如，对于集合[2（+），2（-）]，需要一个比特来指定从哪个类别中选出哪个项，其中1的意思是某人喜欢该项，0表示某人不喜欢该项。相反，当某人喜欢所有的项时，在集合[4（+），0（-）]，不需要比特来标记项，因此某人喜欢所有的项时，熵为0。
10.7 使用ID3构建决策树
1986年，昆兰（Quinlan）开发了ID3算法。ID3是决策树学习中应用最广泛的算法之一，它是以自上而下的方式构建决策树的。它首先搜索尽可能地将训练集分成相等子集的那个属性。如果要成功地应用决策树，必须了解它们是如何构建的。在意大利面食的例子中，有三个属性——酱汁色、含肉、含海鲜，见表10.1。
表10.1 用于决策树学习的数据
其中有3种不同的属性，因此，对于哪种属性首先出现有不同的选择，如图10.7所示。
如果根据该属性的值可以将样本一分为二，那么就认为这个属性是好的，例如，对应于某个属性值所有的实例都为正，对于其他属性值所有的实例都为负。相反，如果某个属性不包含具有判别力的属性值，则认为这个属性是没用的。在示例中，好的属性意味着对于每个属性值，喜欢的面食和不喜欢的面食数量相等。
ID3使用信息增益来对属性进行位置安排。如果该属性能获得最大预期的熵减，那么这个属性的位置更接近于根节点。如图10.7所示，为了确定3棵子树中最先选择哪个子树，ID3对所示的每棵子树先计算出其平均信息，然后选择能够产生信息增益最大的那棵子树。其中，属性A产生的信息增益，指的是利用A对集合S进行分割，从而导致熵的减少。
式中，v是属性A采用的一个值。这个公式对v的所有值对应的Sv（具有值v的S子集）进行求和。如图10.8～图10.10所示，理解ID3必须完成的计算。
图10.7 决策树可以按照3种属性中的任意一种开始。在（a）中，在酱汁颜色是红色的情况下，作者喜欢两种意大利面，不喜欢3种意大利面。对于其他方框，也可以进行类似的解释
仔细观察图10.8～图10.10，很明显，由于“含有海鲜”的属性，其相关的信息增益为0.32，是对应3种属性中最大的值，因此ID3选择“含有海鲜”的属性作为决策树中的第一种属性。
接下来，ID3必须在图10.11绘制的两棵树之间进行选择。
一旦选择了第二个属性，接下来在需要的时候就会应用未选择的属性。本书要求你在练习中完成这些计算。
图10.8 如果首先选择酱汁颜色，那么信息增益等于0.29
图10.9 如果首先选择含有肉类的属性，那么信息增益等于0.17
图10.10 如果首先选择含有海鲜的属性，那么信息增益等于0.32
图10.11 ID3必须选择哪个属性作为第二个属性——是酱汁颜色，还是含有肉类？
本文截选自《人工智能》（第2版）
京公网安备 11010802035086号