Active Evaluation of Ranking Functions Based on Graded Relevance (Extended Abstract)

1 Introduction

This paper addresses the problem of estimating the performance of a given ranking function in terms of graded relevance measures such as Discounted Cumulative Gain [J¨arvelin and Kek¨al¨ainen, 2002] and Expected Reciprocal Rank [Chapelle et al., 2009]. In informational retrieval domains, ranking models often cannot be evaluated on heldout training data. For example, older training data might not represent the distribution of queries the model is currently exposed to, or ranking models might be procured from a third party that does not provide any training data.

In practice, ranking performance is estimated by applying a given ranking model to a representative set of test queries

∗The paper on which this extended abstract is based was the recipient of the best paper award of the 2012 European Conference on Machine Learning [Sawade et al., 2012a].

Timo von Oertzen

University of Virginia Charlottesville, VA, USA timo@virgina.edu

Niels Landwehr

University of Potsdam Potsdam, Germany landwehr@cs.uni-potsdam.de

and manually assessing the relevance of all retrieved items for each query. We study the problem of estimating the performance of ranking models as accurately as possible on a fixed budget for labeling item relevance, or, equivalently, minimizing labeling costs for a given level of estimation accuracy. Specifically, we focus on the problem of estimating performance differences between two ranking models; this is required, for instance, to evaluate the result of an index update.

We assume that drawing unlabeled data x ∼ p(x) from the distribution of queries that the model is exposed to is inexpensive, whereas obtaining relevance labels is costly. The standard approach to estimating ranking performance is to draw a sample of test queries from p(x), obtain relevance labels, and compute the empirical performance. However, recent results on active risk estimation [Sawade et al., 2010] and active comparison [Sawade et al., 2012b] indicate that estimation accuracy can be improved by drawing test examples from an appropriately engineered instrumental distribution q(x) rather than p(x), and correcting for the discrepancy between p and q by importance weighting.

In this paper, we study active estimates of ranking performance. Section 2 details the problem setting. Section 3 derives cost-optimal sampling distributions. Section 4 presents empirical results, Section 5 concludes with a discussion of related work.

2 Problem Setting

Let X denote a space of queries and Z denote a finite space of items. We study ranking functions

that, given a query x ∈ X , return a list of |r(x)| items ri(x) ∈ Z ordered by relevance. The number of items in a ranking r(x) can vary depending on the query and application domain from thousands (web search) to ten or fewer (mobile applications that have to present results on a small screen). Ranking performance of r is defined in terms of graded relevance labels yz ∈ Y that represent the relevance of an item z ∈ Z

for the query x, where Y ⊂ R is a finite space of relevance labels with minimum zero (irrelevant) and maximum ymax (perfectly relevant). We summarize the graded relevance of all z ∈ Z in a label vector y ∈ Y Z with components yz for z ∈ Z.

The performance of a ranking r(x) given a label vector y is scored by a ranking measure L(r(x), y). Intuitively, L(r(x), y) will be high if many relevant items are ranked highly in r(x). In the longer version of this paper [Sawade et al., 2012a], we study active performance estimation in detail for two commonly used ranking measures: Discounted Cumulative Gain (DCG), introduced by J¨arvelin and Kek¨al¨ainen [2002], and Expected Reciprocal Rank (ERR), introduced by Chapelle et. al [2009].

In this paper, we will mainly discuss the ERR ranking performance measure. ERR is based on a probabilistic user model: the user scans a list of documents in the order defined by r(x) and chooses the first document that appears sufficiently relevant; the likelihood of choosing a document z is a function of its graded relevance score yz. If s denotes the position of the chosen document in r(x), then ERR is the expectation of the reciprocal rank 1/s under the probabilistic user model. More formally, ERR is given by

Both DCG and ERR discount relevance with ranking position, ranking quality is thus most strongly influenced by documents that are ranked highly. If r(x) includes many items, DCG and ERR are in practice often approximated by only labeling items up to a certain position in the ranking or a certain relevance threshold and ignoring the contribution of lower-ranked items.

The overall ranking performance of the function r with respect to the distribution p(x, y) is given by

If the context is clear, we refer to R[r] simply by R. Since p(x, y) is unknown, ranking performance is typically approximated by an empirical average

where a set of test queries x1, ..., xn and relevance label vectors y1, ..., yn are drawn iid from p(x, y).

Test queries xi need not necessarily be drawn according to the input distribution p. When instances are drawn according to an instrumental distribution q, an estimator can be defined as

where (xj, yj) are drawn from q(x)p(y|x) and W = ∑nj=1 p(xj ) q(xj) . Weighting factors p(xj) q(xj) correct for the discrepancy between p and q, and ensure that the estimator is consistent (that is, ˆRn,q converges to R with n→∞). For certain choices of the sampling distribution q, ˆRn,q may be a more label-efficient estimator of the true performance R than ˆRn [Sawade et al., 2010].

A crucial feature of ranking domains is that labeling costs for queries x ∈ X vary with the number of items |r(x)| returned and item-specific features such as the length of a document whose relevance has to be determined. We denote labeling costs for a query x by λ(x). For the rest of the paper, we assume that we are given two ranking functions r1 and r2, and the goal is to find an accurate estimate ˆΔn,q = ˆRn,q[r1] - ˆRn,q[r2] of their true performance difference Δ = R[r1] - R[r2]. We have additionally studied the related problem of actively estimating the absolute performance R[r] of a single ranking function r [Sawade et al., 2012a].

More formally, in this paper we want to find the sampling distribution q∗ minimizing the expected deviation of ˆΔn,q fromΔ under the constraint that the expected overall labeling costs stay below a budget Λ ∈ R:

Note that Optimization 4 represents a trade-off between labeling costs and informativeness of a test query: optimization over n implies that many inexpensive or few expensive queries could be chosen. When applying the method, we will sample and label test queries from the distribution solving Optimization 4; the number of instances sampled in practice is determined by the labeling budget.

3 Optimal Sampling Distribution

We call a sampling distribution asymptotically optimal if it holds that any other sampling distribution produces a higher estimation error E[( ˆΔn,q - Δ)2 ] if Λ is made sufficiently large. Theorem 1 states the asymptotically optimal sampling distribution, thereby asymptotically solving Optimization Problem 4.

Theorem 1 (Optimal Sampling Distribution) Let

δ(x, y) = L(r1(x), y) - L(r2(x), y). The asymptotically optimal sampling distribution is

Unfortunately, the sampling distribution prescribed by Theorem 1 cannot directly be evaluated. It depends on the unknown test distribution p(x), the unknown conditional distribution p(y|x), and the true performance difference Δ (that can be computed from p(x) and p(y|x), see Equation 1).

Algorithm 1 Active Estimation of Ranking Performance

input Ranking functions r1,r2, graded relevance model p(yz|x, z; θ); pool D, labeling budget Λ.

• 1: Compute empirical sampling distribution q∗ .
• 2: Initialize n← 0.
• 3: Draw x1 ∼ q∗ (x) from D with replacement.
• 4: while ∑n+1 j=1 λ(xj) ≤ Λ do
• 5: Obtain yn+1 ∼ p(y|xn+1) from human labeler.
• 6: Update number of instances n←n+1.
• 7: Draw xn+1 ∼ q∗ (x) fromD w/ replacement.
• 8: end while
• 9: Compute ˆΔn,q = ˆRn,q[r1] - ˆRn,q[r2] (cf. Equation 3) output ˆΔn,q.

To apply the method, we first move to a setting in which a pool D of m unlabeled queries is available. Queries from this pool can be sampled and then labeled at a cost. Drawing queries from the pool replaces generating them under the test distribution; that is, p(x) = 1m for all x ∈ D. Second, we assume independence of individual relevance labels given a query x, that is, p(y|x) = ∏z∈Z p(yz|x, z), and approximate the remaining conditional p(yz|x, z) by a model p(yz|x, z; θ) of graded relevance. For the large class of pointwise ranking methods - that is, methods that produce a ranking by predicting graded relevance scores for query-document pairs and then sorting documents according to their score - such a model can typically be derived from the graded relevance predictors to be evaluated. Note that while these approximations might degrade the quality of the sampling distribution and thus affect the efficiency of the estimation procedure, the weighting factors in Equation 3 ensure that the performance estimate stays consistent.

Plugging these approximations into Equation 5 yields an empirical sampling distribution that can be computed on the pool of test instances. Despite the simplifying assumptions made, computing this empirical distribution is nontrivial because of the summation over the (exponentially large) space of relevance label vectors y in Equation 5. In the longer version of this paper, we derive polynomial-time solutions using dynamic programming for the ranking measures DCG and ERR [Sawade et al., 2012a].

Algorithm 1 summarizes the active estimation algorithm. It samples queries x1, ..., xn with replacement from the pool D according to the distribution q∗ and obtains relevance labels from a human labeler for all items included in r1(xi)∪r2(xi) until the labeling budget Λ is exhausted. Note that queries can be drawn more than once; in the special case that the labeling process is deterministic, recurring labels can be looked up rather than be queried from the deterministic labeling oracle repeatedly. Hence, the actual labeling costs may stay below ∑nj=1 λ(xj). In this case, the loop is continued until the labeling budget Λ is exhausted.

4 Empirical Studies

We compare active estimation of ranking performance (Algorithm 1, labeled active) to estimation based on a test sample drawn uniformly from the pool (Equation 2, labeled passive). Algorithm 1 requires a model p(yz|x, z; θ) of graded relevance in order to compute the sampling distribution q∗ as explained in Section 3. If no such model is available, a uniform distribution p(yz|x, z; θ) = 1 |Y| can be used instead (labeled activeuniD). To quantify the effect of modeling costs, we also study a variant of Algorithm 1 that assumes uniform costs λ(x) = 1 in Equation 5 (labeled activeuniC).

It contains 31,531 queries, and a set of documents for each query whose relevance for the query has been determined by human labelers in the process of developing the Bing search engine. The resulting 3,771,125 query-document pairs are represented by 136 features widely used in the information retrieval community (such as query term statistics, page rank, and click counts). Relevance labels take values from 0 (irrelevant) to 4 (perfectly relevant).

We train different types of ranking functions on part of the data, and use the remaining data as the pool D from which queries can be drawn and labeled until the labeling budget Λ is exhausted. To quantify the human effort realistically, we model the labeling costs λ(x) for a query x as proportional to a sum of costs incurred for labeling individual documents z ∈ r(x); labeling costs for a single document z are assumed to be logarithmic in the document length. The cost unit is chosen such that average labeling costs for a query are one. Figure 2 shows the distribution of labeling costs λ(x). All results are averaged over five folds and 5,000 repetitions of the evaluation process.

Based on the outcome of the 2010 Yahoo ranking challenge [Mohan et al., 2011; Chapelle and Chang, 2011], we study pointwise ranking approaches. The ranking function is obtained by returning all documents associated with a query sorted according to their predicted graded relevance. To train graded relevance models on query-document pairs, we employ Random Forest regression [Breiman, 2001], the ordinal classification extension to Random Forests [Li et al., 2007; Mohan et al., 2011], a MAP version of Ordered Logit [McCullagh, 1980], and a linear Ranking SVM [Herbrich et al., 2000]. For the Random Forest model, we apply the approach from [Li et al., 2007; Mohan et al., 2011] to obtain the probability estimates p(yz|x, z; θ) required for active estimation.

Figure 1 (top row) shows model selection error - defined as the fraction of experiments in which an evaluation method does not correctly identify the model with higher true performance - when comparing different ranking functions based on Random Forest, Logit, and SVM models. Active estimation more reliably identifies the model with higher ranking performance, saving between 30% and 55% of labeling effort compared to passive estimation at Λ = 200.

As a further comparative evaluation we simulate an index update. An outdated index with lower coverage is simulated by randomly removing 10% of all query-document pairs from each result list r(x) for all queries; we estimate the difference in performance between models based on the outdated and current index. Figure 1 (bottom row, left) shows absolute deviation of estimated from true performance difference over labeling budget Λ. We observe that active estimation quantifies the impact of the index update more accurately than passive estimation, saving approximately 75% of labeling effort. We finally simulate the incorporation of novel sources of training data by comparing a Random Forest model trained on 100,000 query-document pairs (r1) to a Random Forest model trained on between 120,000 and 200,000 querydocument pairs (r2). Figure 1 (bottom row; center and right) shows absolute deviation of estimated from true performance difference as a function of Λ and as a function of the number of query-document pairs the model r2 is trained on.

5 RelatedWork

There has been significant interest in learning ranking functions from data in order to improve the relevance of search results [Burges, 2010; Li et al., 2007; Mohan et al., 2011; Zheng et al., 2007].

To reduce the amount of training data that needs to be relevance-labeled, several approaches for active learning of ranking functions have been proposed [Long et al., 2010; Radlinski and Joachims, 2007]. The active performance estimation problem discussed in this paper can be seen as a dual problem of active learning, where the goal is to obtain accurate performance estimates rather than accurate models.

As an alternative to selecting most relevant queries, approaches that select the most relevant documents to label for a single query have also been studied. Carterette et al. [2006] use document sampling to decide which of two ranking functions achieves higher precision at k. Aslam et al. [2006] use document sampling to obtain unbiased estimates of mean average precision and mean R-precision. Carterette and Smucker [2007] study statistical significance testing from reduced document sets.