Timezone: »
The problem of obtaining the maximum a posteriori estimate of a given Markov random field is known to be NP-hard in general. However, due to its central importance in many applications, several approximate algorithms have been proposed in the literature. In this paper, we present an analysis of three such algorithms based on convex relaxations: (i) LP-S: the linear programming (LP) relaxation proposed by Schlesinger for a special case and independently by Chekuri et al., Koster et al. and Wainwright et al. for the general case; (ii) QP-RL: the quadratic programming (QP) relaxation by Ravikumar and Lafferty; and (iii) SOCP-MS: the second order cone programming (SOCP) relaxation first proposed by Muramatsu and Suzuki for two label problems and later extended by Kumar et al. for a general label set. Specifically, we show that the SOCP-MS and QP-RL relaxations are equivalent. Furthermore, we prove that despite the flexibility in the form of the constraints and the objective function offered by QP and SOCP, the LP-S relaxation dominates (i.e. provides a better approximation than) QP-RL and SOCP-MS. We generalize these results by defining a large class of SOCP (and equivalent QP) relaxations which are dominated by the LP-S relaxation. Based on these results we propose some novel SOCP constraints which dominate the previous approaches. We develop efficient algorithms for solving the resulting relaxations and show that the empirical results conform with our analysis.
Author Information
Pawan K Mudigonda (University of Oxford)
Vladimir Kolmogorov (University College London)
Philip Torr (Oxford University)
Related Events (a corresponding poster, oral, or spotlight)
-
2007 Poster: An Analysis of Convex Relaxations for MAP Estimation »
Tue. Dec 4th 06:30 -- 06:40 PM Room
More from the Same Authors
-
2021 : Faking Interpolation Until You Make It »
Alasdair Paren · Rudra Poudel · Pawan K Mudigonda -
2022 Poster: In Defense of the Unitary Scalarization for Deep Multi-Task Learning »
Vitaly Kurin · Alessandro De Palma · Ilya Kostrikov · Shimon Whiteson · Pawan K Mudigonda -
2020 Poster: Hybrid Models for Learning to Branch »
Prateek Gupta · Maxime Gasse · Elias Khalil · Pawan K Mudigonda · Andrea Lodi · Yoshua Bengio -
2018 Poster: A Unified View of Piecewise Linear Neural Network Verification »
Rudy Bunel · Ilker Turkaslan · Philip Torr · Pushmeet Kohli · Pawan K Mudigonda -
2016 Poster: Adaptive Neural Compilation »
Rudy Bunel · Alban Desmaison · Pawan K Mudigonda · Pushmeet Kohli · Philip Torr -
2016 Poster: Learning feed-forward one-shot learners »
Luca Bertinetto · João Henriques · Jack Valmadre · Philip Torr · Andrea Vedaldi -
2016 Poster: DISCO Nets : DISsimilarity COefficients Networks »
Diane Bouchacourt · Pawan K Mudigonda · Sebastian Nowozin -
2011 Poster: Learning Anchor Planes for Classification »
Ziming Zhang · Lubor Ladicky · Philip Torr · Amir Saffari -
2011 Demonstration: Online structured-output learning for real-time object tracking and detection »
Sam Hare · Amir Saffari · Philip Torr -
2010 Poster: Generalized roof duality and bisubmodular functions »
Vladimir Kolmogorov -
2008 Poster: Improved Moves for Truncated Convex Models »
Pawan K Mudigonda · Philip Torr -
2008 Spotlight: Improved Moves for Truncated Convex Models »
Pawan K Mudigonda · Philip Torr