第2卷第4期 智能系统学报 Vol.2 Ne 4 2007年8月 CAAI Transactions on Intelligent Systems Aug.2007 优先归纳逻辑程序的极限行为 马世龙2，眭跃飞2，许可 (1.北京航空航天大学计算机学院，北京100083：2.中国科学院计算技术研究所，北京100080) 摘要：虽然对归纳逻辑程序的极限行为至今并没有深入的研究，但是通常在分析正在执行的增量式或在线归纳学 习算法时，必须考虑这种程序的极限行为.某些归纳学习算法如果不考虑极限行为可能运行到最后会发生错误.如 果给定一个递增的例子集合序列，一个归纳逻辑程序会产生一个相应的具有集合论极限的Ho逻辑程序序列，则 此归纳逻辑程序是收敛的，并且如果该Hor逻辑程序序列关于例子集合序列的极限是极限正确的，则此归纳逻辑 程序是极限正确的，还说明GOL EM系统不是极限正确的.为了解决这个问题，提出了一个极限正确的称为优先 GOL EM系统的归纳逻辑系统，并证明了在一定的限制下，优先GOL EM系统的算法是极限正确的. 关键词：归纳逻辑程序；机器学习；极限行为 中图分类号：TN911.7文献标识码：A文章编号：1673-4785(2007)04000905 Limit behavior of prioritized inductive logic programs MA Shi-long'2,SUI Yue-fei2,XU Ke' (1.School of Computer Science,Beihang University,Beijing 100083,China;2.Institute of Computing Technology,Chinese A- cademy of Sciences Beijing 100080,China) Abstract:Limit behavior of inductive logic programs is an important research topic,but it has not been deeply explored until now.When running incremental or online inductive learning algorithms on a comput- er,limit behavior should be taken into account.An example is given to show that some inductive learning algorithms may produce errors in the long run if limit behavior is not considered.An inductive logic pro- gram is convergent if,given an increasing sequence of example sets,the inductive logic program creates a corresponding sequence of Horn logic programs which have the set-theoretic limit.Furthermore,it is lim- it-correct if the limit of the sequence of the Horn logic programs is correct with respect to the limit of the sequence of the example sets.Two examples show that the GOL EM system is not limit-correct.Finally, we propose an inductive logic program which is limit-correct,called the prioritized GOL EM system.It is proved that the prioritized GOL EM is limit-correct under certain constraints. Key words :inductive logic program;machine learning;limit behavior 随着信息量呈指数倍的增长，从大量信息中发现在自然数k使得Π=k.1=·,例如，如果把这些 有用的知识变得越来越重要归纳逻辑程序是一种从理论限制到Hor逻辑程序上，那么存在一个Her 例子中学习一般理论的程序.在增量式的学习中，例 brand解释I使人永远无法找到一个有限的程序 子总是一个接一个给出的.每获得一个新的例子，从 L,它的最小Herbrand模型等于I,因为有限的 以前的例子中学习到的理论需要不断地更新以满足 Horn逻辑程序集合只满足可数多个条件时，该 目前出现的例子.这样就能得到一个理论序列： Herbrand解释集合是不可数的.因此，还应该考虑 Π，正，…Π， 理论的极限，使得对所有的例子理论都正确) 李未4.s)独立地提出了将一阶理论的集合论极 有时会出现无穷多个例子，该过程无法停止，即不存 限引入到逻辑和计算机科学，并在收敛无穷计算中 使用理论版本作为某些形式理论的逼近.李未s) 收稿日期：200611-12. 定义了一阶理论的集合论极限，并随后给出了它的 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 4 期 智 能 系 统 学 报 Vol. 2 №. 4 2007 年 8 月 CAAI Transactions on Intelligent Systems Aug. 2007 优先归纳逻辑程序的极限行为 马世龙1 ,2 ,眭跃飞2 ,许 可1 (1. 北京航空航天大学 计算机学院 ,北京 100083 ;2. 中国科学院 计算技术研究所 ,北京 100080) 摘 要 :虽然对归纳逻辑程序的极限行为至今并没有深入的研究 ,但是通常在分析正在执行的增量式或在线归纳学 习算法时 ,必须考虑这种程序的极限行为. 某些归纳学习算法如果不考虑极限行为可能运行到最后会发生错误. 如 果给定一个递增的例子集合序列 ,一个归纳逻辑程序会产生一个相应的具有集合论极限的 Horn 逻辑程序序列 ,则 此归纳逻辑程序是收敛的 ,并且如果该 Horn 逻辑程序序列关于例子集合序列的极限是极限正确的 ,则此归纳逻辑 程序是极限正确的 ,还说明 GOL EM 系统不是极限正确的. 为了解决这个问题 ,提出了一个极限正确的称为优先 GOL EM 系统的归纳逻辑系统 ,并证明了在一定的限制下 ,优先 GOL EM 系统的算法是极限正确的. 关键词 :归纳逻辑程序 ;机器学习 ;极限行为 中图分类号 : TN911. 7 文献标识码 :A 文章编号 :167324785 (2007) 0420009205 Limit behavior of prioritized inductive logic programs MA Shi2long 1 ,2 ,SU I Yue2fei 2 ,XU Ke 1 (1. School of Computer Science ,Beihang University ,Beijing 100083 ,China ; 2. Institute of Computing Technology ,Chinese A2 cademy of Sciences ,Beijing 100080 ,China) Abstract :Limit behavior of inductive logic programs is an important research topic , but it has not been deeply explored until now. When running incremental or online inductive learning algorit hms on a comp ut2 er , limit behavior should be taken into account. An example is given to show t hat some inductive learning algorit hms may produce errors in the long run if limit behavior is not considered. An inductive logic pro2 gram is convergent if , given an increasing sequence of example sets , the inductive logic program creates a corresponding sequence of Horn logic programs which have the set2t heoretic limit. Furt hermore , it is lim2 it2correct if t he limit of the sequence of t he Horn logic programs is correct wit h respect to t he limit of t he sequence of t he example sets. Two examples show t hat t he GOL EM system is not limit2correct. Finally , we propose an inductive logic program which is limit2correct , called t he prioritized GOL EM system. It is proved that t he prioritized GOL EM is limit2correct under certain constraints. Keywords :inductive logic program ; machine learning ; limit behavior 收稿日期 :2006211212. 随着信息量呈指数倍的增长 ,从大量信息中发现 有用的知识变得越来越重要. 归纳逻辑程序是一种从 例子中学习一般理论的程序. 在增量式的学习中 ,例 子总是一个接一个给出的. 每获得一个新的例子 ,从 以前的例子中学习到的理论需要不断地更新以满足 目前出现的例子. 这样就能得到一个理论序列 : ∏1 , ∏2 , …, ∏n , …. 有时会出现无穷多个例子 ,该过程无法停止 ,即不存 在自然数 k 使得 ∏k = ∏k - 1 = …,例如 ,如果把这些 理论限制到 Horn 逻辑程序上 ,那么存在一个 Her2 brand 解释 I 使人永远无法找到一个有限的程序 ∏,它的最小 Herbrand 模型等于 I , 因为有限的 Horn 逻辑程序集合只满足可数多个条件时 ,该 Herbrand 解释集合是不可数的. 因此 ,还应该考虑 理论的极限 ,使得对所有的例子理论都正确[1 - 3 ] . 李未[4 - 5 ]独立地提出了将一阶理论的集合论极 限引入到逻辑和计算机科学 ,并在收敛无穷计算中 使用理论版本作为某些形式理论的逼近. 李未[4 - 5 ] 定义了一阶理论的集合论极限 ,并随后给出了它的
·10· 智能系统学报 第2卷 归纳逻辑的形式系统.精确地，给定一阶理论的序列 满足假设的Horn逻辑程序.下面举2个实例来说 几，{}的集合论极限，记为Π=lim几，是一些语 明目前的GOL EM系统产生的逻辑程序不满足假 句的集合，满足：每条包含在中的语句几乎包含在 设.将GOL EM系统修改为一个优先GOL EM系 每个几中，且在无限多的几中的每条语句也包含 统，假设其中的文字上定义一个优先序.详细地，令 在Π中.只有部分一阶理论序列存在集合论极限.本 G和P分别为GOL EM算法和优先GOL EM算法 文用极限表示集合论极限 对任意的例子集合E,用G(和P(分别表示由 归纳逻辑程序的极限行为至今还是个未知的研 GOL EM系统和优先GOL EM系统产生的Horn逻 究领域.目前大部分软件和算法都是增量式的或在 辑程序.则对例子集合E,G(E可能不会满足假设 线的，需要长期运行.当考虑此类软件和算法的正确 但P(日能满足假设.这样，P就是极限正确的 性问题时，它们的极限行为也应该考虑.本文研究的 1 GOL EM系统 重点是归纳逻辑程序中的增量式归纳学习算法.假 设存在一个例子序列，并令E。为n时刻的例子.归 类似于NienhuysCheng的项和公式上距离 纳学习算法A产生理论A(E),其中对每个n,理论 的定义，下面给出一个距离的不同定义 A(Em)关于E都是正确的.然后将给出一个实例表 定义1令f和g分别为n元和m元函数符 明如果不考虑极限行为，有的归纳学习算法就不正 号，距离P定义如下： 确就极限行为而言，合理的归纳学习算法A应该 1)对任意项t,有p(t,=0: 满足下面的条件： 2)如果f≠g,则 1)收敛性：对给定的例子集合序列{E}使得 P(f(,,tal,g(,…sm）=1. E三五三E三fA(E)}有集合论极限； 3)P(f(h,…1n),f(s,s)= 2)极限正确性：A(E)的极限应该关于E。的极 max4pl上L≤i≤nk max{P(ti,s)上1≤i≤nW+1 限是正确的，即，对每个e Elim E有limA(E卜e; 式中：h,a,,5m为项。 可以根据上面的条件考虑下面LP系统，如 上面定义的距离与Nienhuys-Cheng定义的不 FOL、GOL EM和MOBAL.因为FOL和MOBAL 同之处在于距离的值可以是一个简单的形式1/m, 是无函数的，所以这里考虑的重点是GOL EM系 其中m为某自然数.这样的距离用于图论中树之间 统.下面将讨论基于一个只含有有限多谓词符号的 的距离.每个项都可以看成是一棵树T.例如，1= 固定的逻辑语言 f(,,树T,具有标有符号f的根，及n个子 考虑了Horn逻辑程序的极限行为，并对以下 树T4,,Tn如果工，和Tr在深度m上相同，则1 定理进行了证明. 和1在深度m相同。 定理1给定Horn逻辑程序序列{几}，若 设有2个子句C和G,为了计算C和G的 Π=lim卫.存在且对每个足够大的n,几满足下列 最小一般概化(the least general generalization of 假设1： Ci and G),用lgg(G,G)表示，给出如下计算过 对所有几的子句，每个出现在体中的项都会 程 出现在头中，则 步骤1设项1=f(h,…)和项s=g(s, limM(D=MimΠy Sm) 式中：M是一个算子使得对任意的Horn逻辑程序 lgg(t.s)= 立，M(是的最小Herbrand模型. ,ff2, 为了说明归纳逻辑程序的极限正确性，假设归 f1Agg(t,),…,Igg(n,2）,fi=fz 纳逻辑程序满足收敛性.给定一个归纳逻辑程序A, 式中：v为任意新的变量 若对所有的正例集合Em,A(E为关于Em正确的 步骤2给定2个文字h=)4p1(1, Horn逻辑程序，即，M(A(Ea)2Ea,且A(Em)满足 1)和h=()1p2(,…m), 假设，则根据定理1，得 1gg(h,k)= M(limA(E))=lim M(A(E))2 lim En 无定义，i≠n或p1≠， 所以A是极限正确的.因此，为了使A满足极限正 )1pIgg11,…2),,lgg(in,2), 确性，还要设计A使得对任意的输入E,A(E就是 i=且p=p 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
归纳逻辑的形式系统. 精确地 ,给定一阶理论的序列 ∏n ,{ ∏n }的集合论极限 ,记为 ∏= limn→∞ ∏n 是一些语 句的集合 ,满足 :每条包含在 ∏中的语句几乎包含在 每个 ∏n 中 ,且在无限多的 ∏n 中的每条语句也包含 在 ∏中. 只有部分一阶理论序列存在集合论极限. 本 文用极限表示集合论极限. 归纳逻辑程序的极限行为至今还是个未知的研 究领域. 目前大部分软件和算法都是增量式的或在 线的 ,需要长期运行. 当考虑此类软件和算法的正确 性问题时 ,它们的极限行为也应该考虑. 本文研究的 重点是归纳逻辑程序中的增量式归纳学习算法. 假 设存在一个例子序列 ,并令 En 为 n 时刻的例子. 归 纳学习算法 A 产生理论 A ( En ) ,其中对每个 n ,理论 A ( En ) 关于 En 都是正确的. 然后将给出一个实例表 明如果不考虑极限行为 ,有的归纳学习算法就不正 确. 就极限行为而言 ,合理的归纳学习算法 A 应该 满足下面的条件 : 1) 收敛性 : 对给定的例子集合序列{ En } 使得 E1 Α E2 Α E3 Α …,{ A ( En ) }有集合论极限; 2) 极限正确性 :A ( En ) 的极限应该关于 En 的极 限是正确的 ,即 ,对每个 e ∈limn →∞ En 有limn→∞ A ( En ) |2 e ; 可以根据上面的条件考虑下面 IL P 系统 ,如 FOIL 、GOL EM 和 MOBAL . 因为 FOIL 和 MOBAL 是无函数的 ,所以这里考虑的重点是 GOL EM 系 统. 下面将讨论基于一个只含有有限多谓词符号的 固定的逻辑语言. 考虑了 Horn 逻辑程序的极限行为 ,并对以下 定理进行了证明. 定理 1 给定 Horn 逻辑程序序列{ ∏n } , 若 ∏= limn →∞ ∏n 存在且对每个足够大的 n , ∏n 满足下列 假设[7 ] : 对所有 ∏n 的子句 ,每个出现在体中的项都会 出现在头中 ,则 limn→∞ M ( ∏n ) = M (limn→∞ ∏n ) , 式中 : M 是一个算子使得对任意的 Horn 逻辑程序 ∏, M ( ∏) 是 ∏的最小 Herbrand 模型. 为了说明归纳逻辑程序的极限正确性 ,假设归 纳逻辑程序满足收敛性. 给定一个归纳逻辑程序 A , 若对所有的正例集合 En , A ( En ) 为关于 En 正确的 Horn 逻辑程序 ,即 , M ( A ( En ) ) Β En ,且 A ( En ) 满足 假设 ,则根据定理 1 ,得 M (limn →∞ A ( En ) ) = limn→∞ M ( A ( En ) ) Β limn →∞ En . 所以 A 是极限正确的. 因此 ,为了使 A 满足极限正 确性 ,还要设计 A 使得对任意的输入 E , A ( E) 就是 满足假设的 Horn 逻辑程序. 下面举 2 个实例来说 明目前的 GOL EM 系统产生的逻辑程序不满足假 设. 将 GOL EM 系统修改为一个优先 GOL EM 系 统 ,假设其中的文字上定义一个优先序. 详细地 ,令 G和 P 分别为 GOL EM 算法和优先 GOL EM 算法 , 对任意的例子集合 E,用 G( E) 和 P( E) 分别表示由 GOL EM 系统和优先 GOL EM 系统产生的 Horn 逻 辑程序. 则对例子集合 E, G( E) 可能不会满足假设 , 但 P( E) 能满足假设. 这样 , P 就是极限正确的. 1 GOL EM 系统 类似于 Nienhuys2Cheng [9 ] 的项和公式上距离 的定义 ,下面给出一个距离的不同定义. 定义 1 令 f 和 g 分别为 n 元和 m 元函数符 号 ,距离ρ定义如下 : 1) 对任意项 t ,有ρ( t , t) = 0 ; 2) 如果 f ≠g ,则 ρ( f ( t1 , …, tn ) , g (s1 , …,sm ) ) = 1. 3)ρ( f ( t1 , …, tn ) , f (s1 , …,sn ) ) = max{ρ( ti ,si) |2 1 ≤i ≤n} max{ρ( ti ,si) |2 1 ≤i ≤n} + 1 , 式中 :t1 , …, tn ,s1 , …,sm 为项. 上面定义的距离与 Nienhuys2Cheng 定义的不 同之处在于距离的值可以是一个简单的形式 1/ m , 其中 m 为某自然数. 这样的距离用于图论中树之间 的距离. 每个项都可以看成是一棵树 Tt . 例如 , t = f ( t1 , …, tn ) ,树 Tt 具有标有符号 f 的根 ,及 n 个子 树 T t 1 , …, Tt n . 如果 Tt 和 T t′在深度 m 上相同 ,则 t 和 t′在深度 m 相同. 设有 2 个子句 C1 和 C2 ,为了计算 C1 和 C2 的 最小一般概化 (the least general generalization of C1 and C2 ) ,用 lgg ( C1 , C2 ) 表示 ,给出如下计算过 程 : 步骤 1 设项 t = f ( t1 , …, tn ) 和项 s = g (s1 , …, sm ) , lgg ( t ,s) = v , f 1 ≠f 2 , f 1 (lgg ( t11 , t21 ) , …,lgg ( t1 n , t2 n ) ) , f 1 = f 2 . 式中 : v 为任意新的变量. 步骤 2 给定 2 个文字 l1 = ( ) i 1 p1 ( t11 , …, t1 n ) 和 l2 = ( ) i 1 p2 ( t21 , …, t2 m ) , lgg ( l1 , l2 ) = 无定义 , i1 ≠i2 或 p1 ≠p2 , ( ) i 1 p1 (lgg ( t11 , …, t21 ) , …,lgg ( t1 n , t2 n ) ) , i1 = i2 且 p1 = p2 . ·10 · 智 能 系 统 学 报 第 2 卷
第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 ·
·12· 智能系统学报 第2卷 找到最小的in,只有当在E 定义2一个子句中，若每个出现在子句体中 中实例e'<e可列举时，r才能从P(E)中提取.这 的子项都出现在该子句头中，则称该子句是简单的 样对无限多n,π不能在P(E)中列举且从P(E)中 一个逻辑程序，若其中的每个子句都是简单的，则称 提取出.因此{P(E)}具有集合论极限 该逻辑程序是简单的 前文的假设要求Horn逻辑程序是简单的.给 4结束语 定例子集合E,将GOL EM系统修改为新的算法P 当输入例子集合E时，优先的GOL EM系统产 使得P(E是简单的， 生一个简单的Horn逻辑程序P(E).简单Horn逻 先定义文字上的优先关系<假设有2个文字1 辑程序有很多好的普通的Horn逻辑程序没有的性 和1'，如果1中出现的每个子项都在1中出现，则说 质.优先的GOL EM系统是基于例子的语法性质， 1比1优先级高，记做1<1 即，文字上的优先序<，该序可以使优先GOL EM 命题1<是一个前序，即<是自反的和传递 系统在多种应用中变得有用 的 将来的工作可以基于一个逻辑语言的项或公式 优先GOL EM系统： 上定义的距离.这种距离定义可以采用Fitting或 假设给定一个逻辑程序「（即一个背景知识）和 Nienhuys-Cheng给出的距离.然后可以定义项或公 2个例子(2个基原子)E和丘使得THE和 式的Cauchy序列.然后根据例子集合的Cauchy序 HE成立.构造一个与T有关的E:和E的 列和Horn逻辑程序定义收敛性和极限正确性.推 1ggC,有「∧CE∧B且C在E,和推导中用 测优先GOL EM系统还满足定义在Cauchy序列上 了一次令T={pi,pm,… 的收敛性和极限正确性 定义 G=((gg Vy Vei) 参考文献： G=(g1VgV…yVa, [1 ]BERGADANO F,GUNETTI D.Inductive logic program- 集合C=lggG,G),其中，，为带序 ming:from machine learning to software engineering <的集合{p,p,E},即，对每个i有{，， [M].London:The MIT Press,1996. a}=fp,,Ei},且a本g;类似地可定义 [2]DA HR M.Deductive eatabases:theory and applications [M].Boston:International Thomson Computer Press, {q1,9取，a} 1997. 序列上的优先GOL EM系统： [3]FITTIN G M.MeETRIC methods,three examples and a 给定例子集合序列{En},在步骤n输入Em.若 theorem[J ]J of Logic Programming,1994,21:113 对任意i<n,有E。大E,则可用GOL EM系统直接 127. 产生一个Horn逻辑程序，记做A(E):否则，可以 [4]LI W.An open logic system[J ]Science in China (Scien- 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
… S3 k+i = { p (s 6 k+4 - 2 i (0) ) ; p (s 2 ( x) ) →p ( x) } , … 式中 : γ1 = { p (s 4 (0) ) ,s 2 (0) ) } , γ2 = { p (s 4 (0) ) , p (0) } ∧{ p (s 2 (0) ) , p (0) } , lgg (γ1 ,γ2 ) = { p ( x) , p (s 2 ( x) ) } . 从上述可知 ,该实例说明 GOL EM 系统不是极 限正确的 ,且对例子的顺序是敏感的. 3 优先 GOL EM 系统 笔者[7 ] 提出了关于 Horn 逻辑程序的假设 ,用 以保证 Horn 逻辑程序序列的极限的最小 Her2 brand 模型就是逻辑程序的最小 Herbrand 模型的 极限 ,且前一个极限的最小 Herbrand 模型关于 Horn 逻辑程序序列是不变的. 定义 2 一个子句中 ,若每个出现在子句体中 的子项都出现在该子句头中 ,则称该子句是简单的. 一个逻辑程序 ,若其中的每个子句都是简单的 ,则称 该逻辑程序是简单的. 前文的假设要求 Horn 逻辑程序是简单的. 给 定例子集合 E ,将 GOL EM 系统修改为新的算法 P 使得 P ( E) 是简单的. 先定义文字上的优先关系 ; . 假设有 2 个文字 l 和 l′,如果 l 中出现的每个子项都在 l′中出现 ,则说 l 比 l′优先级高 ,记做 l ; l′. 命题 1 ; 是一个前序 ,即 ; 是自反的和传递 的. 优先 GOL EM 系统 : 假设给定一个逻辑程序Γ(即一个背景知识) 和 2 个例子 ( 2 个基原子) Ε1 和 E2 使得 Γ|2/ E1 和 Γ|2/ E2 成立. 构造一个 与 Γ 有关的 E1 和 E2 的 lgg C,有Γ∧C|2E1 ∧E2 且 C 在 E1 和 E2 推导中用 了一次令Γ= { p1 , …, pn , …} . 定义 C1 = ( ( q1 ∨ q2 ∨…) ∨e1 ) , C2 = ( ( q′1 ∨ q′2 ∨…) ∨e2 ) , 集合 C = lgg ( C1 , C2 ) ,其中 q1 , q2 , …, e1 为带序 ; 的集合{ p1 , p2 , …, E1 } , 即 , 对每个 i 有{ q1 , q2 , …, e1 } = { p1 , p2 , …, E1 } ,且 e1 ≮qi ; 类似地可定义 { q′1 , q′2 , …, e2 } . 序列上的优先 GOL EM 系统 : 给定例子集合序列{ En } ,在步骤 n 输入 En . 若 对任意 i i Ej 上. 令 P( En ) 为结果. 定理 2 给定例子集合 E, P( E) 是简单的. 证明 根据前序的定义 ,当一个子句π列举在 P( E) 中时 ,π的头在 E 中总是有最低优先级. 这就 保证了π是简单的. 这样 ,可以得出如下定理. 定理 3 P 是收敛且极限正确的. 即给定一个 正例集合的增长序列{ En } , 1) { P( En ) } 是有集合论 极限的 Horn 逻辑程序序列; 2) limn→∞ P ( En ) 是关于 limn→∞ En极限正确的. 证明 根据前文的讨论只需要证明 1) . 根据前 序 ; 的定义 ,可知 ; 是良定的. 给定一个实例 e ,只 存在有限多个 e′使得 e′; e. 假设对某 n , e 是在 En 中可列举的 ,则子句π产生. 对 n′> n ,只有当在 En 中实例 e′; e 可列举时 ,π才能从 P( En ) 中提取. 这 样对无限多 n ,π不能在 P ( En ) 中列举且从 P( En ) 中 提取出. 因此{ P( En ) }具有集合论极限. 4 结束语 当输入例子集合 E 时 ,优先的 GOL EM 系统产 生一个简单的 Horn 逻辑程序 P( E) . 简单 Horn 逻 辑程序有很多好的普通的 Horn 逻辑程序没有的性 质. 优先的 GOL EM 系统是基于例子的语法性质 , 即 ,文字上的优先序 ; ,该序可以使优先 GOL EM 系统在多种应用中变得有用. 将来的工作可以基于一个逻辑语言的项或公式 上定义的距离. 这种距离定义可以采用 Fitting 或 Nienhuys2Cheng 给出的距离. 然后可以定义项或公 式的 Cauchy 序列. 然后根据例子集合的 Cauchy 序 列和 Horn 逻辑程序定义收敛性和极限正确性. 推 测优先 GOL EM 系统还满足定义在 Cauchy 序列上 的收敛性和极限正确性. 参考文献 : [ 1 ]BERGADANO F , GUN ETTI D. Inductive logic program2 ming : from machine learning to software engineering [ M ]. London : The MIT Press ,1996. [2 ]DA HR M. Deductive eatabases: theory and applications [ M ]. Boston : International Thomson Computer Press , 1997. [3 ] FITTIN G M. MeETRIC methods ,three examples and a theorem[J ]. J of Logic Programming , 1994 , 21 : 113 - 127. [4 ]L I W. An open logic system[J ]. Science in China (Scien2 ·12 · 智 能 系 统 学 报 第 2 卷
第4期 马世龙，等：优先归纳逻辑程序的极限行为 ·13 tia Sinica)(series A),1992(10):1103-1113. [9]NIEN HU YS-CHENG S H.Distances and limits on her- [5]LI W.A logical framework for inductive inference and its brand interpretations [A ]Proc of the 8th International rationality A ]Advanced Topics in Artificial Intelli- Workshop on Inductive Programming,LNAI 1446 [C]. gence LNAI 1747[C].Berlin:Springer,1999. Springer,1998. [6]LLOYD J W.Foundations of logic programming M]. [10]PLOTKIN G.A note on inductive generalization [J ] Berlin:Springer-Verlag,1987. Machine Intelligence,1970,5:153-163. [7]MA S,SUI Y,XU K.The limits of the horn logic pro- 作者简介： grams[A].Lecture Notes in Computer Science (LNCS) 马世龙，男，1953年生，教授，主要 [C]1.[S.1.],2005. 研究方向为网络环境下计算研究、海量 [8]MU GGL ETON S,FENG C.Efficient inductive of logic 信息处理计算模型研究、网格计算技术 programs[A].Proc of the First Conf on Algorithmic 及其应用研究，发表学术论文30余篇。 Learning Theory[C].Tokyo,1990. Email slma @nlsde.buaa.edu.cn 2008 IEEE International Conference on Mechatronics and Automation 2008年EEE机械制造及自动化国际会议 2008 IEEE International Conference on Mechatronics and Automation (ICMA 2008)will take place in Takamatsu,Kagawa,Japan from June 24 to J une 27,2008.Takamatsu is the small city located at Sikoku which is the smallest island in 4 main islands of Japan.Shikoku contains a lot of temples including Zentsu -ji,where one of the most famous Buddhists,Kukai,was born.In addition,you can feel the Japanese history through several historical architectures. The objective of ICMA 2008 is to provide a forum for researchers,educators,engineers,and govern- ment officials involved in the general areas of mechatronics,robotics,automation and sensors to dissemi- nate their latest research results and exchange views on the future research directions of these fields.The topics of interest include,but not limited to the following: -Intelligent mechatronics,robotics,biomimetics,automation,and control systems -Elements,structures,mechanisms,and applications of micro and nano systems -Teleoperation,telerobotics,haptics,and teleoperated semi-autonomous systems Sensor design,multi-sensor data fusion algorithms and wireless sensor networks Biomedical and rehabilitation engineering,prosthetics and artificial organs -Control system modeling and simulation techniques and methodologies -AI,intelligent control,neuro-control,fuzzy control and their applications -Industrial automation,process control,manufacturing process and automation Important Dates: Full papers and organized session proposals,January 15,2008; Proposals for tutorials and workshops,March 1,2008; Notification of paper and organized session acceptance,March 31,2008; Sebmission of final papers,April 20,2008. Website:http://www.icma2008.org 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
tia Sinica) (series A) ,1992 (10) :1103 - 1113. [5 ]L I W. A logical framework for inductive inference and its rationality [ A ]. Advanced Topics in Artificial Intelli2 gence ,LNAI 1747[C]. Berlin :Springer ,1999. [6 ] LLO YD J W. Foundations of logic programming [ M ]. Berlin :Springer2Verlag ,1987. [7 ] MA S , SU I Y, XU K. The limits of the horn logic pro2 grams[ A ]. Lecture Notes in Computer Science (LNCS) [C]. [ S. l. ] ,2005. [8 ] MU GGL ETON S , FEN G C. Efficient inductive of logic programs[ A ]. Proc of the First Conf on Algorithmic Learning Theory[C]. Tokyo ,1990. [9 ]NIEN HU YS2CHEN G S H. Distances and limits on her2 brand interpretations [ A ]. Proc of the 8th International Workshop on Inductive Programming ,LNAI 1446 [ C ]. Springer ,1998. [10 ] PLO T KIN G. A note on inductive generalization [J ]. Machine Intelligence , 1970 ,5 :153 - 163. 作者简介 : 马世龙 ,男 , 1953 年生 ,教授 ,主要 研究方向为网络环境下计算研究、海量 信息处理计算模型研究、网格计算技术 及其应用研究 ,发表学术论文 30 余篇. E2mail :slma @nlsde. buaa. edu. cn. 2008 IEEE International Conference on Mechatronics and Automation 2008 年 IEEE机械制造及自动化国际会议 2008 IEEE International Conference on Mechatronics and Automation (ICMA 2008) will take place in Takamatsu , Kagawa , J apan from J une 24 to J une 27 , 2008. Takamatsu is t he small city located at Sikoku which is t he smallest island in 4 main islands of J apan. Shikoku contains a lot of temples including Zentsu - ji , where one of t he most famous Buddhists , Kukai , was born. In addition , you can feel t he J apanese history t hrough several historical architect ures. The objective of ICMA 2008 is to provide a forum for researchers , educators , engineers , and govern2 ment officials involved in t he general areas of mechatronics , robotics , automation and sensors to dissemi2 nate t heir latest research results and exchange views on the f ut ure research directions of t hese fields. The topics of interest include , but not limited to the following : —Intelligent mechatronics , robotics , biomimetics , automation , and control systems —Elements , struct ures , mechanisms , and applications of micro and nano systems —Teleoperation , telerobotics , haptics , and teleoperated semi - autonomous systems —Sensor design , multi2sensor data f usion algorithms and wireless sensor networks —Biomedical and rehabilitation engineering , prost hetics and artificial organs —Control system modeling and simulation techniques and met hodologies —A I , intelligent control , neuro2control , f uzzy control and t heir applications —Industrial automation , process control , manufact uring process and automation . Important Dates: Full papers and organized session proposals , J anuary 15 , 2008 ; Proposals for t utorials and workshop s , March 1 , 2008 ; Notification of paper and organized session acceptance , March 31 , 2008 ; Sebmission of final papers , April 20 , 2008. Website :http :/ / www.icma2008. org 第 4 期 马世龙 ,等 :优先归纳逻辑程序的极限行为 ·13 ·
