Learning Probability Distributions over Permutations by Means of Fourier Coefficients

Abstract

A large and increasing number of data mining domains consider data that can be represented as permutations. Therefore, it is important to devise new methods to learn predictive models over datasets of permutations. However, maintaining models, such as probability distributions, over the space of permutations is a hard task since there are n! permutations of n elements. Recently the Fourier transform has been successfully generalized to functions over permutations and offers an attractive way to represent uncertainty over the space of permutations. One of its main advantages is that the Fourier transform compactly summarizes approximations to functions by discarding high order marginals information. Moreover, a lately proposed framework for making inference completely in the Fourier domain has opened new doors for efficiently reasoning over a space of permutations. In this paper, we present a method to learn a probability distribution that approximates the generating distribution of a given sample of permutations. Particularly, this method learns the Fourier domain information representing this probability distribution.