| Description |
Dr. Guy Bresler
The Department of Electrical and Computer Science
Massachusetts Institute of Technology
- - Learning complex structure in data: Efficient Estimation of Graphical Models - -
Abstract:
Graphical models are a powerful framework used to succinctly represent complex high-dimensional distributions, and are at the core of 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.
Structure estimation---finding the graph underlying a graphical model---is algorithmically challenging, and much effort has been directed towards finding algorithms with low computational cost. Nevertheless, for learning the graph structure underlying a binary pairwise interaction (Ising) model on an arbitrary bounded-degree graph, it is not known whether or not it is possible to improve upon the computation-time needed to exhaustively search over all possible neighborhoods for each node.
We show that structure estimation can be accomplished by a simple and efficient greedy procedure. The proof rests on a new structural property of Ising models that for the first time captures the pairwise nature of the interactions between variables. Next, departing from the standard assumption of samples being generated i.i.d. from the model, we suppose that one observes a dynamical process. We show that given samples from the Glauber dynamics, a natural Markov chain, it is possible to efficiently learn arbitrary pairwise graphical models, using almost the information-theoretically minimum number of samples.
Bio:
Guy Bresler is currently a postdoctoral associate at LIDS, 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.
Faculty Host: Professor Bobak Nazer
Light refreshments will be available at 2:45 outside of PHO 339.
|
