《ch15规则学习-周志华课件》由会员分享，可在线阅读，更多相关《ch15规则学习-周志华课件（63页珍藏版）》请在金锄头文库上搜索。
1、戴望州,第十五章：规则学习,大纲,基本概念 序贯覆盖 剪枝优化 一阶规则学习 归纳逻辑程序设计,基本概念,机器学习里的规则： 若，则. 回归 分类 聚类 ,若 ，则,若 ，则,逻辑规则 规则集 充分性与必要性 冲突消解：顺序规则、缺省规则、元规则,基本概念,读作：若（文字1且文字2且），则（目标概念）成立,基本概念,命题逻辑 命题规则 原子命题： 逻辑连词： 一阶逻辑 一阶规则 常量： 变量： （n元）谓词/函数： 项： 原子公式： 逻辑连词 逻辑量词：,大纲,基本概念 序贯覆盖 剪枝优化 一阶规则学习 归纳逻辑程序设计,序贯覆盖,-,在训练集上每学到一条规则，就将改规则覆盖的样例去除，然后以
2、剩下的样例组成训练集重复上述过程（分治策略）。,序贯覆盖,-,序贯覆盖,-,Rule 1,序贯覆盖,-,Rule 1,序贯覆盖,-,Rule 1,Rule 2,序贯覆盖,-,Rule 1,Rule 2,序贯覆盖,-,Rule 1,Rule 2,Rule 4,Rule 3,大纲,基本概念 序贯覆盖 单条规则学习 剪枝优化 一阶规则学习 归纳逻辑程序设计,单条规则学习,目标：寻找一组最优的逻辑文字来构成规则体 本质：搜索问题 搜索空间大，易造成组合爆炸 方法： 自顶向下：一般到特殊（泛化） 自底向上：特殊到一般（特化）,单条规则学习,自顶向下策略：一般到特殊（特化）,-,单条规则学习,自顶向下策略
3、：一般到特殊（特化）,-,单条规则学习,自顶向下策略：一般到特殊（特化）,-,Rule 1,单条规则学习,自顶向下策略：一般到特殊（特化）,-,Rule 1,Rule 2,Rule 3,Rule 4,单条规则学习,自底向上策略：特殊到一般（泛化）,-,单条规则学习,自底向上策略：特殊到一般（泛化）,-,单条规则学习,自底向上策略：特殊到一般（泛化）,-,Rule 1,单条规则学习,规则评判：增加/删除哪一个候选文字 准确率 信息熵增益（率） 基尼系数 规避局部最优 集束搜索：每次保留最优的多个候选规则 ,大纲,基本概念 序贯覆盖 剪枝优化 一阶规则学习 归纳逻辑程序设计,序贯覆盖（非最优）,-
4、,贪心算法导致的非最优情况,序贯覆盖（非最优）,-,序贯覆盖（非最优）,-,Rule 1,序贯覆盖（非最优）,-,Rule 1,序贯覆盖（非最优）,-,Rule 1,Rule 2,序贯覆盖（非最优）,-,Rule 1,Rule 2,Rule 3,Rule 4,Rule 5,剪枝优化,预剪枝 似然率统计量Clark and Niblett, 1989 后剪枝 减错剪枝（REP）Brunk and Pazzani, 1991 穷举所有可能的剪枝操作（删除文字，删除规则），复杂度非常高 用验证集反复剪枝直到准确率无法提高 二者结合 IREPFrnkranz and Widmer, 1994 每生成一
5、条新规则即对其进行REP剪枝 IREP*Cohen, 1995 对IREP的改进 RIPPERCohen, 1995,大纲,基本概念 序贯覆盖 剪枝优化 RIPPER 一阶规则学习 归纳逻辑程序设计,RIPPER Cohen, 1995,-,Rule 1,Rule 2,Rule 3,Rule 4,IREP*生成规则集,覆盖了两个负样本！,RIPPER Cohen, 1995,-,IREP*生成规则集 选取一条规则，找到其覆 盖的样例,Rule 2,Rule 3,Rule 4,RIPPER Cohen, 1995,-,IREP*生成规则集 选取该规则，找到其覆 盖的样例 重新生成规则,Rule
6、2,Rule 3,Rule 4,RIPPER Cohen, 1995,-,IREP*生成规则集 选取该规则，找到其覆 盖的样例 重新生成规则 特化原规则再泛化,Rule 2,Rule 3,Rule 4,RIPPER Cohen, 1995,-,生成规则集 选取一条规则，找到其覆 盖的样例 重新生成规则 特化原规则再泛化 把原规则和新规则分别置 入规则集进行评价，留下 最好的,Rule 2,Rule 3,Rule 4,RIPPER Cohen, 1995,-,生成规则集 选取一条规则，找到其覆 盖的样例 重新生成规则 特化原规则再泛化 把原规则和新规则分别置 入规则集进行评价，留下 最好的。 4
7、. 反复优化直到无法进步,RIPPER将所有规则放在一起优化，通过全局的考虑来缓解序贯覆盖的局部性,Rule 3,Rule 4,大纲,基本概念 序贯覆盖 剪枝优化 一阶规则学习 归纳逻辑程序设计,一阶规则学习,“一阶”的目的：描述一类物体的性质、相互关系,实际应用中很难量化颜色、敲声的属性值,一阶规则学习,利用一阶关系来挑“更好的”瓜,2,1,一般情况下可以省略全称量词,一阶规则学习,属性-值(Attribute-value)数据 【命题逻辑】,关系型(Relational)数据 【一阶逻辑】,背景知识,样例,FOILQuinlan, 1990,序贯覆盖生成规则集 自顶向下学习单条规则 候选文
8、字需考虑所有可能的选项 规则生长的评判标准为FOIL增益 后剪枝优化规则集,能否引入新变量？ 能否使用否定文字？ 能否允许递归？ 能否引入函数嵌套？：p(f(f(f(X),大纲,基本概念 序贯覆盖 剪枝优化 一阶规则学习 归纳逻辑程序设计,归纳逻辑程序Muggleton, 1991,目标：完备地学习一阶规则（Horn子句） 仍然以序贯覆盖方法学习规则集 一般采用自底向上策略学习单条规则 不需要列举所有可能的候选规则 对目标概念的搜索维持在样例附近的局部区域 自顶向下策略的搜索空间对于规则长度呈指数级增长,最小一般泛化(LGG)Plotkin, 1970,“泛化”：将覆盖率低的规则变换为覆盖率高
9、的规则 “一般”：覆盖率尽可能高 “最小”：变换时对原规则的改动尽可能小 寻找两条规则LGG的步骤： 找出两条规则中涉及相同谓词的文字 考察谓词后括号里的项： s, t不是谓词相同的项，则 ，V为任意未出现过的变量 s, t为谓词相同的项，递归考察其括号内的项 删除没有相同谓词出现的文字,最小一般泛化(LGG)Plotkin, 1970,最小一般泛化(LGG)Plotkin, 1970,其他基于LGG的ILP算法 考虑否定文字 不同的初始化选择 多条特殊规则 考虑所有背景知识（RLGG）Plotkin, 1971 ,逆归结Muggleton and Buntine, 1988,演绎(deduc
10、tion) VS 归纳(induction),“猜想是很不好的习惯，它有害于作逻辑的推理。你所以觉得奇怪，是因为你没有了解我的思路，没有注意到往往能推断出大事来的那些细小问题（the small facts upon which large inferences may depend）。举例来说吧，我开始时曾说你哥哥的行为很不谨慎。请看这只表，不仅下面边缘上有凹痕两处，整个表的上面还有无数的伤痕，这是因为惯于把表放在有钱币、钥匙一类硬东西的衣袋里的缘故。对一只价值五十多镑的表这样不经心，说他生活不检点，总不算是过分吧！。” 歇洛克福尔摩斯 演绎法研究（The science of deduct
11、ion）四签名,归结与逆归结Muggleton and Buntine, 1988,演绎：归结原理Robinson, 1965 归纳：逆归结,如何考虑带变量的逻辑表达式？,演绎：验证逻辑表达式的可满足性,输入,输出,一阶逆归结,置换：用项替换变量 复合置换： 逆置换： 合一：通过置换让两个表达式相等 最一般合一置换（MGU）：任意一个合一置换都是MGU的复合置换,MGU,一阶逆归结,一阶归结：当 ， 一阶逆归结： 例子（p. 353）： 找一个不在归结项 中的 使 存在一个解： 使得,逆归结Muggleton and Buntine, 1988,四种完备的逆归结操作,逆归结Muggleton
12、and Buntine, 1988,吸收,逆归结Muggleton and Buntine, 1988,辨识,逆归结Muggleton and Buntine, 1988,内构,逆归结Muggleton and Buntine, 1988,内构,逆归结Muggleton and Buntine, 1988,互构,谓词发明,目标概念：“楼梯”,归纳逻辑程序学习,完备地学习一阶规则 谓词发明：发现领域中隐含的结构 得到的规则可直接作为逻辑程序进行应用 其他归纳逻辑程序学习方法： 命题化学习Lavrac and Dzeroski, 1993 逆蕴含Muggleton, 1995 Meta-Inter
13、pretive LearningMuggleton and Lin, 2013 ,总结,逻辑规则 命题规则、一阶规则 规则集学习：序贯覆盖 单条规则学习：自顶向下、自底向上 剪枝与后处理 一阶规则学习 归纳逻辑程序学习 最小一般泛化 逆归结,常用工具,WEKA中的JRIP（ ILP的集大成工具ALEPH（http:/www.cs.ox.ac.uk/activities/machlearn/Aleph/aleph.html） 相对最小一般泛化：GOLEM（http:/www.doc.ic.ac.uk/shm/golem.html） 逆演绎：Progol（http:/www.doc.ic.ac.uk/shm/progol.html） 开源Prolog环境： YAP（http:/www.dcc.fc.up.pt/vsc/Yap/） SWI-Prolog（http:/www.swi-prolog.org/）,
