Martin J. Wainwright and Michael I. Jordan

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-03-1226

, 2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1226.pdf

We present a new method for calculating approximate marginals for probability distributions defined by graphs with cycles, based on a Gaussian entropy bound combined with a semidefinite outer bound on the marginal polytope. This combination leads to a log-determinant maximization problem that can be solved by efficient interior point methods. As with the Bethe approximation and its generalizations, the optimizing arguments of this problem can be taken as approximations to the exact marginals. In contrast to Bethe/Kikuchi approaches, our variational 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. Such upper bounds are of interest in their own right (e.g., for parameter estimation, large deviations exponents, combinatorial enumeration). Finally, we show that taking the zero-temperature limit of our log-determinant relaxation recovers a class of well-known semidefinite relaxations for integer programming.

---

BibTeX citation:

@techreport{Wainwright:CSD-03-1226,
    Author= {Wainwright, Martin J. and Jordan, Michael I.},
    Title= {Semidefinite Relaxations for Approximate Inference on Graphs with Cycles},
    Year= {2003},
    Month= {Jan},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5347.html},
    Number= {UCB/CSD-03-1226},
    Abstract= {We present a new method for calculating approximate marginals for probability distributions defined by graphs with cycles, based on a Gaussian entropy bound combined with a semidefinite outer bound on the marginal polytope. This combination leads to a log-determinant maximization problem that can be solved by efficient interior point methods. As with the Bethe approximation and its generalizations, the optimizing arguments of this problem can be taken as approximations to the exact marginals. In contrast to Bethe/Kikuchi approaches, our variational 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. Such upper bounds are of interest in their own right (e.g., for parameter estimation, large deviations exponents, combinatorial enumeration). Finally, we show that taking the zero-temperature limit of our log-determinant relaxation recovers a class of well-known semidefinite relaxations for integer programming.},
}

EndNote citation:

%0 Report
%A Wainwright, Martin J. 
%A Jordan, Michael I. 
%T Semidefinite Relaxations for Approximate Inference on Graphs with Cycles
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1226
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5347.html
%F Wainwright:CSD-03-1226