nips nips2003 nips2003-189 nips2003-189-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Yuan Qi, Tom Minka
Abstract: Approximation structure plays an important role in inference on loopy graphs. As a tractable structure, tree approximations have been utilized in the variational method of Ghahramani & Jordan (1997) and the sequential projection method of Frey et al. (2000). However, belief propagation represents each factor of the graph with a product of single-node messages. In this paper, belief propagation is extended to represent factors with tree approximations, by way of the expectation propagation framework. That is, each factor sends a “message” to all pairs of nodes in a tree structure. The result is more accurate inferences and more frequent convergence than ordinary belief propagation, at a lower cost than variational trees or double-loop algorithms. 1
Chow, C. K., & Liu, C. N. (1968). Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory, 14, 462–467. Frey, B. J., Patrascu, R., Jaakkola, T., & Moran, J. (2000). Sequentially fitting inclusive trees for inference in noisy-OR networks. NIPS 13. Ghahramani, Z., & Jordan, M. I. (1997). Factorial hidden Markov models. Machine Learning, 29, 245–273. Heskes, T., & Zoeter, O. (2002). Expectation propagation for approximate inference in dynamic Bayesian networks. Proc UAI. Jensen, F. V., Lauritzen, S. L., & Olesen, K. G. (1990). Bayesian updating in causal probabilistic networks by local computations. Computational Statistics Quarterly, 5, 269–282. Kappen, H. J., & Wiegerinck, W. (2001). Novel iteration schemes for the cluster variation method. NIPS 14. Minka, T. P. (2001a). Expectation propagation for approximate Bayesian inference. UAI (pp. 362– 369). Minka, T. P. (2001b). A family of algorithms for approximate Bayesian inference. Doctoral dissertation, Massachusetts Institute of Technology. Murphy, K. (2001). The Bayes Net Toolbox for Matlab. Computing Science and Statistics, 33. Teh, Y. W., & Welling, M. (2001). The unified propagation and scaling algorithm. NIPS 14. Wainwright, M. J., Jaakkola, T., & Willsky, A. S. (2001). Tree-based reparameterization for approximate estimation on loopy graphs. NIPS 14. Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S. (2002). A new class of upper bounds on the log partition function. Proc UAI. Welling, M., & Teh, Y. W. (2001). Belief optimization for binary networks: A stable alternative to loopy belief propagation. UAI. Wiegerinck, W. (2000). Variational approximations between mean field theory and the junction tree algorithm. Proc UAI. Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2000). Generalized belief propagation. NIPS 13. Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2002). Constructing free energy approximations and generalized belief propagation algorithms (Technical Report). MERL Research Lab. Yuille, A. (In press, 2002). A double-loop algorithm to minimize the Bethe and Kikuchi free energies. Neural Computation.