Abstract
Motivated by generating personalized recommendations using ordinal (or preference) data, we study the question of learning a mixture of MultiNomial Logit (MNL) model, a parameterized class of distributions over permutations, from partial ordinal or preference data (e.g. pair-wise comparisons). Despite its long standing importance across disciplines including social choice, operations research and revenue management, little is known about this question. In case of single MNL models (no mixture), computationally and statistically tractable learning from pair-wise comparisons is feasible. However, even learning mixture with two MNL components is infeasible in general. Given this state of affairs, we seek conditions under which it is feasible to learn the mixture model in both computationally and statistically efficient manner. We present a sufficient condition as well as an efficient algorithm for learning mixed MNL models from partial preferences/comparisons data. In particular, a mixture of $r$ MNL components over $n$ objects can be learnt using samples whose size scales polynomially in $n$ and $r$ (concretely, $r^{3.5}n^3(log n)^4$, with $r\ll n^{2/7}$ when the model parameters are sufficiently incoherent). The algorithm has two phases: first, learn the pair-wise marginals for each component using tensor decomposition; second, learn the model parameters for each component using Rank Centrality introduced by Negahban et al. In the process of proving these results, we obtain a generalization of existing analysis for tensor decomposition to a more realistic regime where only partial information about each sample is available.
Introduction
Modern recommendation systems are increasingly moving away from explicit scoring (e.g., 1-5 star ratings) toward ordinal data, which captures user behavior through clicks, rankings, or pairwise comparisons. The Multinomial Logit (MNL) model serves as a foundational framework for representing these preferences. In a standard MNL model, each item is assigned a latent weight, and the probability of a user selecting an item is proportional to that weight.
However, real-world populations are rarely homogeneous. A single MNL model fails to capture the diversity of preferences across different user segments. The Mixed MNL model addresses this by assuming the population is composed of multiple latent groups, each governed by its own preference weights. While more realistic, learning these mixtures from partial data is notoriously difficult. This paper identifies the conditions under which learning these mixtures becomes both computationally and statistically tractable.
The Challenge of Latent Mixtures
The primary difficulty in learning mixed MNL models lies in the ambiguity of observed data. When users only provide partial rankings or pairwise comparisons, multiple distinct latent mixtures can produce identical observed statistics. This identifiability problem makes it mathematically impossible to distinguish between different population profiles without specific structural assumptions.
As shown in Figure 1, different "types" within a mixture model (latent) lead to specific observed probabilities for partial rankings. The goal of this research is to reverse this process: disentangling the observed aggregate probabilities to recover the underlying latent preference profiles.
Methodology: A Two-Phase Approach
The authors propose a novel algorithm that combines spectral methods with ranking theory to solve the mixture recovery problem in two distinct phases:
Phase 1: Spectral and Tensor Decomposition
The first phase focuses on estimating the second and third "moments" of the observed pairwise comparisons. Because users typically only compare a small subset of items, the data is inherently sparse. The authors generalized existing tensor decomposition techniques to handle this "missing" information. This phase successfully disentangles the mixture, identifying the pairwise marginals—the probability that item $i$ is preferred over item $j$—for each of the $r$ latent components.
Phase 2: Rank Centrality
Once the components are separated, the problem is reduced to learning $r$ individual MNL models. The algorithm employs Rank Centrality, which treats item preferences as transitions in a Markov chain. The stationary distribution of this chain reveals the latent weights ($w$) for the items within that specific mixture component. This spectral approach avoids the local optima issues common in traditional Expectation-Maximization (EM) heuristics.
Key Insights and Theoretical Guarantees
The feasibility of this approach relies on several critical conditions:
- Incoherence Requirement: To distinguish between components, they must be sufficiently distinct in the parameter space. This is quantified by an "incoherence" parameter ($\mu$). If preference profiles are too similar, they cannot be reliably separated.
- Graph Connectivity: The "comparison graph" (representing which items were compared by users) must be a spectral expander. This ensures that the items are sufficiently interconnected to allow for a global ranking recovery.
- Sample Efficiency: Surprisingly, the global mixture can be recovered even if individual users only provide a finite number of random pairwise comparisons, provided the total number of users is sufficiently large.
Results and Complexity
The paper provides the first theoretical guarantees for learning mixed MNL models with polynomial complexity. Specifically, a mixture of $r$ components over $n$ objects can be learned with a sample size scaling as $O(r^{3.5} n^3 (\log n)^4)$. The algorithm is guaranteed to converge when the number of components $r$ is significantly smaller than the number of items ($r \ll n^{2/7}$), assuming sufficient incoherence.
Conclusion and Future Work
This work establishes a rigorous framework for learning complex preference models from sparse, ordinal data. While the $n^3$ scaling is a significant theoretical milestone, future research is needed to reduce this complexity for massive datasets with millions of items. Additionally, exploring how these models perform when user preferences are highly overlapping or evolve dynamically over time remains an open and important challenge for the field of personalized recommendations.
Summary updated