手记

机器学习 西瓜书 Day22 规则学习

p347 - p371
前几天休刊了,今天回来了= =
进入第15章

第15章 规则学习模型

15.1 基本概念

“规则”通常指语义明确,能描述数据分布隐含的客观规律或领域概念,可写成“若..则..”。

与其他黑箱模型相比,规则学习具有更好的可解释性。
绝大多数人类知识都能通过数理逻辑来进行刻画,因此便于引进领域知识。

符合一条规则的样本称为被该规则“覆盖”

当同一个示例被判别结果不同的多条规则覆盖时,称发生了冲突
解决冲突的方法称为冲突消解,包括投票法、排序法、元规则法。

一般都要设置默认规则,来处理规则集合未覆盖的样本。

命题规则VS一阶规则(关系型规则) p348

15.2 序贯覆盖

规则学习最直接的做法是“序贯覆盖”,即逐条归纳。
每学到一条规则,就将该规则覆盖的样本去掉,以剩下的样例继续训练。
由于每次只处理一部分数据,所以也被称为“分治”策略。

基于穷尽搜索的做法
例子:p350。

但现实中会因为组合爆炸而不可行。
通常有两种策略:
自顶向下(生成-测试) vs 自底向上(数据驱动)

前者是从一般的规则开始,逐渐添加新文字,是规则逐渐“特化”的过程
更容易产生泛化性能较好的规则。
对噪声鲁棒性强。
例子p351-352。
可每次采用多个最优文字来避免过于贪心。

后者是从特殊的规则开始,减少文字,是“泛化”的过程。
更适用于训练样本较少。

15.3 剪枝优化

规则生成本质是一个贪心搜索过程,需要缓解过拟合。
最常见做法是剪枝

预剪枝  vs  后剪枝

CN2算法的预剪枝。借助了统计性检验。

REP的后剪枝,O(m^4)。
IREP O(m log^2 m)
著名的规则学习算法 RIPPER 后处理机制,将R中所有规则再进行一次优化,就是通过全局的考虑来缓解了贪心算法的局部性。

15.4 一阶规则学习

通常很难定义属性值。
因此可以采用“色泽更深(2,1)、更好(2,1)”这样的表述方式。

色泽更深 这样的原子公式称为“背景知识”
更好 这样由样本类别转化而来的原子公式称为“关系数据样例”

一阶学习能容易的引入领域知识,是相比命题学习的一大优势。

在命题规则学习乃至一般的统计学习中,引入领域知识通常有两种做法:
1)通过领域知识构造新属性。
2)基于领域知识设计某种函数机制(如正则化)来对假设空间进行约束。

FOIL算法:著名的一阶规则学习算法。
遵循序贯覆盖并采用自顶向下的归纳策略。
并采用后剪枝进行优化。
使用FOIL增益来选择文字。

15.5 归纳逻辑程序设计(ILP)

在一阶学习中引入了函数和逻辑表达式嵌套
容易看到这样就不能自顶向上了,因为无法穷举。

15.5.1 最小一般泛化(LGG)

ILP都采用自底向上的策略。
如何把特殊规则转化为一般规则?
最基础的技术是LGG
举例:p358 - p359

15.5.2 逆归结

归结原理:一阶谓词演算中的演绎推理能用一条十分简洁的规则描述。
可将复杂的逻辑规则和背景知识联系起来化繁为简

逆归结:能基于背景知识来发明新的概念和关系

p360-p363 具体过程有些抽象
逆归结的一大特点是可以自动发明新谓词,这些新谓词可能对应于一些新知识。

15.6 阅读材料

规则学习是符号主义学习的主要代表。



作者:皇家马德里主教练齐达内
链接:https://www.jianshu.com/p/065eb5ba5945


0人推荐
随时随地看视频
慕课网APP