Sketching Algorithms for Approximating Rank Correlations in Collaborative Filtering Systems

Yoram Bachrach, Ralf Herbrich, Ely PoratSPIRE 2009 · DOI

TL;DR

This paper introduces a novel sketching technique to efficiently approximate rank correlations (specifically Kendall's Tau) between users in collaborative filtering systems. This allows for more nuanced user similarity assessment beyond simple item overlap, enabling better recommendations while significantly reducing storage and computational costs.

What Problem Does This Paper Address?

Collaborative filtering (CF) systems recommend items to users based on the preferences of similar users. A key challenge is determining user similarity. While previous work focused on approximating the proportion of shared items (Proportional Intersection or PI) between users' ranked lists, this paper addresses a more critical gap: approximating the correlation between these rankings. Simply having many shared items isn't enough; users might have ranked them very differently. Storing complete user rankings is infeasible for large-scale systems. Therefore, the authors aim to develop a method that can estimate rank correlation using extremely concise "sketches" of user rankings, maintaining high accuracy and confidence with minimal data.

Methods

The core contribution is a rank correlation sketching framework. This framework builds upon existing item sketching techniques from prior work [2]. The original item sketches approximate the PI by using min-wise independent hash functions to create compact representations of item sets.

The novel aspect here is the extension to rank correlation. The authors propose rank correlation sketches that augment the item sketches. For each user, the sketch now includes not only the minimal items under a set of random hash functions (as in item sketches) but also the ranks of these minimal items according to that user's ranking.

The key idea is that when two users' item sketches "collide" (i.e., they have the same minimal item under a given hash function), this provides a pair of items that can be used to estimate the rank correlation. By analyzing the ranks assigned to these colliding items by each user, the system can approximate Kendall's Tau. The paper leverages Hoeffding's inequality to bound the error and determine the required sketch size for a desired accuracy and confidence level.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and algorithmic design, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Beyond Item Overlap: The paper highlights that simply knowing users share many items isn't sufficient for good recommendations. Their relative ordering (ranking) of those shared items is crucial for understanding taste similarity.
  • Rank Correlation via Collisions: The ingenious insight is using "sketch collisions" (where two users' sketches agree on a minimal item under a hash) as a proxy for randomly sampled pairs of items. This allows for rank correlation estimation without explicitly sampling pairs.
  • Concise Representation: The sketches are designed to be extremely compact, with their size being logarithmic in confidence and polynomial in accuracy. This is critical for scalability in large recommender systems.
  • Kendall's Tau Approximation: The framework specifically targets Kendall's Tau, a well-established measure of rank correlation, making the results directly applicable to existing similarity metrics.

Key Results

The paper provides theoretical guarantees for the proposed sketching framework. Specifically, it shows that:

  • The framework can approximate Kendall's Tau with a given accuracy ($\epsilon$) and confidence ($1-\delta$).
  • The required sketch size is polynomial in accuracy and logarithmic in confidence.
  • The probability of a sketch collision for users with a Proportional Intersection (PI) of at least $p^*$ is at least $2p^*/(2-p^*)$.

Limitations and Future Work

The authors acknowledge several limitations:

  • Limited to Kendall's Tau: The current framework only approximates Kendall's Tau and does not extend to other rank correlation measures like Spearman's Rho.
  • Assumes Complete Rankings: The analysis assumes users provide complete rankings of items, and it does not handle ties in rankings.
  • Theoretical Analysis: The paper's analysis is theoretical, and the authors suggest that empirical testing on real-world datasets is a crucial next step.

Future work could involve extending the framework to other correlation measures, handling incomplete rankings and ties, and conducting empirical studies to validate the theoretical performance.

Summary updated

BibTeX
@inproceedings{bachrach2009sketching,
  author = {Yoram Bachrach and Ralf Herbrich and Ely Porat},
  title = {{Sketching Algorithms for Approximating Rank Correlations in Collaborative Filtering Systems}},
  booktitle = {SPIRE},
  year = {2009},
  doi = {10.1007/978-3-642-03784-9\_34},
}
Figure