贝叶斯网络推理算法综述

©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.(2008)0520935205:2007202207;:2007210209:(19832),,,,BaysE2mail:[e-mail],,,,(,410073):,,,,,:;;:TP399:ASurveyofBayesiannetworkinferencealgorithmsLIHai2tao,JINGuang,ZHOUJing2lun,ZHOUZhong2bao,LIDa2qing(Inst.ofInformationSystem&ManagementofNationalUniv.ofDefenseTechnology,Changsha410073,China)Abstract:Bayesiannetwork(BN)isapowerfultooltoexpressandinferuncertainknowledge.Probabilisticinferenceisanimportantaspectofitsresearch.Bayesiannetworkshavealreadyhadsomerelativelymatureac2curateandapproximateinferencealgorithmsasaresultoftwentyyearsdevelopment.ThepresentachievementonBayesiannetworkinferencealgorithmsissurveied.Andthenathoroughanalysisofthealgorithmscomplex2ity,applicabilityandprecisionispresented.Somekeyaspectsofthealgorithmsarealsopointedout.Thesurveywillbehelpfulonselectionandresearchoftheinferencealgorithms.Keywords:Bayesiannetwork;accurateinference;approximateinference0(Bayesiannetwork)[1]Pearl1986,,NBNN=nV,Em,P,:V,EN(directedacyclicgraph,DAG),ViV,(Vi,Vj)EViVj,ViVj,VjViP(conditionalprobabilitydistribution,CPD),,;,(probabilisticinference)(MAPex2planation)CooperNP2[2],,11.1(message2passingalgorithm,polytreeal2gorithm),Pearl1986[1],,,©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.[1],,,,,1992,Diez,(localconditioningalgo2rithm)[3],,Shachter(globalcon2ditioningalgorithm)[4],,,,Darwiche(dynam2icconditioningalgorithm)[5],,;,Dar2wiche(recursiveconditioningalgo2rithm)[6],,,,,(AND/ORcutsetcon2ditioningalgorithm)[7](conditioninggraphal2gorithm)[8]SuermondtCooperNP2,[9]1.3(junctiontreealgorithm,clique2treealgo2rithm)LauritzenSpiegelhalter1988[10](,),,,,,She2noy2Shafer[11]Hugin[12],Hugin,,Shenoy2Shafer,ParkDarwiche,,[13],Jensen1998(lazypropaga2tionalgorithm)[14],D2,,,,NP2,1.4(symbolicprobabilisticinferenceal2gorithm)Shachter1990[15],,,,,,Zhang[16]Dechter[17]Kask[18],,,,NP2(minimumdeficiency)[19](minimumdegree)[20],,,,,,,1.5//(arcreversal/nodereductional2gorithm)Shachter1990[21],,,,,CheukBoutilier1997,,,[22]/,,,,,CheukBoutilier1.6(differentialalgorithm)Darwiche1999[23],©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.[24];Brandherm[25],,,,,22.1(stochasticsamplingalgorithm),[26],,,:Henrion[27],,,,,Fung[28],Shacther[29](gibbssam2pling)[30](hybridMonte2Carlosampling)[31],,,,,,,2.2(search2basedalgorithm),,,,HenrionTop2N[32]Poole[33]Santos[34]Cooper[35],:(1);(2),2.3(modelsimplificationalgorithm),,,,,[36];[35];[37];[38],,,;[39],,;Sarkar[40],,,,,2.4,,,Murphy1999,(loopybe2liefpropagationalgorithm)[41],,,Mur2phy:,,;tt-1t,,TatikondaJordan,[42]31,,,,,©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.(1),,,,,,,,(2),,,(3),,,,,,(4),,,,,,,:[1]PearlJF,propagationandstructuringinbeliefnetworks[J].ArtificialIntelligence,1986,29(3):2412288.[2]CooperGF.Thecomputationalcomplexityofprobabilisticinfer2enceusingBayesianbeliefnetworks[J].ArtificialIntelligence,1990,42:3932405.[3]DiezFJ.LocalconditioninginBayesiannetworks[R].CognitiveSystemslaboratory,DepartmentofComputerScience,UCLA,1992.[4]ShachterRD,AndersonSK,SzolovitsP.Globalconditioningforprobabilisticinferenceinbeliefnetworks[C]ProceedingsoftheUncertaintyinAIConference1994,SanFrancisco,CA:MorganKaufmann,1994:5142522.[5]DarwicheA.Conditioningmethodsforexactandapproximatein2ferenceincausalnetworks[C]ProceedingsoftheEleventhAnnualConferenceonUncertaintyinArtificialIntelligence,Montreal:MorganKauffman,1995.[6]DarwicheA.Recursiveconditioning[J].ArtificialIntelligence,2001,125(122):5241.[7]MateescuR,DechterR.AND/ORCutsetConditioning[R].Ir2vine,CA:SchoolofInformationandComputerScienceUniver2sityofCalifornia,2005.[8]KevinG,MichaelCH.Conditioninggraphs:practicalstruc2turesforinferenceinBayesiannetworks[C]AustralianCon2ferenceonArtificialIntelligence,2005:49259.[9]SuermondtHJ,CooperGF.Probabilisticinferenceinmultiplyconnectbeliefnetworksusingloopcutsets[J].InternationalJournalofApproximateReasoning,1990.[10]LauritzenSL,SpiegelhalterDJ.Localcomputationswith©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.[J]ProceedingsoftheRoyalStatisticalSocie2ty,1988,B(50):1542227.[11]ShenoyP,ShaferG.Axiomsforprobabilityandbelief2functionpropagation[J].UncertaintyinAI,1990,4:1692198.[12]JensenFV,LauritzenS,OlesenK.Bayesianupdatingincaus2alprobabilisticnetworksbylocalcomputation[J].Computa2tionalStatisticsQuarterly,1990(4):2692282.[13]ParkJD,DarwicheA.MorphingtheHuginandShenoy2ShaferArchitectures[C]Europeanconferenceonsymbolicandquantitativeapproachestoreasoningwithuncertainty,Aal2borg,Danemark,2003:1492160.[14]MadsenAL,JensenFV.Lazypropagationinjunctiontrees[C]ProceedingsoftheFourteenthConferenceonUncertain2tyinArtificialIntelligence,Morga