Abstract A mean filed interval propagation algorithm is designed based on incomplete functional iterations. This algorithm can yield the expectation bound of variables. Firstly, a concept of computation tree is proposed to reveal the iteration computation process of Ising mean field. Then, a mean field interval propagation algorithm based on the Ising computation tree is put forward, which propagates message intervals through the computation tree and presents the mean intervals of random variables in root node. It is proved that the variable mean interval computed by the interval propagation algorithm with 2-layer computation tree contains the exact value, called the mean bound of random variable. Finally, theoretical and experimental results show that the interval propagation algorithm is valid and the mean bound is tight.
[1] Parisi G. Statistical Field Theory. Redwood City ,USA: Addison-Wesley, 1988 [2] Shao Chao, Huang Houkuang, 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. Technical Report, 649, Berkeley, USA: University of California. Department of Statistics, 2003 [4] Sutton C, McCallum A. Piecewise Training for Undirected Models // Proc of the 21st Annual Conference on Uncertainty in Artificial Intelligence. Edinburgh, Scotland, 2005: 568-595 [5] Sutton C, Minka T. Local Training and Belief Propagation. Technical Report, MSR-TR-2006-121, Cambridge, UK: Microsoft Research Cambridge, 2006 [6] Sutton C. Efficient Training Methods for Conditional Random Fields. Ph.D Dissertation. Amherst, USA: University of Massachusetts Amherst. Department of Computer Science, 2008 [7] Ihler A T, Fisher III J W, Willsky A S. Message Errors in Belief Propagation // Saul L K, Weiss Y, Bottou L, eds. Advances in Neural Information Processing Systems. Cambridge, USA: MIT Press, 2005: 609-616 [8] Ihler A T. Accuracy Bounds for Belief Propagation // Proc of the 23th Conference on Uncertainty in Artificial Intelligence. Vancouver, Canada, 2007: 183-190 [9] Jordan M I, Ghahramani Z, Jaakkola T S, et al. An Introduction to Variational Methods for Graphical Models. Machine Learning, 1999, 37(2): 183-233 [10] Jordan M I, Weiss Y. Graphical Models: Probabilistic Inference // Arbib M A, ed. The Handbook of Brain Theory and Neural Networks. Cambridge, USA: MIT Press, 2002: 490-496 [11] Kuang Jichang. Applied Inequalities. Jinan, China: Shandong Science and Technology Press, 2004 (in Chinese) (匡继昌.常用不等式.济南:山东科学技术出版社, 2004)
2010, Vol. 23 
