Wednesday, Sept 23, 2009 at 12 noon. Room TBA.
Belief propagation (BP) is a
widely-used message-passing algorithm that approximately computes marginal
distributions in graphical models. A wide variety of computational problems can
be formulated as inference problems in such models, and BP and its variants
such as the min-sum algorithm perform empirically well in application areas
including coding theory, statistical physics, and linear programming. However,
rigorously characterizing their behavior outside of a few well-structured
instances has proven challenging.
In this talk, I will present
a new approach to understanding the behavior of the min-sum algorithm by
exploiting the properties of graph covers.
I will first motivate this approach by demonstrating that the standard
sufficient conditions for convergence of min-sum in the case of quadratic
minimization have a natural analog in terms of graph covers. I will then explain how to use graph covers
to understand the frequently-observed periodic behavior of the min-sum
algorithm in some important special cases. Finally, I will show how to use
these results to recover useful estimates from the min-sum algorithm even in
the presence of periodic behavior. Some of our techniques apply more broadly,
and we believe that by capturing the notion of indistinguishability,
graph covers represent a valuable tool for understanding the abilities and
limitations of general message-passing algorithms.
Joint work
with Nicholas Ruozzi and Sekhar
Tatikonda of