Learning Mixtures of Random Utility Models

Zhibing Zhao, Tristan Villamil, Lirong XiaAAAI 2018 · DOI

Introduction

Rank aggregation—the task of synthesizing multiple individual rankings into a single consensus—is a cornerstone of modern data science, with applications spanning from search engine optimization to social choice theory. While the Plackett-Luce (PL) model is frequently employed due to its computational simplicity, it often fails to capture the nuances of complex human behavior. General Random Utility Models (RUMs), such as those based on Gaussian distributions, offer superior flexibility but present significant challenges: they lack closed-form likelihood functions and raise difficult questions regarding identifiability.

This paper provides the first comprehensive theoretical and algorithmic framework for learning mixtures of general RUMs ($k$-RUMs). By establishing the conditions under which these models can be uniquely identified from data and introducing a novel "sandwich" algorithm, the authors bridge the gap between theoretical expressiveness and practical learnability.

Theoretical Foundations: The Identifiability Challenge

A primary hurdle in learning $k$-RUMs is identifiability: determining whether model parameters can be uniquely recovered from observed rankings. The authors identify a "symmetry trap"—the inherent symmetry in utility distributions (like the Gaussian bell curve) makes distinguishing between mixture components difficult.

The research establishes that learnability depends heavily on the number of alternatives ($m$) relative to the number of mixture components ($k$). Specifically:

  • For symmetric utility distributions, the model is non-identifiable if $m \le 2k - 1$.
  • The model becomes "generically identifiable" when $m \ge \max\{4k - 2, 6\}$.

This insight reveals that increasing the volume of data is insufficient if the number of alternatives is too low; structural complexity requires a sufficiently large choice set.

The Sandwich Algorithm

To overcome the lack of a closed-form likelihood function, the authors propose three algorithmic approaches:

  1. Generalized Method of Moments (GMM): Matches observed pairwise comparison frequencies with theoretical predictions. It is computationally efficient but may lack statistical precision.
  2. E-GMM: An Expectation-Maximization (EM) variant. The E-step estimates component membership probabilities, while the M-step updates parameters using a GMM-based approach.
  3. The Sandwich Algorithm (GMM-E-GMM): The paper's flagship contribution. It utilizes the fast GMM to provide a robust initial estimate, which is then refined through E-GMM iterations. This "sandwiching" strategy mitigates the sensitivity of EM algorithms to initial conditions.

Experimental Results

The proposed framework was evaluated using both synthetic datasets and 209 real-world linear order datasets from the Preflib repository.

Synthetic Benchmarks

In controlled environments ($k=2, m=6$), the Sandwich algorithm demonstrated a clear advantage over standalone GMM. While the GMM is faster, the Sandwich algorithm achieves significantly lower Mean Weighted Root Square Error (MWRSE) and tighter confidence intervals, as shown in the performance comparison below.

Performance comparison of MWRSE and Runtime between GMM and the Sandwich algorithm on synthetic data ($k=2, m=6$).

Real-World Performance

On Preflib data, Gaussian $k$-RUMs consistently outperformed standard benchmarks, including single RUMs and mixtures of Plackett-Luce models. Using information criteria such as AIC, AICc, and BIC, the $k$-RUM model (with optimized $k$) surpassed the standard Plackett-Luce model in approximately 90% of the 209 datasets tested.

Conclusion and Future Directions

This work establishes a rigorous foundation for using complex mixtures of RUMs in rank aggregation. By solving the identifiability problem and providing an efficient learning algorithm, the authors enable more accurate modeling of heterogeneous preferences. Future research may focus on tightening the identifiability bounds and exploring "tensor-decomposition" techniques to further enhance computational scalability for massive datasets.

Summary updated

BibTeX
@inproceedings{zhao2018learning,
  author = {Zhibing Zhao and Tristan Villamil and Lirong Xia},
  title = {{Learning Mixtures of Random Utility Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11727},
}
Figure