Active evaluation of ranking functions based on graded relevance

Christoph Sawade, Steffen Bickel, Timo von Oertzen, Tobias Scheffer, Niels Landwehr

Introduction

Evaluating the quality of information retrieval (IR) systems is a fundamental yet resource-intensive task. Traditional evaluation relies on human annotators to provide relevance labels for query-document pairs, a process that becomes prohibitively expensive as datasets scale. This paper proposes an "active evaluation" framework designed to optimize the selection of queries for labeling. By employing an intelligent sampling strategy, the authors demonstrate that it is possible to maintain high estimation accuracy while reducing human labeling effort by up to 75%.

The Challenge of Ranking Evaluation

In modern search engines, performance is typically measured using metrics such as Discounted Cumulative Gain (DCG) and Expected Reciprocal Rank (ERR). These metrics quantify how effectively a system places relevant documents at the top of the search results. However, two primary obstacles hinder efficient evaluation:

  1. Query Drift: User behavior and search trends evolve over time, rendering static "held-out" datasets obsolete and requiring continuous re-evaluation.
  2. Labeling Costs: Human judgment is required to determine the relevance of documents to specific queries. Given the volume of queries and the depth of result lists, exhaustive labeling is financially and logistically taxing.

The standard "passive evaluation" approach involves sampling queries randomly from a natural distribution. This paper argues that such an approach is inefficient because it treats all queries as equally informative, regardless of their complexity or the uncertainty of the ranking model.

Active Evaluation Framework

The authors introduce a framework that shifts from sampling queries from the natural distribution $p(x)$ to an "instrumental distribution" $q(x)$. This distribution is mathematically optimized to minimize the variance of the performance estimate.

Importance Weighting and Consistency

Because the sampling distribution $q(x)$ is biased compared to the true distribution $p(x)$, the framework utilizes importance weighting. This ensures that the final performance estimate remains "consistent"—meaning it converges to the true value as the sample size increases—despite the non-random selection of queries.

Cost-Sensitive Sampling

A significant contribution of this work is the explicit inclusion of labeling costs. Not all queries are equal in terms of effort; a query with dozens of long documents is more expensive to label than one with a few short snippets. The authors prove that the optimal sampling weights should be inversely proportional to the square root of the labeling cost. This allows the system to prioritize "informative yet cheap" queries, maximizing the utility of a fixed budget.

Efficient Computation via Dynamic Programming

Calculating the "informativeness" of a query requires calculating an expectation over all possible relevance labels. For a list of 10 documents with 5 possible relevance grades, there are $5^{10}$ possible combinations. This exponential complexity usually makes active sampling computationally infeasible.

To overcome this, the authors developed a novel polynomial-time algorithm using dynamic programming (DP). This algorithm efficiently computes the necessary distributions for both DCG and the more complex ERR metric. In the case of ERR, where the value of a document depends on the relevance of preceding documents (sequential dependency), the authors successfully decomposed the metric into a form manageable by DP.

Experimental Results

The framework was evaluated using the Microsoft Learning to Rank (MSLR-WEB30k) dataset, which contains over 31,000 queries and 3.7 million query-document pairs with graded relevance labels ranging from 0 (irrelevant) to 4 (perfectly relevant).

The results demonstrate significant efficiency gains across multiple scenarios:

  • Single Model Evaluation: Active evaluation reduced labeling costs by 10% to 20% compared to random sampling.
  • Model Comparison: When comparing two different ranking functions to determine which is superior, the method was even more effective, saving between 30% and 55% of the budget.
  • Index Updates: In scenarios simulating search engine index updates, the framework quantified the impact of changes with 75% less effort than passive baselines.

The method proved robust across various underlying models, including Random Forests and Ordered Logit models.

Conclusion and Future Work

Active evaluation represents a significant step forward in making IR system assessment more sustainable. By intelligently selecting queries based on both informativeness and cost, researchers can achieve high-fidelity results with a fraction of the traditional budget.

However, some limitations remain. The effectiveness of the sampling distribution depends on an initial "introspective" model to estimate relevance; a poor initial model reduces efficiency, though importance weighting maintains accuracy. Future research may explore document-level sampling—deciding which specific documents within a query result list to label—and addressing truncation bias in top-$k$ evaluation.

Summary updated

Abstract

Evaluating the quality of ranking functions is a core task in web search and other information retrieval domains. Because query distributions and item relevance change over time, ranking models often cannot be evaluated accurately on held-out training data. Instead, considerable effort is spent on manually labeling the relevance of query results for test queries in order to track ranking performance. We address the problem of estimating ranking performance as accurately as possible on a fixed labeling budget. Estimates are based on a set of most informative test queries selected by an active sampling distribution. Query labeling costs depend on the number of result items as well as item-specific attributes such as document length. We derive cost-optimal sampling distributions for the commonly used performance measures Discounted Cumulative Gain and Expected Reciprocal Rank. Experiments on web search engine data illustrate significant reductions in labeling costs.
BibTeX
@inproceedings{sawade2012active,
  author = {Christoph Sawade and Steffen Bickel and Timo von Oertzen and Tobias Scheffer and Niels Landwehr},
  title = {{Active evaluation of ranking functions based on graded relevance}},
  booktitle = {ECML/PKDD},
  year = {2012},
  doi = {10.1007/978-3-642-33486-3\_43},
}
Figure