Tel-Aviv University - Computer Science Colloquium
Sunday, January 9, 14:15-15:15
at 14:00
Schreiber Building, Room 309
Loopy belief propagation ---
from image understanding to error correcting codes
Yair Weiss
UC Berkeley
Abstract:
Algorithms for probability propagation in graphs have been
independently discovered and analyzed in a variety of fields including
artificial intelligence, speech recognition and error-correcting
codes. In these various fields it was shown that the algorithms
converge to the globally correct posterior probabilities for singly
connected graphs. Recently, however, a number of researchers have
empirially demonstrated good performance of these same algorithms
on
graphs with loops. Perhaps the most dramatic instance is the
near
Shannon limit performance of ``Turbo Codes'' whose decoding algorithm
is equivalent to probability propagation on a loopy graph.
I will describe analytical results for probability propagation in
graphs with loops --- including sufficient conditions for convergence
and a formula relating the correct probabilities with the probabilities
calculated using propagation algorithms. This leads to a category
of
loopy graphs for which the decision based on probability propagation
can be proven to be optimal (although the probabilities will be
incorrect). I will illustrate the analysis using examples
from image
understanding and error-correcting codes.
For colloquium schedule, see
http://www.math.tau.ac.il/~zwick/colloq.html