Learning Plackett-Luce Mixtures from Partial Preferences

We propose an EM-based framework for learning Plackett- Luce model and its mixtures from partial orders. The core of our framework is the efficient sampling of linear extensions of partial orders under Plackett-Luce model. We propose two Markov Chain Monte Carlo (MCMC) samplers: Gibbs sampler and the generalized repeated insertion method tuned by MCMC (GRIM-MCMC), and prove the efficiency of GRIM- MCMC for a large class of preferences. Experiments on synthetic data show that the algorithm with Gibbs sampler outperforms that with GRIM-MCMC. Experiments on real-world data show that the likelihood of test dataset increases when (i) partial orders provide more information; or (ii) the number of components in mixtures of Plackett- Luce model increases.

Authors

• Ao Liu Sichuan University
• Zhibing Zhao
• Chao Liao
• Pinyan Lu
• Lirong Xia Rensselaer Polytechnic Institute

Keywords

No keywords are indexed for this paper.