机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

Slides:

Advertisements

Similar presentations

一、一阶线性微分方程及其解法二、一阶线性微分方程的简单应用三、小结及作业 §6.2 一阶线性微分方程.

Advertisements

第五节函数的微分一、微分的定义二、微分的几何意义三、基本初等函数的微分公式与微分运算法则四、微分形式不变性五、微分在近似计算中的应用六、小结.

2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.

2.5 函数的微分一、问题的提出二、微分的定义三、可微的条件四、微分的几何意义五、微分的求法六、小结.

全微分教学目的：全微分的有关概念和意义教学重点：全微分的计算和应用教学难点：全微分应用于近似计算.

圆的一般方程 (x-a)2 +(y-b)2=r2 x2+y2+Dx+Ey+F=0 Ax2+Bxy+Cy2+Dx+Ey+ F=0.

第五章二次型. 第五章二次型知识点1---二次型及其矩阵表示二次型的基本概念 1. 线性变换与合同矩阵 2.

中国科学院研究生院 2006年6月27日机器学习研究第五讲：关系学习韩彦军中国科学院自动化研究所.

《高等数学》（理学）常数项级数的概念袁安锋

1.1.3四种命题的相互关系高二数学选修2-1 第一章常用逻辑用语.

常用逻辑用语复习课李娟.

Oracle数据库 Oracle 子程序.

一、原函数与不定积分二、不定积分的几何意义三、基本积分公式及积分法则四、牛顿—莱布尼兹公式五、小结

第5章定积分及其应用基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法

第三节格林公式及其应用（2）一、曲线积分与路径无关的定义二、曲线积分与路径无关的条件三、二元函数的全微分的求积四、小结.

§5 微分及其应用一、微分的概念实例:正方形金属薄片受热后面积的改变量..

2-7、函数的微分教学要求教学要点.

§5 微分及其应用一、微分的概念实例:正方形金属薄片受热后面积的改变量..

探索三角形相似的条件(2).

在PHP和MYSQL中实现完美的中文显示

Hadoop I/O By ShiChaojie.

走进编程程序的顺序结构（二）.

辅导课程六.

网络常用常用命令课件制作人：谢希仁.

第一单元初识C程序与C程序开发平台搭建 ---观其大略

§2 求导法则 2.1 求导数的四则运算法则下面分三部分加以证明, 并同时给出相应的推论和例题 .

Online job scheduling in Distributed Machine Learning Clusters

第一章　函数函数 — 研究对象—第一章分析基础极限 — 研究方法—第二章连续 — 研究桥梁—第二章.

What have we learned?.

使用矩阵表示最小生成树算法.

宁波市高校慕课联盟课程与进行交互 Linux 系统管理.

λ演算与函数式设计语言有以下函数： Y = λg.((λf.g(f f)) (λf .g(f f)))

SOA – Experiment 2: Query Classification Web Service

第4章非线性规划 4.5 约束最优化方法 2019/4/6 山东大学软件学院.

第一章函数与极限.

简单介绍用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)

§4 谓词演算的性质谓词逻辑Pred(Y)。是Y上的关于类型 {F,→,x|xX}的自由代数赋值形式证明

模型分类问题 Presented by 刘婷婷苏琬琳.

线性代数厦门大学线性代数教学组 2019年4月24日6时8分 / 45.

WPT MRC. WPT MRC 由题目引出的几个问题 1.做MRC-WPT的多了，与其他文章的区别是什么？ 2.Charging Control的手段是什么？ 3.Power Reigon是什么东西？

用计算器开方.

Lightweight Data-flow Analysis for Execution-driven Constraint Solving

实体描述呈现方法的研究实验评估 2019/5/1.

成绩是怎么算出来的？ 16级第一学期半期考试成绩班级姓名语文数学英语政治历史地理物理化学生物总分 1 张三1 115

第4章 Excel电子表格制作软件 4.4 函数（一）.

定理21.9(可满足性定理)设A是P(Y)的协调子集，则存在P(Y)的解释域U和项解释，使得赋值函数v(A){1}。

iSIGHT 基本培训使用 Excel的栅栏问题

§6.7 子空间的直和一、直和的定义二、直和的判定三、多个子空间的直和.

3.16 枚举算法及其程序实现 ——数组的作用.

数据集的抽取式摘要程龚, 徐丹云.

1.设A和B是集合，证明：A=B当且仅当A∩B=A∪B

多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer

学习任务三偏导数结合一元函数的导数学习二元函数的偏导数是非常有用的. 要求了解二元函数的偏导数的定义, 掌握二元函数偏导数的计算.

海报题目简介: 介绍此项仿真工作的目标和需要解决的问题。可以添加合适的图片。

基于最大margin的决策树归纳李宁.

基于规则抽取的时间表达式识别 -英文Ⅲ 高冠吉.

第15讲特征值与特征向量的性质主要内容：特征值与特征向量的性质.

GIS基本功能数据存储与管理数据采集数据处理与编辑空间查询空间查询 GIS能做什么？与分析叠加分析缓冲区分析网络分析

第二节函数的极限一、函数极限的定义二、函数极限的性质三、小结思考题.

定义21.17:设P1=P(Y1)和P2=P(Y2)，其个体变元与个体常元分别为X1,C1和 X2,C2，并且或者C1=或者C2。一个半同态映射(,):(P1,X1∪C1)→(P2,X2∪C2)是一对映射: P1→P2; : X1∪C1→X2∪C2，它们联合实现了映射p(x,c)→(p)((x),

基于列存储的RDF数据管理朱敏

第三节数量积向量积混合积一、向量的数量积二、向量的向量积三、向量的混合积四、小结思考题.

第四章 UNIX文件系统.

第十七讲密码执行(1).

《偏微分方程》第一章绪论第一章绪论 1.1.

§4.5 最大公因式的矩阵求法（ Ⅱ ）.

§2 自由代数定义19.7:设X是集合，G是一个T-代数，为X到G的函数,若对每个T-代数A和X到A的函数，都存在唯一的G到A的同态映射,使得=，则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变， 变 变， 也变对给定的 和A，是唯一的.

海报题目简介: 介绍此项仿真工作的目标和需要解决的问题。可以添加合适的图片。

Presentation transcript:

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏第10章学习规则集合 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏概述对学习到的假设，最具有表征力的和最能为人类所理解的表示方法之一是if-then规则的集合本章探索若干能学习这样的规则集合的算法其中，最重要的是学习包含变量的规则集合，或称一阶Horn子句集合由于一阶Horn子句集合可被解释为逻辑编程语言Prolog中的程序，学习的过程常被称为归纳逻辑编程本章考察了多种学习规则集合的途径，其中一种是基于机器定理证明器中演绎算子的逆转 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏简介在许多情况下，有必要学习一个由若干if-then规则共同定义的目标函数，比如决策树遗传算法本章我们讨论一组不同的算法，它们直接学习规则集合，与前面算法有两点关键的不同可学习包含变量的一阶规则集合（一阶子句的表达能力比命题规则要强得多）使用序列覆盖算法，一次学习一个规则，以递增的方式形成最终的规则集合 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：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.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏内容安排先介绍能够学习命题规则集的算法（命题规则可看作不含变量的一阶规则），算法搜寻假设空间学习析取规则集合将上面算法扩展到一阶规则讨论归纳逻辑的两种通用途径以及归纳和演绎推理的基本关系 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏序列覆盖算法序列覆盖算法学习一个规则，移去它覆盖的数据，再重复这一过程假定已有一个子程序Learn-One-Rule，它的输入是一组正例和反例，输出是单个规则，它能够覆盖许多正例而覆盖很少的反例我们要求输出的规则有较高的精确度，但不必有较高的覆盖度 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏序列覆盖算法（2）序列覆盖算法的过程在所有可用训练样例上执行Learn-One-Rule 再移去由其学到的规则覆盖的正例重复上面的过程，直到规则集覆盖正例达到希望的程度序列覆盖算法按次序学习到一组规则，它们共同覆盖了全部正例规则集中的规则可排序，分类新实例时可先应用精度最高的规则 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

表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正确分类的样例} Learned_rules按照在Examples上的Performance排序的Learned_rules 返回Learned_rules 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏序列覆盖算法（3）序列覆盖算法将问题化简为一系列简单的问题，执行的是一种贪婪搜索，它不能保证找到能覆盖样例的最小或最佳规则集下面重点讨论Learn-One-Rule的设计，我们希望算法能够得到较高精度的规则集，但不必覆盖所有的正例 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏一般到特殊的柱状搜索一种方法是，将假设空间搜索过程设计为与ID3算法中相似的方式，但在每一步只沿着最有希望的分支进行，即产生最佳性能的属性-值对，而不是用增长子树的办法覆盖所选属性的所有可能值与ID3类似，可定义最佳分支，它覆盖的样例有最低的熵与其他贪婪算法一样，上面算法的缺陷是，它的每一步都可能做出次优的选择用柱状搜索来减小风险，即每一步保留k个最佳候选分支，每一步对k个候选分支进行处理，然后再将结果集削减至k个最可能成员 2003.12.18 机器学习-学习规则集合作者：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_hypothesish 更新Candidate_hypotheses Candidate_hypothesesCandidate_hypotheses中k个Performance最佳成员返回如下形式的一个规则 “如果Best_hypothesis”，则prediction 其中，prediction为在与Best_hypothesis匹配的Examples中最频繁的Target_attribute值 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

表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 译者：曾华军等讲者：陶晓鹏

对表10-2的Learn-One-Rule算法的说明算法主循环中考虑的每个假设都是属性-值约束的合取每个合取假设对应于待学习规则的候选前件集合，它由其覆盖的样例的熵来评估搜索算法不断特化候选假设，直到得到一个极大特殊假设，它包含所有可用的属性规则的后件在算法的最后一步产生，在其前件确定后，算法构造出的规则后件用于预测在前件所能覆盖的样例中最常见的目标属性值尽管使用了柱状搜索，贪婪搜索仍可能产生次优的规则 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏序列覆盖算法的几种变型只学习覆盖正例的规则，对该规则没有覆盖的实例默认地赋予其反例分类正例在整个群体中所占比例很小，所以规则集只标定正例的类别，而对其他样例默认分类为反例，这样规则集更简洁易懂这一方法对应于Prolog中的失败否定策略，其中不能证明为真的表达式都默认为假需要修改Learn-One-Rule算法增加输入变量，指定感兴趣的目标值 Performance使用假设覆盖正例的比例 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏序列覆盖算法的几种变型（2） AQ算法 AQ明确地寻找覆盖特定目标值的规则，然后，对每个目标值学习一个析取规则集 AQ算法学习单个规则的方法也不同于Learn-One-Rule，当它对每个规则执行一般到特殊柱状搜索时，他围绕单个正例来进行搜索中只考虑被某正例满足的属性，以得到逐渐特殊的假设，每次学一个新规则时，它从那些未覆盖的样例中也选择一个新的正例，以指引新析取项的搜索 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏学习规则集：小结串行与并行的差异序列学习算法（CN2）每次学习一个规则，而ID3每一步并行学习整个析取项的集合，ID3可称为并行覆盖算法 ID3在每一搜索步中根据它对数据产生的划分选择不同的属性，CN2选择的是不同的属性-值对为了学习到n个规则的集合，每个规则前件包含k个属性值测试，CN2需要nk次基本搜索步，而ID3独立选择次数要少得多 CN2需要较大数量的训练数据 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏学习规则集：小结（2）搜索方向的差异 Learn-One-Rule的搜索方向是从一般到特殊，而其他算法是从特殊到一般从一般到特殊的一个优点是只有一个极大一般假设可作为搜索起始点而多数假设空间中有很多特殊假设，因此有许多极大特殊假设，从特殊到一般的算法难以确定搜索的起点 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏学习规则集：小结（3）生成再测试与样例驱动搜索的差异样例驱动搜索算法包括：Find-S、候选消除、AQ算法、Gigol 样例驱动算法中，对假设的生成或修正是由单独的训练样例驱动的，而且结果是一个已修正的假设，它对此单个样例的性能得到改善 Learn-One-Rule是生成再测试搜索生成再测试搜索方法中，后续的假设的生成只基于假设表示的语法，然后基于这些假设在全部样例上的性能来进行选择生成再测试的一个优点是搜索中每一步的选择都基于在许多样例上的假设性能，因此噪声数据的影响被最小化 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏学习规则集：小结（4）规则的后修剪和后修剪的方法 Learn-One-Rule也有可能形成过度拟合，解决的方法也可以是后修剪性能函数的定义相对频率：令n代表规则所匹配的样例数目，nc代表其中它能正确分类的数目，则规则性能的相对频率估计为精度的m-估计：令p为从整个数据集中随机抽取的样例与该规则赋予的分类相同的先验概率，令m为权，或称对此先验概率p进行加权的等效样例数目熵：令S为匹配规则前件的样例集合，熵衡量的是该样例集合中目标函数的均一性 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏学习一阶规则本节考虑带有变量的规则，即一阶Horn子句，它们比命题规则有强得多的表征能力一阶规则的归纳学习通常被称为归纳逻辑编程，因为这一过程可看作从样例中自动推导出Prolog程序命题规则过于特殊了，不能描述属性值之间的实质关系，对今后的分类几乎不起作用，一阶规则能够表示更一般的规则一阶Horn子句还可指定前件中的变量不出现在后件中的规则，这种变量可以被存在量词或全称量词修饰还可能在规则的后件和前件中使用相同的谓词描述递归的规则 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏术语所有的一阶表达式由常量、变量、谓词符号以及函数符号组成谓词和函数的区别是谓词只能取真或假（特殊的函数），而函数的取值可为任意常量通常用小写符号表示函数，大写符号表示谓词术语：项：任意常量、任意变量、应用到任意项上的任意函数文字：应用到项上的任意谓词或其否定，如果包含否定符号，称为负文字，否则称为正文字，不包含任何变量的称为基本文字子句：多个文字的任意析取，其中所有的变量假定是全称量化的 Horn子句：至多包含一个正文字的子句，Horn子句的前件被称为子句体或子句先行词，后件被称为子句头或子句推论置换：将文字L的某些变量替换为某些项的函数，记为L。如果置换使得L1=L2，那么称为L1和L2的合一置换 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏学习一阶规则集：FOIL FOIL学习的规则类似Horn子句，但有两个不同：比Horn子句更受限，因为文字不允许包含函数符号比Horn子句更有表征力，因为规则体中的文字可以是负文字 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏表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 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 FOIL算法的解释 FOIL外层循环中每次加入一条新的规则到其析取式假设Learned_rules中去每个新规则的效果是通过加入一个析取项泛化当前的析取假设这是假设空间的特殊到一般的搜索过程，它开始于最特殊的空析取式，在假设足够一般以至覆盖所有正例时终止 FOIL内层循环执行的是细粒度较高的搜索，以确定每个新规则的确切定义内层循环在另一假设空间中搜索，它包含文字的合取，以找到一个合取式形成规则的前件内层循环执行一般到特殊的爬山搜索，开始于最一般的前件，然后增加文字以使规则特化直到避开所有的反例 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 FOIL算法的解释（2） FOIL与前面的序列覆盖和Learn-One-Rule算法之间有两个最实质的不同，来源于算法对一阶规则处理的需求在学习每个新规则的一般到特殊搜索中，FOIL使用了不同的细节步骤来生成规则的候选特化式，这一不同是为了处理规则前件中含有的变量 FOIL使用的性能度量FOIL_Gain不同于表10-2中的熵度量，这是为了区别规则变量的不同约束，以及由于FOIL只搜寻覆盖正例的规则 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 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 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：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.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：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.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏引导FOIL的搜索（选择文字）要在每一步中从候选文字中选择最有希望的文字，FOIL在训练数据上测量规则的性能在此过程中，考虑当前规则中每个变量的可能的约束 FOIL使用评估函数以估计增加新文字的效用，它基于加入新文字前后的正例和反例的约束数目考虑某个规则R和一个可能被加到R的规则体的候选文字L，令R’为加入文字L到规则R后生成的规则，则按照信息论理论，Foil_Gain(L,R)可看作，为了编码R的所有正例约束的分类所需的全部位数由于L带来的减少 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏学习递归规则集如果在表10-4的算法输入参数Predicates中包含目标谓词（即规则头的谓词），那么FOIL在生成候选文字时必须考虑它，这允许产生递归的规则递归规则是否能被FOIL发现，取决于它在FOIL的贪婪搜索中是否比其他候选评分更高避免在学习规则集中产生无限递归 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 FOIL小结 FOIL扩展了CN2的序列覆盖算法，执行一般到特殊的搜索，每步增加一个新的文字到规则前件中，新文字可是规则前件或后件中已有的变量，或为新变量 FOIL在每一步使用Foil_Gain函数在候选新文字中进行选择，如果新文字可指向目标谓词，那么FOIL可能学习到递归规则在训练数据无噪声的情况下，FOIL可持续地增加新文字到规则中，直到不覆盖任何反例为处理有噪声数据，搜索的终止需要在规则精度、覆盖度和复杂性之间做出折中 FOIL使用最小描述长度的方法终止规则增长，新的文字只在它们的描述长度短于它们所解释的数据的描述长度时才被加入 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏作为逆演绎的归纳归纳逻辑编程，基于一个简单的事实：归纳是演绎的逆过程一般来说，机器学习涉及的是如何建立能解释观察数据的理论，给定某些数据D和一些不完整的背景知识B，学习过程被描述为生成一个假设h，它与B一起解释了D，即基于背景知识扩展谓词集合的过程，称为建设性归纳可以利用演绎推理的逆过程，以使归纳泛化的过程自动化 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏作为逆演绎的归纳（2）我们感兴趣的是设计一个逆涵蕴算子O(B,D)，它使用训练数据D和背景知识B作为输入，输出一个满足式子10.2的假设h 满足式子10.2的假设很多，一般依赖最小描述长度准则来进行选择逆演绎的归纳方法有许多有吸引力的特点：包含了一种普遍的学习定义方法，即寻找某个一般概念，它与给定的训练样例相拟合通过引入背景知识，可以对一个假设何时可被称作“拟合”训练数据进行更充分的定义通过引入背景知识B，该公式要求学习算法使用这一背景信息来引导h的搜索，而不是只搜索语法上合法的假设空间 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏作为逆演绎的归纳（3）不能处理有噪声的数据，不允许在观察到实例xi和其目标值f(xi)中出现差错的可能性，这样的差错可能产生对h的不一致约束，但是多数形式逻辑框架完全没有处理不一致断言的能力一阶逻辑语言的表征力太强，而且满足式子10.2的假设很多，以至于假设空间的搜索在一般情形下难以执行尽管直觉上背景知识有助于限制假设的搜索，但在多数ILP系统中，搜索的复杂度随着背景知识的增加而增高 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏逆归纳自动演绎的一般方法是Robinson提出的归纳规则，归纳规则是一阶逻辑中一个合理且完备的演绎推理规则算法Gigol通过反转归纳规则来形成逆涵蕴算子命题归纳规则是归纳算子给定初始子句C1和C2，从子句C1中寻找一个文字L，并且L出现在C2中通过合并C1和C2中的除了L和L的所有文字，形成归纳式C，即C=(C1-{L})(C2-{L}) 给定两个子句，归纳算子首先确定文字L是否以正文字出现在一个子句中，以负文字出现在另一个子句中，然后使用上面的归纳规则，见图10-2 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：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})){L} 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏逆归纳（3）可以基于逆归纳这样的逆涵蕴算子开发出规则学习算法来一种策略是使用序列覆盖算法，循环地以这种方法学习Horn子句集每次循环中，算法选择没有被以前学习到的子句覆盖的一个训练样例<xi,f(xi)>，然后应用归纳规则来生成满足(Bhixi)f(xi)的候选假设hi 这是一个样例驱动的搜索，因为每个候选假设的建立是为了覆盖一特定样例如果存在多个候选假设，那么选择的策略是选取在其他样例上也有最高精度的假设 Gigol程序使用了结合这种序列覆盖算法的逆归纳，通过它与用户交互，获得训练样例并引导它在可能的归纳推理步骤的巨大空间中的搜索， Gigol使用了一阶表示而不是命题表示 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏一阶归纳归纳规则可以很容易地扩展到一阶表示，与命题归纳的关键不同是：这个过程基于合一置换操作定义置换为变量到项的任意映射，符号W表示应用置换到表达式W上的结果置换的例子 L=Father(x,Bill) ={x/Bob, y/z} L=Father(Bob,Bill) 合一置换：如果L1=L2，则为两个文字L1和L2的合一置换 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：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.3 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：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.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏一阶情况的逆归纳式子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 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏一阶情况的逆归纳（2）式子10.4表示的逆涵蕴算子是非确定的，在应用过程中，一般可找到待归纳的子句C1和置换1和2的多种选择，每组不同的选择都产生一个不同的C2 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：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.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏逆归纳小结逆归纳提供了一种一般的途径以自动产生满足式子10.2的假设与FOIL方法的差异逆归纳是样例驱动，FOIL是生成再测试逆归纳在每一步只考虑可用数据中的一小部分，FOIL考虑所有的可用数据看起来基于逆归纳的搜索更有针对性且更有效，但实际未必如此 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏泛化、-包容于和涵蕴考虑如下的定义 more_general_than：给定两布尔值函数hj(x)和hk(x)，称hjghk，当且仅当(x)hk(x)hj(x)（参见第2章） -包容于：考虑两个子句Cj和Ck，称Cj -包容于Ck，当且仅当存在一个置换，使得CjCk 涵蕴：考虑两个子句Cj和Ck，子句Cj被称为涵蕴Ck，当且仅当Ck从Cj中演绎派生 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏泛化、-包容于和涵蕴（2）三个定义之间的关系泛化和-包容于的关系：如果h1gh2，则子句C1:c(x)h1(x) -包容于子句C2:c(x)h2(x) -包容于是涵蕴的一种特殊形式，即如果子句A -包容于子句B，则AB，然而反之不一定成立因此，泛化是-包容于的一种特殊情况，而-包容于又是涵蕴的特殊情况通过泛化和特化假设来搜索假设空间比用一般的逆涵蕴算子来搜索更局限遗憾的是，逆涵蕴这种最一般的形式可产生无法处理的搜索中间的-包容于提供了位于泛化和涵蕴之间的一种概念和方法 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 Progol 在实践中，逆归纳容易导致候选假设的组合爆炸另一种途径（Progol的思想）是：只使用逆涵蕴来生成一个最特殊假设，它与背景信息一起涵蕴观察的数据然后，这个最特殊假设可用于确定假设空间的一般到特殊搜索边界，只考虑比此边界更一般的假设 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏 Prolog（2） Progol使用的算法概述用户指定使用一个受限的一阶表示语言为假设空间H， Progol使用序列覆盖法来从H中学习一组覆盖数据的表达式 Progol在这个由最一般假设和第2步中得到的特殊边界hi所界定的假设空间中执行了一般到特殊搜索，在此假设集合中，它寻找有最小描述长度的假设 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏小结序列覆盖算法学习析取的规则集，方法是先学习单个精确的规则，然后移去被此规则覆盖的正例，再在剩余样例上重复这一过程序列覆盖算法提供了一个学习规则集的有效的贪婪算法，可作为由顶向下的决策树学习算法的替代算法，决策树算法可被看作并行覆盖，与序列覆盖相对应在序列覆盖算法中，已研究了多种方法以学习单个规则，这些方法的不同在于它们考察规则前件空间的策略不同一阶规则集提供了一种表征能力很强的表示，学习一阶Horn子句的问题常被称为归纳逻辑编程的问题 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏小结（2）学习一阶规则集的方法是将CN2中的序列覆盖算法由命题形式扩展到一阶表示，体现在FOIL程序中，它可学习包括简单递归规则集在内的一阶规则集学习一阶规则集的另一个方法是逆归纳，通过运用熟知的演绎推理的逆算子来搜索假设 Cigol使用的逆归纳是归纳算子的逆转，而归纳是普遍用于机器定理证明的一种推理规则，Progol结合了逆涵蕴策略和一般到特殊策略来搜索假设空间 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏补充读物 Winston1970，学习如“arch”这样的概念的网络式描述 Banerji1964,1969，将逻辑表示用于学习问题的研究 Michalski，AQ算法 Plotkin1970，-包容于的定义，对归纳和演绎之间的关系进行了形式化 Vere1975，研究了学习的逻辑表示问题 Buchanan1976，Meta-Dendral程序可学习分子结构中可在质谱仪中被分割的部分的关系描述 Mitchell1979，候选消除变型空间算法被用于化学结构的关系描述 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏补充读物（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 译者：曾华军等讲者：陶晓鹏

机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏补充读物（3）归纳逻辑编程 Lavrac & Dzeroski，一个可读性很强的教材 Wrobel1996，一个好的综述 Bratko & Muggleton1995，概述了ILP在一些重要问题上的应用 2003.12.18 机器学习-学习规则集合作者：Mitchell 译者：曾华军等讲者：陶晓鹏