MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming

DOI10.1109/TIT.2005.856938zbMATH Open1318.94025arXivcs/0508070OpenAlexW2108619558MaRDI QIDQ3547762FDOQ3547762

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

Publication date: 21 December 2008

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

Abstract: We develop and analyze methods for computing provably optimal {em maximum a posteriori} (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 {em tree-relaxed linear program} (LP), which is derived from the Lagrangian dual of the upper bounds; and (b) a {em 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.

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

Recommendations

• Message-passing for graph-structured linear programs: proximal methods and rounding schemes
• On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
• Factor graphs and the sum-product algorithm
• Linear programming relaxations and belief propagation -- an empirical study
• An analysis of convex relaxations for MAP estimation of discrete MRFs

Mathematics Subject Classification ID

Markov processes: estimation; hidden Markov models (62M05) Linear programming (90C05) Detection theory in information and communication theory (94A13)

Cited In (43)

• Distributed primal–dual interior-point methods for solving tree-structured coupled convex problems using message-passing
• An analysis of convex relaxations for MAP estimation of discrete MRFs
• Title not available (Why is that?)
• Discriminative models for multi-class object layout
• Global optimization for first order Markov random fields with submodular priors
• A Doubly Graduated Method for Inference in Markov Random Field
• Decoding turbo-like codes via linear programming
• Improved generalized belief propagation for vision processing
• Conditional random fields for pattern recognition applied to structured data
• Scale selection for anisotropic diffusion filter by Markov random field model
• Bilevel Optimization with Nonsmooth Lower Level Problems
• Unsupervised multi-class segmentation of SAR images using fuzzy triplet Markov fields model
• Learning adaptive regularization for image labeling using geometric assignment
• Understanding the scalability of Bayesian network inference using clique tree growth curves
• Tree-based reparameterization framework for analysis of sum-product and related algorithms
• Energy distribution view for monotonic dual decomposition
• Title not available (Why is that?)
• Fast structured prediction using large margin sigmoid belief networks
• Multilabel classification through random graph ensembles
• Optical flow estimation with occlusion detection
• Global minimization for continuous multiphase partitioning problems using a dual approach
• Maximum likelihood bounded tree-width Markov networks
• Global optimization of wavelet-domain hidden Markov tree for image segmentation
• Diffusion methods for classification with pairwise relationships
• Cycle-based cluster variational method for direct and inverse inference
• On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
• Multiscale stochastic modeling for tractable inference and data assimilation
• MAP inference via \(\ell_2\)-sphere linear program reformulation
• Estimation and Marginalization Using the Kikuchi Approximation Methods
• Efficient semidefinite branch-and-cut for MAP-MRF inference
• Combinatorial optimization of the discretized multiphase Mumford-Shah functional
• Iterated conditional modes for inverse dithering
• Soft arc consistency revisited
• Inference methods for CRFs with co-occurrence statistics
• Data association based on optimization in graphical models with application to sensor networks
• The Power of Linear Programming for General-Valued CSPs
• On learning conditional random fields for stereo
• A spatially continuous max-flow and min-cut framework for binary labeling problems
• Message-passing algorithms for inference and optimization
• Lifted graphical models: a survey
• A survey and comparison of discrete and continuous multi-label optimization approaches for the Potts model
• Leveraging cluster backbones for improving MAP inference in statistical relational models
• Image Labeling Based on Graphical Models Using Wasserstein Messages and Geometric Assignment

This page was built for publication: MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming

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