On Iteratively Constraining the Marginal Polytope for Approximate Inference and MAP

We propose a cutting-plane style algorithm for finding the maximum a posteriori (MAP) state and approximately inferring marginal probabilities in discrete Markov Random Fields (MRFs). The variational formulation of both problems consists of an optimization over the marginal polytope, with the latter having an additional non-linear entropy term in the objective. While there has been significant progress toward approximating the entropy term, the marginal polytope is generally approximated by the local consistency constraints, which give only a loose outer bound. Our algorithm efficiently finds linear constraints that are violated by points outside of the marginal polytope, making use of the cut polytope, which has been studied extensively in the context of MAX-CUT. We demonstrate empirically that our algorithm finds the MAP solution for a larger class of MRFs than before. We also show that tighter yet efficient relaxations of the marginal polytope result in more accurate pseudomarginals.