Learning Mixtures of Ranking Models *
This work concerns learning probabilistic models for ranking data in a heterogeneous population. The specific problem we study is learning the parameters of a Mallows Mixture Model. Despite being widely studied, current heuristics for this problem do not have theoretical guarantees and can get stuck in bad local optima. We present the first polynomial time algorithm which provably learns the parameters of a mixture of two Mallows models. A key component of our algorithm is a novel use of tensor decomposition techniques to learn the top-k prefix in both the rankings. Before this work, even the question of identifiability in the case of a mixture of two Mallows models was unresolved.
This paper considers the problem of the estimation of a mixture of two Mallows models. Though this problem has already attracted significant attention in the literature, the present paper is the first to introduce a polynomial time algorithm that provably solve it. It shows in particular the identifiability of the model, which was not known previously. The algorithm relies on two main ingredients:•	Explicit combinatorial formulas for the probability of the set of the k items ranked first under the mixture, for k = 1, 2, 3.•	The tensor decomposition of the matrix of these probabilities in terms of the representative vectors of the two Mallows models of the mixture.The statement of the algorithm is rather technical but it is well segmented into subroutines. Broadly speaking, the algorithm first randomly partition the set of items to obtain the mixture parameters as well as the diffusion parameters and the first elements of the central rankings of the two Mallows models, via a tensor decomposition. Then it completes the central permutations via a fine analysis of the different possible cases. The algorithm is proved to find the exact parameters of the mixture with high probability. At last, numerical experiments on synthetic data show that the proposed algorithm largely outperforms a classic EM based algorithm of the literature.This paper introduces explicit calculations on the Mallows model that, up to our knowledge, were never carried out before, highlighting a particular tensor-based structure. They are then exploited with a fine technical analysis in the design of a specific, novel algorithm. Finally the technical complexity of the approach is rewarded by convincing numerical experiments.