Ranking median regression: learning to order through local consensus

zbMATH Open1405.68282arXiv1711.00070MaRDI QIDQ4617604FDOQ4617604

Authors: Stephan Clémençon, Anna Korba, Eric Sibony 

Publication date: 6 February 2019

Abstract: This article is devoted to the problem of predicting the value taken by a random permutation $Sigma$, describing the preferences of an individual over a set of numbered items $1,;ldots,;n$ say, based on the observation of an input/explanatory r.v. $X$ e.g. characteristics of the individual), when error is measured by the Kendall $au$ distance. In the probabilistic formulation of the 'Learning to Order' problem we propose, which extends the framework for statistical Kemeny ranking aggregation developped in citet{CKS17}, this boils down to recovering conditional Kemeny medians of $Sigma$ given $X$ from i.i.d. training examples $(X_1,Sigm{a}_1),;ldots,;(X_N,Sigm{a}_N)$. For this reason, this statistical learning problem is referred to as extit{ranking median regression} here. Our contribution is twofold. We first propose a probabilistic theory of ranking median regression: the set of optimal elements is characterized, the performance of empirical risk minimizers is investigated in this context and situations where fast learning rates can be achieved are also exhibited. Next we introduce the concept of local consensus/median, in order to derive efficient methods for ranking median regression. The major advantage of this local learning approach lies in its close connection with the widely studied Kemeny aggregation problem. From an algorithmic perspective, this permits to build predictive rules for ranking median regression by implementing efficient techniques for (approximate) Kemeny median computations at a local level in a tractable manner. In particular, versions of $k$-nearest neighbor and tree-based methods, tailored to ranking median regression, are investigated. Accuracy of piecewise constant ranking median regression rules is studied under a specific smoothness assumption for $Sigma$'s conditional distribution given $X$.

Full work available at URL: https://arxiv.org/abs/1711.00070

Recommendations

• On kernel methods for covariates that are rankings
• A new approach for identifying the Kemeny median ranking
• Ranking and empirical minimization of \(U\)-statistics
• Experiments with Kemeny ranking: What works when?
• Learning Theory

zbMATH Keywords

consensus rankingdecision treesempirical risk minimizationpredictive learninglocal learningfast ratesnearest-neighborsranking aggregationKemeny median

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Learning and adaptive systems in artificial intelligence (68T05)

Cited In (4)

• Beyond pairwise comparisons in social choice: a setwise Kemeny aggregation problem
• Recognizing single-peaked preferences on an arbitrary graph: complexity and algorithms
• On the median in imprecise ordinal problems
• A new probabilistic approach in rank regression with optimal Bayesian partitioning

This page was built for publication: Ranking median regression: learning to order through local consensus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4617604)