Model Selection Through Sparse Maximum Likelihood Estimation for Multivariate Gaussian or Binary Data

摘要

We consider the problem of estimating the parameters of a Gaussian orbinary distribution in such a way that the resulting undirectedgraphical model is sparse. Our approach is to solve a maximumlikelihood problem with an added l₁-norm penalty term. Theproblem as formulated is convex but the memory requirements andcomplexity of existing interior point methods are prohibitive forproblems with more than tens of nodes. We present two new algorithmsfor solving problems with at least a thousand nodes in the Gaussiancase. Our first algorithm uses block coordinate descent, and can beinterpreted as recursive l₁-norm penalized regression. Oursecond algorithm, based on Nesterov's first order method, yields acomplexity estimate with a better dependence on problem size thanexisting interior point methods. Using a log determinant relaxationof the log partition function (Wainwright and Jordan, 2006), we show that thesesame algorithms can be used to solve an approximate sparse maximumlikelihood problem for the binary case. We test our algorithms onsynthetic data, as well as on gene expression and senate votingrecords data. color="gray">