nips nips2001 nips2001-188 nips2001-188-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Yee W. Teh, Max Welling
Abstract: In this paper we will show that a restricted class of constrained minimum divergence problems, named generalized inference problems, can be solved by approximating the KL divergence with a Bethe free energy. The algorithm we derive is closely related to both loopy belief propagation and iterative scaling. This unified propagation and scaling algorithm reduces to a convergent alternative to loopy belief propagation when no constraints are present. Experiments show the viability of our algorithm.
[1] J. Pearl. Probabilistic reasoning in intelligent systems : networks of plausible inference. Morgan Kaufmann Publishers, San Mateo CA, 1988. (a) Ordinary Inference (c) σ(α) = 0.2 (b) No Obs Constraints (d) σ(α) = 2.0 0.4 loopy IS 9 7 5 3 1 0.2 9 UPS 7 5 3 1 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 Figure 2: Each plot shows the mean absolute errors for various settings of 5 7 0 9 (x-axis) and (yaxis). The top plots show errors for loopy IS and bottom plots show errors for UPS. The inset shows the cases (black) when loopy IS did not converge within 2000 iterations, with linear damping slowly . increasing to ' ¡ ¢ £ ¤£ D F
[2] J.S. Yedidia, W. Freeman, and Y. Weiss. Generalized belief propagation. In Advances in Neural Information Processing Systems, volume 13, 2000.
[3] W. E. Deming and F. F. Stephan. On a least square adjustment of a sampled frequency table when the expected marginal totals are known. Annals of Mathematical Statistics, 11:427–444, 1940.
[4] J. Darroch and D. Ratcliff. Generalized iterative scaling for log-linear models. Annals of Mathematical Statistics, 43:1470–1480, 1972.
[5] K. Murphy, Y. Weiss, and M. Jordan. Loopy belief propagation for approximate inference : An empirical study. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, volume 15. Morgan Kaufmann Publishers, 1999.
[6] M. Welling and Y. W. Teh. Belief optimization for binary networks : A stable alternative to loopy belief propagation. In Uncertainty in Artificial Intelligence, 2001.
[7] A. L. Yuille. CCCP algorithms to minimize the Bethe and Kikuchi free energies: Convergent alternatives to belief propagation. 2002.