Directional Statistics on Permutations

Sergey M. Plis, Stephen McCracken, Terran Lane, Vince D. Calhoun

Abstract

Performing Bayesian inference over the space of permutations is a significant challenge in combinatorial optimization due to the factorial growth of the state space. This paper introduces a geometric approach that embeds the discrete space of $n!$ permutations into a continuous hypersphere. By utilizing directional statistics, specifically the von Mises-Fisher distribution, the authors develop a scalable recursive Bayesian filter for tracking and ranking. The method is evaluated on synthetic data, air traffic control records, and visual surveillance datasets, demonstrating superior scalability and efficiency compared to existing Fourier-based techniques.

Introduction

Permutations are fundamental to tasks like multi-object tracking and ranking. However, the space of permutations for $n$ objects grows at a rate of $n!$, making explicit representation of probability distributions impossible for even moderately sized $n$. Previous attempts using Fourier analysis or metric-based methods often suffer from high computational complexity or lack the smooth structure necessary for standard analytic tools. This work bridges the gap between unstructured combinatorial sets and structured continuous spaces by embedding permutations into a hypersphere.

Methods

The authors propose a geometric solution that maps the discrete space of permutations into a continuous domain where directional statistics can be applied.

The Hypersphere Embedding

Permutation matrices of size $n \times n$ are treated as vectors in $\mathbb{R}^{n^2}$. The authors leverage the fact that these matrices are the extreme points of the Birkhoff polytope (the set of all doubly stochastic matrices). They prove that these $n!$ points lie on the surface of a hypersphere within a lower-dimensional subspace of dimension $(n-1)^2$. This embedding is advantageous because it preserves the "closeness" of permutations; for instance, permutations differing by a single swap remain nearby in the continuous space.

Directional Statistics and the vMF Distribution

Once mapped to the sphere, the authors employ the von Mises-Fisher (vMF) distribution, often considered the spherical analogue of the Gaussian distribution. It is defined by a mean direction $\mu$ and a concentration parameter $\kappa$.

The von Mises-Fisher distribution on a sphere, representing a probability density centered around a mean direction.

Efficient Projections and Filtering

The transition between discrete permutations and continuous spherical points is computationally efficient. Mapping to the sphere involves a linear shift and basis change ($O(n^4)$). The inverse mapping—finding the permutation closest to a point on the sphere—is formulated as a minimum weighted bipartite matching problem, solvable in polynomial time. This framework allows for the derivation of a recursive Bayesian filter, similar to a Kalman filter, which updates the distribution over permutations as noisy observations are received.

Experimental Evaluation

The model was tested across three distinct scenarios:

  1. Synthetic Data: Tracking up to 50 objects with varying noise levels.
  2. Air Traffic Control: Managing identities of aircraft near JFK airport, a standard benchmark for identity management.
  3. Visual Surveillance: Tracking 41 players in a soccer match (PETS dataset), demonstrating the model's ability to handle large-scale, real-world tracking.
Evolution of the probability distribution over permutations during a tracking task, showing the concentration of the vMF distribution as more data is observed.

Key Results and Insights

The proposed approach demonstrates significant improvements in scalability and efficiency. While Fourier-based methods struggle beyond $n=15$, this framework handles over 50 objects with ease. For 80 objects, the mean convergence time was approximately 17.2 seconds on 2011-era hardware. On the JFK dataset, the vMF filter achieved error rates (0.12–0.17) comparable to state-of-the-art methods but with much lower computational cost.

A critical insight is the handling of partial observations. In the hypersphere representation, marginalizing out missing objects corresponds to another vMF distribution, allowing for an elegant treatment of incomplete data.

Conclusion and Future Work

This work provides a robust framework for Bayesian inference on permutations by leveraging the geometry of the hypersphere. While the marginalization step requires an approximation using angular Gaussians, the results are highly accurate in practice. Future research may explore more complex spherical distributions or the use of spherical harmonics to represent multi-modal distributions.

Summary updated

Abstract

Distributions over permutations arise in applications ranging from multi-object tracking to ranking of instances. The difficulty of dealing with these distributions is caused by the size of their domain, which is factorial in the number of considered entities ($n!$). It makes the direct definition of a multinomial distribution over permutation space 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 $\mathbbm{R}^{(n-1)^2}$. As a result of the embedding, we acquire 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.
BibTeX
@inproceedings{plis2011directional,
  author = {Sergey M. Plis and Stephen McCracken and Terran Lane and Vince D. Calhoun},
  title = {{Directional Statistics on Permutations}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2011},
  url = {https://openreview.net/forum?id=GEQzy6lgrt},
}
Figure