High-Dimensional Structure Learning of Graphical Models: Trees, Latent trees and Beyond

Friday, January 28, Giedt Hall 1002, 12:00pm-1:00pm

Prof. Anima Anandkumar
UC Irvine

Host: Professor Anna Scaglione


Graphical models or Markov random fields provide a graph-based framework for capturing dependencies between random variables of a large-scale multivariate distribution. This interdisciplinary topic has found widespread application in a variety of areas including image processing, bioinformatics, combinatorial optimization and machine learning. Estimating the graph structure of the model using samples drawn from it forms an important task, since the structure reveals important relationships between the variables. However, structure estimation has several challenges: in general graphical models, it is NP-hard, the models are typically in the high-dimensional regime where the number of variables is much larger than the number of samples obtained, and there could be many latent variables which are unobserved. I will address these challenges in the talk and provide solutions for certain classes of models.

I will focus on latent tree models. These are tree graphical models where there are latent variables, but there is no knowledge of the number or the location of the latent variables. We have developed two novel algorithms which are consistent, computationally efficient and have low sample complexity. These algorithms are based on the presence of an additive metric on the tree, due to the properties of correlations on a tree model. The first algorithm uses these properties to check for sibling relationships between node pairs and builds the tree in a recursive fashion. The second algorithm initially builds a tree over the observed variables, and then adds hidden nodes in a step-by-step fashion by only operating on small subsets of variables. This leads to considerable computational savings compared to the first algorithm. We modify the second algorithm for experiments on real data by trading off number of added latent variables with the accuracy of resulting model fitting via the Bayesian Information Criterion (BIC). Experiments on the S&P 100 monthly returns data and on the occurrence of words in newsgroups reveal interesting relationships.


Dr. Anima Anandkumar received her B.Tech in Electrical Engineering from the Indian Institute of Technology (IIT) Madras in 2004 and her MS and PhD degrees in Electrical Engineering from Cornell University, Ithaca, NY in 2009. She was at the Stochastic Systems Group at MIT, Cambridge, MA as a post-doctoral researcher. She has been an assistant professor at EECS Dept. at U.C.Irvine since July 2010. She is the recipient of the 2009 Best Thesis Award by the ACM Sigmetrics Society, 2008 IEEE Signal Processing Society Young Author Best Paper Award, 2008 IBM Fran Allen PhD fellowship, and student paper award at 2006 IEEE ICASSP. Her research interests are in the area of statistical-signal processing, network theory and information theory.