2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 1
机器学习第 10章 学习规则集合
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
对学习到的假设，最具有表征力的和最能为人类所理解的表示方法之一是 if-then规则的集合
本章探索若干能学习这样的规则集合的算法
其中，最重要的是学习包含变量的规则集合，
或称一阶 Horn子句集合
由于一阶 Horn子句集合可被解释为逻辑编程语言 Prolog中的程序，学习的过程常被称为归纳逻辑编程
本章考察了多种学习规则集合的途径，其中一种是基于机器定理证明器中演绎算子的逆转
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介
在许多情况下，有必要学习一个由若干 if-then
规则共同定义的目标函数，比如
– 决策树
– 遗传算法
本章我们讨论一组不同的算法，它们直接学习规则集合，与前面算法有两点关键的不同
– 可学习包含变量的一阶规则集合（一阶子句的表达能力比命题规则要强得多）
– 使用序列覆盖算法，一次学习一个规则，以递增的方式形成最终的规则集合
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
简介（ 2）
一阶规则集合的例子
if Parent(x,y) then Ancestor(x,y)
if Parent(x,z)? Ancestor(z,y) then Ancestor(x,y)
– 这个规则集合很紧凑地描述了一个递归函数，它很难用决策树或其他命题的方法来表示
Prolog程序就是一阶规则的集合，因此一个可以学习这种规则集合的通用算法，可被看作是从样例中自动推导出 Prolog程序的算法
一阶表示的学习系统在实践中的应用
– 在质谱仪中学习哪一个化学药品能粘合碎片
– 学习哪一个化学亚结构会产生诱导有机体突变的放射性物质
– 学习有限单元网以分析物理结构中的应力
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
内容安排
先介绍能够学习命题规则集的算法（命题规则可看作不含变量的一阶规则），
算法搜寻假设空间学习析取规则集合
将上面算法扩展到一阶规则
讨论归纳逻辑的两种通用途径以及归纳和演绎推理的基本关系
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
序列覆盖算法
序列覆盖算法
– 学习一个规则，移去它覆盖的数据，再重复这一过程
假定已有一个子程序 Learn-One-Rule，它的输入是一组正例和反例，输出是单个规则，它能够覆盖许多正例而覆盖很少的反例
我们要求输出的规则有较高的精确度，但不必有较高的覆盖度
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
序列覆盖算法（ 2）
序列覆盖算法的过程
– 在所有可用训练样例上执行 Learn-One-Rule
– 再移去由其学到的规则覆盖的正例
– 重复上面的过程，直到规则集覆盖正例达到希望的程度
序列覆盖算法按次序学习到一组规则，它们共同覆盖了全部正例
规则集中的规则可排序，分类新实例时可先应用精度最高的规则
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
表 10-1 学习析取规则集的序列覆盖算法（ CN2）
Sequential-Covering(Target_attribute,Attributes,Examples,
Threshold)
Learned_rules?{}
Rule?Learn-One-Rule(Target_attribute,Attributes,
Examples)
当 Performance(Rule,Examples)>Threshold
– Learned_rules?Learned_rules+Rule
– Examples?Examples-{被 Rule正确分类的样例 }
– Rule?Learn-One-Rule(Target_attribute,Attributes,Examples)
Learned_rules?按照在 Examples上的 Performance排序的
Learned_rules
返回 Learned_rules
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
序列覆盖算法（ 3）
序列覆盖算法将问题化简为一系列简单的问题，执行的是一种贪婪搜索，它不能保证找到能覆盖样例的最小或最佳规则集
下面重点讨论 Learn-One-Rule的设计，我们希望算法能够得到较高精度的规则集，
但不必覆盖所有的正例
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
一般到特殊的柱状搜索
一种方法是，将假设空间搜索过程设计为与 ID3算法中相似的方式，但在每一步只沿着最有希望的分支进行，
即产生最佳性能的属性 -值对，而不是用增长子树的办法覆盖所选属性的所有可能值
与 ID3类似，可定义最佳分支，它覆盖的样例有最低的熵
与其他贪婪算法一样，上面算法的缺陷是，它的每一步都可能做出次优的选择
用柱状搜索来减小风险，即每一步保留 k个最佳候选分支，每一步对 k个候选分支进行处理，然后再将结果集削减至 k个最可能成员
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
表 10-2 Learn-One-Rule的一种实现：一般到特殊柱状搜索
Learn-One-Rule(Target_attribute,Attributes,Examples,k)
初始化 Best_hypothesis为最一般的假设?
初始化 Candidate_hypotheses为集合 {Best_hypothesis}
当 Candidate_hypotheses不空，做以下操作
– 生成下一个更特殊的候选假设
All_constraints?所有形式为 (a=v)的约束集合，其中,a为 Attributes的成员,v为出现在当前 Examples集合中的 a的值
New_candidate_hypotheses?
– 对 Candidate_hypotheses中每个 h，循环
对 All_constraints中每个 c，循环通过加入约束 c创建一个 h的特化式
New_candidate_hypotheses中移去任意重复的、不一致的或非极大特殊化的假设
– 更新 Best_hypothesis
对 New_candidate_hypotheses中所有 h做以下操作
– 如果
Performance(h,Examples,Target_attribute)>Performance(Best_hypothesis,Examples,Target_attri
bute)
则 Best_hypothesis?h
– 更新 Candidate_hypotheses
Candidate_hypotheses?Candidate_hypotheses中 k个 Performance最佳成员
返回如下形式的一个规则
–,如果 Best_hypothesis”，则 prediction
– 其中,prediction为在与 Best_hypothesis匹配的 Examples中最频繁的
Target_attribute值
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
表 10-2 Learn-One-Rule的一种实现：一般到特殊柱状搜索
（ 2）
Performance(h,Examples,Target_attribute)
h_examples?与 h匹配的 Examples子集
返回 -Entropy(h_examples),Entropy是关于 Target_attribute的熵
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
对表 10-2的 Learn-One-Rule算法的说明
算法主循环中考虑的每个假设都是属性 -值约束的合取
每个合取假设对应于待学习规则的候选前件集合，它由其覆盖的样例的熵来评估
搜索算法不断特化候选假设，直到得到一个极大特殊假设，它包含所有可用的属性
规则的后件在算法的最后一步产生，在其前件确定后，
算法构造出的规则后件用于预测在前件所能覆盖的样例中最常见的目标属性值
尽管使用了柱状搜索，贪婪搜索仍可能产生次优的规则
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
序列覆盖算法的几种变型
只学习覆盖正例的规则，对该规则没有覆盖的实例默认地赋予其反例分类
– 正例在整个群体中所占比例很小，所以规则集只标定正例的类别，而对其他样例默认分类为反例，这样规则集更简洁易懂
– 这一方法对应于 Prolog中的失败否定策略，其中不能证明为真的表达式都默认为假
– 需要修改 Learn-One-Rule算法
增加输入变量，指定感兴趣的目标值
Performance使用假设覆盖正例的比例
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
序列覆盖算法的几种变型（ 2）
AQ算法
– AQ明确地寻找覆盖特定目标值的规则，然后，对每个目标值学习一个析取规则集
– AQ算法学习单个规则的方法也不同于 Learn-One-
Rule，当它对每个规则执行一般到特殊柱状搜索时，
他围绕单个正例来进行
– 搜索中只考虑被某正例满足的属性，以得到逐渐特殊的假设，每次学一个新规则时，它从那些未覆盖的样例中也选择一个新的正例，以指引新析取项的搜索
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
学习规则集：小结
串行与并行的差异
– 序列学习算法（ CN2）每次学习一个规则，而 ID3每一步并行学习整个析取项的集合,ID3可称为并行覆盖算法
– ID3在每一搜索步中根据它对数据产生的划分选择不同的属性,CN2选择的是不同的属性 -值对
– 为了学习到 n个规则的集合，每个规则前件包含 k个属性值测试,CN2需要 nk次基本搜索步，而 ID3独立选择次数要少得多
– CN2需要较大数量的训练数据
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
学习规则集：小结（ 2）
搜索方向的差异
– Learn-One-Rule的搜索方向是从一般到特殊，
而其他算法是从特殊到一般
– 从一般到特殊的一个优点是只有一个极大一般假设可作为搜索起始点
– 而多数假设空间中有很多特殊假设，因此有许多极大特殊假设，从特殊到一般的算法难以确定搜索的起点
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
学习规则集：小结（ 3）
生成再测试与样例驱动搜索的差异
– 样例驱动搜索算法包括,Find-S、候选消除,AQ算法,Gigol
– 样例驱动算法中，对假设的生成或修正是由单独的训练样例驱动的，而且结果是一个已修正的假设，它对此单个样例的性能得到改善
– Learn-One-Rule是生成再测试搜索
– 生成再测试搜索方法中，后续的假设的生成只基于假设表示的语法，然后基于这些假设在全部样例上的性能来进行选择
– 生成再测试的一个优点是搜索中每一步的选择都基于在许多样例上的假设性能，因此噪声数据的影响被最小化
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
学习规则集：小结（ 4）
规则的后修剪和后修剪的方法
– Learn-One-Rule也有可能形成过度拟合，解决的方法也可以是后修剪
性能函数的定义
– 相对频率：令 n代表规则所匹配的样例数目,nc代表其中它能正确分类的数目，则规则性能的相对频率估计为
– 精度的 m-估计：令 p为从整个数据集中随机抽取的样例与该规则赋予的分类相同的先验概率，令 m为权，或称对此先验概率
p进行加权的等效样例数目
– 熵：令 S为匹配规则前件的样例集合，熵衡量的是该样例集合中目标函数的均一性
nnc
mn mpnc
ci ii ppSE nt ropy 1 2log)(
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
学习一阶规则
本节考虑带有变量的规则，即一阶 Horn子句，它们比命题规则有强得多的表征能力
一阶规则的归纳学习通常被称为归纳逻辑编程，因为这一过程可看作从样例中自动推导出 Prolog程序
命题规则过于特殊了，不能描述属性值之间的实质关系，对今后的分类几乎不起作用，一阶规则能够表示更一般的规则
一阶 Horn子句还可指定前件中的变量不出现在后件中的规则，这种变量可以被存在量词或全称量词修饰
还可能在规则的后件和前件中使用相同的谓词描述递归的规则
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
术语
所有的一阶表达式由常量、变量、谓词符号以及函数符号组成
谓词和函数的区别是谓词只能取真或假（特殊的函数），而函数的取值可为任意常量
通常用小写符号表示函数，大写符号表示谓词
术语：
– 项：任意常量、任意变量、应用到任意项上的任意函数
– 文字：应用到项上的任意谓词或其否定，如果包含否定符号，称为负文字，否则称为正文字，不包含任何变量的称为基本文字
– 子句：多个文字的任意析取，其中所有的变量假定是全称量化的
– Horn子句：至多包含一个正文字的子句,Horn子句的前件被称为子句体或子句先行词，后件被称为子句头或子句推论
– 置换：将文字 L的某些变量替换为某些项的函数?，记为 L?。如果置换?使得 L1?=L2?，那么?称为 L1和 L2的合一置换
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
学习一阶规则集,FOIL
FOIL学习的规则类似 Horn子句，但有两个不同：
– 比 Horn子句更受限，因为文字不允许包含函数符号
– 比 Horn子句更有表征力，因为规则体中的文字可以是负文字
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
表 10-4 基本的 FOIL算法
FOIL(Target_predicate,Predicates,Examples)
Pos?Examples中 Target_predicate为 True的成员
Neg?Examples中 Target_predicate为 False的成员
Learned_rules?{}
当 Pos不空，学习 NewRule
– NewRule?没有前件的谓词 Target_predicate规则
– NewRule?Neg
– 当 NewRuleNeg不空，增加新文字以特化 NewRule
Candidate_literature?对 NewRule生成候选新文字，基于 Predicate
Best_literal?
把 Best_literal加入到 NewRule的前件
NewRuleNeg?NewRuleNeg中满足 NewRule前件的子集
– Learned_rules?Learned_rules+NewRule
– Pos?Pos-{被 NewRule覆盖的 Pos成员 }
返回 Learned_rules
),(_m a xa r g _ N e w R u leLGa inF o illite r a lsC a n d id a teL?
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
FOIL算法的解释
FOIL外层循环中每次加入一条新的规则到其析取式假设
Learned_rules中去
每个新规则的效果是通过加入一个析取项泛化当前的析取假设
这是假设空间的特殊到一般的搜索过程，它开始于最特殊的空析取式，在假设足够一般以至覆盖所有正例时终止
FOIL内层循环执行的是细粒度较高的搜索，以确定每个新规则的确切定义
内层循环在另一假设空间中搜索，它包含文字的合取，以找到一个合取式形成规则的前件
内层循环执行一般到特殊的爬山搜索，开始于最一般的前件，然后增加文字以使规则特化直到避开所有的反例
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
FOIL算法的解释（ 2）
FOIL与前面的序列覆盖和 Learn-One-Rule算法之间有两个最实质的不同，来源于算法对一阶规则处理的需求
– 在学习每个新规则的一般到特殊搜索中,FOIL使用了不同的细节步骤来生成规则的候选特化式，这一不同是为了处理规则前件中含有的变量
– FOIL使用的性能度量 FOIL_Gain不同于表 10-2中的熵度量，这是为了区别规则变量的不同约束，以及由于 FOIL只搜寻覆盖正例的规则
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
FOIL中的候选特化式的生成
FOIL生成多个不同的新文字，每个可被单独地加到规则前件中
更精确地，假定当前规则为：
P(x1,...,xk)?L1...Ln
FOIL生成该规则的候选特化式的方法是考虑符合下列形式的新文字 Ln+1
– Q(v1,...,vr)，其中 Q为在 Predicates中出现的任意谓词名,vi既可为新变量，也可为规则中已有的变量，至少有一个是当前规则中已有的
– Equal(xj,xk)，其中 xj和 xk为规则中已有的变量
– 以上两种文字的否定
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
FOIL中的候选特化式的生成
（ 2）
举例：待学习的规则的目标文字是 GrandDaughter(x,y)，即
GrandDaughter(x,y)?
– 生成下列候选文字
Equal(x,y)
Female(x)
Female(y)
Father(x,y)
Father(y,x)
Father(x,z)
Father(y,z)
Father(z,y)
上面文字的否定
– 假定 FOIL贪婪地选择了 Father(y,z)作为最有希望的文字，得到一个较特殊的规则
GrandDaughter(x,y)?Father(y,z)
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
FOIL中的候选特化式的生成
（ 3）
– 生成进一步特化该规则的候选文字
Female(z)
Equal(z,x)
Equal(x,z)
Father(z,w)
Father(w,z)
上面文字的否定
– 如果 FOIL选择了 Father(z,x)，然后又选择了 Female(y)，将得到下面的规则，它只覆盖正例，因此终止了进一步搜索该规则的特化式的过程
GrandDaughter(x,y)?Father(y,z)?Father(z,x)?Female(y)
– FOIL移去被该规则覆盖的所有样例，如果还有未覆盖的正例，
算法将开始搜索下一个规则
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
引导 FOIL的搜索（选择文字）
要在每一步中从候选文字中选择最有希望的文字，
FOIL在训练数据上测量规则的性能
在此过程中，考虑当前规则中每个变量的可能的约束
FOIL使用评估函数以估计增加新文字的效用，它基于加入新文字前后的正例和反例的约束数目
考虑某个规则 R和一个可能被加到 R的规则体的候选文字 L，令 R’为加入文字 L到规则 R后生成的规则，则
按照信息论理论,Foil_Gain(L,R)可看作，为了编码 R
的所有正例约束的分类所需的全部位数由于 L带来的减少
00 0211 12 lo glo g),(_ np pnp ptRLG a inF o il
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
学习递归规则集
如果在表 10-4的算法输入参数 Predicates
中包含目标谓词（即规则头的谓词），
那么 FOIL在生成候选文字时必须考虑它，
这允许产生递归的规则
递归规则是否能被 FOIL发现，取决于它在 FOIL的贪婪搜索中是否比其他候选评分更高
避免在学习规则集中产生无限递归
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
FOIL小结
FOIL扩展了 CN2的序列覆盖算法，执行一般到特殊的搜索，每步增加一个新的文字到规则前件中，新文字可是规则前件或后件中已有的变量，或为新变量
FOIL在每一步使用 Foil_Gain函数在候选新文字中进行选择，如果新文字可指向目标谓词，那么 FOIL可能学习到递归规则
在训练数据无噪声的情况下,FOIL可持续地增加新文字到规则中，
直到不覆盖任何反例
为处理有噪声数据，搜索的终止需要在规则精度、覆盖度和复杂性之间做出折中
FOIL使用最小描述长度的方法终止规则增长，新的文字只在它们的描述长度短于它们所解释的数据的描述长度时才被加入
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
作为逆演绎的归纳
归纳逻辑编程，基于一个简单的事实：归纳是演绎的逆过程
一般来说，机器学习涉及的是如何建立能解释观察数据的理论，给定某些数据 D和一些不完整的背景知识 B，
学习过程被描述为生成一个假设 h，它与 B一起解释了
D，即
基于背景知识扩展谓词集合的过程，称为建设性归纳
可以利用演绎推理的逆过程，以使归纳泛化的过程自动化
)()(,iiii xfxhBDxfx
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
作为逆演绎的归纳（ 2）
我们感兴趣的是设计一个逆涵蕴算子 O(B,D)，它使用训练数据 D和背景知识 B作为输入，输出一个满足式子
10.2的假设 h
满足式子 10.2的假设很多，一般依赖最小描述长度准则来进行选择
逆演绎的归纳方法有许多有吸引力的特点：
– 包含了一种普遍的学习定义方法，即寻找某个一般概念，它与给定的训练样例相拟合
– 通过引入背景知识，可以对一个假设何时可被称作“拟合”
训练数据进行更充分的定义
– 通过引入背景知识 B，该公式要求学习算法使用这一背景信息来引导 h的搜索，而不是只搜索语法上合法的假设空间
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
作为逆演绎的归纳（ 3）
– 不能处理有噪声的数据，不允许在观察到实例 xi和其目标值 f(xi)中出现差错的可能性，这样的差错可能产生对 h的不一致约束，但是多数形式逻辑框架完全没有处理不一致断言的能力
– 一阶逻辑语言的表征力太强，而且满足式子 10.2的假设很多，以至于假设空间的搜索在一般情形下难以执行
– 尽管直觉上背景知识有助于限制假设的搜索，但在多数 ILP系统中，搜索的复杂度随着背景知识的增加而增高
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
逆归纳
自动演绎的一般方法是 Robinson提出的归纳规则，归纳规则是一阶逻辑中一个合理且完备的演绎推理规则
算法 Gigol通过反转归纳规则来形成逆涵蕴算子
命题归纳规则是
归纳算子
– 给定初始子句 C1和 C2，从子句 C1中寻找一个文字 L，并且?L
出现在 C2中
– 通过合并 C1和 C2中的除了 L和?L的所有文字，形成归纳式 C，
即 C=(C1-{L})?(C2-{?L})
给定两个子句，归纳算子首先确定文字 L是否以正文字出现在一个子句中，以负文字出现在另一个子句中，
然后使用上面的归纳规则，见图 10-2
RP
RL
LP
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
逆归纳（ 2）
归纳算子根据初始子句 C1和 C2，得到归纳式 C，逆涵蕴算子 O(C,C1)根据 C和 C1得到另一个初始子句 C2
逆归纳是不确定的，即可能有多个子句 C2，使得 C1和
C2产生 C，在其中进行选择的一个启发式方法是偏好更短的子句，即假定 C2和 C1没有共同的文字
逆归纳算子
– 给定初始子句 C1和 C，寻找一个文字 L，它出现在子句 C1中但不出现在 C中
– 通过包含下列的文字，形成第二个子句 C2=(C-(C1-{L}))?{?L}
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 37
逆归纳（ 3）
可以基于逆归纳这样的逆涵蕴算子开发出规则学习算法来
– 一种策略是使用序列覆盖算法，循环地以这种方法学习 Horn子句集
– 每次循环中，算法选择没有被以前学习到的子句覆盖的一个训练样例 <xi,f(xi)>，然后应用归纳规则来生成满足 (B?hi?xi)?f(xi)的候选假设 hi
– 这是一个样例驱动的搜索，因为每个候选假设的建立是为了覆盖一特定样例
– 如果存在多个候选假设，那么选择的策略是选取在其他样例上也有最高精度的假设
Gigol程序使用了结合这种序列覆盖算法的逆归纳，通过它与用户交互，获得训练样例并引导它在可能的归纳推理步骤的巨大空间中的搜索，
Gigol使用了一阶表示而不是命题表示
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 38
一阶归纳
归纳规则可以很容易地扩展到一阶表示，与命题归纳的关键不同是：这个过程基于合一置换操作
定义置换为变量到项的任意映射，符号 W?表示应用置换?到表达式 W上的结果
置换的例子
– L=Father(x,Bill)
–?={x/Bob,y/z}
– L?=Father(Bob,Bill)
合一置换：如果 L1?=L2?，则?为两个文字 L1和 L2的合一置换
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 39
一阶归纳（ 2）
合一置换的意义在于可用来推广命题的归纳规则，在一阶归纳中，从子句 C1中寻找一文字 L1
和在 C2中寻找一文字 L2，使得存在 L1和?L2的合一置换，则归纳式计算方法如下
C=(C1-{L1})(C2-{L2})?
表 10-7一阶形式的归纳规则
– 寻找 C1中的文字 L1,C2中的文字 L2，以及置换?，
使得 L1?=?L2?
– 通过包含 C1?和 C2?中，除了 L1?和?L2?以外的文字，
形成归纳式 C，见式子 10.3
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 40
一阶归纳（ 3）
一阶形式的归纳的举例
– C1=White(x)?Swan(x),C2=Swan(Fred)
– 首先表示成子句形式 C1=White(x)Swan(x)
– 找到 C1中的文字 L1=Swan(x)和 C2中的文字
L2=Swan(Fred)，存在它们的合一置换
={x/Fred}
– 因此归纳结果 C=White(Fred)=White(Fred)
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 41
一阶情况的逆归纳
式子 10.3中的合一置换?可被为唯一地分解为?1
和?2，即?=?1?2,?1包含涉及 C1中变量的所有置换,?2包含涉及 C2中变量的所有置换
由于 C1和 C2是全称量化陈述，可以使用不同的变量名，因此上面的分解是合理的
使用这种分解，式子 10.3可重新表达为：
C=(C1-{L1})?1?(C2-{L2})?2
使用归纳规则的定义 L2=?L1?1?2-1，解出 C2为
C2=(C-(C1-{L1}?1)?2?{?L1?1?2-1}
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 42
一阶情况的逆归纳（ 2）
式子 10.4表示的逆涵蕴算子是非确定的，
在应用过程中，一般可找到待归纳的子句 C1和置换?1和?2的多种选择，每组不同的选择都产生一个不同的 C2
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 43
一阶情况的逆归纳（ 3）
图 10-3显示了此逆归纳规则应用在一个简单例子上的多个步骤
– 训练数据 D=GrandChild(Bob,Shannon)
– 背景知识 B={Father(Shanon,Tom),Father(Tom,Bob)}
– 学习目标谓词 GrandChild(y,x)的规则
第一步
– 设置结论 C为训练样例 GrandChild(Bob,Shannon)
– 从背景知识中选择子句 C1=Father(Shannon,Tom)
– 选择逆置换?1-1={},?2-1={Shannon/x}
– 得到 C2=GrandChild(Bob,x)Father(x,Tom)
第二步
– 设置结论为上步得到的 C=C2
– 从背景知识中选择 C1=Father(Tom,Bob)
– 得到 GrandChild(y,x)Father(x,z)Father(z,y)
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 44
逆归纳小结
逆归纳提供了一种一般的途径以自动产生满足式子 10.2的假设
与 FOIL方法的差异
– 逆归纳是样例驱动,FOIL是生成再测试
– 逆归纳在每一步只考虑可用数据中的一小部分,FOIL考虑所有的可用数据
– 看起来基于逆归纳的搜索更有针对性且更有效，但实际未必如此
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 45
泛化,?-包容于和涵蕴
考虑如下的定义
– more_general_than：给定两布尔值函数 hj(x)
和 hk(x)，称 hj?ghk，当且仅当
(?x)hk(x)?hj(x)（参见第 2章）
–?-包容于：考虑两个子句 Cj和 Ck，称 Cj?-包容于 Ck，当且仅当存在一个置换?，使得
CjCk
– 涵蕴：考虑两个子句 Cj和 Ck，子句 Cj被称为涵蕴 Ck，当且仅当 Ck从 Cj中演绎派生
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 46
泛化,?-包容于和涵蕴（ 2）
三个定义之间的关系
– 泛化和?-包容于的关系：如果 h1?gh2，则子句 C1:c(x)?h1(x)
-包容于子句 C2:c(x)?h2(x)
–?-包容于是涵蕴的一种特殊形式，即如果子句 A?-包容于子句
B，则 A?B，然而反之不一定成立
– 因此，泛化是?-包容于的一种特殊情况，而?-包容于又是涵蕴的特殊情况
通过泛化和特化假设来搜索假设空间比用一般的逆涵蕴算子来搜索更局限
遗憾的是，逆涵蕴这种最一般的形式可产生无法处理的搜索
中间的?-包容于提供了位于泛化和涵蕴之间的一种概念和方法
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 47
Progol
在实践中，逆归纳容易导致候选假设的组合爆炸
另一种途径（ Progol的思想）是：
– 只使用逆涵蕴来生成一个最特殊假设，它与背景信息一起涵蕴观察的数据
– 然后，这个最特殊假设可用于确定假设空间的一般到特殊搜索边界，只考虑比此边界更一般的假设
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 48
Prolog（ 2）
Progol使用的算法概述
– 用户指定使用一个受限的一阶表示语言为假设空间 H，
– Progol使用序列覆盖法来从 H中学习一组覆盖数据的表达式
– Progol在这个由最一般假设和第 2步中得到的特殊边界 hi所界定的假设空间中执行了一般到特殊搜索，在此假设集合中，它寻找有最小描述长度的假设
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 49
小结
序列覆盖算法学习析取的规则集，方法是先学习单个精确的规则，然后移去被此规则覆盖的正例，再在剩余样例上重复这一过程
序列覆盖算法提供了一个学习规则集的有效的贪婪算法，可作为由顶向下的决策树学习算法的替代算法，
决策树算法可被看作并行覆盖，与序列覆盖相对应
在序列覆盖算法中，已研究了多种方法以学习单个规则，这些方法的不同在于它们考察规则前件空间的策略不同
一阶规则集提供了一种表征能力很强的表示，学习一阶 Horn子句的问题常被称为归纳逻辑编程的问题
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 50
小结（ 2）
学习一阶规则集的方法是将 CN2中的序列覆盖算法由命题形式扩展到一阶表示，体现在 FOIL
程序中，它可学习包括简单递归规则集在内的一阶规则集
学习一阶规则集的另一个方法是逆归纳，通过运用熟知的演绎推理的逆算子来搜索假设
Cigol使用的逆归纳是归纳算子的逆转，而归纳是普遍用于机器定理证明的一种推理规则，
Progol结合了逆涵蕴策略和一般到特殊策略来搜索假设空间
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 51
补充读物
Winston1970，学习如,arch”这样的概念的网络式描述
Banerji1964,1969，将逻辑表示用于学习问题的研究
Michalski,AQ算法
Plotkin1970,?-包容于的定义，对归纳和演绎之间的关系进行了形式化
Vere1975，研究了学习的逻辑表示问题
Buchanan1976,Meta-Dendral程序可学习分子结构中可在质谱仪中被分割的部分的关系描述
Mitchell1979，候选消除变型空间算法被用于化学结构的关系描述
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 52
补充读物（ 2）
Horn子句的研究
– Shapiro1983,MIS
– Sammut & Banerji1986,MARVIN
– Quinlan1990,FOIL
– Dzerosk1991,mFOIL
– Pazzani et al.1991,FOCL
– De Raedt & Bruynooghe1993,CLAUDIEN
– Grobelnik1992,MARKUS
– Muggleton & Buntine1988，逆涵蕴
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 53
补充读物（ 3）
归纳逻辑编程
– Lavrac & Dzeroski，一个可读性很强的教材
– Wrobel1996，一个好的综述
– Bratko & Muggleton1995，概述了 ILP在一些重要问题上的应用
机器学习第 10章 学习规则集合
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
对学习到的假设，最具有表征力的和最能为人类所理解的表示方法之一是 if-then规则的集合
本章探索若干能学习这样的规则集合的算法
其中，最重要的是学习包含变量的规则集合，
或称一阶 Horn子句集合
由于一阶 Horn子句集合可被解释为逻辑编程语言 Prolog中的程序，学习的过程常被称为归纳逻辑编程
本章考察了多种学习规则集合的途径，其中一种是基于机器定理证明器中演绎算子的逆转
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介
在许多情况下，有必要学习一个由若干 if-then
规则共同定义的目标函数，比如
– 决策树
– 遗传算法
本章我们讨论一组不同的算法，它们直接学习规则集合，与前面算法有两点关键的不同
– 可学习包含变量的一阶规则集合（一阶子句的表达能力比命题规则要强得多）
– 使用序列覆盖算法，一次学习一个规则，以递增的方式形成最终的规则集合
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
简介（ 2）
一阶规则集合的例子
if Parent(x,y) then Ancestor(x,y)
if Parent(x,z)? Ancestor(z,y) then Ancestor(x,y)
– 这个规则集合很紧凑地描述了一个递归函数，它很难用决策树或其他命题的方法来表示
Prolog程序就是一阶规则的集合，因此一个可以学习这种规则集合的通用算法，可被看作是从样例中自动推导出 Prolog程序的算法
一阶表示的学习系统在实践中的应用
– 在质谱仪中学习哪一个化学药品能粘合碎片
– 学习哪一个化学亚结构会产生诱导有机体突变的放射性物质
– 学习有限单元网以分析物理结构中的应力
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
内容安排
先介绍能够学习命题规则集的算法（命题规则可看作不含变量的一阶规则），
算法搜寻假设空间学习析取规则集合
将上面算法扩展到一阶规则
讨论归纳逻辑的两种通用途径以及归纳和演绎推理的基本关系
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
序列覆盖算法
序列覆盖算法
– 学习一个规则，移去它覆盖的数据，再重复这一过程
假定已有一个子程序 Learn-One-Rule，它的输入是一组正例和反例，输出是单个规则，它能够覆盖许多正例而覆盖很少的反例
我们要求输出的规则有较高的精确度，但不必有较高的覆盖度
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
序列覆盖算法（ 2）
序列覆盖算法的过程
– 在所有可用训练样例上执行 Learn-One-Rule
– 再移去由其学到的规则覆盖的正例
– 重复上面的过程，直到规则集覆盖正例达到希望的程度
序列覆盖算法按次序学习到一组规则，它们共同覆盖了全部正例
规则集中的规则可排序，分类新实例时可先应用精度最高的规则
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
表 10-1 学习析取规则集的序列覆盖算法（ CN2）
Sequential-Covering(Target_attribute,Attributes,Examples,
Threshold)
Learned_rules?{}
Rule?Learn-One-Rule(Target_attribute,Attributes,
Examples)
当 Performance(Rule,Examples)>Threshold
– Learned_rules?Learned_rules+Rule
– Examples?Examples-{被 Rule正确分类的样例 }
– Rule?Learn-One-Rule(Target_attribute,Attributes,Examples)
Learned_rules?按照在 Examples上的 Performance排序的
Learned_rules
返回 Learned_rules
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
序列覆盖算法（ 3）
序列覆盖算法将问题化简为一系列简单的问题，执行的是一种贪婪搜索，它不能保证找到能覆盖样例的最小或最佳规则集
下面重点讨论 Learn-One-Rule的设计，我们希望算法能够得到较高精度的规则集，
但不必覆盖所有的正例
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
一般到特殊的柱状搜索
一种方法是，将假设空间搜索过程设计为与 ID3算法中相似的方式，但在每一步只沿着最有希望的分支进行，
即产生最佳性能的属性 -值对，而不是用增长子树的办法覆盖所选属性的所有可能值
与 ID3类似，可定义最佳分支，它覆盖的样例有最低的熵
与其他贪婪算法一样，上面算法的缺陷是，它的每一步都可能做出次优的选择
用柱状搜索来减小风险，即每一步保留 k个最佳候选分支，每一步对 k个候选分支进行处理，然后再将结果集削减至 k个最可能成员
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
表 10-2 Learn-One-Rule的一种实现：一般到特殊柱状搜索
Learn-One-Rule(Target_attribute,Attributes,Examples,k)
初始化 Best_hypothesis为最一般的假设?
初始化 Candidate_hypotheses为集合 {Best_hypothesis}
当 Candidate_hypotheses不空，做以下操作
– 生成下一个更特殊的候选假设
All_constraints?所有形式为 (a=v)的约束集合，其中,a为 Attributes的成员,v为出现在当前 Examples集合中的 a的值
New_candidate_hypotheses?
– 对 Candidate_hypotheses中每个 h，循环
对 All_constraints中每个 c，循环通过加入约束 c创建一个 h的特化式
New_candidate_hypotheses中移去任意重复的、不一致的或非极大特殊化的假设
– 更新 Best_hypothesis
对 New_candidate_hypotheses中所有 h做以下操作
– 如果
Performance(h,Examples,Target_attribute)>Performance(Best_hypothesis,Examples,Target_attri
bute)
则 Best_hypothesis?h
– 更新 Candidate_hypotheses
Candidate_hypotheses?Candidate_hypotheses中 k个 Performance最佳成员
返回如下形式的一个规则
–,如果 Best_hypothesis”，则 prediction
– 其中,prediction为在与 Best_hypothesis匹配的 Examples中最频繁的
Target_attribute值
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
表 10-2 Learn-One-Rule的一种实现：一般到特殊柱状搜索
（ 2）
Performance(h,Examples,Target_attribute)
h_examples?与 h匹配的 Examples子集
返回 -Entropy(h_examples),Entropy是关于 Target_attribute的熵
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
对表 10-2的 Learn-One-Rule算法的说明
算法主循环中考虑的每个假设都是属性 -值约束的合取
每个合取假设对应于待学习规则的候选前件集合，它由其覆盖的样例的熵来评估
搜索算法不断特化候选假设，直到得到一个极大特殊假设，它包含所有可用的属性
规则的后件在算法的最后一步产生，在其前件确定后，
算法构造出的规则后件用于预测在前件所能覆盖的样例中最常见的目标属性值
尽管使用了柱状搜索，贪婪搜索仍可能产生次优的规则
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
序列覆盖算法的几种变型
只学习覆盖正例的规则，对该规则没有覆盖的实例默认地赋予其反例分类
– 正例在整个群体中所占比例很小，所以规则集只标定正例的类别，而对其他样例默认分类为反例，这样规则集更简洁易懂
– 这一方法对应于 Prolog中的失败否定策略，其中不能证明为真的表达式都默认为假
– 需要修改 Learn-One-Rule算法
增加输入变量，指定感兴趣的目标值
Performance使用假设覆盖正例的比例
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
序列覆盖算法的几种变型（ 2）
AQ算法
– AQ明确地寻找覆盖特定目标值的规则，然后，对每个目标值学习一个析取规则集
– AQ算法学习单个规则的方法也不同于 Learn-One-
Rule，当它对每个规则执行一般到特殊柱状搜索时，
他围绕单个正例来进行
– 搜索中只考虑被某正例满足的属性，以得到逐渐特殊的假设，每次学一个新规则时，它从那些未覆盖的样例中也选择一个新的正例，以指引新析取项的搜索
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
学习规则集：小结
串行与并行的差异
– 序列学习算法（ CN2）每次学习一个规则，而 ID3每一步并行学习整个析取项的集合,ID3可称为并行覆盖算法
– ID3在每一搜索步中根据它对数据产生的划分选择不同的属性,CN2选择的是不同的属性 -值对
– 为了学习到 n个规则的集合，每个规则前件包含 k个属性值测试,CN2需要 nk次基本搜索步，而 ID3独立选择次数要少得多
– CN2需要较大数量的训练数据
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
学习规则集：小结（ 2）
搜索方向的差异
– Learn-One-Rule的搜索方向是从一般到特殊，
而其他算法是从特殊到一般
– 从一般到特殊的一个优点是只有一个极大一般假设可作为搜索起始点
– 而多数假设空间中有很多特殊假设，因此有许多极大特殊假设，从特殊到一般的算法难以确定搜索的起点
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
学习规则集：小结（ 3）
生成再测试与样例驱动搜索的差异
– 样例驱动搜索算法包括,Find-S、候选消除,AQ算法,Gigol
– 样例驱动算法中，对假设的生成或修正是由单独的训练样例驱动的，而且结果是一个已修正的假设，它对此单个样例的性能得到改善
– Learn-One-Rule是生成再测试搜索
– 生成再测试搜索方法中，后续的假设的生成只基于假设表示的语法，然后基于这些假设在全部样例上的性能来进行选择
– 生成再测试的一个优点是搜索中每一步的选择都基于在许多样例上的假设性能，因此噪声数据的影响被最小化
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
学习规则集：小结（ 4）
规则的后修剪和后修剪的方法
– Learn-One-Rule也有可能形成过度拟合，解决的方法也可以是后修剪
性能函数的定义
– 相对频率：令 n代表规则所匹配的样例数目,nc代表其中它能正确分类的数目，则规则性能的相对频率估计为
– 精度的 m-估计：令 p为从整个数据集中随机抽取的样例与该规则赋予的分类相同的先验概率，令 m为权，或称对此先验概率
p进行加权的等效样例数目
– 熵：令 S为匹配规则前件的样例集合，熵衡量的是该样例集合中目标函数的均一性
nnc
mn mpnc
ci ii ppSE nt ropy 1 2log)(
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
学习一阶规则
本节考虑带有变量的规则，即一阶 Horn子句，它们比命题规则有强得多的表征能力
一阶规则的归纳学习通常被称为归纳逻辑编程，因为这一过程可看作从样例中自动推导出 Prolog程序
命题规则过于特殊了，不能描述属性值之间的实质关系，对今后的分类几乎不起作用，一阶规则能够表示更一般的规则
一阶 Horn子句还可指定前件中的变量不出现在后件中的规则，这种变量可以被存在量词或全称量词修饰
还可能在规则的后件和前件中使用相同的谓词描述递归的规则
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
术语
所有的一阶表达式由常量、变量、谓词符号以及函数符号组成
谓词和函数的区别是谓词只能取真或假（特殊的函数），而函数的取值可为任意常量
通常用小写符号表示函数，大写符号表示谓词
术语：
– 项：任意常量、任意变量、应用到任意项上的任意函数
– 文字：应用到项上的任意谓词或其否定，如果包含否定符号，称为负文字，否则称为正文字，不包含任何变量的称为基本文字
– 子句：多个文字的任意析取，其中所有的变量假定是全称量化的
– Horn子句：至多包含一个正文字的子句,Horn子句的前件被称为子句体或子句先行词，后件被称为子句头或子句推论
– 置换：将文字 L的某些变量替换为某些项的函数?，记为 L?。如果置换?使得 L1?=L2?，那么?称为 L1和 L2的合一置换
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
学习一阶规则集,FOIL
FOIL学习的规则类似 Horn子句，但有两个不同：
– 比 Horn子句更受限，因为文字不允许包含函数符号
– 比 Horn子句更有表征力，因为规则体中的文字可以是负文字
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
表 10-4 基本的 FOIL算法
FOIL(Target_predicate,Predicates,Examples)
Pos?Examples中 Target_predicate为 True的成员
Neg?Examples中 Target_predicate为 False的成员
Learned_rules?{}
当 Pos不空，学习 NewRule
– NewRule?没有前件的谓词 Target_predicate规则
– NewRule?Neg
– 当 NewRuleNeg不空，增加新文字以特化 NewRule
Candidate_literature?对 NewRule生成候选新文字，基于 Predicate
Best_literal?
把 Best_literal加入到 NewRule的前件
NewRuleNeg?NewRuleNeg中满足 NewRule前件的子集
– Learned_rules?Learned_rules+NewRule
– Pos?Pos-{被 NewRule覆盖的 Pos成员 }
返回 Learned_rules
),(_m a xa r g _ N e w R u leLGa inF o illite r a lsC a n d id a teL?
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
FOIL算法的解释
FOIL外层循环中每次加入一条新的规则到其析取式假设
Learned_rules中去
每个新规则的效果是通过加入一个析取项泛化当前的析取假设
这是假设空间的特殊到一般的搜索过程，它开始于最特殊的空析取式，在假设足够一般以至覆盖所有正例时终止
FOIL内层循环执行的是细粒度较高的搜索，以确定每个新规则的确切定义
内层循环在另一假设空间中搜索，它包含文字的合取，以找到一个合取式形成规则的前件
内层循环执行一般到特殊的爬山搜索，开始于最一般的前件，然后增加文字以使规则特化直到避开所有的反例
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
FOIL算法的解释（ 2）
FOIL与前面的序列覆盖和 Learn-One-Rule算法之间有两个最实质的不同，来源于算法对一阶规则处理的需求
– 在学习每个新规则的一般到特殊搜索中,FOIL使用了不同的细节步骤来生成规则的候选特化式，这一不同是为了处理规则前件中含有的变量
– FOIL使用的性能度量 FOIL_Gain不同于表 10-2中的熵度量，这是为了区别规则变量的不同约束，以及由于 FOIL只搜寻覆盖正例的规则
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
FOIL中的候选特化式的生成
FOIL生成多个不同的新文字，每个可被单独地加到规则前件中
更精确地，假定当前规则为：
P(x1,...,xk)?L1...Ln
FOIL生成该规则的候选特化式的方法是考虑符合下列形式的新文字 Ln+1
– Q(v1,...,vr)，其中 Q为在 Predicates中出现的任意谓词名,vi既可为新变量，也可为规则中已有的变量，至少有一个是当前规则中已有的
– Equal(xj,xk)，其中 xj和 xk为规则中已有的变量
– 以上两种文字的否定
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
FOIL中的候选特化式的生成
（ 2）
举例：待学习的规则的目标文字是 GrandDaughter(x,y)，即
GrandDaughter(x,y)?
– 生成下列候选文字
Equal(x,y)
Female(x)
Female(y)
Father(x,y)
Father(y,x)
Father(x,z)
Father(y,z)
Father(z,y)
上面文字的否定
– 假定 FOIL贪婪地选择了 Father(y,z)作为最有希望的文字，得到一个较特殊的规则
GrandDaughter(x,y)?Father(y,z)
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
FOIL中的候选特化式的生成
（ 3）
– 生成进一步特化该规则的候选文字
Female(z)
Equal(z,x)
Equal(x,z)
Father(z,w)
Father(w,z)
上面文字的否定
– 如果 FOIL选择了 Father(z,x)，然后又选择了 Female(y)，将得到下面的规则，它只覆盖正例，因此终止了进一步搜索该规则的特化式的过程
GrandDaughter(x,y)?Father(y,z)?Father(z,x)?Female(y)
– FOIL移去被该规则覆盖的所有样例，如果还有未覆盖的正例，
算法将开始搜索下一个规则
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
引导 FOIL的搜索（选择文字）
要在每一步中从候选文字中选择最有希望的文字，
FOIL在训练数据上测量规则的性能
在此过程中，考虑当前规则中每个变量的可能的约束
FOIL使用评估函数以估计增加新文字的效用，它基于加入新文字前后的正例和反例的约束数目
考虑某个规则 R和一个可能被加到 R的规则体的候选文字 L，令 R’为加入文字 L到规则 R后生成的规则，则
按照信息论理论,Foil_Gain(L,R)可看作，为了编码 R
的所有正例约束的分类所需的全部位数由于 L带来的减少
00 0211 12 lo glo g),(_ np pnp ptRLG a inF o il
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
学习递归规则集
如果在表 10-4的算法输入参数 Predicates
中包含目标谓词（即规则头的谓词），
那么 FOIL在生成候选文字时必须考虑它，
这允许产生递归的规则
递归规则是否能被 FOIL发现，取决于它在 FOIL的贪婪搜索中是否比其他候选评分更高
避免在学习规则集中产生无限递归
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
FOIL小结
FOIL扩展了 CN2的序列覆盖算法，执行一般到特殊的搜索，每步增加一个新的文字到规则前件中，新文字可是规则前件或后件中已有的变量，或为新变量
FOIL在每一步使用 Foil_Gain函数在候选新文字中进行选择，如果新文字可指向目标谓词，那么 FOIL可能学习到递归规则
在训练数据无噪声的情况下,FOIL可持续地增加新文字到规则中，
直到不覆盖任何反例
为处理有噪声数据，搜索的终止需要在规则精度、覆盖度和复杂性之间做出折中
FOIL使用最小描述长度的方法终止规则增长，新的文字只在它们的描述长度短于它们所解释的数据的描述长度时才被加入
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
作为逆演绎的归纳
归纳逻辑编程，基于一个简单的事实：归纳是演绎的逆过程
一般来说，机器学习涉及的是如何建立能解释观察数据的理论，给定某些数据 D和一些不完整的背景知识 B，
学习过程被描述为生成一个假设 h，它与 B一起解释了
D，即
基于背景知识扩展谓词集合的过程，称为建设性归纳
可以利用演绎推理的逆过程，以使归纳泛化的过程自动化
)()(,iiii xfxhBDxfx
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
作为逆演绎的归纳（ 2）
我们感兴趣的是设计一个逆涵蕴算子 O(B,D)，它使用训练数据 D和背景知识 B作为输入，输出一个满足式子
10.2的假设 h
满足式子 10.2的假设很多，一般依赖最小描述长度准则来进行选择
逆演绎的归纳方法有许多有吸引力的特点：
– 包含了一种普遍的学习定义方法，即寻找某个一般概念，它与给定的训练样例相拟合
– 通过引入背景知识，可以对一个假设何时可被称作“拟合”
训练数据进行更充分的定义
– 通过引入背景知识 B，该公式要求学习算法使用这一背景信息来引导 h的搜索，而不是只搜索语法上合法的假设空间
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
作为逆演绎的归纳（ 3）
– 不能处理有噪声的数据，不允许在观察到实例 xi和其目标值 f(xi)中出现差错的可能性，这样的差错可能产生对 h的不一致约束，但是多数形式逻辑框架完全没有处理不一致断言的能力
– 一阶逻辑语言的表征力太强，而且满足式子 10.2的假设很多，以至于假设空间的搜索在一般情形下难以执行
– 尽管直觉上背景知识有助于限制假设的搜索，但在多数 ILP系统中，搜索的复杂度随着背景知识的增加而增高
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
逆归纳
自动演绎的一般方法是 Robinson提出的归纳规则，归纳规则是一阶逻辑中一个合理且完备的演绎推理规则
算法 Gigol通过反转归纳规则来形成逆涵蕴算子
命题归纳规则是
归纳算子
– 给定初始子句 C1和 C2，从子句 C1中寻找一个文字 L，并且?L
出现在 C2中
– 通过合并 C1和 C2中的除了 L和?L的所有文字，形成归纳式 C，
即 C=(C1-{L})?(C2-{?L})
给定两个子句，归纳算子首先确定文字 L是否以正文字出现在一个子句中，以负文字出现在另一个子句中，
然后使用上面的归纳规则，见图 10-2
RP
RL
LP
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
逆归纳（ 2）
归纳算子根据初始子句 C1和 C2，得到归纳式 C，逆涵蕴算子 O(C,C1)根据 C和 C1得到另一个初始子句 C2
逆归纳是不确定的，即可能有多个子句 C2，使得 C1和
C2产生 C，在其中进行选择的一个启发式方法是偏好更短的子句，即假定 C2和 C1没有共同的文字
逆归纳算子
– 给定初始子句 C1和 C，寻找一个文字 L，它出现在子句 C1中但不出现在 C中
– 通过包含下列的文字，形成第二个子句 C2=(C-(C1-{L}))?{?L}
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 37
逆归纳（ 3）
可以基于逆归纳这样的逆涵蕴算子开发出规则学习算法来
– 一种策略是使用序列覆盖算法，循环地以这种方法学习 Horn子句集
– 每次循环中，算法选择没有被以前学习到的子句覆盖的一个训练样例 <xi,f(xi)>，然后应用归纳规则来生成满足 (B?hi?xi)?f(xi)的候选假设 hi
– 这是一个样例驱动的搜索，因为每个候选假设的建立是为了覆盖一特定样例
– 如果存在多个候选假设，那么选择的策略是选取在其他样例上也有最高精度的假设
Gigol程序使用了结合这种序列覆盖算法的逆归纳，通过它与用户交互，获得训练样例并引导它在可能的归纳推理步骤的巨大空间中的搜索，
Gigol使用了一阶表示而不是命题表示
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 38
一阶归纳
归纳规则可以很容易地扩展到一阶表示，与命题归纳的关键不同是：这个过程基于合一置换操作
定义置换为变量到项的任意映射，符号 W?表示应用置换?到表达式 W上的结果
置换的例子
– L=Father(x,Bill)
–?={x/Bob,y/z}
– L?=Father(Bob,Bill)
合一置换：如果 L1?=L2?，则?为两个文字 L1和 L2的合一置换
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 39
一阶归纳（ 2）
合一置换的意义在于可用来推广命题的归纳规则，在一阶归纳中，从子句 C1中寻找一文字 L1
和在 C2中寻找一文字 L2，使得存在 L1和?L2的合一置换，则归纳式计算方法如下
C=(C1-{L1})(C2-{L2})?
表 10-7一阶形式的归纳规则
– 寻找 C1中的文字 L1,C2中的文字 L2，以及置换?，
使得 L1?=?L2?
– 通过包含 C1?和 C2?中，除了 L1?和?L2?以外的文字，
形成归纳式 C，见式子 10.3
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 40
一阶归纳（ 3）
一阶形式的归纳的举例
– C1=White(x)?Swan(x),C2=Swan(Fred)
– 首先表示成子句形式 C1=White(x)Swan(x)
– 找到 C1中的文字 L1=Swan(x)和 C2中的文字
L2=Swan(Fred)，存在它们的合一置换
={x/Fred}
– 因此归纳结果 C=White(Fred)=White(Fred)
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 41
一阶情况的逆归纳
式子 10.3中的合一置换?可被为唯一地分解为?1
和?2，即?=?1?2,?1包含涉及 C1中变量的所有置换,?2包含涉及 C2中变量的所有置换
由于 C1和 C2是全称量化陈述，可以使用不同的变量名，因此上面的分解是合理的
使用这种分解，式子 10.3可重新表达为：
C=(C1-{L1})?1?(C2-{L2})?2
使用归纳规则的定义 L2=?L1?1?2-1，解出 C2为
C2=(C-(C1-{L1}?1)?2?{?L1?1?2-1}
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 42
一阶情况的逆归纳（ 2）
式子 10.4表示的逆涵蕴算子是非确定的，
在应用过程中，一般可找到待归纳的子句 C1和置换?1和?2的多种选择，每组不同的选择都产生一个不同的 C2
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 43
一阶情况的逆归纳（ 3）
图 10-3显示了此逆归纳规则应用在一个简单例子上的多个步骤
– 训练数据 D=GrandChild(Bob,Shannon)
– 背景知识 B={Father(Shanon,Tom),Father(Tom,Bob)}
– 学习目标谓词 GrandChild(y,x)的规则
第一步
– 设置结论 C为训练样例 GrandChild(Bob,Shannon)
– 从背景知识中选择子句 C1=Father(Shannon,Tom)
– 选择逆置换?1-1={},?2-1={Shannon/x}
– 得到 C2=GrandChild(Bob,x)Father(x,Tom)
第二步
– 设置结论为上步得到的 C=C2
– 从背景知识中选择 C1=Father(Tom,Bob)
– 得到 GrandChild(y,x)Father(x,z)Father(z,y)
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 44
逆归纳小结
逆归纳提供了一种一般的途径以自动产生满足式子 10.2的假设
与 FOIL方法的差异
– 逆归纳是样例驱动,FOIL是生成再测试
– 逆归纳在每一步只考虑可用数据中的一小部分,FOIL考虑所有的可用数据
– 看起来基于逆归纳的搜索更有针对性且更有效，但实际未必如此
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 45
泛化,?-包容于和涵蕴
考虑如下的定义
– more_general_than：给定两布尔值函数 hj(x)
和 hk(x)，称 hj?ghk，当且仅当
(?x)hk(x)?hj(x)（参见第 2章）
–?-包容于：考虑两个子句 Cj和 Ck，称 Cj?-包容于 Ck，当且仅当存在一个置换?，使得
CjCk
– 涵蕴：考虑两个子句 Cj和 Ck，子句 Cj被称为涵蕴 Ck，当且仅当 Ck从 Cj中演绎派生
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 46
泛化,?-包容于和涵蕴（ 2）
三个定义之间的关系
– 泛化和?-包容于的关系：如果 h1?gh2，则子句 C1:c(x)?h1(x)
-包容于子句 C2:c(x)?h2(x)
–?-包容于是涵蕴的一种特殊形式，即如果子句 A?-包容于子句
B，则 A?B，然而反之不一定成立
– 因此，泛化是?-包容于的一种特殊情况，而?-包容于又是涵蕴的特殊情况
通过泛化和特化假设来搜索假设空间比用一般的逆涵蕴算子来搜索更局限
遗憾的是，逆涵蕴这种最一般的形式可产生无法处理的搜索
中间的?-包容于提供了位于泛化和涵蕴之间的一种概念和方法
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 47
Progol
在实践中，逆归纳容易导致候选假设的组合爆炸
另一种途径（ Progol的思想）是：
– 只使用逆涵蕴来生成一个最特殊假设，它与背景信息一起涵蕴观察的数据
– 然后，这个最特殊假设可用于确定假设空间的一般到特殊搜索边界，只考虑比此边界更一般的假设
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 48
Prolog（ 2）
Progol使用的算法概述
– 用户指定使用一个受限的一阶表示语言为假设空间 H，
– Progol使用序列覆盖法来从 H中学习一组覆盖数据的表达式
– Progol在这个由最一般假设和第 2步中得到的特殊边界 hi所界定的假设空间中执行了一般到特殊搜索，在此假设集合中，它寻找有最小描述长度的假设
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 49
小结
序列覆盖算法学习析取的规则集，方法是先学习单个精确的规则，然后移去被此规则覆盖的正例，再在剩余样例上重复这一过程
序列覆盖算法提供了一个学习规则集的有效的贪婪算法，可作为由顶向下的决策树学习算法的替代算法，
决策树算法可被看作并行覆盖，与序列覆盖相对应
在序列覆盖算法中，已研究了多种方法以学习单个规则，这些方法的不同在于它们考察规则前件空间的策略不同
一阶规则集提供了一种表征能力很强的表示，学习一阶 Horn子句的问题常被称为归纳逻辑编程的问题
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 50
小结（ 2）
学习一阶规则集的方法是将 CN2中的序列覆盖算法由命题形式扩展到一阶表示，体现在 FOIL
程序中，它可学习包括简单递归规则集在内的一阶规则集
学习一阶规则集的另一个方法是逆归纳，通过运用熟知的演绎推理的逆算子来搜索假设
Cigol使用的逆归纳是归纳算子的逆转，而归纳是普遍用于机器定理证明的一种推理规则，
Progol结合了逆涵蕴策略和一般到特殊策略来搜索假设空间
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 51
补充读物
Winston1970，学习如,arch”这样的概念的网络式描述
Banerji1964,1969，将逻辑表示用于学习问题的研究
Michalski,AQ算法
Plotkin1970,?-包容于的定义，对归纳和演绎之间的关系进行了形式化
Vere1975，研究了学习的逻辑表示问题
Buchanan1976,Meta-Dendral程序可学习分子结构中可在质谱仪中被分割的部分的关系描述
Mitchell1979，候选消除变型空间算法被用于化学结构的关系描述
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 52
补充读物（ 2）
Horn子句的研究
– Shapiro1983,MIS
– Sammut & Banerji1986,MARVIN
– Quinlan1990,FOIL
– Dzerosk1991,mFOIL
– Pazzani et al.1991,FOCL
– De Raedt & Bruynooghe1993,CLAUDIEN
– Grobelnik1992,MARKUS
– Muggleton & Buntine1988，逆涵蕴
2003.12.18 机器学习 -学习规则集合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 53
补充读物（ 3）
归纳逻辑编程
– Lavrac & Dzeroski，一个可读性很强的教材
– Wrobel1996，一个好的综述
– Bratko & Muggleton1995，概述了 ILP在一些重要问题上的应用
