ѧ
JOURNAL OF SOFTWARE
1999 10 7ڡNo.7 Vol.10 1999



չ۵ļ
ŷͮƷ
ժҪѧ߽ϵһӦڻģ͵.Ȼ,ǵоֻڼ.չ˸Ϣ,ָչ۵ϿռСڵӦ۵Ͽռ.,չڲ,֤˶ڷյչ,ϵڻһԼ.һӦڲѡĲ.
ؼʡ,չ,ģ͵,,.
ͼšTP18
Differential Diagnosis Based on Generalized Causal Theory
OU-YANG Dan-tong1 JIANG Yun-fei2
1(Department of Computer Science Jilin University Changchun 130023
2(Institute of Computer Software Zhongshan University Guangzhou 510275
AbstractMany researchers have applied the concept of causation to model-based diagnosis. However, their researches are limited to simple causal theory. In this paper, the concept of generalized causal theory that contains more information is proposed. It is pointed out that the diagnostic space of a generalized causal theory is smaller than or equal to that of the corresponding simple causal theory. Furthermore, generalized causal theory is applied to the area of test. It is demonstrated that for closed generalized causal theory, the abductive differential diagnosis is equivalent to the consistency-based differential diagnosis.
Key wordsSimple causal theory, generalized causal theory, model-based diagnosis, test, differential diagnosis.
ϵ֪ʶǳʶһҪ.ǳʹԭͽճ.,ҽѧϽΪԭ,֢״Ϊе͵ϵͳΪԭ,Ϊ滮򽫹滮Ϊԭ,Ϊȵ.,ѧʶ˽ϵһӦڻģ͵Ҫ.,Consoleˣ1ݺKonolige2ݷֱڼо˻һԵϺ.McIraithReiter3֤˶ڷյļ,ϵڻһԼ.
һľ,ΪֻбʾϵϢʵӦл͵Ϣ,綨Ϣʾϵ(correlationϢ.չ۾ͰЩϢ.ʵİϵϢļϿռС,ҳõĽ.
һԵĵ.˴豸ϵͳͶϵͳΪĹ۲,ôԲһܹ͸ù۲Ϊĺѡϼ.,üеϲֻһ,,ΪҵĹ,ҪӸüϳһĲ,ȻִЩ,µĹ۲Ϊ,Ծµĺѡϼ.ظ,ֱҵΨһϻҲҲܹϵĲΪֹ.о˵Խչ۵ĻһϿռϿռӰ,ֽһоչ۵ļ.Ͼͨѡһ,ҳΨһ.֤˶ڷյչ,һԼһ.һӦڲѡĲ.
1 չ
13. LΪ.һSCΪԪ顴C,E,,CΪԭ,LԭӼ;EΪ,LԭӼ;ǰԭͽϵϢ,L伯.еʽCe,eE,CΪֵĺȡʽ,ЩֵΪԭ.
1:ͼ1ʾĵ·ͼ.һڵS3ͬͺŵĵB1,B2,B3(Ϊٲ,W1,...,W6ֱ.

ͼ1
ϵͳɲCOMPS={S,Bi,Wj|i=1,2,3,j=1,...,6}.SCΪC,E,,бʾϵϢۦΪ
OK(S)OK(W1)OK(W2)OK(B1)on(B1),
OK(S)OK(W1)OK(W2)OK(W3)OK(W4)OK(B2)on(B2),
OK(S)OK(W1)OK(W2)OK(W3)OK(W4)OK(W5)OK(W6)OK(B3)on(B3),
ԭC={OK(Ck),AB(Ck)|CkCOMPS},
E={on(Bi),off(Bi)|i=1,2,3}.
ֻʹSCһ,Ϊϵ,͵Ϣ,綨Ϣ
AB(Ck)OK(Ck),CkCOMPS,(1)
on(Bi)off(Bi),i=1,2,3. (2)
,бʾϵ(correlationϢ,磺
off(B1)OK(B1)off(B2)off(B3), (3)
off(B2)OK(B2)off(B3).(4)
ϵ(3)˵,B1,ֻǵԴSǵW1W2֮й.ʵ,֪һǷ,B2B3.ͬ,Խһϵ(4).ְϵϢԤ,.,A={OK(B1),off(B1)}Ƴoff(B2),AǪoff(B2)ԭ.
Ϊ,չ۵ĸ.
2. LΪ,һչGCΪԪ顴SC,DF,CR,SCΪۡC,E,,ͬ1;DFΪ,ΪL伯;CRΪϵ,ΪL伯.
Ȼ,ϵӦģƳ,Ͳг,Ҳ𲻵СϿռ.ӦǴƽǶܽͨ,ܴһʽ͵Ϣ.,ʹпųЩ߼ϿܵΥȻĲܵ.
ʵİϵϢļСϿռ.Ϊ˵һ,Ȼعһת4漰ĻһСϵһЩͶ,Ϊ׼.
34. һϵͳһԪ(SD,COMPS,OBS,SDΪϵͳ,һνʹʽļ;COMPSΪϵͳɲ,һ޵ĳ;OBSΪһ۲⼯,һνʹʽ޼.SD˴ϵͳر֪ʶ,Ϊۡչ۵ȵ.
44. (SD,COMPS,OBSĻһСΪСϲ,ʹSDOBS{AB(ccʦ}{AB(ccCOMPS}һµ.
54. (SD,COMPS,OBSĳͻΪһ{c1,...,cn},ʹSDOBS{AB(c1),...,AB(cn)}һ.ƹ(SD,COMPS,OBS)һͻΪСģҽüϵһӼǹ(SD,COMPS,OBS)ĳͻ.
5еĳͻף5жĳͻһһӦ.
64. CǼϴ(ɼɵļ).CһΪHsC s,ʹöÿһsCHs.CһΪСĵҽκһӼC.
14. (SD,COMPS,OBSĻһСϵҽ(SD,COMPS,OBSСͻصһС.
öμһС.
1,۲OBS={off(B1),off(B2),on(B3)}.ûж,ôļSC͹۲OBS,㲻κһһԵ.
ڼ붨DF(1)(2).SCֻ˲Ϊ,,ʹûһԵС̻һԵϿռ.ɶ1,ȼ(SCDF,COMPS,OBSСͻأ{{S,W1,W2,B1 },{S,W1,W2,W3,W4,B2}},(SCDF,COMPS,OBS)ĻһСΪСͻصС{S},{W1},{W2},{B1,W3},{B1,W4},{B1,B2}.ô,һϿռеΪЩСϼ䳬,Ȼ൱.
ټϵϢ(3)(4),õ·չGCSC,DF,CR,SC,DFа(1)(2),CRа(3)(4),ʱСͻرˣ{{S,W1,W2,B1 },{S,W1,W2,W3,W4,B2},{B1 },{B2}},,(GC,COMPS,OBSĻһСΪ{B1,B2}.Ϊϵ۵ļС۵Ͽռ,ųΥȻĲܵ,磺{S},{W1},{W2},{B1,W3},{B1,W4}ԼǵĲ{B1,B2}ĳ.
2
һ,ɳͻʶ𡢺ѡõϲֻһ,ԵĿҪһЩϣҳĹ.ף3ݽƲ,ָ:ڷյļ,һԼһ.
73. һ(test)һż(I,O,Iǿɻֵһȡʽ,Oһ۲.
һָɲĳһʼIԼ۲O,һ۲ֵɲж.ֻ򵥵һϵͳ۲ؽڲԵĳʼʱ,I=true.ڵ·,IΪ·,OΪ·Ľֵмֵ.ҽѧ,IܰһЩʵ,Ѫ,۲ΪϸĿ.
83. (I,OĽΪOΪO.
棬رоһչGCеĲ.
TΪһ,ñʾTдһAB֤.
9. ֪GC=C,E,,DF,CR,DSΪǵǰӵеϼ.Ʋ(I,O)Ľ֤ʵ(confirms)DDS,ҽIDDFD.Ʀ(refutes)D,ҽIDGCD.
ϵͳĲΪ{C1,...,Cn},ALLΪl1...li...lnĺȡʽɵļ,liΪAB(CiOK(Ci,i=1,...,n.
10. GC(I,O)ĽĻһΪһDALL,ʹIDĦGC.
11. GC(I,OĽΪһDALL,ʹIDGCIDDF.
ĶҪIDDF,IDGC,ȼ˼,ʹDΪԭ.
濼ǵֻǵԶϿռӰ.ܵļ(differential diagnosis,DD(sequentialϲеһ.ʵڴ²ǲ,ʽ,Ϲ𲽵õ.,ϽγҲɵ.ף6ļϵֱ۸Ϊ:֪һϼ,ִһϵ,µ.ÿһԺĽϼǡð׼ǵ.
2(һDD. DSΪGCлһϵļ,Ϊ(true,OĽ,NEWDS={DDSD}ΪGC{}Ļһϼ.
֤:DALL,Ҫ֤DNEWDSҽDΪGC{}Ļһ.
DNEWDS,D.ɶ9֪,,༴DĦGC.ɶ10֪,DΪGC{}Ļһ.
,DΪGC{}Ļһ.ɶ10֪,DĦGC,GCD.DĦGC֪,DGC,,DDS.ɶ9֪,D.,DNEWDS..
3(DD. DSΪGCϼ,Ϊ(true,OĽ,NEWDS={DDS֤ʵD}ΪGC{}ϼ.
֤:DALL,Ҫ֤DNEWDSҽDΪGC{}.
DNEWDS֤ʵD.ɶ9֪,DGCҦDFD,DDF.,ɶ11֪,DΪGC{}.
,DΪGC{},ɶ11֪,DGC,DDF,,DFD.,DDS,ɶ9֪,֤ʵD.,DNEWDS..
˵ԺµϼNEWDSһΪԭϼDSӼ,µ.ͬ:һDDDSһµϱ,DDǦԭ(ڦDF߼Ƴϱ.ĲʹÿһNEWDSΪǰDSķǿյӼ,ÿһβԺ,µǰDSΪNEWDS,ִһ,յõNEWDSֻһ.,ͽϴڶм.
ֵע:(1DSΪСϼϼ(ǻһԵĻģ,.ԭǣ,Խ޼Ͽռ,ܲµĲDS.(2ֻ(true,Oļ򵥲,ԴʼIĲ.ԭǳʼIʵֿܸıǰ۲ֵ,ѿ̻ʱļ.
12. GC=C,E,,D,CRΪչ,ΪԭӵȷӾ伯,ֱͼΪѭ,GC*=C,E,*,DF,CRΪյչ,Ц*ΪClark걸7.
4. GCΪչ,GC*ΪӦķչ,DSΪGC*лһϵļ,Ϊ(true,OĽ,OE.NEWDS={DDS֤ʵD}ΪGC*{}Ļһϼ.
֤:DALL,Ҫ֤DNEWDSҽDΪ GC*{}Ļһ.
DNEWDS,֤ʵD.ɶ9֪,DGC*,Ҧ*DFD,D*DF.,DGC*.ȻDĦGC.ɶ10֪,DΪGC*{}Ļһ.
,DΪGC*{}Ļһ,ɶ10֪,DĦGC*,ȻDĦ*DF. D,༴*DFD.ֻ֤Ӧ*صֻƳֿܽ:*DFD*DFD(֤֪*DFDǲܵ,ֻЦ*DFD.Ϊ֤,ע⵽:*ΪϵϢۦClark걸.ɴ˿֪*DFB,BΪһ,BֶΪAB(CiOK(Cj,i,j{1,...,n}.DALL,l1...lk...ln,lkΪAB(CkOK(Ck,k=1,...,n.,DB,DB.ɴ˼*DFB֪,Ц*DFD,Ц*DFD.֪*DF D,*DFDǲܵ.,ֻЦ*DF D. DĦGC*֪,DGC*,,DDS,ɶ9֪,֤ʵD(ɶ11֪,DΪGC*{}ϣ.,DNEWDS.
ö˵,ڷյġչ,һԼһ.
24ĽۿӦڲѡĲ.ڷյġչ,ҪӻһϿռΨһ,Ǽȿѡһ(ûһԼϷ,ѡֻ֤ʵһϵһԻ(Ϸ.
3 
ģ͵ϷһµAI,Կ˷ͳϷȱ,ӦҲԽԽ㷺.ϵһֺҪĹϵ,ճʹ.,ǲʶϵڻģ͵Ҫ.˱ȼ۰Ϣչ۵ĸ,оչеĲ.֤˵Խչ۵ϿռӰ,ֽһ֤˶ڷյչ,һԼһ.ЩڲԲԵѡ.
оõȻѧ͹ҽʿ.ŷͮ,Ů,1968,ʿ,ʦ,ҪоΪ֤,ģ͵.Ʒ,1945,,ʿʦ,ҪоΪģ͵ϼ滮,Զ.
ͨѶϵ:ŷͮ,130023,ִѧѧϵ
ߵλŷͮ(ִѧѧϵ130023)Ʒ(ɽѧоݡ510275
ο
1Console L, Dupr D T, Torasso P. Abductive reasoning through direct deduction from completed domain models. In: Ras Z W ed. Methodologies for Intelligent Systems. New York: North-Holland Publishing Company, 1988. 175182
2Konolige K. Abduction versus closure in causal theories. Artificial Intelligence, 1992,53(2-3):255272
3McIraith S, Reiter R. On tests for hypothetical reasoning. In: Hamscher W, Console L, de Kleer J eds. Readings in Model-based Diagnosis. San Mateo, CA: Morgan Kaufmann Publishers, 1992. 8996
4Reiter R. A theory of diagnosis from first principles. Artificial Intelligence, 1987,32(1):5796
5de Kleer J, Mackworth A K, Reiter R. Characterizing diagnosis and systems. Artificial Intelligence, 1992,56(2-3):197222
6Ledley R S, Lusted L B. Reasoning foundations of medical diagnosis. Science, 1959,130(3366):921
7Clark K. Negation as failure. In: Gallaire H, Minker J eds. Logic and Data Bases. New York: Plenum Publishing Corporation, 1978. 293322
1998-03-23յԭ 
1998-08-05յ޸ĸ
