On Learning Mixture Models for Permutations
On Learning Mixture Models for Permutations
复制标题
关于学习排列的混合模型
DOI：
10.1145/2688073.2688111
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Silvio Lattanzi
中科院分区：
文献类型：
--
作者：
Flavio Chierichetti;Anirban Dasgupta;Ravi Kumar;Silvio Lattanzi
在这篇文章中，我们考虑了学习排列的混合的问题，其中混合的每个分量都是由一个随机过程产生的。当通过不同的子群体对一组项目进行排序并且子群体中的用户的排名趋于彼此一致时，在实际设置中会出现学习排列混合。虽然有一些关于学习这种混合物的应用工作，但它们本质上大多是启发式的。我们研究了混合分量的排列是由经典的Mlowers过程产生的问题，在这个过程中，每个分量都与一个中心和一个标量参数相关联。我们证明了，即使中心是任意分离的，只要参数都是相同的和已知的，人们也可以用指数型多个样本学习混合；我们还证明了后两个假设是信息理论上不可避免的。然后，我们将重点放在多项式时间的可学习性上，并给出了两个简单算法在中心很好分离的情况下的性能的界。从概念上讲，我们的工作表明，虽然排列可能不像高斯排列那样具有良好的数学特性，但某些结构方面仍然可以用于分析相应的混合学习问题。
In this paper we consider the problem of learning a mixture of permutations, where each component of the mixture is generated by a stochastic process. Learning permutation mixtures arises in practical settings when a set of items is ranked by different sub-populations and the rankings of users in a sub-population tend to agree with each other. While there is some applied work on learning such mixtures, they have been mostly heuristic in nature. We study the problem where the permutations in a mixture component are generated by the classical Mallows process in which each component is associated with a center and a scalar parameter. We show that even when the centers are arbitrarily separated, with exponentially many samples one can learn the mixture, provided the parameters are all the same and known; we also show that the latter two assumptions are information-theoretically inevitable. We then focus on polynomial-time learnability and show bounds on the performance of two simple algorithms for the case when the centers are well separated. Conceptually, our work suggests that while permutations may not enjoy as nice mathematical properties as Gaussians, certain structural aspects can still be exploited towards analyzing the corresponding mixture learning problem.