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 阅读材料
规则学习是符号主义学习的主要代表。
