Partial optimality by pruning for map-inference with general graphical models

We consider the energy minimization problem for undi-rected graphical models, also known as MAP-inference problem for Markov random fields which is NP-hard in general. We propose a novel polynomial time algorithm to obtain a part of its optimal non-relaxed integral solu-tion. Our algorithm is initialized with variables taking integral values in the solution of a convex relaxation of the MAP-inference problem and iteratively prunes those, which do not satisfy our criterion for partial optimality. We show that our pruning strategy is in a certain sense theoretically optimal. Also empirically our method out-performs previous approaches in terms of the number of persistently labelled variables. The method is very gen-eral, as it is applicable to models with arbitrary factors of an arbitrary order and can employ any solver for the considered relaxed problem. Our method’s runtime is de-termined by the runtime of the convex relaxation solver for the MAP-inference problem.