论文标题
对一组对象进行排名：基于图形的最小二乘方法
Ranking a set of objects: a graph based least-square approach
论文作者
论文摘要
我们考虑了从一组平等工人提供的一组嘈杂的成对比较开始的排名$ n $对象的问题。我们假设对象具有内在品质，并且对象优先于另一个对象的概率仅取决于两个竞争者的素质之间的差异。我们提出了一类非自适应排名算法，这些算法依赖于最小二乘优化标准来估计质量。此类算法在渐近上是最佳的（即它们需要$ o（\ frac {n} {ε^2} \ log \ frac {n}δ）$比较为$（ε，δ）$ - PAC）。数值结果表明，我们的方案在许多非症状场景中也非常有效，表现出类似于最大样本算法的性能。此外，我们展示了如何将它们扩展到自适应方案并在现实世界数据集上进行测试。
We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We assume that objects are endowed with intrinsic qualities and that the probability with which an object is preferred to another depends only on the difference between the qualities of the two competitors. We propose a class of non-adaptive ranking algorithms that rely on a least-squares optimization criterion for the estimation of qualities. Such algorithms are shown to be asymptotically optimal (i.e., they require $O(\frac{N}{ε^2}\log \frac{N}δ)$ comparisons to be $(ε, δ)$-PAC). Numerical results show that our schemes are very efficient also in many non-asymptotic scenarios exhibiting a performance similar to the maximum-likelihood algorithm. Moreover, we show how they can be extended to adaptive schemes and test them on real-world datasets.
