1、第第7章章 机器学习机器学习 学习是人类获取知识的重要途径和自然智能的重要标志，机学习是人类获取知识的重要途径和自然智能的重要标志，机器学习则是机器获取知识的重要途径和人工智能的重要标志。器学习则是机器获取知识的重要途径和人工智能的重要标志。7.1 机器学习的基本概念机器学习的基本概念 7.1.1 学习和机器学习学习和机器学习 7.1.2 机器学习的发展过程机器学习的发展过程 7.1.3 学习系统学习系统 7.1.4 机器学习的主要策略机器学习的主要策略7.2 记忆学习记忆学习7.3 归纳学习归纳学习7.4 解释学习解释学习7.5 神经学习神经学习17.1.1 学习和机器学习学习和机器学习1.
2、学习的概念学习的概念 代表性观点代表性观点 (1)西蒙（西蒙（Simon,1983）：学习就是系统中的适应性变化，这种变）：学习就是系统中的适应性变化，这种变化使系统在重复同样工作或类似工作时，能够做得更好。化使系统在重复同样工作或类似工作时，能够做得更好。(2)明斯基（明斯基（Minsky,1985）：学习是在人们头脑里（心理内部）有）：学习是在人们头脑里（心理内部）有用的变化。用的变化。(3)迈克尔斯基（迈克尔斯基（Michalski,1986）：学习是对经历描述的建立和修）：学习是对经历描述的建立和修改。改。一般性解释：一般性解释：学习是一个有特定目的知识获取和能力增长过程，其内在行为是
3、获学习是一个有特定目的知识获取和能力增长过程，其内在行为是获得知识、积累经验、发现规律等，其外部表现是改进性能、适应环境、得知识、积累经验、发现规律等，其外部表现是改进性能、适应环境、实现自我完善等。实现自我完善等。27.1.1 学习和机器学习学习和机器学习2.机器学习的概念机器学习的概念 一般性解释一般性解释 机器学习就是让机器（计算机）来模拟和实现人类的学习功能。机器学习就是让机器（计算机）来模拟和实现人类的学习功能。主要研究内容主要研究内容 认知模拟认知模拟 主要目的是要通过对人类学习机理的研究和模拟，从根本上解决主要目的是要通过对人类学习机理的研究和模拟，从根本上解决机器学习方面存在的
4、种种问题。机器学习方面存在的种种问题。理论性分析理论性分析 主要目的是要从理论上探索各种可能的学习方法，并建立起独立主要目的是要从理论上探索各种可能的学习方法，并建立起独立于具体应用领域的学习算法。于具体应用领域的学习算法。面向任务的研究面向任务的研究 主要目的是要根据特定任务的要求，建立相应的学习系统。主要目的是要根据特定任务的要求，建立相应的学习系统。3 神经元模型研究神经元模型研究 20世纪世纪50年代中期到年代中期到60年代初期，也被称为机器学习的热烈时期，最具有年代初期，也被称为机器学习的热烈时期，最具有代表性的工作是罗森勃拉特代表性的工作是罗森勃拉特1957年提出的感知器模型。年提
5、出的感知器模型。符号概念获取符号概念获取 20世纪世纪60年代中期到年代中期到70年代初期。其主要研究目标是模拟人类的概念学习年代初期。其主要研究目标是模拟人类的概念学习过程。这一阶段神经学习落入低谷，称为机器学习的冷静时期。过程。这一阶段神经学习落入低谷，称为机器学习的冷静时期。知识强化学习知识强化学习 20世纪世纪70年代中期到年代中期到80年代初期。人们开始把机器学习与各种实际应用相年代初期。人们开始把机器学习与各种实际应用相结合，尤其是专家系统在知识获取方面的需求，也有人称这一阶段为机器结合，尤其是专家系统在知识获取方面的需求，也有人称这一阶段为机器学习的复兴时期。学习的复兴时期。连接
6、学习和混合型学习连接学习和混合型学习 20世纪世纪80年代中期至今。把符号学习和连接学习结合起来的混合型学习系年代中期至今。把符号学习和连接学习结合起来的混合型学习系统研究已成为机器学习研究的一个新的热点。统研究已成为机器学习研究的一个新的热点。7.1.1 学习和机器学习学习和机器学习3.机器学习的发展过程机器学习的发展过程47.1.3 学习系统学习系统环境环境学习环节学习环节知识库知识库执行环节执行环节 环境环境 是学习系统所感知到的外界信息集合，也是学习系统的外界来源。信息的是学习系统所感知到的外界信息集合，也是学习系统的外界来源。信息的水平（一般化程度）和质量（正确性）对学习系统影响较大
7、。水平（一般化程度）和质量（正确性）对学习系统影响较大。学习环节学习环节 对环境提供的信息进行整理、分析归纳或类比，形成知识，并将其放入知对环境提供的信息进行整理、分析归纳或类比，形成知识，并将其放入知识库。识库。知识库知识库 存储经过加工后的信息（即知识）。其表示形式是否合适非常重要。存储经过加工后的信息（即知识）。其表示形式是否合适非常重要。执行环节执行环节 根据知识库去执行一系列任务，并将执行结果或执行过程中获得的信息反根据知识库去执行一系列任务，并将执行结果或执行过程中获得的信息反馈给学习环节。学习环节再利用反馈信息对知识进行评价，进一步改善执行馈给学习环节。学习环节再利用反馈信息对知
8、识进行评价，进一步改善执行环节的行为。环节的行为。57.1.4 机器学习的主要策略机器学习的主要策略 按学习策略来分类按学习策略来分类 即按学习中所使用的推理方法来分，可分为记忆学习、传授学习、即按学习中所使用的推理方法来分，可分为记忆学习、传授学习、演绎学习、归纳学习等。演绎学习、归纳学习等。按应用领域分类按应用领域分类 专家系统学习、机器人学习、自然语言理解学习等。专家系统学习、机器人学习、自然语言理解学习等。按对人类学习的模拟方式按对人类学习的模拟方式 符号主义学习、连接主义学习等。符号主义学习、连接主义学习等。6第第7章章 机器学习机器学习7.1 机器学习的基本概念机器学习的基本概念7
9、.2 记忆学习记忆学习7.3 归纳学习归纳学习7.4 解释学习解释学习7.5 神经学习神经学习77.2 记忆学习记忆学习概概 念念 记忆学习记忆学习(Rote learning)也叫死记硬背学习，是一种最基本的学习也叫死记硬背学习，是一种最基本的学习过程，它没有足够的能力独立完成智能学习，但对学习系统来说都过程，它没有足够的能力独立完成智能学习，但对学习系统来说都是十分重要的一个组成部分，原因是任何学习系统都必须记住它们是十分重要的一个组成部分，原因是任何学习系统都必须记住它们所获取的知识，以便将来使用。所获取的知识，以便将来使用。记忆学习的基本过程是：执行元素每解决一个问题，系统就记住记忆学
10、习的基本过程是：执行元素每解决一个问题，系统就记住这个问题和它的解，当以后再遇到此类问题时，系统就不必重新进这个问题和它的解，当以后再遇到此类问题时，系统就不必重新进行计算，而可以直接找出原来的解去使用行计算，而可以直接找出原来的解去使用 8 若把执行元素比作一个函数若把执行元素比作一个函数f，由环境得到的输入模式记为，由环境得到的输入模式记为(x1,x2,xn)，由该输入模式经由该输入模式经F计算后得到的输出模式记为计算后得到的输出模式记为(y1,y2,ym)，则机械学习系统则机械学习系统就是要把这一输入输出模式对：就是要把这一输入输出模式对：(x1,x2,xn)，(y1,y2,ym)保存在
11、知识库中，当以后再需要计算保存在知识库中，当以后再需要计算f(x1,x2,xn)时，就可以直接从存储器时，就可以直接从存储器把把(y1,y2,ym)检索出来，而不需要再重新进行计算。检索出来，而不需要再重新进行计算。(x1,x2,xn)(y1,y2,yn)(x1,x2,xn),(y1,y2,yn)f存储存储输入模式输入模式执行函数执行函数输出模式输出模式输入输出模式对输入输出模式对机械式学习的学习模型机械式学习的学习模型7.2 记忆学习记忆学习模模 型型97.3 归纳学习归纳学习 归纳学习是指以归纳推理为基础的学习，其任务是要从关于某个概念的一归纳学习是指以归纳推理为基础的学习，其任务是要从关
12、于某个概念的一系列已知的正例和反例中归纳出一个一般的概念描述。系列已知的正例和反例中归纳出一个一般的概念描述。7.3.1 示例学习示例学习 是归纳学习的一种特例。它给学习者提供某一概念的一组正例和反例，学是归纳学习的一种特例。它给学习者提供某一概念的一组正例和反例，学习者归纳出一个总的概念描述，并使这个描述适合于所有的正例，排除所习者归纳出一个总的概念描述，并使这个描述适合于所有的正例，排除所有的反例。有的反例。7.3.2 决策树学习决策树学习 是一种以示例为基础的归纳学习方法，也是目前最流行的归纳学习方法之是一种以示例为基础的归纳学习方法，也是目前最流行的归纳学习方法之一。在现有的各种决策树
13、学习算法中，影响较大的是一。在现有的各种决策树学习算法中，影响较大的是ID3算法。本节主要讨算法。本节主要讨论决策树的概念和决策树学习的论决策树的概念和决策树学习的ID3算法。算法。10 按例子的来源分类按例子的来源分类 例子来源于教师的示例学习例子来源于教师的示例学习 例子来源于学习者本身的示例学习例子来源于学习者本身的示例学习 学习者明确知道自己的状态，但完全不清楚所要获取的概念。学习者明确知道自己的状态，但完全不清楚所要获取的概念。例子来源于学习者以外的外部环境的示例学习例子来源于学习者以外的外部环境的示例学习 例子的产生是随机的。例子的产生是随机的。按例子的类型分类按例子的类型分类 仅
14、利用正例的示例学习仅利用正例的示例学习 这种学习方法会使推出的概念的外延扩大化。这种学习方法会使推出的概念的外延扩大化。利用正例和反例的示例学习利用正例和反例的示例学习 这是示例学习的一种典型方式，它用正例用来产生概念，用反例用来防止这是示例学习的一种典型方式，它用正例用来产生概念，用反例用来防止概念外延的扩大。概念外延的扩大。7.3.1 示例学习示例学习1.示例学习的类型示例学习的类型11示例空间示例空间规则空间规则空间验证过程验证过程解释过程解释过程 示例空间示例空间 是我们向系统提供的示教例子的集合。研究问题：例子质量，搜索方法。是我们向系统提供的示教例子的集合。研究问题：例子质量，搜索
15、方法。解释过程解释过程 是从搜索到的示例中抽象出一般性的知识的归纳过程。解释方法：常量转是从搜索到的示例中抽象出一般性的知识的归纳过程。解释方法：常量转换为变量，去掉条件，增加选择，曲线拟合等。换为变量，去掉条件，增加选择，曲线拟合等。规则空间规则空间 是事务所具有的各种规律的集合。研究问题：对空间的要求，搜索方法是事务所具有的各种规律的集合。研究问题：对空间的要求，搜索方法 验证过程验证过程 是要从示例空间中选择新的示例，对刚刚归纳出的规则做进一步的验证和是要从示例空间中选择新的示例，对刚刚归纳出的规则做进一步的验证和修改修改。7.3.1 示例学习示例学习2.示例学习的模型示例学习的模型12
16、 是指解释过程从具体示例形成一般性知识所采用的归纳推理方法。最常用是指解释过程从具体示例形成一般性知识所采用的归纳推理方法。最常用的解释方法有以下的解释方法有以下4种：种：(1)把常量转换为变量把常量转换为变量 把示例中的常量换成变量而得到一个一般性的规则。把示例中的常量换成变量而得到一个一般性的规则。(2)去掉条件去掉条件 把示例中的某些无关的子条件舍去。把示例中的某些无关的子条件舍去。(3)增加选择增加选择 在析取条件中增加一个新的析取项。常用的增加析取项的方法有前件析取在析取条件中增加一个新的析取项。常用的增加析取项的方法有前件析取法和内部析取法两种法和内部析取法两种 (4)曲线拟合曲线
17、拟合 对数值问题的归纳可采用最小二乘法进行曲线拟合对数值问题的归纳可采用最小二乘法进行曲线拟合 7.3.1 示例学习示例学习3.示例学习的解释方法示例学习的解释方法(1/5)13 例：例：假设例子空间中有以下两个关于扑克牌中假设例子空间中有以下两个关于扑克牌中“同花同花”概念的示例：概念的示例：示例示例1：花色花色(c1，梅花梅花)花色花色(c2，梅花梅花)花色花色(c3，梅花梅花)花色花色(c4，梅花梅花)花色花色(c5，梅花梅花)同花同花(c1,c2,c3,c4,c5)示例示例2：花色花色(c1，红桃红桃)花色花色(c2，红桃红桃)花色花色(c3，红桃红桃)花色花色(c4，红桃红桃)花色花
18、色(c5，红桃红桃)同花同花(c1,c2,c3,c4,c5)其中，示例其中，示例1表示表示5张梅花牌是同花，示例张梅花牌是同花，示例2表示表示5张红桃牌是同花。张红桃牌是同花。解释过程：解释过程：(1)把常量化为变量把常量化为变量 例如，对这两个示例，只要把例如，对这两个示例，只要把“梅花梅花”和和“红桃红桃”用变量用变量x代换，就可得代换，就可得到如下一般性的规则：到如下一般性的规则：规则规则1：花色花色(c1，x)花色花色(c2，x)花色花色(c3，x)花色花色(c4，x)花色花色(c5，x)同花同花(c1,c2,c3,c4,c5)7.3.1 示例学习示例学习3.示例学习的解释方法示例学习
19、的解释方法(2/5)14 (2)去掉条件去掉条件 这种方法是要把示例中的某些无关的子条件舍去。例如，有如下示例：这种方法是要把示例中的某些无关的子条件舍去。例如，有如下示例：示例示例3：花色花色(c1,红桃红桃)点数点数(c1，2)花色花色(c2,红桃红桃)点数点数(c2，3)花色花色(c3,红桃红桃)点数点数(c3，4)花色花色(c4,红桃红桃)点数点数(c4，5)花色花色(c5,红桃红桃)点数点数(c5，6)同花同花(c1,c2,c3,c4,c5)7.3.1 示例学习示例学习3.示例学习的解释方法示例学习的解释方法(3/5)为了学习同花的概念，除了需要把常量变为变量外，还需要把与花色无关为
20、了学习同花的概念，除了需要把常量变为变量外，还需要把与花色无关的的“点数点数”子条件舍去。这样也可得到上述规则子条件舍去。这样也可得到上述规则1：规则规则1：花色花色(c1，x)花色花色(c2，x)花色花色(c3，x)花色花色(c4，x)花色花色(c5，x)同花同花(c1,c2,c3,c4,c5)157.3.1 示例学习示例学习3.示例学习的解释方法示例学习的解释方法(4/5)(3)增加选择增加选择 在析取条件中增加一个新的析取项。包括前件析取法和内部析取法。在析取条件中增加一个新的析取项。包括前件析取法和内部析取法。前件析取法：前件析取法：是通过对示例的前件的析取来形成知识的。例如：是通过对
21、示例的前件的析取来形成知识的。例如：示例示例4：点数点数(c1,J)脸脸(c1)示例示例5：点数点数(c1,Q)脸脸(c1)示例示例6：点数点数(c1,K)脸脸(c1)将各示例的前件进行析取，就可得到所要求的规则：将各示例的前件进行析取，就可得到所要求的规则：规则规则2：点数点数(c1,J)点数点数(c1,Q)点数点数(c1,K)脸脸(c1)内部析取法：内部析取法：是在示例的表示中使用集合与集合的成员关系来形成知识的。是在示例的表示中使用集合与集合的成员关系来形成知识的。例如，有如下关于例如，有如下关于“脸牌脸牌”的示例：的示例：示例示例7：点数点数c1J脸脸(c1)示例示例8：点数点数c1Q
22、脸脸(c1)示例示例9：点数点数c1K脸脸(c1)用内部析取法，可得到如下规则：用内部析取法，可得到如下规则：规则规则3：点数点数(c1)J,Q,K脸脸(c1)16 (4)曲线拟合曲线拟合 对数值问题的归纳可采用曲线拟合法。假设示例空间中的每个对数值问题的归纳可采用曲线拟合法。假设示例空间中的每个示示例例(x,y,z)都都是输入是输入x,y与输出与输出z之间关系的三元组。例如，有下之间关系的三元组。例如，有下3个示例：个示例：示例示例10：(0,2,7)示例示例11：(6,-1,10)示例示例12：(-1,-5,-16)用最小二乘法进行曲线拟合，可得用最小二乘法进行曲线拟合，可得x,y,z之间
23、关系的规则如下：之间关系的规则如下：规则规则4：z=2x+3y+1 说明：说明：在上述前三种方法中，方法在上述前三种方法中，方法(1)是把常量转换为变量；方法是把常量转换为变量；方法(2)是去掉合是去掉合取项（约束条件）；方法取项（约束条件）；方法(3)是增加析取项。它们都是要扩大条件的适用范围。是增加析取项。它们都是要扩大条件的适用范围。从归纳速度上看，方法从归纳速度上看，方法(1)的归纳速度快，但容易出错；方法的归纳速度快，但容易出错；方法(2)归纳速度慢，但归纳速度慢，但不容易出错。因此，在使用方法不容易出错。因此，在使用方法(1)时应特别小心。例如：时应特别小心。例如：对示例对示例4、
24、示例、示例5及示例及示例6，若使用方法，若使用方法(1),则会归纳出如下的错误规则：则会归纳出如下的错误规则：规则规则5：（错误）点数（错误）点数(c1,x)脸脸(c1)它说明，归纳过程是很容易出错的。它说明，归纳过程是很容易出错的。7.3.1 示例学习示例学习3.示例学习的解释方法示例学习的解释方法(5/5)17 是一种由节点和边构成的用来描述分类过程的层次数据结构。该树的根接是一种由节点和边构成的用来描述分类过程的层次数据结构。该树的根接点表示分类的开始，叶节点表示一个实例的结束，中间节点表示相应实例中点表示分类的开始，叶节点表示一个实例的结束，中间节点表示相应实例中的某一属性，而边则代表
25、某一属性可能的属性值。的某一属性，而边则代表某一属性可能的属性值。在决策树中，从根节点到叶节点的每一条路径都代表一个具体的实例，并在决策树中，从根节点到叶节点的每一条路径都代表一个具体的实例，并且同一路径上的所有属性之间为合取关系，不同路径（即一个属性的不同属且同一路径上的所有属性之间为合取关系，不同路径（即一个属性的不同属性值）之间为析取关系。性值）之间为析取关系。决策树的分类过程就是从这棵树的根接点开始，按照给定的事例的属性值决策树的分类过程就是从这棵树的根接点开始，按照给定的事例的属性值去测试对应的树枝，并依次下移，直至到达某个叶节点为止。去测试对应的树枝，并依次下移，直至到达某个叶节点
26、为止。图图7.4是一个非常简单的用来描述对鸟类进行分类的决策树。在该图中：是一个非常简单的用来描述对鸟类进行分类的决策树。在该图中：根节点包含各种鸟类，叶节点是所能识别的各种鸟的名称；根节点包含各种鸟类，叶节点是所能识别的各种鸟的名称；中间节点是鸟的一些属性，边是鸟的某一属性的属性值；中间节点是鸟的一些属性，边是鸟的某一属性的属性值；从根节点到叶节点的每一条路径都描述了一种鸟，它包括该种鸟的一些从根节点到叶节点的每一条路径都描述了一种鸟，它包括该种鸟的一些属性及相应的属性值。属性及相应的属性值。7.3.2 决策树学习决策树学习1.决策树的概念决策树的概念(1/2)18鸟类鸟类家养家养可能是和平
27、鸽可能是和平鸽可能是可能是信天翁信天翁游泳游泳可能是可能是企鹅企鹅可能是可能是鸵鸟鸵鸟图图7.4 一个简单的鸟类识别决策树一个简单的鸟类识别决策树会飞会飞不会飞不会飞是是不是不是会会不会不会 决策树还可以表示成规则的形式。上图的决策树可表示为如下规则集：决策树还可以表示成规则的形式。上图的决策树可表示为如下规则集：IF 鸟类会飞鸟类会飞 AND 是家养的是家养的 THEN 该鸟类是和平鸽该鸟类是和平鸽 IF 鸟类会飞鸟类会飞 AND 不是家养的不是家养的 THEN 该鸟类是信天翁该鸟类是信天翁 IF 鸟类不会飞鸟类不会飞 AND 会游泳会游泳 THEN 该鸟类是企鹅该鸟类是企鹅 IF 鸟类不会
28、飞鸟类不会飞 AND 不会游泳不会游泳 THEN 该鸟类是鸵鸟该鸟类是鸵鸟 决策树学习过程实际上是一个构造决策树的过程。当学习完成后，就可以决策树学习过程实际上是一个构造决策树的过程。当学习完成后，就可以利用这棵决策树对未知事物进行分类。利用这棵决策树对未知事物进行分类。7.3.2 决策树学习决策树学习1.决策树的概念决策树的概念(2/2)197.3.2 决策树学习决策树学习2.ID3算法算法(1/11)D3算法是昆兰（算法是昆兰（J.R.Quinlan）于）于1979年提出的一种以信息年提出的一种以信息熵（熵（entropy）的下降速度作为属性选择标准的一种学习算法。）的下降速度作为属性选择
29、标准的一种学习算法。其输入是一个用来描述各种已知类别的例子集，学习结果是其输入是一个用来描述各种已知类别的例子集，学习结果是一棵用于进行分类的决策树。一棵用于进行分类的决策树。主要讨论：主要讨论：ID3算法的数学基础算法的数学基础 ID3算法机器举例算法机器举例 207.3.2 决策树学习决策树学习2.ID3算法算法(2/11)(1)ID3算法的数学基础算法的数学基础 下面讨论信息熵和条件熵的数学概念下面讨论信息熵和条件熵的数学概念 信息熵信息熵 信息熵是对信息源整体不确定性的度量。假设信息熵是对信息源整体不确定性的度量。假设X为信源，为信源，xi为为X所发出的所发出的单个信息，单个信息，P(
30、xi)为为X发出发出xi的概率，则信息熵可定义为：的概率，则信息熵可定义为：其中，其中，k为信源为信源X发出的所有可能的信息类型，对数可以是以各种数为底的发出的所有可能的信息类型，对数可以是以各种数为底的对数，在对数，在ID3算法中，我们取以算法中，我们取以2为底的对数。为底的对数。信息熵反应的是信源每发出一个信息所提供的平均信息量。信息熵反应的是信源每发出一个信息所提供的平均信息量。)(log)()(log)()(log)()(log)()(12211ikiirrxPxPxPxPxPxPxPxPXH21 条件熵条件熵 条件熵是收信者在收到信息后对信息源不确定性的度量。若假条件熵是收信者在收到
31、信息后对信息源不确定性的度量。若假设信源为设信源为X，收信者收到的信息为收信者收到的信息为Y，P(xi/yj)为当为当Y为为yj时时X为为xi的的条件概率，则条件熵可定义为：条件概率，则条件熵可定义为：它表示收信者收到它表示收信者收到Y后对后对X不确定性的估计。不确定性的估计。(|)(|)log(|)kkijijijH X YP xyP xy 7.3.2 决策树学习决策树学习2.ID3算法算法(3/11)227.3.2 决策树学习决策树学习2.ID3算法算法(4/11)(2)ID3算法及举例算法及举例 ID3算法的学习过程：算法的学习过程：首先以整个例子集作为决策树的根节点首先以整个例子集作为
32、决策树的根节点S，并计算，并计算S关于每个属性的关于每个属性的期望熵（即条件熵）；期望熵（即条件熵）；然后选择能使然后选择能使S的期望熵为最小的一个属性对根节点进行分裂，得的期望熵为最小的一个属性对根节点进行分裂，得到根节点的一层子节点；到根节点的一层子节点；接着再用同样的方法对这些子节点进行分裂，直至所有叶节点的熵接着再用同样的方法对这些子节点进行分裂，直至所有叶节点的熵值都下降为值都下降为0为止。为止。这时，就可得到一棵与训练例子集对应的熵为这时，就可得到一棵与训练例子集对应的熵为0的决策树，即的决策树，即ID3算算法学习过程所得到的最终决策树。该树中每一条从根节点到叶节点的法学习过程所得
33、到的最终决策树。该树中每一条从根节点到叶节点的路径，都代表了一个分类过程，即决策过程。路径，都代表了一个分类过程，即决策过程。23 例例7.1 用用ID3算法完成下述学生选课的例子算法完成下述学生选课的例子 假设将决策假设将决策y分为以下类：分为以下类：y1：必修必修AI y2：选修选修AI y3：不修不修AI做出这些决策的依据有以下做出这些决策的依据有以下3个属性：个属性：x1：学历层次学历层次x1=1 研究生，研究生，x1=2 本科本科 x2：专业类别专业类别x2=1 电信类，电信类，x2=2 机电类机电类 x3：学习基础学习基础x3=1 修过修过AI，x3=2 未修未修AI 表表7.1给
34、出了一个关于选课决策的训练例子集给出了一个关于选课决策的训练例子集S。7.3.2 决策树学习决策树学习2.ID3算法算法(5/11)24表表7-1关于选课决策的训练例子集关于选课决策的训练例子集 在该表中，训练例子集在该表中，训练例子集S的大小为。的大小为。ID3算法是依据这些训练例子，以算法是依据这些训练例子，以S为根节点，按照信息熵下降最大的原则来构造决策树的。为根节点，按照信息熵下降最大的原则来构造决策树的。序号序号属性值属性值决策方案决策方案yix1x2x31111y32112y13121y34122y25211y36212y27221y38222y37.3.2 决策树学习决策树学习2
35、.ID3算法算法(6/11)25 解：解：首先对根节点，其信息熵为：首先对根节点，其信息熵为：其中，为可选的决策方案数，且有其中，为可选的决策方案数，且有P(y1)=1/8，P(y2)=2/8，P(y3)=5/8即有：即有：H(S)=-(1/8)log2(1/8)-(2/8)log2(2/8)-(5/8)log2(5/8)=1.2988 按照按照ID3算法，需要选择一个能使算法，需要选择一个能使S的期望熵为最小的一个属性对根节点的期望熵为最小的一个属性对根节点进行扩展，因此我们需要先计算进行扩展，因此我们需要先计算S关于每个属性的条件熵：关于每个属性的条件熵：其中，其中，t为属性为属性xi的属
36、性值，的属性值，St为为xi=t时的例子集，时的例子集，|S|和和|Si|分别是例子集分别是例子集S和和Si的大小。的大小。)(log)()(231iiiyPyPSH)(|)/(ittiSHSSxSH7.3.2 决策树学习决策树学习2.ID3算法算法(7/11)26 下面先计算下面先计算S关于属性关于属性x1的条件熵：的条件熵：在表在表7-1中，中，x1的属性值可以为的属性值可以为1或或2。当。当x1=1时，时，t=1时，有：时，有：S1=1，2，3，4当当x1=2时，时，t=2时，有：时，有：S2=5，6，7，8其中，其中，S1和和S2中的数字均为例子集中的数字均为例子集S中的各个例子的序号
37、，且有中的各个例子的序号，且有|S|=8，|S1|=|S2|=4。由由S1可知可知：Ps1(y1)=1/4,Ps1(y2)=1/4,Ps1(y3)=2/4则有则有：H(S1)=-Ps1(y1)log2 Ps1(y1)-Ps1(y2)log2 Ps1(y2)-Ps1(y3)log2 Ps1(y3)=-(1/4)log2(1/4)-(1/4)log2(1/4)-(2/4)log2(2/4)=1.57.3.2 决策树学习决策树学习2.ID3算法算法(8/11)27 再由再由S2可知：可知：Ps2(y1)=0/4,Ps2(y2)=1/4,Ps2(y3)=3/4则有则有：H(S2)=Ps2(y2)log
38、2 Ps2(y2)-Ps2(y3)log2 Ps2(y3)=-(1/4)log2(1/4)-(3/4)log2(3/4)=0.8113将将H(S1)和和H(S2)代入条件熵公式，有：代入条件熵公式，有：H(S/x1)=(|S1|/|S|)H(S1)+(|S2|/|S|)H(S2)=(4/8)1.5+(4/8)0.8113=1.1557同样道理，可以求得：同样道理，可以求得：H(S/x2)=1.1557 H(S/x3)=0.75 可见，应该选择属性可见，应该选择属性x3对根节点进行扩展。用对根节点进行扩展。用x3对对S扩展后所得到的得到扩展后所得到的得到部分决策树如图部分决策树如图7.5所示。所
39、示。7.3.2 决策树学习决策树学习2.ID3算法算法(9/10)28 S x3=1,y3 x3=2,x1,x2 图图7.5 部分决策树部分决策树x3=1x3=2 在该树中，节点在该树中，节点“x3=1,y3”表示当表示当x3的属性值为的属性值为1时，得到决策方案时，得到决策方案y3。由于由于y3已是具体的决策方案，故该节点的信息熵为已是具体的决策方案，故该节点的信息熵为0，已经为叶节点。，已经为叶节点。节点节点“x3=2，x1,x2”的含义是的含义是“当当x3的属性值为的属性值为2时，还需要考虑属性时，还需要考虑属性x1,x2”，它是一个中间节点，还需要继续扩展。它是一个中间节点，还需要继续
40、扩展。至于节点至于节点“x3=2，x1,x2”，其扩展方法与上面的过程类似。通过计算可知，其扩展方法与上面的过程类似。通过计算可知，该节点对属性该节点对属性x1和和x2，其条件熵均为其条件熵均为1。由于它对属性。由于它对属性x1和和x2的条件熵相同，的条件熵相同，因此可以先选择因此可以先选择x1，也可以先选择也可以先选择x2，本例是先选择本例是先选择x2。依此进行下去，可得到如图依此进行下去，可得到如图7.6所示的最终的决策树。在该决策树中，各所示的最终的决策树。在该决策树中，各节点的含义与图节点的含义与图7.5类似。类似。7.3.2 决策树学习决策树学习2.ID3算法算法(10/11)29
41、S x3=1,y3 x3=2,x1,x2图图7.6 最终的决策树最终的决策树x3=1x3=21 x2=1,x1 x2=2,x1 x1=1,y1 x1=2,y2 x1=1,y2 x1=2,y3x2=1x2=2x1=1x1=2x1=2x1=17.3.2 决策树学习决策树学习2.ID3算法算法(11/11)30第第7章章 机器学习机器学习7.1 机器学习的基本概念机器学习的基本概念7.2 记忆学习记忆学习7.3 归纳学习归纳学习7.4 解释学习解释学习 解释学习解释学习(Explanation-Based Learning)是一种分析学习方法。它是在是一种分析学习方法。它是在领域知识的指导下，通过对
42、单个问题求解例子的分析来进行学习的。领域知识的指导下，通过对单个问题求解例子的分析来进行学习的。7.1.1 解释学习概述解释学习概述 7.1.2 解释的基本原理解释的基本原理 7.1.3 解释学习的基本过程解释学习的基本过程 7.1.4 领域知识的完善性领域知识的完善性7.5 神经学习神经学习31 解释学习涉及三个不同的空间：例子空间，概念空间和概念描述空间。三解释学习涉及三个不同的空间：例子空间，概念空间和概念描述空间。三个空间及它们之间的关系如图个空间及它们之间的关系如图7.7所示。所示。C1不可操作的不可操作的可操作的可操作的D1D2I1I2I3概念描述空间概念描述空间概念空间概念空间例
43、子空间例子空间 概念描述空间概念描述空间是所有概念描述的集合，其中的概念描述可分为两大类，一是所有概念描述的集合，其中的概念描述可分为两大类，一类是可操作的，另一类是不可操作的。所谓可操作是指一个概念描述能有类是可操作的，另一类是不可操作的。所谓可操作是指一个概念描述能有效的用于识别相应概念的例子。否则是不可操作的。解释学习的任务就是效的用于识别相应概念的例子。否则是不可操作的。解释学习的任务就是要把不可操作的概念描述转化为可操作的概念描述。要把不可操作的概念描述转化为可操作的概念描述。概念空间概念空间是学习过程能够描述的所有概念的集合是学习过程能够描述的所有概念的集合 例子空间例子空间是用于
44、问题求解的例子集合是用于问题求解的例子集合 7.4.1 解释学习概述解释学习概述解释学习的空间描述解释学习的空间描述32 模型：模型：KB EXL 为学习系统为学习系统 KB 为领域知识库，它是不同概念描述之间进行转换所使用的规则集合为领域知识库，它是不同概念描述之间进行转换所使用的规则集合 PS 为执行系统为执行系统 D1 是输入的概念描述，一般为不可操作的；是输入的概念描述，一般为不可操作的；D2 是学习结束时输出的概念描述，它是可操作的。是学习结束时输出的概念描述，它是可操作的。执行过程：执行过程：先由先由EXL接受输入的概念描述接受输入的概念描述D1，然后再根据，然后再根据KB中的知识
45、对中的知识对D1进行不同描述的转换，并由进行不同描述的转换，并由PS对每个转换结果进行测试，直到被对每个转换结果进行测试，直到被PS所接所接受，即为可操作的概念描述受，即为可操作的概念描述D2为止；最后输出为止；最后输出D2。结果是否结果是否可操作可操作PSD2NYEXL概念描述概念描述的转换的转换KBD17.4.1 解释学习概述解释学习概述解释学习的模型解释学习的模型33 本节主要讨论米切尔等人提出的解释泛化学习方法。本节主要讨论米切尔等人提出的解释泛化学习方法。其基本思想：其基本思想：先对某一情况建立一个解释结构，然后在对此解释结构进行先对某一情况建立一个解释结构，然后在对此解释结构进行概
46、括，获取一般性控制知识。概括，获取一般性控制知识。其一般性描述为：其一般性描述为：已知：已知：目标概念目标概念GC(Goal Concept)；训练实例训练实例TE(Training Example)；领域理论领域理论DT(Domain Theory)；操作性标准操作性标准OC(Operationality Criterion)。求出：求出：满足满足OC的关于的关于GC的充分概念描述。的充分概念描述。其中：目标概念其中：目标概念GC 是要学习概念的描述；是要学习概念的描述；训练实例训练实例TE 是为学习系统提供的一个实例；是为学习系统提供的一个实例；领域理论领域理论DT 是相关领域的事实和规则
47、，即为背景知识；是相关领域的事实和规则，即为背景知识；操作性标准操作性标准OC 用于指导学习系统对用来描述目标的概念进行舍取等用于指导学习系统对用来描述目标的概念进行舍取等的控制性知识。的控制性知识。7.4.3 解释学习的基本原理解释学习的基本原理34 其任务是要证明提供给系统的训练实例为什么是目标概念的一个实例。其任务是要证明提供给系统的训练实例为什么是目标概念的一个实例。为此，系统应从目标开始反向推理，根据知识库中已有的事实和规则分解为此，系统应从目标开始反向推理，根据知识库中已有的事实和规则分解目标，直到求解结束。一旦得到解，便完成了该问题的证明，同时也获得目标，直到求解结束。一旦得到解
48、，便完成了该问题的证明，同时也获得了一个解释结构。了一个解释结构。例如，例如，假设要学习的目标是假设要学习的目标是“一个物体一个物体x x可以安全地放置在另一个物体可以安全地放置在另一个物体y y的上面的上面”。即。即 目标概念：目标概念：Safe-to-Stack(x,y)Safe-to-Stack(x,y)训练实例训练实例（是一些描述物体（是一些描述物体objobj1 1与与objobj2 2的事实）：的事实）：On(objOn(obj1 1,obj,obj2 2)物体物体1 1在物体在物体2 2的上面的上面 Isa(objIsa(obj1 1,book),book)物体物体1 1是书是书
49、 Isa(objIsa(obj2 2,table),table)物体物体2 2是桌子是桌子 Volume(objVolume(obj1 1,1),1)物体物体1 1的体积是的体积是1 1 Density(obj Density(obj1 1,0.1),0.1)物体物体1 1的密度是的密度是0.10.17.4.3 解释学习的基本过程解释学习的基本过程1.产生解释结构产生解释结构(1/3)35 领域知识领域知识 是把一个物体安全地放置在另一个物体上面的准则：是把一个物体安全地放置在另一个物体上面的准则：Fragile(y)Safe-to-stack(x,y)如果如果y不是易碎的，则不是易碎的，则x
50、可以安全地放到可以安全地放到y的上面的上面 Lighter(x,y)Safe-to-stack(x,y)如果如果x 比比y轻，则轻，则x可以安全地放到可以安全地放到y的上面的上面 Volume(p,v)Density(p,d)Product(v,d,w)Weight(p,w)如果如果p的体积是的体积是v、密度是密度是d、v乘以乘以d的积是的积是w，则，则p的重量是的重量是w Is-a(p,table)Weight(p,5)如果如果p是桌子，则是桌子，则p的重量是的重量是5 Weight(p1,w1)Weight(p2,w2)Smaller(w1,w2)Lighter(p1,p2)如果如果p1的
