The asymptotics of ranking algorithms
From MaRDI portal
Publication:2438754
Abstract: We consider the predictive problem of supervised ranking, where the task is to rank sets of candidate items returned in response to queries. Although there exist statistical procedures that come with guarantees of consistency in this setting, these procedures require that individuals provide a complete ranking of all items, which is rarely feasible in practice. Instead, individuals routinely provide partial preference information, such as pairwise comparisons of items, and more practical approaches to ranking have aimed at modeling this partial preference data directly. As we show, however, such an approach raises serious theoretical challenges. Indeed, we demonstrate that many commonly used surrogate losses for pairwise comparison data do not yield consistency; surprisingly, we show inconsistency even in low-noise settings. With these negative results as motivation, we present a new approach to supervised ranking based on aggregation of partial preferences, and we develop -statistic-based empirical risk minimization procedures. We present an asymptotic analysis of these new procedures, showing that they yield consistency results that parallel those available for classification. We complement our theoretical results with an experiment studying the new procedures in a large-scale web-ranking task.
Recommendations
Cites work
- 10.1162/1532443041827916
- A least squares solution for paired comparisons with incomplete data
- Convexity, Classification, and Risk Bounds
- Decision-making with the AHP: Why is the principal eigenvector necessary
- Efficient online and batch learning using forward backward splitting
- How to compare different loss functions and their risks
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- scientific article; zbMATH DE number 3073477 (Why is no real title available?)
- Introduction to Information Retrieval
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- NON-NULL RANKING MODELS. I
- On the Generalization Ability of On-Line Learning Algorithms
- Ranking and empirical minimization of \(U\)-statistics
- Relative measurement and its generalization in decision making why pairwise comparisons are central in mathematics for the measurement of intangible factors the analytic hierarchy/network process
- Robust Stochastic Approximation Approach to Stochastic Programming
- Social choice and individual values
- Statistical Analysis of Bayes Optimal Subset Ranking
- Statistical analysis of some multi-category large margin classification methods
- Statistical behavior and consistency of classification methods based on convex risk minimization.
- The asymptotics of ranking algorithms
Cited in
(18)- Fixed-parameter algorithms for Kemeny rankings
- Query-dependent ranking and its asymptotic properties
- A probabilistic framework for the design of instance-based supervised ranking algorithms in an ordinal setting
- Ranking and empirical minimization of \(U\)-statistics
- The asymptotics of ranking algorithms
- New learning methods for supervised and unsupervised preference aggregation
- A Survey of Ranking Theory
- Statistical Analysis of Bayes Optimal Subset Ranking
- Generalized rank-breaking: computational and statistical tradeoffs
- Online learning to rank with top-k feedback
- Analysis of \(k\)-partite ranking algorithm in area under the receiver operating characteristic curve criterion
- A Survey of Ranking Theory
- Ranking with a P-Norm Push
- Collaborative Ranking: An Aggregation Algorithm for Individuals’ Preference Estimation
- Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
- Theory and Applications of Relational Structures as Knowledge Instruments
- Scalable Collaborative Ranking for Personalized Prediction
- Stochastic iterative methods for online rank aggregation from pairwise comparisons
This page was built for publication: The asymptotics of ranking algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2438754)
