We propose new positive definite kernels for permutations. First we introduce
a weighted version of the Kendall kernel, which allows to weight unequally the
contributions of different item pairs in the permutations depending on their
ranks. Like the Kendall kernel, we show that the weighted version is invariant
to relabeling of items and can be computed efficiently in $O(n \ln(n))$
operations, where $n$ is the number of items in the permutation. Second, we
propose a supervised approach to learn the weights by jointly optimizing them
with the function estimated by a kernel machine. Third, while the Kendall
kernel considers pairwise comparison between items, we extend it by considering
higher-order comparisons among tuples of items and show that the supervised
approach of learning the weights can be systematically generalized to
higher-order permutation kernels.

本文提出了若干种排列的正定核函数，其中包括了 Kendall 核函数、加权 Kendall 核函数，探究了它们的优化方法和在高阶排列核函数上的推广。

排列的加权 Kendall 和高阶核

The Weighted Kendall and High-order Kernels for Permutations

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.

研究使用再生核希尔伯特空间方法从排列值特征中学习，并通过表征两个核的特征空间、谱特性、多项式核等方法展示实用性。