Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)
Michael Jordan, Martin J. Wainwright
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. In experimental trials, the performance of the log-determinant relaxation is comparable to or better than the sum-product algorithm, and by a sub- stantial margin for certain problem classes. Finally, the zero-temperature limit of our log-determinant relaxation recovers a class of well-known semidefinite relaxations for integer programming [e.g., 3].