Laurent El Ghaoui

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-146

December 10, 2007

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