A New Class of Upper Bounds on the Log Partition Function

DOI10.1109/TIT.2005.850091MaRDI QIDQ3547761zbMATH OpenFDO

Authors Martin J. Wainwright, Alan S. Willsky, Tommi S. Jaakkola

Publication date 21 December 2008

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.0610

Mathematics Subject Classification ID

Random fields (60G60) Random fields; image analysis (62M40) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Detection theory in information and communication theory (94A13)

Abstract: Bounds on the log partition function are important in a variety of contexts, including approximate inference, model fitting, decision theory, and large deviations analysis. We introduce a new class of upper bounds on the log partition function, based on convex combinations of distributions in the exponential domain, that is applicable to an arbitrary undirected graphical model. In the special case of convex combinations of tree-structured distributions, we obtain a family of variational problems, similar to the Bethe free energy, but distinguished by the following desirable properties: i. they are cnvex, and have a unique global minimum; and ii. the global minimum gives an upper bound on the log partition function. The global minimum is defined by stationary conditions very similar to those defining fixed points of belief propagation or tree-based reparameterization Wainwright et al., 2001. As with BP fixed points, the elements of the minimizing argument can be used as approximations to the marginals of the original model. The analysis described here can be extended to structures of higher treewidth e.g., hypertrees, thereby making connections with more advanced approximations e.g., Kikuchi and variants Yedidia et al., 2001; Minka, 2001.

Recommendations

• New closed-form bounds on the partition function
• Harnessing the Bethe free energy
• scientific article; zbMATH DE number 2000820
• A tighter bound for graphical models
• Convexity arguments for efficient minimization of the Bethe and Kikuchi free energies

Cited in

(27)

• Simple upper bounds for partition functions
• Applicability of \(n\)-vicinity method for calculation of free energy of Ising model
• Fast structured prediction using large margin sigmoid belief networks
• Discrete temporal models of social networks
• Piecewise training for structured prediction
• New closed-form bounds on the partition function
• Universality of the mean-field for the Potts model
• A family of CCCP algorithms which minimize the TRW free energy
• A tighter bound for graphical models
• Model-based machine learning
• Blending learning and inference in conditional random fields
• Spectral bounds for the Ising ferromagnet on an arbitrary given graph
• Margin losses for training conditional random fields
• Spatio-temporal random fields: compressible representation and distributed estimation
• Recursive sum-product algorithm for generalized outer-planar graphs
• scientific article; zbMATH DE number 2000820 (Why is no real title available?)
• Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited
• Estimation and Marginalization Using the Kikuchi Approximation Methods
• Gauging variational inference
• Bucket renormalization for approximate inference
• Gauges, loops, and polynomials for partition functions of graphical models
• Tractable minor-free generalization of planar zero-field Ising models
• Belief propagation: accurate marginals or accurate partition function—where is the difference?
• A structured variational learning approach for switching latent factor models
• Message-passing algorithms for inference and optimization
• Approximate inference with exponential tilting densities: theory and applications
• Multiscale stochastic modeling for tractable inference and data assimilation

This page was built for publication: A New Class of Upper Bounds on the Log Partition Function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3547761)