ѧ
JOURNAL OF SOFTWARE
1999 19 3  Vol.19 No.3 1999



Ƚ͵ĲȫϢӦ
Ҷ硡ɡǶ
ժҪȫϢµĽ֪ʶٵ֮һ.һ־зǵʵ߼.ܹ֪ʶĽͽۺУѡͣʹΪ֪ʶ۱ƽﵽµȫ˶֪ʶȫԼһҪ.ΪȡӦ߼򣬻ڹ߼Ƽһֶ෽ѧϰ㷨㷨нǿĹ.㷨Ӧ863ũҵרϵͳ,.
ؼʡרϵͳȫϢȽͣ߼.
ͼšTP18
Precedent Interpretation Based Incomplete Information 
Reasoning and Its Application
YE Feng XU Xiao-fei WANG Ya-dong
(Department of Computer Science and Engineering Harbin Institute of Technology Harbin 150001)
Abstract Approximate reasoning with the incomplete information is one of the difficulties that the knowledge engineering has faced. A precedent logic program theory with the property of nonmonotonicity is proposed in this paper. The synthesis evaluation for the interpretation of knowledge can be taken with the theory, such that the optimal selection of interpretation is made possible which becomes the best approach to the current knowledge. The theory completion in the significance of optimal selection is achieved and the requirement of completion and consistency of knowledge are avoided. To acquire the precedent logic programs in the applications, based on an inductive logic programming, learning algorithm is presented which incorporates the multiple inductive methods and has greater ability of induction. The presented theory and the algorithm have been applied in an expert system and gained satisfactory results.
Key wordsExpert system, incomplete information reasoning, precedent interpretation, inductive logic programming.
ȫϢµĽ֪ʶٵ֮һҲ˹оеҪ⣬ҪӦüֵ.˹ܻڲȫϢ£Ӻдìܵؽһƽ˴о,糣ʶо.оһ̻һƵʽϵͳ13ݵĳ֣Щϵͳзǵ.Щܵǿ̻ĳЩضϢδ֪,ϵͳӦĸԴ֪ʶٵ,ѽ.ģһƵһϵͳпټ㼰ݴǶԸȫϢ.Ȼȱ㹻ıԴ߼.
G.Pinkasķ߼4⼶ϵĹìһֽ.ڴ˻һֻ߼ۣеȨֵ˼߼УӶõ߼Ӿۣۣ.һһ׵,Ȼؾ߼ϵԽԣһۿԵõʾ֪ʶȽ.Ƚ۽ŵĽǱ׼߼ģ͵Ȼƹ㣬һйȫͬ.оȽһµܹܺõؿ̻ڲȫϢµֱܹЧشìܻȫ֪ʶ.ĵһǣһڹ߼ƣ5,6ݷILP(inductive logic programming)ѧϰ㷨BDI(bi-directional induction)һ㷨ܹɲӦ.ͨһרϵͳʵ˵㷨Ӧ.
1߼
ڲȫϢ½Ĺؼʹ֪ʶȫ.ͳǽĳʩ֪ʶ֪ʶûпǸ֪ʶĿɿԶӰ죬˴ڸ.ڶһйظ֪ʶɿԼ֪ʶ۵.
1.1 ߼﷨
ɿԳõķʽиʡŶȵ.ĲPinkas4ݵĴʽ֪ʶʵһʵ䲻ر,Աһһܣʹϵͳܹ׵.
߼򲿷ֵزPinkasķ߼(penalty logic)ʽÿһӾһʵʹͨӾõĽ˶.
 1. ߼߼䣬rPQ1,...,QnӾ伯.rR+ʵΪֵPԭӣΪӾͷQi֣ΪӾ壨Ŀ꣩.
Ϊ㣬ӾΪʽ{P,Q1,...,Qn}.
߼ͨ߼Ĳڣpr:pQ1,...,QnõpʵrΪr:pΪpõ̶ֳ֧Ϊr.
߼ṩһڳͻѡĻƣ⼴һ۵.ΪˣReiter۷ǵʱһ.
1:Nixon.֪κ˻Ϊ͵˻Ϊͽ͵˶ǺƽߣͽǺƽߣʣNixonǺƽ߻ǷǺƽ?ʵ߼Ϊ
1000: Person(Nixon).
20: Republican(X)Person(X).
20: Christian(X)Person(X).
10: Not_Pacifist(X)Republican(X).
10: Pacifist(X)Christian(X).
ӾеֵǼٶ.еõ10:Pacifist(Nixon)10:Not_Pacifist(Nixon)ֵȶͻĽ.ΪһΪͽǺƽߣ͵˷֮.ַ۵ֱԭǹ10:Not_Pacifist(X)Republican(X)10:Pacifist(X)Christian(X)ƽȵҪ.ߵֵΪ15ֽ۵ȣ15:Pacifist(Nixon)10:Not_Pacifist(Nixon)Pacifist(Nixon)õ֧.
1˵,߼ֵʽḻ߼ı滹һ򵥵ĴʽԲȫϢĴҲ˵.
1.2 ߼Ľ
ֵɶ߼Ľͽ.һأʵнϴֵ,ʾԵõ϶֧֣нϴֵ,ӳһнϴɿ.͵ȼΪиʵֵĺ.ˣ͵ȼСӳ֪ʶԽ͵̶ֳ֧.߼ȽѡЩõ϶ֵ֧Ļʵ.
ֻ۷ǵݹ߼Ϊ˱֤пɼԣҲٶ֪ʶ޺ڣHerbrand.ƪȥ֤.
ۻֵΪ.Ϊ߼UH()ʾHerbrandBH()ʾHerbrandInst()ʾUH()Ӿȫ壬MH()ʾHerbrandģ͵ԭӲ.ĻּIΪI=I+?I-I+={e|eBH()eI}I-={e|eBH()?eI}.
2. ĻּIΪĽ͵ҽI+I-=.
߼򦷵ĽIֵ㺯Prec.
3. IΪĽ.
PrecIÿڦеõֵٽЩֵȡ͵õIֵ.˱ʾһڽIĻʵڦδõκ֧ʱ,ϵͳ䡰ͷ.Prec˽ۼĹϵֵۺϵ˽Ͷ֪ʶ˳̶.õĽͼֵ.
n=|Inst()|,ӾĻm=|I|=Max{r|rPQ1,...,Qnʦ}.
1. ˡPrec({e},)n.
2. mPrec(I,)ܦnm.
4. IΪ߼򦷵Ƚ͵ҽPrec(I,)=Max{Prec(I,)|IǦĽ}.
()={I|IǦȽ}.
1. Iʦ()MH()I.
ȽͱظǱ׼ģ͵ԭӲ֣,ȽǶԱ׼ģ͵ʵ.
2. Iʦ()eI,Prec(I-{e},)Prec(I,).
Ƚÿһʵήͽ͵ȼ.ȽͿ£͵ȶʵҪ.
5. KΪȽͺ,.
1. ȽͺKMH().
2:Կ1¼.ȥʵ1000:Person(Nixon)Not_PacifistPacifist෴һʵȡ-10Ϊ{Nixon}.
(1) 20: Republican(X)Person(X).
(2) 20: Christian(X)Person(X).
(3) 10: Not_Pacifist(X)Republican(X).
(4) 10: Pacifist(X)Christian(X).
(5) 100: Not_Pacifist(X)Pacifist(X).
(6) 100: Pacifist(X)Not_Pacifist(X).
Prec岻ѵõеȽͣI1={Person(Nixon),Republican(Nixon),
Christian(Nixon),Pacifist(Nixon)},I2={Person(Nixon),Republican(Nixon),Christian
(Nixon),Not_Pacifist(Nixon)},ֵΪ140߼򦷵ȽͺΪ{Person
(Nixon),Republican(Nixon),Christian(Nixon)}ע⵽һȶеʵPerson(Nixon)ǲ³.4ӾֵΪ15õΨһȽI1,4ӾֵΪ5ʱֵõΨһȽI2.ɴ˿ɼȽͿܾзǵ.
1.3 Ƚ͵Ĺ
۵ġӡ,ȡ۱ϵͳֵˣֵĴСһܶԽѡġء롰.PrecĶ岻ѵ֪ԽСȽԽӽ߼HerbrandģͣΪءʽ֮ȽͺԽķHerbrandģͲ֣Ϊʽ˵ȡֵӦӾӦö.
3. =-ޣ()={MH()}.
ǸȽ͹Ч㷨Ƚ͵Ĺڼѵ.ȻӦУֻ迼һضʵǷȽͼ.رǶж߼֤㷨Ĵ.
6. ExtΪԭe߼򦷵ż
Ext={e}.
Ext=T{Q1,...,Qn|eT,eQ1,...,QnInst()}.TeĹڦż.
Ext=T{Q1,...,Qn|eT,QiQ1,...,Qi-1,e,Qi+1,...,QnInst()}.TeĹڦż.
3. e.ҽeĹж߼򦷵żExtʹPrec(Ext,)>0.
ɴˣжǷeֻѰeżExtʹPrec(Ext,)>0.ж£ײż.
2ѧϰ㷨
߼ILPǻѧϰ³ֵһо֧,ĿǴʵ֪ʶйɲĿһرǲ߼ʽĸ.ILPҪǣ(1) ڹѧϰгеı֪ʶ(2) ʹ߼Ϊԣʹȷ.Ϊ֪ʶȡֶΣͨƻILPѧϰ㷨ɲйص߼򣬲ڽѧϰʹϵͳ֪ʶϵ.
2.1 ILP
֪ʶBK,ʾE=E+E-,E+E-ILPɲH
 . BKE-|١.  Ҫ. BK|E+.
 . BKHE-|١. . BKH|E+.
Сì.ILPĿǣڱ֤һǰ£ҳH,ʹBKHܹ߼̺E+.,BK,H,E-,E+Լ߼ռ.
̣ɹҲΪ.걸ģʹ5,6ݣVWILPоõջ.ЩǴ⵽һջ.ILPһѧϰʹôһ㵽ػ.ʹջػܹϳֵزѡĿ.
2.2 ѧϰ㷨
߼ռѰӾǻILPѧϰ㷨ĺ֮һ.ILPѧϰ㷨BDI㷨ͬʱʹջػӾ(߼Ӿ)ʹȨ溯Ӿ.·ʵΪPQ1,...,QnĻӾ䣬PʾνʣQiӦν.TʾPQ1,...,Qniff T,Q1,...,QnP.֮,TųʾPQ1,...,Qn.2.1ж壬ҵ輯HʹöԸʾE=E+E-eE+,THeeE-,THųe.
Ȩ溯7hHҪhE+ĸǳ̶ԼE+E-Ļ.n(h)ʾhǵʾn+(h)ʾhǵhAC(h)=P(+/h),hǵʾΪĸ.Զѧϰ⣬LaplaceP(+/h)ĽϺýƣkEʾ.hǽɹڼhõģhhӿüȨ溯WAC.hhļȨ
7. ӾhBKE¹HģeE+,BK,H-{h}e.
ʾPQ1,...,QnEPΪνʣͷ.Ϊ{P(X1,...,Xn)},Xiͬ.
BDI㷨Ļ˼ǣ(1) ѡȡЩ,ʩջ򣬲ųзļӾ䲢ACѡ(2) ʩػ,ųзļӾ䲢WACѡ; (3) ӲļӾѡõļ,ʹֵǵ; (4) ȥѱǵԼ.ظ,ֱ.㷨BDI϶º¶ֻILPۺ϶ɵѧϰ㷨.봫ͳILP㷨ȣBDIнϸߵѧϰЧ.رأBDIɲӾֵǵʹӾֵӦоȷ.
3רϵͳӦʵ
1996,863߿ƼĿƻڶչũҵϢʾ̣ҵѧ绯ге󶹸߲ۺרϵͳ.ϵͳĺĹ֮һǲȫϢ֪ʶȡ.ڽܱĵ㷨Ӧ.
3.1 ȫϢӦ
ϵͳи֪ʶ;õ:(1) BDI㷨ӵũҵʵнйѧϰõ(2) ֱרṩͬṩֵ.֪ʶ˶죬ӳרҵʵʸܣҪԭ,ͬص켫.ͬרҶͬһĲܷͬӳĸ棬֪ʶһǲʵ.ϵͳ֪ʶһ룬֪ʶҲԱ֤һԣϵͳ֪ʶǷḻ.ͨĲȷ֪ʶȫһҪϸŶƵ.ĵ߼ϵȽͷȴ.ĵķԸֿܵĽۣ֪ͣʶۺУŽۣͣ.
ΪӳȽ͵׼ȷԣô󶹲溦֪ʶʵ˶ȱʵʵ飬ͼ1ʾ.֤ȱ15%,Ӱȷ۵Ļ;֤ȱ40%ʱ۴.άڽϵˮƽ.ˣȽʵ.

ͼ1Ƚʵ
3.2 ֪ʶȡ
BDI㷨ֱӴʾѧϰԲר֪ʶ⣬һǶ֪ʶнѧϰ.ǽ֪ʶѵʾԱ棬ϵͳʹ,ʱBDI֪ʶ.
(1) µķ.ǰʵ֪ʶ޵.ǰʵʾγֵΪ1ļӾ֪ʶ.
(2) ֪ʶ.ǰʵֺȽͲĽ.ǰʵi࣬򽫵ǰʵµiʾУֱӵBDIеiѧϰ²ӾܵԭiеӾ࣬BDIܹɾӾ.
(3) ۲ȷ.ǰʵֺȷĽûеõֵ.ǰʵi࣬򽫵ǰʵµiʾУԲȷķ֪ʶBDIѧϰѧϰʾΪѧϰķ.
ϵʹBDI̵ѧϰʹϵͳ֪ʶҪ.
4 
ԲȫϢһ֪ʶ̵⣬һȽ͵ĲȫϢ.һ֪ʶͽۺţʹȽонϴֵʵܵϵͳҪ֪ʶֱ֧.ʵ,ȽͲ֪ʶĽϼѱƽ,ӦҲרֱֱӿ̻.
Ϊ߼Զȡ֧֣ĻILPѧϰһֽԶº¶ֻɷѧϰ㷨BDI.㷨¾нǿṩ˶֪ʶԶȡ۽ֱ֧.
Ľۼ㷨BDIũҵרϵͳеʵӦ.ʵķ֪ʶȡʧΪһӦĽ.
оõ863߿ƼĿ.Ҷ,1960,ʿ,ҪоΪѧϰ˹߼.,1962,ʿڣʿʦ,ҪоΪ죬ֲʽݿ.Ƕ,1964,ڣҪоΪѧϰרϵͳ.
ͨѶϵ:Ҷ磬150001ҵѧѧ빤ϵ
ߵλҵѧѧ빤ϵ150001
ο
1Reiter R. On closed world databases. In: Gallaire H, Minker J eds. Logic and Database. New York: Plenum Press, 1978
2Reiter R. A logic for default reasoning. Artificial Intelligence, 1985,13(1):81132
3McCarthy J. Circumscriptiona form of nonmonotonic reasoning. Artificial Intelligence, 1985,13(1):2739
4Pinkas G. Reasoning, nonmonotonicity and learning in connectionist networks that capture propositional knowledge. Artificial Intelligence, 1995,77(2):203247
5Muggleton S, DeRaedt L. Inductive logic programming: theory and method. Journal of Logic Programming, 1994,19(20):629679
6Muggleton S, Buntine W. Machine invention of first order predicates by inverting resolution. In: Muggleton S ed. Inductive Logic Programming. London: Academic Press. 1992. 161280
7Lavrac N, Dzeroski S, Bratko I. Handling imperfect data in inductive logic programming. In: DeRaedt L ed. Advances in Inductive Logic Programming. Amsterdam: IOS Press, 1996. 4864
1998-03-23ո壩
