Dynamics and geometry from high dimensional data

Universality of Mallows’ and degeneracy of Kendall’s kernels for rankings

Aaditya Ramdas

CMU

Kernel methods provide an attractive framework for aggregating and learning from ranking data, and so understanding the fundamental properties of kernels over permutations (the symmetric group) is a question of broad interest. We provide a detailed analysis of the Fourier spectra of the standard Kendall and Mallows kernels, and a new class of polynomial-type kernels. We prove that the Kendall kernel has exactly two irreducible representations at which the Fourier transform is non-zero, and moreover, the associated matrices are rank one. This implies that the Kendall kernel is nearly degenerate, with limited expressive and discriminative power. In sharp contrast, we prove that the Fourier transform of the Mallows kernel is a strictly positive definite matrix at all irreducible representations. This property guarantees that the Mallows kernel is both characteristic and universal. We introduce a family of normalized polynomial kernels of degree p that interpolates between the Kendall (degree one) and Mallows (infinite degree) kernels, and show that for d-dimensional permutations, the pth-degree kernel is characteristic when p is larger than d ? 1, unlike the Euclidean case in which no finite-degree polynomial kernel is characteristic. We also derive an explicit finite-dimensional feature map for the Mallows kernel, which allow computations in primal form. We demonstrate applications to testing, regression and classification using a Eurobarometer survey dataset where we have access to respondents’ features (age/gender/…) as well as their rankings over sources of information (internet/tv/radio/newspaper/...).