人工智能-AI章符号学习优秀PPT.ppt

6.1.1学习的概念学习的概念1.学习的心理学观点学习的心理学观点基于脑科学和认知科学对人类学习机理的相识，心理学有两种观点：基于脑科学和认知科学对人类学习机理的相识，心理学有两种观点：联结论观点：学习的实质是联结的形成；联结论观点：学习的实质是联结的形成；认知论观点：学习的实质是学习者头脑中认知结构的变更。认知论观点：学习的实质是学习者头脑中认知结构的变更。这些变更既包括行为，也包括行为潜能；既包括感知、记忆、想象、思维这些变更既包括行为，也包括行为潜能；既包括感知、记忆、想象、思维等内部心理过程，也包括语言、表情、动作等外部活动。等内部心理过程，也包括语言、表情、动作等外部活动。心理学的学习概念，主要有以下三个核心要点：心理学的学习概念，主要有以下三个核心要点：(1)学习的发生以行为和行为潜能的变更为标记。学习的发生以行为和行为潜能的变更为标记。学习总会引起行为的变更，并且这种变更可以是外显的，也可以是内隐的，学习总会引起行为的变更，并且这种变更可以是外显的，也可以是内隐的，即即“行为潜能行为潜能”的变更。的变更。(2)学习是由阅历引起的行为变更。学习是由阅历引起的行为变更。阅历是一个人通过活动干脆与客观世界相互作用的过程或在这一过程中所阅历是一个人通过活动干脆与客观世界相互作用的过程或在这一过程中所得到的结果。只有因阅历而引起的行为变更才是学习。得到的结果。只有因阅历而引起的行为变更才是学习。(3)学习所引起的行为变更时间比较许久。学习所引起的行为变更时间比较许久。学习对行为的影响时间一般比较长，只有当旧的学习被新的学习代替时，学习对行为的影响时间一般比较长，只有当旧的学习被新的学习代替时，旧的行为变更才会消逝。旧的行为变更才会消逝。16.1.1学习的概念学习的概念1.学习的人工智能观点学习的人工智能观点在人工智能领域，对学习的概念有多种不同的说明。其中，影响最大的观在人工智能领域，对学习的概念有多种不同的说明。其中，影响最大的观点有以下几种：点有以下几种：(1)西蒙（西蒙（Simon，1983）：学习就是系统中的适应性变更，这种变更使系）：学习就是系统中的适应性变更，这种变更使系统在重复同样工作或类似工作时，能够做得更好。统在重复同样工作或类似工作时，能够做得更好。(2)明斯基（明斯基（Minsky，1985）：学习是在人们头脑里（心理内部）有用的变）：学习是在人们头脑里（心理内部）有用的变更。更。(3)米哈尔斯基（米哈尔斯基（Michalski，1986）：学习是对阅历描述的建立和修改。）：学习是对阅历描述的建立和修改。这些观点虽然不尽相同，但却都包含了学问获得和实力改善这两个主要方这些观点虽然不尽相同，但却都包含了学问获得和实力改善这两个主要方面。其中面。其中学问获得是指获得学问、积累阅历、发觉规律等。学问获得是指获得学问、积累阅历、发觉规律等。实力改善是指改进性能、适应环境、实现自我完善等。实力改善是指改进性能、适应环境、实现自我完善等。二者之间，学问获得是学习的核心，实力改善是学习的结果。二者之间，学问获得是学习的核心，实力改善是学习的结果。学习的一般性说明：学习的一般性说明：学习是一个有特定目的的学问获得和实力增长过程，其内在行为是获得学学习是一个有特定目的的学问获得和实力增长过程，其内在行为是获得学问、积累阅历、发觉规律等，其外部表现是改进性能、适应环境、实现自我问、积累阅历、发觉规律等，其外部表现是改进性能、适应环境、实现自我完善等。完善等。26.1.2机器学习的概念机器学习的概念1.什么是机器学习什么是机器学习一般性说明一般性说明机器学习就是让机器（计算机）来模拟和实现人类的学习功能。机器学习就是让机器（计算机）来模拟和实现人类的学习功能。学科性说明学科性说明是一门探讨如何利用机器模拟或实现人类学习功能的学科。是一门探讨如何利用机器模拟或实现人类学习功能的学科。主要探讨内容主要探讨内容认知模拟认知模拟通过对人类学习机理的探讨和模拟，从根本上解决机器学习方面存在的种通过对人类学习机理的探讨和模拟，从根本上解决机器学习方面存在的种种问题。种问题。理论性分析理论性分析从理论上探究各种可能的学习方法，并建立起独立于具体应用领域的学习从理论上探究各种可能的学习方法，并建立起独立于具体应用领域的学习算法。算法。面对任务的探讨面对任务的探讨依据特定任务的要求，建立相应的学习系统。依据特定任务的要求，建立相应的学习系统。3按机器学习的探讨途径和探讨目标，机器学习课划分为以下按机器学习的探讨途径和探讨目标，机器学习课划分为以下4个阶段：个阶段：(1)神经元模型探讨神经元模型探讨20世纪世纪50年头中期到年头中期到60年头初期，也被称为机器学习的热忱时期，最具有年头初期，也被称为机器学习的热忱时期，最具有代表性的工作是罗森勃拉特代表性的工作是罗森勃拉特1957年提出的感知器模型。年提出的感知器模型。(2)符号概念获得符号概念获得20世纪世纪60年头中期到年头中期到70年头初期。其主要探讨目标是模拟人类的概念学习年头初期。其主要探讨目标是模拟人类的概念学习过程。这一阶段神经学习落入低谷，称为机器学习的冷静时期。过程。这一阶段神经学习落入低谷，称为机器学习的冷静时期。(3)学问强化学习学问强化学习20世纪世纪70年头中期到年头中期到80年头初期。人们起先把机器学习与各种实际应用相年头初期。人们起先把机器学习与各种实际应用相结合，尤其是专家系统在学问获得方面的需求，也有人称这一阶段为机器学结合，尤其是专家系统在学问获得方面的需求，也有人称这一阶段为机器学习的复兴时期。习的复兴时期。(4)连接学习和混合型学习连接学习和混合型学习20世纪世纪80年头中期至今。把符号学习和连接学习结合起来的混合型学习系年头中期至今。把符号学习和连接学习结合起来的混合型学习系统探讨已成为机器学习探讨的一个新的热点。统探讨已成为机器学习探讨的一个新的热点。6.1.2机器学习的概念机器学习的概念2.机器学习的发展过程机器学习的发展过程4按机器学习系统的含义按机器学习系统的含义是指能够在确定程度上实现机器学习系统。是指能够在确定程度上实现机器学习系统。6.1.2机器学习的概念机器学习的概念3.机器学习系统机器学习系统机器学习系统的典型定义机器学习系统的典型定义萨利斯萨利斯(Saris)1973年的说明：年的说明：假如一个系统能够从某个过程和环境的未知特征中学到有关信息，并且能假如一个系统能够从某个过程和环境的未知特征中学到有关信息，并且能把学到的信息用于将来的估计、分类、决策和限制，以便改进系统的性能，把学到的信息用于将来的估计、分类、决策和限制，以便改进系统的性能，那么它就是学习系统那么它就是学习系统史密斯史密斯(Smith)1977年给出的说明：年给出的说明：假如一个系统在与环境相互作用时，能利用过去与环境作用时得到的信息，假如一个系统在与环境相互作用时，能利用过去与环境作用时得到的信息，并提高其性能，那么这样的系统就是学习系统并提高其性能，那么这样的系统就是学习系统56.1.2机器学习的概念机器学习的概念3.机器学习系统机器学习系统学习系统的基本要求：学习系统的基本要求：(1)具有适当的学习环境具有适当的学习环境所谓学习系统的环境，是指学习系统进行学习时的信息来源。所谓学习系统的环境，是指学习系统进行学习时的信息来源。(2)具有确定的学习实力具有确定的学习实力环境仅是为学习系统供应了相应的信息和条件，要从中学到学问，还必需环境仅是为学习系统供应了相应的信息和条件，要从中学到学问，还必需有适当的学习方法和确定的学习实力。有适当的学习方法和确定的学习实力。(3)够运用所学学问求解问题够运用所学学问求解问题学以致用，对人这样，对学习系统也是如此。学以致用，对人这样，对学习系统也是如此。(4)通过学习提高自身性能通过学习提高自身性能提高自身性能，是学习系统应当达到的最终目标。提高自身性能，是学习系统应当达到的最终目标。6按学习策略来分类按学习策略来分类即按学习中所运用的推理方法来分，可分为记忆学习、传授学习、演绎学即按学习中所运用的推理方法来分，可分为记忆学习、传授学习、演绎学习、归纳学习等。习、归纳学习等。按应用领域分类按应用领域分类专家系统学习、机器人学习、自然语言理解学习等。专家系统学习、机器人学习、自然语言理解学习等。按对人类学习的模拟方式按对人类学习的模拟方式符号主义学习、连接主义学习等。符号主义学习、连接主义学习等。6.1.2机器学习的概念机器学习的概念4.机器学习的类型机器学习的类型76.1.3符号学习系统的基本模型符号学习系统的基本模型环境环境学习环节学习环节知识库知识库执行环节执行环节环境环境是学习系统所感知到的外界信息集合，也是学习系统的外界来源。信息的是学习系统所感知到的外界信息集合，也是学习系统的外界来源。信息的水平（一般化程度）和质量（正确性）对学习系统影响较大。水平（一般化程度）和质量（正确性）对学习系统影响较大。学习环节学习环节对环境供应的信息进行整理、分析归纳或类比，形成学问，并将其放入学对环境供应的信息进行整理、分析归纳或类比，形成学问，并将其放入学问库。问库。学问库学问库存储经过加工后的信息（即学问）。其表示形式是否合适特殊重要。存储经过加工后的信息（即学问）。其表示形式是否合适特殊重要。执行环节执行环节依据学问库去执行一系列任务，并将执行结果或执行过程中获得的信息反依据学问库去执行一系列任务，并将执行结果或执行过程中获得的信息反馈给学习环节。学习环节再利用反馈信息对学问进行评价，进一步改善执行馈给学习环节。学习环节再利用反馈信息对学问进行评价，进一步改善执行环节的行为。环节的行为。8第第6章章符号学习符号学习7.1机器学习概述机器学习概述7.2记忆学习记忆学习7.3示例学习示例学习7.4决策树学习决策树学习7.5统计学习统计学习9记忆学习也叫死记硬背学习，其基本过程是每当系统解决一个问题时，就记忆学习也叫死记硬背学习，其基本过程是每当系统解决一个问题时，就系统就记住这个问题和它的解，当以后再遇到此类问题时，不必重新计算，系统就记住这个问题和它的解，当以后再遇到此类问题时，不必重新计算，干脆找出原来的解即可运用。记忆学习的基本模型如下：干脆找出原来的解即可运用。记忆学习的基本模型如下：(x1,x2,xn)(y1,y2,yn)(x1,x2,xn),(y1,y2,yn)f存储存储输入模式输入模式执行函数执行函数输出模式输出模式输入输出模式对输入输出模式对6.2记忆学习记忆学习执行函数执行函数f是记忆学习系统的核心，若将由环境得到的输入模式记为是记忆学习系统的核心，若将由环境得到的输入模式记为(x1,x2,xn)，f的作用就是要对该输入模式进行计算，得到其对应的输出的作用就是要对该输入模式进行计算，得到其对应的输出模式模式(y1,y2,ym)。即如下输入。即如下输入/输出模式对：输出模式对：(x1,x2,xn)，(y1,y2,ym)然后，由系统将这一输入然后，由系统将这一输入/输出模式对保存到学问库中，当以后再遇见输入输出模式对保存到学问库中，当以后再遇见输入模式模式(x1,x2,xn)时，就可以干脆从存储器中把时，就可以干脆从存储器中把(y1,y2,ym)检索出来，检索出来，而不须要重新进行计算。而不须要重新进行计算。10第第6章章符号学习符号学习6.1机器学习的基本概念机器学习的基本概念6.2记忆学习记忆学习6.3示例学习示例学习6.3.1示例学习的类型示例学习的类型6.3.2示例学习的模型示例学习的模型6.3.3示例学习的归纳方法示例学习的归纳方法6.4决策树学习决策树学习6.5统计学习统计学习11按例子的来源分类按例子的来源分类例子来源于老师的示例学习例子来源于老师的示例学习例子来源于学习者本身的示例学习例子来源于学习者本身的示例学习学习者明确知道自己的状态，但完全不清晰所要获得的概念。学习者明确知道自己的状态，但完全不清晰所要获得的概念。例子来源于学习者以外的外部环境的示例学习例子来源于学习者以外的外部环境的示例学习例子的产生是随机的。例子的产生是随机的。按例子的类型分类按例子的类型分类仅利用正例的示例学习仅利用正例的示例学习这种学习方法会使推出的概念的外延扩大化。这种学习方法会使推出的概念的外延扩大化。利用正例和反例的示例学习利用正例和反例的示例学习这是示例学习的一种典型方式，它用正例用来产生概念，用反例用来防止这是示例学习的一种典型方式，它用正例用来产生概念，用反例用来防止概念外延的扩大。概念外延的扩大。6.3.1示例学习的类型示例学习的类型12示例空间示例空间规则空间规则空间验证过程验证过程归纳过程归纳过程 示例空间 是我们向系统供应的示教例子的集合。探讨问题：例子质量，搜寻方法。归纳过程 是从搜寻到的示例中抽象出一般性的学问的归纳过程。归纳方法：常量转换为变量，去掉条件，增加选择，曲线拟合等。规则空间 是事务所具有的各种规律的集合。探讨问题：对空间的要求，搜寻方法 验证过程 是要从示例空间中选择新的示例，对刚刚归纳出的规则做进一步的验证和修改。6.3.2示例学习的模型示例学习的模型13 把示例中的常量换成相应的变量即可得到一个一般性的规则。下面以扑克牌中同花的概念为例，进行探讨。假设例子空间中有以下两个关于扑克牌中“同花”概念的示例：示例1：花色(c1，梅花)花色(c2，梅花)花色(c3，梅花)花色(c4，梅花)花色(c5，梅花)同花(c1,c2,c3,c4,c5)示例2：花色(c1，红桃)花色(c2，红桃)花色(c3，红桃)花色(c4，红桃)花色(c5，红桃)同花(c1,c2,c3,c4,c5)其中，示例1表示5张梅花牌是同花，示例2表示5张红桃牌是同花。对这两个示例，采把常量化为变量的归纳方法，只要把“梅花”和“红桃”用变量x代换，就可得到如下一般性的规则：规则1：花色(c1，x)花色(c2，x)花色(c3，x)花色(c4，x)花色(c5，x)同花(c1,c2,c3,c4,c5)6.3.3示例学习的归纳方法示例学习的归纳方法1.把常量转化为变量把常量转化为变量14该方法是要把示例中的某些无关的子条件舍去，得到一个一般性的结论该方法是要把示例中的某些无关的子条件舍去，得到一个一般性的结论例如，有如下示例：例如，有如下示例：示例示例3：花色花色(c1,红桃红桃)点数点数(c1，2)花色花色(c2,红桃红桃)点数点数(c2，3)花色花色(c3,红桃红桃)点数点数(c3，4)花色花色(c4,红桃红桃)点数点数(c4，5)花色花色(c5,红桃红桃)点数点数(c5，6)同花同花(c1,c2,c3,c4,c5)6.3.3示例学习的归纳方法示例学习的归纳方法2.去掉条件去掉条件为了学习同花的概念，除了须要把常量变为变量外，还须要把与花色无关为了学习同花的概念，除了须要把常量变为变量外，还须要把与花色无关的的“点数点数”子条件舍去。这样也可得到上述规则子条件舍去。这样也可得到上述规则1：规则规则1：花色：花色(c1，x)花色花色(c2，x)花色花色(c3，x)花色花色(c4，x)花花色色(c5，x)同花同花(c1,c2,c3,c4,c5)156.3.3示例学习的归纳方法示例学习的归纳方法3.增加选择增加选择该方法是要在析取条件中增加一个新的析取项。它包括前件析取法和内部该方法是要在析取条件中增加一个新的析取项。它包括前件析取法和内部析取法。析取法。前件析取法：是通过对示例的前件的析取来形成学问的。例如：前件析取法：是通过对示例的前件的析取来形成学问的。例如：示例示例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脸脸(c1)示例示例9：点数：点数c1K脸脸(c1)用内部析取法，可得到如下规则：用内部析取法，可得到如下规则：规则规则3：点数：点数(c1)J,Q,K脸脸(c1)16对数值问题的归纳可接受曲线拟合法。假设示例空间中的每个示例对数值问题的归纳可接受曲线拟合法。假设示例空间中的每个示例(x,y,z)都是输入都是输入x,y与输出与输出z之间关系的三元组。例如，有下之间关系的三元组。例如，有下3个示例：个示例：示例示例10：(0,2,7)示例示例11：(6,-1,10)示例示例12：(-1,-5,-16)用最小二乘法进行曲线拟合，可得用最小二乘法进行曲线拟合，可得x,y,z之间关系的规则如下：之间关系的规则如下：规则规则4：z=2x+3y+1说明：在上述前三种方法中，方法说明：在上述前三种方法中，方法(1)是把常量转换为变量；方法是把常量转换为变量；方法(2)是去掉是去掉合取项（约束条件）；方法合取项（约束条件）；方法(3)是增加析取项。它们都是要扩大条件的适用范是增加析取项。它们都是要扩大条件的适用范围。从归纳速度上看，方法围。从归纳速度上看，方法(1)的归纳速度快，但简洁出错；方法的归纳速度快，但简洁出错；方法(2)归纳速度归纳速度慢，但不简洁出错。因此，在运用方法慢，但不简洁出错。因此，在运用方法(1)时应特殊当心。例如：时应特殊当心。例如：对示例对示例4、示例、示例5及示例及示例6，若运用方法，若运用方法(1),则会归纳出如下的错误规则：则会归纳出如下的错误规则：规则规则5：（错误）点数：（错误）点数(c1,x)脸脸(c1)它说明，归纳过程是很简洁出错的。它说明，归纳过程是很简洁出错的。6.3.3示例学习的归纳方法示例学习的归纳方法4.曲线拟合曲线拟合17第第6章章符号学习符号学习7.1机器学习的基本概念机器学习的基本概念7.2记忆学习记忆学习7.3示例学习示例学习7.4决策树学习决策树学习7.4.1决策树的概念决策树的概念7.3.2ID3算法算法7.5统计学习统计学习18决策树是一种由节点和边构成的用来描述分类过程的层次数据结构。决策树是一种由节点和边构成的用来描述分类过程的层次数据结构。根节点：表示分类的起先根节点：表示分类的起先叶节点：表示一个实例的结束叶节点：表示一个实例的结束中间节点：表示相应实例中的某一属性中间节点：表示相应实例中的某一属性边代表：某一属性可能的属性值边代表：某一属性可能的属性值路径：从根节点到叶节点的每一条路径都代表一个具体的实例，并且同一路径：从根节点到叶节点的每一条路径都代表一个具体的实例，并且同一路径上的全部属性之间为合取关系，不同路径（即一个属性的不同属性值）路径上的全部属性之间为合取关系，不同路径（即一个属性的不同属性值）之间为析取关系。之间为析取关系。决策树的分类过程：从树的根接点起先，依据给定的事例的属性值去测试决策树的分类过程：从树的根接点起先，依据给定的事例的属性值去测试对应的树枝，并依次下移，直至到达某个叶节点为止。对应的树枝，并依次下移，直至到达某个叶节点为止。图图6.4是一个简洁的用来对鸟类进行分类的决策树。在该图中，根节点包含是一个简洁的用来对鸟类进行分类的决策树。在该图中，根节点包含各种鸟类；叶节点是所能识别的各种鸟的名称；中间节点是鸟的一些属性；各种鸟类；叶节点是所能识别的各种鸟的名称；中间节点是鸟的一些属性；边是鸟的某一属性的属性值；边是鸟的某一属性的属性值；从根节点到叶节点的每一条路径都描述了一种鸟，它包括该种鸟的一些属从根节点到叶节点的每一条路径都描述了一种鸟，它包括该种鸟的一些属性及相应的属性值。性及相应的属性值。6.4.1决策树的概念决策树的概念19鸟类鸟类家养家养可能是和平鸽可能是和平鸽可能是可能是信天翁信天翁游泳游泳可能是可能是企鹅企鹅可能是可能是鸵鸟鸵鸟图图6.4一个简单的鸟类识别决策树一个简单的鸟类识别决策树会飞会飞不会飞不会飞是是不是不是会会不会不会决策树还可以表示为规则的形式。上图的决策树可表示为如下规则集：决策树还可以表示为规则的形式。上图的决策树可表示为如下规则集：IF鸟类会飞鸟类会飞AND是家养的是家养的THEN可能是和平鸽可能是和平鸽IF鸟类会飞鸟类会飞AND不是家养的不是家养的THEN可能是信天翁可能是信天翁IF鸟类不会飞鸟类不会飞AND会游泳会游泳THEN可能是企鹅可能是企鹅IF鸟类不会飞鸟类不会飞AND不会游泳不会游泳THEN可能是鸵鸟可能是鸵鸟决策树学习过程事实上是一个构造决策树的过程。当学习完成后，就可以决策树学习过程事实上是一个构造决策树的过程。当学习完成后，就可以利用这棵决策树对未知事物进行分类。利用这棵决策树对未知事物进行分类。6.4.1决策树的概念决策树的概念207.4.2ID3算法算法 ID3算法是昆兰（J.R.Quinlan）于1979年提出的一种以信息熵的下降速度作为属性选择标准的一种学习算法。其输入是一个用来描述各种已知类别的例子集，学习结果是一棵用于进行分类的决策树。主要探讨：ID3算法的数学基础 ID3算法的学习过程和例子 216.4.2ID3算法算法1.数学基础数学基础信息熵信息熵信息熵是对信息源整体不确定性的度量。假设信息熵是对信息源整体不确定性的度量。假设X为信源，为信源，xi为为X所发出的所发出的单个信息，单个信息，P(xi)为为X发出发出xi的概率，则信息熵可定义为：的概率，则信息熵可定义为：其中，其中，k为信源为信源X发出的全部可能的信息类型，对数可以是以各种数为底的对发出的全部可能的信息类型，对数可以是以各种数为底的对数，在数，在ID3算法中，我们取以算法中，我们取以2为底的对数。为底的对数。信息熵反应的是信源每发出一个信息所供应的平均信息量。信息熵反应的是信源每发出一个信息所供应的平均信息量。条件熵条件熵条件熵是收信者在收到信息后对信息源不确定性的度量。若假设信源为条件熵是收信者在收到信息后对信息源不确定性的度量。若假设信源为X，收信者收到的信息为，收信者收到的信息为Y，P(xi/yj)为当为当Y为为yj时时X为为xi的条件概率，则条件熵的条件概率，则条件熵可定义为：可定义为：表示收信者收到表示收信者收到Y后对后对X不确定性的估计。不确定性的估计。226.4.2ID3算法算法2.算法及举例算法及举例(1/9)ID3算法的学习过程：算法的学习过程：(1)首先以整个例子集作为决策树的根节点首先以整个例子集作为决策树的根节点S，并计算，并计算S关于每个属关于每个属性的期望熵（即条件熵）；性的期望熵（即条件熵）；(2)然后选择能使然后选择能使S的期望熵为最小的一个属性对根节点进行扩展，的期望熵为最小的一个属性对根节点进行扩展，得到根节点的一层子节点；得到根节点的一层子节点；(3)接着再用同样的方法对这些子节点进行分裂，直至全部叶节点接着再用同样的方法对这些子节点进行分裂，直至全部叶节点的熵值都下降为的熵值都下降为0为止。为止。这时，就可得到一棵与训练例子集对应的熵为这时，就可得到一棵与训练例子集对应的熵为0的决策树，即的决策树，即ID3算算法学习过程所得到的最终决策树。该树中每一条从根节点到叶节点的法学习过程所得到的最终决策树。该树中每一条从根节点到叶节点的路径，都代表了一个分类过程，即决策过程。路径，都代表了一个分类过程，即决策过程。23例例6.1用用ID3算法完成下述学生选课的例子算法完成下述学生选课的例子假设将决策假设将决策y分为以下类：分为以下类：y1：必修：必修AIy2：选修：选修AIy3：不修：不修AI做出这些决策的依据有以下做出这些决策的依据有以下3个属性：个属性：x1：学历层次：学历层次x1=1探讨生，探讨生，x1=2本科本科x2：专业类别：专业类别x2=1电信类，电信类，x2=2机电类机电类x3：学习基础：学习基础x3=1修过修过AI，x3=2未修未修AI表表6.1给出了一个关于选课决策的训练例子集给出了一个关于选课决策的训练例子集S。6.4.2ID3算法算法2.算法及举例算法及举例(2/9)24该训练例子集该训练例子集S的大小为。的大小为。ID3算法就是依据这些训练例子，以算法就是依据这些训练例子，以S为根节为根节点，依据信息熵下降最大的原则来构造决策树的。点，依据信息熵下降最大的原则来构造决策树的。6.4.2ID3算法算法2.算法及举例算法及举例(3/9)表表6-1学生选课决策的训练例子集学生选课决策的训练例子集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的属性值，的属性值，St为为xi=t时的例子集，时的例子集，|S|和和|St|分别是例子集分别是例子集S和和St的大小。的大小。6.4.2ID3算法算法2.算法及举例算法及举例(4/9)26下面先计算下面先计算S关于属性关于属性x1的条件熵：的条件熵：在表在表6-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中的各个例子的序号，且有中的各个例子的序号，且有|S|=8，|S1|=|S2|=4。由由S1可知可知：Ps1(y1)=1/4,Ps1(y2)=1/4,Ps1(y3)=2/4则有：则有：H(S1)=-Ps1(y1)log2Ps1(y1)-Ps1(y2)log2Ps1(y2)-Ps1(y3)log2Ps1(y3)=-(1/4)log2(1/4)-(1/4)log2(1/4)-(2/4)log2(2/4)=1.56.4.2ID3算法算法2.算法及举例算法及举例(5/9)27再由再由S2可知：可知：Ps2(y1)=0/4,Ps2(y2)=1/4,Ps2(y3)=3/4则有：则有：H(S2)=Ps2(y2)log2Ps2(y2)-Ps2(y3)log2Ps2(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.1557H(S/x3)=0.75可见，应当选择属性可见，应当选择属性x3对根节点进行扩展。用对根节点进行扩展。用x3对对S扩展后所得到的得到扩展后所得到的得到部分决策树如图部分决策树如图6.5所示。所示。6.4.2ID3算法算法2.算法及举例算法及举例(6/9)28在该树中，节点在该树中，节点“x3=1,y3”为决策方案为决策方案y3。由于。由于y3已是具体的决策方案，已是具体的决策方案，故该节点的信息熵为故该节点的信息熵为0，已经为叶节点。，已经为叶节点。节点节点“x3=2,x1,x2？”的含义是须要进一步考虑学历和专业这两个属性，的含义是须要进一步考虑学历和专业这两个属性，它是一个中间节点，还须要接着扩展。至于其扩展方法与上面的过程类似。它是一个中间节点，还须要接着扩展。至于其扩展方法与上面的过程类似。通过计算可知，该节点对属性通过计算可知，该节点对属性x1和和x2，其条件熵均为，其条件熵均为1。由于它对属性。由于它对属性x1和和x2的条件熵相同，因此可以先选择的条件熵相同，因此可以先选择x1，也可以先选择，也可以先选择x2。依此进行下去，依此进行下去，若先选择若先选择x1可得到如图可得到如图6.6所示的最终的决策树；若先选所示的最终的决策树；若先选择择x2可得到如图可得到如图7.7所示的最终的决策树。所示的最终的决策树。6.4.2ID3算法算法2.算法及举例算法及举例(7/9)Sx3=1,y3x3=2,x1,x2图图6.5部分决策树部分决策树x3=1x3=2修过修过AI不修不修AI未修未修AI学历和专业？学历和专业？29S不修不修AI学历和专业？学历和专业？图图6.6最终的决策树最终的决策树修过修过AI，x3=1未修未修AI,x3=2专业？专业？专业？专业？必修必修AI选修选修AI选修选修AI不修不修AI探探 讨讨 生生,x1=1本科生本科生,x1=2电信类电信类,x2=1机电类机电类,x2=2机电类机电类,x2=2电信类电信类,x2=16.4.2ID3算法算法2.算法及举例算法及举例(8/9)306.4.2ID3算法算法2.算法及举例算法及举例(9/9)Sx3=1,y3x3=2,x1,x2图图6.7最终的决策树最终的决策树x3=1x3=2x2=1,x1x2=2,x1x1=1,y1x1=2,y2x1=1,y2x1=2,y3x2=1x2=2x1=1x1=2x1=2x1=131第第6章章符号学习符号学习6.1机器学习的基本概念机器学习的基本概念6.2记忆学习记忆学习6.3示例学习示例学习6.4决策树学习决策树学习6.5统计学习统计学习 统计学习是一种基于小样本理论的学习方法，其典型方法是支持向量机统计学习是一种基于小样本理论的学习方法，其典型方法是支持向量机（SupportVectorMachine.SVM）。6.5.1小样本统计学习理论小样本统计学习理论6.5.2支持向量机支持向量机32小小样样本本统统计计学学习习理理论论一一种种以以有有限限样样本本统统计计学学理理论论为为基基础础进进行行统统计计学学习习的的理理论论。其其核核心心是是结结构构风风险险最最小小化化原原理理，涉涉及及的的概概念念主主要要包包括括阅阅历历风风险险、期期望望风风险险和和VC维等。维等。6.5.1小样本统计学习理论小样本统计学习理论1.期望风险和阅历风险期望风险和阅历风险(1/2)期望风险期望风险统计学习是要依据给定的训练样本，求出用联合概率分布函数统计学习是要依据给定的训练样本，求出用联合概率分布函数P(x,y)表示的表示的输入变量集输入变量集x和输出变量集和输出变量集y之间未知的依靠关系，并使期望风险最小。之间未知的依靠关系，并使期望风险最小。设有设有n个独立且同分布（即具有相同概率分布）的训练样本个独立且同分布（即具有相同概率分布）的训练样本（x1,y1），（），（x2,y2），），（，（xn,yn）在一个函数集在一个函数集f(x,w)中求出一个最优函数中求出一个最优函数f(x,w0)，使得系统用该函数对依，使得系统用该函数对依靠关系进行估计时期望风险靠关系进行估计时期望风险为最小。为最小。其中，其中，w为函数的广义参数；为函数的广义参数；f(x,w)为学习函数集（或预料函数集），它可为学习函数集（或预料函数集），它可以表示任何函数集，用于从以表示任何函数集，用于从x预料预料y，目的是通过对训练样本的学习得到一个，目的是通过对训练样本的学习得到一个最优函数最优函数f(x,w0)；L(y,f(x,w)为损失函数，表示因预料失误而产生的损失，为损失函数，表示因预料失误而产生的损失，该函数的具体表示形式与学习问题的类型有关。该函数的具体表示形式与学习问题的类型有关。（6.1）336.5.1小样本统计学习理论小样本统计学习理论1.期望风险和阅历风险期望风险和阅历风险(2/2)对期望风险进行估计。对期望风险进行估计。阅历风险则是用样本损失的算术平均值进行计算的。阅历风险则是用样本损失的算术平均值进行计算的。统计学习的目标就是要设计学习算法，使得该阅历风险最小化。这一原理统计学习的目标就是要设计学习算法，使得该阅历风险最小化。这一原理也称为阅历风险最小化原理。也称为阅历风险最小化原理。阅历风险阅历风险对上述期望风险函数，由于其中的概率分布函数对上述期望风险函数，由于其中的概率分布函数P(x,y)未知，因此无法干脆未知，因此无法干脆对其进行计算。常用的方法是利用阅历风险函数对其进行计算。常用的方法是利用阅历风险函数（6.2）34(1)打散操作打散操作6.5.1小样本统计学习理论小样本统计学习理论2.VC维维(1/3)VC维是小样本统计学习理论中的又一个重要概念，用于描述构成学习模维是小样本统计学习理论中的又一个重要概念，用于描述构成学习模型的函数集合的容量及学习实力。通常，其型的函数集合的容量及学习实力。通常，其VC维越大、容量越大、学习实维越大、容量越大、学习实力越强。力越强。由于由于VC维是通过维是通过“打散打散”操作定义的，下面先探讨打散操作。操作定义的，下面先探讨打散操作。样本集的打散（样本集的打散（shatter）操作可描述如下：）操作可描述如下：假设假设X为样本空间，为样本空间，S是是X的一个子集，的一个子集，H是由指示性学习函数所构成的指是由指示性学习函数所构成的指示函数集。对一个样本集示函数集。对一个样本集S，若其大小为，若其大小为h，则它应当有，则它应当有2h种划分，假设种划分，假设S中的中的每一种划分都能被每一种划分都能被H中的某个指示函数将其分为两类，则称函数集中的某个指示函数将其分为两类，则称函数集H能够打散能够打散样本集样本集S。所谓指示性学习函数是指其值只能取所谓指示性学习函数是指其值只能取0或或1的学习函数。的学习函数。356.5.1小样本统计学习理论小样本统计学习理论2.VC维维(2/3)例例6.10对二维实空间对二维实空间R2，假设给定的样本集，假设给定的样本集S为为R2中的不共线的中的不共线的3个数据点，个数据点，每个数据点有两种状态，指示函数集每个数据点有两种状态，指示函数集H为有向直线的集合，求为有向直线的集合，求H是否可以打散是否可以打散S？解：解：S中不共线的中不共线的3个数个数据点可构成据点可构成23种不同的点种不同的点集，如图集，如图6.10所示。在该所示。在该图中，可以看出，每一点图中，可以看出，每一点集中的数据点，都能被集中的数据点，都能被H中的一条有向直线按其状中的一条有向直线按其状态分为两类。即位于有向态分为两类。即位于有向直线正方向一侧的数据点直线正方向一侧的数据点为一类，而位于有向直线为一类，而位于有向直线负方向一侧的数据点为另负方向一侧的数据点为另一类。因此，我们说一类。因此，我们说H能能够打散够打散S。图图6.10在在R2中被中被H打散的打散的3个数据点个数据点36(2)VC维的确定维的确定6.5.1小样本统计学习理论小样本统计学习理论2.VC维维(3/3)VC维用来表示指示函数集维用来表示指示函数集H能够打散一个样本集能够打散一个样本集S的实力，其值定义为能被的实力，其值定义为能被H打散的打散的X的最大有限子集的大小。若样本空间的最大有限子集的大小。若样本空间X的随意有限大的子集都可以的随意有限大的子集都可以被被H打散，则其打散，则其VC为为。例如，对前面给出的例例如，对前面给出的例6.10，指示函数集，指示函数集H中的有向直线能够将大小为中的有向直线能够将大小为3的的X的子集的子集S打散，但却不能打散的打散，但却不能打散的4个点，如图个点，如图6.11，因此该，因此该H的的VC维至少为维至少为3。可见，在可见，在R2中，由有向直线构成的指示函数集中，由有向直线构成的指示函数集H，所能打散的，所能打散的R2的最大子的最大子集为集为3，因此，因此H的的VC维为维为3.须要指出的是，目前还没有一套关于随意须要指出的是，目前还没有一套关于随意H的的VC维的计算理论，只是对一维的计算理论