February 10, 2012, David Gamarnik, Massachusetts Institute of Technology
Friday, February 10, 2012 at 3:00 PM
8 St. Mary’s Street, Room 203
Refreshments served at 2:45.
David Gamarnik
Massachusetts Institute of Technology
Correlation Decay Property and Inference in Markov Random Fields
Loosely speaking, a stochastic system exhibits the correlation decay property if correlations between components of the system decay as a function of the distance between the components. The notion appears primarily in the context of Gibbs measures in statistical physics and Markov random field inference, but also appears to have interesting algorithmic applications.
We illustrate how the correlation decay property can be used for designing a polynomial time deterministic approximation algorithm, which we call cavity expansion algorithm, for the problem of computing the partition function of a Markov random field. Prior algorithms for this problem rely primarily on the Monte Carlo simulation technique and thus suffer from the sampling error. One can view the cavity expansion algorithm as a corrected Belief Propagation algorithm applied to graphs with loops. We will illustrate our method on a stylized Markov random field model: counting partial matchings in a graph – a well known #P hard problem. Then we will demonstrate the practicality of our approach for the problem on inference on some lattice models. Specifically, we compute the entropy of monomer-dimer coverings of a lattice, improving earlier estimations by several orders of magnitude.
David Gamarnik is an Associate Professor of Operations Research at the Sloan School of Management of Massachusetts Institute of Technology. He received B.A. in mathematics from New York University in 1993 and Ph.D. in Operations Research from MIT in 1998. Since then he worked in the Department of Mathematical Sciences, IBM Research, before joining MIT in 2005.
His research interests include applied probability and stochastic processes, theory of random graphs and algorithms, combinatorial optimization, statistical learning theory and various applications. He is a recipient of the Erlang Prize and Best Publication Award for 2011, both from the INFORMS Applied Probability Society. He is also a recipient of the IBM Faculty Partnership Award and several NSF sponsored grants. He is an associate editor of the Annals of Applied Probability, Operations Research, Mathematics of Operations Research, Stochastic Systems, and Queueing Systems journals.
Hosting Professor: Erol Pekoz
Student Host: Yanfeng Geng