Title: Message Passing Algorithms for Marginalization
Speaker: Venkat Anantharam, University of California, Berkeley
Date: Friday, March 14, 2003, 4:30pm
Location: CoRE Bldg, DIMACS Seminar Room (room 431), Rutgers University, Busch Campus, Piscataway, NJ
The problem of finding marginals of a product function provides a convenient unifying formulation for a wide range of problems in engineering and science, including extremely important ones such as posterior probability calculations in an estimation framework. Efficient message passing algorithms are known for solving such problems when certain conditional independencies are know to hold a priori. The art of finding a good algorithm for such a problem is usually one of finding a formulation of the problem with useful conditional independencies. We will give a survey of this area, including a look at some of the recently discoved connections with ideas from statistical physics. We will then describe a novel measure-theoretic view of the issues which subsumes significant parts of the existing view. This broadened view allows one to broaden the kinds of conditional independencies one is looking for and can thus lead to efficient algorithms of a rather unconventional kind, relative to those one might discover with the existing formulations, and which appear to have significantly lower complexity than the latter, as we will try to demonstrate through examples.
Seminar Sponsored by DIMACS Special Focus on Computational Information Theory and Coding.