Many problems in communications, machine learning, and other fields require the (weighted) counting of objects. For example, the information rate of a communication channel is related to counting the number of sequences that can be distinguished at the receiver, the computation of certain kernels in machine learning is related to computing weighted sums, etc. Moreover, because of real-time or other constraints, many of these applications require fast counting methods, even if these methods count only approximately.
In this talk, we explore the use of loopy belief propagation (LBP) for fast approximate counting. In particular, we focus on the use of LBP for estimating the sum of 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.
We discuss why this is the case by presenting an LBP analysis technique that gives 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 usually differs from the correct value. This generally applicable LBP analysis technique allows one also to understand why LBP works so well for some counting problems, yet also has some limitations when dealing with other counting problems.
At the end, we will contemplate the use of the above LBP-based estimates in the context of pattern maximum likelihood distribution estimation, the computation of certain two-dimensional data storage capacities, for the analysis of pseudo-codewords, and for kernel-based techniques in machine learning.
(The talk is planned to be accessible to an audience with a general background in communications and/or machine learning.)
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 was a research scientist with the Information Theory Research Group at Hewlett-Packard Laboratories in Palo Alto, CA, USA, from 2006 to 2013. Currently, he is a visiting scholar at Stanford University. His research interests lie in information theory, communications, and signal processing.
Dr. Vontobel has been an Associate Editor for the IEEE Transactions on Information Theory, has been on the technical program committees of several international conferences, and has co-organized several topical workshops, most recently a workshop at Princeton University on “Counting, Inference, and Optimization on Graphs.” 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.
