规则学习
原理
15.1 基本概念
- 机器学习中的“规则”(rule)通常是指语义明确、能描述数据分布所隐含的客观规律或领域概念、可写成“若……，则……”形式的规则逻辑。“规则学习”(rule learning)是从训练数据中学习出一组能用于对未见示例进行判别的规则。
- 与神经网络、支持向量机这样的“黑箱模型”相比，规则学习具有更好的可解释性，能使用户更直观地对判别过程有所了解。另一方面，数理逻辑具有极强的表达能力，绝大多数人类知识都能通过梳理逻辑进行简洁的刻画和表达。例如“父亲的父亲是爷爷”这样的知识不易用函数式描述，而用一阶逻辑可以方便地描述。因此，规则学习能更自然地在学习过程中引入领域知识。此外，逻辑规则的抽象描述能力在处理一些高度复杂的AI任务时具有显著的优势，例如在问答系统中有时可能遇到非常多、甚至无穷种可能的答案，此时若能基于逻辑规则进行抽象表述或者推理，则将带来极大的便利。
- 规则集合中的每条规则都可看作一个子模型，规则集合是这些子模型的一个集成。当同一个示例被判别结果不同的多条规则覆盖时，称发生了“冲突”(conflict)，解决冲突的办法称为“冲突消解”(conflict resolution)。常用的冲突消解策略有投票法、排序法、元规则法等。投票法是将判别相同的规则数最多的结果作为最终结果。排序法是在规则集合上定义一个顺序，在发生冲突时使用排序最前的规则；相应的规则学习过程称为“带序规则”(ordered rule)学习或“优先级规则”(priority rule)学习。元规则法是根据领域知识事先设定一些“元规则”(meta-rule)，即关于规则的规则，例如“发生冲突时使用长度最小的规则”，然后根据元规则的知道来使用规则集。
- 此外，从训练集学得的规则集合也许不能覆盖所有可能的未见示例。这种情况在属性数目很多时常出现。因此，规则学习算法通常会设置一条“默认规则”(default rule)，由它来处理规则集合未覆盖的样本；例如为 R 增加一条默认规则：“未被规则1,2覆盖的都不是好挂”。
- 从形式语言表达能力而言，规则可分为两类：“命题规则”(propositional rule)和“一阶规则”(first-order rule)。前者是由“原子命题”(propositional atom)和逻辑连接词“与”、“或”、“非”和“蕴含”(←)构成的简单陈述句；
- “一阶规则”的基本成分是能描述事物的属性或关系的“原子公式”(atomic formula)。从形式语言系统的角度看，命题规则是一阶规则的特例，因此一阶规则的学习比命题规则复杂得多。
15.2 序贯覆盖
- 规则学习的目标是产生一个能覆盖尽可能多的样例的规则集。最直接的做法是“序贯覆盖”(sequential covering)，即逐条归纳：在训练集上每学到一条规则，就将该规则覆盖的训练样例去除，然后以剩下的训练样例组成训练集重复上述过程。由于每次只处理一部分数据，因此也被称为“分治”(separate-and-conquer)策略。
- 基于穷尽搜索的做法在属性和候选值较多时会由于组合爆炸而不可行。现实任务中一般有两种策略来产生规则：第一种是“自顶向下”(top-down)，即从比较一般的规则开始，逐渐添加新文字以缩小规则覆盖范围，直到满足预定条件为止；亦称为“生成-测试”(generate-then-test)法，是规则逐渐“特化”(specialization)的过程。第二种策略是“自底向上”(bottom-up)，即从比较特殊的规则开始，逐渐删除文字以扩大规则覆盖范围，直到满足条件为止；亦称为“数据驱动”(data-driven)法，是规则逐渐“泛化”(generalization)的过程。第一种策略是覆盖范围从大往小搜索规则，第二种策略则相反；前者通常更容易产生泛化性能较好的规则，而后者则更适合于训练样本较少的情形，此外，前者对噪声的鲁棒性比后者要强得多。因此，在命题规则学习中通常使用一种策略，而第二种策略在一阶规则学习这类假设空间非常复杂的任务上使用较多。
15.3 剪枝优化
- 规则生成本质上是一个贪心搜索过程，需有一定的机制来缓解过拟合的风险，最常见的做法是剪枝(pruning)。与决策树相似，剪枝可发生在规则生长过程中，即“预剪枝”，也可以发生在规则产生后，即“后剪枝”。通常是基于某种性能度量指标来评估增/删逻辑文字前后的规则性能，或增/删规则前后的规则集性能，从而判断是否要进行剪枝。
15.4 一阶规则学习
- 受限于命题逻辑表达能力，命题规则学习难以处理对象之间的“关系”(relation)，而关系信息在很多任务中非常重要。例如颜色更深，触感更硬。
- 一阶规则学习能容易地引入领域知识，这是它相对于命题规则学习的另一大优势。在命题规则学习乃至一般的统计学习中，若欲引入领域知识，通常由两种做法：在现有属性的基础上基于领域知识构造出新属性，或基于领域知识设计某种函数机制(例如正则化)来对假设空间加以约束。
- FOIL(First-Order Inductive Learner) 是著名的一阶规则学习算法，它遵循序贯覆盖框架且采用自顶向下的规则归纳策略。
15.5 归纳逻辑程序设计
- 归纳逻辑程序设计 (Inductive Logic Programming, ILP) 在一阶规则学习中引入了函数和逻辑表达式嵌套。一方面，这使得机器学习系统具备了更为强大的表达能力；另一方面，ILP 可看作用机器学习技术来解决基于背景知识的逻辑程序 (Logic program) 归纳，其学得的“规则”可被 PROLOG 等逻辑程序设计语言直接使用。
