Abstract
Standard nearest-neighbor algorithms for ranking, such as those based on Kendall-tau (KT) distance, often fail when user preferences are noisy or stochastic. This paper identifies a critical flaw in traditional KT-kNN: it frequently identifies "neighbors" that are distant in the latent feature space. We propose Anchor-kNN, a robust alternative that utilizes the broader population as reference points (anchors) to accurately recover latent similarities. Our method demonstrates superior performance on both synthetic high-dimensional data and the Netflix dataset.
Introduction
In recommendation systems and social choice theory, the "learning-to-rank" paradigm often relies on the assumption that users with similar observed rankings possess similar underlying preferences. The Nearest Neighbor (NN) approach typically employs the Kendall-tau (KT) distance to quantify this similarity by counting pairwise disagreements between rankings. However, this assumption is predicated on deterministic preferences. Real-world human behavior is inherently noisy, often modeled by stochastic processes like the Plackett-Luce model. This paper demonstrates that in the presence of such noise, KT-kNN becomes "critically incorrect," failing to identify true neighbors in the latent space.
The Failure of KT-kNN in Noisy Environments
The authors analyze a distance-based random preference model where users and items are embedded in a latent space. Under the Plackett-Luce model, the probability of a user preferring one item over another depends on their relative distances in this space. The core issue is that the expected KT distance between a target user $x_t$ and another user $x$ does not always reach its minimum at $x = x_t$.
As shown in Figure (a), the function $\mathcal{G}_t(x)$—representing the expected KT distance—can exhibit sublinear behavior or even fail to be minimized at the true latent position $x_t$. In noisy settings, KT-kNN tends to select "extreme" users whose average rankings happen to coincide with the target's noisy observations, rather than users who are truly nearby in the latent space. Theorem 1 in the paper formally proves that for a large fraction of users, KT-kNN returns neighbors at a distance of $\Omega(1)$, meaning they are not "near" at all, even with infinite data.
The Anchor-kNN Algorithm
To overcome the instability of direct pairwise comparisons, the authors introduce Anchor-kNN. Instead of comparing two users directly, this method leverages the rest of the population as "anchors" to create a stable signature for each user.
- Feature Construction: For each user, the algorithm computes the KT distance to every other user (the anchors) in the dataset.
- Latent Signature: These distances form a high-dimensional feature vector representing the user's relationship to the global preference distribution.
- Similarity Computation: The similarity between two users is then defined as the $L_1$ distance between their respective anchor-based feature vectors.
By aggregating information from multiple anchors, the algorithm effectively "averages out" the noise inherent in individual rankings, leading to a much more consistent and robust estimation of latent proximity.
Key Results
Theoretical analysis in a 1D latent space proves that while KT-kNN remains fundamentally biased, Anchor-kNN converges to the true neighbors as the number of items and users grows. Empirically, the method was tested on synthetic datasets with varying dimensions and the real-world Netflix dataset.
As illustrated in Figure (e), while all methods face challenges as dimensionality increases, Anchor-kNN consistently maintains a lower averaged latent distance error compared to standard KT-kNN and traditional collaborative filtering (using cosine similarity). On the Netflix dataset, Anchor-kNN consistently outperformed its peers in preference completion tasks, validating its practical utility in real-world recommendation scenarios.
Conclusion
Anchor-kNN provides a theoretically grounded and empirically robust solution for preference completion in noisy environments. By shifting the focus from direct comparisons to global relationships via anchors, it corrects the systematic biases of traditional nearest-neighbor methods. While the current theoretical proofs are focused on 1D spaces, the empirical success in higher dimensions suggests broad applicability. Future work includes extending these proofs to $d > 1$ and optimizing computational efficiency for web-scale applications.
Summary updated