论文标题
汇总不完整和嘈杂的排名
Aggregating Incomplete and Noisy Rankings
论文作者
论文摘要
我们考虑从很大程度上不完整和嘈杂的排名中学习一组替代方案的真实排序的问题。我们介绍了排名分布的经典曲棍球模型和嘈杂成对比较的广泛研究模型的自然概括。我们的选择性木棍模型基于基础曲棍球分布，在任何给定的替代方案上输出嘈杂的排名。假设每对替代方案频繁出现频繁出现的子集序列，我们在学习基础完整排名的样本复杂性上获得了强大的渐近性上限和下限，以及从选择性蜂鸣器排名中的Top-K替代方案（身份和）排名（身份和）排名。此外，基于（Braverman and Mossel，2009）的工作，我们展示了如何有效地计算出选择性曲棍球排名的最大似然的完整排名。
We consider the problem of learning the true ordering of a set of alternatives from largely incomplete and noisy rankings. We introduce a natural generalization of both the classical Mallows model of ranking distributions and the extensively studied model of noisy pairwise comparisons. Our selective Mallows model outputs a noisy ranking on any given subset of alternatives, based on an underlying Mallows distribution. Assuming a sequence of subsets where each pair of alternatives appears frequently enough, we obtain strong asymptotically tight upper and lower bounds on the sample complexity of learning the underlying complete ranking and the (identities and the) ranking of the top-k alternatives from selective Mallows rankings. Moreover, building on the work of (Braverman and Mossel, 2009), we show how to efficiently compute the maximum likelihood complete ranking from selective Mallows rankings.
