SixEVALUATION

Introduction

Much effort and research has gone into solving the problem of
evaluation of information retrieval systems. However, it is probably fairto say that most people active in the field of information storage andretrieval still feel that the problem is far from solved. One may get an
idea of the extent of the effort by looking at the numerous survey
articles that have been published on the topic (see the regular chapter inthe Annual Review on evaluation). Nevertheless, new approaches toevaluation are constantly being published (e.g. Cooper1; Jardine and
Van Rijsbergen2 ; Heine3).
In a book of this nature it will be impossible to cover all work todate about evaluation. Instead I shall attempt to explicate theconventional, most commonly used method of evaluation, followed bya survey of the more promising attempts to improve on the older
methods of evaluation.
To put the problem of evaluation in perspective let me pose threequestions: (l)W hy evaluate? (2) What to evaluate? (3) How toevaluate? The answers to these questions pretty well cover the whole
field of evaluation. There is much controversy about each and although
I do not wish to add to the controversy I shall attempt an answer toeach one in turn.
The answer to the first question is mainly a social and economic one.
The social part is fairly intangible, but mainly relates to the desire to
put a measure on the benefits (or disadvantages) to be got frominformation retrieval systems. I use ‘benefit’ here in a much wider sensethan just the benefit accruing due to acquisition of relevant documents.
For example, what benefit will users obtain (or what harm will bedone) by replacing the traditional sources of information by a fully95

EVALUATION

automatic and interactive retrieval system? Studies to gauge this aregoing on but results are hard to interpret. For some kinds of retrieval
systems the benefit may be more easily measured than for others(compare statute or case law retrieval with document retrieval). The
economic answer amounts to a statement of how much it is going tocost you to use one of these systems, and coupled with this is thequestion ‘is it worth it?’. Even a simple statement of cost is difficult to
make. The computer costs may be easy to estimate, but the costs interms of personal effort are much harder to ascertain. Then, whether it
is worth it or not depends on the individual user.
It should be apparent now that in evaluating an information retrieval
system we are mainly concerned with providing data so that users canmake a decision as to (1) whether they want such a system (social
question) and (2) whether it will be worth it. Furthermore, thesemethods of evaluation are used in a comparative way to measure
whether certain changes will lead to an improvement in performance. In
other words, when a claim is made for say a particular search strategy,
the yardstick of evaluation can be applied to determine whether theclaim is a valid one.
The second question (what to evaluate?) boils down to what can wemeasure that will reflect the ability of the system to satisfy the user.
Since this book is mainly concerned with automatic document retrieval
systems I shall answer it in this context. In fact, as.early as 1966,
Cleverdon gave an answer to this. He listed six main measurable
quantities:(1) the coverage of the collection, that is, the extent to which thesystem includes relevant matter;(2) the time lag, that is, the average interval between the time thesearch request is made and the time an answer is given;(3) the form of presentation of the output;(4) the effort involved on the part of the user in obtaining answers
to his search requests;(5) the recall of the system, that is, the proportion of relevantmaterial actually retrieved in answer to a search request;(6) the precision of the system, that is, the proportion of retrieved
material that is actually relevant.
It is claimed that (l)-(4 ) are readily assessed. It is recall and precision
which attempt to measure what is now known as the effectiveness of
the retrieval system. In other words it is a measure of the ability of thesystem to retrieve relevant documents while at the same time holdingback non-relevant ones. It is assumed that the more effective the system
the more it will satisfy the user. It is also assumed that precision andrecall are sufficient for the measurement of effectiveness.
96

EVALUATION

There has been much debate in the past as to whether precision andrecall are in fact the appropriate quantities to use as measures ofeffectiveness. A popular alternative has been recall and fall-out (theproportion of non-relevant documents retrieved). However, all thealternatives still require the determination of relevance in some way.
The relationship between the various measures and their dependence on
relevance will be made more explicit later. Later in the chapter a theoryof evaluation is presented based on precision and recall. The advantagesof basing it on precision and recall are that they are:(1) the most commonly used pair;(2) fairly well understood quantities.
The final question (How to evaluate?) has a largely technical answer.
In fact, most of the remainder of this chapter may be said to beconcerned with this. It is interesting to note that the technique of
measuring retrieval effectiveness has been largely influenced by theparticular retrieval strategy adopted and the form of its output. For
example, when the output is a ranking of documents an obvious
parameter such as rank position is immediately available for control.
Using the rank position as cut-off, a series of precision recall values
could then be calculated, one pair for each cut-off value. The results
could then be summarised in the form of a set of points joined by asmooth curve. The path along the curve would then have the immediate
interpretation of varying effectiveness with the cut-off value.
Unfortunately the kind of question this form of evaluation does not
answer is, for example, how many queries did better than average andhow many did worse? Nevertheless, we shall need to spend more time
explaining this approach to the measurement of effectiveness since it is
the most common approach and needs to be understood.
Before proceeding to the technical details relating to themeasurement of effectiveness it is as well to examine more closely theconcept of relevance which underlies it.

Relevance
Relevance is a subjective notion. Different users may differ about therelevance or non-relevance of particular documents to given questions.
However, the difference is not large enough to invalidate experiments
which have been made with document collections for which test
questions with corresponding relevance assessments are available. These
questions are usually elicited from bona fide users, that is, users in aparticular discipline who have an information need. The relevanceassessments are made by a panel of experts in that discipline. So we
97

EVALUATION

now have the situation where a number of questions exist for which the‘correct’ responses are known. It is a general assumption in the field of
IR that should a retrieval strategy fare well under a large number ofexperimental conditions then it is likely to perform well in an
operational situation where relevance is not known in advance.
There is a concept of relevance which can be said to be objective andwhich deserves mention as an interesting source of speculation. This
notion of relevance has been explicated by Cooper4 . It is properly
termed ‘logical relevance’. Its usefulness in present day retrieval systems
is limited. However, it can be shown to be of some importance when it
is related to the development of question-answering systems, such as
the one recently designed by T. Winograd at Massachusetts Institute ofTechnology.
Logical relevance is most easily explicated if the questions are
restricted to the yes-no type. This restriction may be lifted — for
details see Cooper’s original paper. Relevance is defined in terms oflogical consequence. To make this possible a question is represented bya set of sentences. In the case of a yes-no question it is represented by
two formal statements of the form ‘p ’ and ‘not-p’. For example, if thequery were ‘Is hydrogen a halogen element?’, the pair of statements
would be the formal language equivalent of ‘Hydrogen is a halogen
element’ and ‘Hydrogen is not a halogen element’. More complicatedquestions of the ‘which’ and ‘whether’ type can be transformed in thismanner, for details the reader is referred to Belnap5. If the twostatements representing the question are termed component statements
then the subset of the set of stored sentences is a premiss set for acomponent statement if and only if the component statement is alogical consequence of that subset. (Note we are now temporarily
talking about stored sentences rather than stored documents.) A
minimal premiss set for a component statement is one that is as small as
possible in the sense that if any of its members were deleted, thecomponent statement would no longer be a logical consequence of theresulting set. Logical relevance is now defined as a two-place relation
between stored sentences and information need representations (that is,
the question represented as component statements). The final
definition is as follows:
A stored sentence is logically relevant to (a representationof) an information need if and only if it is a member ofsome minimal premiss set of stored sentences for somecomponent statement of that need.
Although logical relevance is initially only defined between sentences it
can easily be extended to apply to stored documents. A document is98

EVALUATION

relevant to an information need if and only if it contains at least one
sentence which is relevant to that need.
Earlier on I stated that this notion of relevance was only of limited
use at the moment. The main reason for this is that the kind of system
which would be required to implement a retrieval strategy which would
retrieve only the logically relevant documents has not been built yet.
However, the components of such a system do exist to a certain extent.
Firstly, theorem provers, which can prove theorems within formal
languages such as the first-order predicate calculus, have reached quite alevel of sophistication now (see, for example, Chang and Lee6).
Secondly, Winograd’s system is capable of answering questions about its
simple universe of blocks in natural language. In principle this system
could be extended to construct a universe of documents, that is, thecontent of a document is analysed and incorporated into the universeof currently ‘understood’ documents. It may be that the scale of asystem of this kind will be too large for present day computers; only
the future will tell.

Precision and recall, and others

We now leave the speculations about relevance and return to thepromised detailed discussion of the measurement of effectiveness.
Relevance will once again be assumed to have its broader meaning of‘aboutness’ and ‘appropriateness’, that is, a document is ultimately
determined to be relevant or not by the user. Effectiveness is purely ameasure of the ability of the system to satisfy the user in terms of therelevance of documents retrieved. Initially, I shall concentrate on
measuring effectiveness by precision and recall; a similar analysis could
be given for any pair of equivalent measures.
It is helpful at this point to introduce the famous ‘contingency’ table
which is not really a contingency table at all.
R ELEVA NTN O N -RELEVA NT

RETRIEVEDA Ci BA CiB

BNOT RETRIEVED

a ns

A ns

B

A

A

N

(N = number of documents in the system)99

EVALUATION

A large number of measures of effectiveness can be derived from thistable. To list but a few:
PRECISION =RECALL\a n b \151\A OB|HI
IA n s |FALLO U T

HI(| . | is the counting measure)
There is a functional relationship between all three involving aparameter called generality (G) which is a measure of the density of
relevant documents in the collection. The relationship is:
R xG(R x G ) + F ( l - G )

where

G=

HI
N

For each request submitted to a retrieval system one of these tables
can be constructed. Based on each one of these tables a precision-recall

Figure 6.1. The precision-recall curves for two queries. The ordinals indicate thevalues o f the control parameter A.

100

EVALUATION

value can be calculated. If the output of the retrieval strategy depends
on a parameter, such as rank position or co-ordination level (the ,number of terms a query has in common with a document), it can bevaried to give a different table for each value of the parameter andhence a different precision-recall value. If X is the parameter, then P \denotes precision, R \ recall, and a precision-recall value will bedenoted by the ordered pair (Rx, P\)- The set of ordered pairs makes
up the precision-recall graph. Geometrically when the points have been
joined up in some way they make up the precision-recall curve. The
performance of each request is usually given by a precision-recall curve(see Figure 6.1). To measure the overall performance of a system, theset of curves, one for each request, is combined in some way to produce
an average curve.

Averaging techniques
The method of pooling or averaging of the individual P-R curves seems
to have depended largely on the retrieval strategy employed. Whenretrieval is done by co-ordination level, micro-evaluation is adopted. If
S is the set of requests then:tfl = £ \AS|seS

where A s is the set of documents relevant to request s. If X is theco-ordination level then:
m

= I

lbj

seS

where
is the set of documents retrieved at or above theco-ordination level X. The points (R \, Px) are now calculated asfollows:
R x= IseS\As nBxs\\A \p _ y \AS FBxs\
X

seS

LBAI

Figure 6.2 shows graphically what happens when two individual P-R
curves are combined in this way. The raw data are given in Table 6.1.
An alternative approach to averaging is macro-evaluation which canbe independent of any parameter such as co-ordination level. The
average curve is obtained by specifying a ietofstandard recall values

101

EVALUATION

0.1

0.2 0.3

0.4

0.5 0.6 0.7 0.8

0.9

1.0

R ecal I
Figure 6.2. An example o f ‘averaging’ in micro-evaluation

TABLE 6.1. THE RAW DATA FOR THE MICRO-EVALUATION IN FIGURE 6.2

QUERY 2 :

R

0.1

0.2

0.4

0.6

0.8

P

1.0

0.8

0.6

0.4

0.3

R

0.1

0.3

0.5

0.7

0.9

P

0.8

0.6

0.5

0.4

0.4

X

15m 1

W in fix il

lfiX2l

W2n 5 X2l

1
2
3
4
5

10
25
66
150
266

10
20
40
60
80

10
40
80
140
180

8
24
40
56
72

102

A , = 100II00o

QUERY 1 :

P\
0.1
0.24
0.44
0.64
0.84

0.9
0.68
0.55
0.40
0.34

EVALUATION

for which average precision values are calculated by averaging over all
queries the individual precision values corresponding to the standard
recall values. Often no unique precision value corresponds exactly so it
becomes necessary to interpolate.

Interpolation
Many interpolation techniques have been suggested in the literature.
See, for example, Keen7.

>4

C

R2

T

0

R3

Ri

Figure 6.3. The right hand figure is the result o f interpolating between the points
A, B, C, D in the left hand figure

Figure 6.3 shows a typical P-R graph for a single query. The points^,
B, C and D, I shall call the observed points, since these are the only
points observed directly during an experiment the others may beinferred from these. Thus given that A = ( R 1, P l ) has been observed,
then the next point B is the one corresponding to an increase in recall,which follows from a unit increase in the number of relevant
documents retrieved. Between any two observed points the recall
remains constant, since no more relevant documents are retrieved.
It is an experimental fact that average precision-recall graphs aremonotonically decreasing. Consistent with this, a linear interpolation
estimates the best possible performance between any two adjacentobserved points. To avoid inflating the experimental results it isprobably better to perform a more conservative interpolation as
follows.
Let (Rx, P\ ) be the set of precision-recall values obtained byvarying some parameter X. To obtain the set of observed points we
specify a subset of the parameters X. Thus (Re, Pe) is an observed point
103

EVALUATION

if 6 corresponds to a value of X at which an increase in recall is
produced. We now have:
Gs = {{Res, Pes)}
the set of observed points for requests. To interpolate between any two
points we define:
PS(R) = {sup P : R ' > R s.t. (R \ P) e Gs}
where R is a standard recall value. From this we obtain the average
precision value at the standard recall value R by:
V Ps(R)
Jrs ISIThe set of observed points is such that the interpolated function ismonotonically decreasing. Figure 6.3 shows the effect of theinterpolation procedure, essentially it turns the P-R curve into a
step-function with the jumps at the observed points. A necessaryconsequence of its monotonicity is that the average P -R curve will also
be monotonically decreasing. It is possible to define the set of observed
points in such a way that the interpolated function is not
monotonically decreasing. In practice, even for this case, we have thatthe average precision-recall curve is monotonically decreasing.
In Figure 6.4 we illustrate the interpolation and averaging process.
P(R) =

P

-o
x

C
o
0o>

'in

X

riZ

-----o
X

X

—o

/?,

/?3
/?5
R
RecallFigure 6.4. An example o f macro-evaluation. The points indicated by crosses lie
midway between the two enclosing horizontal bars and their abscissae are given by
the standard recall values Rj

104

/?2

EVALUATION

Composite measures
Dissatisfaction in the past with methods of measuring effectiveness by apair of numbers (e.g. precision and recall) which may co-vary in aloosely specified way has led to attempts to invent composite measures.
These are still based on the ‘contingency’ table but combine parts of it
into a single number measure. Unfortunately many of these measures
are rather ad hoc and cannot be justified in any rational way. The
simplest example of this kind of measure is the sum of precision andrecall.
S = P +R
This is simply related to a measure suggested by Borko.
B K = P +R - 1
More complicated ones are^ =R + F-2RF
V= 1 -^F = Fallout)

1-3

Vickery’s measure V can be shown to be a special case of a generalmeasure which will be derived below.
Some single-number measures have derivations which can be justified
in a rational manner. Some of them will be given individual attention
later on. Suffice it here to point out that it is the model underlying thederivation of these measures that is important.
The Swets model
As early as 1963 Swets8 expressed dissatisfaction with existing methodsof measuring retrieval effectiveness. His background in signal detection
led him to formulate an evaluation model based on statistical decision
theory. In 1967 he evaluated some fifty different retrieval methods
from the point of view of his model9. The results of his evaluation wereencouraging but not conclusive. Subsequently, Brookes10 suggested
some reasonable modifications to Swets’ measure of effectiveness, andRobertson11 showed that the suggested modifications were in fact
simply related to an alternative measure already suggested by Swets. It
is interesting that although the Swets model is theoretically attractive
105

EVALUATION

and links IR measurements to a ready made and well-developed
statistical theory, it has not found general acceptance amongst workers
in the field.
Before proceeding to an explanation of the Swets model, it is as wellto quote in full the conditions that the desired measure of effectivenessis designed to meet. At the beginning of his 1967 report Swets states:‘A desirable measure of retrieval performance would have thefollowing properties. First, it would express solely the ability of a
retrieval system to distinguish between wanted and unwanted items —that is, it would be a measure of “effectiveness” only, leaving forseparate consideration factors related to cost or “efficiency” . Second,the desired measure would not be confounded by the relative
willingness of the system to emit items — it would express
discrimination power independent of any “acceptance criterion”
employed, whether the criterion is characteristic of the system or
adjusted by the user. Third, the measure would be a single number —inpreference, for example, to a pair of numbers which may co-vary in aloosely specified way, or a curve representing a table of several pairs of
numbers — so that it could be transmitted simply and immediately
apprehended. Fourth, and finally, the measure would allow complete
ordering of different performances, indicate the amount of difference
separating any two performances, and assess the performance of any
one system in absolute terms —that is, the metric would be a scale witha unit, a true zero, and a maximum value. Given a measure with theseproperties, we could be confident of having a pure and valid index of
how well a retrieval system (or method) were performing the function
it was primarily designed to accomplish, and we could reasonably ask
questions of the form “Shall we pay X dollars for Y units ofeffectiveness” . ’
He then goes on to claim that ‘The measure I proposed [in 1963],
one drawn from statistical decision theory, has the potential [myitalics] to satisfy all four desiderata’. So, what is this measure?
To arrive at the measure, we must first discuss the underlying model.
Swets defines the basic variables Precision, Recall, and Fallout inprobabilistic terms.
Recall= an estimate of the conditional probability that an item
will be retrieved given that it is relevant [we denote thisP(B/A) ] .
Precision = an estimate of the conditional probability that an item
will be relevant given that it is retrieved [i.e. P (A /B )\.
Fallout = an estimate of the conditional probability that an item
will be retrieved given that it is non-relevant[i *.P(B/A)\.
106

EVALUATIONHe accepts the validity of measuring the effectiveness of retrieval by acurve either precision-recall or recall-fallout generated by the variationof some control variable X (e.g. co-ordination level). He seeks tocharacterise each curve by a single number. He rejects precision-recall
in favour of recall-fallout since he is unable to do it for the former but
achieves limited success with the latter.
In the simplest case we assume that the variable A is distributed
normally on the set of relevant and non-relevant documents. The two
distributions are given respectively by 7V(jui, a L) and N(ji 2 , o2). The
density functions are given by /) (Af4) and / 2(A(4). We may picture the
distribution as shown in Figure 6.5.

Figure 6.5. Two normal distributions for X, one, N (pl , o j , on the set o f relevant
documents A with density o f
The other, N(ut , o j , on the set o f nonrelevant documents A with density f 2(X\A). The size o f the areas shaded in a N-W
and N—E direction represents recall and fallout respectively.

The usual set-up in IR is now to define a decision rule in terms of A,
to determine which documents are retrieved (the acceptance criterion).
In other words we specify Ac such that a document for which theassociated A exceeds Ac is retrieved. We now measure the effectivenessof a retrieval strategy by measuring some appropriate variables (such as
R and P, or R and F) at various values of Ac . It turns out that thedifferently shaded areas under the curves in Figure 6.5 correspond torecall and fallout. Moreover, we find the operating characteristic (OC)traced out by the point (Fx , R \ ) due to variation in Ac is a smooth
curve fully determined by two points, in the general case of unequalvariance, and by one point in the special case of equal variance. To see
this one only needs to plot the (Fx, R x) points on double probability
paper (scaled linearly for the normal deviate) to find that the points lie
on a straight line. A slope of 45° corresponds to equal variance, and107

EVALUATION

Figure 6.6. The two OC’s are ST and UV. Swets recommends using the distances
y/2 0 I and sJlOI' to compare their effectiveness. Brookes suggests using thenormal distances 01 and ON instead. (Adapted from Brookes'°, page 51 jotherwise the slope is given by the ratio ofand a2 ■Figure 6.6 shows
the two cases. Swets now suggests, regardless of slope, that the distance
01 (actually \/20I) be used as a measure of effectiveness. This amounts
to using:
51

M2 ~ Mih{oi + a 2)

which is simply the difference between the means of the distribution
normalised by the average standard deviation. Unfortunately thismeasure does rather hide the fact that a high 51 value may be due to asteep slope. The slope, and 51, would have to be given which fails tomeet Swets’ second condition. We, also, still have the problem ofdeciding between two strategies whose OC’s intersect and hence havedifferent 51 values and slopes.
Brookes10 in an attempt to correct for the 51 bias towards systems
with slopes much greater than unity suggested a modification to 51.
Mathematically Brookes’s measure is:
52 =
108

M2 +JUi(o\+ olf

EVALUATION

Brookes also gives statistical reasons for preferring 52 to 51 which neednot concern us here. Geometrically 52 is the perpendicular distancefrom 0 to OC (see Figure 6.6).
Interestingly enough Robertson11 showed that 52 is simply related
to the area under the Recall-Fallout curve. In fact the area is a strictlyincreasing function of 52. It also has the appealing interpretation that it
is equal to the percentage of correct choices a strategy will make whenattempting to select from a pair of items, one drawn at random fromthe non-relevant set and one drawn from the relevant set. It does seem
therefore that 52 goes a long way to meeting the requirements laid
down by Swets. However, the appropriateness of the model isquestionable on a number of grounds. Firstly, the linearity of the OC
curve does not necessarily imply that X is normally distributed in both
populations, although they will be ‘similarly’ distributed. Secondly, X is
assumed to be continuous which certainly is not the case for the data
checked out both by Swets and Brookes, in which the co-ordinationlevel used assumed only integer values. Thirdly, there is no evidence tosuggest that in the case of more sophisticated matching functions, as
used by the SMART system, that the distributions will be similarly
distributed let alone normally. Finally the choice of fallout rather than
precision as second variable is hard to justify. The reason is that the
proportion of non-relevant retrieved for large systems is going to behavemuch like the ratio of ‘non-relevant’ retrieved to ‘total documents insystem’. For comparative purposes ‘total document, may be ignored
leaving us with ‘non-relevant retrieved’ which is complementary to‘relevant retrieved’. But now we may as well use precision instead of
fallout.

The Cooper model —expected search length
In 1968, Cooper12 stated: ‘The primary function of a retrieval system isconceived to be that of saving its users to as great an extent as ispossible, the labour of perusing and discarding irrelevant documents, intheir search for relevant ones’. It is this ‘saving’ which is measured andis claimed to be the single index of merit for retrieval systems. In
general the index is applicable to retrieval systems with ordered (orranked) output. It roughly measures the wanted search effort which
one would expect to save by using the retrieval system as opposed tosearching the collection at random. An attempt is made to take into
account the varying difficulty of finding relevant documents fordifferent queries. The index is calculated for a query of a precisely
109

EVALUATION

specified type. It is assumed that users are able to quantify theirinformation need according to one of the following types:(1) only one relevant document is wanted;(2) some arbitrary number n is wanted;(3) all relevant documents are wanted;(4) a given proportion of the relevant documents is wanted, etc.
Thus, the index is a measure of performance for a query of given type.
Here we shall restrict ourselves to Type 2 queries. For further details
the reader is referred to Cooper12.
The output of a search strategy is assumed to be a weak ordering of
documents. I have defined this concept on page 118 in adifferent context. We start by first considering a special case, namely asimple ordering, which is a weak ordering such that for any two distinct
elements ei and e2 it is never the case that e{ R e2 and e2 R et(where R is the order relation). This simply means that all the
documents in the output are ordered linearly with no two or more
documents at the same level of the ordering. The search length is now
defined as the number of non-relevant documents a user must scan
before his information need (in terms of the type quantification above)is satisfied. For example, consider a ranking of 20 documents in which
the relevant ones are distributed as in Figure 6 .7. A Type 2 query withn = 2 would have search length 2, with n = 6 it would have searchlength 3.
R ank

1

2

3

R e le v a n c e

N

Y

N

U

Y

5
Y

6
Y

7

8

9

10

11

12

13

U

15

16

17

18

19

20

Y

N

Y

N

N

N

Y

N

Y

N

N

N

N

N

Figure 6.7. An example o f a simple ordering, that is, the ranks are unique, for 20
retrieval documents. Y indicates relevant and N indicates not relevant

Unfortunately the ranking generated by a matching function israrely a simple ordering, but more commonly a weak ordering. Thismeans that at any given level in the ranking, there is at least one
document (probably more) which makes the search length
inappropriate since the order of documents within a level is random. If
the information need is met at a certain level in the ordering thendepending on the arrangement of the relevant documents within thatlevel we shall get different search lengths. Nevertheless we can use ananalogous quantity which is the expected search length. For this weneed to calculate the probability of each possible search length byjuggling (mentally) the relevant and non-relevant documents in the levelat which the user need is met. For example, consider the weak ordering
110

EVALUATIONR ank
R e le v a n c e

N

1

1

2

2

2

2

2

3

3

3

3

3

4

4

4

4

4

4

4

N

Y

Y

N

Y

Y

Y

N

Y

Y

N

N

N

N

N

N

N

Y

N

Figure 6.8. An example o f a weak ordering, that is, with ties in the ranks, for 20
retrieval documents

in Figure 6.8. If the query is of Type 2 with n = 6 then the need is met
at level 3. The possible search lengths are 3,4 , 5 or 6 depending on how
many non-relevant documents precede the sixth relevant document. We
can ignore the possible arrangements within levels 1 and 2; theircontributions are always the same. To compute the expected searchlength we need the probability of each possible search length. We get at
this by considering first the number of different ways in which two
relevant documents could be distributed among five, it is ( |) = 10. Of
these 4 would result in a search length of 3, 3 in a search length of 4, 2
in a search length of 5 and 1 in a search length of 6. Theircorresponding probabilities are therefore, 4/10, 3/10, 2/10 and 1/10.
The expected search length is now:
(4/10). 3 + (3/10). 4 + (2/10) . 5 + (1/10). 6 = 4
The above procedure leads immediately to a convenient ‘intuitive’
derivation of a formula for the expected search length. It seems
plausible that the average results of many random searches through thefinal level (level at which need is met) will be the same as for a single
search with the relevant documents spaced ‘evenly’ throughout thatlevel. First we enumerate the variables:(a) q is the query of given type;(b) / is the total number of documents non-relevant to q in all levels
preceding the final;(c) r is the number of relevant documents in the final level;(d) i is the number of non-relevant documents in the final level;(e) s is the number of relevant documents required from the final
level to satisfy the need according its type.
Now, to distribute the r relevant documents evenly among the
non-relevant documents, we partition the non-relevant documents intor + 1 subsets each containing i/(r + 1) documents. The expected searchlength is now:E S L fa )= 7 + ^111

EVALUATIONAs a measure of effectiveness ESL is sufficient if the document
collection and test queries are fixed. In that case the overall measure is
the mean expected search length
ESL =

I

ESLfa)

ly l qeQ

where Q is the set of queries. This statistic is chosen in preference toany other for the property that it is minimised when the total expected
search length£
ESL fa) is minimised.
qeQ
To extend the applicability of the measure to deal with varying test
queries and document collections, we need to normalise the ESL insome way to counter the bias introduced because:(1) queries are satisfied by different numbers of documents
according to the type of the query and therefore can be
expected to have widely differing search lengths;(2) the density of relevant documents for a query in one document
collection may be significantly different from the density inanother.
The first item suggests that the ESL per desired relevant document isreally what is wanted as an index of merit. The second suggests
normalising the ESL by a factor proportional to the expected numberof non-relevant documents collected for each relevant one. Luckily itturns out that the correction for variation in test queries and forvariation in document collection can be made by comparing the ESL
with the expected random search length (ERSL). This latter quantity
can be arrived at by calculating the expected search length when theentire document collection is retrieved at one level. The final measure is
therefore:
ERSLfa) - ESLfa)
ERSLfa)which has been called the expected search length reduction factor by
Cooper. Roughly it measures improvement over random retrieval. The
explicit form for ERSL is given by:, N S .I
ERSLfa)112

EVALUATION

where(1) R is the total number of documents in the collection relevant to<7;(2) I is the total number of documents in .the collection
non-relevant to q;(3) S is the total desired number of documents relevant to q.
The explicit form for ESL was given before. Finally, the overallmeasure for a set of queries Q is defined, consistent with the mean ESL,
to be:E R SL -E S L
ERSLwhich is known as the mean expected search length reduction factor.
Within the framework as stated at the head of this section this final
measure meets the bill admirably. However, its acceptability as ameasure of effectiveness is still debatable (see, for example, Senko13). It
totally ignores the recall aspect of retrieval, unless queries are evaluatedwhich express the need for a certain proportion of the relevant
documents in the system. It therefore seems to be a good substitute for
precision, one which takes into account order of retrieval and user need.
For a further defence of its subjective nature see Cooper1.

Hie SMART measures
In 1966, Rocchio gave a derivation of two overall indices of merit basedon recall and precision. They were proposed for the evaluation of
retrieval systems which ranked documents, and were designed to be
independent of cut-off.
The first of these indices is normalised recall. It roughly measuresthe effectiveness of the ranking in relation to the best possible andworst possible ranking. The situation is illustrated in Figure 6.9 for 25
documents where we plot recall on the y-axis and the ranks on thex-axis. Normalised recall (Rn0rm ) is the area between the actual caseand the worst as a proportion of the area between the best and theworst. If n is the number of relevant documents, and rt the rank at
which the ith document is retrieved, then the area between the best andactual case can be shown to be (after a bit of algebra):nn
I r , - ! /A b —A a = — — ' 1(see Salton14, page 285)
113

EVALUATION

Best

1.0

_ 0.8

S
Q6
0)

*

0.4

02

A ctualii ___ Iri Worst

1

10

15

20

25

Ranks
Figure 6.9. An illustration o f how the normalised recall curve is bounded by thebest and worst cases. (Adapted from Robertson'5, page 99)

A convenient explicit form of normalised recall is:
R norm- 2;n(N—n)

where TV is the number of documents in the system and TV- n the area
between the best and the worst case (to see this substitute r,- = TV- i + 1
in the formula for A b - A a ). The form ensures that R norm lies between
0 (for the worst case) and 1 (for the best case).
In an analogous manner normalised precision is worked out. In
Figure 6.10 we once more have three curves showing (1) the best case,(2) the actual case, and (3) the worst case in terms of the precision
values at different rank positions.

Figure 6.10. An illustration o f how the normalised precision curve is bounded by
the best and worst cases. (Adapted from Robertson'5, page 100)

114

EVALUATIONThe calculation of the areas is a bit more messy but simple to do (seeSalton14, page 298). The area between the actual and best case is now
given by:nn

A h ~ A a = £ logrt - £ lo g i
1=1
r=i
The log function appears as a result of approximating S I /r by its
continuous analogue / I jrdr, which is iogr + constant.
The area between the worst and best case is obtained in the same
way as before using the same substitution, and is:iNll0g( N ~ n ) l nl
The explicit form, with appropriate normalisation, for normalised
precision is therefore:
S log rt — S log ii^(N-n)l n l)

Once again it varies between 0 (worst) and 1 (best).
A few comments about these measures are now in order. Firstly
their behaviour is consistent in the sense that if one of them is 0 (or 1)
then the other is 0 (or 1). In other words they both agree on the best
and worst performance. Secondly, they differ in the weights assigned toarbitrary positions of the precision-recall curve, and these weights may
differ considerably from those which the user feels are pertinent(Senko13). Or, as Salton14 (page 289) puts it: ‘the normalised precision
measure assigns a much larger weight to the initial (low) document
ranks than to the later ones, whereas the normalised recall measureassigns a uniform weight to all relevant documents’. Unfortunately theweighting is arbitrary and given. Thirdly, it can be shown that
normalised recall and precision have interpretations as approximations
to the average recall and precision values for all possible cut-off levels.
That is, if R(i) is the recall at rank position i, and P(i) the corresponding
precision value, then:R norm2

N

N £ RQ)
2NI

N i=i m115

EVALUATION

Fourthly, whereas Cooper has gone to some trouble to take account of
the random element introduced by ties in the matching function, it islargely ignored in the derivation of Pnonn and R norm.
One further comment of interest is that Robertson11 has shown that
normalised recall has an interpretation as the area under the
Recall-Fallout curve used by Swets.
Finally mention should be made of two similar but simpler measuresused by the SMART system. They are:n

I 1
Rank Recall = -----ni= 1

Z ln iLog Precision = ---------n
Z In rti=i

and do not take into account the collection size N, n is here the numberof relevant documents for the particular test query.

A normalised symmetric difference
Let us now return to basics and consider how it is that users could
simply measure retrieval effectiveness. We are considering the common
situation where a set of documents is retrieved in response to a query,the possible ordering of this set is ignored. Ideally the set should consist
only of documents relevant to the request, that is giving 100 per centprecision and 100 per cent recall (and by implication 0 per centfallout). In practice, however, this is rarely the case, and the retrieved
set consists of both relevant and non-relevant documents. The situation
may therefore be pictured as shown in Figure 6.11, where A is the setof relevant documents, B the set of retrieved documents, and A n B the
set of retrieved documents which are relevant.

Figure 6.11. An illustration o f the symmetric difference between two sets A and B.
A A B is the shaded area

116

EVALUATION

Now, an intuitive way of measuring the adequacy of the retrieved set
is to measure the size of the shaded area. Or to put it differently, tomeasure tcTwhat extent the two sets do not match. The area is in fact
the symmetric difference: A A B (or A V B —A C\ B). Since we are
more interested in the proportion (rather than absolute number) of
relevant and non-relevant documents retrieved we need to normalise
this measure. A simple normalisation gives:\ A AB\\A\ + \B\In terms of P and R we have:

which is a simple composite measure.
The preceding argument in itself is not sufficient to justify the use ofthis particular composite measure. However, I shall now introduce aframework within which a general measure may be derived whichamong others has E as one of its special cases.

Foundation*
Problems of measurement have arisen in physics, psychology, and more
recently, the social sciences. Clarification of these problems has beensought with the help of the theory o f measurement. I shall attempt todo the same for information retrieval. My purpose is to constmct aframework, based on the mathematical theory of measurement within
which measures of effectiveness for retrieval systems can be derived.
The basic mathematical notions underlying the measurement ideas will
be introduced, but for their deeper understanding the reader is referredto the excellent book by Krantz et al. 15 It would be fair to say that thetheory developed there is applied here. Also of interest are the books
by Ellis16 and Lieberman17.
The problems of measurement in information retrieval differ fromthose encountered in the physical sciences in one important aspect. In
the physical sciences there is usually an empirical ordering of thequantities we wish to measure. For example, we can establish
empirically by means of a scale which masses are equal, and which are* The next three sections are substantially the same as those appearing in mypaper: ‘Foundations of evaluation’, Journal o f Documentation, 30, 365-373
11974). They have been included with the kind permission bf'tKe~Mahaging Editor'o f Aslib.

117

EVALUATION

greater or less than others. Such a situation does not hold in
information retrieval. In the case of the measurement of effectivenessby precision and recall, there is no absolute sense in which one can saythat one particular pair of precision-recall values is better or worse thansome other pair, or, for that matter, that they are comparable at all.
However, to leave it at that is to admit defeat. There is no reason why
we cannot postulate a particular ordering, or, to put it more mildly,
why we cannot show that a certain model for the measurement ofeffectiveness has acceptable properties. The immediate consequence ofproceeding in this fashion is that each property ascribed to the model
may be challenged. The only defence one has against this is that:(1) all properties ascribed are consistent;(2) they bring out into the open all the assumptions made inmeasuring effectiveness;(3) each property has an acceptable interpretation;(4) the model leads to a plausible measure of effectiveness.
It is as well to point out here that it does not lead to a unique measure,but it does show that certain classes of measures can be regarded as
being equivalent.
The model
We start be examining the structure which it is reasonable to assume forthe measurement of effectiveness. Put in other words, we examine theconditions that the factors determining effectiveness can be expected tosatisfy. We limit the discussion here to two factors, namely precisionand recall, although this is no restriction, different factors could beanalysed, and, as will be indicated later, more than two factors can
simplify the analysis.
If (R is the set of possible recall values and (P is the set of possible
precision values then we are interested in the set <R x <P with a relation
on it. We shall refer to this as a relational structure and denote it<(R x <P, > > where > is the binary relation on <R x (P. (We shall use
the same symbol for less than or equal to, the context will make clear
what the domain is.) All we are saying here is that for any given point(R, P) we wish to be able to say whether it indicates more, less or equal
effectiveness than that indicated by some other point. The kind oforder relation is a weak order. To be more precise:
Definition 1. The relational structure < (R x ( P , > > is a weak order if
and only if for e , , e2, e3 e (R x <P the following axioms are satisfied.
(1) Connectedness: either> e2 or e2 > ex(2) Transitivity: if e x > e2 and e2 > e3 then e t > e3
118

EVALUATION

We insist that if two pairs can be ordered both ways then' ( R i , P i ) ~ (R2, P i ), i.e. equivalent not necessarily equal. The
transitivity condition is obviously desirable.
We now turn to a second condition which is commonly called
independence. This notion captures the idea that the two components
contribute their effects independently to the effectiveness.
Definition 2. A relation > on (R x (P is independent if and only if,
for R i , R 2 e<R, (Ri, P) > ( R2, P) for some P e P implies(R\, P ' ) > (R2, P )for every P' e
and for P i , P 2 e P ,(R, P i ) > (R, P2) for some R e <R implies (R P i ) > (R', P2) for every
R ’ e a.
' All we are saying here is, given that at a constant recall (precision)
we find a difference in effectiveness for two values of precision (recall)then this difference cannot be removed or reversed by changing theconstant value.
We now come to a condition which is not quite as obvious as thepreceding ones. To make it more meaningful I shall need to use adiagram, Figure 6.12, which represents the ordering we have got so far
with definitions 1 and 2. The lines
and l2 are lines of equal
effectiveness, that is any two points (R ,P ), (R' ,P' )el j are such that
(R, P) ~ (R', P') (where ~ indicates equal effectiveness). Now let us
assume that we have the points on f and l2 but wish to deduce the

Figure 6.12. A diagram illustrating the Thomsen condition

119

EVALUATION

relative ordering in between these two lines. One may think of this as
an interpolation procedure.
Definition 3 (Thomsen condition). For every R lt R 2, R 3 e <R and Pt ,P2, P 3 e <f\ (R u P i) ~ (R 3 , ^ 2) and ( R3, P t ) ~ (R2, P3) imply that(R uP ^-iR ^P ^.
Intuitively this can be reasoned as follows. The intervals R ] R 3 andP 2 P 3 are equivalent since an increase in the R-factor by R i R 3 and anincrease in the R-factor by P2 P 3 starting from ( R i , P2) lead to the same
effectiveness (points on l2). It therefore follows that a decrease in eachfactor starting from equal effectiveness, in this case the two points( R3, P i ) and (R 2 , P 3) on f , should lead to equal effectiveness.
The fourth condition is one concerned with the continuity of eachcomponent. It makes precise what intuitively we would expect when
considering the existence of intermediate values.
Definition 4 (Restricted Solvability). A relation > on fi x (P satisfies
restricted solvability provided that:(1) whenever R, R, R e (R and P, P' e (P for which(R , P>) > (R , P) > (R, P') then there exists R ' e (R s.t.
(R',P')~(R,Pf,(2) a similar condition holds on the second component.
In other words we are ensuring that the equation (R 1, P1) ~ (R, P) is
soluble for R ' provided that there exist R, R such that
(R, P ) > (R, P') > (R , P ). An assumption of continuity of the
precision and recall factors would ensure this.
The fifth condition is not limiting in any way but needs to be stated.
It requires, in a precise way, that each component is essential.
Definition 5. Component (R is essential if and only if there exist R t ,R 2 e <R and P{ e (P such that it is not the case that(R 1 , P i) ~ (R 2 ,P x). A similar definition holds for <P.
Thus we require that variation in one while leaving the otherconstant gives a variation in effectiveness.
Finally we need a technical condition which will not be explained
here, that is the Archimedean property for each component. It merely
ensures that the intervals on a component are comparable. For details
the reader is referred to Krantz et al.ls
We now have six conditions on the relational structure< <R x (P, > > which in the theory of measurement are necessary andsufficient conditions* for it to be an additive conjoint structure. This isenough for us to state the main representation theorem. It is a theorem* It can be shown that (starting at the other end) given an additively independent
representation the properties defined in 1 and 3, and the Archimedean property
are necessary. The structural conditions 4 and 5 are sufficient.

120

EVALUATION

asserting that if a given relational structure satisfies certain conditions(axioms), then a homomorphism into a numerical relational structure
can be constructed. A homomorphism into the real numbers is often
referred to as a scale. Measurement may therefore be regarded as theconstruction of homomorphisms from empirical relational structures ofinterest into numerical relational structures that are useful.
In our case we can therefore expect to find real-valued functions
on <R and d>2 on <P and a function F from R e x Re into Re, 1:1 in eachvariable, such that, for all R, R ' e (R and P;P' e <P we have:{R, P )> {R ', P’) o F & ^ R ) , d>2(i>)] > *■[*,(*'), d>2(P')](Note that although the same symbol > is used, the first is a binary
relation on (R x (P, the second is the usual one on Re, the set of reals.)
In other words there are numerical scales <!>,■ on the two components
and a rule F for combining them such that-the resultant measurepreserves the qualitative ordering of effectiveness. When such a
representation exists we say that the structure is decomposable. In thisrepresentation the components (<R and (P) contribute to theeffectiveness measure independently. It is not true that all relational
structures are decomposable. What is true, however, is that
non-decomposable structures are extremely difficult to analyse.
A further simplification of the measurement function may beachieved by requiring a special kind of non-interaction of thecomponents which has become known as additive independence. Thisrequires that the equation for decomposable structures is reduced to:(R, P) > (R', P') «■$!(/?) + <h2(P) > $ ,(R ') + <t>2(P')
where F is simply the addition function.
non-decomposable structure is given by:

An example of a

{R, P) > (R ’, P') o $ ,(R ) + <f>2(P) +$!(P)<I)2(P) > $ ,(/? ') ++ d>2(P')+d>,(P')d>2(P').
Here the term dq d>2 is referred to as the interaction term, its absenceaccounts for the non-interaction in the previous condition.
We are now in a position to state the main representation theorem.
TheoremSuppose < <R x(P, > > is an additive conjoint structure, then there
exist functions, d>! from (R, and d>2 from (P into the real numbers suchthat, for all R, R ' e <Rand P, Pf e <P:(R, P) > (R', P ') «• d>i(P)+d>2(P) >IR -9+ $ 2(P')

121

EVALUATION

If 4>/ are two other functions with the same property, then there exist
constants 0 > 0 , 7 !, and y 2 such that
4>i' = ©<!>! + 7 i$ 2' = 0<f>2 + 72

The proof of this theorem may be found in Krantz et al. 15
Let us stop and take stock of the situation. So far we have discussed
the properties of an additive conjoint structure and justified its use forthe measurement of effectiveness based on precision and recall. We havealso shown that an additively independent representation (unique up toa linear transformation) exists for this kind of relational structure. The
explicit form of tb,- has been left unspecified. To determine the form of
4>,- we need to introduce some extrinsic considerations. Although therepresentation theorem shows the existence of a numericalrepresentation F = <!>!+ <b2 , this is not the most convenient form forexpressing the further conditions we require of F, nor for its
interpretation. So, in spite of the fact that we are seeking an additively
independent representation we consider conditions on a general F. It
will turn out that the F which is appropriate can be simply transformed
into
anadditive
representation.
The
transformationisf(F) = — (F — l ) '1 which is strictly monotonically increasing in therange 0 < F < 1, which is the range of interest. In any case whenmeasuring retrieval effectiveness any strictly monotone transformationof the measure will do just as well.

Explicit measures o f effectivenessI shall now argue for a specific form of <b, and F, based on a model forthe user. In other words, the form <!>, and F are partly determined by
the user. We start by showing how the ordering on (R x (P in factinduces an ordering of intervals on each factor. From Figure 6.13 wehave that (R 3,P 1) > (R l t P2), (R3, P 2) > (R u P i) and (R l t P2)> (R i, P i). Therefore the increment (interval)P, P 3 is preferred to theincrement P\P 2. But (R2, P2) > (P 4, P i), which gives P1P2 ispreferred to R 2 R 4. Hence R 1 R 3 > i R 2 R ^ where >1 is the inducedorder relation on (R. We now have a method of comparing each intervalon (R with a fixed interval on <P.
Since we have assumed that effectiveness is determined by precisionand recall we have committed ourselves to the importance ofproportions of documents rather than absolute numbers. Consistent
with this is the assumption of decreasing marginal effectiveness. Let me
illustrate this with an example. Suppose the user is willing to sacrifice122

EVALUATION

Figure 6.13. The diagram shows the relative positions o f points with respect totwo contours

one unit of precision for an increase of one unit of recall, but will notsacrifice another unit of precision for a further unit increase in recall,i.e.
(R + 1, P - 1) > ( R ,P )but
(R + l ,P ) > ( R + 2 ,P ~ 1)
We conclude that the interval between R + 1 and R exceeds the interval
between P and P — 1 whereas the interval between R + 1 and R + 2 issmaller. Hence the marginal effectiveness of recall is decreasing. (Asimilar argument can be given for precision.) The implication of this forthe shape of the curves of equal effectiveness is that they are convex
towards the origin.
Finally, we incorporate into our measurement procedure the factthat users may attach different relative importance to precision andrecall. What we want is therefore a parameter (|3) to characterise themeasurement function in such a way that we can say: it measures theeffectiveness of retrieval with respect to a user who attaches 0 times asmuch importance to recall as precision. The simplest way I know ofquantifying this is to specify the P/R ratio at which the user is willingto trade an increment in precision for an equal loss in recall.
Definition 6 . The relative importance a user attaches to precision andrecall is the P/R ratio at which 'dE/'dR = dE/dP, where E = E(P, R ) is themeasure of effectiveness based on precision and recall.
123

EVALUATION

Can we find a function satisfying all these conditions? If so, can wealso interpret it in an intuitively simple way? The answer to both thesequestions is yes. It involves:« ( y + (1- a ) ^0< a < lThe scale functions are therefore, Tq (P) = a(l /P), and <h2 (R ) = (1 —a)(1 /R). The ‘combination’ function F is now chosen to satisfy
definition 6 without violating the additive independence. We get:F($,,T.2) = 1 -

1$1 +$2

We now have the effectiveness measure. In terms ofjPandi? it will be:

E 1

/ 1\

1

«{p ) + 0 -< * )r

To facilitate interpretation of the function, we transform according
to a = l/( 02 + 1), and find that dE/dR = dE/dP when P/R = 0. If A isthe set of relevant documents and B the set of retrieval documents,
then:\A F B \
I5|

and

R =

\A C \B |\A\

E now gives rise to the following special cases:(1) When a = 1/2 (0 = 1) E = \A A B\I(\A\ + \B\), a normalised
symmetric difference between sets A and B (A A B =A U B —A O B). It corresponds to a user who attaches equal
importance to precision and recall.
(2) E -> 1 —R when a -*■ 0 (0 -> °°), which corresponds to a user who
attaches no importance to precision.
(3) E -> 1 —P when a -»• 1(0 -» 0), which corresponds to a user who
attaches no importance to recall.
It is now a simple matter to show that certain other measures givenin the literature are special cases of the general form E. By the
representation theorem, the <h/s are uniquely determined up to a linear
transformation, that is, <!>'■ is defined by= 0 $ / + y ,• would serve
124

EVALUATION

equally well as scale functions. If we now set <l>i' = 2<S>1 - 1 / 2 ,<h2' = 2<h2 — 1/2, and j3 = 1 then we have:

which is the measure recommended by Heine3.
One final example is the measure suggested by Vickery in 1965
which was documented by Cleverdon et al.18 Here we set:

which is Vickery’s measure (apart from a scale factor of 100).
To summarise, we have shown that it is reasonable to assume that
effectiveness in terms of precision and recall determines an additive
conjoint structure. This guarantees the existence of an additively
independent representation. We then found the representation
satisfying some user requirements and also having special cases which
are simple to interpret.
The analysis is not limited to the two factors precision and recall, it
could equally well be carried out for say the pair fallout and recall.
Furthermore, it is not necessary to restrict the model to two factors. If
appropriate variables need to be incorporated the model readily extends
to n factors. In fact for more than two dimensions the Thomsen
condition is not required for the representation theorem.

Presentation of experimental results

In my discussion of micro-, macro-evaluation, and expected searchlength, various ways of averaging the effectiveness measure of the set of
queries arose in a natural way. I now want to examine the ways inwhich we can summarise our retrieval results when we have no a priori
reason to suspect that taking means is legitimate.
In this section the discussion will be restricted to single number
measures such as a normalised symmetric difference, normalised recall,etc. Let us use Z to denote any arbitrary measure. The test queries will
125

EVALUATION

be Qi and n in number. Our aim in all this is to make statements about
the relative merits of retrieval under different conditions a,b,c,. . . interms of the measure of effectiveness Z. The ‘conditions’ a,b,c,. . . may
be different search strategies, or information structures, etc. In otherwords we have the usual experimental set-up where we control avariable and measure how its change influences retrieval effectiveness.
For the moment we restrict these comparisons to one set of queries andthe same document collection.
The measurements we have therefore are (Za(Q1) ,Z a(Q2), ■■{Zb( Q i \ Z b{Q2\ .. .}, (Zc (Qt ) ,Z c (Q2),where Z x {Qf) is thevalue of Z when measuring the effectiveness of the response to Q{ undercondition x. If we now wish to make an overall comparison between
these sets of measurements we could take means and compare these.
Unfortunately the distributions of Z encountered are far frombell-shaped, or symmetric for that matter, so that the mean is not aparticularly good ‘average’ indicator. The problem of summarising IR
data has been a hurdle ever since the beginning of the subject. Becauseof the non-parametric nature of the data it is better not to quote asingle statistic but instead to show the variation in effectiveness byplotting graphs. Should it be necessary to quote ‘average’ results it isimportant that they are quoted alongside the distribution from which
they are derived.
There are a number of ways of representing sets o f Z-values
graphically. Probably the most obvious one is to use a scatter diagram,where the x-axis is scaled for Z a and the y-axis for Z b and each plotted
point is the pair (Za(Qi), Z ^Q ff). The number of points plotted will
equal the number of queries. If we now draw a line at 45° to the x-axis
from the origin we will be able to see what proportion of the queries
did better under condition a than under condition b. There are two
disadvantages to this method of representation: the comparison islimited to two conditions, and it is difficult to get an idea of the extent
to which two conditions differ.
A more convenient way of showing retrieval results of this kind is toplot them as cumulative frequency distributions, or as they are
frequently called by statisticians empirical distribution functions. Let{Z(Qi), Z(Q2) , . . Z(Q„)j be a set of retrieval results then theempirical distribution function F(z) is a function of z which equals the
proportion of Z(£?,)’s which are less than or equal to z. To plot thisfunction we divide the range of z into intervals. If we assume that0 < z < 1, then a convenient set of intervals is ten. The distributions
will take the general shape as shown in Figure 6.14. When the measure
Z is such that the smaller its value the more effective the retrieval, thenthe higher the curve the better. It is quite simple to read off the various
quantiles. For example to find the median we only need to find the126EVALUATION

Figure 6.14. Two cumulative frequency distributions showing the difference in
effectiveness under conditions a and b

z-value corresponding to 0.5 on the F(z) axis. In our diagrams they are
0.2 and 0.4 respectively for conditions a and b.
I have emphasised the measurement of effectiveness from the pointof view o f the user. If we now wish to compare retrieval on different
document collections with different sets of queries then we can still use
these measures to indicate which system satisfies the user more. On theother hand we cannot thereby establish which system is more effective
in its retrieval operations. It may be that in system A the sets ofrelevant documents constitute a smaller proportion of the total set of
documents than is the case in system B. In other words it is muchharder to find the relevant documents in system B than in system A.
So, any direct comparison must be weighted by the generality measure
which gives the number of relevant documents as a proportion-of thetotal number of documents. Alternatively one could use fallout whichmeasures the proportion of non-relevant documents retrieved. The
important point here is to be clear about whether we are measuring user
satisfaction or system effectiveness.

Significance tests
Once we have our retrieval effectiveness figures we may wish toestablish that the difference in effectiveness under two conditions isstatistically significant. It is precisely for this purpose that manystatistical tests have been designed. Unfortunately I have to agree withthe findings of the Comparative Systems Laboratory 19 in 1968, that
there are no known statistical tests applicable to IR. This may sound127

EVALUATION

like a counsel of defeat but let me hasten to add that it is possible toselect a test which violates only a few of the assumptions it makes. Twogood sources which spell out the pre-conditions for non-parametrictests are Siegel20 and Conover21.
Parametric tests are inappropriate because we do not know the formof the underlying distribution. In this class we must include the populart-test. The assumptions underlying its use are given in some detail bySiegel (page 19), needless to say most of these are not met by IR data.
One obvious failure is that the observations are not drawn fromnormally distributed populations.
On the face of it non-parametric tests might provide the answer.
There are some tests for dealing with the case of related samples. In our
experimental set-up we have one set of queries which is used indifferent retrieval environments. Therefore, without questioning
whether we have random samples, it is clear that the sample undercondition a is related to the sample under condition b. When in thissituation a common test to use has been the Wilcoxon Matched-Pairs
test. Unfortunately again some important assumptions are not met. The
test is done on the differences Df = Za (Q/) —Z b(Qj), but it is assumed
that Dj is continuous and that it is derived from a symmetric
distribution, neither of which is normally met in IR data.
It seems therefore that some of the more sophisticated statisticaltests are inappropriate. There is, however, one simple test which makes
very few assumptions and which can be used providing its limitations
are noted. This one is known in the literature as the sign test (Siegel20,
page 68 and Conover21, page 121). It is applicable in the case of related
samples. It makes no assumptions about the form of the underlying
distribution. It does, however, assume that the data are derived from acontinuous variable and that the Z(Qi) are statistically independent.
These two conditions are unlikely to be met in a retrieval experiment.
Nevertheless given that some of the conditions are not met it can beused conservatively.
The way it works is as follows. Let { Z a ( Q , ), Z a ( Q 2 ) , . .
{ Z b ( Q l ),Z b ( Q 2 ) • • •>} be our two sets of measurements under conditions a and b
respectively. Within each pair (Za (Q,), Z b { Q i ) ) a comparison is made,and each pair is classified as ' + ' if Za (Q,) > Z b ( Q i ) , asif
Z a ( Q j ) < Z b ( Q i ) or ‘tie’ if Z a ( Q , ) = Z a ( Q , ) . Pairs which are classified as‘tie’ are removed from the analysis thereby reducing the effective
number of measurements. The null hypothesis we wish to test is that:
P(Za > Z b)= P (Z a < Z b) = ±Under this hypothesis we expect the number of pairs which have
Z a > Z b to equal the number of pairs which have Z a < Z b. Another128

EVALUATION

way of stating this is that the two populations from which Z a andZfi
are derived have the same median.
In IR this test is usually used as a one-tailed test, that is, thealternative hypothesis prescribes the superiority of retrieval undercondition a over condition b, or vice versa. A table for small samplesn < 25 giving the probability under the null hypothesis for eachpossible combination of ‘+”s and”s may be found in Siegel20(page 250). To give the reader a feel for the values involved: in a sample
of 25 queries the null hypothesis will be rejected at the 5 per cent level
if there are at least 14 differences in the direction predicted by thealternative hypothesis.
The use of the sign test raises a number of interesting points. The
first of these is that unlike the Wilcoxon test it only assumes that the
Z ’s are measured on an ordinal scale, that is, the magnitude of\Za Z b | is not significant. This is a suitable feature since we areusually only seeking to find which strategy is better in an average senseand do not wish the result to be unduly influenced by excellent
retrieval performance on one query. The second point is that some careneeds to be taken when comparing Z a and Z b. Because our measure ofeffectiveness can be calculated to infinite precision we may be insisting
on a difference when in fact it only occurs in the tenth decimal place. It
is therefore important to decide beforehand at what value of e we will
equate Za a ndZ 6 when |Za - Z b\ < e.
Finally, although I have just explained the use of the sign test interms of single number measures it is also used to detect a significant
difference between precision-recall graphs. We now interpret the Z’s as
precision values at a set of standard recall values. Let this set be
SR ={0.1, 0.2, . . ., 1.0}, then corresponding to each Re SR we have apair (Pa (R), Pb(R)). The Pa’s and Pb s are now treated in the same way
as the Z a ’s and Z b s. Note that when doing the evaluation this way theprecision-recall values will have already been averaged over the set of
queries by one of the ways explained before.

Bibliographic remarks

Quite a number of references to the work on evaluation have alreadybeen given in the main body of the chapter. Nevertheless, there are stilla few important ones worth mentioning.
Buried in the report by Keen and Digger22 (Chapter 16) is an
excellent discussion of the desirable properties of any measure ofeffectiveness. It also gives a checklist indicating which measure satisfies
what. It is probably worth repeating here that Part I of Robertson’s
paper23 contains a discussion of measures of effectiveness based on the129EVALUATION‘contingency’ table as well as a list showing who used what measure in
their experiments. King and Bryant24 have written a book on theevaluation of information services and products emphasising thecommercial aspects. Goffman and Newill25 describe a methodology forevaluation in general.
A parameter which I have mentioned in passing but which deserves
closer study is generality. Salton26 has recently done a study of its
effect on precision and fallout for different sized document collections.
The trade-off between precision and recall has for a long time been
the subject of debate. Cleverdon27 who has always been involved in thisdebate has now restated his position. Heine28 in response to this has
attempted to further clarify the trade-off in terms of the Swets model.
The notion of relevance has at all times attracted much discussion.
An interesting early philosophical paper on the subject is by Weiler29.
Goffman30 has done an investigation of relevance in terms of Measure
Theory. And more recently Negoita31 has examined the notion in termsof different kinds of logics.
A short paper by Good32 which is in sympathy with the approachbased on a theory of measurement given here, discusses the evaluationof retrieval systems in terms of expected utility.
One conspicuous omission from this chapter is any discussion of
cost-effectiveness. The main reason for this is that so far very little ofimportance can be said about it. A couple of attempts to work out
mathematical cost models for IR are Cooper33 and Marschak34.

References
1. COOPER, W. S., ‘On selecting a measure of retrieval effectiveness’, Part 1:‘Tlie “subjective” philosophy of evaluation’, Part 2: ‘Implementation of thephilosophy’, Journal o f the American Society for Information Science, 24,
87-100 and 413-424 (1973)
2. JARD1NE, N. and VAN RIJSBERGEN, C. J., ‘The use o f hierarchic
clustering in information retrieval’, Information Storage and Retrieval, 7,
217-240(1971)
3. HEINE, M. H., ‘Distance between sets as an objective measure of retrieval
effectiveness’, Information Storage and Retrieval, 9, 181-198 (1973)
4. COOPER, W. S., ‘A definition of relevance for information retrieval’,
Information Storage and Retrieval, 7, 19-37 (1971)
5. BELNAP, N. P., An analysis of questions: Preliminary report, Scientific
Report TM-1287, SDC, Santa Monica, California (1963)
6. CHANG, C. L. and LEE, R. C. T., Symbolic Logic and Mechanical Theorem
Proving, Academic Press, New York (1973)
7. KEEN, E. M., ‘Evaluation parameters’. In Report ISR-13 to the National
Science Foundation, Section II, Cornell University, Department of Computer
Science (1967)
8. SWETS, J. A., ‘Information retrieval systems’, Science, 1 4 1 ,2 45-250(1963)

130

EVALUATION9.

SWETS, J. A., E ffe ctiv e n e s s o f I n fo r m a tio n R e trie v a l M e th o d s , Bolt, Beranek
and Newman, Cambridge, Massachusetts (1967)
10. BROOKES, B. C., ‘The measure of information retrieval effectivenessproposed by Swets’, J o u rn a l o f D o c u m e n ta tio n , 24, 41-54 (1968)
11. ROBERTSON, S. E., ‘The parametric description of retrieval tests, Part 2:‘Overall m easures J o u rn a l o f D o c u m e n ta tio n , 25 ,9 3 -1 0 7 (1969)
12. COOPER, W. S., ‘Expected search length: A single measure of retrieval
effectiveness based on weak ordering action of retrieval systems’, J o u rn a l o f
th e A m e ric a n S o c ie ty f o r In fo r m a tio n S cie n ce , 19, 30-41 (1968)
13. SENKO, M. E., Information storage and retrieval systems, I n : A d va n ces in
In f o r m a t io n System s S cie n ce , (Edited by J. Tou) Plenum Press, New York
(1969)
14. SALTON, G., A u t o m a t ic I n fo r m a tio n O rg a n iza tion and R e trie v a l,
McGraw-Hill, New York (1968)
15. KRANTZ, D. H„ LUCE, R. D., SUPPES, P. and TVERSKY, A ., F o u n d a tio n s
o f M e a su re m en t, Volume 1, A d d itiv e and P o ly n o m ia l R e p re s e n ta tio n ,Academic Press, London and New York (1971)
16. ELLIS, B., B asic C o n c e p ts o f M ea su re m en t, Cambridge University Press,
London (1966)
17. LIEBERMAN, B., C o n te m p o ra ry P ro b le m s in S ta tistics, Oxford University
Press, New York (1971)
18. CLEVERDON, C. W., MILLS, J. and KEEN, M., F a c to rs D e te r m in in g th e
P e rfo rm a n c e o f In d e x in g S ystem s, Volume I - D esign, Volume II - Test
R esu lts, ASLIB Cranfield Project, Cranfield (1966)
19. Comparative Systems Laboratory, A n In q u ir y in t o T estin g o f In fo r m a tio n
R e trie v a l S ystem s, 3 Volumes, Case-Western Reserve University (1968)
20. SIEGEL, S., N o n p a ra m e tric S ta tistics f o r th e B e h a v io u ra l Sciences,
McGraw-Hill, New York (1956)
21. CONOVER, W. J., P ra c tic a l N o n p a ra m e tric S ta tistics, Wiley, New York(1971)
22. KEEN, E. M. and DIGGER, J. A., R e p o r t o f an In fo r m a tio n S c ie n ce In d e x
Languages Test, Aberystwyth College of Librarianship, Wales (1972)
23. ROBERTSON, S. E., ‘The parametric description of retrieval tests’, Part I:‘The basic parameters J o u rn a l o f D o c u m e n ta tio n , 25, 1-27 (1969)
24. KING, D. W. and BRYANT, E. C., T h e E v a lu a tio n o f In fo r m a tio n S ervices
a n d P ro d u c ts , Information Resources Press, Washington (1971)
25. GOFFMAN, W. and NEWILL, V. A., ‘A methodology for test and evaluationof information retrieval systems’, I n fo r m a tio n S to ra g e and R e trie v a l, 3,19-25 (1966)
26. SALTON, G., ‘The “generality” effect and the retrieval evaluation for large
collections’, J o u rn a l o f th e A m e ric a n S o c ie ty f o r I n fo r m a tio n S cie n ce , 23,
11-22 (1972)
27. CLEVERDON, C. W., ‘On the inverse relationship of recall and precision’,J o u rn a l o f D o c u m e n ta tio n , 28, 195-201 (1972)
28. HEINE, M. H., ‘The inverse relationship of precision and recall in terms of
the Swets’ model’, J o u rn a l o f D o c u m e n ta tio n , 29, 81-84 (1973)
29. WEILER, G., ‘On relevance’, M in d , LXX1, 487-493 (1962)
30. GOFFMAN, W., ‘On relevance as a measure’, I n fo r m a tio n S to ra g e andR e trie v a l, 2, 201-203 (1964)
31. NEGOITA, C. V., ‘On the notion of relevance’, K y b e rn e te s , 2, 161-165(1973)
32. GOOD, I. J., ‘The decision-theory approach to the evaluation of information
retrieval systems\ In f o r m a t io n S to ra g e and R e trie v a l, 3, 31-34 (1967)

131

EVALUATION
33. COOPER, M. D., ‘A cost model for evaluating information retrieval systems’,J o u rn a l o f th e A m e ric a n S o c ie ty f o r I n fo r m a tio n S c ie n ce , 23, 306-312(1972)
34. MARSCHAK, I., ‘Economics of information systems’, J o u rn a l o f theA m e ric a n S ta tis tic a l A s s o c ia tio n , 66, 192-219 (1971)132