Research map / Learning theory and algorithms / Prediction and decision losses
Transductive Conformal Inference for Full 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.
Proposes a transductive conformal prediction method (TCPR) that builds valid rank prediction sets for full ranking algorithms when only the relative ranks of a calibration subset are known, using distribution-free bounds on unknown calibration ranks and controlling the false coverage proportion.
Problem
Quantifying the uncertainty of full ranking algorithms: the true ranks of calibration items depend on unknown ranks of new test items, so classical split conformal calibration is not directly applicable.
Approach
Bound the unknown calibration ranks with high-probability envelopes derived from the distribution of conformal p-values (linear and Monte-Carlo quantile envelopes), build proxy conformity scores from these bounds, and obtain valid rank prediction sets with FCP control.
Key results
- On Yummly-10k, FCP stays below the 0.1 threshold for all three rankers (about 0.069 to 0.076 with RA score), with oracle ratios near 1.06 to 1.10.
- Theoretical envelope reduces interval length from m to O(m/sqrt(tau_{n,m})), a reduction by a factor of about min(sqrt(n), sqrt(m)).
- On synthetic data with small n (n=100), TCPR is conservative with FCP near 0, versus about 0.07 for the oracle.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the quantile envelope instead of the linear envelope (ablation) | TCPR on RankNet · Synthetic data, m=500 | relative length | Helped |
| increase calibration size from n=100 to n=2500 | TCPR · Synthetic data, m=500 | FCP: 0.1 | Mixed |
| use VA rather than RA conformity scores (ablation) | TCPR on RankNet · Synthetic data | relative length | No clear effect |
| use VA rather than RA conformity scores (ablation) | TCPR · Synthetic Beta-distributed data, n=m=500 | adaptivity of prediction-set width: 500 = 0.5 · (n+m) | Helped |
| use a more accurate ranking model | TCPR on Anime recommendation LTR · Anime recommendation LTR data set | prediction-set size | Helped |
Surprising findings
- The method is conservative for small calibration size n, with FCP near 0 when n=100 compared with about 0.07 for the oracle.
Limitations
- Only full ranking is covered; partial ranking and top-k algorithms are not addressed.
- Dependence on the choice of envelope; the envelope is not necessarily tight, and the theoretical constant is loose.
- Conservativeness for small calibration sizes.
Experimental setup
Datasets: Yummly Food-10k Anime recommendation LTR dataset synthetic Gaussian/logistic data
Benchmarks: Yummly-10k Anime recommendation LTR synthetic data
Metrics: false coverage proportion relative length oracle ratio rank error
Baselines: Oracle conformal method RankNet LambdaMART RankSVM
Builds on: split conformal prediction conformal p-values distribution results Dvoretzky-Kiefer-Wolfowitz inequality
Closest papers by meaning
- Conformal Prediction for Deep Classifier via Label Ranking (ICML 2024 · similarity 0.85)
- Online conformal prediction with decaying step sizes (ICML 2024 · similarity 0.85)
- An Information Theoretic Perspective on Conformal Prediction (NeurIPS 2024 · similarity 0.85)
- Optimal transport-based conformal prediction (ICML 2025 · similarity 0.85)
- Leave-One-Out Stable Conformal Prediction (ICLR 2025 · similarity 0.85)
- Robust Conformal Prediction Using Privileged Information (NeurIPS 2024 · similarity 0.85)
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.