nips nips2009 nips2009-103 nips2009-103-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Yusuke Watanabe, Kenji Fukumizu
Abstract: We propose a new approach to the analysis of Loopy Belief Propagation (LBP) by establishing a formula that connects the Hessian of the Bethe free energy with the edge zeta function. The formula has a number of theoretical implications on LBP. It is applied to give a sufficient condition that the Hessian of the Bethe free energy is positive definite, which shows non-convexity for graphs with multiple cycles. The formula clarifies the relation between the local stability of a fixed point of LBP and local minima of the Bethe free energy. We also propose a new approach to the uniqueness of LBP fixed point, and show various conditions of uniqueness. 1
[1] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, San Mateo, CA, 1988.
[2] K. Murphy, Y. Weiss, and M.I. Jordan. Loopy belief propagation for approximate inference: An empirical study. Proc. of Uncertainty in AI, 15:467–475, 1999.
[3] J.S. Yedidia, W.T. Freeman, and Y. Weiss. Generalized belief propagation. Adv. in Neural Information Processing Systems, 13:689–95, 2001.
[4] Y. Weiss. Correctness of Local Probability Propagation in Graphical Models with Loops. Neural Computation, 12(1):1–41, 2000.
[5] T. Heskes. On the uniqueness of loopy belief propagation fixed points. Neural Computation, 16(11):2379–2413, 2004.
[6] T. Heskes. Stable fixed points of loopy belief propagation are minima of the Bethe free energy. Adv. in Neural Information Processing Systems, 15, pages 343–350, 2002.
[7] K. Hashimoto. Zeta functions of finite graphs and representations of p-adic groups. Automorphic forms and geometry of arithmetic varieties, 15:211–280, 1989.
[8] H.M. Stark and A.A. Terras. Zeta functions of finite graphs and coverings. Advances in Mathematics, 121(1):124–165, 1996.
[9] Y. Ihara. On discrete subgroups of the two by two projective linear group over p-adic fields. Journal of the Mathematical Society of Japan, 18(3):219–235, 1966.
[10] H. Bass. The Ihara-Selberg zeta function of a tree lattice. Internat. J. Math, 3(6):717–797, 1992.
[11] P. Pakzad and V. Anantharam. Belief propagation and statistical physics. Conference on Information Sciences and Systems, (225), 2002.
[12] R.A. Horn and C.R. Johnson. Matrix analysis. Cambridge University Press, 1990.
[13] K. Hashimoto. On zeta and L-functions of finite graphs. Internat. J. Math, 1(4):381–396, 1990.
[14] JM Mooij and HJ Kappen. On the properties of the Bethe approximation and loopy belief propagation on binary networks. Journal of Statistical Mechanics: Theory and Experiment, (11):P11012, 2005.
[15] S. Ikeda, T. Tanaka, and S. Amari. Information geometry of turbo and low-density parity-check codes. IEEE Transactions on Information Theory, 50(6):1097–1114, 2004.
[16] C. Furtlehner, J.M. Lasgouttes, and A. De La Fortelle. Belief propagation and Bethe approximation for traffic prediction. INRIA RR-6144, Arxiv preprint physics/0703159, 2007.
[17] A.T. Ihler, JW Fisher, and A.S. Willsky. Loopy belief propagation: Convergence and effects of message errors. Journal of Machine Learning Research, 6(1):905–936, 2006.
[18] J. M. Mooij and H. J. Kappen. Sufficient Conditions for Convergence of the Sum-Product Algorithm. IEEE Transactions on Information Theory, 53(12):4422–4437, 2007.
[19] S. Tatikonda and M.I. Jordan. Loopy belief propagation and Gibbs measures. Uncertainty in AI, 18:493–500, 2002.
[20] B.A. Dubrovin, A.T. Fomenko, S.P. Novikov, and Burns R.G. Modern Geometry: Methods and Applications: Part 2: the Geometry and Topology of Manifolds . Springer-Verlag, 1985.
[21] R. Koetter, W.C.W. Li, PO Vontobel, and JL Walker. Pseudo-codewords of cycle codes via zeta functions. IEEE Information Theory Workshop, pages 6–12, 2004.
[22] R. Koetter, W.C.W. Li, P.O. Vontobel, and J.L. Walker. Characterizations of pseudo-codewords of (low-density) parity-check codes. Advances in Mathematics, 213(1):205–229, 2007.
[23] J.K. Johnson, V.Y. Chernyak, and M. Chertkov. Orbit-Product Representation and Correction of Gaussian Belief Propagation. Proceedings of the 26th International Conference on Machine Learning, (543), 2009. 9