Abstract
This paper investigates the problem of simultaneous preference and metric learning from a crowd of respondents. Given a set of items represented by $d$-dimensional feature vectors and paired comparisons (e.g., "item $i$ is preferable to item $j$"), we propose a model that jointly learns a shared distance metric characterizing the crowd's general perception of item similarity alongside latent "ideal points" reflecting individual user preferences. This framework captures individual nuances while enjoying a metric learning sample cost that is amortized over the entire crowd. We establish theoretical limits for noiseless settings, provide prediction error guarantees for noisy binary measurements, and demonstrate that sample complexity improves significantly when the underlying metric is low-rank. Our findings are validated through simulations and a real-world study of human color preferences.
Introduction
Modern recommendation systems frequently encounter the "cold start" problem: how to accurately model a user's complex preferences with minimal data. Traditional preference models often assume a fixed Euclidean distance to measure similarity. However, human perception is rarely uniform. While two users may have vastly different tastes—one preferring horror films and another comedy—they often share a common underlying "perception metric" regarding which films are similar based on features like pacing, cinematography, or thematic elements.
Learning such a metric typically requires a prohibitive amount of data ($O(d^2)$ comparisons for $d$ features). If a system attempts to learn a unique metric for every user, the data requirement becomes unsustainable. This research addresses a pivotal question: Can we learn a single shared metric for a crowd while still capturing the unique preferences of each individual?
The Framework: Ideal Points and Mahalanobis Metrics
The authors utilize the Ideal Point Model to bridge the gap between shared perception and individual choice. In this model, each user $k$ is represented by a latent ideal point $u_k$ in a $d$-dimensional feature space. A user is assumed to prefer item $i$ over item $j$ if item $i$ is closer to their ideal point.
To account for shared perception, the distance is measured using a Mahalanobis metric $M$: $$d_M(x, y) = \sqrt{(x-y)^T M (x-y)}$$ Here, $M$ is a positive semidefinite matrix that reweights and correlates features to reflect the crowd's collective similarity measures.
Technical Innovations
To make this problem tractable, the authors introduce several key strategies:
- Linearization: By defining a "pseudo-ideal point" $v_k = -2Mu_k$, the quadratic distance comparisons are transformed into a linear system, allowing for the application of convex optimization tools.
- Convex Relaxation: For noisy, binary human responses, the authors formulate the task as a risk minimization problem. They provide specific algorithms for both full-rank metrics (using Frobenius norm regularization) and low-rank metrics (using nuclear norm regularization).
- Subspace Alignment: In low-rank scenarios, the model enforces that the pseudo-ideal points $v_k$ lie within the same column space as the metric $M$, a structural constraint that significantly accelerates learning in high-dimensional spaces.
The Power of Amortization
The core theoretical contribution of this work is the "amortization effect." In a single-user setting, learning the metric $M$ requires $O(d^2)$ samples. However, by learning across $K$ users, the cost of the metric is distributed.
The authors prove that the excess prediction risk scales with $O(\sqrt{(d^2 + Kd)/|S|})$, where $|S|$ is the total number of comparisons. As the number of users $K$ grows, the $d^2$ term (the metric) becomes negligible. Consequently, each user only needs to provide roughly $O(d)$ samples—the minimum required to locate their own ideal point—and the shared metric is essentially learned "for free."
Empirical Validation
Synthetic Data
Simulations using Gaussian-sampled items and ideal points confirmed the theoretical sample complexity bounds. The results demonstrated that the joint model consistently outperforms independent learning as the crowd size increases.
Color Preference Dataset
The model was tested on a psychometric dataset of 48 respondents making pairwise comparisons between 37 colors. While the colors were represented in the CIELAB space—designed to be perceptually uniform—the study revealed it is not preferentially uniform.
Learning a custom metric $M$ significantly improved prediction accuracy over the standard Identity metric. Interestingly, the learned metric revealed that "Lightness" is the dominant factor in human color preference. The "Learned M (Crowd)" model outperformed both fixed-metric models and models that attempted to learn unique metrics per user, particularly in data-scarce regimes (fewer than 20 queries per user).
Conclusion and Future Work
This research demonstrates that shared perception can be leveraged to reduce the data burden of individual preference learning. By amortizing the cost of a Mahalanobis metric across a crowd, systems can achieve high accuracy with fewer user interactions.
Future research directions include:
- Heterogeneity: Moving beyond a single shared metric to model subpopulations with different perception styles.
- Non-linearity: Extending the Mahalanobis metric to non-linear transformations via deep neural networks.
- Active Learning: Investigating how the active selection of item pairs (rather than random sampling) could further optimize sample efficiency.
Summary updated