Data-方法-01 规则学习

Nothing can be accomplished without norms or standards.

Data系列：目录｜配置｜代码仓库｜对应实战
对应《数据挖掘导论》第5章、《机器学习》第15章。
规则学习作为“符号主义学习”(symbolism learning)的主要代表，是最早开始研究的机器学习技术之一，以它作为方法篇的开始，还是蛮有意义的。

1. 规则 (rule)

【基本概念】

规则(rule)：语义明确、能够描述数据分布所隐含的客观规律或领域概念，可表示成“if..., then...”形式的逻辑规则。
一条规则可以写为：$f_1\wedge f_2\wedge...\wedge f_L\rightarrow\oplus$
- 如，$r_i:(胎生=否)\wedge(飞行动物=是)\rightarrow 鸟类$
- $f_1\wedge f_2\wedge...\wedge f_L $：规则体(body)、规则前件(rule anteccedent)、前提(precondition)，是逻辑文字(literal)$f_k$组成的合取式(conjunction)。
- $\oplus$：规则头(head)、规则后件(rule consequent)，表示预测的结果，是目标类别或概念。
- $L$：逻辑文字的个数，称为规则的长度。

【规则的分类】

从形式语言表达能力而言，规则可以分为“命题规则”(propositional rule)和“一阶规则”(first-order rule)。
命题规则：由原子命题(propositional atom)和逻辑连接词(与$\wedge$、或$\vee$、非$\neg$、蕴含$\leftarrow$)构成的简单称述句，如$规则1:好瓜\leftarrow(根蒂=蜷缩)\wedge(脐部=凹陷)$
- 其中类似$根蒂=蜷缩$的等式中，判断了两个逻辑文字的赋值(valuation)。
一阶规则：由能描述事物的属性或关系的“原子公式”(atomic formula)组成，能表示复杂的关系，也被称为“关系型规则”(relational rule)
- 有表示关系的谓词(predicate)，如$父亲(X,Y)$、$\sigma(X)=X+1$、$自然数(X)$；
- 用于限定变量取值范围的量词(quantifier)，如$\forall$和$\exists$；
- 例子：$规则：好瓜(X)\leftarrow根蒂(X,蜷缩)\wedge脐部(X,凹陷)$
命题规则是一阶规则的特例。

【规则的质量】

规则的质量可以用覆盖率(coverage)和准确率(accuracy)来度量，有数据集$D$和规则$r:A\rightarrow y$
覆盖率：$D$中触发规则$r$的记录所占的比例，$Coverage(r)=|A|/|D|$
准确率：规则$r$触发的记录结果正确的比例，$Accuracy(r)=|A\cup y|/|A|$

2. 规则集

【基本概念】

对一个模型中的各条规则/析取项$r_i$，有规则集$R=(r_1\vee r_2\vee...\vee r_k)$。

【两个重要性质】

规则集具有两个重要的性质，互斥规则和穷举规则（并不一定会满足）。
互斥规则(Mutually Exclusive Rule)：规则集中不存在两条规则被同一条记录触发，则称规则集中的规则是互斥的，其保证每条记录至多被规则集中的一条规则覆盖。
穷举规则(Exhaustive Rule)：对数据集中的任意记录，都存在一条规则加以覆盖，则称规则集有穷举覆盖，其保证每一条记录都至少被规则集中的一条规则覆盖。

【冲突与消解】

若规则集不是互斥的，则一条记录可能被多条规则覆盖，则这些规则的预测结果产生了冲突(conflict)。
解决冲突的方法，被称为冲突消解(conflict resolution)，常用的方法有投票法、排序法、元规则法等。
投票法：将判别结果最多的结果作为最终结果。
- 学习过程是一种无序规则(unordered rule)
- 优：不易受选择不当的规则而产生错误的影响，且建立模型开销相对较小
- 劣：测试记录属性要与每一条规则前件比较，因此使用模型预测时开销大
排序法：在规则集上定义顺序，冲突时选择排序在前的规则。
- 学习过程被称为带序规则(ordered rule)或优先级规则(priority rule)
- 有序的规则集也被称为决策表(decision list)
- 排序可以基于规则，也可以基于类，大部分基于规则的分类器都采用基于类的排序方式
  - 基于规则：根据规则的某种度量进行排序，确保每条记录都是由覆盖它的“最好的规则”来分类，但可能导致规则的秩越低越难理解；
  - 基于类：属于同一个预测结果的规则排序在一起，即按照类进行排序，使规则理解更容易，但可能导致质量较差的规则属于秩较高的类。
元规则法：根据领域知识，实现设定一些元规则(meta-rule)，即规则的规则（如，“发生冲突时使用长度最小的规则”）

【缺省规则】

规则集有可能无法覆盖所有的未见示例
这时，一般会设置一条默认规则(default rule)或缺省规则（如，“未被规则1，2覆盖的都不是好瓜”）。

3. 规则学习

【基本概念】

规则学习(rule learning)：从训练数据中学习出一组能用于对未见示例进行判别的规则。
规则学习的目标：产生一个能覆盖尽可能多的样例的规则集。
规则学习的学习过程：寻找最优的一组逻辑文字来构成规则体，即是一个搜索问题，本质上是一个贪心搜索过程，因而需要缓解过拟合的风险，常见方法即剪枝(pruning)。

【规则提取】

规则提取最直接的做法是序贯覆盖(sequential covering)，即逐条归纳：
- 从训练集中学习一条“好的”规则（覆盖较多正例，没有或少量覆盖负例）；
- 从训练集中删除被此规则覆盖的样例，用剩下的样例重复进行。
- 每次只处理一部分数据，也被称为“分治”(separate-and-conquer)策略。
规则提取也可以采用间接的方法，如由决策树生成规则集，如下图所示（来自《数据挖掘导论》）
- 和决策树一样，可以进行剪枝操作；规则的排序可以使用C4.5规则算法。

【规则产生】

基于穷尽搜索的方法，在属性和候选之较多的时候，可能会导致组合爆炸，因此需要有一种策略来产生规则。一般有两种策略，自顶向下和自底向上。
自顶向下(top-down)
- 从比较一般的规则开始，逐渐添加新的合取项，来缩小规则覆盖范围，直到满足终止条件为止（如增加合取项无法提高规则的质量）。
- 也称为“生成-测试”(generate-then-test)法，规则逐渐“特化”(specialization)。
- 更容易产生泛化性能更好的规则，对噪声的鲁棒性更强。
自底向上(bottom-up)
- 从比较特殊的规则开始，逐渐删除合取项，来扩大规则覆盖范围，直到满足中止条件为止。
- 也称为“数据驱动”(data-driven)法，规则逐渐“泛化”(generalization)。
- 更适合训练样本较少的情况。
在命题规则学习中常用自顶向下策略，在如一阶规则学习这类假设空间非常复杂上则使用自底向上策略更多。
另外，每次合取式增减的数量，如果只有一条，则会过于贪心，容易陷入局部最优，因此可以采用如集束搜索(beam search)的方法来缓和（每轮保留$b$个合取式，下一轮均用于构建候选集）。

【规则评估】

我们通过考虑规则的准确率、覆盖率和属性次序来评估规则增减后的优劣。
另外，也可以使用似然比、FOIL信息增益等来度量合取增减后，规则是否质量更好。
- ${\rm FOIL}信息增益=p_1\times(\log_2\frac{p_1}{p_1+n_1}-\log_2\frac{p_0}{p_0+n_0})$
- 其中，$p$和$n$分别表示正类和负类数。
当然，这里的度量和决策树中有着很多的相似，可以借鉴决策树的评估。

【规则剪枝】

为缓解过拟合的风险，可以使用剪枝方法，既可以后剪枝，也可以预剪枝。
CN2算法：借助统计显著性检验来剪枝，使用似然率统计量(Likelihood Ratio Statics, LRS)来度量
- ${\rm LRS}=2\cdot(\hat m_+\log_2\frac{(\frac{\hat m_+}{\hat m_++\hat m_-})}{(\frac{m_+}{m_++m_-})}+\hat m_-\log_2\frac{(\frac{\hat m_-}{\hat m_++\hat m_-})}{(\frac{m_-}{m_++m_-})})$
REP剪枝(Reduced Error Pruning, 减错剪枝)：分成训练集和验证集，进行多轮剪枝，每轮中穷举剪枝操作，用验证机进行评估，保留最好的规则集进行下一轮剪枝，直到无法再提高性能。
IREP剪枝(Incremental REP)：划分训练集和测试集，训练集上生成一条规则$r$，立即在验证集上进行REP剪枝，得到规则$r'$，将$r'$覆盖的规则去除，重复进行REP剪枝。相比REP的$O(m^4)$的复杂度，IREP的复杂度为$O(m\log^2m)$。
RIPPER算法：以$\frac{\hat m_++(m_--\hat m_-)}{m_++m_-}$取代IREP使用的准确率作为规则性能度量指标，剪枝时删除规则尾部的多个文字，在最终得到规则集之后再进行一次IREP剪枝。
- 替换规则(replacement rule)：基于$r_i$覆盖的样例，用IREP*重新生成一条规则$r_i'$。
- 修订规则(revised rule)：对$r_i$增加文字进行特化，然后通过IREP*剪枝生成一条规则$r_i''$。

【特点与优势】

相比神经网络、支持向量机之类的“黑箱模型”，规则学习具有更好的可解释性，更易理解；
数理逻辑有极强的表达能力，规则学习能更自然地在学习过程中引入领域知识；
逻辑规则具有抽象描述能力，规则学习在处理一些高度复杂的AI任务时具有显著的优势；
很多基于规则的分类器采用的基于类的规则定序方法，适用于处理类分布不平衡的数据集。

4. 一阶规则学习与归纳逻辑程序设计

【一阶规则学习】

命题规则学习难以处理对象之间的关系(relation)，如“瓜1比瓜2颜色更深，所以瓜1比瓜2更好”，因此需要用一阶逻辑表示，使用一阶规则学习。
一阶规则学习能更容易地引入领域知识。
FOIL(First-Order Inductive Learner)是著名的一阶规则学习算法，遵循贯序覆盖框架且采用自顶下下的规则归纳策略，使用FOIL增益(FOIL gain)来选择文字。
- ${\rm FOIL}信息增益=p_1\times(\log_2\frac{p_1}{p_1+n_1}-\log_2\frac{p_0}{p_0+n_0})$
- 仅考虑正例的信息量，并且用新规则覆盖的正例数作为权重，因为关系数据中正例数往往远少于反例数。
- FOIL可大致看作命题规则学习与归纳逻辑程序设计之间的过渡。

【归纳逻辑程序设计】

归纳逻辑程序设计(Inductive Logic Programming, ILP)在一阶规则学习中引入了函数和逻辑表达式嵌套。
- 使机器学习系统具备了更为强大的表达能力，可以看作用机器学习技术来解决基于背景知识的逻辑程序(logic program)归纳，其学得的规则可被PROLOG等逻辑程序设计语言直接使用。
- 另一方面，函数和逻辑表达式嵌套的引入也使计算更为复杂。
最小一般泛化
- 归纳逻辑程序设计采用自底向上的规则生成策略，直接将一个或多个正例对应的具体事实(grounded fact)作为初始规则，在对规则逐步进行泛化增加覆盖率。
- 泛化可以是将规则中的常量替换为逻辑变量，也可以是删除规则体中的某个文字。
- 最小一般泛化(Least General Generalization, LGG)：最基础的特化规则
- RLGG(Relative Least General Generalization)：在计算LGG时考虑所有的背景知识，将初始规则定位$e\leftarrow K$，$K$为背景知识中原子的合取。
逆归结(inverse resolution)：基于背景知识来发明新的概念和关系
- $p\leftarrow q$ 等价于 $p\vee\neg q$
- 四种逆归结操作
  - 吸收(absorption)：$\frac{p\leftarrow A\wedge B\quad q\leftarrow A}{p\leftarrow q\wedge B\quad q\leftarrow A}$
  - 辨识(identifictaion)：$\frac{p\leftarrow A\wedge B\quad p\leftarrow A\wedge q}{q\leftarrow B\quad p\leftarrow A\wedge q}$
  - 内构(intra-construction)：$\frac{p\leftarrow A\wedge B\quad p\leftarrow A\wedge C}{q\leftarrow B\quad p\leftarrow A\wedge q\quad q\leftarrow C}$
  - 互构(inter-construction)：$\frac{p\leftarrow A\wedge B\quad q\leftarrow A\wedge C}{p\leftarrow r\wedge B\quad r\leftarrow A\quad q\leftarrow r\wedge C}$
- 置换(substitution)：用某些项来替换逻辑表达式中的变量
- 合一(unification)：用一种变量置换令两个或多个逻辑表达式相等
- 逆归结的一大特点是能自动发明新谓词。