High-Dimensional Estimation via Graphical Approaches: Methods and Guarantees
Speaker: Anima Anandkumar , UC Irvine
Date: March 12 2012
Time: 3:00PM to 4:00PM
Location: 34-401a
Host: Pablo Parrilo, MIT
Contact: Francis Doughty, 253-4602, doughty@mit.edu
Relevant URL: http://www.eecs.mit.edu/cgi-bin/calendar.cgi?page=2012/data/68.dat
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, where structural or qualitative relationships between the variables are represented via a graph structure, while the parametric or quantitative relationships are represented via values assigned to different groups of nodes on the graph. This decoupling is natural in a number of areas such as computer vision, financial modeling and genetics. In this talk, I will focus on high-dimensional graph estimation which reveals the structural relationships among the variables. I will characterize novel criteria for tractable estimation and develop efficient methods with provable guarantees.
I will first present a simple algorithm for graph estimation based on the notion of approximate conditional independence testing. Under certain structural and parametric criteria, this method is statistically consistent, and has low computational and sample complexities. Many graph families such as the classical Erdos-Renyi random graphs, and the small-world graphs can be learnt efficiently under this framework.
The second part of the work incorporates latent or hidden factors, which are not directly observed. Graph estimation in this context is even more challenging since there is no knowledge of the number or the location of the hidden variables. I will present novel methods with efficient guarantees for latent models Markov on trees, and more generally, on girth constrained graphs. Experiments on newsgroup data reveals interesting relationships between topics and words in the discovered structure, and similar observations are made in financial and social domains. I will conclude the talk by discussing the implications of the above results, and pointing out interesting connections with other areas of electrical engineering, computer science and statistics.
Relevant Papers (available at http://newport.eecs.uci.edu/anandkumar/research.html)
[1] "High-Dimensional Structure Learning of Ising Models: Local
Separation Criterion" by A. Anandkumar, V.Y.F Tan and A.S. Willsky. Accepted to Annals of Statistics, Feb. 2012.
[2] "Learning Latent Tree Graphical Models" by M.J. Choi, V. Tan, A. Anandkumar, and A. Willsky. Journal of Machine Learning Research, volume 12, pp. 1771-1812, May 2011.
[3] "Learning Loopy Graphical Models with Latent Variables: Efficient Methods and Guarantees" by A. Anandkumar and R. Valluvan. Preprint, Jan. 2012.
Biography
Anima Anandkumar has been a faculty at the EECS Dept. at U.C.Irvine since Aug. 2010. Her research interests are in the area of high-dimensional statistics, networking and information theory with a focus on probabilistic graphical models. She was previously at the Stochastic Systems Group at MIT between 2009 and 2010 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. She is among the 14 finalists for the Microsoft Research Faculty fellowship 2012 (final decision awaited).
Detailed CV available at http://newport.eecs.uci.edu/anandkumar/Resume/CV.pdf
See other events that are part of CS Special Seminar Series 2011/2012
See other events happening in March 2012
