Probability Distributions on Permutations: Compact Representations and Inference
published: April 17, 2008, recorded: March 2008, views: 1199
Report a problem or upload filesIf 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.
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 pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !