A new class of upper bounds on the log partition function

By Martin J. Wainwright, Tommi S. Jaakkola, Alan S. Willsky. 2002

464 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Probabilistic & Bayesian Methods

Citations in the corpus

Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “Fast combinatorial solvers for the TRW objective exist, including Tree-Reweighted Belief Propagation (TRBP) (Wainwright et al., 2005), convergent message-passing based on geometric programming (Globerson and Jaakkola, 2007), and dual decomposition (Jancsary and Matz, 2011).”
Learning Deep Structured Models (2014, methodology): “ization w.r.t. the beliefs bexactly. This is a non-trivial task in itself as inference in general graphical models is NP-hard. Iterative message passing algorithms (Pearl, 1988; Yedidia et al., 2005; Wainwright et al., 2005; Weiss et al., 2007; Meltzer et al., 2009) are typically employed. Important”
Deep Unfolding: Model-Based Inspiration of Novel Deep Architectures (2014, methodology): “This is because rather than optimizing an objective function at test time, we instead optimize the parameters according to a discriminative objective function at training time, such that the inference algorithm implemented by the network obtains the best result on training data.”
Advances in Variational Inference (2017, background): “Some recent extensions of EP [101], [125], [204], [228] can be viewed as classical EP with”
Estimating the "Wrong" Graphical Model: Benefits in the Computation-Limited Setting (2006, methodology): “For all of these variational methods, then, Proposition 5 guarantees that the pseudomarginal computation is globally Lipschitz stable, thereby providing theoretical confirmation of previous experimental results (Wiegerinck, 2005; Wainwright et al., 2005; Wainwright and Jordan, 2006).”
On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations (2013, background): “These probability models generate samples efficiently thorough optimization: they have statistical advantages over purely variational approaches such as tree re-weighted belief propagation [22] or max-marginals [10], and they are faster than standard Gibbs samplers and Markov chain Monte Carlo appro”
Sandwiching the marginal likelihood using bidirectional Monte Carlo (2015, background): “Indeed, while variational upper bounds have been proposed (Wainwright et al., 2002), we aren’t aware of any practical stochastic upper bounds which achieve comparable accuracy to AIS.”
New Era for Robust Speech Recognition (2017, methodology): “The final acoustic model was a fully connected DNN that takes as input 40-dimensional log mel filterbank features with first and second time derivatives [55].”
Convergent Propagation Algorithms via Oriented Trees (2007, methodology): “This differs from the presentation in [13] though the distinction is immaterial in the remainder of this section.”
The IM algorithm: a variational approach to Information Maximization (2003, result): “These initial results are encouraging, and motivate further investigations, for example, using syndrome decoding for CDMA.”
The Benefits of Learning with Strongly Convex Approximate Inference (2015, methodology): “We consider two popular variational methods: tree-reweighted (Wainwright et al., 2005) and counting number (Heskes, 2006) entropies.”
Joint People, Event, and Location Recognition in Personal Photo Collections Using Cross-Domain Context (2010, methodology): “The substitution results in an upper bound of log Z ( X ; R ) [20].”
A Linear Programming Approach to Max-Sum Problem: A Review (2007, background): “[24] shows that a convex combination of problems provides a convex upper bound on the logpartition function of MRF.”
Exact and Approximate Sampling by Systematic Stochastic Search (2009, background): “Many popular approaches to inference, such as mean-ﬁeld variational methods (Jordan et al., 1999), convex relaxations (Wainwright et al., 2002; Sontag and Jaakkola, 2008), and generalized belief propagation (Yedidia et al., 2001), focus on approximating MAP assignments or (low-dimensional, e.g. 1…”
Convergent Decomposition Solvers for Tree-reweighted Free Energies (2011, methodology): “Wainwright et al. (2005a) show that one can obtain even tighter upper bounds by optimizing (7) over the edge occurrence probabilities ν.”
New Outer Bounds on the Marginal Polytope (2007, methodology): “However, both entropy approximations give significantly better pseudomarginals when used by our algorithm together with the cycle inequalities (see “TRW + Cycle” and “Logdet + Cycle” in the figures).”