Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations

By Amir Globerson, Tommi S. Jaakkola. Neural Information Processing Systems, 2007

382 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/5e11fc1e66c1f0a1b514f4d403da500a9125329d

How researchers see this paper

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

Citations in the corpus

Greedy Direction Method of Multiplier for MAP Inference of Large Output Domain (2017, methodology): “• MPLP: The Max-Product Linear Programming algorithm [8, 12, 13] with public implementation (7).”
Introduction to dual composition for inference (2011, methodology): “models (Globerson and Jaakkola, 2008).”
Graphical Models, Exponential Families, and Variational Inference (2008, methodology): “5), including subgradient methods [73, 136], dual coordinate ascent methods [94, 234], annealing-type methods [121, 246], proximal optimization schemes [193], and adaptive LP solvers [223].”
Hinge-Loss Markov Random Fields and Probabilistic Soft Logic (2015, background): “Many DD algorithms use coordinate descent, such as TRW-S (Kolmogorov, 2006), MSD (Werner, 2007), MPLP (Globerson and Jaakkola, 2007), and ADLP (Meshi and Globerson, 2011).”
A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing (2012, methodology): “Finally, we describe the algorithm of Held and Karp (1971) for the traveling salesman problem, and the algorithm of Chang and Collins (2011) for decoding of phrase-based translation models.”
Structured Prediction Energy Networks (2015, unknown): “(Boykov & Kolmogorov, 2004; Globerson & Jaakkola, 2008).”
Hinge-Loss Markov Random Fields and Probabilistic Soft Logic (2015, methodology): “Many DD algorithms use coordinate descent, such as TRW-S (Kolmogorov, 2006), MSD (Werner, 2007), MPLP (Globerson and Jaakkola, 2007), and ADLP (Meshi and Globerson, 2011), Other DD algorithms use subgradient-based approaches (e.”
AD3: alternating directions dual decomposition for MAP inference in graphical models (2015, methodology): “In this section, we provide an empirical comparison between AD 3 (Algorithm 2) and four other algorithms: generalized MPLP (Globerson and Jaakkola, 2008); norm-product BP (Hazan and Shashua, 2010); 7 the PSDD algorithm of Komodakis et al. (2007) (Algorithm 1) and its accelerated version introduced b”
MRF Energy Minimization and Beyond via Dual Decomposition (2011, unknown): “This motivation also lies behind some other MAP estimation algorithms such as the max-sum diffusion algorithm reviewed in [53] or the more recent algorithm of Globerson and Jaakkola that was proposed in [14].”
A Review of Relational Machine Learning for Knowledge Graphs (2015, methodology): “One approach for computing the MAP estimate is to use the MPLP (max product linear programming) method [129].”
Learning Efficient Random Maximum A-Posteriori Predictors with Non-Decomposable Loss Functions (2013, background): “This theorem extends Proposition 3 in [6] to non-binary and non-pairwise graphical models.”
Marginal Inference in MRFs using Frank-Wolfe (2013, background): “Many message passing algorithms approximately solve this LP very efficiently [8].”
Distributed message passing for large scale graphical models (2011, methodology): “algorithms were introduced for solving these problems [28, 27, 29, 4 , 8, 11].”
Automorphism Groups of Graphical Models and Lifted Variational Inference (2012, methodology): “ in cycles of different length, hence are subject to different cycle constraints. 7 us to lift even asynchronous message passing algorithms such as the max-product linear programming (MPLP) algorithm [4], which cannot be lifted using existing lifting techniques. 7 Beyond Local Polytope: Lifted MAP I”