jmlr jmlr2013 jmlr2013-71 jmlr2013-71-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nicholas Ruozzi, Sekhar Tatikonda
Abstract: Gaussian belief propagation (GaBP) is an iterative algorithm for computing the mean (and variances) of a multivariate Gaussian distribution, or equivalently, the minimum of a multivariate positive definite quadratic function. Sufficient conditions, such as walk-summability, that guarantee the convergence and correctness of GaBP are known, but GaBP may fail to converge to the correct solution given an arbitrary positive definite covariance matrix. As was observed by Malioutov et al. (2006), the GaBP algorithm fails to converge if the computation trees produced by the algorithm are not positive definite. In this work, we will show that the failure modes of the GaBP algorithm can be understood via graph covers, and we prove that a parameterized generalization of the min-sum algorithm can be used to ensure that the computation trees remain positive definite whenever the input matrix is positive definite. We demonstrate that the resulting algorithm is closely related to other iterative schemes for quadratic minimization such as the Gauss-Seidel and Jacobi algorithms. Finally, we observe, empirically, that there always exists a choice of parameters such that the above generalization of the GaBP algorithm converges. Keywords: belief propagation, Gaussian graphical models, graph covers
C. L. Byrne. Applied Iterative Methods. A K Peters, Ltd., 2008. B. J. Frey, R. Koetter, and A. Vardy. Signal-space characterization of iterative decoding. Information Theory, IEEE Transactions on, 47(2):766–781, Feb. 2001. A. Globerson and T. S. Jaakkola. Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. In Proc. Neural Information Processing Systems (NIPS), Vancouver, B. C., Canada, Dec. 2007. T. Hazan and A. Shashua. Norm-product belief propagation: Primal-dual message-passing for approximate inference. Information Theory, IEEE Transactions on, 56(12):6294 –6316, Dec. 2010. R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 1990. J. K. Johnson, D. Bickson, and D. Dolev. Fixing convergence of Gaussian belief propagation. In Proc. Information Theory, IEEE International Symposium on (ISIT), pages 1674–1678, Seoul, South Korea, July 2009. D. M. Malioutov. Approximate inference in Gaussian graphical models. Ph.D. thesis, EECS, MIT, 2008. D. M. Malioutov, J. K. Johnson, and A. S. Willsky. Walk-sums and belief propagation in Gaussian graphical models. Journal of Machine Learning Research (JMLR), 7:2031–2064, 2006. 2312 M ESSAGE -PASSING A LGORITHMS FOR Q UADRATIC M INIMIZATION T. Meltzer, A. Globerson, and Y. Weiss. Convergent message passing algorithms: a unifying view. In Proc. of the 25th Conference on Uncertainty in Artificial Intelligence (UAI), Montreal, Canada, June 2009. C. C. Moallemi and B. Van Roy. Convergence of min-sum message passing for quadratic optimization. Information Theory, IEEE Transactions on, 55(5):2413 –2423, May 2009. C. C. Moallemi and B. Van Roy. Convergence of min-sum message-passing for convex optimization. Information Theory, IEEE Transactions on, 56(4):2041 –2050, April 2010. N. Ruozzi, J. Thaler, and S. Tatikonda. Graph covers and quadratic minimization. In Proc. Communication, Control, and Computing, 47th Annual Allerton Conference on, Allerton, IL, Sept. 2009. D. Sontag and T. S. Jaakkola. Tree block coordinate descent for MAP in graphical models. In Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS), Clearwater Beach, Florida, April 2009. S. Tatikonda and M. I. Jordan. Loopy belief propagation and Gibbs measures. In Proc. of the Conference on Uncertainty in Artificial Intelligence (UAI), pages 493–500, Edmonton, Alberta, Canada, 2002. P. O. Vontobel and R. Koetter. Graph-cover decoding and finite-length analysis of message-passing iterative decoding of LDPC codes. CoRR, abs/cs/0512078, 2005. M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky. Tree-based reparameterization framework for analysis of sum-product and related algorithms. Information Theory, IEEE Transactions on, 49 (5):1120 – 1146, May 2003a. M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky. Tree-reweighted belief propagation algorithms and approximate ML estimation via pseudo-moment matching. In Proceedings of the 9th International Conference on Artificial Intelligence and Statistics (AISTATS), Key West, Florida, Jan. 2003b. M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky. Tree consistency and bounds on the performance of the max-product algorithm and its generalizations. Statistics and Computing, 14(2): 143–166, 2004. M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky. MAP estimation via agreement on (hyper)trees: message-passing and linear programming. Information Theory, IEEE Transactions on, 51(11): 3697–3717, Nov. 2005. Y. Weiss. Correctness of local probability propagation in graphical models with loops. Neural Comput., 12(1):1–41, 2000. Y. Weiss and W. T. Freeman. On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs. Information Theory, IEEE Transactions on, 47(2):736 –744, Feb. 2001a. 2313 RUOZZI AND TATIKONDA Y. Weiss and W. T. Freeman. Correctness of belief propagation in Gaussian graphical models of arbitrary topology. Neural Comput., 13(10):2173–2200, Oct. 2001b. T. Werner. A linear programming approach to max-sum problem: A review. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 29(7):1165–1179, 2007. 2314