2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 1
机器学习第 11章 分析学习
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
神经网络和决策树这样的学习方法需要一定数目的训练样例才能达到一定级别的泛化精度
分析学习使用先验知识和演绎推理来扩大训练样例提供的信息，因此它不受同样的界限制约
本章讨论一种称为基于解释的学习（ EBL）的分析学习方法
基于解释的学习中，先验知识用于分析观察到的学习样例是怎样满足目标概念的
然后这个解释用于区分训练样例中哪些是相关的特征，
哪些是不相关的
样例就可基于逻辑推理进行泛化，而不是基于统计推理
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介
前面章节讨论的各种归纳法，决策树、神经网络、归纳逻辑编程、遗传算法，在实践中的一个关键限制是：
在可用数据不足时性能较差，正如第 7章分析，给定数目的训练样例，学习的精度存在基本的上下界
我们希望开发出这样的学习方法：它们训练精度上的基本限制不受可用训练数据的数量所制约
基于解释的学习：
– 使用先验知识来分析或解释每个训练样例，以推理出样例的哪些特征与目标函数相关，哪些不相关
– 减小了待搜索假设空间的复杂度，减小了样本复杂度，提高了学习器的泛化精度
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
简介（ 2）
一个例子：下国际象棋的学习任务
– 前面的概念学习算法需要大量的训练样例
– 人类只要少数训练样例，原因是人类非常依赖合法移动棋子的先验知识来解释或分析训练样例
– 但是，人类学习中包含了一个很长的发现先验知识的过程
本章内容安排
– 给出一个特定的基于解释的学习算法，称为 Prolog-EBG
– 考查 Prolog-EBG的一般特性以及与前面讨论的归纳算法之间的关系
– 描述了应用基于解释的学习以提高大状态空间搜索的性能
本章假定生成解释所基于的先验知识是完全正确的，
下一章讨论更一般的情况，即先验知识只是近似正确
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
归纳和分析学习问题
分析和归纳学习问题的重要区别是，它们设想的学习问题的形式不同
– 在归纳学习中，学习器被赋予一个假设空间 H和训练数据 D，
它从 H中选择一个输出假设，并且希望这个假设与 D一致
– 在分析学习中，学习器的输入除了假设空间 H和训练数据 D，
还有一个领域理论 B，由可用于解释训练样例的背景知识组成，
学习器中 H中选择一个输出假设，并希望这个假设既与 D一致，
也与 B一致
分析学习举例
– 学习的目标概念：黑棋将在两步内失去王后的状态
– 实例 <xi,f(xi)>,xi描述一特定棋盘状态，当黑棋两步内失去王后,f(xi)值为真，否则为假
– 假设空间：用 Horn子句集表示，其中谓词表示棋子的位置
– 领域理论：形式化的下棋规则
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
归纳和分析学习问题（ 2）
在分析学习中，引入一致性约束：当领域理论 B不涵蕴 h的否定时，则称 h与 B一致
一致性约束减少了当数据不能单独在 H中决定 h时，学习器面临的歧义性
领域理论也由一组 Horn子句描述，它使系统原则上可以加入任何学习到的假设至后续的领域理论中
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中一个与训练样例和领域理论一致的假设
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
用完美的领域理论学习：
Prolog-EBG
本章考虑的基于解释的学习是在领域理论完美的情况下，即领域理论正确且完整
– 当领域理论中每个断言都是客观的真实描述时，该领域理论被称为是正确的
– 当领域理论覆盖了实例空间中所有正例时，该领域理论被称为是完整的
每个满足目标概念的实例都可由领域理论证明其满足性
根据 Prolog惯例，不能证明的断言认定为假
因此完整性定义包含全部正例和反例
对于学习器的完美领域理论的假定的合理性的解释
– 在某些情况下，有可能提供完美领域理论。比如下棋问题，棋子的合法走子提供了完美的领域理论
– 在许多情况下，不能够假定有完美的领域理论，但我们可以使用基于不完美领域理论的近似合理的解释，它以完美理论为基础
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
Prolog-EBG算法
Prolog-EBG是一种基于解释的学习方法，
是一种序列覆盖算法
– 学习单个 Horn子句规则，移去此规则覆盖的正例
– 在剩余正例上重复这个过程，直到覆盖所有正例为止
对于任意的正例集合,Prolog-EBG输出的假设包含一组对应于领域理论的目标概念的逻辑充分条件
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的形式是,TargetConcept?SufficientConditions
返回 LearnedRules
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
Prolog-EBG的运行举例
Prolog-EBG对每个还没有被某个 Horn子句覆盖的正例，通过下列步骤生成一新
Horn子句
– 解释新的正例
– 分析该解释以确定一合适的泛化
– 通过加入一新的 Horn子句以覆盖该正例以及其他相似实例来改进当前假设
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
解释训练样例
按照领域理论建立解释，说明该正例如何满足目标概念，当领域理论正确且完整时，此解释构成了训练样例满足目标概念的证明
例子图 11-2
一般情况下，可能有多种解释，这些解释中任意一个或所有的都可被使用，每个解释可对训练样例形成不同的泛化，所有解释都将被给定的领域理论论证
在 Prolog-EBG中，解释的生成使用了如 Prolog中的反向链式搜索，找到第一个有效证明时终止
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
分析解释
由学习器构造的解释回答了哪些特征与目标概念相关，
哪些无关
图 11-2的例子
通过收集解释的叶节点中提及的特征，可形成一个由领域理论论证的一般规则
形成的规则构成了此训练样例的一个有意义的泛化，
因为它去除了样例的许多与目标概念无关的属性
通过更仔细地分析解释，能够得到更一般的规则
Prolog-EBG通过计算解释的最弱前像，能够得到由解释论证的最一般的规则
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
分析解释（ 2）
定义：结论 C对应于证明 P的最弱前像为最一般的初始断言集合 A，使得 A按照 P涵蕴 C
Prolog-EBG计算目标概念的关于解释的最弱前像的过程，使用的是回归过程
回归过程的工作方式是在解释中反复后退
– 首先对应于解释中最后证明步计算目标概念的最弱前像
– 然后对应于其前一步计算结果表达式的最弱前像，依次类推
– 这个过程在遍历过解释中所有步骤后终止，得到对应于解释的叶节点上的文字的目标概念的最弱前件
图 11-3
回归过程的核心是，每一步通过领域理论的一条 Horn
子句回归当前边缘表达式的算法
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
分析解释（ 3）
回归算法的操作过程是，寻找一个置换使 Horn
子句的头与边缘中的相应文字合一，用规则体替换边缘中的表达式，再应用一个合一置换到整个边缘
Prolog-EBG输出的最终 Horn子句形式如下：子句体被定义为上述过程计算出的最弱前件，子句头为目标概念本身
应用置换到每一回归步中，以便子句头和子句体保持一致变量名
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
表 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)
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
表 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)}
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
改进当前假设
每一阶段的当前假设由当时学习到的
Horn子句集组成，每一阶段，算法选取还未被当前 Horn子句覆盖的新正例，解释该正例并按照上面的过程形成新规则
新规则加入到当前假设中
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
对基于解释的学习的说明
Prolog-EBG算法的要点
– Prolog-EBG不像归纳的方法，它运用先验知识分析单个样例以产生合理的一般假设
– 对样例如何满足目标概念的解释，确定了样例的哪些属性是相关的，即在解释中提及的属性
– 对解释的进一步分析，即回归目标概念以确定其对应解释的最弱前像，可推导出相关特征值的一般约束
– 每个学习到的 Horn子句对应于满足目标概念的一个充分条件，
学习到的 Horn子句集覆盖了学习器遇到的正例，以及其他与此共享同样解释的实例
– 学习到的 Horn子句的泛化将依赖于领域理论的形式以及训练样例被考虑的序列
– 算法隐含假定了领域理论是正确且完整的，如果领域理论不正确或不完整，学到的概念也将不正确
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
对基于解释的学习的说明（ 2）
基于解释的学习的特点
– 作为理论引导的样例泛化
使用给定的领域理论以从样例中合理泛化，区分出相关和不相关的样例属性，因此可以避免用于纯归纳推理中的样本复杂度界限
– 作为样例引导的理论重建
Prolog-EBG算法被看作是一种重建领域理论到一种可操作形式的方式
重建领域理论是通过创建这样的规则
– 能从领域理论中演绎派生
– 在一个推理步内分类观察到的训练样例
学习到的规则可看作是领域理论的重组，它们能够在一个推理步内对目标概念的实例分类
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
对基于解释的学习的说明（ 3）
– 仅仅重述学习器已经知道的
学习器并没有学习新的知识，意义在于
– 原则上已知的和实践上可有效计算的之间的区别很大，因此这种
“知识重建”也是学习的重要形式
学习到的规则直接从可观察到实例映射得到，方法是使其与基本领域理论一致
使用原始的领域理论可能需要许多推理步和很乐观的搜索才能对任意实例分类
学习到的规则可在一个推理步内分类观察到的实例
基于解释的学习致力于重建领域理论，产生单步推理出样例分类的一般规则
这种知识重建的过程有时被称为知识汇编，表示这种转换是为了增加知识使用的效率，而不改变知识的正确性和完备性
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
发现新特征
Prolog-EBG一个有趣的能力是形成在训练样例的描述中没有显示出现的新特征
这些学习到的“新特征”类似于由神经网络的隐藏单元表示的特征类型
不像神经网络中使用统计过程从多个训练样例中推导出隐藏单元特征,Prolog-EBG应用了一个分析过程基于单个训练样例的分析推导新特征
领域理论中的最初项的特定合成和实例化导致了新特征的定义
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
演绎学习
纯粹的 Prolog-EBG是一个演绎的而不是归纳的学习过程，它输出一个假设满足下面的约束
– (?<xi,f(xi)>?D)(h?xi)?f(xi)
– D?B?h
第一个约束只是简单地将机器学习的需求形式化，第二个约束描述了领域理论的作用：输出假设被进一步约束，使其符合领域理论和数据
第二个约束减少了学习器在选择假设时面临的歧义性，因此领域理论减少了假设空间的规模并降低了学习的样本复杂度
实质上,Prolog-EBG假定领域理论 B涵蕴训练数据中实例的分类，
即
(?<xi,f(xi)>?D)(B?xi)?f(xi)
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
演绎学习（ 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)
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
基于解释的学习的归纳偏置
根据第 2章，一个学习算法的归纳偏置为一组断言，它们与训练样例一起演绎后续预测
Prolog-EBG的归纳偏置
– 似乎是领域理论 B，但由于领域理论可涵蕴多个可选的 Horn子句集，因此归纳偏置还需包含在这些子句集中做出选择的内容
– 由于每个单独的 Horn子句是当前训练样例的解释所许可的最一般子句，因此归纳偏置为对极大一般化 Horn子句的小集合的偏好
– 实际上,Prolog-EBG的贪婪算法只是为寻找极大一般化 Horn
子句的真正最短集合所需的彻底搜索算法的一个启发式的近似
近似的 Prolog-EBG归纳偏置：领域理论 B，加上对极大一般化 Horn子句的小集合的偏好
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
基于解释的学习的归纳偏置（ 2）
Prolog-EBG的归纳偏置在很大程度上由输入的领域理论决定，这与前面讨论的许多算法不同
前面讨论的算法的归纳偏置是学习算法的一个固定属性，一般由其假设表示的语法所确定
把归纳偏置作为一个输入参数而不是学习器的固定属性十分重要
一个通用的学习方法至少会允许归纳偏置能够随待解决的学习问题变化，通过修改输入参数比通过限制假设的语法形式来实现偏置性要方便得多
比如一个自治 agent随着时间改进它的学习能力，那么最好有一个算法，它的泛化能力可在其获得更多的领域知识后增强
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
知识级的学习
Prolog-EBG算法中假设 h可以直接从 B中派生，与 D无关
– 可以设想有一个条目枚举器，它基于领域理论 B中的断言简单地枚举能得到目标概念的所有证明树
– 条目枚举器用与 Prolog-EBG相似的方法计算最弱前像并构造一个 Horn子句
条目枚举器输出的是 Prolog-EBG输出的子句的超集，
存在下面的特点：
– 训练样例的用途：使算法更关注覆盖实际出现的样例分布的生成规则，比尝试枚举棋盘的所有可能条目更可能得到更小、
更相关的规则集
– Prolog-EBG不会学习到一个超出隐含在领域理论中的知识的假设
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
知识级的学习（ 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演绎闭包的真子集
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
搜索控制知识的基于解释的学习（？？？）
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
小结
纯粹的归纳学习方法寻找一个假设以拟合训练数据，
而纯粹的分析学习方法搜寻一个假设拟合学习器的先验知识并覆盖训练样例
基于解释的学习是分析学习的一种形式，其中学习器处理每个新训练样例的方法是：
– 按照领域理论解释该样例中观察到的目标值
– 分析此解释，确定解释成立的一般条件
– 改进假设，合并这些一般条件
Prolog-EBG是基于解释的学习算法，它使用一阶 Horn
子句来表示其领域理论和学到的假设，在 Prolog-EBG
中，解释即是 Prolog证明，而从解释中抽取的假设是此证明的最弱前像
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
小结（ 2）
Prolog-EBG这样的分析学习方法建立游泳的中间特征，
它是分析单独训练样例的一个副产品，这种生成特征的分析途径补充了如反向传播这样的归纳方法中基于统计方法的中间特征生成
Prolog-EBG不会产生能扩展其领域理论的演绎闭包的假设，但其他演绎学习过程具备这个能力
可应用正确且完整的领域理论的一类重要问题是大的状态空间的搜索问题，如 Prodigy和 Soar这样的系统已显示了基于解释的学习方法的效用，它们自动获取有效的搜索规则以加速后续的问题求解
纯粹的演绎推理的一个缺点是：它输出的假设的正确性只在领域理论正确时才能保证
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
补充读物
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系统是使用基于解释的学习来学习问题求解的两个最成熟的系统
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
补充读物（ 2）
对人类学习的实验性研究支持了这样一个猜想，即人类的学习是基于解释的
– Ahn et al.1987和 Qin et al.1992概述了支持人类应用基于解释的学习过程这一猜想的证据
– Wisniewski & Medin1995描述了对人类学习 的实验性研究，它建议在先验知识和观察数据之间进行丰富的相互作用以影响学习过程
– Kotovsky & Baillargeon1994描述的实验说明，即使 11个月大的婴儿在学习时也是基于其先验知识的
Van Harmelen & Bundy1988提供了基于解释的学习中执行的分析与 Prolog程序中使用的几类优化方法的关系
机器学习第 11章 分析学习
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
神经网络和决策树这样的学习方法需要一定数目的训练样例才能达到一定级别的泛化精度
分析学习使用先验知识和演绎推理来扩大训练样例提供的信息，因此它不受同样的界限制约
本章讨论一种称为基于解释的学习（ EBL）的分析学习方法
基于解释的学习中，先验知识用于分析观察到的学习样例是怎样满足目标概念的
然后这个解释用于区分训练样例中哪些是相关的特征，
哪些是不相关的
样例就可基于逻辑推理进行泛化，而不是基于统计推理
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介
前面章节讨论的各种归纳法，决策树、神经网络、归纳逻辑编程、遗传算法，在实践中的一个关键限制是：
在可用数据不足时性能较差，正如第 7章分析，给定数目的训练样例，学习的精度存在基本的上下界
我们希望开发出这样的学习方法：它们训练精度上的基本限制不受可用训练数据的数量所制约
基于解释的学习：
– 使用先验知识来分析或解释每个训练样例，以推理出样例的哪些特征与目标函数相关，哪些不相关
– 减小了待搜索假设空间的复杂度，减小了样本复杂度，提高了学习器的泛化精度
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
简介（ 2）
一个例子：下国际象棋的学习任务
– 前面的概念学习算法需要大量的训练样例
– 人类只要少数训练样例，原因是人类非常依赖合法移动棋子的先验知识来解释或分析训练样例
– 但是，人类学习中包含了一个很长的发现先验知识的过程
本章内容安排
– 给出一个特定的基于解释的学习算法，称为 Prolog-EBG
– 考查 Prolog-EBG的一般特性以及与前面讨论的归纳算法之间的关系
– 描述了应用基于解释的学习以提高大状态空间搜索的性能
本章假定生成解释所基于的先验知识是完全正确的，
下一章讨论更一般的情况，即先验知识只是近似正确
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
归纳和分析学习问题
分析和归纳学习问题的重要区别是，它们设想的学习问题的形式不同
– 在归纳学习中，学习器被赋予一个假设空间 H和训练数据 D，
它从 H中选择一个输出假设，并且希望这个假设与 D一致
– 在分析学习中，学习器的输入除了假设空间 H和训练数据 D，
还有一个领域理论 B，由可用于解释训练样例的背景知识组成，
学习器中 H中选择一个输出假设，并希望这个假设既与 D一致，
也与 B一致
分析学习举例
– 学习的目标概念：黑棋将在两步内失去王后的状态
– 实例 <xi,f(xi)>,xi描述一特定棋盘状态，当黑棋两步内失去王后,f(xi)值为真，否则为假
– 假设空间：用 Horn子句集表示，其中谓词表示棋子的位置
– 领域理论：形式化的下棋规则
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
归纳和分析学习问题（ 2）
在分析学习中，引入一致性约束：当领域理论 B不涵蕴 h的否定时，则称 h与 B一致
一致性约束减少了当数据不能单独在 H中决定 h时，学习器面临的歧义性
领域理论也由一组 Horn子句描述，它使系统原则上可以加入任何学习到的假设至后续的领域理论中
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中一个与训练样例和领域理论一致的假设
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
用完美的领域理论学习：
Prolog-EBG
本章考虑的基于解释的学习是在领域理论完美的情况下，即领域理论正确且完整
– 当领域理论中每个断言都是客观的真实描述时，该领域理论被称为是正确的
– 当领域理论覆盖了实例空间中所有正例时，该领域理论被称为是完整的
每个满足目标概念的实例都可由领域理论证明其满足性
根据 Prolog惯例，不能证明的断言认定为假
因此完整性定义包含全部正例和反例
对于学习器的完美领域理论的假定的合理性的解释
– 在某些情况下，有可能提供完美领域理论。比如下棋问题，棋子的合法走子提供了完美的领域理论
– 在许多情况下，不能够假定有完美的领域理论，但我们可以使用基于不完美领域理论的近似合理的解释，它以完美理论为基础
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
Prolog-EBG算法
Prolog-EBG是一种基于解释的学习方法，
是一种序列覆盖算法
– 学习单个 Horn子句规则，移去此规则覆盖的正例
– 在剩余正例上重复这个过程，直到覆盖所有正例为止
对于任意的正例集合,Prolog-EBG输出的假设包含一组对应于领域理论的目标概念的逻辑充分条件
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的形式是,TargetConcept?SufficientConditions
返回 LearnedRules
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
Prolog-EBG的运行举例
Prolog-EBG对每个还没有被某个 Horn子句覆盖的正例，通过下列步骤生成一新
Horn子句
– 解释新的正例
– 分析该解释以确定一合适的泛化
– 通过加入一新的 Horn子句以覆盖该正例以及其他相似实例来改进当前假设
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
解释训练样例
按照领域理论建立解释，说明该正例如何满足目标概念，当领域理论正确且完整时，此解释构成了训练样例满足目标概念的证明
例子图 11-2
一般情况下，可能有多种解释，这些解释中任意一个或所有的都可被使用，每个解释可对训练样例形成不同的泛化，所有解释都将被给定的领域理论论证
在 Prolog-EBG中，解释的生成使用了如 Prolog中的反向链式搜索，找到第一个有效证明时终止
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
分析解释
由学习器构造的解释回答了哪些特征与目标概念相关，
哪些无关
图 11-2的例子
通过收集解释的叶节点中提及的特征，可形成一个由领域理论论证的一般规则
形成的规则构成了此训练样例的一个有意义的泛化，
因为它去除了样例的许多与目标概念无关的属性
通过更仔细地分析解释，能够得到更一般的规则
Prolog-EBG通过计算解释的最弱前像，能够得到由解释论证的最一般的规则
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
分析解释（ 2）
定义：结论 C对应于证明 P的最弱前像为最一般的初始断言集合 A，使得 A按照 P涵蕴 C
Prolog-EBG计算目标概念的关于解释的最弱前像的过程，使用的是回归过程
回归过程的工作方式是在解释中反复后退
– 首先对应于解释中最后证明步计算目标概念的最弱前像
– 然后对应于其前一步计算结果表达式的最弱前像，依次类推
– 这个过程在遍历过解释中所有步骤后终止，得到对应于解释的叶节点上的文字的目标概念的最弱前件
图 11-3
回归过程的核心是，每一步通过领域理论的一条 Horn
子句回归当前边缘表达式的算法
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
分析解释（ 3）
回归算法的操作过程是，寻找一个置换使 Horn
子句的头与边缘中的相应文字合一，用规则体替换边缘中的表达式，再应用一个合一置换到整个边缘
Prolog-EBG输出的最终 Horn子句形式如下：子句体被定义为上述过程计算出的最弱前件，子句头为目标概念本身
应用置换到每一回归步中，以便子句头和子句体保持一致变量名
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
表 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)
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
表 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)}
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
改进当前假设
每一阶段的当前假设由当时学习到的
Horn子句集组成，每一阶段，算法选取还未被当前 Horn子句覆盖的新正例，解释该正例并按照上面的过程形成新规则
新规则加入到当前假设中
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
对基于解释的学习的说明
Prolog-EBG算法的要点
– Prolog-EBG不像归纳的方法，它运用先验知识分析单个样例以产生合理的一般假设
– 对样例如何满足目标概念的解释，确定了样例的哪些属性是相关的，即在解释中提及的属性
– 对解释的进一步分析，即回归目标概念以确定其对应解释的最弱前像，可推导出相关特征值的一般约束
– 每个学习到的 Horn子句对应于满足目标概念的一个充分条件，
学习到的 Horn子句集覆盖了学习器遇到的正例，以及其他与此共享同样解释的实例
– 学习到的 Horn子句的泛化将依赖于领域理论的形式以及训练样例被考虑的序列
– 算法隐含假定了领域理论是正确且完整的，如果领域理论不正确或不完整，学到的概念也将不正确
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
对基于解释的学习的说明（ 2）
基于解释的学习的特点
– 作为理论引导的样例泛化
使用给定的领域理论以从样例中合理泛化，区分出相关和不相关的样例属性，因此可以避免用于纯归纳推理中的样本复杂度界限
– 作为样例引导的理论重建
Prolog-EBG算法被看作是一种重建领域理论到一种可操作形式的方式
重建领域理论是通过创建这样的规则
– 能从领域理论中演绎派生
– 在一个推理步内分类观察到的训练样例
学习到的规则可看作是领域理论的重组，它们能够在一个推理步内对目标概念的实例分类
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
对基于解释的学习的说明（ 3）
– 仅仅重述学习器已经知道的
学习器并没有学习新的知识，意义在于
– 原则上已知的和实践上可有效计算的之间的区别很大，因此这种
“知识重建”也是学习的重要形式
学习到的规则直接从可观察到实例映射得到，方法是使其与基本领域理论一致
使用原始的领域理论可能需要许多推理步和很乐观的搜索才能对任意实例分类
学习到的规则可在一个推理步内分类观察到的实例
基于解释的学习致力于重建领域理论，产生单步推理出样例分类的一般规则
这种知识重建的过程有时被称为知识汇编，表示这种转换是为了增加知识使用的效率，而不改变知识的正确性和完备性
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
发现新特征
Prolog-EBG一个有趣的能力是形成在训练样例的描述中没有显示出现的新特征
这些学习到的“新特征”类似于由神经网络的隐藏单元表示的特征类型
不像神经网络中使用统计过程从多个训练样例中推导出隐藏单元特征,Prolog-EBG应用了一个分析过程基于单个训练样例的分析推导新特征
领域理论中的最初项的特定合成和实例化导致了新特征的定义
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
演绎学习
纯粹的 Prolog-EBG是一个演绎的而不是归纳的学习过程，它输出一个假设满足下面的约束
– (?<xi,f(xi)>?D)(h?xi)?f(xi)
– D?B?h
第一个约束只是简单地将机器学习的需求形式化，第二个约束描述了领域理论的作用：输出假设被进一步约束，使其符合领域理论和数据
第二个约束减少了学习器在选择假设时面临的歧义性，因此领域理论减少了假设空间的规模并降低了学习的样本复杂度
实质上,Prolog-EBG假定领域理论 B涵蕴训练数据中实例的分类，
即
(?<xi,f(xi)>?D)(B?xi)?f(xi)
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
演绎学习（ 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)
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
基于解释的学习的归纳偏置
根据第 2章，一个学习算法的归纳偏置为一组断言，它们与训练样例一起演绎后续预测
Prolog-EBG的归纳偏置
– 似乎是领域理论 B，但由于领域理论可涵蕴多个可选的 Horn子句集，因此归纳偏置还需包含在这些子句集中做出选择的内容
– 由于每个单独的 Horn子句是当前训练样例的解释所许可的最一般子句，因此归纳偏置为对极大一般化 Horn子句的小集合的偏好
– 实际上,Prolog-EBG的贪婪算法只是为寻找极大一般化 Horn
子句的真正最短集合所需的彻底搜索算法的一个启发式的近似
近似的 Prolog-EBG归纳偏置：领域理论 B，加上对极大一般化 Horn子句的小集合的偏好
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
基于解释的学习的归纳偏置（ 2）
Prolog-EBG的归纳偏置在很大程度上由输入的领域理论决定，这与前面讨论的许多算法不同
前面讨论的算法的归纳偏置是学习算法的一个固定属性，一般由其假设表示的语法所确定
把归纳偏置作为一个输入参数而不是学习器的固定属性十分重要
一个通用的学习方法至少会允许归纳偏置能够随待解决的学习问题变化，通过修改输入参数比通过限制假设的语法形式来实现偏置性要方便得多
比如一个自治 agent随着时间改进它的学习能力，那么最好有一个算法，它的泛化能力可在其获得更多的领域知识后增强
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
知识级的学习
Prolog-EBG算法中假设 h可以直接从 B中派生，与 D无关
– 可以设想有一个条目枚举器，它基于领域理论 B中的断言简单地枚举能得到目标概念的所有证明树
– 条目枚举器用与 Prolog-EBG相似的方法计算最弱前像并构造一个 Horn子句
条目枚举器输出的是 Prolog-EBG输出的子句的超集，
存在下面的特点：
– 训练样例的用途：使算法更关注覆盖实际出现的样例分布的生成规则，比尝试枚举棋盘的所有可能条目更可能得到更小、
更相关的规则集
– Prolog-EBG不会学习到一个超出隐含在领域理论中的知识的假设
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
知识级的学习（ 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演绎闭包的真子集
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
搜索控制知识的基于解释的学习（？？？）
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
小结
纯粹的归纳学习方法寻找一个假设以拟合训练数据，
而纯粹的分析学习方法搜寻一个假设拟合学习器的先验知识并覆盖训练样例
基于解释的学习是分析学习的一种形式，其中学习器处理每个新训练样例的方法是：
– 按照领域理论解释该样例中观察到的目标值
– 分析此解释，确定解释成立的一般条件
– 改进假设，合并这些一般条件
Prolog-EBG是基于解释的学习算法，它使用一阶 Horn
子句来表示其领域理论和学到的假设，在 Prolog-EBG
中，解释即是 Prolog证明，而从解释中抽取的假设是此证明的最弱前像
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
小结（ 2）
Prolog-EBG这样的分析学习方法建立游泳的中间特征，
它是分析单独训练样例的一个副产品，这种生成特征的分析途径补充了如反向传播这样的归纳方法中基于统计方法的中间特征生成
Prolog-EBG不会产生能扩展其领域理论的演绎闭包的假设，但其他演绎学习过程具备这个能力
可应用正确且完整的领域理论的一类重要问题是大的状态空间的搜索问题，如 Prodigy和 Soar这样的系统已显示了基于解释的学习方法的效用，它们自动获取有效的搜索规则以加速后续的问题求解
纯粹的演绎推理的一个缺点是：它输出的假设的正确性只在领域理论正确时才能保证
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
补充读物
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系统是使用基于解释的学习来学习问题求解的两个最成熟的系统
2003.12.18 机器学习 -分析学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
补充读物（ 2）
对人类学习的实验性研究支持了这样一个猜想，即人类的学习是基于解释的
– Ahn et al.1987和 Qin et al.1992概述了支持人类应用基于解释的学习过程这一猜想的证据
– Wisniewski & Medin1995描述了对人类学习 的实验性研究，它建议在先验知识和观察数据之间进行丰富的相互作用以影响学习过程
– Kotovsky & Baillargeon1994描述的实验说明，即使 11个月大的婴儿在学习时也是基于其先验知识的
Van Harmelen & Bundy1988提供了基于解释的学习中执行的分析与 Prolog程序中使用的几类优化方法的关系
