arXiv:2602.24263stat.MLcs.LG2026-02被引 1

提出新算法Smooth-rank,解决连续分布下的主动二元排序问题。

Active Bipartite Ranking with Smooth Posterior Distributions

  • 针对连续条件分布设计新型主动排序算法
  • 理论证明算法在指定置信度下有效,采样时间有上下界
  • 适合需要高效标注的推荐系统与信息检索场景

本文将广泛研究的被动二元排序问题扩展到更一般的主动设置,突破以往仅限于离散分布的局限。以往方法假设条件分布为分段常数,而本文框架允许处理满足Hölder光滑性约束的连续分布。我们指出,基于均匀离散化的朴素方法通常失效;为此提出新算法smooth-rank,目标是最小化估计排序规则的ROC曲线与最优曲线之间的上确界距离。对于任意固定置信水平ε>0和概率δ∈(0,1),smooth-rank被证明是PAC(ε,δ)的。进一步,给出了smooth-rank期望采样时间的问题相关上界,并建立了任意PAC(ε,δ)算法的期望采样时间问题相关下界。数值实验表明,所提算法性能优于现有方法,具有良好的实证效果。

原文摘要 · Abstract (English)

In this article, bipartite ranking, a statistical learning problem involved in many applications and widely studied in the passive context, is approached in a much more general \textit{active setting} than the discrete one previously considered in the literature. While the latter assumes that the conditional distribution is piece wise constant, the framework we develop permits in contrast to deal with continuous conditional distributions, provided that they fulfill a Hölder smoothness constraint. We first show that a naive approach based on discretisation at a uniform level, fixed \textit{a priori} and consisting in applying next the active strategy designed for the discrete setting generally fails. Instead, we propose a novel algorithm, referred to as smooth-rank and designed for the continuous setting, which aims to minimise the distance between the ROC curve of the estimated ranking rule and the optimal one w.r.t. the $\sup$ norm. We show that, for a fixed confidence level $ε>0$ and probability $δ\in (0,1)$, smooth-rank is PAC$(ε,δ)$. In addition, we provide a problem dependent upper bound on the expected sampling time of smooth-rank and establish a problem dependent lower bound on the expected sampling time of any PAC$(ε,δ)$ algorithm. Beyond the theoretical analysis carried out, numerical results are presented, providing solid empirical evidence of the performance of the algorithm proposed, which compares favorably with alternative approaches.

主动学习排序学习统计推断

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