Inference for Distributions over the Permutation Group - Robotics Institute Carnegie Mellon University

Inference for Distributions over the Permutation Group

Jonathan Huang, Carlos Ernesto Guestrin, and Leonidas Guibas
Tech. Report, CMU-ML-08-108, Machine Learning Department, Carnegie Mellon University, May, 2008

Abstract

Permutations are ubiquitous in many real-world problems, such as voting, ranking, and data association. Representing uncertainty over permutations is challenging, since there are $n!$ possibilities, and typical compact and factorized probability distribution representations, such as graphical models, cannot capture the mutual exclusivity constraints associated with permutations. In this paper, we use the ``low-frequency'' terms of a Fourier decomposition to represent distributions over permutations compactly. We present emph{Kronecker conditioning}, a novel approach for maintaining and updating these distributions directly in the Fourier domain, allowing for polynomial time bandlimited approximations. Low order Fourier-based approximations, however, may lead to functions that do not correspond to valid distributions. To address this problem, we present a quadratic program defined directly in the Fourier domain for projecting the approximation onto a relaxation of the polytope of legal marginal distributions. We demonstrate the effectiveness of our approach on a real camera-based multi-person tracking scenario.

BibTeX

@techreport{Huang-2008-9971,
author = {Jonathan Huang and Carlos Ernesto Guestrin and Leonidas Guibas},
title = {Inference for Distributions over the Permutation Group},
year = {2008},
month = {May},
institute = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-ML-08-108},
}