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
(53)- Iterated conditional modes for inverse dithering
- Conditional random fields for pattern recognition applied to structured data
- Efficient semidefinite branch-and-cut for MAP-MRF inference
- Maximum likelihood bounded tree-width Markov networks
- Fast structured prediction using large margin sigmoid belief networks
- On learning conditional random fields for stereo
- Optical flow estimation with occlusion detection
- Learning adaptive regularization for image labeling using geometric assignment
- New closed-form bounds on the partition function
- MAP inference via _2-sphere linear program reformulation
- Leveraging cluster backbones for improving MAP inference in statistical relational models
- A survey and comparison of discrete and continuous multi-label optimization approaches for the Potts model
- Combinatorial optimization of the discretized multiphase Mumford-Shah functional
- Global optimization of wavelet-domain hidden Markov tree for image segmentation
- Lifted graphical models: a survey
- Multilabel classification through random graph ensembles
- Energy distribution view for monotonic dual decomposition
- A spatially continuous max-flow and min-cut framework for binary labeling problems
- Data association based on optimization in graphical models with application to sensor networks
- Linear coordinate-descent message passing for quadratic optimization
- An analysis of convex relaxations for MAP estimation of discrete MRFs
- Message-passing for graph-structured linear programs: proximal methods and rounding schemes
- Variational algorithms for marginal MAP
- Estimating the ``wrong graphical model: benefits in the computation-limited setting
- Linear programming relaxations and belief propagation -- an empirical study
- Bilevel optimization with nonsmooth lower level problems
- Cycle-based cluster variational method for direct and inverse inference
- Inference methods for CRFs with co-occurrence statistics
- Global minimization for continuous multiphase partitioning problems using a dual approach
- Discriminative models for multi-class object layout
- Unsupervised multi-class segmentation of SAR images using fuzzy triplet Markov fields model
- On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
- Train and test tightness of LP relaxations in structured prediction
- Tree-based reparameterization framework for analysis of sum-product and related algorithms
- Image labeling based on graphical models using Wasserstein messages and geometric assignment
- scientific article; zbMATH DE number 1834036 (Why is no real title available?)
- On solving probabilistic linear Diophantine equations
- Discrete graphical models -- an optimization perspective
- Diffusion methods for classification with pairwise relationships
- The power of linear programming for general-valued CSPs
- Distributed primal–dual interior-point methods for solving tree-structured coupled convex problems using message-passing
- Estimation and Marginalization Using the Kikuchi Approximation Methods
- A doubly graduated method for inference in Markov random field
- Decoding turbo-like codes via linear programming
- Improved generalized belief propagation for vision processing
- Message-passing algorithms for inference and optimization
- Distributed nonlinear conic optimization with partially separable structure
- Bounded degree nonnegative counting CSP
- Global optimization for first order Markov random fields with submodular priors
- Soft arc consistency revisited
- Scale selection for anisotropic diffusion filter by Markov random field model
- Understanding the scalability of Bayesian network inference using clique tree growth curves
- Multiscale stochastic modeling for tractable inference and data assimilation
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)
