MAP estimation via agreement on trees: message-passing and linear programming

By Martin J. Wainwright, Tommi S. Jaakkola, Alan S. Willsky. IEEE Transactions on Information Theory, 2005

712 citations recorded by the source corpus.

We develop 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. By decomposing the original distribution into a convex combination of tree-structured distributions, we obtain an upper bound on the optimal value of the original problem (i.e., the log probability of the MAP assignment) in terms of the combined optimal values of the tree problems. We prove that this upper bound is tight if and only if all the tree distributions share an optimal configuration in common. An important implication is that any such shared configuration must also be a MAP configuration for the original distribution. Next we develop two approaches to attempting to obtain tight upper bounds: a) a tree-relaxed linear program (LP), which is derived from the Lagrangian dual of the upper bounds; and b) a tree-reweighted max-product message-passing algorithm that is related to but distinct from the max-product algorithm. In this way, we establish 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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/b28024225b22741035cf87203a3639c917959404

How researchers see this paper

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

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Robust Higher Order Potentials for Enforcing Label Consistency (2008, methodology): “The α-expansion algorithm was preferred because it was faster and gave a solution with lower energy compared to TRW-S.”
AD3: alternating directions dual decomposition for MAP inference in graphical models (2015, background): “Examples are max-sum diffusion (Kovalevsky and Koval, 1975; Werner, 2007); max-product sequential tree-reweighted belief propagation (TRW-S, Wainwright et al. 2005; Kolmogorov 2006); and the max-product linear programming algorithm (MPLP; Globerson and Jaakkola 2008).”
MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts (2009, background): “of the free energy associated with the MRF [10, 14, 15, 29, 34, 36]. Amongst them, the algorithms of [14, 15, 34] are closely related to the linear programming (LP) relaxation of semi-metric labeling [7, 17, 25, 33]. Although message passing algorithms provide accurate MAP estimates, they can be com”
A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing (2012, background): “Wainwright, Jaakkola, and Willsky (2005) describe an early and important algorithm for Markov random fields (MRFs) based on LP relaxations, tree-reweighted message passing (TRW).”
Advanced Structured Prediction (2014, methodology): “In what follows we review the most common LP relaxation for the MAP problem (Wainwright and Jordan, 2008; Wainwright et al., 2005; Werner, 2007).”
Exact Decoding of Phrase-Based Translation Models through Lagrangian Relaxation (2011, methodology): “, 2010), and also to Markov random fields (Wainwright et al., 2005; Komodakis et al., 2007; Sontag et al., 2008).”
Structured Learning with Approximate Inference (2007, methodology): “In general, max-product LBP on pairwise MRFs requires iterating the following rule to update messagesmij(yj) from node i to node j, where yj ranges over the possible labels for node j and N(i) is the neighbor set of node i. mij(yj) = max yi ψij(yi, yj)ψi(yi) ∏ k∈N(i)\{j} mki(yi) (5) Since we take…”
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 ν.”
Introduction to dual composition for inference (2011, methodology): “Tree structures (Wainwright et al., 2005; Komodakis et al., 2010), Matchings (Lacoste-Julien et al.”
The potential of automatic methods of classification to identify leaf diseases from multispectral images (2011, methodology): “We implemented the linear programming (LP) relaxation proposed by Schlesinger (1976) for a special case and independently by Chekuri et al. (2001), Koster et al. (1998), Wainwright et al. (2005) for the general case.”
New Outer Bounds on the Marginal Polytope (2007, methodology): “They also showed that the treereweighted max-product algorithm [9] can be used to solve the LP relaxation given by LOCAL(G), and that this succeeds in finding the MAP assignment for 339 of the 369 proteins in their data set.”
Slice-to-volume medical image registration: a survey (2017, background): “, 1999) and Three Re-weighted Belief Propagation (TRBP) (Wainwright et al., 2005).”
Distributed message passing for large scale graphical models (2011, methodology): “algorithms were introduced for solving these problems [28, 27, 29, 4, 8, 11].”