Stochastic Systems Group  

Correlation decay property and inference in Markov Random Fields
David Gamarnik
Operations Research, MIT
Loosely speaking, a complex system exhibits a correlation decay property if correlations between components of the system decay as a function of a distance between the components. The notion appears primarily in the context of Gibbs measures in statistical physics and MRF, but appears to have interesting algorithmic applications.
We illustrate how this property can be used for designing scalable deterministic algorithms for the problem of computing the partition function of a MRF. Prior algorithms for this problem rely primarily on Monte Carlo simulations and thus suffer from the sampling error. One can view our approach as a corrected Belief Propagation algorithm applied to graphs with loops. We will illustrate the method on a very simplified MRF model: counting partial matchings in a graph. Then we will demonstrate practicality of our approach for the problem on inference on some low dimensional lattice models.
Problems with this site should be emailed to jonesb@mit.edu