Directional Statistics on Permutations

Sergey M. Plis, Stephen McCracken, Terran Lane, Vince D. Calhoun
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:600-608, 2011.

Abstract

Distributions over permutations arise in applications ranging from multi-object tracking to ranking. The difficulty of dealing with these distributions is caused by the size of their domain, which is factorial in the number of entities (n!). The direct definition of a multinomial distribution over permutation space is impractical for all but a very small n. In this work we propose an embedding of all n! permutations for a given n in a surface of a hypersphere defined in R(n−1)2. As a result, we acquire the ability to define continuous distributions over a hypersphere with all the benefits of directional statistics. We provide polynomial time projections between the continuous hypersphere representation and the n!-element permutation space. The framework provides a way to use continuous directional probability densities and the methods developed thereof for establishing densities over permutations. As a demonstration of the benefits of the framework we derive an inference procedure for a state-space model over permutations. We demonstrate the approach with applications and comparisons to existing models.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-plis11a, title = {Directional Statistics on Permutations}, author = {Plis, Sergey M. and McCracken, Stephen and Lane, Terran and Calhoun, Vince D.}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {600--608}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/plis11a/plis11a.pdf}, url = {https://proceedings.mlr.press/v15/plis11a.html}, abstract = {Distributions over permutations arise in applications ranging from multi-object tracking to ranking. The difficulty of dealing with these distributions is caused by the size of their domain, which is factorial in the number of entities $(n!)$. The direct definition of a multinomial distribution over permutation space is impractical for all but a very small $n$. In this work we propose an embedding of all $n!$ permutations for a given $n$ in a surface of a hypersphere defined in $\mathbb{R}^{(n-1)^2}$. As a result, we acquire the ability to define continuous distributions over a hypersphere with all the benefits of directional statistics. We provide polynomial time projections between the continuous hypersphere representation and the $n!$-element permutation space. The framework provides a way to use continuous directional probability densities and the methods developed thereof for establishing densities over permutations. As a demonstration of the benefits of the framework we derive an inference procedure for a state-space model over permutations. We demonstrate the approach with applications and comparisons to existing models.} }
Endnote
%0 Conference Paper %T Directional Statistics on Permutations %A Sergey M. Plis %A Stephen McCracken %A Terran Lane %A Vince D. Calhoun %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-plis11a %I PMLR %P 600--608 %U https://proceedings.mlr.press/v15/plis11a.html %V 15 %X Distributions over permutations arise in applications ranging from multi-object tracking to ranking. The difficulty of dealing with these distributions is caused by the size of their domain, which is factorial in the number of entities $(n!)$. The direct definition of a multinomial distribution over permutation space is impractical for all but a very small $n$. In this work we propose an embedding of all $n!$ permutations for a given $n$ in a surface of a hypersphere defined in $\mathbb{R}^{(n-1)^2}$. As a result, we acquire the ability to define continuous distributions over a hypersphere with all the benefits of directional statistics. We provide polynomial time projections between the continuous hypersphere representation and the $n!$-element permutation space. The framework provides a way to use continuous directional probability densities and the methods developed thereof for establishing densities over permutations. As a demonstration of the benefits of the framework we derive an inference procedure for a state-space model over permutations. We demonstrate the approach with applications and comparisons to existing models.
RIS
TY - CPAPER TI - Directional Statistics on Permutations AU - Sergey M. Plis AU - Stephen McCracken AU - Terran Lane AU - Vince D. Calhoun BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-plis11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 600 EP - 608 L1 - http://proceedings.mlr.press/v15/plis11a/plis11a.pdf UR - https://proceedings.mlr.press/v15/plis11a.html AB - Distributions over permutations arise in applications ranging from multi-object tracking to ranking. The difficulty of dealing with these distributions is caused by the size of their domain, which is factorial in the number of entities $(n!)$. The direct definition of a multinomial distribution over permutation space is impractical for all but a very small $n$. In this work we propose an embedding of all $n!$ permutations for a given $n$ in a surface of a hypersphere defined in $\mathbb{R}^{(n-1)^2}$. As a result, we acquire the ability to define continuous distributions over a hypersphere with all the benefits of directional statistics. We provide polynomial time projections between the continuous hypersphere representation and the $n!$-element permutation space. The framework provides a way to use continuous directional probability densities and the methods developed thereof for establishing densities over permutations. As a demonstration of the benefits of the framework we derive an inference procedure for a state-space model over permutations. We demonstrate the approach with applications and comparisons to existing models. ER -
APA
Plis, S.M., McCracken, S., Lane, T. & Calhoun, V.D.. (2011). Directional Statistics on Permutations. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:600-608 Available from https://proceedings.mlr.press/v15/plis11a.html.

Related Material