The Sum-Product Algorithm

The problem of computing marginal statistics of probability distributions
defined over graphs with cycles occurs in many fields: error-correcting
coding, machine learning, communication theory, computer vision, and
statistical physics. Because exact computations are often difficult
approximate algorithms based on local message passing have been developed.
One such algorithm is the sum-product (loopy belief propagation) algorithm.
In this talk we present a new framework for analyzing the sum-product
algorithm. Applications to some combinatorial optimization problems will
be discussed.