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 $\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.

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