机器学习第10章 学习规则集合2003.12.181机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏概述对学习到的假设，最具有表征力的和最能为人类所理解的表示方法之一是if-then规则的集合本章探索若干能学习这样的规则集合的算法其中，最重要的是学习包含变量的规则集合，或称一阶Horn子句集合由于一阶Horn子句集合可被解释为逻辑编程语言Prolog中的程序，学习的过程常被称为归纳逻辑编程本章考察了多种学习规则集合的途径，其中一种是基于机器定理证明器中演绎算子的逆转2003.12.182机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏简介在许多情况下，有必要学习一个由若干if-then规则共同定义的目标函数，比如决策树遗传算法本章我们讨论一组不同的算法，它们直接学习规则集合，与前面算法有两点关键的不同可学习包含变量的一阶规则集合（一阶子句的表达能力比命题规则要强得多）使用序列覆盖算法，一次学习一个规则，以递增的方式形成最终的规则集合2003.12.183机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏简介（2）一阶规则集合的例子if Parent(x,y) then Ancestor(x,y)if Parent(x,z) Ancestor(z,y) then Ancestor(x,y)这个规则集合很紧凑地描述了一个递归函数，它很难用决策树或其他命题的方法来表示Prolog程序就是一阶规则的集合，因此一个可以学习这种规则集合的通用算法，可被看作是从样例中自动推导出Prolog程序的算法一阶表示的学习系统在实践中的应用在质谱仪中学习哪一个化学药品能粘合碎片学习哪一个化学亚结构会产生诱导有机体突变的放射性物质学习有限单元网以分析物理结构中的应力2003.12.184机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏内容安排先介绍能够学习命题规则集的算法（命题规则可看作不含变量的一阶规则），算法搜寻假设空间学习析取规则集合将上面算法扩展到一阶规则讨论归纳逻辑的两种通用途径以及归纳和演绎推理的基本关系2003.12.185机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏序列覆盖算法序列覆盖算法学习一个规则，移去它覆盖的数据，再重复这一过程假定已有一个子程序Learn-One-Rule，它的输入是一组正例和反例，输出是单个规则，它能够覆盖许多正例而覆盖很少的反例我们要求输出的规则有较高的精确度，但不必有较高的覆盖度2003.12.186机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏序列覆盖算法（2）序列覆盖算法的过程在所有可用训练样例上执行Learn-One-Rule再移去由其学到的规则覆盖的正例重复上面的过程，直到规则集覆盖正例达到希望的程度序列覆盖算法按次序学习到一组规则，它们共同覆盖了全部正例规则集中的规则可排序，分类新实例时可先应用精度最高的规则2003.12.187机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏表10-1 学习析取规则集的序列覆盖算法（CN2）Sequential-Covering(Target_attribute, Attributes, Examples, Threshold)Learned_rulesRuleLearn-One-Rule(Target_attribute, Attributes, Examples)当Performance(Rule, Examples)ThresholdLearned_rulesLearned_rules+RuleExamplesExamples-被Rule正确分类的样例RuleLearn-One-Rule(Target_attribute, Attributes, Examples)Learned_rules按照在Examples上的Performance排序的Learned_rules返回Learned_rules2003.12.188机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏序列覆盖算法（3）序列覆盖算法将问题化简为一系列简单的问题，执行的是一种贪婪搜索，它不能保证找到能覆盖样例的最小或最佳规则集下面重点讨论Learn-One-Rule的设计，我们希望算法能够得到较高精度的规则集，但不必覆盖所有的正例2003.12.189机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏一般到特殊的柱状搜索一种方法是，将假设空间搜索过程设计为与ID3算法中相似的方式，但在每一步只沿着最有希望的分支进行，即产生最佳性能的属性-值对，而不是用增长子树的办法覆盖所选属性的所有可能值与ID3类似，可定义最佳分支，它覆盖的样例有最低的熵与其他贪婪算法一样，上面算法的缺陷是，它的每一步都可能做出次优的选择用柱状搜索来减小风险，即每一步保留k个最佳候选分支，每一步对k个候选分支进行处理，然后再将结果集削减至k个最可能成员2003.12.1810机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏表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_attribute)则Best_hypothesish更新Candidate_hypothesesCandidate_hypothesesCandidate_hypotheses中k个Performance最佳成员返回如下形式的一个规则“如果Best_hypothesis”，则prediction其中，prediction为在与Best_hypothesis匹配的Examples中最频繁的Target_attribute值2003.12.1811机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏表10-2 Learn-One-Rule的一种实现：一般到特殊柱状搜索（2）Performance(h, Examples, Target_attribute)h_examples与h匹配的Examples子集返回-Entropy(h_examples)，Entropy是关于Target_attribute的熵2003.12.1812机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏对表10-2的Learn-One-Rule算法的说明算法主循环中考虑的每个假设都是属性-值约束的合取每个合取假设对应于待学习规则的候选前件集合，它由其覆盖的样例的熵来评估搜索算法不断特化候选假设，直到得到一个极大特殊假设，它包含所有可用的属性规则的后件在算法的最后一步产生，在其前件确定后，算法构造出的规则后件用于预测在前件所能覆盖的样例中最常见的目标属性值尽管使用了柱状搜索，贪婪搜索仍可能产生次优的规则2003.12.1813机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏序列覆盖算法的几种变型只学习覆盖正例的规则，对该规则没有覆盖的实例默认地赋予其反例分类正例在整个群体中所占比例很小，所以规则集只标定正例的类别，而对其他样例默认分类为反例，这样规则集更简洁易懂这一方法对应于Prolog中的失败否定策略，其中不能证明为真的表达式都默认为假需要修改Learn-One-Rule算法增加输入变量，指定感兴趣的目标值Performance使用假设覆盖正例的比例2003.12.1814机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏序列覆盖算法的几种变型（2）AQ算法AQ明确地寻找覆盖特定目标值的规则，然后，对每个目标值学习一个析取规则集AQ算法学习单个规则的方法也不同于Learn-One-Rule，当它对每个规则执行一般到特殊柱状搜索时，他围绕单个正例来进行搜索中只考虑被某正例满足的属性，以得到逐渐特殊的假设，每次学一个新规则时，它从那些未覆盖的样例中也选择一个新的正例，以指引新析取项的搜索2003.12.1815机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏学习规则集：小结串行与并行的差异序列学习算法（CN2）每次学习一个规则，而ID3每一步并行学习整个析取项的集合，ID3可称为并行覆盖算法ID3在每一搜索步中根据它对数据产生的划分选择不同的属性，CN2选择的是不同的属性-值对为了学习到n个规则的集合，每个规则前件包含k个属性值测试，CN2需要nk次基本搜索步，而ID3独立选择次数要少得多CN2需要较大数量的训练数据2003.12.1816机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏学习规则集：小结（2）搜索方向的差异Learn-One-Rule的搜索方向是从一般到特殊，而其他算法是从特殊到一般从一般到特殊的一个优点是只有一个极大一般假设可作为搜索起始点而多数假设空间中有很多特殊假设，因此有许多极大特殊假设，从特殊到一般的算法难以确定搜索的起点2003.12.1817机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏学习规则集：小结（3）生成再测试与样例驱动搜索的差异样例驱动搜索算法包括：Find-S、候选消除、AQ算法、Gigol样例驱动算法中，对假设的生成或修正是由单独的训练样例驱动的，而且结果是一个已修正的假设，它对此单个样例的性能得到改善Learn-One-Rule是生成再测试搜索生成再测试搜索方法中，后续的假设的生成只基于假设表示的语法，然后基于这些假设在全部样例上的性能来进行选择生成再测试的一个优点是搜索中每一步的选择都基于在许多样例上的假设性能，因此噪声数据的影响被最小化2003.12.1818机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏学习规则集：小结（4）规则的后修剪和后修剪的方法Learn-One-Rule也有可能形成过度拟合，解决的方法也可以是后修剪性能函数的定义相对频率：令n代表规则所匹配的样例数目，nc代表其中它能正确分类的数目，则规则性能的相对频率估计为精度的m-估计：令p为从整个数据集中随机抽取的样例与该规则赋予的分类相同的先验概率，令m为权，或称对此先验概率p进行加权的等效样例数目熵：令S为匹配规则前件的样例集合，熵衡量的是该样例集合中目标函数的均一性2003.12.1819机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏学习一阶规则本节考虑带有变量的规则，即一阶Horn子句，它们比命题规则有强得多的表征能力一阶规则的归纳学习通常被称为归纳逻辑编程，因为这一过程可看作从样例中自动推导出Prolog程序命题规则过于特殊了，不能描述属性值之间的实质关系，对今后的分类几乎不起作用，一阶规则能够表示更一般的规则一阶Horn子句还可指定前件中的变量不出现在后件中的规则，这种变量可以被存在量词或全称量词修饰还可能在规则的后件和前件中使用相同的谓词描述递归的规则2003.12.1820机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏术语所有的一阶表达式由常量、变量、谓词符号以及函数符号组成谓词和函数的区别是谓词只能取真或假（特殊的函数），而函数的取值可为任意常量通常用小写符号表示函数，大写符号表示谓词术语：项：任意常量、任意变量、应用到任意项上的任意函数文字：应用到项上的任意谓词或其否定，如果包含否定符号，称为负文字，否则称为正文字，不包含任何变量的称为基本文字子句：多个文字的任意析取，其中所有的变量假定是全称量化的Horn子句：至多包含一个正文字的子句，Horn子句的前件被称为子句体或子句先行词，后件被称为子句头或子句推论置换：将文字L的某些变量替换为某些项的函数，记为L。如果置换使得L1=L2，那么称为L1和L2的合一置换2003.12.1821机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏学习一阶规则集：FOILFOIL学习的规则类似Horn子句，但有两个不同：比Horn子句更受限，因为文字不允许包含函数符号比Horn子句更有表征力，因为规则体中的文字可以是负文字2003.12.1822机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏表10-4 基本的FOIL算法FOIL(Target_predicate, Predicates, Examples)PosExamples中Target_predicate为True的成员NegExamples中Target_predicate为False的成员Learned_rules当Pos不空，学习NewRuleNewRule没有前件的谓词Target_predicate规则NewRuleNeg当NewRuleNeg不空，增加新文字以特化NewRuleCandidate_literature对NewRule生成候选新文字，基于PredicateBest_literal把Best_literal加入到NewRule的前件NewRuleNegNewRuleNeg中满足NewRule前件的子集Learned_rulesLearned_rules+NewRulePosPos-被NewRule覆盖的Pos成员返回Learned_rules2003.12.1823机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏FOIL算法的解释FOIL外层循环中每次加入一条新的规则到其析取式假设Learned_rules中去每个新规则的效果是通过加入一个析取项泛化当前的析取假设这是假设空间的特殊到一般的搜索过程，它开始于最特殊的空析取式，在假设足够一般以至覆盖所有正例时终止FOIL内层循环执行的是细粒度较高的搜索，以确定每个新规则的确切定义内层循环在另一假设空间中搜索，它包含文字的合取，以找到一个合取式形成规则的前件内层循环执行一般到特殊的爬山搜索，开始于最一般的前件，然后增加文字以使规则特化直到避开所有的反例2003.12.1824机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏FOIL算法的解释（2）FOIL与前面的序列覆盖和Learn-One-Rule算法之间有两个最实质的不同，来源于算法对一阶规则处理的需求在学习每个新规则的一般到特殊搜索中，FOIL使用了不同的细节步骤来生成规则的候选特化式，这一不同是为了处理规则前件中含有的变量FOIL使用的性能度量FOIL_Gain不同于表10-2中的熵度量，这是为了区别规则变量的不同约束，以及由于FOIL只搜寻覆盖正例的规则2003.12.1825机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏FOIL中的候选特化式的生成FOIL生成多个不同的新文字，每个可被单独地加到规则前件中更精确地，假定当前规则为：P(x1,.,xk)L1.LnFOIL生成该规则的候选特化式的方法是考虑符合下列形式的新文字Ln+1Q(v1,.,vr)，其中Q为在Predicates中出现的任意谓词名，vi既可为新变量，也可为规则中已有的变量，至少有一个是当前规则中已有的Equal(xj,xk)，其中xj和xk为规则中已有的变量以上两种文字的否定2003.12.1826机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏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.1827机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏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.1828机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏引导FOIL的搜索（选择文字）要在每一步中从候选文字中选择最有希望的文字，FOIL在训练数据上测量规则的性能在此过程中，考虑当前规则中每个变量的可能的约束FOIL使用评估函数以估计增加新文字的效用，它基于加入新文字前后的正例和反例的约束数目考虑某个规则R和一个可能被加到R的规则体的候选文字L，令R为加入文字L到规则R后生成的规则，则按照信息论理论，Foil_Gain(L,R)可看作，为了编码R的所有正例约束的分类所需的全部位数由于L带来的减少2003.12.1829机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏学习递归规则集如果在表10-4的算法输入参数Predicates中包含目标谓词（即规则头的谓词），那么FOIL在生成候选文字时必须考虑它，这允许产生递归的规则递归规则是否能被FOIL发现，取决于它在FOIL的贪婪搜索中是否比其他候选评分更高避免在学习规则集中产生无限递归2003.12.1830机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏FOIL小结FOIL扩展了CN2的序列覆盖算法，执行一般到特殊的搜索，每步增加一个新的文字到规则前件中，新文字可是规则前件或后件中已有的变量，或为新变量FOIL在每一步使用Foil_Gain函数在候选新文字中进行选择，如果新文字可指向目标谓词，那么FOIL可能学习到递归规则在训练数据无噪声的情况下，FOIL可持续地增加新文字到规则中，直到不覆盖任何反例为处理有噪声数据，搜索的终止需要在规则精度、覆盖度和复杂性之间做出折中FOIL使用最小描述长度的方法终止规则增长，新的文字只在它们的描述长度短于它们所解释的数据的描述长度时才被加入2003.12.1831机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏作为逆演绎的归纳归纳逻辑编程，基于一个简单的事实：归纳是演绎的逆过程一般来说，机器学习涉及的是如何建立能解释观察数据的理论，给定某些数据D和一些不完整的背景知识B，学习过程被描述为生成一个假设h，它与B一起解释了D，即基于背景知识扩展谓词集合的过程，称为建设性归纳可以利用演绎推理的逆过程，以使归纳泛化的过程自动化2003.12.1832机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏作为逆演绎的归纳（2）我们感兴趣的是设计一个逆涵蕴算子O(B,D)，它使用训练数据D和背景知识B作为输入，输出一个满足式子10.2的假设h满足式子10.2的假设很多，一般依赖最小描述长度准则来进行选择逆演绎的归纳方法有许多有吸引力的特点：包含了一种普遍的学习定义方法，即寻找某个一般概念，它与给定的训练样例相拟合通过引入背景知识，可以对一个假设何时可被称作“拟合”训练数据进行更充分的定义通过引入背景知识B，该公式要求学习算法使用这一背景信息来引导h的搜索，而不是只搜索语法上合法的假设空间2003.12.1833机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏作为逆演绎的归纳（3）不能处理有噪声的数据，不允许在观察到实例xi和其目标值f(xi)中出现差错的可能性，这样的差错可能产生对h的不一致约束，但是多数形式逻辑框架完全没有处理不一致断言的能力一阶逻辑语言的表征力太强，而且满足式子10.2的假设很多，以至于假设空间的搜索在一般情形下难以执行尽管直觉上背景知识有助于限制假设的搜索，但在多数ILP系统中，搜索的复杂度随着背景知识的增加而增高2003.12.1834机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏逆归纳自动演绎的一般方法是Robinson提出的归纳规则，归纳规则是一阶逻辑中一个合理且完备的演绎推理规则算法Gigol通过反转归纳规则来形成逆涵蕴算子命题归纳规则是归纳算子给定初始子句C1和C2，从子句C1中寻找一个文字L，并且L出现在C2中通过合并C1和C2中的除了L和L的所有文字，形成归纳式C，即C=(C1-L)(C2-L)给定两个子句，归纳算子首先确定文字L是否以正文字出现在一个子句中，以负文字出现在另一个子句中，然后使用上面的归纳规则，见图10-22003.12.1835机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏逆归纳（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)L2003.12.1836机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏逆归纳（3）可以基于逆归纳这样的逆涵蕴算子开发出规则学习算法来一种策略是使用序列覆盖算法，循环地以这种方法学习Horn子句集每次循环中，算法选择没有被以前学习到的子句覆盖的一个训练样例，然后应用归纳规则来生成满足(Bhixi)f(xi)的候选假设hi这是一个样例驱动的搜索，因为每个候选假设的建立是为了覆盖一特定样例如果存在多个候选假设，那么选择的策略是选取在其他样例上也有最高精度的假设Gigol程序使用了结合这种序列覆盖算法的逆归纳，通过它与用户交互，获得训练样例并引导它在可能的归纳推理步骤的巨大空间中的搜索，Gigol使用了一阶表示而不是命题表示2003.12.1837机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏一阶归纳归纳规则可以很容易地扩展到一阶表示，与命题归纳的关键不同是：这个过程基于合一置换操作定义置换为变量到项的任意映射，符号W表示应用置换到表达式W上的结果置换的例子L=Father(x,Bill)=x/Bob, y/zL=Father(Bob,Bill)合一置换：如果L1=L2，则为两个文字L1和L2的合一置换2003.12.1838机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏一阶归纳（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.32003.12.1839机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏一阶归纳（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.1840机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏一阶情况的逆归纳式子10.3中的合一置换可被为唯一地分解为1和2，即=12，1包含涉及C1中变量的所有置换，2包含涉及C2中变量的所有置换由于C1和C2是全称量化陈述，可以使用不同的变量名，因此上面的分解是合理的使用这种分解，式子10.3可重新表达为：C=(C1-L1)1(C2-L2)2使用归纳规则的定义L2=L112-1，解出C2为C2=(C-(C1-L11)2L112-12003.12.1841机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏一阶情况的逆归纳（2）式子10.4表示的逆涵蕴算子是非确定的，在应用过程中，一般可找到待归纳的子句C1和置换1和2的多种选择，每组不同的选择都产生一个不同的C22003.12.1842机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏一阶情况的逆归纳（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.1843机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏逆归纳小结逆归纳提供了一种一般的途径以自动产生满足式子10.2的假设与FOIL方法的差异逆归纳是样例驱动，FOIL是生成再测试逆归纳在每一步只考虑可用数据中的一小部分，FOIL考虑所有的可用数据看起来基于逆归纳的搜索更有针对性且更有效，但实际未必如此2003.12.1844机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏泛化、-包容于和涵蕴考虑如下的定义more_general_than：给定两布尔值函数hj(x)和hk(x)，称hjghk，当且仅当(x)hk(x)hj(x)（参见第2章）-包容于：考虑两个子句Cj和Ck，称Cj -包容于Ck，当且仅当存在一个置换，使得CjCk涵蕴：考虑两个子句Cj和Ck，子句Cj被称为涵蕴Ck，当且仅当Ck从Cj中演绎派生2003.12.1845机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏泛化、-包容于和涵蕴（2）三个定义之间的关系泛化和-包容于的关系：如果h1gh2，则子句C1:c(x)h1(x) -包容于子句C2:c(x)h2(x)-包容于是涵蕴的一种特殊形式，即如果子句A -包容于子句B，则AB，然而反之不一定成立因此，泛化是-包容于的一种特殊情况，而-包容于又是涵蕴的特殊情况通过泛化和特化假设来搜索假设空间比用一般的逆涵蕴算子来搜索更局限遗憾的是，逆涵蕴这种最一般的形式可产生无法处理的搜索中间的-包容于提供了位于泛化和涵蕴之间的一种概念和方法2003.12.1846机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏Progol在实践中，逆归纳容易导致候选假设的组合爆炸另一种途径（Progol的思想）是：只使用逆涵蕴来生成一个最特殊假设，它与背景信息一起涵蕴观察的数据然后，这个最特殊假设可用于确定假设空间的一般到特殊搜索边界，只考虑比此边界更一般的假设2003.12.1847机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏Prolog（2）Progol使用的算法概述用户指定使用一个受限的一阶表示语言为假设空间H，Progol使用序列覆盖法来从H中学习一组覆盖数据的表达式Progol在这个由最一般假设和第2步中得到的特殊边界hi所界定的假设空间中执行了一般到特殊搜索，在此假设集合中，它寻找有最小描述长度的假设2003.12.1848机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏小结序列覆盖算法学习析取的规则集，方法是先学习单个精确的规则，然后移去被此规则覆盖的正例，再在剩余样例上重复这一过程序列覆盖算法提供了一个学习规则集的有效的贪婪算法，可作为由顶向下的决策树学习算法的替代算法，决策树算法可被看作并行覆盖，与序列覆盖相对应在序列覆盖算法中，已研究了多种方法以学习单个规则，这些方法的不同在于它们考察规则前件空间的策略不同一阶规则集提供了一种表征能力很强的表示，学习一阶Horn子句的问题常被称为归纳逻辑编程的问题2003.12.1849机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏小结（2）学习一阶规则集的方法是将CN2中的序列覆盖算法由命题形式扩展到一阶表示，体现在FOIL程序中，它可学习包括简单递归规则集在内的一阶规则集学习一阶规则集的另一个方法是逆归纳，通过运用熟知的演绎推理的逆算子来搜索假设Cigol使用的逆归纳是归纳算子的逆转，而归纳是普遍用于机器定理证明的一种推理规则，Progol结合了逆涵蕴策略和一般到特殊策略来搜索假设空间2003.12.1850机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏补充读物Winston1970，学习如“arch”这样的概念的网络式描述Banerji1964,1969，将逻辑表示用于学习问题的研究Michalski，AQ算法Plotkin1970，-包容于的定义，对归纳和演绎之间的关系进行了形式化Vere1975，研究了学习的逻辑表示问题Buchanan1976，Meta-Dendral程序可学习分子结构中可在质谱仪中被分割的部分的关系描述Mitchell1979，候选消除变型空间算法被用于化学结构的关系描述2003.12.1851机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏补充读物（2）Horn子句的研究Shapiro1983，MISSammut & Banerji1986，MARVINQuinlan1990，FOILDzerosk1991，mFOILPazzani et al.1991，FOCLDe Raedt & Bruynooghe1993，CLAUDIENGrobelnik1992，MARKUSMuggleton & Buntine1988，逆涵蕴2003.12.1852机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏补充读物（3）归纳逻辑编程Lavrac & Dzeroski，一个可读性很强的教材Wrobel1996，一个好的综述Bratko & Muggleton1995，概述了ILP在一些重要问题上的应用2003.12.1853机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏