Label Ranking Methods based on the Plackett-Luce Model

Weiwei Cheng, Krzysztof Dembczynski, Eyke HüllermeierICML 2010 · OpenReview

Introduction

While standard classification tasks require predicting a single label for a given input, label ranking demands predicting a full preference ordering of all possible labels (e.g., "User A prefers Label 3 > Label 1 > Label 2").

Historically, most approaches have solved this via "reduction"—breaking the ranking problem into many independent binary classification problems, such as pairwise comparisons. While easy to implement, this approach has a major theoretical flaw: minimizing error on individual pairs does not necessarily minimize the error of the final overall ranking. Furthermore, these reduction models often struggle with incomplete rankings (where the order of only a subset of labels is known), a common occurrence in real-world data like survey results or recommendation logs.

To address these limitations, this paper introduces two novel methods based on the Plackett-Luce (PL) statistical model, demonstrating superior performance particularly when training data is incomplete.

The Plackett-Luce Approach

The authors propose leveraging the Plackett-Luce (PL) model, a probabilistic framework frequently used in choice modeling. The PL model can be conceptualized as a "vase model": each label has an underlying "weight" or parameter ($v$). You draw the first label with a probability proportional to its weight, then draw the second from the remaining labels, and so on.

The paper introduces two distinct ways to apply this model to label ranking:

  1. IB-PL (Instance-Based): A "local" approach. For a new query, the algorithm finds the $K$ nearest neighbors in the training set and fits a PL model to their rankings using Maximum Likelihood Estimation (MLE) via a specialized Minorization-Maximization (MM) algorithm.
  2. Lin-PL (Generalized Linear): A "global" approach. This method assumes the logarithm of the PL parameters is a linear function of the input features. It utilizes Stochastic Gradient Descent to learn the weights that best explain the training rankings.

A significant advantage of the PL model over previously popular models (like the Mallows model) is that it allows for a closed-form expression of the probability of incomplete rankings. This mathematical elegance makes it computationally efficient and highly robust for messy, real-world datasets.

Key Insights

  • Handling Incomplete Data: The PL model’s most significant theoretical advantage is its treatment of missing data. The probability of a partial ranking (e.g., $y_1 > y_2$) is calculated exactly the same way as a full ranking, simply with fewer terms. This is a massive upgrade over the Mallows model, which requires complex and computationally expensive marginalization to handle missing labels.
  • Reliability as a Feature: Because these are probabilistic models, they output a confidence score alongside the ranking. The authors demonstrate that higher model confidence strongly correlates with higher accuracy. This allows systems to implement "accuracy-rejection" curves, declining to make a prediction if the confidence threshold is too low.
  • Theoretical Optimality: For the PL model, simply sorting the labels by their learned parameters ($v_i$) provides the Maximum A Posteriori (MAP) ranking, which is theoretically optimal for almost all common ranking loss functions.

Experimental Results

To evaluate the models, the authors adapted 16 datasets from the UCI and Statlog repositories, transforming them into ranking tasks. They simulated real-world missingness by randomly deleting labels from the training rankings at rates of 30% and 60%. Performance was measured using Kendall’s tau, a correlation metric where 1.0 is a perfect match and -1.0 is a total reversal.

Kendall's tau performance across datasets for complete and incomplete rankings.

The experimental evaluation revealed several key findings:

  • IB-PL vs. IB-Mal: While the Mallows-based model (IB-Mal) performs slightly better on complete data, IB-PL dominates as the data becomes more incomplete. The mathematical advantages of the PL model translate directly to better empirical performance on 30% and 60% missing label tasks.
  • Lin-PL vs. Lin-LL: The global linear PL model consistently outperformed state-of-the-art log-linear (Lin-LL) models across almost all datasets, winning 14 out of 16 trials in the complete ranking scenario.
  • Local vs. Global Robustness: Instance-based (local) methods generally performed better on complete data. However, they proved much more sensitive to missing information compared to the "sturdier" linear (global) models. As missingness increases, the performance of local models degrades much faster than their global counterparts.
Performance degradation of IB-PL vs. Lin-PL as missing label percentage increases.

Limitations and Future Work

While highly effective, the proposed methods have limitations. The MM algorithm used in the instance-based method is efficient, but finding neighbors and performing MLE at prediction time can still be computationally expensive for massive datasets. Conversely, the global model (Lin-PL) assumes a strict linear relationship between features and label preferences; it will struggle if the true preference boundary is highly non-linear.

For future work, the authors suggest exploring a hybrid "Local Linear" approach. By fitting a linear model only within the local neighborhood of a query, it may be possible to combine the flexible, non-linear capabilities of instance-based learning with the robust missing-data handling of linear modeling.

Summary updated

Abstract

This paper introduces two new methods for label ranking based on a probabilistic model of ranking data, called the Plackett-Luce model. The idea of the first method is to use the PL model to fit locally constant probability models in the context of instance-based learning. As opposed to this, the second method estimates a global model in which the PL parameters are represented as functions of the instance. Comparing our methods with previous approaches to label ranking, we find that they offer a number of advantages. Experimentally, we moreover show that they are highly competitive to start-of-the-art methods in terms of predictive accuracy, especially in the case of training data with incomplete ranking information.
BibTeX
@inproceedings{cheng2010label,
  author = {Weiwei Cheng and Krzysztof Dembczynski and Eyke Hüllermeier},
  title = {{Label Ranking Methods based on the Plackett-Luce Model}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=rk-7YiZOWB},
}
Figure