【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.一阶规则学习
受限于命题逻辑表达能力，命题规则学习难以处理对象之间的“关系”（relation），而关系信息在很多任务中非常重要。例如，我们在现实世界挑选西瓜时，通常很难把水果摊上所有西瓜的特征用属性值描述出来，因为我们很难判断：色泽看起来多深才叫“色泽青绿”？敲起来声音多低才叫“敲声沉闷”？比较现实的做法是将西瓜进行相互比较，例如，“瓜1的颜色比瓜2更深，并且瓜1的根蒂比瓜2更蜷”，因此“瓜1比瓜2更好”。然而，这已超越了命题逻辑的表达能力，需用一阶逻辑表示，并且要使用一阶规则学习。
对西瓜数据，我们不妨定义：
- 色泽深度：乌黑>青绿>浅白；
- 根蒂蜷度：蜷缩>稍蜷>硬挺；
- 敲声沉度：沉闷>浊响>清脆；
- 纹理清晰度：清晰>稍糊>模糊；
- 脐部凹陷度：凹陷>稍凹>平坦；
- 触感硬度：硬滑>软粘。
括号内数字对应于表4.2中的样例编号。
分隔线上半部分为背景知识，下半部分为样例。
于是，西瓜数据集2.0训练集就转化为表15.1的西瓜数据集5.0。这样的数据直接描述了样例间的关系，称为“关系数据”（relational data），其中由原样本属性转化而来的“色泽更深”“根蒂更蜷”等原子公式称为“背景知识”（background knowledge），而由样本类别转化而来的关于“更好”“$\neg$更好”的原子公式称为关系数据样例（examples）。从西瓜数据集5.0可学出这样的一阶规则：
\[(\forall X, \forall Y) (更好(X,Y)\leftarrow 根蒂更蜷(X,Y) \land 脐部更凹(X,Y))\]这样的规则亦称为一阶逻辑子句（clause）。
显然，一阶规则仍是式1的形式，但其规则头、规则体都是一阶逻辑表达式，“更好$(\cdot,\cdot)$”、“根蒂更蜷$(\cdot, \cdot)$”、“脐部更凹$(\cdot , \cdot)$”是关系描述所对应的谓词，个体对象“瓜1”、“瓜2”被逻辑变量“$X$”、“$Y$”替换。全称量词“$\forall$”表示该规则对所有个体对象都成立；通常，在一阶规则中所有出现的变量都被全称量词限定，因此下面我们在不影响理解的情况下将省略量词部分。一阶规则有强大的表达能力，例如它能简洁地表达递归概念，如：
\[更好(X,Y) \leftarrow 更好(X,Z) \land 更好(Z,Y)\]一阶规则学习能容易地引入领域知识，这是它相对于命题规则学习的另一大优势。在命题规则学习乃至一般的统计学习中，若欲引入领域知识，通常有两种做法：在现有属性的基础上基于领域知识构造出新属性，或基于领域知识设计某种函数机制（例如正则化）来对假设空间加以约束。然而，现实任务中并非所有的领域知识都能容易地通过属性重构和函数约束来表达。
统计学习一般是基于“属性-值”表示，这与命题逻辑表示等价；此类学习可统称为“基于命题表示的学习”。
FOIL（First-Order Inductive Learner）是著名的一阶规则学习算法，它遵循序贯覆盖框架且采用自顶向下的规则归纳策略，与【机器学习基础】第六十九课：[规则学习]序贯覆盖中的命题规则学习过程很相似。但由于逻辑变量的存在，FOIL在规则生成时需考虑不同的变量组合。例如在西瓜数据集5.0上，对“更好$(X,Y)$”这个概念，最初的空规则是：
\[更好(X,Y) \leftarrow\]接下来要考虑数据中所有其他谓词以及各种变量搭配作为候选文字。新加入的文字应包含至少一个已出现的变量，否则没有任何实质意义。在这个例子中考虑下列候选文字：
FOIL使用“FOIL增益”（FOIL gain）来选择文字：
\[\text{F_Gain} = \hat{m}_+ \times \left( \log _2 \frac{\hat{m}_+}{\hat{m}_+ + \hat{m}_-} - \log _2 \frac{m_+}{m_+ + m_-} \right) \tag{1}\]其中，$\hat{m}_+,\hat{m}_-$分别为增加候选文字后新规则所覆盖的正、反例数；$m_+,m_-$为原规则覆盖的正、反例数。FOIL增益与决策树使用的信息增益不同，它仅考虑正例的信息量，并且用新规则覆盖的正例数作为权重。这是由于关系数据中正例数往往远少于反例数，因此通常对正例应赋予更多的关注。
在西瓜数据集5.0的例子中，只需给初始的空规则体加入“色泽更深$(X,Y)$”或“脐部更凹$(X,Y)$”，新规则就能覆盖16个正例和2个反例，所对应的FOIL增益为候选最大值$16 \times ( \log _2 \frac{16}{18} - \log _2 \frac{25}{50} )=13.28$。假定前者被选中，则得到：
\[更好(X,Y) \leftarrow 色泽更深(X,Y)\]该规则仍覆盖2个反例：“更好$(15,1)$”与“更好$(15,6)$”。于是，FOIL像命题规则学习那样继续增加规则体长度，最终生成合适的单条规则加入规则集。此后，FOIL使用后剪枝对规则集进行优化。
若允许将目标谓词作为候选文字加入规则体，则FOIL能学出递归规则；若允许将否定形式的文字$\neg \mathbf{f}$作为候选，则往往能得到更简洁的规则集。
FOIL可大致看作命题规则学习与归纳逻辑程序设计之间的过渡，其自顶向下的规则生成过程不能支持函数和逻辑表达式嵌套，因此规则表达能力仍有不足；但它是把命题规则学习过程通过变量替换等操作直接转化为一阶规则学习，因此比一般归纳逻辑程序设计技术更高效。
