Efficient and Accurate Learning of Mixtures of Plackett-Luce Models

Duc Nguyen, Anderson Y. ZhangAAAI 2023 · DOI

TL;DR

This paper introduces a novel EM algorithm for learning mixtures of Plackett-Luce (PL) models, which are fundamental for ranking data. Their approach offers a provably accurate initialization and an efficient M-step that directly optimizes the true likelihood, outperforming existing methods in accuracy and speed, especially for datasets with many items.

What Problem Does This Paper Address?

Learning to rank is crucial for applications like recommendation systems and information retrieval. The Plackett-Luce (PL) model is a foundational tool for understanding user preferences and generating rankings. However, real-world scenarios often involve diverse user groups with different preference patterns, which a single PL model cannot capture. This necessitates using mixtures of PL models.

The challenge lies in efficiently and accurately learning these mixture models. Traditional approaches rely on the Expectation-Maximization (EM) algorithm, but they suffer from two main issues:

  1. Initialization: Random initialization can lead to poor starting points, requiring multiple restarts and increasing computational cost.
  2. M-step Difficulty: Maximizing the PL likelihood in the M-step is combinatorially complex. Existing methods often resort to optimizing surrogate likelihood functions, which can lead to estimates that deviate from the true maximum likelihood.

This paper aims to overcome these limitations by proposing a new EM algorithm that provides a reliable initialization and an efficient M-step for learning mixtures of PL models.

Methods

The proposed algorithm, termed Spectral EM (EM-LSR), consists of two main components:

  1. Spectral Initialization: This is a novel, provably accurate initialization procedure. It leverages spectral clustering on an embedded representation of the rankings.
  2. Rankings are converted into "pairwise vectors" indicating which item is preferred in each pair.
  3. Singular Value Decomposition (SVD) is used for dimensionality reduction.
  4. K-means clustering is applied to the reduced data to identify distinct user preference groups (components).
  5. For each cluster, pairwise preference probabilities are estimated, and a least-squares optimization (Algorithm 2) recovers the utility parameters for that component. This method is model-agnostic and doesn't require a spectral gap condition, unlike prior work.
  6. Iterative Refinement via EM (Weighted LSR): The M-step of the EM algorithm is addressed by generalizing the Luce Spectral Ranking (LSR) algorithm.
  7. The generalized LSR (Algorithm 4) efficiently maximizes the weighted log-likelihood function. This is achieved by constructing a Markov chain based on choice enumerations derived from rankings and their weights, and then recovering parameters from the stationary distribution.
  8. This approach directly optimizes the true log-likelihood, avoiding the inaccuracies of surrogate functions.
  9. The EM algorithm then iteratively uses the spectral initialization and the weighted LSR M-step to refine the estimates until convergence.

Datasets

The paper evaluates its method on:

  • Synthetic Datasets: Generated using a novel generative model (described in Theorem 1) that allows for controlled variation in the number of items, mixture components, and the "informativeness" of items.
  • Real Datasets:
    • APA (American Political Science Association)
    • Irish Elections (West, North, Meath)
    • SUSHI (a common benchmark for ranking models)
    • ML-10M movie ratings dataset (a larger-scale dataset)

The authors use standard train-test splits and Bayesian Information Criterion (BIC) for model selection (determining the number of components, K).

Key Insights and Ideas

  • Spectral Clustering for Initialization: Using spectral clustering on pairwise preference embeddings is a powerful way to group similar preference patterns, providing a strong initial estimate for mixture components. This is a key departure from random initialization.
  • Direct Likelihood Maximization: The generalized LSR algorithm allows for efficient maximization of the true weighted log-likelihood in the M-step, which is crucial for obtaining accurate maximum likelihood estimates, unlike methods using surrogate objectives.
  • Scalability to Large Item Sets: The proposed EM-LSR algorithm demonstrates competitive performance and scalability, particularly for datasets with a large number of items (n ≥ 100), where other methods struggle.
  • Provable Guarantees: The paper provides theoretical guarantees for the spectral initialization, showing finite sample error bounds, which is a novel contribution.

Key Results

  • Accuracy: EM-LSR consistently achieves competitive or superior accuracy (measured by test log-likelihood) compared to baseline methods (EMM, EM-GMM, EM-CML) across synthetic and real datasets. It is particularly effective on larger datasets.
  • Speed: While EMM (which also optimizes the true likelihood but uses a slower M-step) is accurate, EM-LSR is significantly faster, making it more practical for larger problems. EM-LSR is also competitive with EM-CML and EM-GMM in terms of speed, especially as the number of items increases.
  • Initialization Advantage: Spectral initialization provides better initial estimates than random initialization, leading to faster convergence and more accurate final results.
  • Scalability: The algorithm scales well to datasets with up to 100 items and beyond, outperforming baselines that become computationally prohibitive.

Limitations and Future Work

  • Convergence Basin: While the EM algorithm is guaranteed to converge to a stationary point, there's no guarantee it will reach the global optimum. Characterizing the "basin of attraction" where convergence to the global optimum is assured is left as future work.
  • Initialization Sensitivity: While spectral initialization is provably accurate, its performance might still depend on the signal-to-noise ratio of the data.
  • Future Directions:
    • Exploring other initialization methods like moment-based or tensor decomposition approaches.
  • Incorporating deep neural networks to enhance the representation power of the model for large-scale recommendation systems.
  • Extending the algorithm to handle partial rankings and ties.
  • Investigating Bayesian inference methods for PL mixtures.

Summary updated

BibTeX
@inproceedings{nguyen2023efficient,
  author = {Duc Nguyen and Anderson Y. Zhang},
  title = {{Efficient and Accurate Learning of Mixtures of Plackett-Luce Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i8.26114},
}
Figure