nips nips2011 nips2011-296 nips2011-296-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Yusuke Watanabe
Abstract: While loopy Belief Propagation (LBP) has been utilized in a wide variety of applications with empirical success, it comes with few theoretical guarantees. Especially, if the interactions of random variables in a graphical model are strong, the behaviors of the algorithm can be difficult to analyze due to underlying phase transitions. In this paper, we develop a novel approach to the uniqueness problem of the LBP fixed point; our new “necessary and sufficient” condition is stated in terms of graphs and signs, where the sign denotes the types (attractive/repulsive) of the interaction (i.e., compatibility function) on the edge. In all previous works, uniqueness is guaranteed only in the situations where the strength of the interactions are “sufficiently” small in certain senses. In contrast, our condition covers arbitrary strong interactions on the specified class of signed graphs. The result of this paper is based on the recent theoretical advance in the LBP algorithm; the connection with the graph zeta function.
[1] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, San Mateo, CA, 1988. 8
[2] P.F. Felzenszwalb and D.P. Huttenlocher. Efficient belief propagation for early vision. International journal of computer vision, 70(1):41–54, 2006.
[3] D. Baron, S. Sarvotham, and R.G. Baraniuk. Bayesian compressive sensing via belief propagation. Signal Processing, IEEE Transactions on, 58(1):269–280, 2010.
[4] R.J. McEliece, D.J.C. MacKay, and J.F. Cheng. Turbo decoding as an instance of Pearl’s ”belief propagation” algorithm. IEEE J. Sel. Areas Commun., 16(2):140–52, 1998.
[5] S. Ikeda, T. Tanaka, and S. Amari. Stochastic reasoning, free energy, and information geometry. Neural Computation, 16(9):1779–1810, 2004.
[6] M.J. Wainwright and M.I. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 1(1-2):1–305, 2008.
[7] J.S. Yedidia, W.T. Freeman, and Y. Weiss. Generalized belief propagation. Adv. in Neural Information Processing Systems, 13:689–95, 2001.
[8] 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.
[9] A.L. Yuille and A. Rangarajan. The concave-convex procedure. Neural Computation, 15(4):915–936, 2003.
[10] Y.W. Teh, M. Welling, et al. The unified propagation and scaling algorithm. Advances in neural information processing systems, 2:953–960, 2002.
[11] T. Heskes. Convexity arguments for efficient minimization of the bethe and kikuchi free energies. Journal of Artificial Intelligence Research, 26(1):153–190, 2006.
[12] T. Heskes. On the uniqueness of loopy belief propagation fixed points. Neural Computation, 16(11):2379–2413, 2004.
[13] 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.
[14] 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.
[15] S. Tatikonda and M.I. Jordan. Loopy belief propagation and Gibbs measures. Uncertainty in AI, 18:493–500, 2002.
[16] Y. Watanabe and K. Fukumizu. Graph zeta function in the bethe free energy and loopy belief propagation. Adv. in Neural Information Processing Systems, 22:2017–2025, 2009.
[17] M. Kotani and T. Sunada. Zeta functions of finite graphs. J. Math. Sci. Univ. Tokyo, 7(1):7–25, 2000.
[18] K. Hashimoto. Zeta functions of finite graphs and representations of p-adic groups. Automorphic forms and geometry of arithmetic varieties, 15:211–280, 1989.
[19] H.M. Stark and A.A. Terras. Zeta functions of finite graphs and coverings. Advances in Mathematics, 121(1):124–165, 1996.
[20] Y. Watanabe and K. Fukumizu. Loopy belief propagation, Bethe free energy and graph zeta function. arXiv:1103.0605.
[21] D.M. Malioutov, J.K. Johnson, and A.S. Willsky. Walk-sums and belief propagation in Gaussian graphical models. The Journal of Machine Learning Research, 7:2064, 2006.
[22] Y. Weiss. Correctness of Local Probability Propagation in Graphical Models with Loops. Neural Computation, 12(1):1–41, 2000.
[23] Thomas Zaslavsky. Characterizations of signed graphs. Journal of Graph Theory, 5(4):401– 406, 1981. 9