nips nips2012 nips2012-335 nips2012-335-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nicholas Ruozzi
Abstract: Sudderth, Wainwright, and Willsky conjectured that the Bethe approximation corresponding to any fixed point of the belief propagation algorithm over an attractive, pairwise binary graphical model provides a lower bound on the true partition function. In this work, we resolve this conjecture in the affirmative by demonstrating that, for any graphical model with binary variables whose potential functions (not necessarily pairwise) are all log-supermodular, the Bethe partition function always lower bounds the true partition function. The proof of this result follows from a new variant of the “four functions” theorem that may be of independent interest. 1
[1] J. S. Yedidia, W. T. Freeman, and Y. Weiss. Constructing free-energy approximations and generalized belief propagation algorithms. Information Theory, IEEE Transactions on, 51(7):2282 – 2312, July 2005.
[2] E. B. Sudderth, M. J. Wainwright, and A. S. Willsky. Loop series and Bethe variational bounds in attractive graphical models. In Neural Information Processing Systems (NIPS), Vancouver, BC, Canada, Dec. 2007.
[3] M. Chertkov and V. Y. Chernyak. Loop series for discrete statistical models on graphs. J. Stat. Mech., 2006.
[4] V. G´ mez, J. M. Mooij, and H. J. Kappen. Truncating the loop series expansion for BP. Journal o of Machine Learning Research (JMLR), 2007.
[5] P. O. Vontobel. Counting in graph covers: A combinatorial characterization of the Bethe entropy function. CoRR, abs/1012.0065, 2010.
[6] P. O. Vontobel and R. Koetter. Graph-cover decoding and finite-length analysis of messagepassing iterative decoding of LDPC codes. CoRR, abs/cs/0512078, 2005.
[7] R. Ahlswede and D. E. Daykin. An inequality for the weights of two families of sets, their unions and intersections. Probability Theory and Related Fields, 43:183–185, 1978.
[8] N. Alon and J.H. Spencer. The probabilistic method. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 2000.
[9] R. Aharoni and U. Keich. A generalization of the Ahlswede-Daykin inequality. Discrete Mathematics, 152(13):1 – 12, 1996.
[10] Y. Rinott and M. Saks. Correlation inequalities and a conjecture for permanents. Combinatorica, 13:269–277, 1993.
[11] Y. Rinott and M. Saks. On FKG-type and permanental inequalities. Lecture Notes-Monograph Series, 22:pp. 332–342, 1992.
[12] A. W. Marshall and I. Olkin. Inequalities: Theory of Majorization and its Applications. Academic Press, New York, 1979.
[13] P. O. Vontobel. The Bethe permanent of a non-negative matrix. In Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference on, pages 341 –346, Oct. 2010.
[14] L. Gurvits. Unleashing the power of Schrijver’s permanental inequality with the help of the Bethe approximation. ArXiv e-prints, June 2011. 9