第15章：规则学习 — 西瓜书学习笔记

本文是周志华《机器学习》（西瓜书）第15章 规则学习（Rule Learning）的学习笔记，涵盖本章所有核心知识点，配有通俗类比与公式推导。

①. 基本概念与”规则”的形式

命题规则 vs. 一阶规则，规则集与规则列表

📋 生活类比：医学诊断手册

医生看病的经验，最自然的表达就是”规则”——“如果发烧+咳嗽+白细胞升高，则很可能是细菌感染”。一条规则覆盖一类病例，不需要算概率，不需要调参数，看一眼就懂。规则学习的目标就是从数据中自动挖掘这样的诊断规则。

📜 规则的基本形式

规则的一般形式为：

📐 命题规则（Propositional Rule）

$$\textbf{IF}\;(f_1 \in V_1) \land (f_2 \in V_2) \land \cdots \land (f_k \in V_k)\;\textbf{THEN}\; c$$

规则体（body）是属性-值检验的合取，头部（head）是一个类别标签。

规则集（Rule Set）

一组无序的规则，每个样本被匹配的规则投票决定类别。冲突时可用优先级解决。

规则列表（Rule List）

规则按顺序排列，第一个匹配的规则决定结果。若都无法匹配，使用默认规则（default rule）。

🔑 核心评估指标

指标	定义	直觉
覆盖率（Coverage）	规则体为真的样本中，头部类别正确的比例	这条规则”准不准”？
准确率（Accuracy）	$|\{\text{正确分类}\}| / |\{\text{覆盖样本}\}|$	命中率
信息增益（FOIL Gain）	加入新文字后，正例覆盖量的对数增量	新条件”有没有用”？

②. 序贯覆盖（Sequential Covering）

逐条学习，覆盖一批就划掉一批

🎯 生活类比：一块块地”吃”数据

规则学习不像决策树那样一次性划分样本空间，而是像玩贪吃蛇：每次学一条最好的规则，覆盖到的样本就”吃掉”（从训练集中移除），然后对着剩下的样本再学下一条。直到所有样本都被覆盖，或剩下的都是”噪音”。

Algorithm: 序贯覆盖框架
输入: 训练集 D，评估函数 E
R ← ∅ // 规则集

while D 中还有未被覆盖的目标类样本:
r ← LearnOneRule(D, E) // 学习一条最优规则
if r 的质量低于阈值: break
R ← R ∪ {r}
从 D 中移除被 r 覆盖的样本

return R

🌿 单条规则生成 — 从一般到特殊

初始规则体为空 $\emptyset$（匹配所有样本），然后逐步**添加文字（literal）**使其更”特殊”，直到覆盖的样本质量足够高：

📐 自顶向下搜索（Top-Down / 一般→特殊）

$$\emptyset \;\xrightarrow{+f_1=v_1}\; (f_1=v_1) \;\xrightarrow{+f_2=v_2}\; (f_1=v_1)\land(f_2=v_2) \;\longrightarrow\; \cdots$$

🔽 自顶向下（多数算法）

从空规则出发，贪心地添加文字。每次加文字时，评估所有可能的候选文字，选择使规则质量提升最大的。典型算法：CN2、RIPPER。

🔼 自底向上

从某个正例出发生成最特殊的规则，再逐步删除文字（泛化）。如 AQ 系列算法。较少单独使用，通常结合剪枝。

③. 剪枝优化

防止过拟合：删除冗余文字和整条规则

✂️ 预剪枝 vs. 后剪枝

在规则生成过程中提前停止。当加入新文字后，验证集上的性能不再提升时，停止继续添加文字。

优点：加速生成；缺点：可能过早停止

🔧 后剪枝（Post-pruning）

先生成完整的规则，再用**缩减误差剪枝（REP）**等技术逐步删除末尾的文字，检查验证集性能是否提升。

优点：更精准；缺点：先要生成完整规则

RIPPER 的剪枝策略（k 折交叉验证）

RIPPER 算法使用增长集（growing set）生成规则，用剪枝集（pruning set）后剪枝。剪枝时计算每个文字的剪枝度量 $v$：

📐 剪枝度量（RIPPER）

$$v(r, D) = \frac{p + (N - n)}{P + N}$$

其中 $p$=剪枝后规则命中正例数，$n$=剪枝后命中负例数，$P,N$=剪枝集上总正/负例数。

直觉：删除冗余文字后，若度量值上升就剪掉。

④. 一阶规则学习

从命题到一阶：引入变量和关系

🎓 从”属性”到”关系”

命题规则：IF 身高>180 AND 体重>80 THEN 类别=篮球 ← 只能处理固定属性。一阶规则：IF Father(X, Y) AND Father(Y, Z) THEN Grandfather(X, Z) ← 引入变量和谓词，能表达关系！

🌐 FOIL 算法（First-Order Inductive Learner）

FOIL 是一阶序贯覆盖的代表算法，每条规则按 FOIL 信息增益选择文字：

📐 FOIL 信息增益

$$\text{FoilGain} = |\hat{P}| \cdot \left( \log_2 \frac{|\hat{P}|}{|\hat{P}|+|\hat{N}|} - \log_2 \frac{|P|}{|P|+|N|} \right)$$

其中 $P,N$ 是加入文字前覆盖的正/负例数，$\hat{P},\hat{N}$ 是加入后。直观理解：新文字让正例更集中了吗？

💡 一阶文字的类型

FOIL 可添加以下类型的新文字到规则中：

1. 已有变量的谓词：用规则中已有的变量组合描述关系（如 Parents(X,Y)）
2. 引入新变量：用谓词引入新变量（如 Father(X,Z)，其中 Z 是新变量）
3. 常量赋值：将变量绑定到特定常量

⚠️ 组合爆炸：一阶规则的搜索代价

一阶空间的搜索比命题空间大得多——不仅有属性值组合，还有变量绑定的各种排列。实践中需要强剪枝和启发式排序来控制复杂度。

⑤. 归纳逻辑程序设计（ILP）

在背景知识上做归纳——从经验中学逻辑程序

🧬 ILP 的基本框架

ILP 不仅要利用训练样例，还要利用背景知识（BK）。目标是从 BK + 样例中归纳出一阶规则：

📐 ILP 问题形式化

$$\text{BK} \land H \models E^+ \quad \text{且} \quad \text{BK} \land H \not\models E^-$$

其中 BK = 背景知识，H = 待学习的规则（目标谓词），$E^+$ = 正例，$E^-$ = 负例。要求：BK+H 蕴含所有正例，且不蕴含任何负例。

θ-包容（θ-subsumption）

子句 $C$ θ-包容 $D$，若存在替换 θ 使 $C\theta \subseteq D$。这是 ILP 中判断覆盖关系的核心工具。

最小一般泛化（LGG）

两个子句的最小一般泛化（least general generalization），是它们最”紧”的共同泛化。ILP 中的理论工具。

🔄 逆蕴含（Inverse Entailment） — Progol 算法核心

普通的归纳是从”特殊”推”一般”。Progol 反过来：从一个正例 $e$ 出发，在模式声明（mode declaration）的约束下，反推出可能的最一般规则 $H$ 使得 $\text{BK} \land H \models e$。这大大缩小了搜索空间。

⑥. 方法对比与总结

从命题到一阶，从简单到强大

维度	命题规则	一阶规则 (FOIL)	ILP (Progol)
表达能力	属性-值检验	变量 + 谓词 + 关系	变量 + 谓词 + 背景知识
搜索空间	小	大	非常大（但有模式约束）
可解释性	极高（人一眼看懂）	高（类自然语言）	中高（有逻辑符号）
典型算法	CN2、RIPPER	FOIL	Progol、Aleph
适用场景	表格数据、医疗	关系数据库、分子结构	科学发现、知识图谱补全
组合爆炸风险	低	中	高（需强约束）

📝 规则学习 vs. 决策树

对比维度	规则学习	决策树
表示方式	IF-THEN 规则集	树形结构
覆盖策略	逐条序贯覆盖	一次性递归划分
可独立解释	每条规则可独立理解	需要整棵树一起看
知识修改	增删单条规则轻松	修改节点影响子树
可转写	决策树可转规则 (C4.5Rules)	规则不可逆向转为树

🧠 本章一句话总结

规则学习的精髓在于**”从特殊到一般”的搜索范式。命题规则简单高效，一阶规则引入了变量与关系，ILP 更进一步在背景知识上做归纳。三者共享”序贯覆盖 + 精化搜索”的框架，只是表达的语言的复杂度**逐级提升——语言越强，搜索空间越大，需要用更精巧的剪枝和约束来控制。