Research map / Learning theory and algorithms / Prediction and decision losses
Foundations of the Theory of Performance-Based Ranking
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Establishes a probability- and order-theoretic framework for performance-based ranking, gives three axioms for performance orderings and rankings, and proposes a parametric family of "ranking scores" satisfying them, analyzed for two-class classification.
Problem
Performance-based ranking of entities (algorithms, models, etc.) lacks mathematical foundations: performances, orderings, satisfaction, and application-specific preferences are not rigorously defined, and scores used for ranking are often chosen without justification.
Approach
Model performances as probability measures on a sample space with a preorder, a satisfaction random variable, and an importance random variable encoding application preferences; state three axioms for performance orderings and rankings; and define ranking scores (expected satisfaction under importance-reweighted distribution) that satisfy them.
Key results
- Ranking scores RI are shown to satisfy all three axioms, with the family parameterized by importance I.
- Among 30+ classical two-class scores tested, several (e.g., accuracy, F-score, TPR, TNR, PPV, balanced accuracy, informedness) satisfy the axioms (fully for accuracy, F-score, PPV, NPV, TPR, TNR with fixed priors for some), while others such as MCC, geometric mean of TNR and TPR, markedness, and odd
- In all studied cases where the axioms hold, the score has a perfect rank correlation (tau=1) with some ranking score, except the constant chance-accuracy of Cohen's kappa under balanced classes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a ranking score to induce the performance ordering instead of a commonly used score that fails the ranking tests | Two-class crisp classification · All performances | Axiom-test suitability | Helped |
| Use Balanced Accuracy for ranking when class priors are unconstrained | Two-class crisp classification · All performances | Axiom-test suitability | Hurt |
| Use Balanced Accuracy only when the class prior is fixed | Two-class crisp classification · Positive prior = 0.2 | Axiom-test suitability | Helped |
| Use Matthews Correlation Coefficient for ranking | Two-class crisp classification · All performances | Axiom-test suitability | Hurt |
| Use Matthews Correlation Coefficient only when the class prior is fixed | Two-class crisp classification · Positive prior = 0.2 | Axiom-test suitability | Hurt |
| Use Accuracy for ranking | Two-class crisp classification · All performances | Axiom-test suitability | Helped |
| Use ranking scores instead of the geometric mean of TNR and TPR | Two-class crisp classification · All performances | Axiom-test suitability | Helped |
| Use ranking scores instead of Error Rate | Two-class crisp classification · All performances | Kendall's τ: -1† to -0.469 | Helped |
| Use a ranking score to rank classifiers when priors vary | Two-class crisp classification · All performances | Ranking consistency | Helped |
| Use the ranking-score family to induce an ordering satisfying the three axioms | Performance-based ranking · Φ = conv | Axiom satisfaction | Helped |
Surprising findings
- Several widely used classifier comparison scores (MCC, geometric mean of TNR and TPR, markedness, odds ratio) cannot induce performance orderings satisfying the axioms even with fixed priors.
- ROC and PR users do not intuitively make the same ranking decisions, although both spaces show the same information at fixed priors.
Limitations
- Theory's practical scores are developed mainly for convex combination (Phi = conv) of achievable performances.
- Importance cannot be deduced from a score's formula, so it must be specified by the user for each application.
- Empirical Kendall's tau values for many scores were obtained by numerical optimization on a finite set of performances rather than analytically.
Experimental setup
Metrics: Kendall's tau rank correlation axiom satisfaction tests
Builds on: Fawcett ROC interpolation Kendall's tau Nguyen et al. ranking reliability framework
Closest papers by meaning
- On ranking via sorting by estimated expected utility (NeurIPS 2020 · similarity 0.86)
- Conditional independence and graphical models for rankings (NeurIPS 2026 · similarity 0.86)
- RankSHAP: Shapley Value Based Feature Attributions for Learning to Rank (ICLR 2025 · similarity 0.85)
- Aggregating Quantitative Relative Judgments: From Social Choice to Ranking Prediction (NeurIPS 2024 · similarity 0.84)
- An Analysis of Elo Rating Systems via Markov Chains (NeurIPS 2024 · similarity 0.84)
- Stability and Multigroup Fairness in Ranking with Uncertain Predictions (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.