Should We Believe in Numbers Computed by Loopy Belief Propagation?

Pascal O. Vontobel
Hewlett-Packard Laboratories

Monday, November 22, 2010 at 12:30PM
54-134 Engineering IV Building
Refreshments Served

Abstract: Loopy belief propagation (LBP) has been very popular in the last fifteen years in the area of coded data transmission (and beyond) because of its low implementation complexity and its outstanding performance. In this talk, we discuss an analysis technique that allows one to obtain a better understanding of why LBP works so well for some problems, yet also has some limitations.

Although this LBP analysis technique is broadly applicable, to be concrete, we present it in a specific context. Namely, we focus on the use of LBP for estimating the sum of so-called perfect matchings in a weighted complete bipartite graph, a setup that subsumes many interesting counting problems.

Common wisdom would suggest that LBP does not work well in this context because the underlying graph is dense and has many short cycles. However, it turns out that LBP gives a very valuable estimate for this counting problem, and the above-mentioned analysis technique allows us to see why this is so by providing a combinatorial characterization of the LBP-based estimate: on the one hand, this combinatorial characterization gives insights why the LBP-based estimate is useful, on the other hand, it shows why the LBP-based estimate differs in general from the correct value.

At the end, we will contemplate the use of the above LBP-based estimates for the analysis of pseudo-codewords and for kernel-based techniques in machine learning.

Biography: Pascal O. Vontobel received the Diploma degree in electrical engineering in 1997, the Post-Diploma degree in information techniques in 2002, and the Ph.D. degree in electrical engineering in 2003, all from ETH Zurich, Switzerland.

From 1997 to 2002 he was a research and teaching assistant at the Signal and Information Processing Laboratory at ETH Zurich. After being a postdoctoral research associate at the University of Illinois at Urbana-Champaign, at the University of Wisconsin-Madison (visiting assistant professor), and at the Massachusetts Institute of Technology, he joined the Information Theory Research Group at Hewlett-Packard Laboratories in Palo Alto, CA, in the summer of 2006 as a research scientist. His research interests lie in information theory, communications, and signal processing.

Dr. Vontobel is an Associate Editor for the IEEE Transactions on Information Theory, has been on the technical program committees of several international conferences, and has recently co-organized a BIRS workshop in Banff on "Applications of Matroid Theory and Combinatorial Optimization to Information and Coding Theory" and a workshop at Tel Aviv University on "Linear Programming and Message-Passing Approaches to High-Density Parity-Check Codes and High-Density Graphical Models." Moreover, he has been three times a plenary speaker at international information and coding theory conferences and has been awarded the ETH medal for his Ph.D. dissertation.