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

《联合树j-tree算法过程简介》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、JunctionTrees:MotivationStandardalgorithms(e.g.,variableelimination)areinefficientiftheundirectedgraphunderlyingtheBayesNetcontainscycles.Wecanavoidcyclesifweturnhighly-interconnectedsubsetsofthenodesinto“supernodes.”如果贝叶斯网络底层的无向图中包含环，标准算法（如标量消元）是低效的。如果我们把节点的高度互联

2、的子集转变为“超级节点”，我们可以避开环的存在。ARunningExamplefortheStepsinConstructingaJunctionTreeStep1:MaketheGraphMoralStep2:RemoveDirectionalityStep3:TriangulatetheGraphStep3:TriangulatetheGraphStep3:TriangulatetheGraphIsitTriangulatedYet?TriangulationChecking上述的最大势算法（mcs算法，Maximu

3、mCardinalitySearch），实际上也是求是否存在完美消除序列的方法，存在完美消除序列即为弦图，反之不是，IsitTriangulatedYet?IsitTriangulatedYet?IsitTriangulatedYet?IsitTriangulatedYet?IsitTriangulatedYet?IsitTriangulatedYet?ItisNotTriangulatedFixingtheFaultyCycleContinuingourCheck...ContinuingourCheck...Fixi

4、ngthisProblemContinuingourCheck...TheFollowingisTriangulatedTriangulation:KeyPointsPreviousalgorithmisanefficientchecker,butnotnecessarilybestwaytotriangulate.Ingeneral,manytriangulationsmayexist.Theonlyefficientalgorithmsareheuristic.JensenandJensen(1994)showedt

5、hatanyschemeforexactinference(beliefupdatinggivenevidence)mustperformtriangulation(perhapshiddenasinDraper1995).DefinitionsCompletegraphornodeset:allnodesareadjacent.Clique:maximalcompletesubgraph.Simplicialnode:nodewhosesetofneighborsisacompletenodeset.Step4:Bui

6、ldCliqueGraphTheCliqueGraphJunctionTreesAjunctiontreeisasubgraphofthecliquegraphthat(1)isatree,(2)containsallthenodesofthecliquegraph,and(3)satisfiesthejunctiontreeproperty.Junctiontreeproperty:ForeachpairU,VofcliqueswithintersectionS,allcliquesonthepathbetweenUa

7、ndVcontainS.应该是其他文献中所说的变量连通性CliqueGraphtoJunctionTreeWecanperformexactinferenceefficientlyonajunctiontree(althoughCPTsmaybelarge).Butcanwealwaysbuildajunctiontree?Ifso,how?在联合树中，可以高效的进行精确推理（CPT：条件概率分布表）Lettheweightofanedgeinthecliquegraphbethecardinalityofthesepa

8、rator.Thananymaximumweightspanningtree（最大生成树）isajunctiontree(Jensen&Jensen1994).Step5:BuildtheJunctionTreeStep6:ChooseaRootStep7:PopulateCliqueNodesForeachdist