Mixtures of Plackett-Luce Models with Three-way Structured Partial Rankings

Abstract With the dramatic growth of available alternatives these days, it becomes necessary and important to collect rank data to predict the preferences of users with rank aggregation. One of the traditional rank aggregation is to utilize full rankings, and its solid statistics background makes it easy to balance between effectiveness and efficiency, such as Plackett-Luce models. However, from time to time it is usually impossible to have full rankings, which leads to partial rankings. As for the rank aggregation for partial rankings, mixtures of Plackett-Luce models can be introduced and analysed in this paper. Specifically, by introducing three-way decisions into structured partial rankings to have three-way structured partial rankings, including top-l, last-k, l-way, choice-l and last-choice-k, it is necessary and important to study mixtures of Plackett-Luce models with three-way structured partial rankings statistically effectively and experimentally efficiently, which can handle the uncertainty well. In addition, the (non-) identifiability of the mixtures of different three-way structured partial rankings has been proved, which makes it possible to process the subsequent parameter estimation. Then technically, the Generalized Method-of-Moments algorithm GMM-TW for mixtures of Plackett-Luce model is proposed to learn three-way structured partial rankings effectively. Moreover, due to uncertainty in real world, the GMM-P and the collaborative filtering based GMM algorithm GMM-CF are proposed to increase the robustness and reduce errors caused by the perturbations of rank data with three-way structure. Furthermore, the experiments both on synthetic datasets and the sushi dataset can demonstrate the effectiveness and efficiency of our proposed algorithms on different structured partial rankings.