【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.归纳逻辑程序设计
归纳逻辑程序设计（Inductive Logic Programming，简称ILP）在一阶规则学习中引入了函数和逻辑表达式嵌套。一方面，这使得机器学习系统具备了更为强大的表达能力；另一方面，ILP可看作用机器学习技术来解决基于背景知识的逻辑程序（logic program）归纳，其学得的“规则”可被PROLOG等逻辑程序设计语言直接使用。
然而，函数和逻辑表达式嵌套的引入也带来了计算上的巨大挑战。例如，给定一元谓词$P$和一元函数$f$，它们能组成的文字有$P(X),P(f(X)),P(f(f(X)))$等无穷多个（个人注解：可以无限嵌套），这就使得规则学习过程中可能的候选原子公式有无穷多个。若仍采用命题逻辑规则或FOIL学习那样自顶向下的规则生成过程，则在增加规则长度时将因无法列举所有候选文字而失败。实际困难还不止这些，例如计算FOIL增益需对规则覆盖的全部正反例计数，而在引入函数和逻辑表达式嵌套之后这也变得不可行。
2.最小一般泛化
归纳逻辑程序设计采用自底向上的规则生成策略，直接将一个或多个正例所对应的具体事实（grounded fact）作为初始规则，再对规则逐步进行泛化以增加其对样例的覆盖率。泛化操作可以是将规则中的常量替换为逻辑变量，也可以是删除规则体中的某个文字。
以西瓜数据集5.0为例，为简便起见，暂且假定“更好$(X,Y)$”仅决定于$(X,Y)$取值相同的关系，正例“更好$(1,10)$”和“更好$(1,15)$”所对应的初始规则分别为：
\[更好(1,10) \leftarrow 根蒂更蜷(1,10) \land 声音更沉(1,10) \land 脐部更凹(1,10) \land 触感更硬(1,10)\] \[更好(1,15) \leftarrow 根蒂更蜷(1,15) \land 脐部更凹(1,15) \land 触感更硬(1,15)\]这里的数字是瓜的编号。
显然，这两条规则只对应了特殊的关系数据样例，难以具有泛化能力。因此，我们希望把这样的“特殊”规则转变为更“一般”的规则。为达到这个目的，最基础的技术是“最小一般泛化”（Least General Generalization，简称LGG）。
给定一阶公式$\mathbf{r}_1$和$\mathbf{r}_2$，LGG先找出涉及相同谓词的文字，然后对文字中每个位置的常量逐一进行考察，若常量在两个文字中相同则保持不变，记为$LGG(t,t)=t$；否则将它们替换为同一个新变量，并将该替换应用于公式的所有其他位置：假定这两个不同的常量分别为$s,t$，新变量为$V$，则记为$LGG(s,t)=V$，并在以后所有出现$LGG(s,t)$的位置用$V$来代替。例如对上面例子中的两条规则，先比较“更好$(1,10)$”和“更好$(1,15)$”，由于文字中常量“10”$\neq$“15”，因此将它们都替换为$Y$，并在$\mathbf{r}_1$和$\mathbf{r}_2$中将其余位置上成对出现的“10”和“15”都替换为$Y$，得到：
\[更好(1,Y) \leftarrow 根蒂更蜷(1,Y) \land 声音更沉(1,Y) \land 脐部更凹(1,Y) \land 触感更硬(1,Y)\] \[更好(1,Y) \leftarrow 根蒂更蜷(1,Y) \land 脐部更凹(1,Y) \land 触感更硬(1,Y)\]然后，LGG忽略$\mathbf{r}_1$和$\mathbf{r}_2$中不含共同谓词的文字，因为若LGG包含某条公式所没有的谓词，则LGG无法特化为那条公式。容易看出，在这个例子中需忽略“声音更沉(1,10)”这个文字，于是得到的LGG为：
\[更好(1,Y) \leftarrow 根蒂更蜷(1,Y) \land 脐部更凹(1,Y) \land 触感更硬(1,Y) \tag{1}\]式(1)仅能判断瓜1是否比其他瓜更好。为了提升其泛化能力，假定另有一条关于瓜2的初始规则：
\[更好(2,10) \leftarrow 颜色更深(2,10) \land 根蒂更蜷(2,10) \land 敲声更沉(2,10) \land 脐部更凹(2,10) \land 触感更硬(2,10) \tag{2}\]于是可求取式(1)与(2)的LGG。注意到文字“更好$(2,10)$”和“更好$(1,Y)$”的对应位置同时出现了常量“10”与变量“Y”，于是可令$LGG(10,Y)=Y_2$，并将所有“10”与“Y”成对出现的位置均替换为$Y_2$。最后，令$LGG(2,1)=X$并删去谓词不同的文字，就得到如下这条不包含常量的一般规则：
\[更好(X,Y_2) \leftarrow 根蒂更蜷 (X,Y_2) \land 脐部更凹 (X,Y_2) \land 触感更硬(X,Y_2)\]上面的例子中仅考虑了肯定文字，未使用“$\neg$”符号。实际上LGG还能进行更复杂的泛化操作。此外，上面还假定“更好$(X,Y)$”的初始规则仅包含变量同为$(X,Y)$的关系，而背景知识中往往包含其他一些有用的关系，因此许多ILP系统采用了不同的初始规则选择方法。最常用的是RLGG（Relative Least General Generalization），它在计算LGG时考虑所有的背景知识，将样例$e$的初始规则定义为$e \leftarrow K$，其中$K$是背景知识中所有原子的合取。
容易证明，LGG是能特化为$\mathbf{r}_1$和$\mathbf{r}_2$的所有一阶公式中最特殊的一个：不存在既能特化为$\mathbf{r}_1$和$\mathbf{r}_2$，也能泛化为它们的LGG的一阶公式$\mathbf{r}’$。
在归纳逻辑程序设计中，获得LGG之后，可将其看作单条规则加入规则集，最后再进一步优化，例如对规则集进行后剪枝等。
3.逆归结
个人注解：这部分没细看，仅作记录。
在逻辑学中，“演绎”（deduction）与“归纳”（induction）是人类认识世界的两种基本方式。大致来说，演绎是从一般性规律出发来探讨具体事物，而归纳则是从个别事物出发概括出一般性规律。一般数学定理证明是演绎实践的代表，而机器学习显然是属于归纳的范畴。1965年，逻辑学家J.A.Robinson提出，一阶谓词演算中的演绎推理能用一条十分简洁的规则描述，这就是数理逻辑中著名的归结原理（resolution principle）。二十多年后，计算机科学家S.Muggleton和W.Buntine针对归纳推理提出了“逆归结”（inverse resolution），这对归纳逻辑程序设计的发展起到了重要作用。
基于归结原理，我们可将貌似复杂的逻辑规则与背景知识联系起来化繁为简；而基于逆归结，我们可基于背景知识来发明新的概念和关系。下面我们先以较为简单的命题演算为例，来看看归结、逆归结是怎么回事。
假定两个逻辑表达式$C_1$和$C_2$成立，且分别包含了互补项$L_1$与$L_2$；不失一般性，令$L=L_1=\neg L_2, C_1 = A \lor L, C_2 = B \lor \neg L$。归结原理告诉我们，通过演绎推理能消去$L$而得到“归结项”$C=A\lor B$。若定义析合范式的删除操作：
\[(A \lor B) - \{ B\} = A \tag{3}\]则归结过程可表述为：
\[C=(C_1 - \{ L \}) \lor (C_2 - \{ \neg L \}) \tag{4}\]简记为：
\[C=C_1 \cdot C_2 \tag{5}\]图15.3给出了归结原理的一个直观例示：
与上面的过程相反，逆归结研究的是在已知$C$和某个$C_i$的情况下如何得到$C_j(i \neq j)$。假定已知$C$和$C_1$求$C_2$，则由式(4)，该过程可表述为：
\[C_2 = (C - (C_1 - \{ L \})) \lor \{ \neg L \} \tag{6}\]在逻辑推理实践中如何实现逆归结呢？定义了四种完备的逆归结操作。若以规则形式$p \leftarrow q$等价地表达$p \lor \neg q$，并假定用小写字母表示逻辑文字、大写字母表示合取式组成的逻辑子句，则这四种操作是：
👉吸收（absorption）：
\[\frac{p \leftarrow A \land B \quad q \leftarrow A}{p \leftarrow q \land B \quad q \leftarrow A} \tag{7}\]👉辨识（identification）：
\[\frac{p \leftarrow A \land B \quad p \leftarrow A \land q}{q \leftarrow B \quad p \leftarrow A \land q} \tag{8}\]👉内构（intra-construction）：
\[\frac{p \leftarrow A \land B \quad p \leftarrow A \land C}{q \leftarrow B \quad p \leftarrow A \land q \quad q \leftarrow C} \tag{9}\]👉互构（inter-construction）：
\[\frac{p \leftarrow A \land B \quad q \leftarrow A \land C}{p \leftarrow r \land B \quad r \leftarrow A \quad q \leftarrow r \land C} \tag{10}\]这里我们用$\frac{X}{Y}$表示$X$蕴含$Y$，在数理逻辑里写作$X \vdash Y$（读作“$X$推出$Y$”）。上述规则中，$X$的子句或是$Y$的归结项，或是$Y$的某个子句的等价项；而$Y$中出现的新逻辑文字则可看作通过归纳学到的新命题。
归结、逆归结都能容易地扩展为一阶逻辑形式；与命题逻辑的主要不同之处是，一阶逻辑的归结、逆归结通常需进行合一置换操作。
“置换”（substitution）是用某些项来替换逻辑表达式中的变量。例如用$\theta = \{ 1/X,2/Y \}$置换“$C=色泽更深(X,Y) \land 敲声更沉 (X,Y)$”可得到“$C’=C\theta = 色泽更深(1,2) \land 敲声更沉(1,2)$”，其中$\{X,Y \}$称为$\theta$的作用域（domain）。与代数中的置换类似，一阶逻辑中也有“复合置换”和“逆置换”。例如先用$\theta = \{Y/X \}$将$X$替换为$Y$，再用$\lambda = \{ 1/Y \}$将$Y$替换为1，这样的复合操作记为$\theta \circ \lambda$；$\theta$的逆置换则记为$\theta ^{-1}= \{ X/Y \}$。
“合一”（unification）是用一种变量置换令两个或多个逻辑表达式相等。例如对“$A=色泽更深(1,X)$”和“$B=色泽更深(Y,2)$”，可用$\theta = \{ 2/X,1/Y \}$使“$A\theta = B\theta = 色泽更深(1,2)$”；此时称$A$和$B$是“可合一的”（unifiable），称$\theta$为$A$和$B$的“合一化子”（unifier）。若$\delta$是一组一阶逻辑表达式$W$的合一化子，且对$W$的任意合一化子$\theta$均存在相应的置换$\lambda$使$\theta = \delta \circ \lambda$，则称$\delta$为$W$的“最一般合一置换”或“最一般合一化子”（most general unifier，简记为MGU），这是归纳逻辑程序中最重要的概念之一。例如“$色泽更深(1,Y)$”和“色泽更深(X,Y)”能被$\theta_1 = \{ 1/X \},\theta_2=\{ 1/X,2/Y \},\theta_3=\{1/Z,Z/X \}$合一，但仅有$\theta_1$是它们的MGU。
一阶逻辑进行归结时，需利用合一操作来搜索互补项$L_1$和$L_2$。对两个一阶逻辑表达式$C_1 = A \lor L_1$和$C_2 = B \lor L_2$，若存在合一化子$\theta$使$L_1 \theta = \neg L_2 \theta$，则可对其进行归结：
\[C = (C_1 - \{ L_1 \}) \theta \lor (C_2 - \{ L_2 \}) \theta \tag{11}\]类似的，可利用合一化子对式(6)进行扩展得到一阶逻辑的逆归结。基于式(5)，定义$C_1=C/C_2$和$C_2=C/C_1$为“归结商”（resolution quotient），于是，逆归结的目标就是在已知$C$和$C_1$时求出归结商$C_2$。对某个$L_1 \in C_1$，假定$\phi_1$是一个置换，它能使：
\[(C_1 - \{ L_1 \}) \phi_1 \vdash C \tag{12}\]对$C=A \lor B$，有$A \vdash C$与$\exists B (C=A\lor B)$等价。
这里$\phi_1$的作用域是$C_1$中所有变量，记为$vars(C_1)$，其作用是使$C_1 - \{ L_1 \}$与$C$中的对应文字能合一。令$\phi_2$为作用域是$vars(L_1)-vars(C_1 - \{L_1 \})$的置换，$L_2$为归结商$C_2$中将被消去的文字，$\theta_2$是以$vars(L_2)$为作用域的置换，$\phi_2$与$\phi_1$共同作用于$L_1$，使得$\neg L_1 \phi_1 \circ \phi_2 = L_2 \theta_2$，于是$\phi_1 \circ \phi_2 \circ \theta_2$为$\neg L_1$与$L_2$的MGU。将前两步的复合置换$\phi_1 \circ \phi_2$记为$\theta_1$，用$\theta_2^{-1}$表示$\theta_2$的逆置换，则有$(\neg L_1 \theta_1) \theta_2^{-1}=L_2$。于是，类似于式(6)，一阶逆归结是：
\[C_2 = (C-(C_1 - \{ L_1 \}) \theta_1 \lor \{ \neg L_1 \theta_1 \}) \theta_2^{-1} \tag{13}\]在一阶情形下$L_1$、$L_2$、$\theta_1$和$\theta_2$的选择通常都不唯一，这时需通过一些其他的判断标准来取舍，例如覆盖率、准确率、信息熵等。
以西瓜数据集5.0为例，假定我们通过一些步骤已得到规则：
\[C_1 = 更好(1,X) \leftarrow 根蒂更蜷(1,X) \land 纹理更清(1,X)\] \[C_2 = 更好(1,Y) \leftarrow 根蒂更蜷(1,Y) \land 敲声更沉(1,Y)\]容易看出它们是“$p \leftarrow A \land B$”和“$p \leftarrow A \land C$”的形式，于是可使用内构操作式(9)来进行逆归结。由于$C_1,C_2$中的谓词都是二元的，为保持新规则描述信息的完整性，我们创造一个新的二元谓词$q(M,N)$，并根据式(9)得到：
\[C' = 更好(1,Z) \leftarrow 根蒂更蜷(1,Z) \land q(M,N)\]式(9)中横线下方的另两项分别是$C_1 / C’$和$C_2 / C’$的归结商。对$C_1 / C’$，容易发现$C’$中通过归结消去$L_1$的选择可以有“$\neg 根蒂更蜷(1,Z)$”和“$\neg q(M,N)$”。$q$是新发明的谓词，迟早需学习一条新规则“$q(M,N)\leftarrow ?$”来定义它；根据奥卡姆剃刀原则，同等描述能力下学得的规则越少越好，因此我们将$\neg q(M,N)$作为$L_1$。由式(13)，存在解：$L_2 = q(1,S), \phi_1 = \{ X/Z \}, \phi_2=\{ 1/M,X/N \}, \theta_2 = \{ X/S \}$。通过简单的演算即可求出归结商为“$q(1,S)\leftarrow 纹理更清(1,S)$”。类似地可求出$C_2 / C’$的归结商“$q(1,T) \leftarrow 敲声更沉(1,T)$”。
逆归结的一大特点是能自动发明新谓词，这些新谓词可能对应于样例属性和背景知识中不存在的新知识，对知识发现与精化有重要意义。但自动发明的新谓词究竟对应于什么语义，例如“$q$”意味着“更新鲜”？“更甜”？“更多日晒”？$\cdots \cdots$这只能通过使用者对任务领域的进一步理解才能明确。
上面的例子中我们只介绍了如何基于两条规则进行逆归结。在现实任务中，ILP系统通常先自底向上生成一组规则，然后再结合最小一般泛化与逆归结做进一步学习。
4.PROLOG
PROLOG是一种非常经典的逻辑程序设计语言，其全称是PROgramming in LOGic。严格来说，PROLOG本身不是训练出来的，而是基于事实和规则进行推理。比如，事实可以是：
1
2
father(tom, bob).
father(bob, alice).
意思是Tom是Bob的父亲，Bob是Alice的父亲。规则可以是：
1
2
3
grandfather(X, Y) :-
father(X, Z),
father(Z, Y).
意思是，如果X是Z的父亲，并且Z是Y的父亲，那么X是Y的祖父。那么如果要判断Tom和Alice之间的关系：
1
?- grandfather(tom, alice).
PROLOG会自动推理：Tom是Bob的父亲；Bob是Alice的父亲；所以Tom是Alice的祖父。因此PROLOG会返回true。
事实和规则通常都是人为定义的。根据第1部分的描述，PROLOG所用的规则也可以由ILP学得。
