PART I - We present an analysis of three MAP estimation 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.
We show that the SOCP-MS and the QP-RL relaxations are equivalent.
Furthermore,
we prove that despite the flexibility in the form of the constraints/objective function offered by QP and SOCP, the LP-S relaxation strictly 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 is dominated by the LP-S relaxation. Based on these results we propose some novel SOCP relaxations which strictly dominate the previous approaches.
(*Honourable mention at NIPS 2007)
PART II - This part of the talk will focus on the problem of minimizing higher order functions of discrete variables. These functions are defined over higher order cliques and are able to model interactions among groups of random variables. We will show how certain higher order energy functions can be minimized using the graph cut based large move making algorithms such as alpha-expansion and alpha-beta-swap. This method is extremely efficient and is able to handle cliques involving thousands of variables.
Co-authors include Vladimir Kolmogorov, Pawan Kumar and Pushmeet Kohli.
Additional Presentation Files (Zip Archive)
Copyright. All Rights Reserved.