Abstract A message family propagation algorithm based on mean field computing tree for the Ising graphical model is proposed. Firstly the concepts of mean field computing tree and mean field pruned computing tree are defined to describe the iteration computation process of the mean field inference of the Ising graphical model. Next, the message family propagation algorithm based on the mean field computing trees is designed. The proposed algorithm propagates message families from bottom to top in the computing tree and computes the marginal distribution families of root random variables. Then, the marginal distribution bound theorem is proved, which shows that the marginal distribution families computed by the algorithm in the pruned computing tree contain the exact marginal distributions. Finally, the theoretical and experimental results show that the message family propagation algorithm is valid and the marginal distribution bounds are tight.
[1] Jordan M I.Graphical Models.Statistical Science,2004,19(1): 140-155 [2] Shao Chao,Huang Houkuan,Yu Jian.Parameter Estimation in Markov Random Field Based on Evolutionary Programming.Pattern Recognition and Artificial Intelligence,2006,19(2): 143-148 (in Chinese) (邵 超,黄厚宽,于 剑.基于进化规则的Markov随机场参数的估计.模式识别与人工智能,2006,19(2): 143-148) [3] Wainwright M J,Jordan M I.Graphical Models,Exponential Families,and Variational Inference.Foundations and Trends in Machine Learning,2008,1(1/2): 1-305 [4] Minka T.Divergence Measures and Message Passing.Technical Report,MSR-TR-2005-173.Cambridge,UK: Microsoft Research Ltd,2005 [5] Frey B J,MacKay D J.A Revolution: Belief Propagation in Graphs with Cycles // Jordan M I,Kearns M J,Solla S A,eds.Advances in Neural Information Processing Systems.Cambridge,USA: MIT Press,1997,X: 479-485 [6] Winn J,Bishop C M.Variational Message Passing.Journal of Machine Learning Research,2005,6: 661-694 [7] Minka T.Expectation Propagation for Approximate Bayesian Inference // Proc of the 17th Conference on Uncertainty in Artificial Intelligence.Seattle,USA,2001: 362-369 [8] Sutton C.Efficient Training Methods for Conditional Random Fields.Ph.D Dissertation.Amherst,USA: University of Massachusetts Amherst,2008 [9] Ihler A T.Accuracy Bounds for Belief Propagation // Proc of the 23rd Conference on Uncertainty in Artificial Intelligence.Corvallis,USA,2007: 183-190 [10] Chen Yarui,Liao Shizhong.Mean Field Interval Propagation Algorithm Based on Ising Computation Tree.Pattern Recognition and Artificial Intelligence,2010,23(2): 154-159 (in Chinese) (陈亚瑞,廖士中.基于Ising计算树的均值场区间传播算法.模式识别与人工智能,2010,23(2): 154-159) [11] Chen Yarui.Approximate Variational Inference in Graphical Model Based on Message Propagation.Ph.D Dissertation.Tianjin,China: Tianjin University,2011 (in Chinese) (陈亚瑞.基于消息传播的图模型近似变分推理.博士学位论文.天津:天津大学,2011) [12] Saul L K,Jaakkola T S,Jordan M I.Mean Field Theory for Sigmoid Belief Networks.Journal of Artificial Intelligence Research,1996,4(1): 61-76 [13] Xing E P,Jordan M I,Russell S.A Generalized Mean Field Algorithm for Variational Inference in Exponential Families // Proc of the 19th Conference on Uncertainty in Artificial Intelligence.Acapulco,Mexico,2003: 583-591
2012, Vol. 25 
