Semidefinite Relaxations for Approximate Inference on Graphs with Cycles

We present a new method for calculating approximate marginals for probability distributions defined by graphs with cycles, based on a Gaus- sian entropy bound combined with a semidefinite outer bound on the marginal polytope. This combination leads to a log-determinant max- imization problem that can be solved by efficient interior point meth- ods [8]. As with the Bethe approximation and its generalizations [12], the optimizing arguments of this problem can be taken as approximations to the exact marginals. In contrast to Bethe/Kikuchi approaches, our vari- ational problem is strictly convex and so has a unique global optimum. An additional desirable feature is that the value of the optimal solution is guaranteed to provide an upper bound on the log partition function.