Transductive Conformal Inference for Ranking

• URL: http://arxiv.org/abs/2501.11384v1
• Date: Mon, 20 Jan 2025 10:24:33 GMT
• Title: Transductive Conformal Inference for Ranking
• Authors: Jean-Baptiste Fermanian, Pierre Humbert, Gilles Blanchard,
• Abstract summary: We introduce a method based on Conformal Prediction (CP) to quantify the uncertainty of full ranking algorithms. We focus on a specific scenario where $n + m$ items are to be ranked by some ''black box'' algorithm.
• Score: 8.050897403457995
• License:
• Abstract: We introduce a method based on Conformal Prediction (CP) to quantify the uncertainty of full ranking algorithms. We focus on a specific scenario where $n + m$ items are to be ranked by some ''black box'' algorithm. It is assumed that the relative (ground truth) ranking of n of them is known. The objective is then to quantify the error made by the algorithm on the ranks of the m new items among the total $(n + m)$. In such a setting, the true ranks of the n original items in the total $(n + m)$ depend on the (unknown) true ranks of the m new ones. Consequently, we have no direct access to a calibration set to apply a classical CP method. To address this challenge, we propose to construct distribution-free bounds of the unknown conformity scores using recent results on the distribution of conformal p-values. Using these scores upper bounds, we provide valid prediction sets for the rank of any item. We also control the false coverage proportion, a crucial quantity when dealing with multiple prediction sets. Finally, we empirically show on both synthetic and real data the efficiency of our CP method.

Related papers

• Fair Secretaries with Unfair Predictions [12.756552522270198]
  We show that an algorithm can have zero probability of accepting the best candidate, which we deem unfair, despite promising to accept a candidate whose expected value is at least $maxOmega (1), 1 - O(epsilon)$ times the optimal value, where $epsilon$ is the prediction error. Our algorithm and analysis are based on a new "pegging" idea that diverges from existing works and simplifies/unifies some of their results.
  arXiv  Detail & Related papers  (2024-11-15T00:23:59Z)
• Online Combinatorial Allocations and Auctions with Few Samples [9.675397292814122]
  This paper investigates the feasibility of achieving O(1)-competitive algorithms under the realistic constraint of having access to only a limited number of samples from the underlying bidder distributions. Our first main contribution shows that a mere single sample from each bidder distribution is sufficient to yield an O(1)-competitive algorithm for submodular/XOS valuations.
  arXiv  Detail & Related papers  (2024-09-17T11:43:55Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  We propose algorithms that utilize the variance of the reward distribution as well as the $B_K$, and show that they can achieve tighter regret upper bounds. We introduce two novel algorithms: Restarted Weighted$textOFUL+$ and Restarted $textSAVE+$. Notably, when the total variance $V_K$ is much smaller than $K$, our algorithms outperform previous state-of-the-art results on non-stationary linear bandits under different settings.
  arXiv  Detail & Related papers  (2024-03-15T23:36:55Z)
• PAC Prediction Sets Under Label Shift [52.30074177997787]
  Prediction sets capture uncertainty by predicting sets of labels rather than individual labels. We propose a novel algorithm for constructing prediction sets with PAC guarantees in the label shift setting. We evaluate our approach on five datasets.
  arXiv  Detail & Related papers  (2023-10-19T17:57:57Z)
• Found in the Middle: Permutation Self-Consistency Improves Listwise Ranking in Large Language Models [63.714662435555674]
  Large language models (LLMs) exhibit positional bias in how they use context. We propose permutation self-consistency, a form of self-consistency over ranking list outputs of black-box LLMs. Our approach improves scores from conventional inference by up to 7-18% for GPT-3.5 and 8-16% for LLaMA v2 (70B)
  arXiv  Detail & Related papers  (2023-10-11T17:59:02Z)
• Improved theoretical guarantee for rank aggregation via spectral method [1.0152838128195467]
  Given pairwise comparisons between multiple items, how to rank them so that the ranking matches the observations? This problem, known as rank aggregation, has found many applications in sports, recommendation systems, and other web applications. Here, each pairwise comparison is a corrupted copy of the true score difference.
  arXiv  Detail & Related papers  (2023-09-07T16:01:47Z)
• Sorting and Hypergraph Orientation under Uncertainty with Predictions [0.45880283710344055]
  We study learning-augmented algorithms for sorting and hypergraph orientation under uncertainty. Our algorithms provide improved performance guarantees for accurate predictions while maintaining worst-case guarantees that are best possible without predictions.
  arXiv  Detail & Related papers  (2023-05-16T07:52:08Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  Inverse reinforcement learning (IRL) aims to recover the reward function and the associated optimal policy. Many algorithms for IRL have an inherently nested structure. We develop a novel single-loop algorithm for IRL that does not compromise reward estimation accuracy.
  arXiv  Detail & Related papers  (2022-10-04T17:13:45Z)
• Lagrangian Inference for Ranking Problems [18.70913621061314]
  We consider the widely adopted Bradley-Terry-Luce (BTL) model, where each item is assigned a positive preference score that determines the Bernoulli distributions of pairwise comparisons' outcomes. Our proposed method aims to infer general ranking properties of the BTL model. We generalize our framework to multiple testing problems where we control the false discovery rate (FDR) and apply the method to infer the top-$K$ ranked items.
  arXiv  Detail & Related papers  (2021-10-01T01:16:25Z)
• Social Distancing is Good for Points too! [91.3755431537592]
  We show that FCNN can behave poorly when points are too close to each other. We then successfully modify the algorithm to avoid such cases. This modification is sufficient to prove useful upper-bounds, along with approximation guarantees for the algorithm.
  arXiv  Detail & Related papers  (2020-06-28T16:49:59Z)
• SetRank: A Setwise Bayesian Approach for Collaborative Ranking from Implicit Feedback [50.13745601531148]
  We propose a novel setwise Bayesian approach for collaborative ranking, namely SetRank, to accommodate the characteristics of implicit feedback in recommender system. Specifically, SetRank aims at maximizing the posterior probability of novel setwise preference comparisons. We also present the theoretical analysis of SetRank to show that the bound of excess risk can be proportional to $sqrtM/N$.
  arXiv  Detail & Related papers  (2020-02-23T06:40:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.