机器学习 第11章分析学习 203.12.18机器学习-分析学习作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 1 机器学习 第11章 分析学习
概述 神经网络和决策树这样的学习方法需要一定数目的训 练样例才能达到一定级别的泛化精度 分析学习使用先验知识和演绎推理来扩大训练样例提 供的信息,因此它不受同样的界限制约 本章讨论一种称为基于解释的学习(EBL)的分析学 习方法 基于解释的学习中,先验知识用于分析观察到的学习 样例是怎样满足目标概念的 然后这个解释用于区分训练样例中哪些是相关的特征, 哪些是不相关的 样例就可基于逻辑推理进行泛化,而不是基于统计推 理 203.12.18机器学习-分析学习作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 2 概述 • 神经网络和决策树这样的学习方法需要一定数目的训 练样例才能达到一定级别的泛化精度 • 分析学习使用先验知识和演绎推理来扩大训练样例提 供的信息，因此它不受同样的界限制约 • 本章讨论一种称为基于解释的学习（EBL）的分析学 习方法 • 基于解释的学习中，先验知识用于分析观察到的学习 样例是怎样满足目标概念的 • 然后这个解释用于区分训练样例中哪些是相关的特征， 哪些是不相关的 • 样例就可基于逻辑推理进行泛化，而不是基于统计推 理
简介 前面章节讨论的各种归纳法,决策树、神经网络、归 纳逻辑编程、遗传算法,在实践中的一个关键限制是: 在可用数据不足时性能较差,正如第7章分析,给定数 目的训练样例,学习的精度存在基本的上下界 我们希望开发出这样的学习方法:它们训练精度上的 基本限制不受可用训练数据的数量所制约 基于解释的学习 使用先验知识来分析或解释每个训练样例,以推理出样例的 哪些特征与目标函数相关,哪些不相关 减小了待搜索假设空间的复杂度,减小了样本复杂度,提高 了学习器的泛化精度 203.12.18机器学习-分析学习作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 3 简介 • 前面章节讨论的各种归纳法，决策树、神经网络、归 纳逻辑编程、遗传算法，在实践中的一个关键限制是： 在可用数据不足时性能较差，正如第7章分析，给定数 目的训练样例，学习的精度存在基本的上下界 • 我们希望开发出这样的学习方法：它们训练精度上的 基本限制不受可用训练数据的数量所制约 • 基于解释的学习： – 使用先验知识来分析或解释每个训练样例，以推理出样例的 哪些特征与目标函数相关，哪些不相关 – 减小了待搜索假设空间的复杂度，减小了样本复杂度，提高 了学习器的泛化精度
简介(2) 个例子:下国际象棋的学习任务 前面的概念学习算法需要大量的训练样例 人类只要少数训练样例,原因是人类非常依赖合法移动棋子 的先验知识来解释或分析训练样例 但是,人类学习中包含了一个很长的发现先验知识的过程 本章内容安排 给出一个特定的基于解释的学习算法,称为 Prolog-EBG 考查 Prolog-EBG的一般特性以及与前面讨论的归纳算法之间 的关系 描述了应用基于解释的学习以提高大状态空间搜索的性能 本章假定生成解释所基于的先验知识是完全正确的, 下一章讨论更一般的情况,即先验知识只是近似正确 2003.12.18机器学习-分析学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 4 简介（2） • 一个例子：下国际象棋的学习任务 – 前面的概念学习算法需要大量的训练样例 – 人类只要少数训练样例，原因是人类非常依赖合法移动棋子 的先验知识来解释或分析训练样例 – 但是，人类学习中包含了一个很长的发现先验知识的过程 • 本章内容安排 – 给出一个特定的基于解释的学习算法，称为Prolog-EBG – 考查Prolog-EBG的一般特性以及与前面讨论的归纳算法之间 的关系 – 描述了应用基于解释的学习以提高大状态空间搜索的性能 • 本章假定生成解释所基于的先验知识是完全正确的， 下一章讨论更一般的情况，即先验知识只是近似正确
归纳和分析学习问题 分析和归纳学习问题的重要区别是,它们设想的学习 问题的形式不同 在归纳学习中,学习器被赋予一个假设空间H和训练数据D, 它从H中选择一个输出假设,并且希望这个假设与D一致 在分析学习中,学习器的输入除了假设空间H和训练数据D, 还有一个领域理论B,由可用于解释训练样例的背景知识组成, 学习器中H中选择一个输出假设,并希望这个假设既与D一致, 也与B一致 分析学习举例 学习的目标概念:黑棋将在两步内失去王后的状态 实例:x描述一特定棋盘状态,当黑棋两步内失去王 后,fx)值为真,否则为假 假设空间:用Homn子句集表示,其中谓词表示棋子的位置 203rz1领域颶諱习形神賴下娸趯眾者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 5 归纳和分析学习问题 • 分析和归纳学习问题的重要区别是，它们设想的学习 问题的形式不同 – 在归纳学习中，学习器被赋予一个假设空间H和训练数据D， 它从H中选择一个输出假设，并且希望这个假设与D一致 – 在分析学习中，学习器的输入除了假设空间H和训练数据D， 还有一个领域理论B，由可用于解释训练样例的背景知识组成， 学习器中H中选择一个输出假设，并希望这个假设既与D一致， 也与B一致 • 分析学习举例 – 学习的目标概念：黑棋将在两步内失去王后的状态 – 实例：xi描述一特定棋盘状态，当黑棋两步内失去王 后，f(xi )值为真，否则为假 – 假设空间：用Horn子句集表示，其中谓词表示棋子的位置 – 领域理论：形式化的下棋规则
归纳和分析学习问题(2) 在分析学习中,引入一致性约束:当领 域理论B不涵蕴h的否定时,则称h与B 致 一致性约束减少了当数据不能单独在H中 决定h时,学习器面临的歧义性 领域理论也由一组Homn子句描述,它使 系统原则上可以加入任何学习到的假设 至后续的领域理论中 203.12.18机器学习-分析学习作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 6 归纳和分析学习问题（2） • 在分析学习中，引入一致性约束：当领 域理论B不涵蕴h的否定时，则称h与B一 致 • 一致性约束减少了当数据不能单独在H中 决定h时，学习器面临的歧义性 • 领域理论也由一组Horn子句描述，它使 系统原则上可以加入任何学习到的假设 至后续的领域理论中
例子,表11-1分析学习问题: SafeTostack(x,y) 已知 实例空间X:每个实例描述一对物理对象,它们由谓词 Color, olume, Owner, Material, Type, Density描述,它们之间的关系用谓词On描述 假设空间H:每个假设是一组Homn子句规则。每个Homn子句的头部为一个包 含目标谓词 Safe ToStack的文字,每个Homn子句为文字的合取,这些文字基于 描述实例的谓词以及谓词 Less than, Equal, Greater Than和函数plus, minus和 time,如下例 SafeTo Stack(xy)< Volume(x,wx)∧ Volume(ywy) Less than(w 目标概念:谓词 Safe ToStack(x y),表示两个物理对象,一个可被安全地叠放 在另一个上 训练样例:下面显示了一个典型的正例 Safe To Stack(obj l,Ob2) On(Obj 1, obj2) Owner(Obj l, fred Type(Obj l, Box Owner(Obj2, Louise) 领域理论B: Safe ToStack(x, y)<- Fragilely Safe ToStack(x, y)<Lighter(x, y) 求解 H中一个与训练样例和领域理论一致的假设 203.12.18机器学习-分析学习作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 7 例子，表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中一个与训练样例和领域理论一致的假设
用完美的领域理论学习 Prolog-EBG 本章考虑的基于解释的学习是在领域理论完美的情况下,即领域 理论正确且完整 当领域理论中每个断言都是客观的真实描述时,该领域理论被称为 是正确的 当领域理论覆盖了实例空间中所有正例时,该领域理论被称为是完 整的 每个满足目标概念的实例都可由领域理论证明其满足性 根据 Prolog惯例,不能证明的断言认定为假 ·因此完整性定义包含全部正例和反例 对于学习器的完美领域理论的假定的合理性的解释 在某些情况下,有可能提供完美领域理论。比如下棋问题,棋子的 合法走子提供了完美的领域理论 在许多情况下,不能够假定有完美的领域理论,但我们可以使用基 于不完美领域理论的近似合理的解释,它以完美理论为基础 203.12.18机器学习-分析学习作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 8 用完美的领域理论学习： Prolog-EBG • 本章考虑的基于解释的学习是在领域理论完美的情况下，即领域 理论正确且完整 – 当领域理论中每个断言都是客观的真实描述时，该领域理论被称为 是正确的 – 当领域理论覆盖了实例空间中所有正例时，该领域理论被称为是完 整的 • 每个满足目标概念的实例都可由领域理论证明其满足性 • 根据Prolog惯例，不能证明的断言认定为假 • 因此完整性定义包含全部正例和反例 • 对于学习器的完美领域理论的假定的合理性的解释 – 在某些情况下，有可能提供完美领域理论。比如下棋问题，棋子的 合法走子提供了完美的领域理论 – 在许多情况下，不能够假定有完美的领域理论，但我们可以使用基 于不完美领域理论的近似合理的解释，它以完美理论为基础
Prolog-EBG算法 Prolog-EBG是一种基于解释的学习方法, 是一种序列覆盖算法 学习单个Homn子句规则,移去此规则覆盖的 正例 在剩余正例上重复这个过程,直到覆盖所有 正例为止 对于任意的正例集合, Prolog-EBG输出 的假设包含一组对应于领域理论的目标 概念的逻辑充分条件 2003.12.18机器学习-分析学习作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 9 Prolog-EBG算法 • Prolog-EBG是一种基于解释的学习方法， 是一种序列覆盖算法 – 学习单个Horn子句规则，移去此规则覆盖的 正例 – 在剩余正例上重复这个过程，直到覆盖所有 正例为止 • 对于任意的正例集合，Prolog-EBG输出 的假设包含一组对应于领域理论的目标 概念的逻辑充分条件
表11-2基于解释的学习算法 Prolog-EBG Prolog-EBGTargetConcept, Training Example, Domain Theroy) earnedrules- Pos= Training Example中的正例 ·对Pos中没有被 Learnedrules覆盖的每个正例,做 解释: Explanation=以 Domain Theory表示的解释,说明正例满足 TargetConcept 分析: · Suffcient conditions=按照 Explanation能够充分满足 TargetConcepti的正例的 最一般特征集合 改进: · LearnedRules= LearnedRules+ Newhorn clause,其中 NewHorn clause的形式 是: TargetConcept← SufficientConditions 返回 Learnedrules 203.12.18机器学习-分析学习作者: Mitchel译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-分析学习作者：Mitchell 译者：曾华军等讲者：陶晓鹏 10 表11-2基于解释的学习算法 Prolog-EBG Prolog-EBG(TargetConcept, TrainingExample, DomainTheroy) • LearnedRules={} • Pos=TrainingExamples中的正例 • 对Pos中没有被LearnedRules覆盖的每个正例，做 – 解释： • Explanation=以DomainTheory表示的解释，说明正例满足TargetConcept – 分析： • SuffcientConditions=按照Explanation能够充分满足TargetConcept的正例的 最一般特征集合 – 改进： • LearnedRules=LearnedRules+NewHornClause，其中NewHornClause的形式 是：TargetConceptSufficientConditions • 返回LearnedRules
