规则学习

第15章 规则学习

• Page347: 规则（rule）

  机器学习中的 “规则” 通常是指语义明确、能描述数据分布所隐含的客观规律或领域的概念、可写成 “若……，则……” 形式的逻辑规则。

• Page347: 规则学习（rule learning）

  规则学习是从训练数据中学习出一组能用于对未见示例进行判别的规则。

• Page347: 逻辑文字（literal）

  在数理逻辑中，“文字” 专指原子公式（atom）及其否定。

• Page348: 冲突消解（conflict resolution）

  规则集合是每条规则的的集成，当同一个示例被判别结果不同的多条规则覆盖时，称发生了 “冲突”（conflict），解决冲突的办法称为 “冲突消解”（conflict resolution）。常用的策略有投票法、排序法、元规则法等。

• Page348: 带序规则（ordered rule）

  排序法消解冲突时会在规则集合上定义一个顺序，在发生冲突时使用排序最前的规则；相应的规则学习过程称为 “带序规则”（ordered rule）学习或 “优先级规则”（priority rule）学习。

• Page348: 优先级规则（priority rule）

  同 “带序规则”

• Page348: 元规则（meta-rule）

  关于规则的规则。

• Page348: 默认规则（default rule）

  规则学习算法通常会设置一条 “默认规则”（default rule）来处理规则集合未覆盖的样本。

• Page348: 缺省规则

  同 “默认规则”，可认为是一种特殊的元规则。

• Page348: 命题规则（propositional rule）

  由 “原子命题”（propositional atom）和逻辑连接词 “与”（∧）、“或”（∨）、“非”（￢）和 “蕴含”（←）构成的简单陈述句。

• Page348: 原子命题

  最基本的命题，不含逻辑连接词的逻辑文字。

• Page348: 一阶规则

  也被称为 “关系型规则”（relational rule），基本成分是能描述事物的属性或关系的 “原子公式”（atomic formula），例如表达父子关系的谓词（predicate）“父亲（X,Y）” 就是原子公式。 如果进一步用谓词 “自然数（X)” 表示 X 是自然数，那么 “所有自然数加 1 都是自然数” 就可写作 “∀X∃Y（自然数(Y) ← 自然数(X)∧(Y=δ(X)）”，或更简洁的 “∀X(自然数(δ(X)) ← 自然数(X))”。这样的规则就是一阶规则。其中 X 和 Y 称为逻辑变量，“∀” “∃” 分别表示 “任意” 和 “存在”，用于限定变量的取值范围，称为 “量词”（quantifier）。 从形式语言系统的角度看，命题规则是一阶规则的特例。

• Page349: 序贯覆盖（sequential covering）

  规则学习的目标是产生一个能覆盖尽可能多的样例的规则集。最直接的做法是 “序贯覆盖”（sequential covering），即逐条归纳：在训练集上每学到一条规则，就将该规则覆盖的训练样例去除，然后以剩下的训练样例组成训练集重复上述过程。 由于每次只处理一部分数据，因此也被称为 “分治”（separate-and-conquer）策略。

• Page350: 特化（specialization）

  使用序贯覆盖法时，在属性和候选值较多时会由于组合爆炸而不可行。现实任务中一般有两种策略来产生规则。其中一种是 “自顶向下”（top-down），即从比较一般的规则开始，逐渐添加新文字以缩小规则覆盖范围，直到满足预定条件为止；亦称为 “生成-测试”（generate-then-test）法，这个过程就是规则逐渐 “特化”（specialization）的过程。这种方法通常更容易产生泛化性能较好的规则，也是通常使用的一种策略。

• Page350: 泛化（generalization）

  另一种产生策略的规则是 “自底向上”（bottom-up），即从比较特殊的规则开始，逐渐删除文字以扩大规则覆盖范围，直到满足条件为止；亦称为 “数据驱动”（data-driven）法，这个过程就是规则逐渐 “泛化”（generalization）的过程。适用于训练样本较少的情形；通常在一阶规则学习这类假设空间非常复杂的任务上使用较多。

• Page352: 似然率（Likelihood Ratio Statistics，LRS）

  用于在已知某些观测数据时，对其参数进行估计，是关于模型参数的函数。在规则学习中，它衡量了规则（集）覆盖样例的分布与训练集经验分布的差别。LRS 越大，说明采用规则（集）进行预测与直接使用训练集正、反例比率进行猜测的差别越大；LRS 越小，说明规则（集）的效果越可能仅是偶然现象。

• Page353: RIPPER（Repeated Incremental Pruning to Produce Error Reduction）

  一种著名的规则学习算法，它首先使用 IREP* 剪枝机制生成规则集 $\mathcal{R}$，对 $\mathcal{R}$ 中的每条规则 $r_i$ 产生两个变体：

  • $r'_i$: 基于 $r_i$ 覆盖的样例，用 IREP* 重新生成一条规则 $r'_i$，该规则称为替换规则（replacement rule）；

  • $r''_i$: 基于 $r_i$ 增加文字进行特化，然后再用 IREP* 剪枝生成一条规则 $r''_i$，该规则称为修订规则（revised rule）。

  接下来，把 $r'_i$ 和 $r''_i$ 分别与 $\mathcal{R}$ 中除 $r_i$ 之外的规则放在一起，组成规则集 $\mathcal{R'}$ 和 $\mathcal{R''}$，将它们与 $\mathcal{R}$ 一起进行比较，选择最优的规则集保留下来。 RIPPER 将 $\mathcal{R}$ 中的所有规则放在一起重新加以优化，避免了最初按序生成时，每条规则没有对其后产生的规则加以考虑常常导致算法陷入局部最优的问题。

• Page357: ILP(364)（Inductive Logic Programming，归纳逻辑程序设计）

  归纳逻辑程序设计在一阶规则学习中引入了函数和逻辑表达式嵌套。一方面，这使得机器学习系统具备了更为强大的表达能力；另一方面 ILP 可看作用机器学习技术来解决基于背景知识的逻辑程序（logic program）归纳，其学得的 “规则” 可被 PROLOG 等逻辑程序设计语言直接使用。

• Page357: 归纳逻辑程序设计(364)

  同 ILP。

• Page358: 最小一般泛化（Least General Generalization）

  自底向上的规则生成策略中，将 “特殊” 规则转变为更 “一般” 规则的技术叫 “最小一般泛化”（Least General Generalization，简称 LGG）。 给定一阶公式 r1 和 r2，LGG 先找出涉及相同谓词的文字，然后对文字中每个位置的常量逐一进行考察，若常量在两个文字中相同则保持不变，记为 LGG(t,t)=t；否则将他们替换为同一个新变量，并将该替换应用于公式的所有其他位置：假定这两个不同的常量分别为 s,t，新变量为 V，则记为 LGG(s,t) = V，并在以后所有出现 LGG(s,t) 的位置用 V 来代替。

• Page359: 归纳（induction）

  归纳是从个别事物出发概括出一般规律性。机器学习属于归纳的范畴。

• Page359: 逆归结

  假设两个逻辑表达式 C1 和 C2 成立，且分别包含了互补项 L1 与 L2；不失一般性，令 L = L1 = ￢L2，C1 = A ∨ L，C2 = B ∨ ￢L。归结原理是通过演绎推理消去 L 而得到 “归结项” C = A ∨ B。 而逆归结与上面过程相反，它研究的是在已知 C 和某个 Ci 的情况下如何得到 Cj。 基于逆归结，我们可基于背景知识来发明新的概念和关系。 在逻辑推理实践中，有四种完备的逆归结操作：吸收（absorption）、辨识（identification）、内构（intra-construction）、互构（inter-construction）。

• Page359: 演绎（deduction）

  演绎是从一般性规律出发来探讨具体事物。

• Page361: 置换（substitution）

  置换（substitution）是用某些项来替换逻辑表达式中的变量。

• Page361: 合一（unification）

  合一（unification）是用一种变量置换令两个或多个逻辑表达式相等。

• Page361: 最一般合一置换（most general unifer，简称 MGU)

  若 δ 是一组一阶逻辑表达式 W 的合一化子，且对 W 的任意合一化子 θ 均存在相应的置换 λ 使 θ = δ o λ，则称 δ 为 W 的 “最一般合一置换” 或 “最一般合一化子”。

• Page362: 归结商（resolution quotient）

  逆归结中，已知 C 和某个 Ci，则 Cj = C/Ci 称为 “归结商”。

• Page363: 关系学习

  关系学习是指学习对概念的网络式描述。

• Page364: 统计关系学习（statistical relational learning）

  将关系学习与统计学习相结合，如概率归纳逻辑程序设计、概率关系模型、贝叶斯逻辑程序、马尔科夫逻辑网等统称为 “统计关系学习”。