机器学习入门介绍PPT课件.ppt

Artificial Intelligence Principles and Applications 第第 7 章章 机器学习机器学习 (Machine Learning) 桑克（桑克（R. Shank)： “一台计算机若不会学习，就不能说它具一台计算机若不会学习，就不能说它具有智能。有智能。” 2第7章 机器学习7.1 机器学习的基本概念机器学习的基本概念7.2 机械式学习机械式学习7.3 指导式学习指导式学习7.4 归纳学习归纳学习7.5 类比学习类比学习7.6 基于解释的学习基于解释的学习7.7 学习方法的比较与展望学习方法的比较与展望7.1 机器学习的基本概念机器学习的基本概念37.1 机器学习的基本概念7.1.1 学习学习7.1.2 机器学习机器学习7.1.3 机器学习系统机器学习系统7.1.4 机器学习的发展机器学习的发展7.1.5 机器学习的分类机器学习的分类4 7.1.1 学习（1）学习是系统改进其性能的过程：西蒙，）学习是系统改进其性能的过程：西蒙，1980。（2）学习是获取知识的过程。）学习是获取知识的过程。（3）学习是技能的获取。）学习是技能的获取。（4）学习是事物规律的发现过程。）学习是事物规律的发现过程。 学习学习：一个有特定目的的知识获取过程。：一个有特定目的的知识获取过程。 内在行为内在行为：获取知识、积累经验、发现规律。：获取知识、积累经验、发现规律。 外部表现外部表现：改进性能、适应环境、实现系统的自我完善。：改进性能、适应环境、实现系统的自我完善。 “学习是系统中的学习是系统中的任何改进，这种改任何改进，这种改进使得系统在重复进使得系统在重复同样的工作或进行同样的工作或进行类似的工作时，能类似的工作时，能完成得更好。完成得更好。”例如例如“小孩学走路小孩学走路”、“学弹钢琴学弹钢琴”等。等。学习：从感性知识到理性知识的认识过程，从表层知学习：从感性知识到理性知识的认识过程，从表层知识到深层知识的转换过程。识到深层知识的转换过程。57.1 机器学习的基本概念7.1.1 学习学习7.1.2 机器学习机器学习7.1.3 机器学习系统机器学习系统7.1.4 机器学习的发展机器学习的发展7.1.5 机器学习的分类机器学习的分类6 机器学习机器学习(Machine Learning)：计算机能模拟人的：计算机能模拟人的学习行为，自动地通过学习获取知识和技能，不断学习行为，自动地通过学习获取知识和技能，不断改善性能，实现自我完善。改善性能，实现自我完善。 7.1.2 机器学习1）学习机理学习机理: 对学习机制的研究，即人类获取知识、技能和对学习机制的研究，即人类获取知识、技能和抽象概念的天赋能力。抽象概念的天赋能力。 2）学习方法学习方法：在生物学习机理进行简化的基础上，用计算的：在生物学习机理进行简化的基础上，用计算的方法进行再现。方法进行再现。3）学习系统学习系统：根据特定任务的要求，建立相应的学习系统。：根据特定任务的要求，建立相应的学习系统。77.1 机器学习的基本概念7.1.1 学习学习7.1.2 机器学习机器学习7.1.3 机器学习系统机器学习系统7.1.4 机器学习的发展机器学习的发展7.1.5 机器学习的分类机器学习的分类81. 机器学习系统的定义机器学习系统的定义 学习系统：学习系统：能够在一定程度上实现机器学习的系统。能够在一定程度上实现机器学习的系统。 萨利斯萨利斯(Saris)的定义（的定义（1973年）年）：能够从：能够从某个过程或环某个过程或环境境的未知特征中的未知特征中学到有关信息学到有关信息，并且能把学到的信息，并且能把学到的信息用用于于未来的估计、分类、决策或控制，以便未来的估计、分类、决策或控制，以便改进系统的性改进系统的性能能。 施密斯等的定义（施密斯等的定义（1977年）年）：在与在与环境环境相互作用时，能相互作用时，能利用利用过去过去与环境作用时得到的信息与环境作用时得到的信息，并，并提高其性能提高其性能。7.1 机器学习的基本概念机器学习的基本概念 7.1.3 机器学习系统9 2. 机器学习系统的条件和能力机器学习系统的条件和能力 （1）具有适当的学习环境）具有适当的学习环境（2）具有一定的学习能力）具有一定的学习能力 （3）能应用学到的知识求解问题）能应用学到的知识求解问题 （4）能提高系统的性能）能提高系统的性能 7.1.3 机器学习系统10 3. 机器学习系统的基本模型机器学习系统的基本模型7.1.3 机器学习系统执行与评价环境学习知识库学习系统的基本结构学习系统的基本结构117.1 机器学习的基本概念7.1.1 学习学习7.1.2 机器学习机器学习7.1.3 机器学习系统机器学习系统7.1.4 机器学习的发展机器学习的发展7.1.5 机器学习的分类机器学习的分类127.1.4 机器学习的发展1. 神经元模型的研究（神经元模型的研究（20世纪世纪50年代中期年代中期） 主要研究工作：应用主要研究工作：应用决策理论的方法决策理论的方法研制可适应环境的研制可适应环境的通用通用学习系统（学习系统（general purpose learning system）。 1957年，罗森勃拉特（年，罗森勃拉特（F. Rosenblatt）提出）提出感知器模型感知器模型。 塞缪尔（塞缪尔（Samuel）的）的跳棋程序跳棋程序：分析了约：分析了约175000副不同棋局副不同棋局后，归纳出了棋类书上推荐的走法，准确率达到后，归纳出了棋类书上推荐的走法，准确率达到48。 1 9 6 9 年 ， 明 斯 基 和 佩 珀 特 （年 ， 明 斯 基 和 佩 珀 特 （ P a p e r t ） 发 表 了 论 著） 发 表 了 论 著Perceptron，对神经元模型的研究作出了悲观的论断。，对神经元模型的研究作出了悲观的论断。 137.1.4 机器学习的发展2. 符号学习的研究（符号学习的研究（20世纪世纪70年代中期年代中期）符号概念获取的学习方法符号概念获取的学习方法（1970年）：模拟人类的概年）：模拟人类的概念学习过程，通过分析一些概念的正例和反例构造出念学习过程，通过分析一些概念的正例和反例构造出这些概念的符号表示。这些概念的符号表示。莫斯托夫（莫斯托夫（D. J. Mostow）的）的指导式学习指导式学习。温斯顿（温斯顿（Winston）和卡鲍尼尔（）和卡鲍尼尔（J. G. Carbonell）的）的类比学习类比学习。米切尔（米切尔（T. M. Mitchell）等人的）等人的解释学习解释学习。147.1.4 机器学习的发展3. 连接学习的研究（连接学习的研究（20世纪世纪80年代年代） 连接学习：一种以非线性大规模并行处理为主流的神连接学习：一种以非线性大规模并行处理为主流的神经网络研究。经网络研究。 1980年，在卡内基梅隆大学召开了第一届机器学习年，在卡内基梅隆大学召开了第一届机器学习国际研讨会。国际研讨会。 1986年，创刊了第一本机器学习杂志年，创刊了第一本机器学习杂志Machine Learning。 157.1 机器学习的基本概念7.1.1 学习学习7.1.2 机器学习机器学习7.1.3 机器学习系统机器学习系统7.1.4 机器学习的发展机器学习的发展7.1.5 机器学习的分类机器学习的分类167.1.5 机器学习的分类 1. 按学习方法分类（温斯顿，按学习方法分类（温斯顿，1977 ）：）：机械式学习、指导式学习、示例学习、类比学习、机械式学习、指导式学习、示例学习、类比学习、 解释学习等。解释学习等。2. 按学习能力分类：按学习能力分类：监督学习监督学习（有教师学习）（有教师学习）177.1.5 机器学习的分类 2. 按学习能力分类：按学习能力分类： 再励学习（强化学习或增强学习）再励学习（强化学习或增强学习）187.1.5 机器学习的分类 2. 按学习能力分类：按学习能力分类： 非监督学习（无教师学习）非监督学习（无教师学习）3. 按推理方式分类：按推理方式分类：n基于演绎的学习（解释学习）。基于演绎的学习（解释学习）。n基于归纳的学习基于归纳的学习 （示例学习、发现学习等（示例学习、发现学习等 ）。）。4. 按综合属性分类：按综合属性分类：n归纳学习、分析学习、连接学习、归纳学习、分析学习、连接学习、 遗传式学习等。遗传式学习等。19第7章 机器学习7.1 机器学习的基本概念机器学习的基本概念7.2 机械式学习机械式学习7.3 指导式学习指导式学习7.4 归纳学习归纳学习7.5 类比学习类比学习7.6 基于解释的学习基于解释的学习7.7 学习方法的比较与展望学习方法的比较与展望207.2 机械式学习机械式学习 机械式机械式学习（学习（rote learning）又称又称记忆学习记忆学习，或，或死死记式学习记式学习：通过直接记忆或者存储外部环境所提供：通过直接记忆或者存储外部环境所提供的信息达到学习的目的，并在以后通过对知识库的的信息达到学习的目的，并在以后通过对知识库的检索得到相应的知识直接用来求解问题。检索得到相应的知识直接用来求解问题。 机械式学习机械式学习实质实质是用存储空间来换取处理时间。是用存储空间来换取处理时间。217.2 机械式学习 l在在给定搜索深度给定搜索深度下用估价函下用估价函数对格局进行评分，通过倒数对格局进行评分，通过倒推计算求出上层节点的推计算求出上层节点的倒推倒推值值，决定当前的，决定当前的最佳走步最佳走步。l 下次遇到相同情况，直接利下次遇到相同情况，直接利用倒推值决定最佳走步，不用倒推值决定最佳走步，不需重新计算。需重新计算。塞缪尔的跳棋程序塞缪尔的跳棋程序 CHECKERS以以 A A 为结点的博弈树为结点的博弈树QA6A博弈搜索树博弈搜索树2B6C2486912343865649622第7章 机器学习7.1 机器学习的基本概念机器学习的基本概念7.2 机械式学习机械式学习7.3 指导式学习指导式学习7.4 归纳学习归纳学习7.5 类比学习类比学习7.6 基于解释的学习基于解释的学习7.7 学习方法的比较与展望学习方法的比较与展望237.3 指导式学习指导式学习 指导式学习指导式学习（learning by being told）又称）又称嘱咐式嘱咐式学习学习或或教授式学习教授式学习：由外部环境向系统提供一般性：由外部环境向系统提供一般性的指示或建议，系统把它们具体地转化为细节知识的指示或建议，系统把它们具体地转化为细节知识并送入知识库中。在学习过程中要反复对形成的知并送入知识库中。在学习过程中要反复对形成的知识进行评价，使其不断完善。识进行评价，使其不断完善。 指导式学习的学习过程：征询指导者的指示或建指导式学习的学习过程：征询指导者的指示或建议议 、把征询意见转换为可执行的内部形式、把征询意见转换为可执行的内部形式 、加入知、加入知识库、评价。识库、评价。 247.3 指导式学习 简单征询：指导者给出一般性的意见，系统将其具体化。简单征询：指导者给出一般性的意见，系统将其具体化。 复杂征询：系统不仅要求指导者给出一般性的建议，而复杂征询：系统不仅要求指导者给出一般性的建议，而且还要具体地鉴别知识库中可能存在的问题，并给出修改且还要具体地鉴别知识库中可能存在的问题，并给出修改意见。意见。 被动征询：系统只是被动地等待指导者提供意见。被动征询：系统只是被动地等待指导者提供意见。 主动征询：系统不只是被动地接受指示，而且还能主动主动征询：系统不只是被动地接受指示，而且还能主动地提出询问，把指导者的注意力集中在特定的问题上。地提出询问，把指导者的注意力集中在特定的问题上。 1. 征询指导者的指示或建议征询指导者的指示或建议 257.3 指导式学习指导式学习 学习系统应具有把用约定形式表示的征询意见转化为计算机学习系统应具有把用约定形式表示的征询意见转化为计算机内部可执行形式的能力，并且能在转化过程中进行语法检查及内部可执行形式的能力，并且能在转化过程中进行语法检查及适当的语义分析。适当的语义分析。 2. 把征询意见转换为可执行的内部形式把征询意见转换为可执行的内部形式 在加入过程中要对知识进行一致性检查，以防止出现矛盾、在加入过程中要对知识进行一致性检查，以防止出现矛盾、冗余、环路等问题。冗余、环路等问题。 3. 加入知识库加入知识库 评价方法：对新知识进行经验测试，即执行一些标准例子，评价方法：对新知识进行经验测试，即执行一些标准例子，然后检查执行情况是否与已知情况一致。然后检查执行情况是否与已知情况一致。 4. 评价评价 26第7章 机器学习7.1 机器学习的基本概念机器学习的基本概念7.2 机械式学习机械式学习7.3 指导式学习指导式学习7.4 归纳学习归纳学习7.5 类比学习类比学习7.6 基于解释的学习基于解释的学习7.7 学习方法的比较与展望学习方法的比较与展望277.4 归纳学习7.4.1 归纳推理归纳推理7.4.2 示例学习示例学习7.4.3 观察与发现学习观察与发现学习28 7.4.1 归纳推理归纳推理归纳推理：应用归纳推理：应用归纳方法归纳方法所进行的推理，即从足够所进行的推理，即从足够多的事例中归纳出一般性的知识。多的事例中归纳出一般性的知识。它是一种从个别到一般、从部分到整体的推理。它是一种从个别到一般、从部分到整体的推理。归纳推理的重要特征：归纳推理的重要特征：归纳出的结论不能绝对保证归纳出的结论不能绝对保证它的正确性，只能以某种程度相信它为真它的正确性，只能以某种程度相信它为真。 例如，由例如，由“麻雀会飞麻雀会飞”、“鸽子会飞鸽子会飞”、“燕子会燕子会飞飞”归纳出归纳出“有翅膀的动物会飞有翅膀的动物会飞”、“长羽毛的动物会飞长羽毛的动物会飞”等结等结论。论。 29 从个别事例归纳出一般性知识的方法：从个别事例归纳出一般性知识的方法： 设设 ：某类事物：某类事物 A中的具体事物。中的具体事物。 已知已知 都有属性都有属性 P，并且没有发现反例。，并且没有发现反例。 当当 n 足够大时，可得出：足够大时，可得出：“ A中所有事物都有属性中所有事物都有属性 P” 。 7.4.1 归纳推理归纳推理n21 aaa， 1. 枚举归纳枚举归纳 n21 aaa， 30 例如，设有如下已知事例：例如，设有如下已知事例： 张三是足球运动员，他的体格健壮。张三是足球运动员，他的体格健壮。 李四是足球运动员，他的体格健壮。李四是足球运动员，他的体格健壮。 刘六是足球运动员，他的体格健壮。刘六是足球运动员，他的体格健壮。 事例足够多时，可归纳出一般性知识：事例足够多时，可归纳出一般性知识： 凡是足球运动员，他的体格一定健壮。凡是足球运动员，他的体格一定健壮。7.4.1 归纳推理归纳推理1. 枚举归纳枚举归纳 (0.9)31 已知两个事物已知两个事物 a与与 b有有 n个属性相似或相同，即：个属性相似或相同，即：a具有属性具有属性 P1， b也具有属性也具有属性 P1。 a具有属性具有属性 P2， b也具有属性也具有属性P2。 a具有属性具有属性 Pn， b也具有属性也具有属性Pn。 且且 a具有属性具有属性 Pn+1 ，则当，则当 n足够大时，可归纳出足够大时，可归纳出 b也具有属性也具有属性Pn+1。 7.4.1 归纳推理归纳推理2. 联想归纳联想归纳 32 设：设： 且且 则当则当A与与B中有新元素出现时（设中有新元素出现时（设 A 中的中的a及及B中的中的 b ），），若已知若已知 a 有属性，就可得出有属性，就可得出 b 有属性，即有属性，即 7.4.1 归纳推理归纳推理 3. 类比归纳类比归纳 12,Aa a,21bbB 1,2,.iiP aQ bi bQaP33 一般模式一般模式：（1）若）若 H 为真时，则为真时，则H E必为真或以置信度必为真或以置信度 cf1成立。成立。（2）观察到）观察到 E 成立或以置信度成立或以置信度cf2成立。成立。（3）则）则 H 以某种置信度以某种置信度 ( cf ) 成立。成立。7.4.1 归纳推理归纳推理4. 逆推理归纳：逆推理归纳：由结论成立推出前提以某种置信度成立。由结论成立推出前提以某种置信度成立。 用公式表示用公式表示 ：EH1cfE2cfHcf34 则则H的置信度：的置信度：7.4.1 归纳推理4. 逆推理归纳（续）逆推理归纳（续） EPHPcfEPHPHEPEHPf c1121cff ccfEH的置信度的置信度cf1 = P(H/E)HE的置信度的置信度cf1= P(E/H)EH1cfE2cfHcfHE1cfE2cfHcf357.4.1 归纳推理归纳推理5. 消除归纳消除归纳 消除归纳：通过不断否定原先的假设来得出结论消除归纳：通过不断否定原先的假设来得出结论。 已知：已知： 结论：结论：12111iniiniAAAAAAAAA367.4.1 归纳推理归纳推理演绎推理演绎推理归纳推理归纳推理 一般一般 个别个别 个别个别 一般一般 必然性推理必然性推理 或然性推理（或然性推理（“主观不充主观不充分置信分置信”的推理）的推理） 结论不会超出前提所断结论不会超出前提所断定定 的范围；的范围； 不能获取新知识。不能获取新知识。 结论适用于更大的范围；结论适用于更大的范围； 可获取新知识。可获取新知识。 演绎推理与归纳推理的区别演绎推理与归纳推理的区别 377.4 归纳学习7.4.1 归纳推理归纳推理7.4.2 示例学习示例学习7.4.3 观察与发现学习观察与发现学习387.4.2 示例学习示例学习 示例学习示例学习（learning from examples，实例学习实例学习或或从例子从例子中学习中学习） ：通过从环境中取得若干与某概念有关的例子，：通过从环境中取得若干与某概念有关的例子，经归纳得出一般性概念的一种学习方法。经归纳得出一般性概念的一种学习方法。 示例学习中，外部环境（教师）提供一组例子（正例和示例学习中，外部环境（教师）提供一组例子（正例和反例），然后从这些特殊知识中归纳出适用于更大范围的反例），然后从这些特殊知识中归纳出适用于更大范围的一般性知识，它将覆盖所有的正例并排除所有反例。一般性知识，它将覆盖所有的正例并排除所有反例。 397.4.2 示例学习1. 示例学习的学习模型示例学习的学习模型 示例空间验证搜索解释形成知识知识库 图图7.7 示例学习的学习模型示例学习的学习模型407.4.2 示例学习示例学习 2. 形成知识的方法形成知识的方法（1）变量代换常量变量代换常量 例如，假设有两个关于扑克牌例如，假设有两个关于扑克牌“同花同花”概念的示例。概念的示例。示例示例1：示例示例2： 12341234, , ,ccccc c c c花色（ ，梅花） 花色（ ，梅花） 花色（ ，梅花） 花色（ ，梅花）同花（）12341234,cxcxcxcxc c c c花色（ ， ） 花色（ ， ） 花色（ ， ） 花色（ ， ）同花（） 可得到一条一般性的知识：可得到一条一般性的知识：规则规则1：12341234, , ,ccccc c c c花色（ ，红桃） 花色（ ，红桃） 花色（ ，红桃） 花色（ ，红桃）同花（）417.4.2 示例学习示例学习 2. 形成知识的方法形成知识的方法（2） 舍弃条件舍弃条件 例如示例：例如示例： 12341234, , ,cxcxcxcxc c c c花色（ ，） 花色（ ，） 花色（ ，） 花色（ ，）同花（） 可得到一条一般性的知识：可得到一条一般性的知识：规则规则1：花色花色( c1,黑桃黑桃) 点数（点数（c1, 7） 花色花色( c2,黑桃黑桃) 点数（点数（c2, 3） 花色花色( c3,黑桃黑桃) 点数（点数（c3, 10） 花色花色( c4,黑桃黑桃) 点数（点数（c4, 5） 同花同花( c1, c2, c3, c4)427.4.2 示例学习示例学习 2. 形成知识的方法形成知识的方法（3）增加操作）增加操作 前件析取法前件析取法 例如例如关于关于“脸牌脸牌” 示例：示例： 111111cJccQccKc示例1：点数（ ， ）脸（ ）示例2：点数（ ， ）脸（ ）示例3：点数（ ，）脸（ ）1231cJcQcKc规则2： 点数 （ ， ） 点数（ ， ） 点数（ ， ）脸（ ）得到知识：得到知识：437.4.2 示例学习示例学习 2. 形成知识的方法形成知识的方法（3）增加操作）增加操作 内部析取法：在示例的表示中使用集合与集合间的成员内部析取法：在示例的表示中使用集合与集合间的成员关系来形成知识。关系来形成知识。 例如示例：例如示例： 111111 cJccQccKc示例1：点数（ ）脸（ ）示例2：点数（ ）脸（ ）示例3：点数（ ）脸（ ）11cJQKc点数（ ）， ，脸（ ）得到知识：得到知识：447.4.2 示例学习示例学习 2. 形成知识的方法形成知识的方法（4）合取变析取）合取变析取 例如：例如：“男同学男同学与与女同学可以组成一个班女同学可以组成一个班”。 归纳：归纳：“男同学男同学或或女同学可以组成一个班女同学可以组成一个班”。 （5） 归结归纳归结归纳 例如：例如： 得到：得到：11PEHPEH12EEHl 示例示例1：某天下雨，且：某天下雨，且自行车在路上出了毛自行车在路上出了毛病需修理病需修理，所以他上班迟到。，所以他上班迟到。l 示例示例2：某天没下雨，但：某天没下雨，但交通阻塞交通阻塞，所以他，所以他上班迟到。上班迟到。l 得到：如果得到：如果自行车在路上出了毛病需修理自行车在路上出了毛病需修理，或者或者交通阻塞交通阻塞，则他有可能上班迟到。，则他有可能上班迟到。457.4.2 示例学习示例学习 2. 形成知识的方法形成知识的方法（6）曲线拟合）曲线拟合 设在示例空间提供了一批如下形式的示例：设在示例空间提供了一批如下形式的示例：(x, y, z) 示例示例1：(1, 0, 10) 示例示例2：(2, 1, 18) 示例示例3：(-1, -2, -6)应用曲线拟合法（例如应用曲线拟合法（例如最小二乘法）最小二乘法）得到：得到： z=2x+6 y+8 467.4 归纳学习7.4.1 归纳推理归纳推理7.4.2 示例学习示例学习7.4.3 观察与发现学习观察与发现学习477.4.3 观察与发现学习观察与发现学习观察与发现学习（观察与发现学习（learning from observing and discovery）: 观察学习观察学习：用于对事例进行概念聚类，形成概：用于对事例进行概念聚类，形成概念描述。念描述。 发现学习发现学习：用于发现规律，产生定律或规则。：用于发现规律，产生定律或规则。 487.4.3 观察与发现学习观察与发现学习1. 概念聚类概念聚类( (1980年年, ,米卡尔斯基（米卡尔斯基（R. S. Michalski) 基本思想基本思想: : 把事例按一定的方式和准则进行分组，如划把事例按一定的方式和准则进行分组，如划分为不同的类，不同的层次等，使不同的组代表不同的概分为不同的类，不同的层次等，使不同的组代表不同的概念，并且对每一个组进行特征概括，得到一个概念的语义念，并且对每一个组进行特征概括，得到一个概念的语义符号描述。符号描述。 497.4.3 观察与发现学习观察与发现学习 1. 概念聚类概念聚类 例如事例：例如事例： 喜鹊、麻雀、布谷鸟、乌鸦、鸡、鸭、鹅，喜鹊、麻雀、布谷鸟、乌鸦、鸡、鸭、鹅， 分为两类：分为两类： 鸟鸟 = 喜鹊，麻雀，布谷鸟，乌鸦，喜鹊，麻雀，布谷鸟，乌鸦， 家禽家禽 = 鸡、鸭、鹅，鸡、鸭、鹅， 得知：得知： “鸟鸟有羽毛、有翅膀、会飞、会叫、野生有羽毛、有翅膀、会飞、会叫、野生”。 “家禽家禽有羽毛、有翅膀、会飞、会叫、家养有羽毛、有翅膀、会飞、会叫、家养”。507.4.3 观察与发现学习观察与发现学习 2. 发现学习发现学习 发现学习发现学习: 从系统的初始知识、观察事例或经验数据中从系统的初始知识、观察事例或经验数据中归纳出规律或规则。归纳出规律或规则。无教师指导的归纳学习无教师指导的归纳学习 经验发现经验发现: 从经验数据中发现规律和定律。从经验数据中发现规律和定律。 知识发现知识发现: 指从已观察的事例中发现新的知识。指从已观察的事例中发现新的知识。51第7章 机器学习7.1 机器学习的基本概念机器学习的基本概念7.2 机械式学习机械式学习7.3 指导式学习指导式学习7.4 归纳学习归纳学习7.5 类比学习类比学习7.6 基于解释的学习基于解释的学习7.7 学习方法的比较与展望学习方法的比较与展望52 7.5 类比学习7.5.1 类比推理类比推理7.5.2 属性类比学习属性类比学习7.5.3 转换类比学习转换类比学习类比学习类比学习(learning by analogy)：通过对相似事物进行比较所进行的通过对相似事物进行比较所进行的一种学习。一种学习。53 7.5.1 类比推理类比推理 类比推理：由新情况与记忆中的已知情况在某些类比推理：由新情况与记忆中的已知情况在某些方面相似，从而推出它们在其他相关方面也相似。方面相似，从而推出它们在其他相关方面也相似。 源域源域S：已经认识的域，包括过去曾经解决过且与：已经认识的域，包括过去曾经解决过且与当前问题类似的问题以及相关知识；当前问题类似的问题以及相关知识；目标域目标域T：当前尚未完全认识的域，是遇到的新问：当前尚未完全认识的域，是遇到的新问题。题。 类比推理的目的：从类比推理的目的：从源域源域S中选出与当前问题最近中选出与当前问题最近似的问题及其求解方法来求解当前的问题，或者建似的问题及其求解方法来求解当前的问题，或者建立起立起目标域目标域T中已有命题间的联系，形成新知识。中已有命题间的联系，形成新知识。54 7.5.1 类比推理类比推理 类比推理的推理过程：类比推理的推理过程： 1）回忆与联想：在）回忆与联想：在S中找出与当前情况相似的情况，并按中找出与当前情况相似的情况，并按相似度从高到低进行排序。相似度从高到低进行排序。 2）选择：选出与当前情况最相似的情况及其有关知识。）选择：选出与当前情况最相似的情况及其有关知识。 3）建立对应关系：在）建立对应关系：在S与与T的相似情况之间建立相应的映的相似情况之间建立相应的映射。射。 4）转换：把）转换：把 S中的有关知识引到中的有关知识引到T中，建立起求解当前问中，建立起求解当前问题的方法或者学习到关于题的方法或者学习到关于T的新知识。的新知识。 设设 S1与与 T1分别表示分别表示 S与与 T 中的某一情况，且中的某一情况，且S1与与 T1相似，相似，再假设再假设 S2与与 S1相关，则由类比推理可推出相关，则由类比推理可推出 T 中的中的 T2 ，且，且T2与与 S2相似。相似。55 7.5 类比学习7.5.1 类比推理类比推理7.5.2 属性类比学习属性类比学习7.5.3 转换类比学习转换类比学习567.5.2 属性类比学习属性类比学习 属性类比学习属性类比学习: : 根据两个相似事物的根据两个相似事物的属性属性实现类比实现类比学习的。学习的。 属性类比学习系统（属性类比学习系统（1979年，温斯顿）：年，温斯顿）： 源域和目标域都是用源域和目标域都是用框架框架表示的，分别称为表示的，分别称为源框架源框架和和目标框架目标框架。框架的槽用于表示事物的属性。框架的槽用于表示事物的属性。 学习过程学习过程: : 把把源框架源框架中的某些槽值传递到中的某些槽值传递到目标框架目标框架的相应槽中去。的相应槽中去。 577.5.2 属性类比学习属性类比学习候选槽候选槽：其槽值有可能要传递给目标框架的那些槽。：其槽值有可能要传递给目标框架的那些槽。选择的方法：选择的方法：（1）选择具有极端槽值的槽，例如）选择具有极端槽值的槽，例如“很大很大”、“很很小小”（2）选择已经被确认为）选择已经被确认为“重要槽重要槽”的槽的槽（3）选择与源框架相似的框架中不具有的槽）选择与源框架相似的框架中不具有的槽（4）选择相似框架中不具有这种槽值的槽）选择相似框架中不具有这种槽值的槽（5）选择源框架中的所有槽）选择源框架中的所有槽 1. 从从源框架源框架中选择若干槽作为中选择若干槽作为候选槽候选槽 587.5.2 属性类比学习属性类比学习筛选规则：筛选规则：（1）选择在目标框架中还未填值的槽。）选择在目标框架中还未填值的槽。 （2）选择在目标框架中为典型事例的槽。）选择在目标框架中为典型事例的槽。 （3）选择）选择与目标框架有紧密关系的槽，或者与目与目标框架有紧密关系的槽，或者与目 标框架的槽类似的槽。标框架的槽类似的槽。 2. 根据根据目标框架目标框架对对候选槽候选槽进行筛选进行筛选 59 7.5 类比学习7.5.1 类比推理类比推理7.5.2 属性类比学习属性类比学习7.5.3 转换类比学习转换类比学习607.5.3 转换类比学习转换类比学习 在状态空间表示法的知识表示中，在状态空间表示法的知识表示中， “状态状态”：描述：描述问题在不同时刻的状况；问题在不同时刻的状况；“算符算符”：描述改变状态的操：描述改变状态的操作。作。 当问题由初始状态变换到目标状态时，所用算符的序当问题由初始状态变换到目标状态时，所用算符的序列就构成了问题的一个解。列就构成了问题的一个解。 如何使问题由初始状态变换到目标状态呢？如何使问题由初始状态变换到目标状态呢？ “手段目标分析手段目标分析”法（法（means-end analysis，MEA），又称为，又称为“中间结局分析中间结局分析”法法：纽厄尔等人在：纽厄尔等人在通用问题求解程序通用问题求解程序GPS（general problem solver）中提）中提出的一种问题求解模型。出的一种问题求解模型。 617.5.3 转换类比学习转换类比学习 “手段目标分析手段目标分析”法（法（MEA）求解问题的基本过程求解问题的基本过程 ：（1）把问题的）把问题的当前状态当前状态与与目标状态目标状态进行比较，找出进行比较，找出差异差异。（2）根据差异找出一个）根据差异找出一个可减小差异的算符可减小差异的算符。（3）如果该算符可作用于）如果该算符可作用于当前状态当前状态，则，则用该算符把当前状态用该算符把当前状态改变为另一个更接近于目标状态的状态改变为另一个更接近于目标状态的状态；如果不能，则保留；如果不能，则保留当当前状态前状态，并生成一个子问题，再对此子问题应用，并生成一个子问题，再对此子问题应用MEA。（4）当子问题被求解后，恢复）当子问题被求解后，恢复保留的状态保留的状态，继续处理原问题。，继续处理原问题。627.5.3 转换类比学习转换类比学习 回忆过程回忆过程：找出新、旧问题间的：找出新、旧问题间的差别差别，包括：，包括：（1）初始状态的差别。）初始状态的差别。（2）目标状态的差别。）目标状态的差别。（3）路径约束的差别。）路径约束的差别。（4）求解方法可应用度的差别。）求解方法可应用度的差别。 转换过程转换过程：把：把旧问题的求解方法旧问题的求解方法经适当经适当变换变换使之成为使之成为求解新求解新问题的方法问题的方法，变换中用，变换中用MEA来减小来减小目标状态目标状态与与初始状态初始状态之间的之间的差异，使初始状态逐步过渡到目标状态，即求出问题的解。差异，使初始状态逐步过渡到目标状态，即求出问题的解。 转换类比学习：由外部环境获得与类比有关的信息，学习系转换类比学习：由外部环境获得与类比有关的信息，学习系统找出与新问题相似的旧问题的有关知识，把这些知识进行统找出与新问题相似的旧问题的有关知识，把这些知识进行转转换换使之适用于新问题，从而获得新的知识。使之适用于新问题，从而获得新的知识。63第7章 机器学习7.1 机器学习的基本概念机器学习的基本概念7.2 机械式学习机械式学习7.3 指导式学习指导式学习7.4 归纳学习归纳学习7.5 类比学习类比学习7.6 基于解释的学习基于解释的学习7.7 学习方法的比较与展望学习方法的比较与展望647.6 解释学习解释学习 解释学习（解释学习（explanation-based learning）：由美国：由美国Illinois大学的大学的Dejong于于1983年提出，属于分析学习，年提出，属于分析学习，本质为演绎学习方法。本质为演绎学习方法。 它是通过运用相关的领域知识，对当前提供的它是通过运用相关的领域知识，对当前提供的单单个实例个实例的问题求解进行分析，从而构造解释并产生相的问题求解进行分析，从而构造解释并产生相应知识的。应知识的。 解释学习系统：解释学习系统：米切尔（米切尔（Mitchell）等人研制的）等人研制的LEX和和LEAP系统系统，明顿（明顿（S. Minton）等人研制的）等人研制的PRODIGY系统系统等。等。 657.6 解释学习7.6.1 解释学习的概念解释学习的概念7.6.2 解释学习的学习过程解释学习的学习过程7.6.3 领域知识的完善性领域知识的完善性667.6.1 解释学习的概念解释学习的概念 解释学习：通过运用相关的解释学习：通过运用相关的领域知识领域知识及及一个训练实例一个训练实例来来对某一目标概念进行学习，并最终生成这个目标概念的对某一目标概念进行学习，并最终生成这个目标概念的一般性描述。一般性描述。 解释学习的一般性描述（米切尔（解释学习的一般性描述（米切尔（Mitchell）等，）等，1986）：）： 给定：给定：领域知识领域知识DT（用于证明训练实例为什么可作为目标概念（用于证明训练实例为什么可作为目标概念的实例）的实例） 目标概念目标概念TC（要学习的概念）（要学习的概念） 训练实例训练实例TE 操作性准则操作性准则OC （指导系统对描述目标的概念进行取舍）（指导系统对描述目标的概念进行取舍）找出：找出： 满足满足OC的关于的关于TC的充分条件。的充分条件。 677.6.1 解释学习的概念解释学习的概念 解释学习与示例学习的主要区别：解释学习与示例学习的主要区别：（1）示例学习：输入一组实例。）示例学习：输入一组实例。 解释学习：输入一个实例。解释学习：输入一个实例。（2）示例学习：归纳学习，不要求提供领域知识。）示例学习：归纳学习，不要求提供领域知识。 解释学习：演绎学习，要求提供完善的领域知识。解释学习：演绎学习，要求提供完善的领域知识。（3）示例学习：概念的获取，即知识增加的一面。）示例学习：概念的获取，即知识增加的一面。 解释学习：解释学习：技能提高的一面。技能提高的一面。687.6.2 解释学习的学习过程解释学习的学习过程 证明过程：通过运用领域知识进行演绎实现的，证明证明过程：通过运用领域知识进行演绎实现的，证明的结果是得到一个解释结构。的结果是得到一个解释结构。 1. 构造解释构造解释 解释学习的学习过程：首先运用领域知识找出训练实解释学习的学习过程：首先运用领域知识找出训练实例为什么是目标概念的证明，即解释，然后按操作性准例为什么是目标概念的证明，即解释，然后按操作性准则对解释进行推广，从而得出关于目标概念的学习描述。则对解释进行推广，从而得出关于目标概念的学习描述。 例如，学习目标：例如，学习目标：“一个物体一个物体x可以安全地放置在另一个物体可以安全地放置在另一个物体y的上面的上面”（堆叠问题）。（堆叠问题）。 目标概念：物体（目标概念：物体（x, y)，Safe-to-stack(x, y)697.6.2 解释学习的学习过程解释学习的学习过程 训练实例（描述物体训练实例（描述物体Obj1和和Obj2的事实）：的事实）：领域知识（安全放置准则和计算准则）：领域知识（安全放置准则和计算准则）： ),(21ObjObjStackToSafe12121211(,),(,),(,),(,),(,1)(,0.1).On Obj ObjLighter Obj ObjIsa Obj bookAIIsa ObjtablebookVolume ObjDensity Obj),()(yxStackToSafeyFragile),(),(yxStackToSafeyxLighter),(),(),(),