| |
|
| |
|
Alexander Ihler
University of California Irvine
Loopy Belief Propagation: Convergence and Approximations
April 17, 2006 10:00am
Abstract:
Graphical models provide a convenient method of describing probabilistic distributions and statistical dependency in such a way as to enable the development of relatively simple exact or approximate inference algorithms. Perhaps the best known of these algorithms is belief propagation (BP), which formulates an exact procedure for marginalization in simple (cycle-free, or tree-structured) systems in such a way that it can be easily applied to more complex problems.
Although this has often resulted in great success in such problem domains as turbo and LDPC decoding, computer vision, machine learning, and sensor networks, on these more complex problems so-called "loopy"
BP is no longer guaranteed to converge to a unique solution.
However, intuition and empirical findings tell us that loopy BP will be well-behaved on problems which are tree-like, and that there are several factors which may contribute to this being the case. By performing a stability analysis of BP we can quantify many of these notions and derive powerful sufficient conditions for convergence; these conditions appear to be tight for at least a subset of problems.
Moreover, the framework in which this analysis is performed makes it possible to draw many additional conclusions, including bounding the number of iterations required to achieve a particular precision or analyzing the performance of quantized, censored, or otherwise modified BP-like algorithms.
Alexander Ihler received his B.S. degree in Math and Electrical Engineering from the California Institute of Technology in 1998, and S.M. and Ph.D. degrees in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology in 2000 and 2005 as a member of the Stochastic Systems Group. He is currently a Postdoctoral Scholar at the University of California, Irvine. His research interests include statistical signal processing, machine learning, and nonparametric statistics, with applications in computational biology, atmospheric science, and sensor networks.
If you have questions, or would like to meet the speaker, please contact Ponda at 4-1994 or pondabarnes@tti-c.org. For information on future TTI-C talks or events, please go to the TTI-C Events page.