TL;DR
This paper investigates the limitations of the Euclidean preference model, commonly used in AI for representing user preferences. The authors demonstrate that for low-dimensional Euclidean spaces, almost all preference profiles are not representable, and derive bounds on the expected error when approximating non-Euclidean preferences. This has significant implications for the interpretation and dimensionality choices of vector embeddings in real-world applications.
What Problem Does This Paper Address?
Many AI systems, particularly recommender systems and multi-agent systems, rely on models of user preferences. A popular approach is the "Euclidean preference model," which assumes users have an "ideal point" in a multi-dimensional space, and they prefer items closer to this point. This model is often implicitly assumed even when using vector embeddings, where similarity is measured by Euclidean distance or cosine similarity.
However, previous work has shown that not all possible preference orderings can be perfectly represented by a Euclidean model, especially when the dimensionality of the space is low compared to the number of individuals or alternatives. This paper tackles two key questions arising from this:
- How common are these non-Euclidean preference profiles? Are they rare, pathological edge cases, or do they constitute the majority?
- If we do use a Euclidean model to approximate these non-Euclidean preferences, how large is the expected error?
Understanding these limitations is crucial for building AI systems that accurately reflect human preferences and avoid causing harm.
Methods
The paper extends previous theoretical work on the expressiveness of Euclidean preference models. The authors focus on a specific type of "pathological sub-profile" called the circulant pathology to derive bounds.
- Proportion of Non-Euclidean Profiles: They derive a lower bound on the probability that a randomly generated preference profile exhibits a circulant pathology. This pathology is a specific arrangement of preferences among a subset of individuals and alternatives that inherently cannot be captured by a low-dimensional Euclidean model. The derivation involves combinatorial arguments and relates to problems like the coupon collector's problem.
- Expected Error: To quantify approximation error, they use the Kendall tau distance, which measures the number of pairwise disagreements between two preference orderings (equivalent to the minimum number of adjacent swaps to transform one into the other). They derive a lower bound on the expected Kendall tau distance between a randomly chosen preference and its closest representable preference within a given Euclidean model. This bound is derived under the assumption that the number of unique preferences in the profile is large enough to "fill" the representable space, and it relies on analyzing the structure of the permutohedron (a geometric object representing permutations).
Datasets
Not discussed in the paper. The paper is theoretical and focuses on deriving bounds for general preference profiles and populations.
Key Insights and Ideas
- Non-Euclidean Preferences are the Norm, Not the Exception: The paper strongly suggests that for low-dimensional Euclidean spaces (where dimension $d$ is much smaller than the number of individuals $I$ or alternatives $A$), almost all preference profiles are not d-Euclidean. This means the standard Euclidean model is fundamentally limited in its expressiveness for many realistic scenarios.
- Dimensionality is Key: The bounds show that the proportion of non-Euclidean profiles and the expected approximation error decrease significantly as the dimensionality ($d$) of the Euclidean space increases, especially as $d$ approaches $\min(I, A)$. This highlights the importance of choosing adequate dimensionality for embeddings.
- Error is Quantifiable: Even when a perfect Euclidean representation is impossible, the paper provides a way to quantify the expected error in approximation. This is crucial for understanding the reliability of systems built on these models.
- Implications for Embeddings: The findings directly apply to vector embeddings used in applications like recommender systems. If these embeddings are interpreted through a Euclidean lens (e.g., via cosine similarity), and the dimensionality is low relative to the number of users/items, the learned relationships might not accurately reflect true underlying preferences.
Key Results
- Lower Bound on Non-Euclidean Profiles: The paper provides a lower bound on the probability that a random preference profile is not d-Euclidean. This bound approaches 1 as the number of individuals ($I$) grows large, provided $d$ is small relative to $I$ and $A$.
- Lower Bound on Expected Error: A lower bound on the expected Kendall tau distance between a random preference and its closest Euclidean approximation is derived. For settings where $d \ll \min(I, A)$, this bound can be as high as 7% of the maximum possible variation (measured by Kendall tau distance).
Limitations and Future Work
- Lower Bounds Only: The paper derives lower bounds for both the proportion of non-Euclidean profiles and the expected error. These bounds are not necessarily tight, meaning the actual proportion or error could be even higher.
- Specific Pathology: The bounds are primarily derived using the "circulant pathology." While this pathology is representative of a broader class of non-Euclidean profiles, it doesn't cover all possible cases.
- Computational Complexity: Evaluating the exact bounds can be computationally intensive for large numbers of individuals ($I$) and alternatives ($A$).
- Future Work: The authors suggest extending the bounds to cases where the number of unique preferences ($I^*$) is small relative to the representable space ($r$), developing more computationally efficient approximations, exploring robustness to different preference distributions, and improving the tightness of the bounds. They also ponder the extent to which neural networks might implicitly compensate for these Euclidean model limitations.
Summary updated