arXiv:2506.02257stat.MLcs.LG2025-06被引 5

无需假设即可实现稳定排序,解决真实数据中得分相近项的敏感问题。

Assumption-free stability for ranking problems

  • 提出新型排序算子,通过输出不确定性提升稳定性
  • 在无数据分布假设下保证排序稳定,不依赖候选总数
  • 适用于真实世界数据,尤其适合得分接近的项目排序

本文研究有限候选集上的排序问题,如从大量候选中选出前-k项或对全部项目进行完整排序。现有方法常因数据噪声导致排序高度敏感,尤其当项目得分接近时。多数理论依赖分离条件,但真实数据中此类条件难以满足。为此,本文提出一种无需假设的算法稳定性框架,设计两种新排序算子:用于前-k选择的「膨胀型top-k」和用于全排序的「膨胀型全排序」。二者通过允许输出中包含不确定性来实现稳定,且在无数据分布假设、不依赖候选总数的条件下提供理论保障。实验证明,所提方法在保持输出信息量的同时显著提升稳定性。

原文摘要 · Abstract (English)

In this work, we consider ranking problems among a finite set of candidates: for instance, selecting the top-$k$ items among a larger list of candidates or obtaining the full ranking of all items in the set. These problems are often unstable, in the sense that estimating a ranking from noisy data can exhibit high sensitivity to small perturbations. Concretely, if we use data to provide a score for each item (say, by aggregating preference data over a sample of users), then for two items with similar scores, small fluctuations in the data can alter the relative ranking of those items. Many existing theoretical results for ranking problems assume a separation condition to avoid this challenge, but real-world data often contains items whose scores are approximately tied, limiting the applicability of existing theory. To address this gap, we develop a new algorithmic stability framework for ranking problems, and propose two novel ranking operators for achieving stable ranking: the \emph{inflated top-$k$} for the top-$k$ selection problem and the \emph{inflated full ranking} for ranking the full list. To enable stability, each method allows for expressing some uncertainty in the output. For both of these two problems, our proposed methods provide guaranteed stability, with no assumptions on data distributions and no dependence on the total number of candidates to be ranked. Experiments on real-world data confirm that the proposed methods offer stability without compromising the informativeness of the output.

排序稳定无假设顶k选择不确定性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。