The Third International Workshop on Evaluating Information Access (EVIA), June 15, 2010, Tokyo, Japan

Ranking Retrieval Systems without Relevance
Assessments – Revisited
Chin-Yew Lin

Tetsuya Sakai

Microsoft Research Asia, PRC

Microsoft Research Asia, PRC

tetsuyasakai@acm.org

cyl@microsoft.com

ABSTRACTWe re-examine the problem of ranking retrieval systems
without relevance assessments in the context of collaborativeevaluation forums such as TREC and NTCIR. The problem
was ﬁrst tackled by Soboroﬀ, Nicholas and Cahan in 2001,
using data from TRECs 3-8 [16]. Our long-term goal is tosemi-automate repeated evaluation of search engines; ourshort-term goal is to provide NTCIR participants with a“system ranking forecast” prior to conducting manual relevance assessments, thereby reducing researchers’ idle timeand accelerating research. Our extensive experiments using
graded-relevance test collections from TREC and NTCIR
compare several existing methods for ranking systems without relevance assessments. We show that (a) The simplest
method of forming “pseudo-qrels” based on how many systems returned each pooled document performs as well as
any other existing method; and that (b) the NTCIR systemrankings tend to be easier to predict than the TREC robust
track system rankings, and moreover, the NTCIR pseudoqrels yield fewer false alarms than the TREC pseudo-qrels doin statistical signiﬁcance testing. These diﬀerences between
TREC and NTCIR may be because TREC sorts pooled documents by document IDs before relevance assessments, while
NTCIR sorts them primarily by the number of systems that
returned the document. However, we show that, even for the
TREC robust data, documents returned by many systems
are indeed more likely to be relevant than those returned by
fewer systems.

Categories and Subject Descriptors
H.3.3 [Information Storage and Retrieval]: Information
Search and Retrieval

General Terms
Experimentation

Keywords
test collections, pooling, relevance judgments, evaluation

1.

INTRODUCTION

Search engine companies routinely conduct manual relevance assessments of web pages for thousands of queries forevaluation and improvement. Since manual assessments are

expensive and time-consuming, the idea of evaluating systems without relevance assessments is attractive.
In their very ﬁrst attempt at ranking retrieval systems
without relevance assessments, Soboroﬀ, Nicholas and Cahan [16] remarked that “such a methodology would not be
useful in an environment such as TREC, where there is already a commitment to conducting relevance assessments
and building test collections in the Cranﬁeld tradition.” Infact, our main motivation for tackling this diﬃcult problem
is to accelerate research at evaluation forums such as TREC
and NTCIR.
Take the NTCIR-6 crosslingual task, for example. The
run (i.e. system output) submission deadline was August 1,
2006, and the evaluation results were released on November
29, 2006 [8]. The four months were necessary for the organisers to form “qrels” (i.e. relevance assessment results) for
multiple document languages and to rank submitted runs,
so the participants had no choice but to wait. The “idletime” was reduced to two months at the NTCIR-7 ACLIAIR4QA task (another “ad hoc” IR task), but this resulted intentative qrels [12], and their updated versions were released
six months after NTCIR-7 [13].
If the organisers can release a “system ranking forecast”
with reasonable accuracy right after the run submission deadline, in which at least some good and bad systems are identiﬁed, this may help researchers to conduct some focussed
experiments while waiting for the “true” system ranking toarrive. These experiments may provide some preliminary
lessons to participants1 .
This line of research is complementary to the existing workon constructing test collections economically (e.g. [5, 15])
and those on evaluation with incomplete relevance assessments (e.g. [11]).
The main contributions of this paper are as follows. Using graded-relevance test collections from both TREC andNTCIR, we implement and compare most of the existing
methods for ranking systems without relevance assessments,and show that (a) The simplest method of forming “pseudoqrels” based on how many systems returned each pooled
document performs as well as any other existing method;
and that (b) the NTCIR system rankings tend to be easierto predict than the TREC robust track system rankings, andmoreover, the NTCIR pseudo-qrels yield fewer false alarms
than the TREC pseudo-qrels do in statistical signiﬁcance
1

EVIA 2010 June 15, Tokyo, Japan.
Copyright held by National Institute of Informatics

At NTCIR, participants are required to submit a brief system description together with each run. The system descriptions could be shared among the participants together withthe ranking forecast.

― 25 ―

The Third International Workshop on Evaluating Information Access (EVIA), June 15, 2010, Tokyo, Japan

testing. These diﬀerences between TREC and NTCIR may
be because TREC sorts pooled documents by document IDs
before relevance assessments [19], while NTCIR sorts them
primarily by the number of systems that returned the document2 . However, we show that, even for the TREC robust
data, documents returned by many systems are indeed more
likely to be relevant than those returned by fewer systems.

2.

RELATED WORK

Soboroﬀ, Nicholas and Cahan [16] were the ﬁrst to tackle
the problem of ranking runs without relevance assessments
given pooled documents. Their idea was to replace manual
relevance assessments by random sampling from the pool, as
it is known that diﬀerent relevance assessment sets can yield
similar system rankings [18]. Their method assumed knowledge of the mean and standard deviation of the number oftruly relevant documents, which is unavailable in practice.
Hence, we implemented a variant of this method, following
a previous study [22]. Furthermore, since Soboroﬀ et al.
found that retaining duplicate documents in the pool (i.e.
documents returned by multiple runs) for sampling improves
system ranking accuracy, we follow this particular method.
Wu and Crestani [22] proposed several methods as alternatives to “Soboroﬀ’s method” and actually compared themin terms of system ranking accuracy. We do not include their
methods in our experiments because (a) they reported that
Soboroﬀ’s method performed better; (b) their best methods rely either on the actual document scores3 or an arbitrary parameter (K) for linear discounting of documents
based on document ranks; (c) their basic idea of comparing
documents across runs is also explored by other approaches
examined in this paper.
Aslam and Savell [3] introduced a very simple method for
ranking runs without relevance assessments, based on how
runs resemble one another, and showed that it correlates
very highly with Soboroﬀ’s method. We re-examine thismethod as well.
Nuray and Can [10] also proposed methods for ranking
runs without relevance assessments. Their supposedly best
method, called “condorcet bias,” consists of two parts: (i)select top 50% of the entire set of runs based on bias as deﬁned by Mowshowitz and Kawaguchi [9], which is supposed
to quantify how diﬀerent each system is from the “norm”;(ii) rank the documents returned by the selected runs by the
condorcet measure and treat the top s% as relevant. Whenthe run selection process (i) is omitted, the method is called“condorcet normal.” We implement both of these methods.
Nuray and Can [10] did not directly compare their methods
with previously proposed ones in their experiments.
2
Note that NTCIR does not pool documents based on thenumber of systems that returned each document: just like
TREC, NTCIR takes the top ranked documents from eachrun to form a pool. The only diﬀerence is the order of documents presented to the relevance assessors. We would liketo stress this at this point, as NTCIR has received multiple
criticisms which incorrectly claim that NTCIR pools documents based on popularity and therefore the NTCIR testcollections are biased. To our knowledge, whether the order of relevance assessments really biases them and aﬀect
evaluation results is an open question [12].
3
If we want to evaluate commercial search engines without
relevance assessments, for example, we may not have accessto the document scores.

Table 1: Data used in previous work (in chronological order).
year
2001
2003
2003
2006
2007
2009

authors
Soboroﬀ et al. [16]Wu/Crestani [22]Aslam/Savell [3]Nuray/Can [10]Spoerri [17]Sakai et al. [13]dataTREC-3,5,6,7,8
ditto
ditto
TREC-3,5,6,7
TREC-3,6,7,8
NTCIR IR4QA-CS,CT,JA

Spoerri [17] proposed another method which also examines the “uniqueness” of systems. His method is for ranking
participating teams rather than the entire set of runs: “itis critical that only one run by each participating system
is included” [17]. This is because uniqueness, as measured
by the number of documents returned by one particular run
only, cancels out when two similar runs from the same teamare considered. We therefore evaluate his method in our
team ranking experiments, which we conduct in addition to
our run ranking experiments. Again, Spoerri [17] did notcompare his method with existing alternatives.
Sakai et al. [13] proposed a very simple method for ranking runs without relevance assessments in the context of the
NTCIR ACLIA IR4QA task [12]. They sorted the pooled
documents ﬁrst by the number of runs that returned the document, then by the sum of the ranks of that document withinthose runs. In fact, at IR4QA, the manual relevance assessments themselves were done after applying this very sort.
They reported that the correlations between their pseudoqrels and their “true” qrels were very high, but questions
remained: does the method work with other data? How
does it compare to other automatic ranking methods?
As Table 1 shows, all of the abovementioned studies used
TREC data with binary relevance assessments, except forthat by Sakai et al. [13] who used Simpliﬁed Chinese (CS),
Traditional Chinese (CT) and Japanese (JA) data with graded
relevance assessments. In contrast, we use graded-relevancedata from both of the evaluation forums (which enables us
to use graded-relevance retrieval eﬀectiveness metrics), andexamine a broad choice of automatic system ranking methods mentioned above.

3. SYSTEM RANKING ALGORITHMS
This section describes our implementations of existing algorithms for ranking retrieval systems without relevance assessments. We use formal and precise descriptions as muchas possible to enhance reproducibility. We use documents
ranked at or above 30 within each run4 , and ignore document scores. While both “Aslam’s method” and “Spoerri’s
method” produce a single system ranking without producing
pseudo-qrels, all other methods yield pseudo-qrels that canbe used just like “true” qrels for computing diﬀerent evaluation metrics: “Soboroﬀ’s method” in fact produces many
pseudo-qrels.
Some of these methods require a few parameters, which
we shall discuss in Section 4.

3.1 Soboroff et al. (“Soboroff’s Method”)
Our version of this method randomly samples 10% of the
documents in the depth-30 pool (containing duplicates) for4
We used the pool depth of 30 rather than 100, because (a)Soboroﬀ et al. reported that shallow pools may work betterfor this task; and (b) shallow pools reduce computational
cost: see Section 3.4.

― 26 ―

The Third International Workshop on Evaluating Information Access (EVIA), June 15, 2010, Tokyo, Japaneach topic and treats them as relevant [16, 22]. This is done
10 times to produce 10 diﬀerent pseudo-qrels ﬁles. (Soboroﬀ et al. [16] sampled 50 times, but the variance acrossour trials was actually very small.) Hence, for each, run,we obtained 10 diﬀerent performance values, and we averaged them to produce a single system ranking. (We also
tried evaluating individual system rankings and averaging
the rank correlations [16], but the ﬁnal outcome was very
similar.)

3.2 Aslam/Savell (“Aslam’s Method”)
Let n be the total number of submitted runs and let Reti,tdenote the set of documents returned at or above rank 30
by run i for topic t(∈ T ). Rank runs by how each run (as adocument set) resembles all other runs [3]: that is, by|Reti,t ∩ Retj,t |1  1.
|T | t n − 1 j=i, Ret =φ |Reti,t ∪ Retj,t |j,t3.3 Spoerri (“Spoerri’s Method”)
Select one run from each participating team. In our experiments, we simply sort the runs by their ﬁle names andtake the ﬁrst run from each team, since this is more reproducible than random selection. (In the original paper [17],the “best” run from each team was chosen. In this sense,
Spoerri’s original experiments actually relied on true qrels.)
If there are K teams, K runs are thus selected. From thisset of runs, select ﬁve runs at random (without replacement)
for K trials, so that each run is selected in exactly ﬁve trials.
(This is in essence to generate an K × K bit matrix in which
each row/column adds up to 5.) Let S(k) denote the set ofruns sampled in the k-th trial, where |S(k)| = 5 for 1 ≤ k ≤K. Rank runs by1 
1  |Reti,t − ∪j∈S(k),j=i Retj,t |−5|T | t1 + |Reti,t |k, i∈S(k)which reﬂects the proportion of documents returned by iand no other run for each trial5 . (Spoerri [17] also proposeda variant of this method that relies on the set of documents
returned by all ﬁve systems in each trial. We evaluated thisvariant too, but the outcome was similar.)

3.4 Nuray/Can (“Nuray’s Methods”)
As mentioned earlier, this method consists of two parts:
run selection by bias, followed by document selection bycondorcet. We tried both “condorcet bias” and “condorcet
normal,” i.e. with and without run selection [10].

3.4.1 Run Selection by Bias
Let Pt = ∪i Reti,t , i.e. the depth-30 pool for topic t. Let
P = ∪t Pt . For each run i and for each topic t, computethe “response vector” respi,t =< r1 , r2 , . . . , r|P | >, whererl = 30/m if run i for topic t contains the l-th document of
P at rank m(≤ 30), and rl = 0 otherwise. Then foreach
Rl = t rl .
run i, let Respi =< R1 , R2 , . . . , R|P | > where 
Let RESP =< S1 , S2 , . . . , S|P | > where Sl = i Rl . Sort
the runs by how diﬀerent each run is from the “norm” [9]:BIAS(i) = 1 − cos(Respi , RESP ) .
5

The minus sign is for obtaining positive correlations withretrieval performance. The “1” in the denominator avoids
division by zero: the same applies to our implementation of
condorcet described in Section 3.4.2.

Take the top 50% most “biased” runs.

3.4.2 Document Selection by condorcet

For every document pair d(∈ Pt ) and d (∈ Pt ) (if run selection described above is applied, then deﬁne the depth-30
pool Pt over the selected runs instead of all runs.), computewint (d, d ), the number of runs in which d is ranked aboved , and loset (d, d ), the number of runs in which d is ranked
below d . (If d is ranked within top 30 and d is either below
rank 30 or not retrieved, then d “wins”.) Sort d(∈ Pt ) bycondorcet(d) =wint (d, d ) +

d

1+



1

d loset (d, d ).

That is, sort by the total number of wins (the larger the
better), and then for each tie, sort by the total number oflosses (the smaller the better). Finally, treat the top 30%
documents as relevant. This is a rather computationallyexpensive method, since the ranks must be compared for all
pairs of pooled documents.

3.5 Sakai et al. (“Sakai’s Method”)
For each document d(∈ Pt ), let runst (d) = {i|d ∈ Reti,t }and let ranki,t (d) denote the rank of d for topic t in runi(∈ runst (d)). Sort the documents in Pt by|runst (d)| + 

1i∈runst (d) ranki,t (d).

That is, sort by the number of runs (the larger the better),and then for each tie, sort by the sum of ranks (the smaller
the better). Treat the top 30% as relevant. (The original
method [13] treated the top 100 documents as relevant. We
also tried this method, but the results were very similar.)
We also tried a simple variant of Sakai’s method that relies
only on |runst (d)| for selecting pseudo-relevant documents.
We call this variant “nruns.”

3.6 On condorcet vs. Sakai’s Method
Here, we show that the primary sort key of condorcet andthe primary sort key of Sakai’s method (i.e. “nruns”) arein eﬀect very similar. Recall that condorcet is a relatively
expensive method. Sakai’s method is not.
Suppose d is ranked above d for every d ∈ Pt (d = d)and for every run i(∈ runst (d)). Then, by deﬁnition,d win(d, d ) = |runst (d)| ∗ (|Pt | − 1). That is, the primary sort key of condorcet is proportional to that of Sakai’s
method. Now, d is in practice ranked “above” d for manyd ’s, because the size of the depth-30 pool |Pt | is much larger
than |Reti,t |(≤ 30): usually hundreds [12].
On the other hand, these two statistics are in theory not
equivalent. For example, suppose d1 is retrieved by exactlyn (> 1) runs, all at rank 30, while d2 is retrieved by exactly
one run at rank 1, so that Sakai’s method prefers d1 to d2 .
It is easy to show that condorcet’s ﬁrst key prefers d2 to d1
if |Pt | < (30n − 1)/(n − 1).

4. DATAThe top half of Table 2 provides some statistics on the
TREC and NTCIR “ad hoc” IR data sets that we used.
“ROBUST03” and “ROBUST04” are from the TREC 2003
and 2004 Robust tracks, and we used the “new” topics [20,21]; “CLIR6-JA” and “CLIR6-CT” are from the Japanese― 27 ―

The Third International Workshop on Evaluating Information Access (EVIA), June 15, 2010, Tokyo, Japan

Table 2: Statistics on test collections, runs and pseudo-qrels used in our experiments.
#all runs (teams)#topics#documents
pool depth of “true” qrels|P | (See Section 3.4.1)#total relevant/topic#L3/L2/L1-relevant/topic#pseudo-rel. (soboroﬀ10%)/topic#pseudo-rel. (nuray30%, sakai30%, nruns30%)/topic#pseudo-rel. (BIAS+nuray30%)/topic#pseudo-rel. (TEAM+soboroﬀ10%)/topic#pseudo-rel. (TEAM+nruns30%)/topic

ROBUST03
ROBUST04
78 (16)110 (14)50
49
approx. 528,000
125
100
11,835
15,542
33.2
41.2
8.1/-/25.0
12.5/-/28.8
95.2
120.9
78.7
104.6
66.2
93.8
34.3
32.7
43.5
44.4

CLIR6-JA
74 (12)50
858,400
100
19,28095.3
2.5/61.1/31.7
113.9
133.2
110.3
29.3
52.4

CLIR6-CT
46 (11)
50
901,446100
18,74688.1
21.6/30.4/36.1
89.4
123.2
103.3
27.2
49.4

IR4QA-CS
40 (9)
97545,162100
18,361169.8-/108.2/61.6
66.4
61.8
41.8
21.4
39.3

and Traditional Chinese subtasks of the NTCIR-6 Crosslin5. METRICS
gual task [8]; and “IR4QA-CS” is from the Simpliﬁed ChiFor evaluating system performance, we adopt the three ofnese subtask of the NTCIR-7 ACLIA IR4QA task [12]. Folﬁcial metrics used at NTCIR ACLIA IR4QA: Average Prelowing a practice at NTCIR [12], highly relevant, relevant
cision (AP), Q-measure (Q) and a version of nDCG [12].
and partially relevant documents are referred to as L3-, L2Q and nDCG, which can handle graded relevance, used theand L1-relevant documents, respectively. Following a pregain values of 3/2/1 for L3/L2/L1-relevant documents, revious study that used both TREC and NTCIR data [11],spectively. Due to lack of space, our tables show results withthe (regular) relevant documents of “ROBUST03” and “ROAP and nDCG only; whereas, our graphs show results with
BUST04” were treated as L1-relevant rather than L2-relevant.
Q, as it behaves like a summary of AP and nDCG [12].
The bottom half of Table 2 shows the number of pseudoFor comparing two system rankings, we use Kendall’s τ
relevant documents per topic for some of the methods werank correlation and its “top-heavy” variant called τap [12,examined. As was described in Section 3.1, we used 10%23]. While we acknowledge some problems with τ for the
samples from the document pool (containing duplicates)
purpose of IR evaluation [4], we believe that it is still usefulfor Soboroﬀ’s method because we did not want to assume
as a simple single-value summary. Moreover, using it toknowledge of the true number of relevant documents per
gether with τap provides an additional insight: for example,
topic. As for Nurray’s, Sakai’s and the “nruns” methods,
if τap is much lower than τ , this means that the top ranks
this paper reports on results that used the top 30% docare quite inaccurate [23]. We note, however, that the raw
uments of the sorted list of pooled documents for forming
system ranking graphs deserve more attention than rank
pseudo-qrels. This percentage was chosen so that the numcorrelation values.
ber of pseudo-relevant documents per topic based on thefour methods are comparable: note that unlike Soboroﬀ’s
6. EXPERIMENTS
method, the other three methods use document pools without duplicates6 .
6.1 Ranking Runs
“BIAS+nuray30%” and “nuray30%” represent Nuray’s method
Table 3 compares the predicted system rankings with thewith and without run selection, respectively, and we use similar notations for other methods. Note that “BIAS+nuray30%” “true” system rankings in terms of τ and τap . Note that
small diﬀerences in these correlation values are not meanyields fewer pseudo-relevant documents than “nuray30%”,
ingful. It can be observed that:as the number of candidate documents is reduced throughrun selection. “TEAM+soboroﬀ10%” represents Soboroﬀ’s(1) BIAS+nuray30%, which uses only half of the available
method applied after selecting one run per team as was deruns through computation of “bias” (see Section 3.4.1),
scribed in Section 3.3 for the task of ranking teams rather
is not eﬀective.
than runs: this is also a kind of run selection and therefore
reduces the size of pseudo-qrels. Using a higher percent(2) All of the other methods show comparable performances,age value with the BIAS and the TEAM methods did notalthough Aslam’s method is less robust in that it fails
improve their ranking prediction accuracy, however.
for the IR4QA-CS data.
We also conducted some “oracle” pseudo-qrels experiments,
Observation (1) challenges Nuray and Can’s claim thatin which we ensured that the number of pseudo-relevant docrun selection by “bias” is eﬀective [10]. However, we note
uments is equal to that of true relevant documents for every
that bias hurt accuracy even in their experiments with the
topic. However, we will omit these results as this did not
TREC-7 data. As Section 3.4.1 showed, bias aggregates thenecessarily improve the ranking prediction accuracy. This
distribution of retrieved documents across topics and forms
is in agreement with an observation by Soboroﬀ et al.: “thea sparse, high-dimensional vector for each system (the exact
ranking of systems is not nearly as aﬀected by variation indimension is shown in the “|P |” row in Table 2). The idea isthe number of relevant documents as it is by which speciﬁc
to rely on systems with a novel document distribution for sedocuments are selected” [16].
lecting pseudo-relevant documents, but this did not work in
our experiments. If system “novelty” is useful at all for pre6
We tried a few other percentage values for all four methods,
dicting system ranking, a better approach may be to deﬁne
and found that the methods are not very sensitive to thea measure of novelty per topic. Another possible approachparameter choice. Moreover, it is more useful to observe
to “purifying” the clues for predicting system ranking would
general trends across multiple and diverse data sets thanbe to perform some kind of topic set reduction [6], thereby
tweaking parameter values that can easily lead to overﬁtting.
removing topics with high uncertainty.
See also the above discussion on the “oracle” experiments.

― 28 ―

The Third International Workshop on Evaluating Information Access (EVIA), June 15, 2010, Tokyo, Japan

Table 3: τ and τap rank correlations: “true” run ranking vs predicted run ranking. For each metric, the threehighest values in each column are shown in bold (a tie is counted as one).
AP

nDCG

aslam
soboroﬀ10%
nruns30%
sakai30%
nuray30%
BIAS+nuray30%
aslam
soboroﬀ10%
nruns30%
sakai30%
nuray30%
BIAS+nuray30%

ROBUST03.559/.377.547/.396.564/.398.561/.402.561/.403.458/.325.504/.356.537/.383.577/.436.572/.432.576/.435.538/.409

ROBUST04.663/.451.630/.432.640/.447.633/.443.633/.443.509/.307.645/.425.641/.454.671/.490.664/.481.665/.482.535/.364

CLIR6-JA.730/.561.783/.648.797/.659.800/.663.800/.663.572/.426.729/.575.806/.653.826/.695.819/.682.851/.682.676/.495

CLIR6-CT.818/.737.857/.721.857/.714.851/.704.851/.704.737/.544.778/.678.851/.685.834/.682.826/.673.826/.673.774/.553

IR4QA-CS.608/.521.890/.824.805/.701.818/.728.818/.729.292/.207.579/.504.908/.806.892/.785.903/.806.900/.804.390/.247

average.676/.529.741/.604.733/.584.733/.588.733/.588.514/.362.647/.508.749/.596.760/.618.757/.615.764/.615.583/.414

Table 4: τ and τap rank correlations: “true” team ranking vs predicted team ranking. For each metric, thethree highest values in each column are shown in bold (a tie is counted as one).
AP

nDCG

aslam
soboroﬀ10%
nruns30%
TEAM+aslam
TEAM+soboroﬀ10%
TEAM+nruns30%
TEAM+spoerri
aslamsoboroﬀ10%
nruns30%
TEAM+aslam
TEAM+soboroﬀ10%
TEAM+nruns30%
TEAM+spoerri

ROBUST03.517/.271.500/.374.533/.261.483/.251.517/.384.533/.451.433/.395.450/.197.433/.286.500/.325.450/.196.500/.373.533/.512.367/.320

ROBUST04.560/.406.604/.483.538/.419.670/.535.670/.536.692/.511.604/.518.516/.347.670/.359.670/.366.582/.414.604/.404.648/.352.538/.401

Observation (2) above is even more alarming: it meansthat the “nruns” method is as good as any. Soboroﬀ etal. [16] discovered that retaining duplicates in the document
pool for sampling pseudo-relevant documents is eﬀective,
which implies that documents returned by many runs are effective pseudo-relevant documents for the purpose of systemranking prediction. The “nruns” method follows this strategy, without having to retain duplicates in pools and to form
10 diﬀerent pseudo-qrels. Whereas, the similarity between
the “nruns30%” and “sakai30%” results imply that Sakai’s
second sort key (the ranks of the returned documents) does
not really matter: the only useful statistic is the number ofruns that returned each document. As for “nuray30%”, theresults are extremely similar to “sakai30%” and “nruns30%”
as was predicted, and is probably not worthwhile given its
computational cost.
Figure 1 visualises the run ranking errors for “aslam”,“soboroﬀ10%” and “nruns30%” with mean Q. For each dataset, the runs have been sorted by the true mean Q performance: the horizontal axis represents the sorted runs; thevertical axis represents the (predicted) performance. Recall that this is more important than the correlation values.
A good ranking prediction method should be smooth, anddecreasing from left to right: each increase in a curve represents an error. It can be observed that the “aslam” curvefor IR4QA-CS is too ﬂat, meaning that it fails to distinguishgood runs from bad ones. Whereas, it is clear that “nruns,”
the simplest method, behaves very similarly to Soboroﬀ’s
method. The striking resemblance of the three curves highlights the fact that they all essentially rely on the same clue:
the number of runs that returned each document.
Figure 2 provides scatterplots of our “nruns30%” resultswith mean Q. The horizontal and the vertical axis represent
true and predicted mean Q, respectively. It is clear that thepredicted performance values are highly correlated with the

CLIR6-JA.909/.862.970/.909
1/1.758/.717.909/.847.788/.747.515/.473
1/1.939/.873
1/1.788/.733.848/.788.818/.764.762/.456

CLIR6-CT
1/1.927/.875.927/.700.818/.775.818/.762.855/.625.600/.323
1/1.891/.775.782/.575.673/.591.818/.535.745/.497.455/.183

IR4QA-CS.556/.427.778/.762.722/.512.444/.452.722/.698.667/.656.000/−.136
1/1
1/1.889/.708.389/.442.889/.896.778/829−.056/−.153

average.708/.593.756/.681.744/.578.635/.546.727/.645.707/.598.430/.315.793/.709.787/.659.768/.595.576/.475.732/.599.704/.591.413/.241

true ones. Also of interest is that, unlike what Soboroﬀ etal. [16] and Aslam and Savel [3] observed, we do not see any
serious underestimation of the very top performers. This
may possibly be because our data sets lack truly “novel”
runs: ranking based on majority votes suﬃces for these runs!
Of course, if there are participating runs that are very
novel, the majority vote approach will probably not work.
One hypothesis that may be worth testing in our future workis that while this approach may not work at early roundsof evaluation workshops where participants explore diverse
techniques for a new task, it may work quite well for moremature stages of the same task (as we have witnessed in thepresent study), where diﬀerent systems have adopted similar techniques. Such an investigation may help evaluation
workshops to save cost in the long run.
Another observation from Table 3 and Figure 1 is that the
NTCIR runs appear to be easier to predict than the TREC
robust runs. For example, the τ values of “nruns30%” are.519-.632 in mean Q for the TREC data, and .806-.842 for
the NTCIR data (not shown in Table 3). The curves for thetwo TREC data sets are also relatively ﬂat, representing
failure to diﬀerentiate good runs from bad ones. We shalldiscuss this further in Section 7.

6.2 Ranking Teams
Table 4 shows results similar to Table 3, but this time forranking teams. One run per team was selected as describedin Section 3.3 and only these runs were ranked. Since Spoerri’s method relies on statistics of the selected runs only, weapplied Aslam’s, Soboroﬀ’s and the “nruns” methods to thesame selected runs as well, to be fair to Spoerri. These runs
are represented by “TEAM+aslam” and so on. In the table, “aslam,” “soboroﬀ10%” and “nruns30%” (without the
TEAM preﬁx) represent the original methods that used theentire set of runs. Thus, the predicted scores have been ex-― 29 ―

The Third International Workshop on Evaluating Information Access (EVIA), June 15, 2010, Tokyo, Japan

Figure 1: Accuracy of run ranking prediction. The
horizontal axis represents runs sorted by true mean
Q-measure values. The vertical axis represents thevalue of sort key for each ranking method.

Figure 2: Scatterplot of mean Q-measure values foreach run based on the “nruns30%” pseudo-qrels.
The horizontal axis represents mean Q-measurecomputed with true qrels.

― 30 ―

The Third International Workshop on Evaluating Information Access (EVIA), June 15, 2010, Tokyo, Japan

tracted from our run ranking experiments. (The results for“sakai30%” and “nuray30%” are very similar to those for“nruns30%” and are omitted.) Figure 3 visualises the teamranking results with mean Q in a way similar to Figure 1.
From these results, we can observe that:(1) Spoerri’s method is not eﬀective. While its team ranking curves do tend to resemble the other ones, it isconsistently less accurate than other methods and fails
completely for IR4QA-CS: see the failure to separate
good teams from bad ones at the bottom of Figure 3.

α = 0.05 were recorded: let this set be C. Similarly, significantly diﬀerent pairs at α = 0.05 using the true qrels werealso recorded: let this set be C∗ . Then, we computed thereliability as |C ∩ C∗ |/|C|. As Table 5 shows, the reliabilityof the “nruns” pseudo-qrels is around 82-100% for the NTCIR data, while it is around 68-81% for the TREC robust
data. Hence the TREC robust pseudo-qrels are more likely
to “cry wolf.”(2) “aslam”, “soboroﬀ10%” and “nruns30%” are generally
eﬀective, especially for the NTCIR data. For example, “aslam” and “nruns30%” predict the mean nDCG
ranking for CLIR6-JA with 100% accuracy. However,“aslam” is again a little unpredictable, in that it yields
a perfectly accurate prediction for IR4QA-CS in termsof nDCG, but inaccurate prediction for the same datain terms of AP and Q.
Thus, the “nruns” method is just as eﬀective as any othermethod not only for the task of ranking all runs, but also
for that of ranking teams.

7.

DISCUSSIONS

We have shown that, despite the number of existing publications on this topic, the number of runs that returned eachdocument appears to be the only eﬀective statistic for ranking systems without relevance assessments. We also showedthat the NTCIR rankings tend to be easier to predict than
the TREC robust track rankings. To compare TREC andNTCIR data from the viewpoint of whether documents returned by many runs do indeed tend to be relevant, we
sorted the pooled documents by |runst (d)| (i.e. the number of runs that returned each document at or above rank
30), and examined whether each document is in fact relevant. Then, for each rank in the sorted pools, the statistics
were summed accross topics.
Figure 4 shows the results, with the horizontal axes representing the document ranks within the sorted pool, down torank 150. L0 (in grey) represents judged nonrelevant documents. (For some of the lower ranks, the sum of judged
relevant and nonrelevant docs is smaller than the topic set
size, because the pool size is less than 150 for some topics.) It can be observed that, for all ﬁve test collections,documents returned by many runs are indeed more likely tobe relevant than those returned by few runs. This is true
even though TREC sorts pooled documents by document
IDs prior to relevance assessments [19], while NTCIR sorts
them either primarily or solely by |runst (d)| [12]. Whether
a sort such as that adopted by NTCIR biases human assessments [19], whether that bias (if indeed it exists) aﬀects
system ranking, and whether such a sort improves the assessment consistency and eﬃciency [12] are important open
questions that are beyond the scope of this study. (See alsofootnote 2 on page 2.)
Finally, in order to further quantify the diﬀerences between the TREC robust and the NTCIR data, we tested
the reliability of statistical signiﬁcance test results based on
the pseudo-qrels as follows: For each data set, we conducted
a two-sided bootstrap hypothesis test with 1,000 trials [11] forevery system pair from our team ranking experiments, using the “nruns” pseudo-qrels. Signiﬁcantly diﬀerent pairs at

Figure 3: Accuracy of team ranking prediction. The
horizontal axis represents runs (one run per team)sorted by true mean Q-measure values. The verticalaxis represents the value of sort key for each ranking
method.

― 31 ―

The Third International Workshop on Evaluating Information Access (EVIA), June 15, 2010, Tokyo, Japan

50
40
30
20
10
0

ROBUST03 (50 topics)

L1
L3
1

11

21

31

41

51

61

71

81

91 101 111 121 131 141

50
40
30
20
10
0

ROBUST04 (49 topics)

L0
L1
L3

1

11

21

31

41

51

61

71

81

91 101 111 121 131 141

50
40
30
20
10
0

CLIR6-JA (50 topics)

L0
L1
L2
L3

1

11

21

31

41

51

61

71

81

91 101 111 121 131 141

50
40
30
20
10
0
100
80
60
40
20
0

L0

CLIR6-CT (50 topics)

L0
L1
L2
L3

1

11

21

31

41

51

61

71

81

91 101 111 121 131 141
IR4QA-CS (97 topics)

L0
L1
L2

1

11

21

31

41

51

61

71

81

91 101 111 121 131 141

Figure 4: Number of L3/L2/L1-relevant and L0 (judged nonrelevant) documents at each rank according to|runst (d)|, summed across topics.

Table 5: Proportion of signiﬁcantly diﬀerent team pairs according to pseudo-qrels that are also sigﬁnicantly
diﬀerent according to true qrels.
AP
Q
nDCG

ROBUST03
69/90=77%
69/89=78%
48/71=68%

ROBUST04
54/69=78%
56/69=81%
54/67=81%

CLIR6-JA
47/55=85%
50/55=91%
46/56=82%― 32 ―

CLIR6-CT
44/46=96%
44/46=96%
43/43=100%

IR4QA-CS
30/32=94%
27/31=87%
29/33=88%

The Third International Workshop on Evaluating Information Access (EVIA), June 15, 2010, Tokyo, Japan

8.

CONCLUSIONS

Through extensive experiments on ranking systems without relevance assessments, we showed that (a) The simplest
method of forming “pseudo-qrels” based on how many systems returned each pooled document performs as well as
any other existing method; and that (b) the NTCIR system rankings tend to be easier to predict than the TREC
robust track system rankings, and moreover, the NTCIR
pseudo-qrels yield fewer false alarms than the TREC pseudoqrels do in statistical signiﬁcance testing. These diﬀerences
between TREC and NTCIR may be because TREC sortspooled documents by document IDs before relevance assessments, while NTCIR sorts them primarily by the number ofsystems that returned the document. However, we showed
that, even for the TREC robust data, documents returned
by many systems are indeed more likely to be relevant thanthose returned by fewer systems.
Our experimental results challenge a few previous studies [10, 17]. Lack of reproducibility and lack of “real” progress
are growing concerns in the IR community [2] and elsewhere [7]. While sharing data and programs among researchers is certainly important for improving this situation,equally important are (1) describing the algorithms and experiments clearly, (2) evaluating using diverse data sets andmultiple evaluation metrics. We believe that the present
study has a strength over similar studies in these aspects.
Clearly, we have a long way towards semi-automatic evaluation of Web search engines, where “majority vote” is notreally an option: Utilising clickthrough data (e.g. [1]), forexample, is a more realistic approach for such a purpose.
On the bright side, however, based on the insights from thepresent study, the NTCIR-8 ACLIA-2 IR4QA task has actually adopted our proposed framework of providing “systemranking forecasts” to participants right after the run submission deadline [14]. The actual usefulness of such forecasts
will be investigated in future work. The relationship between the accuracy of forecasts and the maturity of evaluation workshops (see Section 6.1) should also be investigated.

9.

ACKNOWLEDGMENTS

We thank Ellen Voorhees for checking for us that the
TREC 2004 robust track relevance assessments were done
after sorting by document IDs.

10. REFERENCES[1] R. Agrawal, A. Halverson, K. Kenthapadi, N. Mishra, and
P. Tsaparas. Generating labels from clicks. In Proceedingsof ACM WSDM 2009, pages 172–181, 2009.
[2] T. G. Armstrong, A. Moﬀat, W. Webber, and J. Zobel.
Improvements that don’t add up: Ad-hoc retrieval results
since 1998. In Proceedings of ACM CIKM 2009, pages
601–610, 2009.
[3] J. A. Aslam and R. Savell. On the eﬀectiveness ofevaluating retrieval systems in the absence of relevancejudgments. In Proceedings of ACM SIGIR 2003, pages
361–362, 2003.
[4] B. Carterette. On rank correlation and the distance
between rankings. In Proceedings of ACM SIGIR 2009,
pages 436–443, 2009.
[5] B. Carterette, V. Pavlu, E. Kanoulas, J. A. Aslam, and
J. Allan. Evaluation over thousands of queries. In
Proceedings of ACM SIGIR 2008, pages 651–658, 2008.
[6] J. Guiver, S. Mizzaro, and S. Robertson. A few good topics:
Experiments in topic set reduction for retrieval evaluation.
ACM Transactions on Information Systems, 2009.

[7] J. P. Ioannidis. Why most published research ﬁndings arefalse. PLoS Medicine, 2(8), 2005.
[8] K. Kishida, K.-H. Chen, S. Lee, K. Kuriyama, N. Kando,
and H.-H. Chen. Overview of CLIR task at the sixth
NTCIR workshop. In Proceedings of NTCIR-6, pages 1–19,
2007.
[9] A. Mowshowitz and A. Kawaguchi. Assessing bias in searchengines. Information Processing and Management,
38:141–156, 2002.
[10] R. Nuray and F. Can. Automatic ranking of information
retrieval systems using data fusion. Information Processingand Management, 42:595–614, 2006.
[11] T. Sakai and N. Kando. On information retrieval metrics
designed for evaluation with incomplete relevanceassessments. Information Retrieval, 11:447–470, 2008.
[12] T. Sakai, N. Kando, C.-J. Lin, T. Mitamura, H. Shima,
D. Ji, K.-H. Chen, and E. Nyberg. Overview of the
NTCIR-7 ACLIA IR4QA task. In Proceedings of NTCIR-7,
pages 77–114, 2008.
[13] T. Sakai, N. Kando, C.-J. Lin, R. Song, H. Shima, andT. Mitamura. Ranking the NTCIR ACLIA IR4QA systems
without relevance assessments. DBSJ Journal, 8(2):1–6,
2009.
[14] T. Sakai, H. Shima, N. Kando, R. Song, C.-J. Lin,T. Mitamura, M. Sugimoto, and C.-W. Lee. Overview of
ACLIA IR4QA. In Proceedings of NTCIR-8, 2010.
[15] M. Sanderson and H. Joho. Forming test collections withno system pooling. In Proceedings of ACM SIGIR 2004,
pages 33–40, 2004.
[16] I. Soboroﬀ, C. Nicholas, and P. Cahan. Ranking retrieval
systems without relevance judgments. In Proceedings of
ACM SIGIR 2001, pages 66–73, 2001.
[17] A. Spoerri. Using the structure of overlap between search
results to rank retrieval systems without relevancejudgments. Information Proceesing and Management,
43:1059–1070, 2007.
[18] E. M. Voorhees. Variations in relevance judgments and themeasurement of retrieval eﬀectiveness. In Proceedings of
ACM SIGIR ’98, pages 315–323, 1998.
[19] E. M. Voorhees. The philosophy of information retrieval
evaluation. In Revised Papers from the Second Workshop of
CLEF (Lecture Notes in Computer Science 2406), pages
355–370, 2001.
[20] E. M. Voorhees. Overview of the TREC 2003 robust
retrieval track. In The Twelfth Text REtrieval Conference(TREC 2003), 2004.
[21] E. M. Voorhees. Overview of the TREC 2004 robust
retrieval track. In The Thirteenth Text REtrieval
Conference (TREC 2004), 2005.
[22] S. Wu and F. Crestani. Methods for ranking information
retrieval systems without relevance judgements. In
Proceedings of the 2003 ACM Symposium on Applied
Computing, pages 811–816, 2003.
[23] E. Yilmaz, J. A. Aslam, and S. Robertson. A new rankcorrelation coeﬃcient for information retrieval. In
Proceedings of ACM SIGIR 2008, pages 587–594, 2008.

― 33 ―