sheng的学习笔记-AI-归纳逻辑程序设计（ILP）

AI目录：sheng的学习笔记-AI目录-CSDN博客

规则学习（rule learning）: sheng的学习笔记-AI-规则学习（rule learning）-CSDN博客

一阶规则学习： sheng的学习笔记-AI-FOIL(First-Order Inductive Learner)-CSDN博客

基础知识

归纳逻辑程序设计（Inductive Logic Programming,简称ILP）在一阶规则学习中引入了函数和逻辑表达式嵌套。

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

但是，函数和逻辑表达式嵌套的引入也带来了计算上的巨大挑战

最小一般泛化

什么是最小一般泛化

归纳逻辑程序设计采用自底向上的规则生成策略，直接将一个或多个正例所对应的具体事实(grounded fact)作为初始规则，再对规则逐步进行泛化以增加其对样例的覆盖率。

泛化操作可以是将规则中的常量替换为逻辑变量，也可以是删除规则体中的某个文字。

为简便起见，暂且假定“更好(X,Y)”仅决定于(X,Y)取值相同的关系，正例 “更好(1,10)”和“更好(1,15)”所对应的初始规则分别为

• 更好(1,10)←根蒂更蜷(1,10)∧声音更沉(1,10)∧脐部更凹(1,10)∧触感更硬(1,10)；
• 更好(1,15)←根蒂更蜷(1,15)∧脐部更凹(1,15)∧触感更硬(1,15)。

这两条规则只对应了特殊的关系数据样例，难以具有泛化能力。因此，我们希望把这样的“特殊”规则转变为更“一般”的规则。为达到这个目的，最基础的技术是“最小一般泛化”​（Least General Generalization,简称LGG）​

示例

给定一阶公式r1和r2,

1. LGG先找出涉及相同谓词的文字，
2. 对文字中每个位置的常量逐一进行考察，
3. 若常量在两个文字中相同则保持不变，记为LGG(t,t)=t；否则将它们替换为同一个新变量，并将该替换应用于公式的所有其他位置：假定这两个不同的常量分别为s,t,新变量为V，则记为LGG(s,t)=V，并在以后所有出现LGG(s,t)的位置用V来代替。

例如对上面例子中的两条规则，先比较“更好(1,10)”和“更好(1,15)”​，由于文字中常量“10”≠“15”​，因此将它们都替换为Y，并在r1和r2中将其余位置上成对出现的“10”和“15”都替换为Y，得到

• 更好(1,Y)←根蒂更蜷(1,Y)∧声音更沉(1,10)∧脐部更凹(1,Y)∧触感更硬(1,Y)；
• 更好(1,Y)←根蒂更蜷(1,Y)∧脐部更凹(1,Y)∧触感更硬(1,Y)。

LGG忽略r1和r2中不含共同谓词的文字，因为若LGG包含某条公式所没有的谓词，则LGG无法特化为那条公式。在这个例子中需忽略“声音更沉(1,10)”这个文字,得到

更好(1,Y)←根蒂更蜷(1,Y)∧脐部更凹(1,Y)∧触感更硬(1,Y)。(15.4)

式(15.4)仅能判断瓜1是否比其他瓜更好。为了提升其泛化能力，假定另有一条关于瓜2的初始规则

更好(2,10)←颜色更深(2,10)∧根蒂更蜷(2,10)∧敲声更沉(2,10)∧脐部更凹(2,10)∧触感更硬(2,10)，(15.5)

可求取式(15.4)与(15.5)的LGG。

注意到文字“更好(2,10)”和“更好(1,Y)”的对应位置同时出现了常量“10”与变量“Y”​，于是可令LGG(10,Y)=Y2，并将所有“10”与“Y”成对出现的位置均替换为Y2.最后，令LGG(2,1)=X并删去谓词不同的文字，就得到如下这条不包含常量的一般规则：

更好(X,Y2)←根蒂更蜷(X,Y2)∧脐部更凹(X,Y2)∧触感更硬(X,Y2)。

上面的例子中仅考虑了肯定文字，未使用“¬”符号。实际上LGG还能进行更复杂的泛化操作。

在归纳逻辑程序设计中，获得LGG之后，可将其看作单条规则加入规则集，最后再用前几节介绍的技术进一步优化，例如对规则集进行后剪枝等。

逆归结

什么是逆归结

在逻辑学中，​“演绎”(deduction)与“归纳”(induction)是人类认识世界的两种基本方式。

演绎是从一般性规律出发来探讨具体事物，而归纳则是从个别事物出发概括出一般性规律。一般数学定理证明是演绎实践的代表，而机器学习显然是属于归纳的范畴。

一阶谓词演算中的演绎推理能用一条十分简洁的规则描述，这就是数理逻辑中著名的归结原理(resolution principle)[Robinson,1965]​。根据归纳推理提出了“逆归结”(inverse resolution)，这对归纳逻辑程序设计的发展起到了重要作用。

基于归结原理，我们可将貌似复杂的逻辑规则与背景知识联系起来化繁为简；而基于逆归结，我们可基于背景知识来发明新的概念和关系

示例

归结、逆归结都能容易地扩展为一阶逻辑形式；与命题逻辑的主要不同之处是，一阶逻辑的归结、逆归结通常需进行合一置换操作。

逆归结的一大特点是能自动发明新谓词，这些新谓词可能对应于样例属性和背景知识中不存在的新知识，对知识发现与精化有重要意义。但自动发明的新谓词究竟对应于什么语义，例如“q”意味着“更新鲜”​？​“更甜”​？​“更多日晒”​？……这只能通过使用者对任务领域的进一步理解才能明确

上面的例子中我们只介绍了如何基于两条规则进行逆归结。在现实任务中，ILP系统通常先自底向上生成一组规则，然后再结合最小一般泛化与逆归结做进一步学习