Probability Distributions on Permutations: Compact Representations and Inference

author: Jonathan Huang, Robotics Institute, School of Computer Science, Carnegie Mellon University
published: April 17, 2008,   recorded: March 2008,   views: 9826

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


Permutations arise in a variety of real-world problems, such as voting, ranking, and data association. Representing uncertainty over permutations, however, is difficult since there are n! permutations, and unlike many problems, they cannot be represented effectively by graphical models due to the mutual exclusivity constraints typically associated with permutations. I will present a more effective representation which uses the "low-frequency'' terms of a Fourier decomposition to represent distributions over permutations compactly. For such representations to be truly useful, we need to be able to efficiently do inference, and to this end, I will discuss a set of useful inference operations, including marginalization and conditioning, which work completely in the Fourier domain. Performing inference on low frequency Fourier-based approximations, can often lead to functions which do not correspond to any valid distribution. To combat such errors, I will talk about a method for projecting approximations to a relaxed marginal polytope and demonstrate the effectiveness of the approach on a real camera-based multi-person tracking scenario. Finally, I will talk about approaches for splitting a distribution into independent factors and the inverse problem of merging independent factors to form a joint in the Fourier domain. I will discuss how the splitting and joining operations can be applied to our ongoing work on "adaptive inference", where we exploit independence in order to gain speedups for inference. This is joint work with Carlos Guestrin and Leonidas Guibas.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 julia, April 25, 2008 at 9:47 p.m.:

wow! the speaker is hot and he's smart

Comment2 Lourdes, August 20, 2009 at 11:34 p.m.:

Yes, he is indeed quite hot!

Write your own review or comment:

make sure you have javascript enabled or clear this field: