# A Convex Upper Bound on the Log-Partition Function for Binary Graphical Models

### Laurent El Ghaoui

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2007-146

December 10, 2007

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-146.pdf

We consider the problem of bounding from above the log-partition function corresponding to second-order Ising models for binary distributions. We introduce a new bound, the cardinality bound, which can be computed via convex optimization. The corresponding error on the log-partition function is bounded above by twice the distance, in model parameter space, to a class of ``standard'' Ising models, for which variable inter-dependence is described via a simple mean field term. In the context of maximum-likelihood, using the new bound instead of the exact log-partition function, while constraining the distance to the class of standard Ising models, leads not only to a good approximation to the log-partition function, but also to a model that is parsimonious, and easily interpretable. We compare our bound with the log-determinant bound introduced by Wainwright and Jordan (2006), and show that when the $l_1$-norm of the model parameter vector is small enough, the latter is outperformed by the new bound.

BibTeX citation:

@techreport{El Ghaoui:EECS-2007-146, Author = {El Ghaoui, Laurent}, Title = {A Convex Upper Bound on the Log-Partition Function for Binary Graphical Models}, Institution = {EECS Department, University of California, Berkeley}, Year = {2007}, Month = {Dec}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-146.html}, Number = {UCB/EECS-2007-146}, Abstract = {We consider the problem of bounding from above the log-partition function corresponding to second-order Ising models for binary distributions. We introduce a new bound, the cardinality bound, which can be computed via convex optimization. The corresponding error on the log-partition function is bounded above by twice the distance, in model parameter space, to a class of ``standard'' Ising models, for which variable inter-dependence is described via a simple mean field term. In the context of maximum-likelihood, using the new bound instead of the exact log-partition function, while constraining the distance to the class of standard Ising models, leads not only to a good approximation to the log-partition function, but also to a model that is parsimonious, and easily interpretable. We compare our bound with the log-determinant bound introduced by Wainwright and Jordan (2006), and show that when the $l_1$-norm of the model parameter vector is small enough, the latter is outperformed by the new bound.} }

EndNote citation:

%0 Report %A El Ghaoui, Laurent %T A Convex Upper Bound on the Log-Partition Function for Binary Graphical Models %I EECS Department, University of California, Berkeley %D 2007 %8 December 10 %@ UCB/EECS-2007-146 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-146.html %F El Ghaoui:EECS-2007-146