jmlr jmlr2007 jmlr2007-86 jmlr2007-86-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Vicenç Gómez, Joris M. Mooij, Hilbert J. Kappen
Abstract: Recently, Chertkov and Chernyak (2006b) derived an exact expression for the partition sum (normalization constant) corresponding to a graphical model, which is an expansion around the belief propagation (BP) solution. By adding correction terms to the BP free energy, one for each “generalized loop” in the factor graph, the exact partition sum is obtained. However, the usually enormous number of generalized loops generally prohibits summation over all correction terms. In this article we introduce truncated loop series BP (TLSBP), a particular way of truncating the loop series of Chertkov & Chernyak by considering generalized loops as compositions of simple loops. We analyze the performance of TLSBP in different scenarios, including the Ising model on square grids and regular random graphs, and on PROMEDAS, a large probabilistic medical diagnostic system. We show that TLSBP often improves upon the accuracy of the BP solution, at the expense of increased computation time. We also show that the performance of TLSBP strongly depends on the degree of interaction between the variables. For weak interactions, truncating the series leads to significant improvements, whereas for strong interactions it can be ineffective, even if a high number of terms is considered. Keywords: belief propagation, loop calculus, approximate inference, partition function, Ising grid, random regular graphs, medical diagnosis
M. Chertkov and V. Y. Chernyak. Loop calculus helps to improve belief propagation and linear programming decodings of LDPC codes. In Invited Talk at the 44th Allerton Conference, September 2006a. URL http://www.arxiv.org/abs/cs/0609154. M. Chertkov and V. Y. Chernyak. Loop series for discrete statistical models on graphs. Journal of Statistical Mechanics: Theory and Experiment, 2006(06):P06009, 2006b. URL http://arxiv.org/abs/cond-mat/0601487. G. Elidan, I. McGraw, and D. Koller. Residual belief propagation: Informed scheduling for asynchronous message passing. In Proceedings of the 22nd Annual Conference on Uncertainty in Artificial Intelligence (UAI-06), Boston, Massachussetts, July 2006. AUAI Press. 2013 ´ G OMEZ , M OOIJ , AND K APPEN W. T. Freeman, E. C. Pasztor, and O. T. Carmichael. Learning low-level vision. International Journal of Computer Vision, 40(1):25–47, October 2000. R. G. Gallagher. Low-density Parity Check Codes. MIT Press, 1963. ISBN 978-0262571777. T. Heskes, K. Albers, and H. J. Kappen. Approximate inference and constrained optimization. In Proceedings of the 19th Annual conference on Uncertainty in Artificial Intelligence (UAI-03), pages 313–320, San Francisco, CA, 2003. Morgan Kaufmann Publishers. T. Jaakkola and M. I. Jordan. Variational probabilistic inference and the QMR-DT network. Journal of Artificial Intelligence Research, 10:291–322, 1999. D. B. Johnson. Finding all the elementary circuits of a directed graph. SIAM Journal on Computing, 4(1):77–84, 1975. M. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. Saul. An introduction to variational methods for graphical models. In Learning in Graphical Models, pages 105–161. Cambridge, MA: MIT Press, 1999. F. R. Kschischang, B. J. Frey, and H.-A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2):498–519, February 2001. S. L. Lauritzen and D. J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical society. Series B-Methodological, 50(2):154–227, 1988. M. A. R. Leisink and H. J. Kappen. A tighter bound for graphical models. Neural Computation, 13 (9):2149–2171, 2001. ISSN 0899-7667. D. Malioutov, J. Johnson, and A. Willsky. Walk-sums and belief propagation in gaussian graphical models. Journal of Machine Learning Research, 7(Oct):2031–2064, 2006. R. McEliece, D. J. C. MacKay, and J. Cheng. Turbo decoding as an instance of Pearl’s belief propagation algorithm. Journal on Selected Areas of Communication, 16(2):140–152, 1998. M. M´ zard, G. Parisi, and R. Zecchina. e Analytic and algorithmic solution of random satisfiability problems. Science, 297(5582):812–815, August 2002. URL http://www.sciencemag.org/cgi/content/abstract/297/5582/812. A. Montanari and T. Rizzo. How to compute loop corrections to the Bethe approximation. Journal of Statistical Mechanics: Theory and Experiment, 2005(10):P10011, 2005. URL http://arxiv.org/abs/cond-mat/0506769. J. M. Mooij and H. J. Kappen. On the properties of the Bethe approximation and loopy belief propagation on binary networks. Journal of Statistical Mechanics: Theory and Experiment, 2005 (11):P11012, 2005. J. M. Mooij and H. J. Kappen. Loop corrections for approximate inference on factor graphs. Journal of Machine Learning Research, 8(May):1113–1143, 2007. URL http://arxiv.org/abs/cs/0612030. 2014 T RUNCATING THE L OOP S ERIES E XPANSION FOR BP J. M. Mooij, B. Wemmenhove, H. J. Kappen, and T. Rizzo. Loop corrected belief propagation. In Proceedings of the 11th International Conference on Artificial Intelligence and Statistics (AISTATS-07), 2007. K. P. Murphy, Y. Weiss, and M. I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In Proceedings of the 15th Annual Conference on Uncertainty in Artificial Intelligence (UAI-99). Morgan Kaufmann Publishers, 1999. J. Parisi and F. Slanina. Loop expansion around the Bethe-Peierls approximation for lattice models. Journal of Statistical Mechanics: Theory and Experiment, 2006(02):L02003. URL http://stacks.iop.org/1742-5468/2006/L02003. J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, San Francisco, CA, 1988. ISBN 1558604790. A. Pelizzola. Cluster variation method in statistical physics and probabilistic graphical models. Journal of Physics A: Mathematical and General, 38(33):R309–R339(1), August 2005. URL http://arxiv.org/abs/cond-mat/0508216. G. Potamianos and J. Goutsias. Stochastic approximation algorithms for partition function estimation of Gibbs random fields. IEEE Transactions on Information Theory, 43(6):1948–1965, November 1997. M. A. Shwe, B. Middleton, D. E. Heckerman, M. Henrion, E. J. Horvitz, H. P. Lehman, and G. F. Cooper. Probabilistic diagnosis using a reformulation of the INTERNIST-1/QMR knowledge base. I. The probabilistic model and inference algorithms. Methods of Information in Medicine, 30(4):241–55, October 1991. J. Sun, Y. Li, S. B. Kang, and H. Y. Shum. Symmetric stereo matching for occlusion handling. In Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR-05), volume 2, pages 399–406, Washington, DC, USA, 2005. IEEE Computer Society. M. Takinawa and B. D’Ambrosio. Multiplicative factorization of noisy-MAX. In Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI-99), pages 622–30, San Francisco, CA, 1999. Morgan Kaufmann. R. E. Tarjan. Enumeration of the elementary circuits of a directed graph. SIAM Journal on Computing, 2(3):211–216, 1973. J. C. Tiernan. An efficient search algorithm to find the elementary circuits of a graph. Communications of the ACM, 13(12):722–726, 1970. M. Wainwright, T. Jaakkola, and A. Willsky. A new class of upper bounds on the log partition function. IEEE Transactions on Information Theory, 51(7):2313–2335, July 2005. M. Welling, T. Minka, and Y. W. Teh. Structured region graphs: Morphing EP into GBP. In Proceedings of the 21th Annual Conference on Uncertainty in Artificial Intelligence (UAI-05), page 609, Arlington, Virginia, 2005. AUAI Press. 2015 ´ G OMEZ , M OOIJ , AND K APPEN W. Wiegerinck, H. J. Kappen, E. W. M. T. ter Braak, W. J. P. P. Burg, M. J. Nijman, Y. L. O, and J. P. Neijt. Approximate inference for medical diagnosis. Pattern Recognition Letters, 20(11): 1231–1239(9), 1999. J. S. Yedidia, W. T. Freeman, and Y. Weiss. Generalized belief propagation. In T.K. Leen, T.G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13 (NIPS00), pages 689–695, December 2000. J. S. Yedidia, W. T. Freeman, Y. Weiss, and A. L. Yuille. Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Transactions on Information Theory, 51(7): 2282–2312, July 2005. A. L. Yuille. CCCP algorithms to minimize the Bethe and Kikuchi free energies: Convergent alternatives to belief propagation. Neural Computation, 14(7):1691–1722, 2002. ISSN 08997667. S. Zilberstein. Using anytime algorithms in intelligent systems. AI magazine, 17(3):73–83 (1p.1/4), 1996. ISSN 0738–4602. 2016