Active ranking from pairwise comparisons and when parametric assumptions do not help
Active ranking from pairwise comparisons and when parametric assumptions do not help
复制标题
DOI：
10.1214/18-aos1772
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Reinhard Heckel;Nihar B. Shah;K. Ramchandran;M. Wainwright
中科院分区：
文献类型：
--
作者：
Reinhard Heckel;Nihar B. Shah;K. Ramchandran;M. Wainwright
我们考虑基于嘈杂的成对比较对一组 n 个项目进行顺序或主动排名。根据给定项目击败随机选择的项目的概率对项目进行排名，排名是指根据项目的分数将项目划分为预先指定大小的集合。作为特殊情况，这种排名概念包括前 k 个项目的识别以及项目的总排序。我们首先分析顺序排名算法，该算法计算获胜的比较次数，并使用这些计数来决定是否停止或比较另一对项目，这些项目是根据截至该点收集的数据指定的置信区间选择的。我们证明该算法使用多次对数因子最佳的比较成功地恢复了排名。与过去基于参数模型（例如 Thurstone 或 Bradley-Terry-Luce 模型）的成对排序的大量工作不同，这种保证不需要底层成对概率矩阵的任何结构属性。施加这些参数假设是否能够改进排名算法一直是一个长期存在的悬而未决的问题。对于随机比较模型，其中成对概率远离零，我们的第二个贡献是通过证明参数模型的下界来解决这个问题。这表明，也许令人惊讶的是，这些流行的参数建模选择最多为随机比较提供对数增益。
We consider sequential or active ranking of a set of n items based on noisy pairwise comparisons. Items are ranked according to the probability that a given item beats a randomly chosen item, and ranking refers to partitioning the items into sets of pre-specified sizes according to their scores. This notion of ranking includes as special cases the identification of the top-k items and the total ordering of the items. We first analyze a sequential ranking algorithm that counts the number of comparisons won, and uses these counts to decide whether to stop, or to compare another pair of items, chosen based on confidence intervals specified by the data collected up to that point. We prove that this algorithm succeeds in recovering the ranking using a number of comparisons that is optimal up to logarithmic factors. This guarantee does not require any structural properties of the underlying pairwise probability matrix, unlike a significant body of past work on pairwise ranking based on parametric models such as the Thurstone or Bradley-Terry-Luce models. It has been a long-standing open question as to whether or not imposing these parametric assumptions allows for improved ranking algorithms. For stochastic comparison models, in which the pairwise probabilities are bounded away from zero, our second contribution is to resolve this issue by proving a lower bound for parametric models. This shows, perhaps surprisingly, that these popular parametric modeling choices offer at most logarithmic gains for stochastic comparisons.