论文标题
学习排列的混合物：成对比较组和矩的组合方法
Learning Mixtures of Permutations: Groups of Pairwise Comparisons and Combinatorial Method of Moments
论文作者
论文摘要
在等级聚集等应用中，当种群表现出异质性时，经常使用用于排列的混合模型。在这项工作中，我们研究了广泛使用的绿木棍混合模型。在高维设置中，我们提出了一种多项式时算法，该算法在$ n $元素上学习了杂项置换式插入的混合物，其最佳样品复杂性与$ \ log n $成比例，从而改善了以前的结果，可以根据$ n $进行多项量表。在高噪声方面，我们表征了样品复杂性对噪声参数的最佳依赖性。这两个目标都是通过首先使用成对比较组的无噪声查询模型下的分解置换来实现的，这些比较可以看作是混合分布的矩，然后通过模拟无噪声甲骨文将这些结果扩展到嘈杂的木棍模型。
In applications such as rank aggregation, mixture models for permutations are frequently used when the population exhibits heterogeneity. In this work, we study the widely used Mallows mixture model. In the high-dimensional setting, we propose a polynomial-time algorithm that learns a Mallows mixture of permutations on $n$ elements with the optimal sample complexity that is proportional to $\log n$, improving upon previous results that scale polynomially with $n$. In the high-noise regime, we characterize the optimal dependency of the sample complexity on the noise parameter. Both objectives are accomplished by first studying demixing permutations under a noiseless query model using groups of pairwise comparisons, which can be viewed as moments of the mixing distribution, and then extending these results to the noisy Mallows model by simulating the noiseless oracle.
