Abstract

Probabilistic graphical models or Markov random fields provide a graph-based framework for capturing conditional independence relationships between random variables of a high-dimensional 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 from 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 also typically in the high-dimensional regime where the number of variables is much larger than the number of samples obtained. I will address these challenges in the talk.

I will talk about our recent results on learning lsing models on sparse Erdos-Renyi random graphs. We establish achievability of consistent structure learning when the model is in the so-called uniqueness regime, where there is a decay of long-range correlations. The algorithm is based on a set of conditional mutual information tests and is shown to be consistent for structure estimation with almost order-optimal sample complexity. A simpler algorithm based on correlation thresholding is also consistent, but under more stringent conditions. Thus, we establish that correlation decay is a sufficient condition for consistent structure learning in random graphs. We also prove a converse result on the number of samples required by any algorithm to consistently recover the random graph structure. I will also provide an overview on our recent results on structure learning in tree models, and more generally, in latent tree models with hidden variables.