Exploiting Probabilistic Independence for Permutations

Jonathan Huang, Carlos Guestrin, Xiaoye Jiang, Leonidas Guibas
; Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, PMLR 5:248-255, 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 distribution 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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v5-huang09b, title = {Exploiting Probabilistic Independence for Permutations}, author = {Jonathan Huang and Carlos Guestrin and Xiaoye Jiang and Leonidas Guibas}, booktitle = {Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics}, pages = {248--255}, year = {2009}, editor = {David van Dyk and Max Welling}, volume = {5}, series = {Proceedings of Machine Learning Research}, address = {Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v5/huang09b/huang09b.pdf}, url = {http://proceedings.mlr.press/v5/huang09b.html}, 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 distribution 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.} }
Endnote
%0 Conference Paper %T Exploiting Probabilistic Independence for Permutations %A Jonathan Huang %A Carlos Guestrin %A Xiaoye Jiang %A Leonidas Guibas %B Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2009 %E David van Dyk %E Max Welling %F pmlr-v5-huang09b %I PMLR %J Proceedings of Machine Learning Research %P 248--255 %U http://proceedings.mlr.press %V 5 %W PMLR %X 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 distribution 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.
RIS
TY - CPAPER TI - Exploiting Probabilistic Independence for Permutations AU - Jonathan Huang AU - Carlos Guestrin AU - Xiaoye Jiang AU - Leonidas Guibas BT - Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics PY - 2009/04/15 DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-huang09b PB - PMLR SP - 248 DP - PMLR EP - 255 L1 - http://proceedings.mlr.press/v5/huang09b/huang09b.pdf UR - http://proceedings.mlr.press/v5/huang09b.html AB - 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 distribution 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. ER -
APA
Huang, J., Guestrin, C., Jiang, X. & Guibas, L.. (2009). Exploiting Probabilistic Independence for Permutations. Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, in PMLR 5:248-255

Related Material