Jonathan Huang, Carlos Guestrin, Xiaoye Jiang, and Leonidas Guibas. Exploiting Probabilistic Independence for Permutations. The Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS), 2009.

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.

Bibtex: 

@inproceedings{hgjg-epip-09,
title = {Exploiting Probabilistic Independence for Permutations},
author = {Jonathan Huang and Carlos Guestrin and Xiaoye Jiang and Leonidas Guibas},
booktitle = {In Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS)},
year = 2009,
month = {April},
address = {Clearwater Beach, Florida},
wwwfilebase = {aistats2009-huang-guestrin-jiang-guibas},
wwwtopic = {Sensor Networks},
}