图模型推理的层次消息传递算法

《图模型推理的层次消息传递算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图模型推理的层次消息传递算法孙怿欧智坚孙甲松清华大学电子工程系北京100084摘要：本文提出了用于图模型精确推理的层次消息传递（HierarchicalMessagePassing，HMP）算法以及包含树（ContainingTree）算法，以解决传统连接树算法在存在约束包含和约束消除情况下无法充分利用图模型中的结构信息的问题。HMP算法采用递归结构，逐级挖掘图模型具有的条件独立性以减小推理计算量；包含树算法利用势函数定义域之间的包含关系，有效的降低推理所需的乘法次数。理论分析和实验结果均表明，HMP算法和包含树算法能够显著地降低在存在

2、约束包含和约束消除情况下的推理计算量。关键字：图模型推理、层次消息传递算法、包含树算法HierarchicalMessagePassingAlgorithmforGraphicalModelsSUNYi,OUZhijianandSUNJiasongDepartmentofElectronicEngineering,TsinghuaUniversity100084,Beijing,ChinaAbstract:Inthispaper,weproposeHierarchicalMessagePassing(HMP)algorithmforef

3、ficientinferenceonGraphicalModels,whichexploitsthevariable-levelstructuralinformationcontainedinthegraphthoroughlyinarecursiveway.Specifically,eachstepofmessagepassinginareasoningproblem(i.e.marginalizingaproductfunction)istreatedasasmallerreasoningproblem,andweintroduce

4、containingtreeasanefficientstructureformarginalizingoverasinglecluster(thelowest-levelproblem).WedemonstratethatHMPcanbeorder-of-magnitudebetterthantypicalalgorithmsbasedonShenoy-Shaferarchitecture,especiallywhenoperatingoncluster-treesconstructedunderconstraints.Experim

5、entalresultswithvariousrandomgraphsshowthatHMPachievessignificantperformanceimprovementsoverbasicShenoy-Shaferalgorithmandlazypropagation.Keywords:graphicalmodelinference,hierarchicalmessagepassing,containingtree1引言[1][2]连接树算法是图模型推理中一类重要的算法。这类算法首先在图模型上构造连接树[3][4]（JoinTre

6、e）或与之等价的树结构（BucketTree、JunctionTree等），而后在连接树上进行。消息传递（MessagePassing），进而求解连接树各节点上变量集合的边缘分布连接树算法的效率依赖于输入图模型自身的结构和连接树的构造方法。当输入的图模型[9]规模较小时，现有的连接树构造算法可以构造出宽度接近图模型树宽的连接树，使得连接树算法具有良好的性能。然而，在一些情况下，无法构造出宽度较小的连接树。首先，一大类图模型上的推理任务需要求解给定变量集合上的边缘分布。在这种情况下，连接树必须根据特定的推理任务构造，将给定变量集合置于同一

7、个连接树节点中以求得它们的联合概率密度（我们称之为约束包含，ConstrainedInclusion）。其次，对于一些特定的图模型，必须利用约束消除（ConstrainedElimination）以满足特定的复杂度约束。特别的，在动态贝叶斯网[5;6]络推理中，每帧中的界面变量集（InterfaceSet）的消除必须在该帧中其它变量之前被消除。在这些情况下，用于构造连接树的图模型不再是输入的原始图模型，而是一个在原有图模型基础上加入大量虚边（VirtualEdge）的图模型。这些虚边的引入保证了构造出的连接树能够满足特定的推理任务要求。

8、在引入虚边后的图模型中，一部分条件独立性（ConditionalIndependence）被引入的虚边破坏，因此引入虚边后的图模型的树宽往往比原有的图模型高得多，相应的，在引入虚边后的图模型上构造的连接树的