Exploiting Probabilistic Independence for Permutations

Jonathan Huang, Carlos Guestrin, Xiaoye Jiang, Leonidas Guibas
Proceedings of the Twelfth 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 = {Huang, Jonathan and Guestrin, Carlos and Jiang, Xiaoye and Guibas, Leonidas}, booktitle = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics}, pages = {248--255}, year = {2009}, editor = {van Dyk, David and Welling, Max}, 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 = {https://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 Twelfth 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 %P 248--255 %U https://proceedings.mlr.press/v5/huang09b.html %V 5 %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 Twelfth International Conference on Artificial Intelligence and Statistics DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-huang09b PB - PMLR DP - Proceedings of Machine Learning Research VL - 5 SP - 248 EP - 255 L1 - http://proceedings.mlr.press/v5/huang09b/huang09b.pdf UR - https://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 Twelfth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 5:248-255 Available from https://proceedings.mlr.press/v5/huang09b.html.

Related Material