On Sampled Metrics for Item Recommendation (Extended Abstract)

Walid Krichene, Steffen RendleIJCAI 2021 · DOI

Evaluating recommendation algorithms by ranking a small sample of items instead of the full catalog is a common but dangerous practice in recommender systems research. This paper demonstrates that "sampled metrics" are mathematically inconsistent—meaning they can rank a poor algorithm above a superior one even in expectation—and proposes statistical corrections to mitigate these errors.

The Problem: The Sampling Shortcut

In large-scale recommender systems, calculating the exact rank of a relevant item across millions of candidates is computationally expensive. To save time, researchers often take the relevant item and mix it with a small random sample of irrelevant items (e.g., 99 distractors). Metrics like NDCG, Recall@K, or Average Precision are then calculated on this subset. The underlying assumption is that performance on the sample is a reliable proxy for performance on the full catalog. This research proves that this assumption is often false; sampled metrics do not just add noise, they fundamentally alter the metric's properties.

Theoretical Framework

The authors establish that the rank of an item in a sample follows a Binomial distribution. Specifically, if an item has a true rank $r$ in a catalog of $n$ items, its rank $\tilde{r}$ in a sample of $m$ items is distributed as $\tilde{r} \sim B(m, \frac{r-1}{n-1}) + 1$.

A key finding is the "AUC Collapse." As the sample size $m$ decreases, every ranking metric begins to behave like the Area Under the ROC Curve (AUC). Unlike top-heavy metrics like NDCG, AUC is "position-unaware," treating an improvement at rank 100 the same as an improvement at rank 1.

Quality metrics as a function of the rank r of the relevant item. The linear nature of AUC contrasts with the top-heavy nature of other metrics.

Systematic Inconsistency and Flipped Rankings

The error introduced by sampling is not merely random noise that averages out over many trials. It is a systematic bias. In empirical "toy" examples, the authors show that a recommender that is ten times better than its competitors on exact metrics can appear to be the worst performing when evaluated using sampled Average Precision with 99 items.

Expected Average Precision vs. Number of Samples. As the sample size decreases, the relative ordering of different recommenders can flip, leading to incorrect conclusions.

Proposed Corrections

To address these biases, the paper proposes two main approaches:

  1. Unbiased Rank Estimator: An "upscaling" method to estimate the true rank from the sampled rank: $\hat{r} = 1 + \frac{(n-1)(\tilde{r}-1)}{m}$.
  2. Bias-Variance Trade-off: A regularized least-squares approach that minimizes the difference between the sampled estimate and the true value while controlling for variance.

Key Results and Recommendations

  • AUC Consistency: The authors prove that AUC is the only common metric naturally consistent under sampling. If using Recall or NDCG on a sample, the researcher is no longer measuring those specific properties.
  • Correction Efficacy: The proposed unbiased rank estimator significantly improves the likelihood of identifying the correct top algorithm, though it introduces higher variance, requiring more random seeds for stable results.

Conclusion

The ultimate recommendation is to avoid sampling whenever possible. Modern hardware and efficient indexing libraries (like FAISS) have largely removed the computational necessity for this shortcut. If sampling is unavoidable, researchers must apply statistical corrections and acknowledge that the fundamental characteristics of their chosen metrics have changed.

Summary updated

BibTeX
@inproceedings{krichene2021sampled,
  author = {Walid Krichene and Steffen Rendle},
  title = {{On Sampled Metrics for Item Recommendation (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/651},
}
Figure