Columbia University Joint CS/EE Networking Seminar Series


High Dimensional Graphical Model Selection: Tractable Graph Families and Latent Tree Models

Prof. Anima Anandkumar

EECS Dept., U.C. Irvine

Wednesday, August 31st at 11am CS Conference Room (4th floor MUDD)



Abstract: Capturing complex interactions among a large set of variables is a challenging task. Probabilistic graphical models or Markov random fields provide a graph-based framework for capturing such dependencies. Graph estimation is an important task, since it reveals important relationships among the variables. I will present a unified view of graph estimation and propose a simple local algorithm for graph estimation using only low-order statistics of the data. We establish that the algorithm has consistent graph estimation with low sample complexity for a class of graphical models satisfying certain structural and parameter criteria. We explicitly characterize these model classes and point out interesting relationships between the graph structure and the parameter regimes, required for tractable learning. Many graph families such as the classical Erdos-Renyi random graphs, random regular graphs, and the small-world graphs can be learnt efficiently under our framework.

The second part of the work is motivated by the following question: can we discover hidden influences acting on the observed variables? We consider latent tree models for capturing hidden relationships. We develop novel algorithms for learning the unknown high-dimensional latent tree structure. Our algorithm is amenable to efficient implementation of the Bayesian Information Criterion (BIC) to tradeoff the number of hidden variables with the accuracy of the model fitting. Experiment on the S&P 100 financial data reveals sectorization of the companies and experiment on the newsgroups data automatically categorizes words into different topics.

Speaker Biography: Anima Anandkumar has been a faculty at the EECS Dept. at U.C.Irvine since Aug. 2010. She was previously at the Stochastic Systems Group at MIT as a post-doctoral researcher. She received her B.Tech in Electrical Engineering from IIT Madras in 2004 and her PhD from Cornell University in 2009. She is the recipient of the 2011 ACM Sigmetrics Best Paper Award, 2009 ACM Sigmetrics Best Thesis Award, 2008 IEEE Signal Processing Society Young Author Best Paper Award, and 2008 IBM Fran Allen PhD fellowship. Her research interests are in the area of high-dimensional statistics, networking and information theory with a focus on probabilistic graphical models.