A New Class of Upper Bounds on the Log Partition Function
IEEE Transactions on Information TheoryPublished 28 June 2005
Martin J. Wainwright, Tommi Jaakkola, Alan S. Willsky
Citations401
SJR quartileQ1
SJR score1.46
SNIP1.76
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
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.
Abstract
We introduce a new class of upper bounds on the log partition function of a Markov random field (MRF). This quantity plays an important role in various contexts, including approximating marginal distributions, parameter estimation, combinatorial enumeration, statistical decision theory, and large-deviations bounds. Our derivation is based on concepts from convex duality and information geometry: in particular, it exploits mixtures of distributions in the exponential domain, and the Legendre mapping between exponential and mean parameters. In the special case of convex combinations of tree-structured distributions, we obtain a family of variational problems, similar to the Bethe variational problem, but distinguished by the following desirable properties: i) they are convex, and have a unique global optimum; and ii) the optimum gives an upper bound on the log partition function. This optimum is defined by stationary conditions very similar to those defining fixed points of the sum-product algorithm, or more generally, any local optimum of the Bethe variational problem. As with sum-product fixed points, the elements of the optimizing argument can be used as approximations to the marginals of the original model. The analysis extends naturally to convex combinations of hypertree-structured distributions, thereby establishing links to Kikuchi approximations and variants.
Keywords
Computer Science
Elements of Information Theory
37,533 Citations2001Thomas M. Cover, Joy A. Thomas
Physical ReviewCrystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
6,489 Citations1944Lars Onsager
Cambridge University Press eBooksEnumerative Combinatorics
6,487 Citations1997Richard P. Stanley, Gian‐Carlo Rota
IEEE Transactions on Information TheoryFactor graphs and the sum-product algorithm
6,481 Citations2001Frank R. Kschischang, Brendan J. Frey +1 more
A generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph, that computes-either exactly or approximately-various marginal functions derived from the global function.
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.
now publishers, Inc. eBooksGraphical Models, Exponential Families, and Variational Inference
3,154 Citations2007Martin J. Wainwright, Michael I. Jordan
Graduate texts in mathematicsModern Graph Theory
2,844 Citations1998Béla Bollobás
This book presents an account of newer topics, including Szemer'edi's Regularity Lemma and its use; Shelah's extension of the Hales-Jewett Theorem; the precise nature of the phase transition in a random graph process; the connection between electrical networks and random walks on graphs; and the Tutte polynomial and its cousins in knot theory.
Graphical Models
2,780 Citations1996Steffen L. Lauritzen
IEEE Transactions on Information TheoryApproximating discrete probability distributions with dependence trees
2,640 Citations1968Chee Lap Chow, C. Liu
It is shown that the procedure derived in this paper yields an approximation of a minimum difference in information when applied to empirical observations from an unknown distribution of tree dependence, and the procedure is the maximum-likelihood estimate of the distribution.
Convex analysis and minimization algorithms
2,435 Citations1993Jean‐Baptiste Hiriart‐Urruty, Claude Lemaréchal
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.
Understanding belief propagation and its generalizations
1,266 Citations2003Jonathan S. Yedidia, William T. Freeman +1 more
It is shown that BP can only converge to a fixed point that is also a stationary point of the Bethe approximation to the free energy, which enables connections to be made with variational approaches to approximate inference.
Cambridge University Press eBooksA Course in Combinatorics
1,220 Citations2001J. H. van Lint, R. Wilson
DSpace@MIT (Massachusetts Institute of Technology)A family of algorithms for approximate bayesian inference
902 Citations2001Thomas P. Minka, Rosalind W. Picard
This thesis presents an approximation technique that can perform Bayesian inference faster and more accurately than previously possible, and is found to be convincingly better than rival approximation techniques: Monte Carlo, Laplace's method, and variational Bayes.
Mathematical ProgrammingMatroids and the greedy algorithm
867 Citations1971Jack Edmonds
Linear-algebra rank is the solution to an especially tractable optimization problem which are linear programs relative to certain derived polyhedra.
An Introduction to Variational Methods for Graphical Models
563 Citations1998Michael I. Jordan, Zoubin Ghahramani +2 more
SIAM Journal on ComputingPolynomial-Time Approximation Algorithms for the Ising Model
559 Citations1993Mark Jerrum, Alistair Sinclair
Computational solutions to some classical combinatorial problems in statistical physics stem from the Ising model, which has been the focus of much attention in the physics and mathematics communities since it was first introduced by Lenz and Ising in the early 1920s.
Algorithms and computation in mathematicsGraphs, Networks and Algorithms
502 Citations2007Dieter Jungnickel
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.
IEEE Transactions on Information TheoryInformation geometry on hierarchy of probability distributions
394 Citations2001Шун-ичи Амари
The orthogonal decomposition of an exponential family or mixture family of probability distributions has a natural hierarchical structure is given and is important for extracting intrinsic interactions in firing patterns of an ensemble of neurons and for estimating its functional connections.
The Annals of StatisticsDifferential Geometry of Curved Exponential Families-Curvatures and Information Loss
372 Citations1982Шун-ичи Амари
Proceedings of the IEEEMultiresolution Markov models for signal and image processing
306 Citations2002Alan S. Willsky
This presentation reviews a significant component of the rich field of statistical multiresolution (MR) modeling and processing, and shows how a variety of methods and models relate to this framework including models for self-similar and 1/f processes.
IEEE Transactions on Information TheoryTree-based reparameterization framework for analysis of sum-product and related algorithms
238 Citations2003Martin J. Wainwright, Tommi Jaakkola +1 more
A tree-based reparameterization (TRP) framework is presented that provides a new conceptual view of a large class of algorithms for computing approximate marginals in graphs with cycles, which includes the belief propagation or sum-product algorithm as well as variations and extensions of BP.
Tree-reweighted Belief Propagation Algorithms and Approximate ML Estimation by Pseudo-Moment Matching
165 Citations2003Martin J. Wainwright, Tommi Jaakkola +1 more
A class of lo-cal message-passing algorithms is developed, which is called tree-reweighted belief propagation, for ef-flciently computing the value of these upper bounds on the log partition function of an arbitrary undirected graphical model, as well as the associated pseudo-marginals.
Symposium on Discrete AlgorithmsLearning Markov networks: maximum bounded tree-width graphs
110 Citations2001David R. Karger, Nathan Srebro
The problem of learning a maximum likelihood Markov network given certain observed data can be reduced to the problem of identifying a maximum weight low-treewidth graph under a given input weight function and the first constant factor approximation algorithm is given.
arXiv (Cornell University)Approximate Inference and Constrained Optimization
88 Citations2012Tom Heskes, Kees Albers +1 more
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.
DSpace@MIT (Massachusetts Institute of Technology)Stochastic processes on graphs with cycles: geometric and variational approaches
67 Citations2002Martin J. Wainwright, Alan S. Willsky +1 more
A method for performing exact estimation of Gaussian processes on graphs with cycles by solving a sequence of modi ed problems on embedded spanning trees, and a tree-based reparameterization framework for approximate estimation of discrete processes are presented.
Tree-based reparameterization for approximate inference on loopy graphs
62 Citations2001Martin J. Wainwright, Tommi Jaakkola +1 more
A tree-based reparameterization framework that provides a new conceptual view of a large class of iterative algorithms for computing approximate marginals in graphs with cycles, which includes belief propagation, which can be reformulated as a very local form of reparametersization.
arXiv (Cornell University)Computing Upper and Lower Bounds on Likelihoods in Intractable Networks
57 Citations2013Tommi Jaakkola, Michael I. Jordan
Uncertainty in Artificial IntelligenceOn the choice of regions for generalized belief propagation
48 Citations2004Max Welling
This paper proposes a sequential approach to adding new clusters of nodes and their interactions (i.e. "regions") to the approximation of generalized belief propagation, and proposes "weakly irreducible" regions as the natural candidates to be added to the approximation.
The IMA volumes in mathematics and its applicationsBelief Propagation on Partially Ordered Sets
41 Citations2003Robert J. McEliece, Muhammed A. Yıldırım
It is shown that PBP can be thought of as an algorithm for minimizing a certain “free energy” function, and by exploiting this interpretation, a one-to-one correspondence between the fixed points of PBP and the stationary points of the free energy is exhibited.
Recursive Algorithms for Approximating Probabilities in Graphical Models
35 Citations1996Tommi Jaakkola, Michael I. Jordan
A recursive node-elimination formalism for efficiently approximating large probabilistic networks and shows that Boltzmann machines, sigmoid belief networks, or any combination (i.e., chain graphs) can be handled within the same framework.
Variational inference in graphical models: The view from the marginal polytope
31 Citations2003Martin J. Wainwright, Michael I. Jordan
Taking the “zero-temperature limit” recovers a variational representation for MAP computation as a linear program (LP) over the marginal polytope, which clarifies the essential ingredients of known variational methods, and also suggests novel relaxations.
IEEE Transactions on Image ProcessingThe application of the Gibbs-Bogoliubov-Feynman inequality in mean field calculations for Markov random fields
30 Citations1996Jun Zhang
The Gibbs-Bogoliubov-Feynman inequality of statistical mechanics is adopted, with an information-theoretic interpretation, as a general optimization framework for deriving and examining various mean field approximations for Markov random fields (MRF's).
IEEE Transactions on Information TheoryStochastic approximation algorithms for partition function estimation of Gibbs random fields
30 Citations1997Gerasimos Potamianos, John Goutsias
This work presents an analysis of previously proposed Monte Carlo algorithms for estimating the partition function of a Gibbs random field and shows that this problem reduces to estimating one or more expectations of suitable functionals of the Gibbs states with respect to properly chosen Gibbs distributions.
Neural ComputationA Tighter Bound for Graphical Models
23 Citations2001M.A.R. Leisink, Hilbert J. Kappen
A method to bound the partition function of a Boltzmann machine neural network with any odd-order polynomial is presented and it is shown that the third-order bound is strictly better than mean field.
Radboud Repository (Radboud University)Approximations with Reweighted Generalized Belief Propagation
22 Citations2005Wim Wiegerinck
This work increases the complexity of the approximating distributions by taking combinations of junction trees, leading to a convexified Kikuchi free energy, which is minimized by reweighted generalized belief propagation.
DSpace@MIT (Massachusetts Institute of Technology)Maximum likelihood Markov networks : an algorithmic approach
16 Citations2000Nathan Srebro
It is shown how a graphical model learning problem can be presented as a purely combinatorial problem, which allows us to analyze the computational hardness of the learning problem, and devise global optimization algorithms with proven performance guarantees.