  Permutation-valued features arise in a variety of applications, either in a
direct way when preferences are elicited over a collection of items, or an
indirect way in which numerical ratings are converted to a ranking. To date,
there has been relatively limited study of regression, classification, and
testing problems based on permutation-valued features, as opposed to
permutation-valued responses. This paper studies the use of reproducing kernel
Hilbert space methods for learning from permutation-valued features. These
methods embed the rankings into an implicitly defined function space, and allow
for efficient estimation of regression and test functions in this richer space.
Our first contribution is to characterize both the feature spaces and spectral
properties associated with two kernels for rankings, the Kendall and Mallows
kernels. Using tools from representation theory, we explain the limited
expressive power of the Kendall kernel by characterizing its degenerate
spectrum, and in sharp contrast, we prove that Mallows' kernel is universal and
characteristic. We also introduce families of polynomial kernels that
interpolate between the Kendall (degree one) and Mallows' (infinite degree)
kernels. We show the practical effectiveness of our methods via applications to
Eurobarometer survey data as well as a Movielens ratings dataset.
