nips nips2003 nips2003-117 nips2003-117-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Max Welling, Yee W. Teh
Abstract: Belief propagation on cyclic graphs is an efficient algorithm for computing approximate marginal probability distributions over single nodes and neighboring nodes in the graph. In this paper we propose two new algorithms for approximating joint probabilities of arbitrary pairs of nodes and prove a number of desirable properties that these estimates fulfill. The first algorithm is a propagation algorithm which is shown to converge if belief propagation converges to a stable fixed point. The second algorithm is based on matrix inversion. Experiments compare a number of competing methods.
[1] T. Heskes. Stable fixed points of loopy belief propagation are minima of the bethe free energy. In Advances in Neural Information Processing Systems, volume 15, Vancouver, CA, 2003.
[2] H.J. Kappen and F.B. Rodriguez. Efficient learning in Boltzmann machines using linear response theory. Neural Computation, 10:1137–1156, 1998.
[3] F.R. Kschischang, B. Frey, and H.A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2):498–519, 2001.
[4] M. Opper and O. Winther. From naive mean field theory to the TAP equations. In Advanced Mean Field Methods – Theory and Practice. MIT Press, 2001.
[5] K. Tanaka. Probabilistic inference by means of cluster variation method and linear response theory. IEICE Transactions in Information and Systems, E86-D(7):1228–1242, 2003.
[6] Y.W. Teh and M. Welling. The unified propagation and scaling algorithm. In Advances in Neural Information Processing Systems, 2001.
[7] M.J. Wainwright and M.I. Jordan. Semidefinite relaxations for approximate inference on graphs with cycles. Technical report, Computer Science Division, University of California Berkeley, 2003. Rep. No. UCB/CSD-3-1226.
[8] M. Welling and Y.W. Teh. Approximate inference in boltzmann machines. Artificial Intelligence, 143:19–50, 2003.
[9] M. Welling and Y.W. Teh. Linear response algorithms for approximate inference in graphical models. Neural Computation, 16:197–221, 2004.
[10] J.S. Yedidia, W. Freeman, and Y. Weiss. Generalized belief propagation. In Advances in Neural Information Processing Systems, volume 13, 2000.
[11] 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.