Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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