联合树j-tree算法过程简介.ppt

JunctionTrees:Motivation,Standardalgorithms(e.g.,variableelimination)areinefficientiftheundirectedgraphunderlyingtheBayesNetcontainscycles.Wecanavoidcyclesifweturnhighly-interconnectedsubsetsofthenodesinto“supernodes.”,如果贝叶斯网络底层的无向图中包含环，标准算法（如标量消元）是低效的。如果我们把节点的高度互联的子集转变为“超级节点”，我们可以避开环的存在。,ARunningExamplefortheStepsinConstructingaJunctionTree,Step1:MaketheGraphMoral,Step2:RemoveDirectionality,Step3:TriangulatetheGraph,Step3:TriangulatetheGraph,Step3:TriangulatetheGraph,IsitTriangulatedYet?,TriangulationChecking,上述的最大势算法（mcs算法，MaximumCardinalitySearch），实际上也是求是否存在完美消除序列的方法，存在完美消除序列即为弦图，反之不是，,IsitTriangulatedYet?,IsitTriangulatedYet?,IsitTriangulatedYet?,IsitTriangulatedYet?,IsitTriangulatedYet?,IsitTriangulatedYet?,ItisNotTriangulated,FixingtheFaultyCycle,ContinuingourCheck.,ContinuingourCheck.,FixingthisProblem,ContinuingourCheck.,TheFollowingisTriangulated,Triangulation:KeyPoints,Previousalgorithmisanefficientchecker,butnotnecessarilybestwaytotriangulate.Ingeneral,manytriangulationsmayexist.Theonlyefficientalgorithmsareheuristic.JensenandJensen(1994)showedthatanyschemeforexactinference(beliefupdatinggivenevidence)mustperformtriangulation(perhapshiddenasinDraper1995).,Definitions,Completegraphornodeset:allnodesareadjacent.Clique:maximalcompletesubgraph.Simplicialnode:nodewhosesetofneighborsisacompletenodeset.,Step4:BuildCliqueGraph,TheCliqueGraph,JunctionTrees,Ajunctiontreeisasubgraphofthecliquegraphthat(1)isatree,(2)containsallthenodesofthecliquegraph,and(3)satisfiesthejunctiontreeproperty.Junctiontreeproperty:ForeachpairU,VofcliqueswithintersectionS,allcliquesonthepathbetweenUandVcontainS.应该是其他文献中所说的变量连通性,CliqueGraphtoJunctionTree,Wecanperformexactinferenceefficientlyonajunctiontree(althoughCPTsmaybelarge).Butcanwealwaysbuildajunctiontree?Ifso,how?在联合树中，可以高效的进行精确推理（CPT：条件概率分布表）Lettheweightofanedgeinthecliquegraphbethecardinalityoftheseparator.Thananymaximumweightspanningtree（最大生成树）isajunctiontree(Jensen&Jensen1994).,Step5:BuildtheJunctionTree,Step6:ChooseaRoot,Step7:PopulateCliqueNodes,Foreachdistribution(CPT)intheoriginalBayesNet,putthisdistributionintooneofthecliquenodesthatcontainsallthevariablesreferencedbytheCPT.(Atleastonesuchnodemustexistbecauseofthemoralizationstep).Foreachcliquenode,taketheproductofthedistributions(asinvariableelimination).,BetterTriangulationAlgorithmSpecificallyforBayesNets,BasedonVariableElimination,Repeatuntilnonodesremain:Ifthegraphhasasimplicialnode,eliminateit(considerit“processed”andremoveittogetherwithallitsedges).去除单纯点Otherwise,findthenodewhoseeliminationwouldgivethesmallestpotentialpossible.Eliminatethatnode,andnotetheneedfora“fill-in”edgebetweenanytwonon-adjacentnodesintheresultingpotential.Addthe“fill-in”edgestotheoriginalgraph.,FindCliqueswhileTriangulating(orintriangulatedgraph),Whileexecutingthepreviousalgorithm:foreachsimplicialnode,recordthatnodewithallitsneighborsasapossibleclique.(Thenremovethatnodeanditsedgesasbefore.)Afterrecordingallpossiblecliques,throwoutanyonethatisasubsetofanother.Theremainingsetsarethecliquesinthetriangulatedgraph.O(n3),guaranteedcorrectonlyifgraphistriangulated.,ChooseRoot,AssignCPTs,JunctionTreeInferenceAlgorithm,IncorporateEvidence:Foreachevidencevariable,gotoonetablethatincludesthatvariable.Setto0allentriesinthattablethatdisagreewiththeevidence.UpwardStep:Foreachleafinthejunctiontree,sendamessagetoitsparent.Themessageisthemarginalofitstable,.,J.T.Inference(Continued),(UpwardStepcontinued)summingoutanyvariablenotintheseparator.Whenaparentreceivesamessagefromachild,itmultipliesitstablebythemessagetabletoobtainitsnewtable.Whenaparentreceivesmessagesfromallitschildren,itrepeatstheprocess(actsasaleaf).Thisprocesscontinuesuntiltherootreceivesmessagesfromallitschildren.,J.T.Inference(Continued),DownwardStep:(Roughlyreversestheupwardprocess,startingattheroot.)Foreachchild,therootsendsamessagetothatchild.Morespecifically,therootdividesitscurrenttablebythemessagereceivedfromthatchild,marginalizestheresultingtabletotheseparator,andsendstheresultofthismarginalizationtothechild.Whena.,J.T.Inference(Continued),(DownwardStepcontinued)childreceivesamessagefromitsparent,multiplyingthismessagebythechildscurrenttablewillyieldthejointdistributionoverthechildsvariables(ifthechilddoesnotalreadyhaveit).Theprocessrepeats(thechildactsasroot)andcontinuesuntilallleavesreceivemessagesfromtheirparents.,OneCatchforDivision,Attimeswemayfindourselvesneedingtodivideby0.Wecanverifythatwheneverthisoccurs,wearedividing0by0.Wesimplyadopttheconventionthatforthisspecialcase,theresultwillbe0ratherthanundefined.接受约定，这种特殊情况下，结果将为0，而不是未定义。,BuildJunctionTreeforBNBelow,InferenceExample(assumenoevidence):GoingUp,StatusAfterUpwardPass,GoingBackDown,.194.231.260.315,StatusAfterDownwardPass,AnsweringQueries:FinalStep,Havingbuiltthejunctiontree,wenowcanaskaboutanyvariable.Wefindthecliquenodecontainingthatvariableandsumouttheothervariablestoobtainouranswer.Ifgivennewevidence,wemustrepeattheUpward-Downwardprocess.Ajunctiontreecanbethoughtofasstoringthesubjointscomputedduringelimination.,SignificanceofJunctionTrees,“onlywell-understood,efficient,provablycorrectmethodforconcurrentlycomputingmultiplequeries(AIMag99).”Asaresult,theyarethemostwidely-usedandwell-knownmethodofinferenceinBayesNets,althoughJunctiontreessoonmaybeovertakenbyapproximateinferenceusingMCMC.,TheLinkBetweenJunctionTreesandVariableElimination,Toeliminateavariableatanystep,wecombineallremainingdistributions(tables)indexedon(involving)thatvariable.Anodeinthejunctiontreecorrespondstothevaria