ѧ
JOURNAL OF SOFTWARE
1999 10 8 Vol.10 No.8 1999



һܳƵILPѧϰ㷨
Сƽȫ
ժҪ·FOIL(first-order inductive)ݹνѧϰ㷨ϵĲԼɴ˵µӦ÷Χľ,ͨӸϸ˵.Ϊ˿˷һȱ,˷ӳݹRʵռEʹϵʵͼH(R,E)ʵĸ,춨㷨ۻ.ڴ˻,˻ʵͼFOILPlus㷨.㷨ͨĲסʵ,ȻȻķֹ˲̬ݹĲ,Ӷ֤FOILPlusԲܳƵѧϰ;ͬʱ,㷨ʱոӶȽ֮FOIL㷨û.FOILPlus㷨Ѿʵ,FOILѧϰʧܵĵݹ,˳ɹ.
ؼʡ߼,FOIL(first-order inductive),ݹ,ʵͼ,ʵ,,,FOILPlus.
ͼšTP
An ILP Algorithm without the Restriction of Constant Ordering
ZHANG Run-qi
(Department of the Special Class for the Gifted Young University of Science and Technology of China Hefei 230026)
CHEN Xiao-pingLIU Gui-quan
(Department of Computer Science University of Science and Technology of China Hefei 230027)
Abstract In this paper, the shortcomings in theory and limitation in applications of FOIL are analysed. To overcome these difficulties, instance graph H(R,E) and instance order are introduced to clarify the relationship between the set R of recursive rules and the instance space E. Based on these concepts, a new ILP algorithm, FOILPlus, is put forward, which prevents the generation of harmful recursive rules by utilizing hung example and hung arc to hold Instance Graph. The algorithm can complete learning tasks without the restriction of constant ordering, and does not substantially raise the computational complexity compared with FOIL. FOILPlus has been implemented, and experiments with it show that it does complete two learning tasks which FOIL fails.
Key wordsILP, FOIL, rescursive, instance graph, instance order, hung example, hung arc, FOILPlus.
߼(Inductive Logic ProgrammingILP)ǻѧϰһҪ;.ȡҪоɹ,ڲͬһϵгɹӦã14.һILPѧϰ£4:
BͰνʵʾE=E+E-,BE+BE+
󡡡νʵں壨߼HʹHB|=E+HBE-
֪,ILP㷨һҪĻʵĿƳԣǹϵļ.һ,HݹӾʱ,ֹּ̿ܲ.ΪʹILPKDDӦֱΪնû,ҪṩĳһԼ̵Ч,رֹ.Ϊ,ʹH̬ݹ顱5.еĸֵַ.Զ,FOIL5ݲõġ򡱷ΪȽ,ʹFOILϵͳʵû̶,ʹΪĿǰΨһܹѧAckermannILPϵͳ5.
Ȼ,򡱷Ҳвһ,ųһ౾ɽġѧϰ,ʹFOILӦ÷Χܴܵ.һµILP㷨FOILPlus,ɣʽƵĲ걸Ŀǰ޷ģ͸ԼʵֵĲ걸һILPѧϰϵͳڴ⣩֮,FOILPlusԿѧĹûκ.
1 FOILĵݹνѧϰ㷨
FOIL5,6һ޵ѧϰĿϵưνʣں.ǲͬ,ԪػԪصı,ҲɢĻ.ϵеıֻĳ,ϵӶΪʵļ.ʵñʾЩϵΪʵ,ʵëʾЩϵΪٵʵ.FOILͨĿ򱳾ϵӶ壨ʵѧϰĿϵûкHornӾ䶨.ѵݰһĿϵһ鱳ϵΪӶ壩.ѧϰĿǽһ߼򣨻ƹ򼯣,߼ĿϵͱϵĿϵں.öݹ޵,ڴֵʾĽṹ.
FOILѵʵһ,ÿѡһӾ,Ӿ串һ,κη.˲,ֱκһӾΪֹ.FOILһtop-downϵͳ,һ㵽.һӾʱ,ǿʼʱӾΪ,ÿμһ,֮⻯,ֱҪΪֹ.
Ϊ˱֤ѭݹ鲻,FOILڵݹ(recursive literal)1,2ݵѡȡϽ򡱽..
1.1 
ÿһTĳ,ûûָ˳Ļ,FOILͼһƺ˳.FOILÿϵRеÿΪTıԪai,ajai,ajֱָRеi͵jԪ,ǷжRʵ,ai,aj֮䶼һµƫ,aiajΪֱܷaiajaiaj.ƫ,Rÿһʵcicjci,cjֱʾʵеi͵jλõĳ.ĳck,ckck,ƫ򲻴.
1.2 ݹ
TĳܰʾһӾ(patial clause)еTıvi,vjܴ֮ƫ.òӾÿvi,vjֵci,cjcicj,vivj.ڴ,ͷΪR(v1,v2,...,vn),R(w1,w2,...,wn)Ӿ,R(w1,w2,...,wn)R(v1,v2,...,vn),ݹֹȷ.ڳ
R(w1,w2,...,wn)R(v1,v2,...,vn) 
wi1i1 vi1 򡡡
wi1=vi1  wi2i2 vi2 򡡡
(1)
wi1=vi1  wi2=vi2 ҡwin-1=vin-1  winin vin
i1,i2,...,in1,2,...,nĳȫ,k (k{1,...,n})ʾ,ʵ˳֪Ļ;ʾ֮һ.ÿһݹֱ,FOILͼһ,ʹܹ֮ͬʱ㱾ֺ͵ǰ.򲻴,õݹִӹռų.
2 FOILݹνѧϰ㷨ȱݼ
ǰ,FOILݹνѧϰ㷨ĺ˼,ͨûΪظ,ڴ˻ϴӹռųЩĵݹ,Ա֤ݹջսڳʼ.FOILܶԳ,еݹִӹռų;FOILԳ,Ҳһֱĵݹִӹռų.µĹռ䲻ٰκҪĵݹ,FOILѧϰʧ.,ȷĳFOILѧȷĵݹ򼯵ıҪ.
ʵʵѧϰصݵӰܻʹFOILҲҴ˳,ӶѧѧȫȷĵݹעⲻΪݹһ㻯̫Եʣ.
1:(a1,b1,...,h1)(a2,b2,...,h2)Ϊ˱,ϵsuccnextֱΪ˳ϵ,ĿϵmapΪ֮ӳϵ*g1ʾg1۳Ӿĳ;map(X,Y)ʾϵmap,1ΪX,2ΪY.
:X: a1,b1,c1,d1,e1,f1,*g1,h1
Y: a2,b2,c2,d2,e2,f2,*g2,h2
ϵ:succ(X,X): (a1,b1),(b1,c1),(c1,d1),(d1,e1),(e1,f1),(f1,g1),(g1,h1),(h1,a1)
next(Y,Y): (a2,b2),(b2,c2),(c2,d2),(d2,e2),(e2,f2),(f2,g2),(g2,h2),(h2,a2)
Ŀϵ:map(X,Y): (a1,a2),(b1,b2),(c1,c2),(d1,d2),(e1,e2),(f1,f2),(g1,g2),(h1,h2)
йϵķCWA7ݸ.
ȻռҪĹ򼯺
(2)
ʵʲ(жFOILĲԶʹĿǰ߰汾FOIL6.4),FOIL޷ѧ.ΪϵsuccnextֱX,YĳԵĻ,Ŀϵmapû̺κγϢ,,FOILΪ,Ȼg1h1a1b1c1d1e1f1g2h2a2b2c2d2e2f2ȷʵ.޷ʹFOILеݹִӺѡų,ѧϰʧ.ʵ,û˳һ,FOILѧ(2).ΪȽ,(f1,g1),(g1,h1),(f2,g2),(g2,h2)֮һΪ,FOILΪܽXYĳȷ,Ӷѧ(2).,ʵеԹλݵĴڣΪ(f1,g1),(g1,h1),(f2,g2),(g2,h2)֮һݣ,ܵFOILʧ,Ӷȷĵݹ.
2:κȻĶƱʾ1ĸĵݹνʵѧϰ.
: N: *0,1,2,...,100
ϵ: odd(N): (1),(3),(5),...,(99)
even(N): (0),(2),(4),...,(100)
half(N,N): (0,0),(1,0),(2,1),(3,1),(4,2),(5,2),(6,3),(7,3),...,(99,49),(100,50)
succ(N,N): (0,1),(1,2),(2,3),...,(98,99),(99,100)
Ŀϵ: binary(N,N): (0,0),(1,1),(2,1),(3,2),(4,1),(5,2),...,(99,4),(100,3)
йϵķCWA.
ռҪĹ򼯺
(3)
ݲԽ,FOILûѧ3κһ.ȻFOILΪ100,99,...,1,0,ʵ,ѧϰûκΰ.ǿ˵еĳ˳Ļ,Ҳȫ.Ȼ˳СΪ0,1,...,99,100,֮,ÿ˫׽ڸƫеǰԪ.
ͨ,Ǻ׿FOILԳ԰ݹֵѡȡһľ:ڳ򡢳Ϊƫ򡢳λȵFOILѧȷĳĵݹѧϰ,FOILǲʤε.,ʹFOILܹҵȷĳ,ǰ,FOILԵݹֵ,ҲпֵݹֵжIȫ(i1,i2,...,in)ж,FOILҵĲܹӳҪì,ҲܵFOILѧȷĵݹ.ȻFOILû,ֻΪ򵥵ѧϰЧ,ûΪ۵.,Ҫָһ,ݹûбϵ,ܹӳݹʵ,һڽҪ۵ʵͼʵ.
3 ʵͼʵ
3.1 ռʵռеļ
1. eΪӾcĸָ,c޵ݹ,ҴcĳͷΪec,c־Ϊ.ʱҲ˵cece,cǸǵ,cǣcģ.
2. eΪӾcָ,cͷΪec,cдΪ.ʱҲ˵cece,c,cǣcģ.
3. eΪӾcָ,cеݹ,ҴcĳͷΪec,c־Ϊ.ʱҲ˵cece,cҵ,cǣcģ.
4. eΪRĸָ,RĳǵݹӾce,RĳݹӾcͷΪec,cķǵݹ־Ϊ,ݹȫR.Ҳ˵ReRe.
5. eΪRָ,RӾce.Ҳ˵ReRe.
6. eΪRָ,RǵݹӾce,ҴRĳݹӾcͷΪec,cķǵݹ־Ϊ,ݹֲȫR.Ҳ˵ReRe.
7. ӾcRʵռEеĸֱEc(c) (Ec(R)),Eh(c) (Eh(R)),Ea(c)(Ea(R)),ڲ¼ΪEc,Eh,Ea.
3.2 ʵͼʵ
˵,˵ͼָͼ,˵Ļָ,˵ģ򣩱߾ָģ߶.ĳĿϵʵռΪE={e1,e2,...,eq},ռһR={c1,c2,...,cp}.ERΨһȷһȨͼH(R,E)ΪH.EԪeiHĵdiһһӦ;REµķļϵԪHĳһһӦ,зǵݹӾcuͷΪeiӳΪͼ1ʾĳͼtrueǶһ㣩,ݹӾcwͷΪekӳΪͼ2ʾĳͼdj1,...,djtǸӾеݹֵӦĵ㣩.ǳH(R,E)ΪRʵռEµʵͼڲ,ʵͼ.ѿ,H(R,E)ÿ޻ӳͼӳʵһ,ǳ֮Ϊʵ򣨴˴޻ָ޻.Ȼ,ʵƫ.

ͼ1

ͼ2
3.3 ʵͼеĸ
ǵݹ򼯵ʵͼֻͼ1ʾ͵ĳ,˻ΪһĵĲ.Ժֻǵݹ򼯵ʵͼ.HеĸǻֱΪӦĳ.ǵ㡢㡢ֱΪӦĵ.Ȼ,ܴtrueһ,Ǹǻ,.Ϊ0ĵΪ;ȲΪ0ĵ,ܴtrueõ,Ǹǵ,.
HпȨֵͬͬػص.ƴʵeiӾ串ǻҵĹΪ,eiڶµĹ̲Ψһ.Ӧ,ͼָͼдڵdi,diΪյĻڶȨֵ.ѿ,Hܹtrue£ǵdiļСͼ,Ӧeiһ޶.ͼΪdiHУһͼ.Hһͼָ,Hͼ,Hһǵڸͼٴһͼ.
3.4 FOILʵͼٷ
FOILѧϰеĵݹRӦH(R,E)п϶ڻ,Ƕ.ʵ֪H(R,E)ֻΨһʵ.ڳ޵ʵռEѧĹRʵӦڳ޵ʵռEʱܴ޵ݹ飨ѭݹ飩,ȱݶһILPϵͳ,ǲ迼.
ͨʵͼʵFOILݹѧϰ㷨ϵȱ.¾ٶFOILͨûһ,ҵǰѡݹRеݹһڸó.
ȱ1. ǰʾ,ݹûбϵ.FOILǻֿܲǡĳ.
ȱ2. ȷʵ˳ȫ,ǰȷʵƫ.ÿܵƫһȫ.ŵݹ,ƫԽԽ,ҲԽԽ,1.2ڵĵݹҲԽԽ٣ҲѡݹֿռԽԽС.ǰ˲ǡĵݹ,ƫĲǡ,ʹĵݹֹĴӺѡݹֿռų,Ʊصѧϰʧ.ĿĴ.
3.5 С 
ͨϷ,ǵó½:κεݹѧϰʵռEڹRʵ,ǣǰ涨ʵͼH(R,E)ÿ޻ͼӳ.FOILĵݹѧϰ㷨ȱݾͼóӳʵ,ʵϳʵޱʹϵ.ĸĽ㷨ͨסָΪʵʵȻȻķֹ˲̬ݹ򼯵Ĳ.
4 FOILPlus㷨
ԼȷΪκη,ҸĹ.ȷ򼯶ӦHԷָΪͼHpHn,HpеΪ,㶼Ǹǵ;HnеΪ,㶼ǷǸǵ.Hл,Hһͼ.
4.1 ʵͼFOILPlus㷨
㷨еRǵǰ,P,NĿ,BΪ,PNE.
FOILPlus(B,E,P,N)
R:=;better:=true;
while better do
һӾc,ʹH(R{c},E)H(R,E);
if cҲ
then
better:=false;
else
R:=R{c};
R.
H(R,E)ΪۺϿHи縲ǡ,ǡҷȣRĸӳ̶ȺHһ.RԽ򵥡,Խ,ǷԽ,H(R,E)ȾԽ.ǶRҪĸıı,Ҳ˵ǶԹRҪӳΪH(R,E)ȵĶ.,Ҫһȷ,иǷʵͼΪ-.
4.2 FOILPlus㷨
4.1еFOILPlus㷨ʾ,FOILPlusӦ㷨ĺ˼ڹRɵͬʱάH(R,E),ͨH(R,E)ָһӾ.
㷨ûбH(R,E)Ļĳ,:㷨ֹH(R,E)гֻ,3.4еFOILȱ2,ǰ治ǡĵݹɿ谭ȷݹ;ռвڵݹRʹH(R,E)޻,H(R,E)лȷR,ǲӦõģӼ5ڣ.,ȷͬʱ,H(R,E)ȥȻû̫Ҫ.ΪNP-hard,ʵϵͳпΪѡṩ.
㷨ȷˡ㷨ΪĳʵR,õH(R,E)бشڹͼ.ΪҪ.ȷ㷨ĹRFOILĵֿƸʵһǱҵĲ̬.
Ϊֲ㷨ɵĹпѭݹ鵼¹᲻ֹȱ,FOILPlus㷨ָ֮֮׵Ĺ㷨Resolve.㷨Ĺٶ½֮FOILĹ5Ҳж.ΪǿԽܵ.
㷨R,E,P,N,Bǰ.Ec,Eh,EaֱΪRĸǵ㼯㼯㼯.㷨FOIL㷨Ļÿʵ˼¼Example,Exampleĸ:
idʵeıţΨһʶã
Aset,ÿԪeΪյʼıŵļ
SeΪʼߵյıŵļ
AsetSһ໥,ʹݹ麯unhang.
FOILPlus(B,E,P,N)
R:=;Ec:=;Eh:=;Ea:=E;better:=true;
for (eE)
e.Aset:=;
e.S:=;
while ePeEc and better do
c:=FindClause(Ec,Eh,Ea,P,N,B);
if c=
then
better:=false;
else
R:(R{c};
adjustEcEhEa(c,Ec,Eh,Ea,P,N,B);
R
adjustEcEhEa(c,Ec,Eh,Ea,P,N,B)
if cΪǵݹӾ
then
for (cÿe)
if eEc
then
eEhEaƵEc;
unhang(e);
else
for (cÿc,cͷΪe,Ϊe1,...,ej)
if eEc
then
if {e1,...,ej}Ec
then
eEhEaƵEc
unhang(e)
else
if eEh then eEaƵEh
A:({ek.idekEc};
e.Aset:(e.Aset{A};
for (ÿei.idA)
ei.S:=ei.S{e.id};
unhang(e)
for (e.ide.S)
if eEh
then
for (Ae.Aset)
if e.idA
then
A:(A-{e.id};
if A=
then
eEhƵEc
unhang(e)
forѭ
㷨еFindClause̳FOILFindClause8ݵʽ,ۺͼһʱ.FOIL㷨нֻΪdeterminategainful.㷨ھǷdeterminateʱ.һӾnn,ĳgainfulֺmm,mʵʸk,FOILԸֵΪ
kI(n,n)-I(m,m).(4)
I(n,n)=-log2n(n+n)bits
,nmֱʾòӾǰĸ.mǵΪh,ֵΪ
(k+h/2)I(n,n,n)-I(m,m,m).(5)
I(n,n,n)=-log2(n+n/2)(n+n+n)bits
Ȼ,òӾ͸о޵ݹʱ,n=m=h=0,(5)ʽתΪ(4)ʽ.
4.3 㷨Resolve
㷨ֻڳɢ.ʱ,FOILPlusFOILһɵݹ,ԴʱĹһĹͬ.㷨ʹƽAVL9ݴ浱ǰĹ·.ƽĲҺάҪʵܹȽϴС.һ,㷨ָΪʾַ˳,ʽ(1)ik=k,k{1,...,j}жʵĴС.
Resolve(e,R)
AVL:=;
return Cover(e,R);
Cover(e,R)
if eAVL then return false;
AVL:=AVL{e};
for (cR)
if cΪǵݹӾ
then
if cĸe
then
AVL:=AVL-{e};
return true;
else
for (cÿͷΪec,cΪe1,...,ej)
if Cover(e1,R) and ... and Cover(ej,R)
then
AVL:=AVL-{e};
return true;
AVL:=AVL-{e};
return false;
4.4 㷨ʱոӶȷ
nΪʵ.ݽṹ,FOILPlus㷨FOILҪʵ¼Example.ΪʵExampleĶǵǰH(R,E)Ϣ,ÿǡñ洢һ,㷨ִйбFOILʹõĴ洢ռΪS(n)=O(max{MRNRR{㷨ִйеÿǰ}),MR=H(R,E),NR=H(R,E)ƽʼ=Rеݹƽݹ.ΪʵӦ,ʹǰᵽAckermann,ÿݹݹҲ2,ԿΪO(NR)=1;O(MR)=O(H(R,E))=O(H(R,E))O(ÿΪյƽ)O(ʵ)(O(1)=O(n).S(n)O(n).ȻFOILĿռ临ӶΪO(n),,FOILPlusFOILĿռ临Ӷȵ.
FOILPlus㷨֮FOIL㷨Ҫunhang.עݹ麯unhang㷨ִйжÿҽһ,FOILʱ仨ѵƿFindClauseȽ,ȫԺԲ.FindClause,FOILPlusFOILҪЩFOILͨųĵݹ,ҪnѺm.Է֪ʹFOILPlusFOILʱ仨гӣ£1.,㷨ʱոӶȶ.
ڹ㷨Resolve,㷨йmʵ.ѿù̶ӦeΪķǳͼµT,T(ei,ej)eiΪejĺ.TϽeidi,㷨ԸõAVLĲҺάʱ仨ΪO(di),㷨ʱ临ӶΪ
T(m)=O(1)+O(di)=O(m)+O(di)=O(m)+O(md)=O(mlog2m)=O(log2m)T(m)
d=O(log2m)ΪTƽ,T((m)=O(m)Ϊͨ5,7ݵʱ临Ӷ.㷨Ŀռ临ӶS(m)=O(max(di))O(m).Թ㷨resolveʱոӶȶǿԽܵ.޻ʵΧ֪ʱ,һkά¼·,ʱT(m)=T(m).
4.5 С 
һǵݹѧϰ,FOILPlus㷨FOILȫͬ;һݹѧϰ,㷨ּˡʹgainֵļ,Ӿ伶ˡ˲̬ݹ򼯵Ĳ.ʵ,һݹѧϰ,Ec˳,ǰ涨ġʵһµģ,㷨ûжԹռκƵ,ͨ롰סʵ,ȻȻıѭݹȲ̬ݹĲ.
5 ʵ
ñ׼Cʵ㷨ȫ.֮ѧϰmapbinary.ʵ.
(1) ռвFOILǶ֡١ʱ,mapѧϰΪ
(6)
ù򼯶ӦHpͼ3ʾ.

ͼ3
Ȼͼл,ȻtrueΪʼ,õΪյ޻,ΪõӦʵĹͼ.ΪĹǿԽܵ.ǽ١ռ,ѧϰ֮Թ(2).
(2) binaryѧϰΪ
(7)
ʽ(7)(3)ĵ12Ӿͬ,3Ӿвͬ,Ǳʵ.
6 ۺͽһĹ
ʵͼ,ԭָĹռʵռ֮һ.ʵͼָƵFOILPlus㷨,ʱոӶûӵǰ,ɣʽƵĲ걸Ŀǰ޷ģ͸ԼʵֵĲ걸һILPѧϰϵͳڴ⣩֮,FOILPlusԿѧĹûκ,FOILILPѧϰϵͳ޷.ѿ,ʵͼԼFOILPlus㷨ƹ㵽νѧϰУ⽫ʾʵͼҪáҲһҪеĹ.
עоõȻѧ.
ͨѶϵ:,Ϸ 230026,йƼѧϵ
߼飺,1975,,ҪоΪѧϰ,ILP,νѧϰ.Сƽ,1955,ʿ,,ҪоΪѧϰ,MAS,AI߼.ȫ,1970,ʿ,ҪоΪѧϰ,Agentϵͳ,AI.
ߵλйƼѧϵ Ϸ 230026
СƽȫйƼѧϵ Ϸ 230027
E-mail: zhangrq@mail.scgy.ustc.edu.cn
ο
1 King R D, Muggleton S, Lewis R A et al. Drug design by machine learning: the use of inductive logic programming to model the structure-activity relationships of trimethoprim analogues binding to dihydrofolate reductase. In: Proceedings of the National Academy of Sciences of USA. 1992,89,1132211326
2 Bratko I, Dzeroski S. Engineering applications of ILP. New Generation Computing, 1995,13(34):313333
3 Srinivasan A, Muggleton S H et al. Theories for mutagenicity: a study in first-order and feature-based induction. Artificial Intelligence, 1996,85(1/2):277299
4 Muggleton S. Inductive logic programming: derivations, successes and shortcommings. SIGART Bulletin, 1994,5(1):511
5 Quinlan J R, Cameron-Jones R M. Induction of logic programs: foil and related systems. New Generation Computing, 1995,13(34):287312
6 Cameron-Jones R M, Quinlan J R. Efficient top-down inductive of logic programs. Inductive Logic Programming, SIGART Bulletin, 1994,5(1):3342
7 Lloyd J W. Foundations of Logic Programming. Berlin: Springer-Verlag, 1984
8 Quinlan J R. Knowledge acquisition from structured data. IEEE Expert, 1991,6(6):3237
9 Knuth D E. The Art of Computer Programming (Volume 3): Sorting and Searching. Amsterdam: Addison-Wesley Publishing Company Inc., 1973
1998-05-18յԭ,1998-09-11յ޸ĸ
