Worst-case versus average-case design for estimation from partial pairwise comparisons
Worst-case versus average-case design for estimation from partial pairwise comparisons
复制标题
DOI：
10.1214/19-aos1838
复制
发表时间：
2020-04
影响因子：
4.5
通讯作者：
A. Pananjady;Cheng Mao;Vidya Muthukumar;M. Wainwright;T. Courtade
中科院分区：
文献类型：
--
作者：
A. Pananjady;Cheng Mao;Vidya Muthukumar;M. Wainwright;T. Courtade
成对比较数据出现在许多领域，包括锦标赛排名，网络搜索和偏好诱导。在强随机传递性（SST）假设下，研究了固定子集的项目对的噪声比较问题。我们还考虑了SST模型的噪声排序子类。我们表明，当分配的项目的拓扑结构是任意的，这些permutationbased模型，不像他们的参数同行，不承认一致的估计，在实践中使用的比较拓扑结构。然后，我们证明了一致的估计是可能的，当分配的项目的拓扑结构是随机的，从而建立了最坏情况和平均情况的设计之间的二分法。我们提出了两个计算效率的估计在平均情况下设置和分析其风险，表明它只通过拓扑的度序列依赖于比较拓扑。我们还提供了明确的类图，这些估计达到的速度是最佳的。我们的结果得到了多个比较拓扑模拟的证实。
Pairwise comparison data arises in many domains, including tournament rankings, web search, and preference elicitation. Given noisy comparisons of a fixed subset of pairs of items, we study the problem of estimating the underlying comparison probabilities under the assumption of strong stochastic transitivity (SST). We also consider the noisy sorting subclass of the SST model. We show that when the assignment of items to the topology is arbitrary, these permutationbased models, unlike their parametric counterparts, do not admit consistent estimation for most comparison topologies used in practice. We then demonstrate that consistent estimation is possible when the assignment of items to the topology is randomized, thus establishing a dichotomy between worst-case and average-case designs. We propose two computationally efficient estimators in the average-case setting and analyze their risk, showing that it depends on the comparison topology only through the degree sequence of the topology. We also provide explicit classes of graphs for which the rates achieved by these estimators are optimal. Our results are corroborated by simulations on multiple comparison topologies.