nips nips2012 nips2012-213 nips2012-213-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jason Pacheco, Erik B. Sudderth
Abstract: We develop convergent minimization algorithms for Bethe variational approximations which explicitly constrain marginal estimates to families of valid distributions. While existing message passing algorithms define fixed point iterations corresponding to stationary points of the Bethe free energy, their greedy dynamics do not distinguish between local minima and maxima, and can fail to converge. For continuous estimation problems, this instability is linked to the creation of invalid marginal estimates, such as Gaussians with negative variance. Conversely, our approach leverages multiplier methods with well-understood convergence properties, and uses bound projection methods to ensure that marginal approximations are valid at all iterations. We derive general algorithms for discrete and Gaussian pairwise Markov random fields, showing improvements over standard loopy belief propagation. We also apply our method to a hybrid model with both discrete and continuous variables, showing improvements over expectation propagation. 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, 2005.
[2] M. J. Wainwright and M. I. Jordan. Graphical models, exponential families, and variational inference. Technical report, UC Berkeley, Dept. of Statistics, 2003.
[3] T. P. Minka. Expectation Propagation for approximate Bayesian inference. Uncertainty in Artificial Intelligence, 17:362–369, 2001.
[4] Tom Heskes, Wim Wiegerinck, Ole Winther, and Onno Zoeter. Approximate inference techniques with expectation constraints. Journal of Statistical Mechanics: Theory and Experiment, page 11015, 2005.
[5] Dmitry M. Malioutov, Jason K. Johnson, and Alan S. Willsky. Walk-sums and Belief Propagation in Gaussian graphical models. Journal of Machine Learning Research, 7:2031–2064, 2006.
[6] B. Cseke and T. Heskes. Properties of bethe free energies and message passing in Gaussian models. Journal of Artificial Intelligence Research, 41(2):1–24, 2011.
[7] A. Yuille. CCCP algorithms to minimize the Bethe and Kikuchi free energies: Convergent alternatives to Belief Propagation. Neural Computation, 14:1691–1722, 2002.
[8] B. Kappen T. Heskes, K. Albers. Approximate inference and constrained optimization. Uncertainty in Artificial Intelligence, 13:313–320, 2003.
[9] Martin J. Wainwright, Tommi S. Jaakkola, and Alan S. Willsky. Tree-reweighted Belief Propagation algorithms and approximate ML estimation by pseudo-moment matching. In In AISTATS, 2003.
[10] M. Welling and Y.W. Teh. Belief optimization for binary networks: A stable alternative to Loopy Belief Propagation. In Uncertainty in Artificial Intelligence, 2001.
[11] T. Heskes and O. Zoeter. Expectation Propagation for approximate inference in dynamic Bayesian networks. Uncertainty in Artificial Intelligence, 18:216–223, 2002.
[12] T. Minka. The EP energy function and minimization schemes. Technical report, MIT Media Lab, 2001.
[13] D.P. Bertsekas. Nonlinear programming. Athena Scientific, 1999.
[14] M. Seeger. Bayesian inference and optimal design for the sparse linear model. Journal of Machine Learning Research, 9:759–813, 2008.
[15] C. Rasmussen. Gaussian Processes for Machine Learning. MIT Press, 2006.
[16] M. Schmidt, E. Van Den Berg, M. Friedlander, and K. Murphy. Optimizing costly functions with simple constraints: A limited-memory projected quasi-Newton algorithm. In AI & Statistics, 2009.
[17] D.P. Bertsekas. Constrained optimization and Lagrange multiplier methods. Computer Science and Applied Mathematics, Boston: Academic Press, 1982, 1, 1982.
[18] T. Heskes. On the uniqueness of loopy belief propagation fixed points. Neural Computation, 16(11):2379–2413, 2004.
[19] J.S. Yedidia, W.T. Freeman, and Y. Weiss. Generalized Belief Propagation. Advances in neural information processing systems, pages 689–695, 2001.
[20] Joris M. Mooij. libDAI: A free and open source C++ library for discrete approximate inference in graphical models. Journal of Machine Learning Research, 11:2169–2173, August 2010. 9