CMU talk: Fourier Theoretic Probabilistic Inference over Permutations

Speaker: Jonathan Huang (RI @ CMU)

Venue: NSH 1507

Date: Monday, April 6, 2009

Time: 12:00 noon

Title:

Fourier Theoretic Probabilistic Inference over Permutations

Abstract:

Permutations are ubiquitous in many real-world problems, such as voting, ranking, and data association. Representing uncertainty over permutations, however, is challenging, since there are $n!$ possibilities, and common factorized probability distribution representations, such as graphical models, are inefficient due to the mutual exclusivity constraints that are typically associated with permutations.

I will talk about a recent approach for probabilistic reasoning with permutations based on the idea of approximating distributions using their low-frequency Fourier components. Maintaining the appropriate set of low-frequency Fourier terms corresponds to maintaining matrices of simple marginal probabilities which summarize the underlying distribution. Using these intuitions, I will show how to derive the Fourier coefficients of a variety of probabilistic models which arise in practice and that many useful models are either well-approximated or exactly represented by low-frequency (and in many cases, sparse) Fourier coefficient matrices.

In addition to showing that Fourier representations are both compact and intuitive, I will show how to cast common probabilistic inference operations in the Fourier domain, including marginalization, conditioning on evidence, and factoring based on probabilistic independence.

From the theoretical side, our work has tackled several problems in understanding the consequences of the bandlimiting approximation. On this front, I will present illuminating results about the nature of error propagation in the Fourier domain and propose methods for mitigating their effects.

Finally I will demonstrate the approach on several real datasets and show that our methods, in addition to being well-founded theoretically, are also scalable and provide superior results in practice.

joint work with Carlos Guestrin, Leonidas Guibas and Xiaoye Jiang