MRF Optimization via Dual Decomposition: Message-Passing Revisited

By Nikos Komodakis, Nikos Paragios, G. Tziritas. IEEE International Conference on Computer Vision, 2007

339 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/38649fa7ab5b237dc65290f20e16adc648363bc2

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 Computational Mechanics

In Signal Processing

Citations in the corpus

Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers (2013, background): “problems in a modular and extensible manner (Komodakis et al., 2007; Rush et al., 2010).”
Bayesian reasoning and machine learning (2012, neutral): “In the context of the MRF each slave problem may correspond to any tractable problem on the MRF[171].”
Elementary: Large-Scale Knowledge-Base Construction via Machine Learning and Statistical Inference (2012, methodology): “The Master chooses the values of the Lagrange multipliers via an optimization process (Komodakis et al., 2007).”
Structured Learning and Prediction in Computer Vision (2011, methodology): “This derivation is similar to recently proposed efficient MAP inference algorithms, such as in [64, 82, 160, 162].”
Graph cut based image segmentation with connectivity priors (2008, methodology): “Similar to [19, 20, 17], we used a projected subgradient method [23, 2] for maximizing Φ(θ).”
A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing (2012, methodology): “In this section we describe the dual decomposition algorithm from the work of Komodakis et al. (2007, 2011) for finding the MAP solution in pairwise, binary, MRFs. Pairwise MRFs are limited to the case where potential functions consider pairs of random variables, as opposed to larger subsets;…”
Greedy Direction Method of Multiplier for MAP Inference of Large Output Domain (2017, methodology): “A representative work with simple local optimizations is the Projected Subgradient Dual Decomposition (PSDD) algorithm [5].”
Frame-Semantic Parsing (2014, methodology): “Because general-purpose ILP solvers are proprietary and do not fully exploit the structure of the problem, we turn to a class of optimization techniques called dual decomposition (Komodakis, Paragios, and Tziritas 2007; Rush et al. 2010; Martins et al. 2011a).”
MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts (2009, background): “Message passing algorithms attempt to minimize approximations of the free energy associated with the MRF [10, 14, 17, 31, 37, 39].”
Feature Correspondence Via Graph Matching: Models and Global Optimization (2008, methodology): “[6–11].”
MRF Energy Minimization and Beyond via Dual Decomposition (2011, positive): “We note that this paper provides a significantly extended version of our earlier work [24].”
Diverse M-Best Solutions in Markov Random Fields (2012, methodology): “For instance, using max-flow/min-cut methods [7, 13], one can find the globally optimal solution for a (submodular) foreground-background segmentation problem on a 2 Megapixel image within seconds, effectively searching 2 possible segmentations.”
Improving Data Association by Joint Modeling of Pedestrian Trajectories and Groupings (2010, methodology): “The primal solution, and therefore the upper bound to the optimal solution, is found by using a heuristic similar to that described in [23].”
Optimization for machine learning (2010, background): “This suggests that diffusion in a sense exactly solves certain small subprobdiffusion solves subproblems lems (which links it to the dual decomposition interpretation (Komodakis et al., 2007)).”
Advanced Structured Prediction (2014, methodology): “Sub-gradient method of Shor et al. (1985) , where τ t → 0 and was one of the ﬁrst optimization algorithms with convergence guarantees, independently applied by Storvik and Dahl (2000) and later by Schlesinger and Giginyak (2007) and Komodakis et al. (2007) to tackle (1.29).”
Dual Decomposition Inference for Graphical Models over Strings (2015, methodology): “It has been widely used for MAP inference in graphical models (Komodakis et al., 2007; Komodakis and Paragios, 2009; Koo et al., 2010; Martins et al., 2011; Sontag et al., 2011; Rush and Collins, 2014).”
Convergent Decomposition Solvers for Tree-reweighted Free Energies (2011, methodology): “In fact, for the related maximum-a-posteriori (MAP) problem, Komodakis et al. (2007) have shown that a similar convex upper bound, formed over a small number of trees, can be minimized efficiently using the projected subgradient algorithm.”
AD3: alternating directions dual decomposition for MAP inference in graphical models (2015, methodology): “A close look at Algorithm 1 reveals that the consensus is promoted solely by the Lagrange multipliers (line 6).”