归纳和分析学习问题(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