Select Lab Publications

Exploiting Probabilistic Independence for Permutations (2009)

By: Jonathan Huang, Carlos Guestrin, Xiaoye Jiang, and Leonidas Guibas

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. Recent Fourier-based approaches can be used to provide a compact representation over low-frequency components of the distribution. Though polynomial, the complexity of these representations grows very rapidly, especially if we want to maintain reasonable estimates for peaked distributions. In this paper, we first characterize the notion of probabilistic independence for distributions over permutations. We then present a method for factoring distributions into independent components in the Fourier domain, and use our algorithms to decompose large problems into much smaller ones. We demonstrate that our method provides very significant improvements in terms of running time, on real tracking data.

Download Information
Jonathan Huang, Carlos Guestrin, Xiaoye Jiang, and Leonidas Guibas (2009). "Exploiting Probabilistic Independence for Permutations." In Artificial Intelligence and Statistics (AISTATS). pdf long talk        
BibTeX citation

title = {Exploiting Probabilistic Independence for Permutations},
author = {Jonathan Huang and Carlos Guestrin and Xiaoye Jiang and Leonidas Guibas},
booktitle = {In Artificial Intelligence and Statistics (AISTATS)},
year = 2009,
month = {April},
address = {Clearwater Beach, Florida},
wwwfilebase = {aistats2009-huang-guestrin-jiang-guibas},
wwwtopic = {Sensor Networks},

full list