首先讲一个有意思的现象，早期的主流人工智能专注于以逻辑为基础来进行形式化和推理，但这样很难定量地对不确定事件进行表达和处理，后来随着机器学习算法的井喷，大家都更加关注于对定量的数据进行处理。但现在，很多人发现在解决某些任务的时候，加入一些行业中的常识知识可能会让任务解决地更好，而现在定性知识与定量数据之间似乎有着一道鸿沟，唯一的联系就是进行算法设计的人可能会依赖于他的领域知识来选择合适的算法并对算法进行调参。基于学习下定性知识如何表达的想法，这部分介绍下周志华老师🍉书的倒数第二章——规则学习，这部分内容安扎以下结构组织:
- 基本概念
- 序贯覆盖
- 剪枝优化
- 一阶规则学习
- 归纳逻辑程序设计
基本概念
首先给出机器学习中规则和规则学习的概念：
规则: 在机器学习领域中，“规则”通常是指语义明确、能描述数据分布所隐含的客观规律或领域概念，可以写成”若….,则….”形式的逻辑规则。
规则学习: “规则学习”是从训练数据中学习出一组能用于对未见示例进行判别的规则。
形式化来看，一条规则形如：
公式中$\leftarrow$右侧部分称为”规则体”，表示该条规则的前提，左边部分称为”规则头”,表示该条规则的结果。规则体是由逻辑文字$f_k$所组成的合取式(conjuction)，每个文字$f_k$都是对示例属性进行检验的布尔表达式，例如”(色泽 = 乌黑)”或者”$\neg$(根蒂 = 硬挺)”。$L$是规则体中逻辑文字的个数,称为规则的长度,规则头的”$\oplus$”,同样是逻辑文字，一般用来表示所判定的目标的类别或概念，比如”好瓜”，这样的逻辑规则也被称为if-then规则。
与神经网络、支持向量机这样的”黑箱模型”相比，规则学习具有以下几个优点:
- 可解释性较强
- 很强的表达能力，绝大多数的人类知识都能够通过数理逻辑进行简洁的刻画和表达，例如”父亲的父亲是爷爷”这样的知识不易用函数式表达，而用一阶逻辑则可以方便地写为：
- 逻辑规则的抽象描述能力在处理一些高度复杂的AI任务时具有显著的优势，例如在问答系统中有时可能遇到非常多、甚至无穷种可能的答案，此时若能基于逻辑规则进行抽象表述或者推理，则将带来极大的便利。
假设我们从西瓜数据集中学得规则集合$\mathcal{R}$:
规则集合中的每条规则都可看作一个子模型，规则集合是这些子模型的一个集成。当同一个示例被判别结果不同的多条规则覆盖时，则称发生了“冲突”，解决冲突的办法则称为”冲突消解”，常用的冲突消解的方法有投票法、排序法、元规则法，投票法就是常用的少数服从多数策略，排序法则是指定规则优先级，出现冲突时使用排序靠前的规则。所谓元规则，其实就是规则的规则，例如”发生冲突时使用长度最小的规则“，然后根据元规则的指导来使用规则集。
此外，从训练集学得的规则集合也许并不能覆盖所有可能的未见示例，此时规则学习算法通常会设置一条默认规则，由它来处理规则集合未覆盖的样本；例如为$\mathcal{R}$增加一条默认规则：“未被规则1,2覆盖的都不是好瓜”。
从形式语言表达能力而言，规则可分为两类：“命题规则”和“一阶规则”：
- 命题规则是由“原子命题(propositional atom)”和逻辑连接词“与($\land$)”、”(或($\lor$))”、“非($\neg$)”和“蕴含”($\leftarrow$)构成的简单陈述句；例如规则集$\mathcal{R}$就是一个命题规则集，”根蒂 = 蜷缩”，“脐部 = 凹陷”都是元子命题。
- 一阶规则的基本成分是能表述事物的属性或关系的”原子公式”，例如表达父子关系的谓词(predict)“父亲$(X,Y)$”就是原子公式，再如表示加1操作”$\sigma(X) = X+1$”的函数$\sigma(X)$也是原子公式。如果进一步使用谓词“自然数$(X)$”表示$X$是自然数，“$\forall X$”表示对任意$X$成立，”$\exists Y$”表示”存在$Y$使之成立”,那么”所有自然数加1都是自然数”就可以写做:或者表示成更加简洁的形式:这样的规则就是一阶规则，其中$X$和$Y$称为逻辑变量，$\forall,\exists$用于限定变量的取值范围，称为”量词”，显然，一阶规则可以表达复杂的关系，因此也被称为“关系型规则”。若我们简单地把属性当作谓词来定义示例与属性值之间的关系，则命题规则集$\mathcal{R}$可以改写为一阶规则集$R’$:从形式语言系统角度来看，命题规则是一阶规则的特例，因此一阶规则的学习比命题规则要复杂得多。
序贯覆盖
规则学习的目标是产生一个可以覆盖尽可能多样例的规则集，最直接的做法就是“序贯覆盖”，即逐条归纳:在训练集上每学到一条规则，就将该规则覆盖的训练样例去除，然后以剩下的训练样例组成训练集重复上述过程。由于每次只处理一部分数据，因此也被称为”分治”策略。
序贯覆盖法的关键是如何从训练集学出单条规则，显然，对规则学习目标$\oplus$ 产生一条规则就是寻找最优的一组逻辑文字构成规则体，这是一个搜索问题。形式化上来说，给定正例集合与反例集合，学习任务是基于候选文字集合$\mathcal{F} = { fk }$来生成最优规则$r$。在命题规则学习中，候选文字是形如”$R(属性_i,属性值{ij})$”的布尔表达式，$R(x,y)$则是判断$x,y$是否满足关系$R$的二元布尔函数。
而具体的学习方法则是从空规则$”\oplus \leftarrow”$开始，将正例类别作为规则头，再逐个遍历训练集中的每个属性及取值，尝试将其作为逻辑文字增加到规则体中，若能使当前规则体仅覆盖正例，由此产生一条规则，然后去除已被覆盖的正例并基于剩余样本生成下一个规则：通俗来说，这种方法的思想便是挑选出所有仅覆盖正例的特征和仅覆盖反例的特征。
而原始的穷尽搜索的做法在属性和候选值较多时会由于组合爆炸而不可行,现实任务中一般有两种策略来产生规则:
- 自顶向下:从比较一般的规则开始，逐渐添加新文字以缩小规则覆盖范围，直到满足预定条件为止，该策略也称为“生成测试”法，是规则逐渐特化的过程。
- 自底向上:从比较特殊的规则开始,逐渐删除文字以扩大规则覆盖范围，直到满足条件为止，该种策略是规则逐渐泛化的过程。
剪枝优化
规则生成本质上是一个贪心搜索的过程，需有一定的机制来缓解过拟合的风险，最常见的做法是剪枝。与决策树相似，剪枝可以分为预剪枝与后剪枝。在实际操作时通常是基于某种性能度量指标来评估增/删逻辑文字前后的规则性能，或增/删规则集前后的规则集性能，从而判断是否需要进行剪枝。
经常使用的预剪枝算法为$CN2$算法，使用似然率统计量作为指标；后剪枝常用策略为“减错剪枝”，即将样例集进行划分，划分为训练集和验证集，根据在验证集上的表现优劣来对从训练集中学出的模型进行剪枝。、
一阶规则学习
命题逻辑的基本单元是“原子命题”，这也就导致命题规则学习很难处理对象之间的”关系”，而关系信息在很多任务中非常重要。例如，当我们在瓜摊挑瓜时,通常很难把水果摊上所有西瓜的特征用属性值表示出来，因为我们很难判断:色泽看起来多深才叫”色泽青绿”？敲起来声音多低才叫”敲声沉闷”？比较现实的做法是将西瓜进行比较，例如，”瓜1的颜色比瓜2更深，并且瓜1的根蒂比瓜2更蜷”，因此“瓜1比瓜2更好”。然而，这已经超越了命题逻辑的表达能力，需要用一阶逻辑来表达，并且要使用一阶规则进行学习。
首先我们需要将命题逻辑数据转换为关系数据，比如对于瓜的色泽，我们可以定义:
那么“瓜1色泽乌黑，是好瓜；瓜2色泽青绿，不是好瓜”，就可以表示为:
这样的数据直接描述了样例之间的关系，称为“关系数据”，其中由原样本属性转化而来的“色泽更深”、“根蒂更蜷”等原子公式称为“背景知识”，而由样本类别转化而来的关于“更好”，“$\neg$更好”等原子数据称为关系数据样例，下面给出一个一阶规则示例：
与命题规则相比，一阶规则的规则头、规则体都是一阶逻辑表达式，个体对象”瓜1，瓜2”被逻辑变量$X,Y$替换，全称量词$\forall$ 表示该规则对所有个体对象均成立；通常，在一阶规则中所有出现的变量都被全称量词限定，所以有时会将全称量词省去,一阶规则有着强大的表达能力，例如它能简洁地表达递归概念，如:
一阶规则学习能够容易地引入领域知识，这是它相对于命题规则学习的另一大优势。在命题规则学习乃至一般的统计学习中，若欲引入领域知识，通常有两种做法:在现有属性的基础上基于领域知识构造出新属性，或基于领域知识设计某种函数机制(如正则化)来对假设。 然而现实任务中并非所有的领域知识都能够容易地通过属性重构和函数约束来表达。例如，假定我们获得包含了某未知元素的化合物$X$，欲通过实验来发现它与已知化合物$Y$的化学表达式,我们可以重复多次实验，测出每次结果中化合物的组份含量，虽然我们对反应中的未知元素的性质一无所知，但知道一些普遍成立的化学原理，例如金属原子一般产生离子键、氢原子之间一般都是共价键，并且也了解已知元素间可能发生反应，这些领域知识非常重要，但往往很难在基于命题表示的学习中加以利用。
下面介绍一种著名的一阶规则学习算法
First-Order inductive Learner
FOIL是著名的一阶规则学习算法，它遵循序贯覆盖框架且采用自顶向下的规则归纳策略，由于有逻辑变量的存在，FOIL在规则生成时需考虑不同的变量组合。这也是和命题规则所不同的地方,在命题规则的学习中只需要考虑原子命题之间的组合，而在一阶逻辑规则学习中，除了要考虑原子公式的组合，还应当考虑公式中变量的组合。
FOIL使用“FOIL增益”来选择文字:
总结
规则学习是”符号主义学习”，是最早开始研究的机器学习技术之一。序贯覆盖是规则学习的基本框架，CN2采用集述搜索，是最早考虑过拟合问题的规则学习算法，现实出后剪枝在缓解规则学习过拟合中的优势。
由于命题规则的表述能力有限，一阶逻辑学习开始发展，FOIL通过变量替换等操作把命题规则学习转化为一阶规则学习。
近年来随着机器学习技术进入更多应用领域，在富含结构信息和领域知识的任务中，逻辑表达的重要性逐渐凸显出来，因此出现了一些将规则学习与统计学习相结合的努力，例如给贝叶斯网中的节点赋予逻辑意义的“关系贝叶斯网络”、贝叶斯逻辑程序、马尔可夫逻辑网络，统称为”统计关系学习”。
