归纳逻辑程序设计(一)
(Press ?
for help, n
and p
for next and previous slide)
Inductive Logic Programming
“凡生前被火烧死者,其尸口鼻内有烟灰,两手脚皆拳缩……若死后烧者,其人虽手足拳缩,口内即无烟灰。”
——宋慈・《洗冤集录》
若 \(H\) 是逻辑规则集合,\(B\) 和 \(E\) 为具体逻辑事实(ground facts)集合,且以下推理成立
当已知和未知条件不同时,分为三种推理
Scientific Methodology by Charles S. Pierce (1839/9/10 - 1914/4/19)
命题1 | 孙悟空会变身超级赛亚人 |
命题2 | 赛亚人会变成超级赛亚人 |
命题3 | 福尔摩斯住在伦敦 |
命题4 | 福尔摩斯住在英国 |
G. D. Plotkin. A Note on Inductive Generalization. Machine Intelligence, 5(1): 153-163, 1970.
观测实验结果,对规律进行总结:
melted(bit1) :- bit_of_iron(bit1), heatead(bit1,419).
melted(bit2) :- bit_of_iron(bit2), heatead(bit2,419).
melted(X) :- bit_of_iron(X), heatead(X,419).
写做“\(\preceq\)”,也叫做“包摄”。
例如,\(A\preceq B\) 读作“\(A\) 摄涵 \(B\)”或者“\(B\) 摄于 \(A\)”,意思是“\(A\) 比 \(B\) 更一般”。
若 \(K\) 是一个由文字构成的集合,那么 \(W\) 是 \(K\) 的最小一般泛化(least general generalisation, LGG)当且仅当
\[ \{p(f(a, g(Y)), X, g(Y)), p(h(a, g(X)), X, g(X))\} \]
证明思路:
parent(tom,eve) :- father(tom,eve), male(tom).
parent(tom,ann) :- father(tom, ann), male(tom), female(ann).
parent(tom,X) :- father(tom,X), male(tom).
Relative Least General Generalisation:考虑领域知识时的最小一般泛化。
也就是说,\(C\preceq (e_1 \leftarrow B)\) 且 \(C\preceq (e_2 \leftarrow B)\)。
% Background knowledge
append([1,2],[3,4],[1,2,3,4]).
append([a],[],[a]).
append([],[],[]).
append([2],[3,4],[2,3,4]).
% Examples
E1 = append([1,2],[3,4],[1,2,3,4]).
E2 = append([a],[],[a]).
% Saturation
C1 = append([1,2],[3,4],[1,2,3,4]) :-
append([1,2],[3,4],[1,2,3,4]),
append([a],[],[a]),
append([],[],[]),
append([2],[3,4],[2,3,4]).
C2 = append([a],[],[a]) :-
append([1,2],[3,4],[1,2,3,4]),
append([a],[],[a]),
append([],[],[]),
append([2],[3,4],[2,3,4]).
% RLGG(E1,E2,B)
RLGG = append([A|B],C,[A|D]) :-
append([1,2],[3,4],[1,2,3,4]), append([A|B],C,[A|D]),
append(W,C,X), append([S|B],[3,4],[S,T,U|V]),
append([R|G],K,[R|L]), append([a],[],[a]),
append(Q,[],Q), append([P],K,[P|K]), append(N,K,O),
append(M,[],M), append([],[],[]), append(G,K,L),
append([F|G],[3,4],[F,H,I|J]), append([E],C,[E|C]),
append(B,C,D), append([2],[3,4],[2,3,4]).
为了改进 RLGG,GOLEM 对它进行了以下改进:
multiply(A,B,C) :-
decrement(B,D),
multiply(A,D,E),
plus(A,E,C).
D
和 E
均为决定项;D
的度为 1,decrement(B,D)
深度为 1;E
的度为 2,multiply(A,D,E)
深度为 2;plus(A,E,C)
深度为 1。
\(1,1\)-决定的:
class(A,mammal) :- has_milk(A).
\(1,2\)-决定的:
double(A,B) :- plus(A,A,B).
\(2,1\)-决定的:
grandfather(A,B) :- father(A,C), father(C,B).
特化 | 泛化 |
---|---|
演绎 | 归纳 |
变量代换 | 最小一般泛化 |
特化 | 泛化 |
---|---|
演绎 | 归纳 |
变量代换(合一) | 最小一般泛化(逆合一,anti-unification) |
归结 | 逆归结 |
C = child(X,Y) :- father(X,Y).
C2 = parent(X,Y) :- father(X,Y).
输出:
C1 = child(X,Y) :- parent(X,Y).
DUCE 是一个通过逆归结进行命题规则学习的方法,它包含下面几种归纳操作:
Y
用于定义它们X
的泛化:当存在其他规则同样定义 Y
时,同样能被用于证明 X
X
中单独的文字 Y
分离出来Y
的规则体在其他子句中也出现,则同样可以用 Y
替换
N
N
X :- A, B, C, D.
X :- A, B, E, F.
得到
X :- A, B.
X :- A, B, C, D.
Not_X :- A, B, E, F.
得到
X :- A, B, N.
Not_X :- A, B, Not_N.
N :- C, D.
Not_N :- E, F.
DUCE 要求归纳出的子句与另一个归结子句没有公共文字,即它们是有区分性的(separable)。
这会导致:
A :- B, C.
无法从
A :- D, E, F.
B :- D, E.
C :- D, F.
中归纳出。而 DUCE 只可能归纳出下面二者之一
A :- B, F.
A :- C, E.
输入:一个命题逻辑程序,其中每个子句描述一个样例。
输出:一个精化后的命题逻辑程序,能够区分正负样例。
算法:
blackbird(blockhead) :- beak=t, color=black, legs=2, tail=t, wings=t.
chimp(maggie) :- colour=brown, hairy=t, legs=2, tail=t, wings=f.
eagle(egg) :- beak=t, colour=golden, legs=2, tail=t, wings=t.
elephant(adult) :- colour=grey, legs=4, size=big, tail=t, trunk=t, wings=f.
elephant(baby) :- colour=grey, legs=4, size=small, tail=t, trunk=t, wings=f.
falcon(flap) :- beak=t, colour=brown, legs=2, size=big, tail=t, wings=t.
gorilla(ronnie) :- colour=black, hairy=t, legs=2, tail=f, wings=f.
lemur(alone) :- colour=grey, legs=2, tail=t, wings=f.
man(harry) :- colour=brown, hairy=f, legs=2, size=big, tail=f, wings=f.
man(clap) :- colour=pink, hairy=f, legs=2, size=small, tail=f, wings=f.
sparrow(sparky) :- beak=t, colour=brown, legs=2, size=small, tail=t, wings=t.
!- induce.
TRUNCATION - (-12)
Is (elephant :- legs=4) a valid rule? (y/n/i) n
TRUNCATION – (-11)
Is (elephant :- legs=4, wings=f) a valid rule? (y/n/i) n
TRUNCATION – (-11)
Is (elephant :- legs=4, trunk=t) a valid rule? (y/n/i) y
!- induce.
TRUNCATION – (-9)
Is (man :- hairy=f, legs=2, tail=f, wings=f) a valid rule? (y/n/i) y
!- induce.
INTER-CONSTRUCTION – (-1)
Rule:
(? :- legs=2, wings=f)
What shall I call <?>? (name/n/i) primate
!- induce.
INTER-CONSTRUCTION – (-7)
Rule:
(? :- beak=t, legs=2, tail=t, wings=t)
What shall I call <?>? (name/n/i) bird
!- induce.
No applicable transformation
% 归纳得出的结果:
bird :- beak=t, legs=2, tail=t, wings=t.
% covers [blockhead, egg, flap, sparky]
blackbird :- bird, colour=black.
% covers [blockhead]
chimp :- primate, colour=brown, hairy=t, tail=t.
% covers [maggie]
eagle :- bird, colour=golden.
% covers [egg-the-eagle]
elephant :- legs=4, trunk=t.
% covers [adult, baby]
falcon :- bird, colour=brown, size=big.
% covers [flap]
gorilla :- primate, colour=black, hairy=t, tail=f.
% covers [ronnie]
lemur :- primate, colour=grey, tail=t.
% covers [lemur]
man :- primate, hairy=f, tail=f.
% covers [clap, harry]
primate :- legs=2, wings=f.
% covers [maggie, clap, ronnie, harry, alone]
sparrow :- bird, colour=brown, size=small.
% covers [sparky]
\[c_2=(c-(c_1 -\{\mathtt{l}\})\cup\{\neg\mathtt(l)\})\theta_1 \theta_2^{-1}\]
h
的泛化:把 \(\mathtt{A_1}\) 替换成 \(c_1\) 的规则头。
n
时只需要保留相关参数,即同时出现在 n
和 \(c\backslash\mathtt{n}\) 中的参数。
l
的选择可能多样。A
与 B
可有多种交集。
为了缩小一阶逆归结的搜索空间, CIGOL 对几种逆归结操作进行约束: