Active Ranking without Strong Stochastic Transitivity
Active Ranking without Strong Stochastic Transitivity
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Hao Lou;Tao Jin;Yue Wu;Pan Xu;Quanquan Gu;Farzad Farnoud
中科院分区：
文献类型：
--
作者：
Hao Lou;Tao Jin;Yue Wu;Pan Xu;Quanquan Gu;Farzad Farnoud
从噪声比较中进行排名在机器学习中具有很大的实际意义。在本文中，我们考虑的问题，恢复的确切的完整的排名下的排名模型，不承担强随机传递属性的项目列表。我们提出了一个δ -正确的算法，探针排名，积极学习排名从嘈杂的成对比较。我们证明了一个样本的复杂性上界的探测排名，这只取决于在真实的排名相邻的项目之间的偏好概率。这改进了现有的样本复杂度结果，这些结果取决于所有项目对的偏好概率。因此，Probe-Rank在不满足强随机传递性的大量实例上优于现有方法。在各种设置进行彻底的数值实验，证明探针排名是显着更有效的样本比国家的最先进的主动排名方法。
Ranking from noisy comparisons is of great practical interest in machine learning. In this paper, we consider the problem of recovering the exact full ranking for a list of items under ranking models that do not assume the Strong Stochastic Transitivity property. We propose a δ -correct algorithm, Probe-Rank, that actively learns the ranking from noisy pairwise comparisons. We prove a sample complexity upper bound for Probe-Rank, which only depends on the preference probabilities between items that are adjacent in the true ranking. This improves upon existing sample complexity results that depend on the preference probabilities for all pairs of items. Probe-Rank thus outperforms existing methods over a large collection of instances that do not satisfy Strong Stochastic Transitivity. Thorough numerical experiments in various settings are conducted, demonstrating that Probe-Rank is significantly more sample-efficient than the state-of-the-art active ranking method.