Walk-Sum
Analysis and Interpretation of Gaussian Belief Propagation
Dmitry Malioutov
SSG, LIDS, MIT
We describe a powerful new framework based on walks in a graph for
analysis and inference in Gaussian graphical models. The key idea
is to decompose correlations between variables as an infinite sum over
all walks between those variables in the graph. The weight of each
walk is given by a product of edgewise partial correlation
coefficients. We provide a walk-sum interpretation of Gaussian belief
propagation in trees and of the approximate method of loopy belief
propagation in graphs with cycles. This perspective leads to a better
understanding of Gaussian belief propagation and to stronger results
for its convergence in loopy graphs.
Problems with this site should be emailed to jonesb@mit.edu