Yale University
Department of Statistics
Seminar

Monday, March 31, 2003
4:15 pm

Inference on Graphs with Cycles

Sekhar C. Tatikonda
Department of Electrical Engineering
Yale University

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.  Our analysis relies on the computation tree which represents
an unwrapping of the original graph with respect to the sum-product algorithm.
We show that the convergence and quality of sum-product algorithm is related
to the question of uniqueness of the Gibbs measure defined on the infinite
computation tree. The stationary points of the Bethe variational problem
correspond to different Markov chains defined on this tree. We present
easily testable conditions that insure convergence and we compute rates
of convergence. This framework gives new insights into the mechanics of the
sum-product algorithm.
 

Seminar to be held in Room 107, 24 Hillhouse Avenue at 4:15 pm