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

We consider the energy minimization problem for undirected 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 solution. 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 cri-terion for partial optimality. We show that our prun-ing strategy is in a certain sense theoretically optimal. Also empirically our method outperforms previous ap-proaches in terms of the number of persistently labelled variables. The method is very general, as it is appli-cable to models with arbitrary factors of an arbitrary order and can employ any solver for the considered re-laxed problem. Our method’s runtime is determined by the runtime of the convex relaxation solver for the MAP-inference problem. c©(c) IEEE. Persolnal use of this material is permitted. However, permission to reprint/republish this material for advertising or pro-motional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted compo-nent of this work in other works must be obtained from the IEEE. 1