【西瓜书】第十五章 规则学习
本文是周志华老师《机器学习》第十五章规则学习的学习笔记及部分习题答案。
规则： 语义明确，能描述数据分布所隐含的客观规律或领域概念的逻辑规则。
形式化地看，规则形如：
其中右边称作规则体（body），左边称作规则头（head）。可以看出，规则体是由逻辑文字组成的合取式。
相较其他黑箱模型，规则学习有着以下优势：
- 良好的可解释性
- 极强的表达能力，便于引入领域知识
- 处理一些高度复杂的AI任务时有优势
对于规则，我们可以将其视作一个子模型，而规则集合就可以看作是集成模型。
若一个样本满足一条规则，我们称之为被覆盖，那么我们需要规则集能够覆盖尽可能多的样例。
当每条样本被规则判定为不同结果时，我们称之为冲突，消解冲突往往用以下方法：
- 投票法:判别最多的类别作为最终规则
- 排序法:生成规则时就设定好规则的优先级
- 元规则:设定关于规则的规则，如“发生冲突时使用长度最小的规则”
规则可以分为两类：
命题规则 ： 由原子命题和逻辑连接词构成的简单陈述句
一阶规则： 又称关系型规则，描述事物属性或关系的原子公式，如表达父子关系的谓词公式“父子(X,Y)”
序贯覆盖
为了产生一个能够覆盖尽可能多的样例的规则集，最直接的做法就是序贯覆盖，即每学到一条规则就将规则覆盖的样例去除，然后以剩下的样例组成训练集重复上述操作。
显然，生成规则时若采用穷举法，在属性较多的情况下会发生组合爆炸，因此我们通常使用两种策略：
- 自顶向下，又称生成测试法： 从比较一般的规则开始，逐渐添加新的文字以缩小规则覆盖范围，更容易产生泛化性能较好的规则，鲁棒性更好，更适用于命题规则学习
- 自底向上，又称规则驱动法： 从较为特殊的规则出发，逐渐删除文字以扩大覆盖范围，更适合训练样本较少的情况，适用于一阶规则学习这类假设空间非常复制的任务
因为自顶向下中，若每次仅考虑一个最优文字，过于贪心，易陷入局部最优，通常采取集束搜索，每轮保留最优的 $b$ 个文字。
剪枝优化
规则生成本质上是一个贪心的过程，因此需要用剪枝来缓解过拟合的风险。
通常我们基于某种性能度量指标来评估增删文字前后的规则性能从而来判断是否剪枝。
使用CN2算法来进行预剪枝时，我们借助统计显著性检验来进行。它使用了似然统计率（Likelihood Ratio Statistics, LRS）。
LRS越大说明规则的效果越好，否则说明规则的效果越可能是偶然现象，在数据量比较大的现实任务中，通常设置为在LRS很大（如0.99）时算法才停止规则集生长。
后剪枝中常用的是减错剪枝（Reduced Error Pruning， REP），其基本做法是将样例分为训练集（生长集）和测试集（剪枝集）。在训练集上学习到规则后在测试集上进行多轮剪枝，穷举所有的剪枝操作（删除规则中某个文字/删除规则结尾文字/删除规则尾部多个文字/删除整体规则）。然后用验证集上效果最好的规则集进行下一轮剪枝，直到效果无法提升。
REP虽然很有效，但是复杂度太高（$O(n^4)$）。IREP（Incremental REP）算法将复杂度降到了$O(mlog^2m)$。其做法是：生成每条规则前，划分数据集，在训练集上生产一条规则，就在验证集上剪枝，得到新的规则，然后将新规则覆盖的样例去除，在新的道德样例集上重复以上操作。
容易看出REP和IREP的不同，后者仅对单条规则进行剪枝，而前者是对整个规则集进行的。
若将剪枝和许多后处理手段结合起来优化规则集，效果往往更好，如著名的规则学习算法RIPPER，泛化性能超过很多决策树算法。
该算法先使用IREP*剪枝机制来生成规则集。
IREP*和IREP的主要不同就是用$\frac{\hat{m}_+(m_-\hat{m}-)}{m++m_-}$ 取代准确率作为规则性能度量。
这里的后处理机制为，对规则集中的每个规则，RIPPER生成两条变体：
- $r_i’$： 基于$r_i$的样例，用IREP*重新生成规则$r_i’$， 称为替换规则
- $r_i’’$ 对$r_i$增加文字进行特化，然后用IREP*生成规则，称之为修订规则
然后将$r_i’$ 和 $r_i’’$ 分别与规则集中除了$r_i$ 的规则放在一起，对这些规则集进行比较，择优保留，也就是图中算法第4行的操作。
RIPPER有效在通过将规则集中所有规则放在一起重新优化，通过全局的考虑缓解了贪心算法的局部性。
一阶规则学习
关于一阶规则学习机器之后的归纳逻辑程序设计，这里按下暂不表。
习题答案
1. 对西瓜数据集2.0，允许使用否定形式的文字，试基于自顶向下的策略学出命题规则集。
15.1
2. 对西瓜数据集2.0，在学习过程中可通过删去文字、将常量替换为变量来进行规则泛化，试基于自底向上的策略学出命题规则集。
15.2
10 基于序贯覆盖的规则学习算法在学习下一条规则前，会将已被当前规则集所覆盖的样例从训练集中删去。这种贪心策略会使得后续学习过程仅需关注以往未覆盖的样例，在判定规则覆盖率时不需要考虑前后规则间的相关性；但该策略使得后续学习过程中能够参考的样例越来越少，试设计一种不删除样例的规则学习算法。
答：使用集束搜索，并令 $b=k$， 其中$k$ 为一轮候选集中所有逻辑文字的数目。
wechat
alipay
