Generalized method of moments algorithm for learning mixtures of Plackett-Luce models.

摘要

It is often the primary interest of certain voting systems to be able to generate an aggregate ranking over a set of candidates or alternatives from the preferences of individual agents or voters. The Plackett-Luce model is one of the most studied models for statistically describing discrete choice ordinal preferences and summarizing rank data in the machine learning subarea of rank aggregation which has also been widely researched from the approach of problems in computational social choice. Much work has been done by the machine learning community in developing algorithms to efficiently estimate Plackett-Luce model parameters with wide-ranging real-world applications of rank data in e-commerce and political science, such as meta-search engines, consumer products rankings, and presidential elections. In machine learning tasks, a mixture of models can sometimes better fit the data more closely than a single model alone, and so naturally, mixtures of Plackett-Luce models can also confer the same benefits for rank data.;A major obstacle in learning the parameters of mixture models is the identifiability of the models which is necessary in order to be able to make correct, meaningful inferences from the learned parameters. Without identifiability, it becomes impossible even to estimate the parameters in certain cases. Using breakthrough results on the identifiability of mixtures of Plackett-Luce, we propose an efficient generalized method of moments (GMM) algorithm to learn mixtures of Plackett-Luce models and compare it to an existing expectation maximization (EM) algorithm. We outline the overall approach of GMM and the selection of the moment conditions used by our algorithm in estimating the ground-truth parameters. Next, we describe the design and implementation details of our GMM algorithm and present both theory and experiments that show it to be significantly faster than the EM algorithm while achieving competitive statistical efficiency. Finally, we discuss the implications of the identifiability results and our algorithm on future work in extending both for learning mixtures of Plackett-Luce models from big rank data.