Recommender systems frequently face a fundamental trade-off: assume all users perceive items identically (which is often too simplistic), or attempt to learn a custom distance metric for every single user (which requires a prohibitively massive amount of data per person).
This paper, published at NeurIPS 2022, introduces a framework that elegantly bridges this gap by disentangling perception from preference. The authors observe that while users have distinct individual tastes (e.g., one prefers red, another prefers blue), they generally share a common perception of similarity (e.g., both agree that navy is closer to royal blue than it is to bright yellow). By modeling these two facets jointly, the system can make accurate recommendations using far fewer queries.
The "One for All" Approach
The authors propose a model that jointly learns a shared distance metric—representing the crowd's common perception of item similarity—and individual "ideal points" representing personal taste.
To achieve this mathematically, the researchers model user preferences using a Mahalanobis distance metric ($M$). In this $d$-dimensional feature space, the distance between two items $x$ and $y$ is defined as $d_M(x, y) = \sqrt{(x-y)^T M (x-y)}$. This matrix $M$ allows the model to learn which features matter most for similarity. Each user $k$ is then assigned an ideal point $u_k$ in this space, and the model assumes a user will prefer items that are "closer" to their ideal point according to the shared metric $M$.
Key Technical Innovations
- Amortization of Complexity: Learning a metric $M$ in $d$ dimensions typically requires $O(d^2)$ comparisons. By sharing $M$ across $K$ users, the "per-user" cost of learning the metric drops significantly. Once the shared $M$ is established, identifying a specific user's ideal point only requires $O(d)$ comparisons.
- Linearization: The authors demonstrate that the quadratic distance comparison can be rewritten as a linear system by introducing a "pseudo-ideal point" $v_k = -2Mu_k$. This transformation makes the optimization problem highly tractable.
- Low-Rank Regularization: To handle noise and high-dimensional data, the model employs convex optimization. It uses the Frobenius norm for full-rank metrics and the Nuclear norm to encourage low-rank metrics. The low-rank assumption is particularly powerful, as human perception is often driven by only a few latent features.
Experimental Validation and Results
The researchers evaluated their approach on both synthetic data (to verify theoretical error bounds) and a real-world Color Preference Dataset involving 37 respondents making paired comparisons in the 3D CIELAB color space.
- Sample Efficiency: Theoretical and empirical results confirm that the total number of queries needed across the crowd scales with the rank of the metric, rather than the square of the feature dimension.
- Superior Performance: On the real-world color dataset, the joint model outperformed baseline models that attempted to learn metrics for users individually.
- Psychophysical Alignment: The learned metric for the color data revealed that "lightness" was the most critical dimension for how users perceived color similarity, a finding that perfectly aligns with established results in psychophysics.
- Robustness: Models utilizing Nuclear norm regularization to encourage low-rank structures demonstrated superior performance in noisy environments compared to standard metric learning approaches.
Limitations and Future Directions
While highly effective, the framework does have limitations. The Mahalanobis metric is fundamentally a linear weighting of features. For highly complex items like raw images or natural language, a non-linear metric (such as those learned via deep neural networks) might be necessary.
Additionally, current theoretical guarantees suggest that the number of unique items in the dataset must be relatively large ($\Omega(d^2)$) to fully identify the metric, which could pose a hurdle in niche domains with sparse catalogs. Future work may explore incorporating "triplet queries" (e.g., "Is item A more like B or C?") to further reduce the number of items required to learn the underlying perceptual metric.
Summary updated