MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
From MaRDI portal
Publication:3547762
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.
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
Cited in
(50)- Discrete graphical models -- an optimization perspective
- Distributed primal–dual interior-point methods for solving tree-structured coupled convex problems using message-passing
- Variational algorithms for marginal MAP
- An analysis of convex relaxations for MAP estimation of discrete MRFs
- Discriminative models for multi-class object layout
- Global optimization for first order Markov random fields with submodular priors
- scientific article; zbMATH DE number 1834036 (Why is no real title available?)
- Decoding turbo-like codes via linear programming
- Estimating the ``wrong graphical model: benefits in the computation-limited setting
- 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
- The power of linear programming for general-valued CSPs
- 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
- Energy distribution view for monotonic dual decomposition
- Fast structured prediction using large margin sigmoid belief networks
- Tree-based reparameterization framework for analysis of sum-product and related algorithms
- Multilabel classification through random graph ensembles
- Linear programming relaxations and belief propagation -- an empirical study
- A doubly graduated method for inference in Markov random field
- Image labeling based on graphical models using Wasserstein messages and geometric assignment
- Optical flow estimation with occlusion detection
- New closed-form bounds on the partition function
- Global minimization for continuous multiphase partitioning problems using a dual approach
- Maximum likelihood bounded tree-width Markov networks
- Cycle-based cluster variational method for direct and inverse inference
- Global optimization of wavelet-domain hidden Markov tree for image segmentation
- Diffusion methods for classification with pairwise relationships
- Multiscale stochastic modeling for tractable inference and data assimilation
- On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
- 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
- Train and test tightness of LP relaxations in structured prediction
- Linear coordinate-descent message passing for quadratic optimization
- Inference methods for CRFs with co-occurrence statistics
- Data association based on optimization in graphical models with application to sensor networks
- On learning conditional random fields for stereo
- Message-passing algorithms for inference and optimization
- A spatially continuous max-flow and min-cut framework for binary labeling problems
- Lifted graphical models: a survey
- Bilevel optimization with nonsmooth lower level problems
- A survey and comparison of discrete and continuous multi-label optimization approaches for the Potts model
- Message-passing for graph-structured linear programs: proximal methods and rounding schemes
- Leveraging cluster backbones for improving MAP inference in statistical relational models
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)
