Divergence measures and message passing
Published 1 January 2005
Thomas P. Minka
Citations460
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper presents a unifying view of messagepassing algorithms, as methods to approximate a complex Bayesian network by a simpler network with minimum information divergence.
Abstract
This paper presents a unifying view of messagepassing algorithms, as methods to approximate a complex Bayesian network by a simpler network with minimum information divergence. In this view, the difference between mean-field methods and belief propagation is not the amount of structure they model, but only the measure of loss they minimize (‘exclusive ’ versus ‘inclusive’ Kullback-Leibler divergence). In each case, message-passing arises by minimizing a localized version of the divergence, local to each factor. By examining these divergence measures, we can intuit the types of solution they prefer (symmetry-breaking, for example) and their suitability for different tasks. Furthermore, by considering a wider variety of divergence measures (such as alpha-divergences), we can achieve different complexity and performance goals. 1
Keywords
Computer SciencePhysics and Astronomy
Machine LearningAn Introduction to Variational Methods for Graphical Models
3,775 Citations1999Michael I. Jordan, Zoubin Ghahramani +2 more
This paper presents a tutorial introduction to the use of variational methods for inference and learning in graphical models (Bayesian networks and Markov random fields), and describes a general framework for generating variational transformations based on convex duality.
Learning in Graphical Models
2,416 Citations1998Michael I. Jordan
Lecture notes in statisticsDifferential-Geometrical Methods in Statistics
1,647 Citations1985Шун-ичи Амари
IEEE Transactions on Information TheoryConstructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
1,627 Citations2005Jonathan S. Yedidia, William T. Freeman +1 more
This work explains how to obtain region-based free energy approximations that improve the Bethe approximation, and corresponding generalized belief propagation (GBP) algorithms, and describes empirical results showing that GBP can significantly outperform BP.
arXiv (Cornell University)Expectation Propagation for approximate Bayesian inference
1,457 Citations2013Thomas P. Minka
Journal of the Royal Statistical Society Series B (Statistical Methodology)A General Class of Coefficients of Divergence of One Distribution from Another
1,230 Citations1966Syed Mustafa Ali, S. D. Silvey
IEEE Transactions on Information TheoryMAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
670 Citations2005Martin J. Wainwright, Tommi Jaakkola +1 more
This work develops and analyze methods for computing provably optimal maximum a posteriori probability (MAP) configurations for a subclass of Markov random fields defined on graphs with cycles and establishes a connection between a certain LP relaxation of the mode-finding problem and a reweighted form of the max-product (min-sum) message-passing algorithm.
Journal of Machine Learning ResearchVariational Message Passing
644 Citations2005John Winn, Chris Bishop
Variational Message Passing is introduced, a general purpose algorithm for applying variational inference to Bayesian Networks and can be applied to very general class of conjugate-exponential models because it uses a factorised variational approximation.
IEEE Transactions on Information TheoryA New Class of Upper Bounds on the Log Partition Function
401 Citations2005Martin J. Wainwright, Tommi Jaakkola +1 more
A new class of upper bounds on the log partition function of a Markov random field (MRF) is introduced, based on concepts from convex duality and information geometry, and the Legendre mapping between exponential and mean parameters is exploited.
A Revolution: Belief Propagation in Graphs with Cycles
291 Citations1997Brendan J. Frey, David Mackay
Until recently, artificial intelligence researchers have frowned upon the application of probability propagation in Bayesian belief networks that have cycles, but it has recently been discovered that the two best error-correcting decoding algorithms are actually performing probability propagation with cycles.
Neural Information Processing SystemsStable Fixed Points of Loopy Belief Propagation Are Local Minima of the Bethe Free Energy
136 Citations2002Tom Heskes
Stability analysis leads us to conclude that stable fixed points of loopy belief propagation must be (local) minima of the Bethe free energy: minima can be unstable fixed points.
Radboud Repository (Radboud University)Expectation propagation for approximate inference in dynamic bayesian networks
110 Citations2002Tom Heskes, Onno Zoeter
A double-loop algorithm, guaranteed to converge to a local minimum of a Bethe free energy is derived, and it is shown that stable fixed points of (damped) expectation propagation correspond to local minima of this free energy, but that the converse need not be the case.
arXiv (Cornell University)Variational Approximations between Mean Field Theory and the Junction\n Tree Algorithm
80 Citations2013Wim Wiegerinck
Neural Information Processing SystemsTree-structured Approximations by Expectation Propagation
76 Citations2003Yuan Qi, Tom Minka
Belief propagation is extended to represent factors with tree approximations, by way of the expectation propagation framework, which results in more accurate inferences and more frequent convergence than ordinary belief propagation, at a lower cost than variational trees or double-loop algorithms.
The MIT Press eBooksComparing the Mean Field Method and Belief Propagation for Approximate Inference in MRFs
74 Citations2001Yair Weiss
Radboud Repository (Radboud University)Fractional Belief Propagation
71 Citations2002Wim Wiegerinck, Tom Heskes
Fractional belief propagation is formulated in terms of a family of approximate free energies, which includes the Bethe free energy and the naive mean-field free as special cases, and using the linear response correction of the clique marginals, the scale parameters can be tuned.
Power EP
50 Citations2004Tom Minka
Neural Information Processing SystemsLaplace Propagation
41 Citations2003Eleazar Eskin, Alex Smola +1 more
A novel method for approximate inference in Bayesian models and regularized risk functionals based on the propagation of mean and variance derived from the Laplace approximation of conditional probabilities in factorizing distributions, much akin to Minka's Expectation Propagation.
arXiv (Cornell University)Structured Region Graphs: Morphing EP into GBP
32 Citations2012Max Welling, Thomas P. Minka +1 more
"structured region graphs," a formalism which marries these two strategies, reveals a deep connection between them, and suggests how to choose good approximation structures, which is a convenient framework for producing high-quality approximations with a user-adjustable level of complexity.
Journal of Artificial Intelligence ResearchBound Propagation
26 Citations2003M.A.R. Leisink, Bert Kappen
This article presents an algorithm to compute bounds on the marginals of a graphical model and shows that sharp bounds can be obtained for undirected and directed graphs that are used for practical applications, but for which exact computations are infeasible.
Neural Information Processing SystemsSequentially Fitting ``Inclusive'' Trees for Inference in Noisy-OR Networks
26 Citations2000Brendan J. Frey, Relu Patrascu +2 more
A new sequential variational method is introduced for bipartite noisy-OR networks, that favors including all modes of the true posterior and models the posterior distribution as a tree.
Canadian Journal of StatisticsA generalized predictive criterion for model selection
15 Citations2002Mario Trottini, Fulvio Spezzaferri
Radboud Repository (Radboud University)Validity Estimates for Loopy Belief Propagation on Binary Real-world Networks
12 Citations2004Joris M. Mooij, Hilbert J. Kappen
A computationally efficient method is introduced to estimate the validity of the BP method as a function of graph topology, the connectivity strength, frustration and network size and it is found that BP always performs better than MF.