Learning Mixtures of Random Utility Models with Features from Incomplete Preferences

Zhibing Zhao, Ao Liu, Lirong XiaIJCAI 2022 · DOI

TL;DR

This paper tackles the challenge of learning user preferences from incomplete data (like partial rankings) using sophisticated models that incorporate user and item features. They introduce theoretical guarantees for the identifiability and consistency of these models, paving the way for more reliable and interpretable preference learning systems.

What Problem Does This Paper Address?

Preference learning, the task of understanding what users like, is crucial for many applications like recommender systems and discrete choice analysis. The Plackett-Luce (PL) model is a popular choice due to its interpretability and tractability. However, real-world preference data is often incomplete (e.g., users only rank their top few choices, not all items) and can be better explained by models that consider features of users and items. While extensions of PL exist for features and for incomplete preferences separately, their combination, especially in mixture models (where multiple PL models are blended), has been under-theorized. This paper aims to fill this gap by providing theoretical foundations for learning these complex, feature-rich, and incomplete preference models.

Methods

The authors extend the Plackett-Luce model with features to handle top-l orders (partial rankings) and mixtures of such models. They introduce the k-PLx-TO model, which is a mixture of k Plackett-Luce models with features, where each agent can provide a top-l ranking.

Key methodological contributions include:

  • Identifiability Analysis: They provide necessary and sufficient conditions for the identifiability of PLx-TO (a single PL model with features and top-l orders) and its special case, the bilinear model. They also offer a sufficient condition for the identifiability of mixtures (k-PLx-TO), which is crucial for ensuring that learned parameters have meaningful interpretations.
  • MLE Consistency and Sample Complexity: They establish conditions under which the Maximum Likelihood Estimator (MLE) for PLx-TO is consistent and provide a bound on its Root Mean Squared Error (RMSE). This theoretical guarantee is essential for understanding how well the model can learn from data and how much data is needed.
  • Algorithm Proposal: For the general k-PLx-TO model, they propose an Expectation-Maximization (EM) algorithm to learn the model parameters.

Datasets

The paper uses:

  • Synthetic Data: Generated to test the performance of the MLE on PLx-TO and to demonstrate the tradeoffs between statistical and computational efficiency when learning from different top-l preferences.
  • Real-world Data: Used to showcase the prediction power of PLx-TO and its mixture variants. The specific real-world dataset is not detailed in the main paper but is mentioned as being used for experiments.

Key Insights and Ideas

  • Identifiability is Key for Trust: The paper strongly emphasizes that identifiability is not just a theoretical nicety but a fundamental requirement for ensuring that learned model parameters can be interpreted reliably and lead to trustworthy decisions. They illustrate this with an example where non-identifiability can lead to contradictory interpretations of consumer preferences.
  • Generalization is Challenging but Achievable: Combining features, mixtures, and incomplete preferences (k-PLx-TO) creates a highly general model. While full identifiability for mixtures is complex, the paper provides sufficient conditions that are practical and can lead to identifiable models.
  • Top-l Preferences Offer a Tradeoff: Learning from top-l preferences (partial rankings) offers a balance between statistical efficiency and computational cost. More complete rankings (larger l) generally lead to better accuracy but require more computation.
  • Feature Rank is Crucial: The identifiability of PLx-TO and its bilinear variant is directly linked to the rank of the normalized feature matrices. This highlights the importance of diverse and linearly independent features for distinguishing between different preference structures.

Key Results

  • Identifiability Conditions: The paper provides precise conditions for PLx-TO and PLy,z-TO to be identifiable, based on the full row rank of normalized feature matrices.
  • Mixture Identifiability: A sufficient condition is given for the identifiability of k-PLx-TO, and it's shown that 2-PLx-TO is identifiable (modulo label switching) under mild conditions.
  • MLE Consistency: Theoretical guarantees are provided for the consistency of the MLE for PLx-TO, meaning the estimated parameters converge to the true parameters as the amount of data increases.
  • RMSE Bound: A bound on the RMSE of the MLE is derived, offering insights into sample complexity and the rate of convergence.
  • Experimental Validation: Experiments on synthetic data confirm the consistency of MLE and demonstrate the MSE-runtime tradeoffs for different top-l settings. Real-world data experiments show the predictive power of the proposed models.

Limitations and Future Work

  • Mixture Identifiability: While a sufficient condition for k-PLx-TO identifiability is provided, a general necessary and sufficient condition for mixtures (especially for k ≥ 3) remains an open problem.
  • Generic Identifiability: The paper suggests that exploring generic identifiability for k-PLx-TO is a promising future direction.
  • Efficient Algorithms: Developing efficient algorithms for learning general k-PLx-TO models is also highlighted as future work.
  • Broader RUMs: The paper focuses primarily on Plackett-Luce models and defers results on more general Random Utility Models (RUMs) to an appendix. Extending the theoretical findings to broader RUM families is a natural next step.

Summary updated

BibTeX
@inproceedings{zhao2022learning,
  author = {Zhibing Zhao and Ao Liu and Lirong Xia},
  title = {{Learning Mixtures of Random Utility Models with Features from Incomplete Preferences}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/525},
}
Figure