【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.基本概念
机器学习中的“规则”（rule）通常是指语义明确、能描述数据分布所隐含的客观规律或领域概念、可写成“若$\cdots \cdots$，则$\cdots \cdots$”形式的逻辑规则。“规则学习”（rule learning）是从训练数据中学习出一组能用于对未见示例进行判别的规则。
所有预测模型在广义上都可称为一个或一组“规则”，但规则学习中的“规则”是狭义的，事实上约定俗成地省略了“逻辑”二字。
形式化地看，一条规则形如：
\[\oplus \leftarrow \mathbf{f}_1 \land \mathbf{f}_2 \land \cdots \land \mathbf{f}_L \tag{1}\]其中逻辑蕴含符号“$\leftarrow$”右边部分称为“规则体”（body），表示该条规则的前提，左边部分称为“规则头”（head），表示该条规则的结果。规则体是由逻辑文字（literal）$\mathbf{f}_k$组成的合取式（conjunction），其中合取符号“$\land$”用来表示“并且”。每个文字$\mathbf{f}_k$都是对示例属性进行检验的布尔表达式，例如“（色泽=乌黑）”或“$\neg$（根蒂=硬挺）”。$L$是规则体中逻辑文字的个数，称为规则的长度。规则头的“$\oplus$”同样是逻辑文字，一般用来表示规则所判定的目标类型或概念，例如“好瓜”。这样的逻辑规则也被称为“if-then规则”。
在数理逻辑中“文字”专指原子公式（atom）及其否定。
与神经网络、支持向量机这样的“黑箱模型”相比，规则学习具有更好的可解释性，能使用户更直观地对判别过程有所了解。另一方面，数理逻辑具有极强的表达能力，绝大多数人类知识都能通过数理逻辑进行简洁的刻画和表达。例如“父亲的父亲是爷爷”这样的知识不易用函数式描述，而用一阶逻辑则可方便地写为“爷爷$(X,Y) \leftarrow$父亲$(X,Z)\land$父亲$(Z,Y)$”，因此，规则学习能更自然地在学习过程中引入领域知识。此外，逻辑规则的抽象描述能力在处理一些高度复杂的AI任务时具有显著的优势，例如在问答系统中有时可能遇到非常多、甚至无穷种可能的答案，此时若能基于逻辑规则进行抽象表述或者推理，则将带来极大的便利。
假定我们从西瓜数据集学得规则集合$\mathcal{R}$：
- 规则1：好瓜 $\leftarrow$ (根蒂=蜷缩) $\land$ (脐部=凹陷)
- 规则2：$\neg$ 好瓜 $\leftarrow$ (纹理=模糊)
规则1的长度为2，它通过判断两个逻辑文字的赋值来对示例进行判别。符合该规则的样本称为被该规则“覆盖”。需注意的是，被规则1覆盖的样本是好瓜，但没被规则1覆盖的未必不是好瓜；只有被规则2这样以“$\neg$好瓜”为头的规则覆盖的才不是好瓜。
显然，规则集合中的每条规则都可看作一个子模型，规则集合是这些子模型的一个集成。当同一个示例被判别结果不同的多条规则覆盖时，称发生了“冲突”（conflict），解决冲突的办法称为“冲突消解”（conflict resolution）。常用的冲突消解策略有投票法、排序法、元规则法等。投票法是将判别相同的规则数最多的结果作为最终结果。排序法是在规则集合上定义一个顺序，在发生冲突时使用排序最前的规则；相应的规则学习过程称为“带序规则”（ordered rule）学习或“优先级规则”（priority rule）学习。元规则法是根据领域知识事先设定一些“元规则”（meta-rule），即关于规则的规则，例如“发生冲突时使用长度最小的规则”，然后根据元规则的指导来使用规则集。
此外，从训练集学得的规则集合也许不能覆盖所有可能的未见示例，例如前述规则集合$\mathcal{R}$无法对“根蒂=蜷缩”、“脐部=稍凹”且“纹理=清晰”的示例进行判别；这种情况在属性数目很多时常出现。因此，规则学习算法通常会设置一条“默认规则”（default rule），由它来处理规则集合未覆盖的样本；例如为$\mathcal{R}$增加一条默认规则：“未被规则1，2覆盖的都不是好瓜”。
亦称“缺省规则”，可认为是一种特殊的元规则。
从形式语言表达能力而言，规则可分为两类：“命题规则”（propositional rule）和“一阶规则”（first-order rule）。前者是由“原子命题”（propositional atom）和逻辑连接词“与”（$\land$）、“或”（$\lor$）、“非”（$\neg$）和“蕴含”（$\leftarrow$）构成的简单陈述句；例如规则集$\mathcal{R}$就是一个命题规则集，“根蒂=蜷缩”“脐部=凹陷”都是原子命题。后者的基本成分是能描述事物的属性或关系的“原子公式”（atomic formula），例如表达父子关系的谓词（predicate）“父亲$(X,Y)$”就是原子公式，再如表示加一操作“$\sigma(X)=X+1$”的函数“$\sigma(X)$”也是原子公式。如果进一步用谓词“自然数$(X)$”表示$X$是自然数，“$\forall X$”表示“对于任意$X$成立”，“$\exists Y$”表示“存在$Y$使之成立”，那么“所有自然数加1都是自然数”就可写作$\forall X \exists Y(自然数(Y)\leftarrow自然数(X)\land (Y = \sigma (X)))$，或更简洁的“$\forall X (自然数(\sigma (X)) \leftarrow 自然数(X))$”。这样的规则就是一阶规则，其中$X$和$Y$称为逻辑变量，“$\forall$”“$\exists$”分别表示“任意”和“存在”，用于限定变量的取值范围，称为“量词”（quantifier）。显然，一阶规则能表达复杂的关系，因此也被称为“关系型规则”（relational rule）。以西瓜数据为例，若我们简单地把属性当作谓词来定义示例与属性值之间的关系，则命题规则集$\mathcal{R}$可改写为一阶规则集$\mathcal{R}’$：
- 规则1：$好瓜(X) \leftarrow 根蒂(X,蜷缩) \land 脐部(X,凹陷)$
- 规则2：$\neg 好瓜(X) \leftarrow 纹理(X,模糊)$
显然，从形式语言系统的角度来看，命题规则是一阶规则的特例，因此一阶规则的学习比命题规则要复杂得多。
