符号学习简介
归纳逻辑程序设计（二）
(Press ? for help, n and p for next and previous slide)
路径图
符号学习简介・归纳逻辑程序设计（二）
- 实质蕴涵
- 逆蕴涵
- Progol
实质蕴涵
“Material Implication”
\[
A\rightarrow B
\]
真值表
| \(A\) | \(B\) | \(A\rightarrow B\) |
|---|---|---|
| \(True\) | \(True\) | \(True\) |
| \(True\) | \(False\) | \(False\) |
| \(False\) | \(True\) | \(True\) |
| \(False\) | \(False\) | \(False\) |
第一种解释
| \(A\) | \(B\) | \(A\rightarrow B\) |
|---|---|---|
| \(True\) | \(True\) | \(True\) |
| \(True\) | \(False\) | \(False\) |
| \(False\) | \(True\) | \(X=?\) |
| \(False\) | \(False\) | \(Y=?\) |
第二种解释
\[
(A\wedge B)\rightarrow B
\]
第三种解释
“如果中国男足出线，我就把名字倒着写”
Vacuous Truth
\[
\forall a P(a)\rightarrow Q(a)
\]
Entailment：重言蕴涵
\[
\Gamma, A\models B
\]
Entailment：重言蕴涵
\[
\Gamma\models A\rightarrow B
\]
摄涵与实质蕴涵
摄涵不等于蕴涵，例如
\begin{align*}
C&=\mathrm{nat}(s(X))\leftarrow\mathrm{nat}(X)\\
D&=\mathrm{nat}(s(s(Y)))\leftarrow\mathrm{nat}(Y)
\end{align*}
有 \(C\rightarrow D\) 却没有 \(C\preceq D\)。
摄涵与实质蕴涵
没有函数符的例子
\begin{align*}
C&=p(X,Z)\leftarrow p(X,Y)\wedge p(Y,Z)\\
D&=p(A,D)\leftarrow p(A,B)\wedge p(B,C)\wedge p(C,D)
\end{align*}
有 \(C\rightarrow D\) 却没有 \(C\preceq D\)。
从 SLD-归结的角度理解
摄涵与实质蕴涵
定理：若 \(C\) 不是自归结的，且 \(D\) 不是重言式，那么 \(C\rightarrow D\) 等价于 \(C\preceq D\)。
实质蕴涵意义上的泛化
若 \(C\rightarrow D\)，那么
- \(D\) 是重言式；
- \(C\preceq D\)；
- \(E\preceq D\) 且 \(E\) 是由 \(C\) 通过自归结得到。
然而，正是自递归导致 \(C\rightarrow D\) 是不可判定的！所以子句集的 Least General Generalisation under Implication (LGGI) 是不可计算的。
如何解决？
- “Roots of self-resolution” [S. Muggleton, 1992]
- T-Implication [P. Idestam-Almquist, 1995]
- Sub-saturants [S. Muggleton, 1995]
但可惜的是由于递归导致的 \(C\rightarrow D\) 不可判定，这些基于实质蕴涵的泛化无法做到完备，即无法保证在有限时间内计算出正确的 \(C\)。
符号学习简介・归纳逻辑程序设计（二）
- 实质蕴涵
- 逆蕴涵
- Progol
语构蕴涵
\[
\xcancel{
B, H\vdash_{\text{SLD-Resolution}} E
}
\]
- 由于自递归的缘故，直接用 \(\theta\)-subsumption 进行归纳是不可判定的
语义蕴涵
\[
B, H\models E
\]
逆（语义）蕴涵
\[
B, \neg E\models \neg H
\]
逆（语义）蕴涵
\[
B, \neg E\models \neg \bot \models \neg H
\]
- \(\neg\bot\)：在每个 \(\mathrm{M}_{B\wedge\neg E}\) 中均为真的原子命题
逆（语义）蕴涵
\[
H \models \bot
\]
- \(H\) 中的每一个子句均是 \(\bot\) 的子集
- 即 \(H\preceq \bot\) （为什么这里没有摄涵和自递归导致的问题？）
底子句（Bottom clauses）
- \(B\)：
anim(X):-pet(X).pet(X):-dog(X).
- \(E\)：
nice(X):-dog(X). - \(\bot\)：
nice(X):-dog(X),pet(X),anim(X).
底子句（Bottom clauses）
- \(B\)：
hasbeak(X):-bird(X).bird(X):-vulture(X).
- \(E\)：
hasbeak(tweaty). - \(\bot\)：
hasbeak(tweaty).bird(tweaty).vulture(tweaty).
底子句（Bottom clauses）
- \(B\)：
sentence([],[]). - \(E\)：
sentence([a,a,a],[]). - \(\bot\)：
sentence([a,a,a],[]):-sentence([],[]).
逆蕴涵完备吗？
- 看起来，只要 \(\models\) 完备，它就完备了
- 若出现自递归，可以想办法控制“\(\models\)”递归深度，这可基于下面两个假设
越一般的程序应该越短，所以除非有一个极端样本，如 \(nat(s(s(s(s(s(\ldots (0)))))))\)。考虑
% Background knowledge nat(0). nat(s(s(X))) :- nat(X). % Example nat(s(s(s(s(...s(x)))))). % odd numbers of "s/1"- 在定子句程序中“\(\models\)”可以通过 SLD-归结快速计算（由有效性保证）
逆蕴涵完备吗？
互递归呢？[A Yamamoto, 1997]
% Background knowledge even(0). even(s(X)) :- odd(X). % Example odd(s(s(s(0)))). % Bottom clause not(Bot) = ( even(0), not( odd( s(s(s(0))) ) ) ).
让逆蕴涵变完备
利用闭世界假设，将 Herbrand Base 里所有非 Herbrand Model 的原子全部纳入进 \(\bot\)。[Muggleton ,1998]
定义（增广底子句集）令 \(B\) 为一个 Horn 子句集合，\(E\) 为一个子句使得 \(F=(B\cup\neg E)\) 可满足（即 \(B\not\models E\)）。\(E\) 在 \(B\) 下的增广底子句集 \(BOT(B,E)\) 定义如下：
- \(BOT^+(B,E)=\{a|a\in \mathrm{B}(F)\backslash \mathrm{M}(F)\}\)
- \(BOT^-(B,E)=\{\neg a| a\in \mathrm{M}(F)\}\)
- \(BOT(B,E)=BOT^+(B,E)\cup BOT^-(B,E)\)
其中\(\mathrm{B}(F)\) 为 \(F\) 的 Herbrand Base，\(\mathrm{M}(F)\) 为 \(F\) 的 Least Herbrand Model。
让逆蕴涵变完备
Yamamoto 的例子：
\begin{align*}
B&=\left\{
\begin{matrix}
even(0)\leftarrow&\\
even(Y)\leftarrow&\hspace{-.8em} s(X,Y), odd(X)
\end{matrix}
\right\}\\
E&= odd(Z)\leftarrow s(Y,Z), s(X,Y), s(0, X)\\
\neg E&=\left\{
\begin{matrix}
\leftarrow odd(c_z)\\
s(c_y, c_z)\leftarrow\\
s(c_x, c_y)\leftarrow\\
s(0, c_x)\leftarrow
\end{matrix}
\right\}\\
\end{align*}
逆蕴涵的完备性
定义 （增广底子句集下的逆蕴涵）令 \(B\) 为一个 Horn 子句集，\(E\) 为一个子句使得 \(B\not\models E\)。一个子句 \(H\) 被称为从 \(E\) 通过 \(B\) 下的逆蕴涵获得，当且仅当存在一个 \(H'\in BOT(B,E)\) 有 \(H\preceq H'\)。
定理 （逆蕴涵的完备性）令 \(B\) 为一个 Horn 子句集，\(E\) 为一个子句使得 \(F=(B\cup\neg E)\) 可满足（即 \(B\not\models E\)）。\(G=(B\cup H\cup \neg E)\) 不可满足（即 \(B\cup H\models E\)）且 \(\mathrm{B}(G)=\mathrm{B}(F)\)，那么 \(H\) 可以从 \(E\) 通过 \(B\) 下的逆蕴涵获得。
逆蕴涵的问题
显然，这个包含程序 Herbrand Base 的空间太大了！
符号学习简介・归纳逻辑程序设计（二）
- 实质蕴涵
- 逆蕴涵
- Progol
Mode 声明语言
Progol 为了控制 \(\bot\) 形式的种类，使用两种 mode 声明谓词：modeh(N, Atom) 和 modeb(N, Atom)
- 其中
N叫做 recall，表示一条 \(\bot\) 子句中Atom能被实例化的种类个数，N=*表示无限制次数。 Atom=p(T,T,...)是原子公式的模板。T可以是+Type, -Type, #Type；Type可以是int, list, any等等。#表示具体项（ground term）+表示输入变量（来自它前面原子的-变量或规则头）-表示输出变量（用来给后面的原子做输入）
Mode 声明语言
Progol 为了控制 \(\bot\) 形式的长度，使用参数 \(i\) 控制规则深度（即 $i,j$-determinism 里的 \(i\)），用 \(h\) 控制归结证明长度。
例子：
modeh(*, f(+int, -int)).
modeb(*, d(+int, -int)).
modeb(*, f(+int, -int)).
modeb(*, m(+int, -int)).
在 \(i=2\) 时允许下列形式的底子句：
f(A,B) :- d(A,C),f(C,D),m(A,D,B).
f(A,B) :- f(B,C),d(A,C),d(C,D),m(C,D,A).
...
Progol 算法
- 从样本集合里挑一个正样例 \(e\)；
- 根据
mode声明和参数 \(i\) 构造一个摄涵 \(e\) 的底子句 \(\bot_i\)； - 对 \(\bot_i\) 进行利用精化算子进行泛化（Best-first search）；
- 重复步骤 1，直至覆盖全部样例。
Progol 算法
构造 \(\bot_i\)
- 初始化：将 \(e\) 中的常元替换为变元（相同常元换位同一变元）
- 令 \(V\) 为所有与
+关联的变元（初始化时均为 \(e\) 中变元），并记录它们代换了哪些项 - 令深度 \(k=0\)
- 循环：
- 若 \(k=i\) 则返回 \(\bot_i\)，否则 \(k=k+1\)
- 对背景知识中所有逻辑文字：
- 找到所有符合约束的变元代换形式（如果和 \(e\) 中有一样的项，用 V 里对应的变元代换）
- 尝试在 \(h\) 步内对它们进行证明
- 将证明成功的原子公式加入 \(\bot_i\) 并将输出（被重新绑定）的新变元加入 \(V\)
例子
:- mode(*,mem(+any,+list)).
:- mode(1,((+list) = ([-any|-list]))).
:- aleph_set(i,3).
:- aleph_set(noise,0).
:- determination(mem/2,mem/2).
:- determination(mem/2,'='/2).
:-begin_bg.
:-end_bg.
:-begin_in_pos.
mem(0,[0]).
mem(1,[1]).
mem(2,[2]).
mem(3,[3]).
mem(4,[4]).
mem(0,[0,0]).
mem(0,[0,1]).
mem(0,[0,2]).
mem(1,[0,1]).
mem(0,[1,0]).
mem(0,[2,0]).
mem(1,[1,1]).
mem(1,[2,1]).
mem(1,[1,2]).
mem(2,[2,2]).
mem(2,[3,2]).
mem(2,[2,3]).
mem(3,[2,3]).
mem(3,[4,2,3]).
:-end_in_pos.
:-begin_in_neg.
mem(0,[1,2]).
mem(0,[1]).
mem(1,[0]).
mem(3,[]).
mem(2,[]).
mem(2,[3]).
:-end_in_neg.
例子
?- induce(Program).
[select example] [1]
[sat] [1]
[mem(0,[0])]
[bottom clause]
mem(A,B) :-
B=[A|C].
[literals] [2]
[saturation time] [0.0002422499999999994]
[reduce]
[best label so far] [[1,0,2,1]/0]
mem(A,B).
[19/6]
mem(A,B) :-
B=[A|C].
[12/0]
[-------------------------------------]
[found clause]
mem(A,B) :-
B=[A|C].
[pos cover = 12 neg cover = 0] [pos-neg] [12]
[clause label] [[12,0,1,12]]
[clauses constructed] [2]
[-------------------------------------]
[clauses constructed] [2]
[search time] [0.00035609000000000335]
[best clause]
mem(A,B) :-
B=[A|C].
[pos cover = 12 neg cover = 0] [pos-neg] [12]
[atoms left] [7]
[positive examples left] [7]
[estimated time to finish (secs)] [0.00020771916666666862]
[select example] [9]
[sat] [9]
[mem(1,[0,1])]
[bottom clause]
mem(A,B) :-
B=[C|D], mem(C,B), mem(A,D), D=[A|E].
[literals] [5]
[saturation time] [0.0006302100000000199]
[reduce]
[best label so far] [[1,0,2,1]/0]
mem(A,B).
[7/6]
mem(A,B) :-
B=[C|D].
[7/4]
mem(A,B) :-
B=[C|D], mem(C,B).
[7/4]
mem(A,B) :-
B=[C|D], mem(A,D).
[7/0]
[-------------------------------------]
[found clause]
mem(A,B) :-
B=[C|D], mem(A,D).
[pos cover = 7 neg cover = 0] [pos-neg] [7]
[clause label] [[7,0,2,7]]
[clauses constructed] [4]
[-------------------------------------]
mem(A,B) :-
B=[C|D], D=[A|E].
[clauses constructed] [5]
[search time] [0.0006290810000000036]
[best clause]
mem(A,B) :-
B=[C|D], mem(A,D).
[pos cover = 7 neg cover = 0] [pos-neg] [7]
[atoms left] [0]
[positive examples left] [0]
[estimated time to finish (secs)] [0.0]
[theory]
[Rule 1] [Pos cover = 12 Neg cover = 0]
mem(A,B) :-
B=[A|C].
[Rule 2] [Pos cover = 10 Neg cover = 0]
mem(A,B) :-
B=[C|D], mem(A,D).
[Training set performance]
Actual
+ -
+ 19 0 19
Pred
- 0 6 6
19 6 25
Accuracy = 1
[Training set summary] [[19,0,0,6]]
[time taken] [0.002758692000000007]
[total clauses constructed] [7]
Program = [(mem(_A, _B):-_B=[_|_C], mem(_A, _C)), (mem(_D, _E):-_E=[_D|_])].
小结
小结
- Inverse implication 与 $θ$-subsumption
- Inverse entailment
- Progol 是直到 2012 年 Metagol 提出前最成功的 ILP 系统
- 背景知识可以是 Horn 子句
- 训练样例可以是 Horn 子句
- 甚至可以泛化负样例（
:-Negative_Example.）
- 甚至可以泛化负样例（
- 第一次较好地解决了递归问题
- 很难进行谓词发明