第4期 马世龙，等：优先归纳逻辑程序的极限行为 ·11· 式中：i=0or1,)°=，)'= T的最小Herbrand模型为M. 步骤3给定2个子句G=fhi,hm}and 情况2给定E,另一个归纳学习算法产生 G=f21,hm}, Sm=fp(2"0);p(s"(x)→p(x}.则Sm为一个 Igg(G,G)= Horn逻辑程序且Sn的最小Herbrand模型为En, 1gg(:,h:1≤n,1的≤m,l1ggh,h)有 记做Nm,但因为 定义}. S limS.={p(s(x))-p(x): 设有2个子句集合A,B,定义1gg(A,B)= N=limN。=lim En=M. 1gg(G,C):C∈A,G∈B,1ggC,G2)存在， S的最小Herbrand模型，称为M(S,等于空集.则 d(C,C)=minf d(C,C2)C EB. Muggleton和Fengls1证明：如果T是基文字的 有 M(S)≠N 有限集合，那么关于Π的子句G和G的lgg为 因此对任意e∈N,有SHe. Π→G和ΠG的1gg.基于这个性质，给出了LP 学习系统GOL EM,该系统是唯一建立在相关的最 例1假设En如上所述，则GOL EM系统产生 如下的Horn逻辑程序序列： 小一般概化概念基础上的学习系统 GOL EM系统： T6=fp0)}; 假设有逻辑系统即背景知识)和2个实例2 T=fp0);π}； 个基原子)E和B使得HE且HE.构造一个 T乃={p0:π1lggm1,2)}= 与「有关的E和E的1ggC,有TAC、E∧五，且 {p0)1,p(x划→p(3(x}= C在E,和面的推导中只用到一次.令T=(p, {p0);p(x)p(S(x)}, pn,. T3=T3, 定义G=(mVp1V…yVE),G= 八 (门pp V.y VE)和集合C=Igg(G,Ca). Tn=T2, 定义2给定公式集合的序列{A},若满足 … 式中： limA.limA.. 五={Tp0Vp(s0),p(0}= 其中limA。.={P:3"n(p∈A},} {p0),p(s0}A1p(30),p(s0)}, limA。={p:3mn≥m(p∈An}, 1={p0,p(320)}, 式中：3n表示存在无限多的n则{Am}的集合论 lgg1,2)=p(3(x)),p(x} 极限存在，记为imAm. 修改p(2"(s出现的顺序，然后看看GOL EM 2 GOL EM系统的极限正确性 系统得到的结果 例2假设 本节考虑GOL EM系统的极限正确性，将给出 E6=fp(S(0)}, 2个实例说明GOL EM不是极限正确的，且对实例 E=U/p(g0)}, 的顺序是敏感的 E=EU{p(0) 令p为谓词，p(x)表示x为一个偶数；s为后继 函数，即s(x)为x的后继.令 E=E.1Ufp(S+4(0)}, En=p0),p(s0),…p(2m0)} E'3k+1=EkU1p(S20)}, 有对E产生不同理论的2种归纳学习算法 E'36+2=Ek+1U{p(0)},… 情况1给定E。,其中一个归纳学习算法产生 则GOL EM系统会产生如下的Horn逻辑程序序 Tm=fp0);p(x)一p(s(x)},则Tn为Horn逻辑 列： 程序，Tm的最小Herbrand模型为 S0=fp(s0)}: Ma={p0,p(S20),p(2m0),… S={p(s0);}: 可以得出： S2=p(s(0);;lgg(%,}= T lim Tn T: p(s(0)):n:p(s(x)-p(x= M lim M Mi. {p(0);p(s(x)→p(x}, 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net式中 :i1 = 0 or 1 , ( ) 0 = , ( ) 1 = . 步骤 3 给定 2 个子句 C1 = { l11 , …, l1 n } and C2 = { l21 , …, l2 m } , lgg ( C1 , C2 ) = {lgg ( l1 i , l2 j) :1 ≤i ≤n , 1 ≤j ≤m ,lgg ( l1 i , l2 j ) 有 定义} . 设有 2 个子句集合 A , B ,定义 lgg ( A , B) = {lgg ( C1 , C2 ) :C1 ∈A , C2 ∈B ,lgg ( C1 , C2 ) 存在 , d ( C1 , C2 ) = min{ d ( C1 , C2 ) :C2 ∈B}} . Muggleton 和 Feng [8 ]证明 : 如果Γ是基文字的 有限集合 ,那么关于 ∏的子句 C1 和 C2 的 rlgg 为 ∏→C1和 ∏→C2 的 lgg. 基于这个性质 ,给出了 IL P 学习系统 GOL EM ,该系统是唯一建立在相关的最 小一般概化概念基础上的学习系统. GOL EM 系统 : 假设有逻辑系统 Г(即背景知识) 和 2 个实例(2 个基原子) E1 和 E2 使得Γ|2/ E1 且Γ|2/ E2 . 构造一个 与Γ有关的Ε1 和 E2 的lgg C,有Γ∧C、E1 ∧E2 ,且 C在 E1 和 E2 的推导中只用到一次. 令Γ= { p1 , …, pn , …} . 定义 C1 = ( ( p2 ∨ p1 ∨…) ∨E1 ) , C2 = ( ( p1 ∨ p2 ∨…) ∨E2 ) 和集合 C = lgg ( C1 , C2 ) . 定义 2 给定公式集合的序列{ A n } ,若满足 limn →∞ A n = lim n→∞ A n , 其中limn →∞ A n = { P ∶ϖ ∞ n( p ∈A n ) } ,} limn→∞ A n = { p ∶ϖ n0 Πn ≥n0 ( p ∈A n ) } , 式中 : ϖ ∞ n 表示存在无限多的 n 则{ A n } 的集合论 极限存在 ,记为limn→∞ A n . 2 GOL EM 系统的极限正确性 本节考虑 GOL EM 系统的极限正确性 ,将给出 2 个实例说明 GOL EM 不是极限正确的 ,且对实例 的顺序是敏感的. 令 p 为谓词 , p ( x) 表示 x 为一个偶数;s 为后继 函数 ,即 s( x) 为 x 的后继. 令 En = { p (0) , p (s 2 (0) ) , …, p (s2 n (0) ) } . 有对 En 产生不同理论的 2 种归纳学习算法. 情况 1 给定 En ,其中一个归纳学习算法产生 Tn = { p (0) ; p ( x) →p (s 2 ( x) ) } ,则 Tn 为 Horn 逻辑 程序 , Tn 的最小 Herbrand 模型为 Mn = { p (0) , p (s 2 (0) ) , …, p (s 2 m (0) ) , …} . 可以得出 : T = limn →∞ Tn = T1 ; M = limn→∞ Mn = M1 . T 的最小 Herbrand 模型为 M. 情况 2 给定 En , 另一个归纳学习算法产生 S n = { p (s 2 n (0) ) ; p (s n ( x) ) →p ( x) } . 则 S n 为一个 Horn 逻辑程序且 S n 的最小 Herbrand 模型为 En , 记做 N n ,但因为 S = limn →∞ S n = { p (s 2 ( x) ) →p ( x) } ; N = limn →∞ N n = limn→∞ En = M1 . S 的最小 Herbrand 模型 ,称为 M ( S) ,等于空集. 则 有 M ( S) ≠N . 因此对任意 e ∈N ,有 S|2/ e. 例 1 假设 En 如上所述 ,则 GOL EM 系统产生 如下的 Horn 逻辑程序序列 : T0 = { p (0) } ; T1 = { p (0) ;π1 } ; T2 = { p (0) ;π1 ;lgg (π1 ,π2 ) } = { p (0) ;π1 , p ( x) →p (s 2 ( x) ) } = { p (0) ; p ( x) →p (s 2 ( x) ) } , T3 = T2 , … Tn = T2 , … 式中 : π2 = { ( p (0) ∨p (s 2 (0) ) ) , p (s 4 (0) ) } = { p (0) , p (s 4 (0) ) } ∧{ p (s 2 (0) ) , p (s 4 (0) ) } , π1 = { p (0) , p (s 2 (0) ) } , lgg (π1 π, 2 ) = { p (s 2 ( x) ) , p ( x) } . 修改 p (s 2 n (s) 出现的顺序 ,然后看看 GOL EM 系统得到的结果. 例 2 假设 E′0 = { p (s 4 (0) ) } , E′1 = E0 ∪{ p (s 2 (0) ) } , E′2 = E1 ∪{ p (0) } , … E′3 k = E3 k- 1 ∪{ p (s 6 k+4 (0) ) } , E′3 k+1 = E3 k ∪{ p (s 6 k+2 (0) ) } , E′3 k+2 = E3 k+1 ∪{ p (s 6 k (0) ) } , … 则 GOL EM 系统会产生如下的 Horn 逻辑程序序 列 : S0 = { p (s 4 (0) ) } ; S1 = { p (s 4 (0) ) ;γ1 } ; S2 = { p (s 4 (0) ) ;γ1 ;lgg (γ1 ,γ2 ) } = { p (s 4 (0) ) ;γ1 ; p (s 2 ( x) ) →p ( x) } = { p (s 4 (0) ) ; p (s 2 ( x) ) →p ( x) } , 第 4 期 马世龙 ,等 :优先归纳逻辑程序的极限行为 ·11 ·