CS Colloq: Efficient, Adaptive Inference for Distributions on Permutations

Title: Efficient, Adaptive Inference for Distributions on PermutationsSpeaker: Prof. Carlos Guestrin (CMU)Abstract:
Permutations are ubiquitous in many real world problems, such as voting, rankings and data association. Representing uncertainty over permutations is challenging, since there are $n!$ possibilities, and typical compact representations, such as graphical models, cannot efficiently capture the mutual exclusivity constraints associated with permutations. In this talk, we use the ``low-frequency'' terms of a Fourier decomposition to represent such distributions compactly. We first describe how the two standard probabilistic inference operations, conditioning and marginalization, can be performed entirely in the Fourier domain in terms of these low frequency components, without ever enumeration $n!$ terms. We also describe a novel approach for adaptively picking the complexity of this representation in order control the resulting approximation error. We demonstrate the effectiveness of our approach on a real camera- based multi-people tracking setting.Biography:
I am an assistant professor in the Machine Learning Department and in the Computer Science Department at Carnegie Mellon University. I co- direct the Sense, Learn, and Act (Select) Lab with Geoff Gordon. In 2003-2004, I spent a year as a senior researcher at the Intel Research Lab in Berkeley. In August 2003, I received my Ph.D. in Computer Science from Stanford University, where I was advised by Daphne Koller, in the DAGS research group. I received a Mechatronics Engineer (Mechanical Engineering, with emphasis in Automation and Systems) degree in 1998 from the Polytechnic School of the University of São Paulo, Brazil.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Colloquia