# Fast Approximate Counting by Loopy Belief Propagation

## Start:

4/29/2013
at
2:00PM

## End:

4/29/2013
at
3:00PM

## Location:

258 Fitzpatrick Hall## Host:

College of Engineering
close button

# Martin Haenggi

VIEW FULL PROFILE

**Email:**mhaenggi@nd.edu**Phone:**574-631-6103**Website:**http://www.nd.edu/~mhaenggi/**Office:**274 Fitzpatrick Hall### Affiliations

Department of Electrical Engineering
Professor

College of Engineering
Professor

Wireless Institute
Professor

Research Interests: - Information Theory for Mobile Ad Hoc Networks (IT-MANET): The goal of this project is to find the fundamental performance limits of mobile ad hoc networks in terms of throughput, delay, and reliability. It involves 12 investigators from 8 institutions and it support by ...

Click for more information about
Martin
574-631-6103

Many problems in communications, machine learning, and other fields requirethe (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.

## Seminar Speaker:

### Pascal Vontobel

###### Hewlett Packard Laboratories

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 2006 as a research scientist. 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.