机器学习.pptVIP

2003.12.18 机器学习-分析学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏 机器学习 第11章 分析学习 概述 神经网络和决策树这样的学习方法需要一定数目的训练样例才能达到一定级别的泛化精度 分析学习使用先验知识和演绎推理来扩大训练样例提供的信息，因此它不受同样的界限制约 本章讨论一种称为基于解释的学习（EBL）的分析学习方法 基于解释的学习中，先验知识用于分析观察到的学习样例是怎样满足目标概念的 然后这个解释用于区分训练样例中哪些是相关的特征，哪些是不相关的 样例就可基于逻辑推理进行泛化，而不是基于统计推理 简介 前面章节讨论的各种归纳法，决策树、神经网络、归纳逻辑编程、遗传算法，在实践中的一个关键限制是：在可用数据不足时性能较差，正如第7章分析，给定数目的训练样例，学习的精度存在基本的上下界 我们希望开发出这样的学习方法：它们训练精度上的基本限制不受可用训练数据的数量所制约 基于解释的学习： 使用先验知识来分析或解释每个训练样例，以推理出样例的哪些特征与目标函数相关，哪些不相关 减小了待有哪些信誉好的足球投注网站假设空间的复杂度，减小了样本复杂度，提高了学习器的泛化精度 简介（2） 一个例子：下国际象棋的学习任务 前面的概念学习算法需要大量的训练样例 人类只要少数训练样例，原因是人类非常依赖合法移动棋子的先验知识来解释或分析训练样例 但是，人类学习中包含了一个很长的发现先验知识的过程 本章内容安排 给出一个特定的基于解释的学习算法，称为Prolog-EBG 考查Prolog-EBG的一般特性以及与前面讨论的归纳算法之间的关系 描述了应用基于解释的学习以提高大状态空间有哪些信誉好的足球投注网站的性能 本章假定生成解释所基于的先验知识是完全正确的，下一章讨论更一般的情况，即先验知识只是近似正确 归纳和分析学习问题 分析和归纳学习问题的重要区别是，它们设想的学习问题的形式不同 在归纳学习中，学习器被赋予一个假设空间H和训练数据D，它从H中选择一个输出假设，并且希望这个假设与D一致 在分析学习中，学习器的输入除了假设空间H和训练数据D，还有一个领域理论B，由可用于解释训练样例的背景知识组成，学习器中H中选择一个输出假设，并希望这个假设既与D一致，也与B一致 分析学习举例 学习的目标概念：黑棋将在两步内失去王后的状态 实例xi, f(xi)：xi描述一特定棋盘状态，当黑棋两步内失去王后，f(xi)值为真，否则为假 假设空间：用Horn子句集表示，其中谓词表示棋子的位置 领域理论：形式化的下棋规则 归纳和分析学习问题（2） 在分析学习中，引入一致性约束：当领域理论B不涵蕴h的否定时，则称h与B一致 一致性约束减少了当数据不能单独在H中决定h时，学习器面临的歧义性 领域理论也由一组Horn子句描述，它使系统原则上可以加入任何学习到的假设至后续的领域理论中 例子，表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惯例，不能证明的断言认定为假 因此完整性定义包含全部正例和反例 对于学习器的完美领域理论的假定的合理性的解释 在某些情况下，有可能提供完美领域理论。比如下棋问题，棋子