This article is devoted to the problem of predicting the value taken by a random permutation $Σ$, 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$ (\textit{e.g.} characteristics of the individual), when error is measured by the Kendall’s $τ$ 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 $Σ$ given $X$ from i.i.d. training examples $(X_1, \Sigma_1),; \ldots,; (X_N, \Sigma_N)$. For this reason, this statistical learning problem is referred to as \textit{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 $Σ$’s conditional distribution given $X$. The results of various numerical experiments are also displayed for illustration purpose.

Originally formulated in Social Choice theory, Ranking Aggregation, also referred to as Consensus Ranking, has motivated the development of numerous statistical models since the middle of the 20th century. Recently, the analysis of ranking/preference data has been the subject of a renewed interest in machine-learning, boosted by modern applications such as meta-search engines, giving rise to the design of various scalable algorithmic approaches for approximately computing ranking medians, viewed as solutions of a discrete (generally NP-hard) minimization problem. This paper develops a statistical learning theory for ranking aggregation in a general probabilistic setting (avoiding any rigid ranking model assumptions), assessing the generalization ability of empirical ranking medians. Universal rate bounds are established and the situations where convergence occurs at an exponential rate are fully characterized. Minimax lower bounds are also proved, showing that the rate bounds we obtain are optimal.

Due to its numerous applications, rank aggregation has become a problem of major interest across many fields of the computer science literature. In the vast majority of situations, Kemeny consensus(es) are considered as the ideal solutions. It is however well known that their computation is NP-hard. Many contributions have thus established various results to apprehend this complexity. In this paper we introduce a practical method to predict, for a ranking and a dataset, how close the Kemeny consensus(es) are to this ranking. A major strength of this method is its generality: it does not require any assumption on the dataset nor the ranking. Furthermore, it relies on a new geometric interpretation of Kemeny aggregation that, we believe, could lead to many other results.

Statistical analysis of rank data describing preferences over small and variable subsets of a potentially large ensemble of items 1, ..., n is a very challenging problem. It is motivated by a wide variety of modern applications, such as recommender systems or search engines. However, very few inference methods have been documented in the literature to learn a ranking model from such incomplete rank data. The goal of this paper is twofold: it develops a rigorous mathematical framework for the problem of learning a ranking model from incomplete rankings and introduces a novel general statistical method to address it. Based on an original concept of multi-resolution analysis (MRA) of incomplete rankings, it finely adapts to any observation setting, leading to a statistical accuracy and an algorithmic complexity that depend directly on the complexity of the observed data. Beyond theoretical guarantees, we also provide experimental results that show its statistical performance.

Data representing preferences of users are at the core of many Big Data modern applications, such as recommender systems or search engines. While most of the introduced machine learning approaches are designed to handle preference data under the form of cardinal scores, such as ratings given by the users to the items, many situations require to deal with ordinal preferences, coming from implicit feedback data for instance. Methods relying on the analysis of ranking data are best suited for these situations, but they face a great computational challenge insofar as the number of ways to express ordinal preferences on a catalog of n items explodes with n. It is the main purpose of this paper to promote a new representation of preference data when they come under the form of incomplete rankings, that is to say ordinal preferences on small subsets of items. The representation exploits the “multiscale” structure of incomplete rankings and though it relies on recent results in algebraic topology, it is used and interpreted similar to classic wavelet multiresolution analysis on a Euclidean space. We apply it to the problem of incomplete rankings prediction and show at the same time that it is statistically consistent and that it can be computed at a reasonable cost given the complexity of the original data. It is illustrated by very encouraging empirical work based on real datasets.