Global MAP-Optimality by Shrinking the Combinatorial Search Area with Convex Relaxation
Bogdan Savchynskyy, Jörg Hendrik Kappes, Paul Swoboda, Christoph Schnörr · 2013
We consider energy minimization for undirected graphical models, known as MAP- or MLE-inference. We propose a novel method of combining combinatorial and convex programming techniques to obtain an optimal integer solution of the initial combinatorial problem. Our method enables to confine the application of the combinatorial solver to a small fraction of the initial graphical model, where the convex programming solver fails. The method shows superior results on a computer vision benchmark. In particular we report solving so far unsolved large scale benchmark problems and outperform in speed a state-of-the-art specialized method on Potts models. Problem Formulation Given the graph G = (V, E), associated variables xv ∈ Xv, v ∈ V, and potentials θw,xw ∈ R, w ∈ V ∪ E, we consider the energy minimization problem min x∈X E(θ, x) = min x∈X v∈V θv,xv + uv∈E θuv,xuv = min x∈X 〈θ, δ(x) 〉 = min µ∈conv(δ(X)) 〈θ, µ 〉. LP Relaxation min µ∈Λ 〈θ, µ 〉 : Λ = {µ ≥ 0: xv µv = 1, xu µuv,xuv = µv,xv, xv µuv,xuv = µu,xu} ︸ ︷ ︷ ︸ local polytope (LP) ⊃ conv(δ(X)), xv θuv(xu, xv) θu(xu) θv(xv) vu xu v µuv(xu, xv) µu(xu) µv(xv) xvxu