机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏
第11章分析学习机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

概述神经网络和决策树这样的学习方法需要一定数目的训练样例才能达到一定级别的泛化精度分析学习使用先验知识和演绎推理来扩大训练样例提供的信息，因此它不受同样的界限制约本章讨论一种称为基于解释的学习（EBL）的分析学习方法基于解释的学习中，先验知识用于分析观察到的学习样例是怎样满足目标概念的然后这个解释用于区分训练样例中哪些是相关的特征，哪些是不相关的样例就可基于逻辑推理进行泛化，而不是基于统计推理机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

简介前面章节讨论的各种归纳法，决策树、神经网络、归纳逻辑编程、遗传算法，在实践中的一个关键限制是：在可用数据不足时性能较差，正如第7章分析，给定数目的训练样例，学习的精度存在基本的上下界我们希望开发出这样的学习方法：它们训练精度上的基本限制不受可用训练数据的数量所制约基于解释的学习：使用先验知识来分析或解释每个训练样例，以推理出样例的哪些特征与目标函数相关，哪些不相关减小了待搜索假设空间的复杂度，减小了样本复杂度，提高了学习器的泛化精度机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

简介（2）一个例子：下国际象棋的学习任务前面的概念学习算法需要大量的训练样例人类只要少数训练样例，原因是人类非常依赖合法移动棋子的先验知识来解释或分析训练样例但是，人类学习中包含了一个很长的发现先验知识的过程本章内容安排给出一个特定的基于解释的学习算法，称为Prolog-EBG 考查Prolog-EBG的一般特性以及与前面讨论的归纳算法之间的关系描述了应用基于解释的学习以提高大状态空间搜索的性能本章假定生成解释所基于的先验知识是完全正确的，下一章讨论更一般的情况，即先验知识只是近似正确机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

归纳和分析学习问题分析和归纳学习问题的重要区别是，它们设想的学习问题的形式不同在归纳学习中，学习器被赋予一个假设空间H和训练数据D，它从H中选择一个输出假设，并且希望这个假设与D一致在分析学习中，学习器的输入除了假设空间H和训练数据D，还有一个领域理论B，由可用于解释训练样例的背景知识组成，学习器中H中选择一个输出假设，并希望这个假设既与D一致，也与B一致分析学习举例学习的目标概念：黑棋将在两步内失去王后的状态实例<xi, f(xi)>：xi描述一特定棋盘状态，当黑棋两步内失去王后，f(xi)值为真，否则为假假设空间：用Horn子句集表示，其中谓词表示棋子的位置领域理论：形式化的下棋规则机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

归纳和分析学习问题（2）在分析学习中，引入一致性约束：当领域理论B不涵蕴h的否定时，则称h与B一致一致性约束减少了当数据不能单独在H中决定h时，学习器面临的歧义性领域理论也由一组Horn子句描述，它使系统原则上可以加入任何学习到的假设至后续的领域理论中机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

例子，表11-1分析学习问题：SafeToStack(x,y)
已知实例空间X：每个实例描述一对物理对象，它们由谓词Color, Volume, Owner, Material, Type, Density描述，它们之间的关系用谓词On描述假设空间H：每个假设是一组Horn子句规则。每个Horn子句的头部为一个包含目标谓词SafeToStack的文字，每个Horn子句为文字的合取，这些文字基于描述实例的谓词以及谓词LessThan, Equal, GreaterThan和函数plus, minus和time，如下例SafeToStack(x,y)Volume(x,vx)Volume(y,vy)LessThan(vx,vy) 目标概念：谓词SafeToStack(x,y)，表示两个物理对象，一个可被安全地叠放在另一个上训练样例：下面显示了一个典型的正例SafeToStack(Obj1,Obj2)： On(Obj1,Obj2) Owner(Obj1,Fred) Type(Obj1,Box) Owner(Obj2,Louise) ... 领域理论B： SafeToStack(x,y)Fragile(y) SafeToStack(x,y)Lighter(x,y) 求解 H中一个与训练样例和领域理论一致的假设机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

用完美的领域理论学习：Prolog-EBG
本章考虑的基于解释的学习是在领域理论完美的情况下，即领域理论正确且完整当领域理论中每个断言都是客观的真实描述时，该领域理论被称为是正确的当领域理论覆盖了实例空间中所有正例时，该领域理论被称为是完整的每个满足目标概念的实例都可由领域理论证明其满足性根据Prolog惯例，不能证明的断言认定为假因此完整性定义包含全部正例和反例对于学习器的完美领域理论的假定的合理性的解释在某些情况下，有可能提供完美领域理论。比如下棋问题，棋子的合法走子提供了完美的领域理论在许多情况下，不能够假定有完美的领域理论，但我们可以使用基于不完美领域理论的近似合理的解释，它以完美理论为基础机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

Prolog-EBG算法 Prolog-EBG是一种基于解释的学习方法，是一种序列覆盖算法学习单个Horn子句规则，移去此规则覆盖的正例在剩余正例上重复这个过程，直到覆盖所有正例为止对于任意的正例集合，Prolog-EBG输出的假设包含一组对应于领域理论的目标概念的逻辑充分条件机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

表11-2基于解释的学习算法Prolog-EBG
Prolog-EBG(TargetConcept, TrainingExample, DomainTheroy) LearnedRules={} Pos=TrainingExamples中的正例对Pos中没有被LearnedRules覆盖的每个正例，做解释： Explanation=以DomainTheory表示的解释，说明正例满足TargetConcept 分析： SuffcientConditions=按照Explanation能够充分满足TargetConcept的正例的最一般特征集合改进： LearnedRules=LearnedRules+NewHornClause，其中NewHornClause的形式是：TargetConceptSufficientConditions 返回LearnedRules 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

Prolog-EBG的运行举例 Prolog-EBG对每个还没有被某个Horn子句覆盖的正例，通过下列步骤生成一新Horn子句解释新的正例分析该解释以确定一合适的泛化通过加入一新的Horn子句以覆盖该正例以及其他相似实例来改进当前假设机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

解释训练样例按照领域理论建立解释，说明该正例如何满足目标概念，当领域理论正确且完整时，此解释构成了训练样例满足目标概念的证明例子图11-2 一般情况下，可能有多种解释，这些解释中任意一个或所有的都可被使用，每个解释可对训练样例形成不同的泛化，所有解释都将被给定的领域理论论证在Prolog-EBG中，解释的生成使用了如Prolog中的反向链式搜索，找到第一个有效证明时终止机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

分析解释由学习器构造的解释回答了哪些特征与目标概念相关，哪些无关图11-2的例子通过收集解释的叶节点中提及的特征，可形成一个由领域理论论证的一般规则形成的规则构成了此训练样例的一个有意义的泛化，因为它去除了样例的许多与目标概念无关的属性通过更仔细地分析解释，能够得到更一般的规则 Prolog-EBG通过计算解释的最弱前像，能够得到由解释论证的最一般的规则机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

分析解释（2）定义：结论C对应于证明P的最弱前像为最一般的初始断言集合A，使得A按照P涵蕴C Prolog-EBG计算目标概念的关于解释的最弱前像的过程，使用的是回归过程回归过程的工作方式是在解释中反复后退首先对应于解释中最后证明步计算目标概念的最弱前像然后对应于其前一步计算结果表达式的最弱前像，依次类推这个过程在遍历过解释中所有步骤后终止，得到对应于解释的叶节点上的文字的目标概念的最弱前件图11-3 回归过程的核心是，每一步通过领域理论的一条Horn子句回归当前边缘表达式的算法机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

分析解释（3）回归算法的操作过程是，寻找一个置换使Horn子句的头与边缘中的相应文字合一，用规则体替换边缘中的表达式，再应用一个合一置换到整个边缘 Prolog-EBG输出的最终Horn子句形式如下：子句体被定义为上述过程计算出的最弱前件，子句头为目标概念本身应用置换到每一回归步中，以便子句头和子句体保持一致变量名机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

表11-3 通过一个Horn子句回归一组文字的算法
Regress(Frontier, Rule, Literal, hi) Frontier：通过规则被回归的文字集合 Rule：Horn子句 Literal：在Frontier中的文字，它由解释中的Rule推得 hi：是Rule的头与解释中的相应文字合一的置换返回构成Frontier的关于Rule的最弱前像的文字集合 headRule的头 bodyRule的体 hlhead与Literal的最一般合一，使得存在置换li满足：li(hl(head))=hi(head) 返回hl(Frontier-head+body) 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

表11-3 通过一个Horn子句回归一组文字的算法（示例）
Regress(Frontier, Rule, Literal, hi) Frontier={Volume(x,vx), Density(x,dx), Equal(wx,times(vx,dx), LessThan(wx,wy), Weight(y,wy)} Rule=Weight(z,5)Type(z,Endtable) Literal=Weight(y,wy) hi={z/Obj2} headWeight(z,5) bodyType(z,Endtable) hl={z/y, wy/5}, li={y/Obj2} 返回{Volume(x,vx), Density(x,dx), Equal(wx,times(vx,dx)), LessThan(wx,5), Type(y,Endtable)} 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

改进当前假设每一阶段的当前假设由当时学习到的Horn子句集组成，每一阶段，算法选取还未被当前Horn子句覆盖的新正例，解释该正例并按照上面的过程形成新规则新规则加入到当前假设中机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

对基于解释的学习的说明 Prolog-EBG算法的要点 Prolog-EBG不像归纳的方法，它运用先验知识分析单个样例以产生合理的一般假设对样例如何满足目标概念的解释，确定了样例的哪些属性是相关的，即在解释中提及的属性对解释的进一步分析，即回归目标概念以确定其对应解释的最弱前像，可推导出相关特征值的一般约束每个学习到的Horn子句对应于满足目标概念的一个充分条件，学习到的Horn子句集覆盖了学习器遇到的正例，以及其他与此共享同样解释的实例学习到的Horn子句的泛化将依赖于领域理论的形式以及训练样例被考虑的序列算法隐含假定了领域理论是正确且完整的，如果领域理论不正确或不完整，学到的概念也将不正确机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

对基于解释的学习的说明（2）基于解释的学习的特点作为理论引导的样例泛化使用给定的领域理论以从样例中合理泛化，区分出相关和不相关的样例属性，因此可以避免用于纯归纳推理中的样本复杂度界限作为样例引导的理论重建 Prolog-EBG算法被看作是一种重建领域理论到一种可操作形式的方式重建领域理论是通过创建这样的规则能从领域理论中演绎派生在一个推理步内分类观察到的训练样例学习到的规则可看作是领域理论的重组，它们能够在一个推理步内对目标概念的实例分类机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

对基于解释的学习的说明（3）仅仅重述学习器已经知道的学习器并没有学习新的知识，意义在于原则上已知的和实践上可有效计算的之间的区别很大，因此这种“知识重建”也是学习的重要形式学习到的规则直接从可观察到实例映射得到，方法是使其与基本领域理论一致使用原始的领域理论可能需要许多推理步和很乐观的搜索才能对任意实例分类学习到的规则可在一个推理步内分类观察到的实例基于解释的学习致力于重建领域理论，产生单步推理出样例分类的一般规则这种知识重建的过程有时被称为知识汇编，表示这种转换是为了增加知识使用的效率，而不改变知识的正确性和完备性机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

发现新特征 Prolog-EBG一个有趣的能力是形成在训练样例的描述中没有显示出现的新特征这些学习到的“新特征”类似于由神经网络的隐藏单元表示的特征类型不像神经网络中使用统计过程从多个训练样例中推导出隐藏单元特征，Prolog-EBG应用了一个分析过程基于单个训练样例的分析推导新特征领域理论中的最初项的特定合成和实例化导致了新特征的定义机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

演绎学习纯粹的Prolog-EBG是一个演绎的而不是归纳的学习过程，它输出一个假设满足下面的约束 (<xi,f(xi)>D)(hxi)f(xi) DBh 第一个约束只是简单地将机器学习的需求形式化，第二个约束描述了领域理论的作用：输出假设被进一步约束，使其符合领域理论和数据第二个约束减少了学习器在选择假设时面临的歧义性，因此领域理论减少了假设空间的规模并降低了学习的样本复杂度实质上，Prolog-EBG假定领域理论B涵蕴训练数据中实例的分类，即 (<xi,f(xi)>D)(Bxi)f(xi) 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

演绎学习（2） Prolog-EBG和ILP的比较 ILP中也使用到了背景知识B’，B’一般不满足式子11.3的约束 ILP是一个归纳学习系统，而Prolog-EBG是演绎学习系统 ILP使用背景知识来扩大待考虑的假设集合，而Prolog-EBG使用领域理论来减小可接受假设的集合 ILP要求： (<xi,f(xi)>D)(B’hxi)f(xi)，而Prolog-EBG要求更严格： (<xi,f(xi)>D)(hxi)f(xi) 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

基于解释的学习的归纳偏置根据第2章，一个学习算法的归纳偏置为一组断言，它们与训练样例一起演绎后续预测 Prolog-EBG的归纳偏置似乎是领域理论B，但由于领域理论可涵蕴多个可选的Horn子句集，因此归纳偏置还需包含在这些子句集中做出选择的内容由于每个单独的Horn子句是当前训练样例的解释所许可的最一般子句，因此归纳偏置为对极大一般化Horn子句的小集合的偏好实际上，Prolog-EBG的贪婪算法只是为寻找极大一般化Horn子句的真正最短集合所需的彻底搜索算法的一个启发式的近似近似的Prolog-EBG归纳偏置：领域理论B，加上对极大一般化Horn子句的小集合的偏好机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

基于解释的学习的归纳偏置（2） Prolog-EBG的归纳偏置在很大程度上由输入的领域理论决定，这与前面讨论的许多算法不同前面讨论的算法的归纳偏置是学习算法的一个固定属性，一般由其假设表示的语法所确定把归纳偏置作为一个输入参数而不是学习器的固定属性十分重要一个通用的学习方法至少会允许归纳偏置能够随待解决的学习问题变化，通过修改输入参数比通过限制假设的语法形式来实现偏置性要方便得多比如一个自治agent随着时间改进它的学习能力，那么最好有一个算法，它的泛化能力可在其获得更多的领域知识后增强机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

知识级的学习 Prolog-EBG算法中假设h可以直接从B中派生，与D无关可以设想有一个条目枚举器，它基于领域理论B中的断言简单地枚举能得到目标概念的所有证明树条目枚举器用与Prolog-EBG相似的方法计算最弱前像并构造一个Horn子句条目枚举器输出的是Prolog-EBG输出的子句的超集，存在下面的特点：训练样例的用途：使算法更关注覆盖实际出现的样例分布的生成规则，比尝试枚举棋盘的所有可能条目更可能得到更小、更相关的规则集 Prolog-EBG不会学习到一个超出隐含在领域理论中的知识的假设机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

知识级的学习（2） Prolog-EBG不会学习到一个超出隐含在领域理论中的知识的假设，但这不是分析学习或演绎学习的固有缺陷能够找到一个B不涵蕴h，但BD涵蕴h的例子，如 B=(x) IF ((PlayTennis=Yes)(Humidity=x)) THEN ((PlayTennis=Yes)(Humidityx)) D=Humidity=0.3 h=(PlayTennis=Yes)(Humidity0.3) 知识级学习被用来称这类型的学习：学到的假设涵蕴的预测不能被单独的领域理论涵蕴由断言集合Y涵蕴的所有预测的集合常称为Y的演绎闭包，知识级学习中B的演绎闭包是B+h演绎闭包的真子集机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

搜索控制知识的基于解释的学习（？？？）机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

小结纯粹的归纳学习方法寻找一个假设以拟合训练数据，而纯粹的分析学习方法搜寻一个假设拟合学习器的先验知识并覆盖训练样例基于解释的学习是分析学习的一种形式，其中学习器处理每个新训练样例的方法是：按照领域理论解释该样例中观察到的目标值分析此解释，确定解释成立的一般条件改进假设，合并这些一般条件 Prolog-EBG是基于解释的学习算法，它使用一阶Horn子句来表示其领域理论和学到的假设，在Prolog-EBG中，解释即是Prolog证明，而从解释中抽取的假设是此证明的最弱前像机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

小结（2） Prolog-EBG这样的分析学习方法建立游泳的中间特征，它是分析单独训练样例的一个副产品，这种生成特征的分析途径补充了如反向传播这样的归纳方法中基于统计方法的中间特征生成 Prolog-EBG不会产生能扩展其领域理论的演绎闭包的假设，但其他演绎学习过程具备这个能力可应用正确且完整的领域理论的一类重要问题是大的状态空间的搜索问题，如Prodigy和Soar这样的系统已显示了基于解释的学习方法的效用，它们自动获取有效的搜索规则以加速后续的问题求解纯粹的演绎推理的一个缺点是：它输出的假设的正确性只在领域理论正确时才能保证机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

补充读物 Fikes et al.1972，通过对Abstrips中的算子的分析学习宏算子 Soloway1977，在学习中使用明确的先验知识 Dejong1981, Mitchell1981, Winston et al.1983, Silver1983讨论了基于解释的学习 Ram & Leake1995，给出了关于目的和鲜艳知识在人类和记起学习中的作用的综述 Laird et al.1986提出的Soar系统和Carbonell et al.1990描述的Prodigy系统是使用基于解释的学习来学习问题求解的两个最成熟的系统机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

补充读物（2）对人类学习的实验性研究支持了这样一个猜想，即人类的学习是基于解释的 Ahn et al.1987和Qin et al.1992概述了支持人类应用基于解释的学习过程这一猜想的证据 Wisniewski & Medin1995描述了对人类学习的实验性研究，它建议在先验知识和观察数据之间进行丰富的相互作用以影响学习过程 Kotovsky & Baillargeon1994描述的实验说明，即使11个月大的婴儿在学习时也是基于其先验知识的 Van Harmelen & Bundy1988提供了基于解释的学习中执行的分析与Prolog程序中使用的几类优化方法的关系机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

Similar presentations

Presentation on theme: "机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

机器学习-分析学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏

Similar presentations

Presentation on theme: "机器学习-分析学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏"— Presentation transcript:

Similar presentations

About project

反馈

机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏

Presentation on theme: "机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏"— Presentation transcript: