http://www2.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},
Year= {2007},
Month= {Dec},
Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-146.html
%F El Ghaoui:EECS-2007-146

```