Introduction
Evaluating the performance of information retrieval (IR) systems, such as search engines and recommenders, typically requires "ground truth" labels provided by human judges. However, obtaining these labels is expensive and time-consuming. Historically, researchers employed pooling, where only the top results from a set of systems are judged. While efficient, pooling introduces significant bias toward the systems that contributed to the pool, making the resulting datasets less reliable for evaluating new, unseen systems.
Recent shifts toward probabilistic sampling have addressed the bias issue, providing provably unbiased and reusable evaluations. However, simple random sampling often suffers from high variance, requiring a large number of judgments to distinguish between systems reliably. This paper addresses this efficiency gap by asking: How can we select the most informative documents to judge to evaluate systems with minimal effort?
Methodology: A Unified Monte Carlo Framework
The authors frame IR evaluation as a Monte Carlo estimation problem, treating standard metrics like Discounted Cumulative Gain (DCG) or Precision@k as expectations over a document distribution. The core innovation lies in applying Importance Sampling to three scenarios: single system evaluation, pairwise comparison, and multiple system comparison.
To minimize variance, the authors derive the optimal sampling distribution ($Q^*$). For pairwise comparisons, the mathematical derivation suggests sampling documents where systems disagree most. Documents ranked similarly by both systems offer little information regarding which system is superior. Since true relevance is unknown a priori, the authors use approximate utilities (e.g., BM25 scores or rank-based heuristics) to guide the sampler toward the most informative pairs.
As shown in the table above, almost all common IR metrics are linearly decomposable, allowing them to be integrated into this unified importance sampling framework.
Experimental Evaluation
The proposed methods were validated using two distinct environments:
- SYNTH: A synthetic recommender system dataset featuring 6,000 users and 2,000 items with ratings from 0 to 4.
- TREC: Data from the TREC-8 ad hoc track. By using a subset where top documents were already fully judged, the authors could simulate sampling and compare results against a known "ground truth."
Key Results and Discussion
The experiments confirmed that the importance sampling approach significantly outperforms naive methods in both accuracy and efficiency.
- Efficiency Gains: In both synthetic and real-world tests, the $Q^*$ sampling method reached the same level of accuracy as naive sampling using approximately 50% fewer judgments.
- Unbiasedness and Reliability: Unlike deterministic pooling, these estimators converge to true performance values as sample sizes increase without systematic error. Furthermore, the theoretical confidence intervals proved accurate in practice.
- Superior Ranking Performance: When ranking multiple systems, the $Q^*$ sampler maintained a significantly higher correlation (Kendall’s Tau) with true rankings across all budget levels.
Conclusion
This research provides a principled method for making IR evaluation both cheaper and more accurate. By focusing on "contested" documents and using importance weights for reusability, the framework allows for unbiased evaluation of new systems using previously collected data. Future work may explore "active" query selection and adaptive sampling techniques to further enhance efficiency.
Summary updated