ch15规则学习-周志华

戴望州第十五章：规则学习大纲基本概念序贯覆盖剪枝优化一阶规则学习归纳逻辑程序设计基本概念机器学习里的规则：若……，则…….回归分类聚类……若，则若，则；若，则若，则逻辑规则规则集充分性与必要性冲突消解：顺序规则、缺省规则、元规则基本概念规则头规则体逻辑蕴含符目标概念（逻辑文字）逻辑文字逻辑“与”读作：若（文字1且文字2且…），则（目标概念）成立原子公式基本概念命题逻辑命题规则原子命题：逻辑连词：一阶逻辑一阶规则常量：变量：（n元）谓词/函数：项：原子公式：逻辑连词逻辑量词：大纲基本概念序贯覆盖剪枝优化一阶规则学习归纳逻辑程序设计序贯覆盖+++++++++-+++++++++++-----------------------------------在训练集上每学到一条规则，就将改规则覆盖的样例去除，然后以剩下的样例组成训练集重复上述过程（分治策略）。序贯覆盖+++++++++-+++++++++++-----------------------------------序贯覆盖+++++++++-++-----------------------------------Rule1序贯覆盖+++++++++-++-----------------------------------Rule1序贯覆盖++++-++-----------------------------------Rule1Rule2序贯覆盖++++-++-----------------------------------Rule1Rule2序贯覆盖------------------------------------Rule1Rule2Rule4Rule3大纲基本概念序贯覆盖单条规则学习剪枝优化一阶规则学习归纳逻辑程序设计单条规则学习目标：寻找一组最优的逻辑文字来构成规则体本质：搜索问题搜索空间大，易造成组合爆炸方法：自顶向下：一般到特殊（泛化）自底向上：特殊到一般（特化）单条规则学习自顶向下策略：一般到特殊（特化）+++++++++-+++++++++++-----------------------------------单条规则学习自顶向下策略：一般到特殊（特化）+++++++++-+++++++++++-----------------------------------单条规则学习自顶向下策略：一般到特殊（特化）+++++++++-+++++++++++-----------------------------------Rule1单条规则学习自顶向下策略：一般到特殊（特化）+++++++++-+++++++++++-----------------------------------Rule1Rule2Rule3Rule4单条规则学习自底向上策略：特殊到一般（泛化）+++++++++-+++++++++++-----------------------------------单条规则学习自底向上策略：特殊到一般（泛化）+++++++++-+++++++++++-----------------------------------单条规则学习自底向上策略：特殊到一般（泛化）+++++++++-+++++++++++-----------------------------------Rule1单条规则学习规则评判：增加/删除哪一个候选文字准确率信息熵增益（率）基尼系数……规避局部最优集束搜索：每次保留最优的多个候选规则……大纲基本概念序贯覆盖剪枝优化一阶规则学习归纳逻辑程序设计序贯覆盖（非最优）+++++++++-+++++++++++---------------------------------贪心算法导致的非最优情况序贯覆盖（非最优）+++++++++-+++++++++++---------------------------------序贯覆盖（非最优）+++++++++-+++++++++++---------------------------------Rule1序贯覆盖（非最优）+++++++++-+++++++++++---------------------------------Rule1序贯覆盖（非最优）+++++++++-+++++++++++---------------------------------Rule1Rule2序贯覆盖（非最优）+++++++++-+++++++++++---------------------------------Rule1Rule2Rule3Rule4Rule5剪枝优化预剪枝似然率统计量[ClarkandNiblett,1989]后剪枝减错剪枝（REP）[BrunkandPazzani,1991]穷举所有可能的剪枝操作（删除文字，删除规则），复杂度非常高用验证集反复剪枝直到准确率无法提高二者结合IREP[FürnkranzandWidmer,1994]每生成一条新规则即对其进行REP剪枝IREP*[Cohen,1995]对IREP的改进RIPPER[Cohen,1995]大纲基本概念序贯覆盖剪枝优化RIPPER一阶规则学习归纳逻辑程序设计RIPPER[Cohen,1995]+++++++++-+++++++++++-----------------------------------Rule1Rule2Rule3Rule41.IREP*生成规则集覆盖了两个负样本！RIPPER[Cohen,1995]+++++++++-+++++++++++-----------------------------------1.IREP*生成规则集2.选取一条规则，找到其覆盖的样例Rule2Rule3Rule4RIPPER[Cohen,1995]+++++++++-+++++++++++-----------------------------------1.IREP*生成规则集2.选取该规则，找到其覆盖的样例a)重新生成规则Rule2Rule3Rule4RIPPER[Cohen,1995]+++++++++-+++++++++++-----------------------------------1.IREP*生成规则集2.选取该规则，找到其覆盖的样例a)重新生成规则b)特化原规则再泛化Rule2Rule3Rule4RIPPER[Cohen,1995]+++++++++-+++++++++++-----------------------------------1.生成规则集2.选取一条规则，找到其覆盖的样例a)重新生成规则b)特化原规则再泛化3.把原规则和新规则分别置入规则集进行评价，留下最好的Rule2Rule3Rule4RIPPER[Cohen,1995]+++++++++-+++++++++++-----------------------------------1.生成规则集2.选取一条规则，找到其覆盖的样例a)重新生成规则b)特化原规则再泛化3.把原规则和新规则分别置入规则集进行评价，留下最好的。4.反复优化直到无法进步RIPPER将所有规则放在一起优化，通过全局的考虑来缓解序贯覆盖的局部性Rule3Rule4大纲基本概念序贯覆盖剪枝优化一阶规则学习归纳逻辑程序设计一阶规则学习“一阶”的目的：描述一类物体的性质、相互关系实际应用中很难量化颜色、…、敲声的属性值一阶规则学习利用一阶关系来挑“更好的”瓜21颜色更深根蒂更蜷1比2好一般情况下可以省略全称量词一阶规则学习属性-值(Attribute-value)数据【命题逻辑】关系型(Relational)数据【一阶逻辑】背景知识样例FOIL[Quinlan,1990]序贯覆盖生成规则集自顶向下学习单条规则候选文字需考虑所有可能的选项规则生长的评判标准为FOIL增益后剪枝优化规则集能否引入新变量？能否使用否定文字？能否允许递归？能否引入函数嵌套？：p(f(f…(f(X))))大纲基本概念序贯覆盖剪枝优化一阶规则学习归纳逻辑程序设计归纳逻辑程序[Muggleton,1991]目标：完备地学习一阶规则（Horn子句）仍然以序贯覆盖方法学习规则集一般采用自底向上策略学习单条规则不需要列举所有可能的候选规则对目标概念的搜索维持在样例附近的局部区域自顶向下策略的搜索空间对于规则长度呈指数级增长最小一般泛化(LGG)[Plotkin,1970]“泛化”：将覆盖率低的规则变换为覆盖率高的规则“一般”：覆盖率尽可能高“最小”：变换时对原规则的改动尽可能小寻找两条规则LGG的步骤：找出两条规则中涉及相同谓词的文字考察谓词后括号里的项：s,t不是谓词相同的项，则，V为任意未出现过的变量s,t为谓词相同的项，递归考察其括号内的项删除没有相同谓词出现的文字最小一般泛化(LGG)[Plotkin,1970]最小一般泛化(LGG)[Plotkin,1970]其他基于LGG的ILP算法考虑否定文字不同的初始化选择多条特殊规则考虑所有背景知识（RLGG）[Plotkin,1971]…归纳演绎逆归结[MuggletonandBuntine,1988]演绎(deduction)VS归纳(induction)“……猜想是很不好的习惯，它有害于作逻辑的推理。你所以觉得奇怪，是因为你没有了解我的思路，没有注意到往往能推断出大事来的那些细小问题（thesmallfactsuponwhichlargeinferencesmaydepend）。举例来说吧，我开始时曾说你哥哥的行为很不谨慎。请看这只表，不仅下面边缘上有凹痕两处，整个表的上面还有无数的伤痕，这是因为惯于把表放在有钱币、钥匙一类硬东西的衣袋里的缘故。对一只价值五十多镑的表这样不经心，说他生活不检点，总不算是过分吧！……。”歇洛克·福尔摩斯演绎法研究（Thescienceofdeduction）——《四签名》规则（一般）事实（特殊）目标事实（特殊）归结与逆归结[MuggletonandBuntine,1988]演绎：归结原理[Robinson,1965]归纳：逆归结如何考虑带变量的逻辑表达式？已成立的事实规则归结掉（消去）已满足的文字p.从此若需验证r是否可满足，只需验证q是否成立.归结项归结商演绎：验证逻辑表达式的可满足性输入输出一阶逆归结置换：用项替换变量复合置换：逆置换：合一：通过置换让两个表达式相等最一般合一置换（MGU）：任意一个合一置换都是MGU的复合置换MGU一阶逆归结一阶归结：当，一阶逆归结：例子（p.353）：找一个不在归结项中的使存在一个解：使得逆归结[MuggletonandBuntine,1988]四种完备的逆归结操作逆归结[MuggletonandBuntine,1988]吸收吸收#1吸收#2逆归结[MuggletonandBuntine,1988]辨识逆归结[MuggletonandBuntine,1988]内构逆归结[MuggletonandBuntine,1988]内构逆归结[MuggletonandBuntine,1988]互构谓词发明目标概念：“楼梯”stair(X,Y):-a(X,Y).stair(X,Y):-a(X,Z),stair(Z,Y).a(X,Y):-vertical(X,Z),horizontal(Z,Y).自动发明得到的a(X,Y)即是楼梯的梯级归纳逻辑程序学习完备地学习一阶规则谓词发明：发现领域中隐含的结构得到的规则可直接作为逻辑程序进行应用其他归纳逻辑程序学习方法：命题化学习[LavracandDzeroski,1993]逆蕴含[Muggleton,199