Probability models based on graphs, such as Markov random fields (MRFs), are used in many areas of the statistical and computational sciences. The problem of graphical model selection is the following: given a set of samples drawn from some MRF, determine the unknown graph that underlies it. This problem arises in many applications, including social network modeling, genome analysis, and spatial statistics. In the worst-case setting, it is known to be computationally intractable but this does not preclude algorithms that are efficient for typical problems.
In this talk, we begin with an introduction to the problem of graphical model selection and some of its applications. We then discuss some practical methods (meaning polynomial-time in problem parameters) for solving the graphical model selection problem. We show how methods based on $\ell_1$-regularized likelihood (or pseudolikelihood) can be used to recover the graph structure efficiently. Time-permitting, we compare the performance of these practical algorithms to the fundamental (information-theoretic) limits of graphical model selection.
Based on joint works with: John Lafferty (CMU), Garvesh Raskutti (Berkeley), Pradeep Ravikumar (UT Austin), and Prasad Santhanam (UW Hawaii), and Bin Yu (Berkeley).
BioMartin Wainwright joined the faculty at University of California at Berkeley in Fall 2004, with a joint appointment between the Department of Statistics and the Department of Electrical Engineering and Computer Sciences. He received his Bachelor's degree in Mathematics from University of Waterloo, and his Ph.D. degree in Electrical Engineering and Computer Science (EECS) from Massachusetts Institute of Technology (MIT), for which he was awarded the George M. Sprowls Prize from the MIT EECS department in 2002. He is interested in large-scale statistical models, and their applications to communication and coding, machine learning, and statistical signal and image processing. He has received an NSF-CAREER Award (2006), an Alfred P. Sloan Foundation Research Fellowship (2005), an Okawa Research Grant in Information and Telecommunications (2005), the 1967 Fellowship from the Natural Sciences and Engineering Research Council of Canada (1996--2000), and several outstanding conference paper awards.