Graphical models are a powerful framework used to succinctly represent high-dimensional distributions, and play a fundamental role in modern large-scale statistical inference. The graph underlying such a distribution specifies interactions between the variables, and explicitly captures the computational aspect inherent to statistical tasks. For unstructured settings such as those found in social networks, biology, and finance, a central problem is to determine a good model from observed data.
Learning graphical models from high-dimensional data is computationally challenging, and many different algorithms have been proposed over the years. Nevertheless, it is not clear what classes of models can be learned efficiently. In this talk we explore the problem from several angles and obtain a relatively unified view of what determines the computational complexity of learning graphical models. At the core of the approach lies a simple information-theoretic structural property of graphical models, which leads to efficient learning algorithms.
Guy Bresler is currently a postdoctoral associate at the Laboratory for Information and Decision Systems at MIT. His research interests are at the interface of computation, statistics, and information theory. He received his Ph.D. from the Dept. of Electrical Engineering and Computer Sciences at UC Berkeley, and his B.S. in electrical and computer engineering and M.S. in mathematics from the Univ. of Illinois at Urbana-Champaign. He has received several fellowships and awards including the NSF graduate research fellowship and a Vodafone Foundation fellowship.