5-1
CHAPTER 5
EVALUATION OP DOCUMENT RETRIEVAL SYSTEMS

1• The General Problem
An operationally effective automatic document retrieval
system must satisfy the requirements of a diverse class of users. The
functional model discussed in this thesis considers only a subset of .
these requirements, principally those related to the methodologicalaspects of the system operation. The ability to establish system •requirements is directly related to the notion of performance evaluation, and in recent years the investigation of evaluation measures for
document retrieval systems has rec^red considerable attention (references 1 through 8).

The purpose of this chapter is to consider ingeneral the problems associated with the design of evaluation
experiments and the collection of performance statistics, and to
discuss in particular the implications of the system model on these* problems.
The general aim of- a document retrieval system is to"mechanize the deduction of the attribute "relevance1,* which is asubjective relation between the 'state of. a user's information need andthe information content of the "documents11 in some collection, as
perceived by the user. It is clear that since the* system operates^

The references cited are only representativeof the literatureon this topic.
• 'J

5-2
.with imperfect representations of both the needs of its users and theinformation content of documents, and since the notion of relevance islikely to be quite variable over any realistic user population, any
performance measure must represent a statistical estimate of theprobability distribution of a correct assessment of relevance.
The subjective nature of relevance implies that any realistic
system1s evaluation will require-a large amount of data.

Since thecollection of such data is costly, arid since the notion of evaluation
is a critical element of any design process, the designer of a
retrieval system must, rely on analytical tools, local performancemeasures, and intuition to select the most likely set of-functions tosatisfy his objectives.

In this connection, computer based•simulation

systems such as SMART can be of significant benefit since they allow
large amounts of data to be generated and analyzed.

One of the major

objectives of the functional model to be considered here (based on the
SMART simulation system) is to maximize-the utility of the data
generating capabilities of the system by allowing evaluation of theindividual functional elements as well as of the overall performance
characteristics.

2.

Evaluation Measures and the Collection of StatisticsA.

The Idealized Experiment
Most of the evaluation measures proposed for document

retrieval systems are based on the following idealized characterization

5-3of a retrieval operation. A user presents a search .request to thesystem which then compares an index language representation of it to
the index images of the documents in some collection. Each comparison
results in a binary decision to retrieve or not retrieve the reference
document.

Independently of the system, it is assumed that the user

has made a binary relevance judgment with respect to his informationneeds (represented by the' search request) and the content of eachdocument.

The possible results' of such an experiment with respect toa single reference document may be represented by the discrete sample
space shown in Figure 5»1 (a).. Assuming this sample space, estimatesof the probabilities associated, with each of the sample points (i.e.
of the joint probability distribution of .the user/system decisions)can be produced by tabulating the number of occurrences of each of thepossible outcomes over all of the- documents or trials which comprise asingle retrieval operation. .This is represented by the 2-by-2
contingency table of Figure 5»1 (b), where the ratio of each of thenumbers shown to the total' number "of documents represents the estimateof the probability of the corresponding sample point, i*e.:

P1 - =- - Pr {Retrieval and Relevancej ,(5«0

p 2 .• =- - Pr ^Retrieval and Nonrelevancej- ,(5*2)

p. - Tp = Pr jlforiretrieval and Relevance J- ,(5? 3)

I

SampleUser

SystemPoint

Decision

Decision1

relevant

retrieve2

nonrelevant

retrieve3

relevant

not retrieve4

nonrelevant

not retrievea) The Sample Space of the Outcomes of a Retrieval Operation
on a Single Document

Relevant .

n2Retrieved••••*••

v"

Not RetrievednNonrelevant.1.

l.+ n5 •».'n^ + n 2• n4n

3 + n4n 2 + n4H - t^ + n 2 +*3 + n 4b) The 2^by-2 Contingency Table of Retrieval and Relevancethe Outcomes of a Retrieval Operation on N Documents

Characterization of Retrieval Results
Figure5*1

5-5p, = TJF « Pr INonretrieval and Nonrelevancej- .

(5.4). Prom this joint probability distribution a number ofconditional probabilities can be defined as follows (following Swets,
reference 1):n^/ixL^+ri)« Pr ^Retrieval/Relevancej - P 1 / ( P 1 + P , ) ,(5*5)

the conditional probability of a "hit"; •'".:•.

n2/(n2+n ) = Pr [Retrieval/Nonrelevancej • P^APg+P^),.

(5*6)

the conditional probability of a "false drop";n /(n +n ) - Pr {Nonretrievai/kelevance j ••« p /(p. +p ),(5*7)

the conditional probability of a "miss";nj(n+n)« Pr ^Nonfetriieval/Nonrelevahce j » pVCPp+P^)*(5-8)

the conditional probability of a "correct rejection1;.

Note that nJ{nAnS)

is the riecall: r$tio as defined by Cleverdon

while n 1 /(n 1 +n 2 ), the conditional probability of relevance givenr'

retrieval, is his precision (also called relevance) ratio.
The Bernoulli-likemodel assumed above is in many respects• ** A Bernoulli model assumes repeated independent trials in which
there are only two possible outcomes for each trial and theprobabilities of each"outcome remain constant throughout theexperiment.

5-6
an inadequate description of the true situation. Users do. notnecessarily make binary relevance decisions nor are such decisions
9
necessarily independent when examining a sequence of documents.
Inaddition, query-document matching functions do not always lead tobinary acceptance-rejection decisions;' instead, they often result in
the assignment of a coefficient of relevance or association between a1query-document pair as has been discussed in Chapter..4. Further, inmany respects it may be more realistic to assume that the system* s
assessment of relevance should be interpreted on a relative rather
than an absolute basis. Thus, a user is

to examine at least a

few of the highest assessed documents resulting from his search
operation, independently of the absolute retrieval coefficients which
are assigned to them.

In this sense, there is a degree of difficultyin establishing a uniform criterion for what constitutes a positive
relevance assessment by the retrieval system over a sample set ofsearch requests.

B. Evaluation Statistics

The contingency table description* of a retrieval operation,
shown in Figure 5«1 ("b) provides frequency ratio estimates of thejoint probability distribution of the user/system decisions for the
given query.

One may then assxrae, Mother .variables remaining constant,that these frequency ratios converge to probabilities as the number of"documents searched (N) increases.* Alternatively, one may assume thatthe probability estimates obtained by a search over N documents
predict the behavpur of the system with respect to the input query5-7
for some larger collection from which N is a representative random
sample •Consider now the typical evaluation situation in which a
number of retrieval operations are performed on some sample set ofsearch requests. In the conceptual framework of the idealized experiment, one assumes the existence of a universe of queries from which
the sample set is drawn at random. According to the above characterization, each retrieval operation results in a particular estimate forthe joint probability distribution of the user/system decisions,applicable to the input query. Let the query sample contain m.
elements. The results-of the m retrieval operations may be summarized
by .m 4-tuples '•(piJYpJrPji P J ) i - 1fffl

where the p,.fs are defined by equations {5.1) to (5*4)•'. Each" of the
4-tuples in addition to defining the probabilities of. the' sample
points of Figure 5*1 (a), defines a set of conditional probabilities
such as are given by equations (5*5) to (5-8)« 'In terms of the probabilistip model, the beha^bxir of a
retrieval system is completely specified by the 4-tuple (p1,p2,p.,p.)of each query (and associated user relevance decisions) in the.
universe of queries or query sample space of the system, (which for.,convience is assumed to be discrete).' This sample space defines ajoint probability distribution'of four random variables P.-, Pp, P..,and P

given by:

5-8

> [P1 =p1.' V p2.' V p3 ' V P 4^ "f(p1.'p2.'p3 ' V '(i, j, k, 1 « 1,2,/.) .

The set of m 4-tuples which result from the test set of retrieval operations provides then an estimate for this joint distribution.

The fact

that the random variables assume values which are probabilities (or more
precisely estimates of probabilities ) represents only a notationaldifficulty.
Statistically then, the objective of an evaluation experimentis to estimate this joint probability distribution or some parameters •which characterize it.

Clearly any evaluation which ignores the essen*..

tial fact that the system performance is a random variable defined overthe query sample space can produce misleading results.

Consider forfi 7 ftexample the evaluation data produced "by the Cranfield studies.

'

System evaluations in these reports were presented primarily in terms.of
the two conditional probabilities, precision and recall, rather than interms of the joint probabilities p.. This in itself introduces noproblem (other than ^Pe**the fact that' it does not represent all theinformation available in the experimental data); the method used tocompute estimates for the mean values of the precision and recall probabilities,..however, was in error.
The precision and recall conditional probabilities, being functions of the random variables P., are themselves random variables definedon the query sample space. The results of m.retrieval operations may besummarized in terms of these conditional probabilities by m couples:5-9(p1, r 1 )i - 1,m

where

,

4

i

precision - p•

i i * query-_ip., •+

and

1

.

i

1

n^-h n g

P2irecall • r

1

-

PV

n

=

i
i
1 + p3nP±^ query

i

1

i

(5-9)

>

i
i

+ n

1

<

(5-10)i • 5

3where the n.fs are defined "by-Figure 5*1 (*&)•' The m couples (p ,r )Jprovide an estimate of the joint probability distribution of therandom variables P and R defined by:Pr^P * p , R = r ^= g(p , r k )(j, k - 1,2,..) .

The respective expectations of these random variables E(P) and E(R)are estimated by the sample means:

m

i

m

' • i t 77? -it'Simr --1 V
i-1

PP

777- •

1 * 2

i-1

i

m-

n

1

+ n

(5 11)-2i- A T - -1 7
Pi * P 3

i

-^ •
n

i-i - i+•(5.12)"5

The Cranfield data was interpreted in a different manner;In

particular the precision and recall estimates were computed according
to the equations:

5-10
m

£•1
1=1
m .

£<

(5.13)

+ n

2

1=1

£x
. i-1

c

(5.H)

'

These estimates may be interpreted as resulting from a composite
contingency table description of the results of m retrieval operations
in which the entries of tthe composite table are cumulations of the corresponding entries of the m individual tables. As such, these are valid 'estimates for the conditional population ratios, but not for the meansof the associated conditional probabilities over the.query sample space.
Without justification it can be assumed that a valid measure of
the performance of a retrieval system is the average value received by
the system1 s users. Assuming that the precision and recall conditional
probabilities which characterize a given retrieval operation are infact indicitive of the value of that operation, the estimators defined •by equations (5*11) and (5*12) are clearly the appropriate, ones. -Moreprecisely if it is assumed that the value of the i* of a set of m
retrieval operations can be expressed as:v.

-

h(p\ r 1 );a random variable V is defined which is a function of the random variables P and R.

An estimate for the expectation of V, E(v) is given by:

5-11
m

1

v

.

- -£- L ^ p 1 * r l ) »i=1

i.e. the1 sample mean, which is a function of the sample distributionof the precision and recall conditional probabilities and not of the.
population ratio estimates.
A numerical example may serve to illustrate the precea&ing
points. Assume that a sample set of test queries produces results
which can be placed in the four categories shown in Table 5*1 • It
is implied in this hypothetical case that each of the observations isrepresentative of some large subset of input queries of the test sample,
so that it can be assumed'that the four qujery types represent equallyprobable subclasses of the query sample space.
i

.

.

•

'

•

!
Query Type'
1
2

3
4

*i
• Relevant &Retrieved

n

2

!~

*s~

'. Nonrelevant& Retrieved

Relevant &Not Retrieved

>

3
^5
. 1

5

45

3
5
9
45

.7
5

Retrieval Results for 4 Equally Brobable.Query.O^rpes.
Table "5-1

Table 5»2 (a) shows the precision and recall sample distributions and the sample mean estimators for the averages of these randomvariables over the query sample space. If, however, the data from

5-12

Table 5-1 is cumulated into a single set of frequencies, the population
ratio estimates for the precision and recall are as shown in Table 5*2(b).

The numbers were chosen to illustrate that the cumulation of obr-

servations results in a precision estimate weighted towards thesystem's performance for queries with higher than average number of
documents retrieved, and a recall estimate weighted towards the system's
performance for queries with a higher than average number of documents
relevant. Thus, for the example shown^the population ratio estimatesare biased by the presence of query type 4-

Query
Type
1

Precision j Becall

Cumulative Frequencies
V

•7

2

•7

n

.5

1

n

26

54'

2

n

.

3

•9

.5

Population Jia$$os

4

.1

.1

26 ,
„
*c-80**53

Sample
Means

•55

•45

r

i (a) Query Dependent Statistics

• 26

*'

62

!

TA

c - 55 " -50(b) Population Dependent
Statistics

Comparison of Precision and Recall Estimates '
Table

5-2

C. Output Characterization

The model discussed above for describing a set of retrieval
operations is generally extended by allowing a parametric characterization of search output, i.e. of the system1 s retrieval, decisions. The

5-13

data obtained in this manner can usually be interpreted as portraying
the variation of the joint probability distribution of the user/systemdecisions as the system's retrieval criterion is relaxed. A typicalexample of this type of system characterization is given by a precision
vs. recall plot such as the one shown in Figure 3.10.
Within the framework of the functional model, the result of a
retrieval operation has been characterized by two essentially different
forms.

Thus as described,in Chapter 4> the set inclusion query-document matching function leads to a natural partition of the referencecollection into the retrieved and not retrieved subsets. The othermatching functions considered (correlation processes) require thespecification of a cutoff or decision criterion to induce such ainpartition.

It. is 3hown below that the commom means used to vary thesize of the retrieved subset under set inclusion matching is, in fact,
equivalent to the use of the set overlap correlation function.
Consider a query containing n keywords. With set inclusion
matching, the retrieved subset R contains all document images containing at least all nquery keywords. Define now a subset Ef(k) whichcontains all documents that include at least k of the n keywords ofthe query. A uniformly decreasing sequence of values for k from n
1 produces a sequence of retrieved subsets satisfying:R(n )'C E(n- 1) £.... C_R(2) C

R(l) .

The retrieved subset R(k) is thus monotonically increasing withdecreasing'values of the cutoff parameter k.

to

5-14
The set overlap correlation function was defined in Chapter 4
as:jO(q.d) - n(qOd),

where n(A) is the number of elements in the set A.
contains nThus if the query q

keywords, all documents containing at least those same nkeywords receive correlation n . Documents containing n -1 of the nquery terms receive correlation n -1, etc. Therefore, the union of all
document subsets with correlation k or greater under the overlap
matching .function is equivalent to the retrieved set H(k) under set
inclusion matching, and thus when the retrieval criterion is allowed tovary, these matching functions are essentially equivalent.
Set represented index images lead to retrieval rankings of
document subsets, whereas .with vector represented index images
individual documents are ranked. The difference is essentially one ofdegree and can be attributed to the-increased information content of thevector index language. With a vector correlation-matching process theretrieved subset may be parametrically associated with a cutoff
correlation (defined either absolutely or relatively with respect to thecorrelation distribution for each query)', or with the rank position of
documents in the ordering' induced' from the correlation coefficient (forexample by defining the retrieved subset to contain the k highest.correlating documents).

The common property of any of these alternatives

id that they all yield a sequence of'monotone increasing retrieved

5-15

subsets as the degree of association (defined by the matching relation)
is decreased. Each of these techniques is commonly used to represent
the variation in the joint distribution of the user/system decisions as
the quantity of output (the size of the retrieved subset) is increased(or equivalently as the matching criterion is relaxed).

In section 4of this chapter an alternative to the general evaluation strategy ofdescribing performance by a set of parameters which vary with discretechanges in the matching criterion is presented.

D.

The Precision-Recall Tradeoff
The use of a precision vs. recall plot variable with thecutoff parameter as an evaluation tool for document retrieval systems(introduced by Cleverdon ) has led to observations that there exists a
so-balled tradeoff between these two conditional probabilities which
is of fundamental significance.

It will be shown here, however, that

this inverse relationship is a direct consequence of assuming astatistically significant matching function, and further that bothof these conditional probabilities are increased by any process which
improves the joint probability of retrieval and relevance.
The increase in recall as the amount of output accepted as
retrieved is increased ifi a direct consequence of the definition of
the recall conditional probability.

Since the retrieved subset ismonotonically increasing, the ratio of relevant documents retrieved totb"6al number of relevant documents (a constant for any retrieval
operation) is necessarily'monotonically increasing. .Precision, *however, is defined as the ratio of relevant documents retrieved to5-16

the total number of retrieved documents. It has been shown above that .
an increase in the size of the. retrieved subset is tantamount torelaxing the requirements for query-document matching.

Thus if it is. assumed that the matching function is a statistically significant
indicator of relevance (the counter assumption is clearly contradictory
to its use), precision must decrease with increase in the size of theretrieved subset.
As a concrete example, consider the vector indexing model.
With respect to a given query, one- assumes that the probability that a
dociament d. be relevant to the query is a monotonic function of thecorrelation coefficient J>(q,d.).

Consider the two highest correlating

documents d* and d^ which result from search operations for someensemble of queries q..

Let q1 be the probability that dL is relevant

and q 2 be the probability that <L is relevant.

The assumption above

implies that averages over the query ensemble will yield estimates forthese probabilities such that:(5 15)

VV-

Now assume that the precision ratio is calculated after each retrieved
document (i.e. the cutoff is a function of the retrieval ordering). At
cutoff 1, the precision ratio is clearly q1.
precision ratio is (^-KL)/^.

Since ^>^2

At cutoff 2, the^ P 1 ^ 8 '&*** q ^ ^ + q g ) / ^ ,, the precision decreases as the number of documents considered retrieved,
inoreases.'

.5-17
The tradeoff, then, between precision and recall is anecessary statistical consequence of using a meaningful matching
function.

The nature of this tradeoff is fundamentally related to thejoint probability distribution of the user/system decisions from which
the conditional probabilities, recall and precision, are defined.
Improvements in retrieval systems which increase the joint probabilityof relevance and retrieval will increase both recall and precision fora given level of query-document association.

For a given user, theinverse relation of recall and precision influence the number of
output (retrieved) documents which it is useful for him to examine.

3.

The Use of Optimal Queries in Test Design

In Chapter 3 the notion of an optimal search request, wasintroduced and developed*from the point of view of query modification
in a system environment allowing iterative searches, and real timesystem-user interaction.

It was noted there that the concept of an

optimal query offered the potential of allowing an explicit evaluationof the power of the index language independent of the performance'
variations which can be expected from the query formulation process.
In essence, any evaluation measure based on a retrieval
operation 'with an optimal query is a measure of the relative
association between the members of a subset of relevant documents(specified by the user) compared to the association of these documentswith the entire collection.

Viewed in this manner, the definition ofan optimal query offers a positive alternative to the design of5-18

evaluation experiments for retrieval systems.

Conventionally, on an

experimental basis, there is a serious problem in obtaining representative search requests with accompanying relevance judgments (witnessedby the controversy as to the value of the test queries used in the
Cranfield study

10

for example).

Rather than measuring performance by

the use of test queries,- a retrieval system can be evaluated byobtaining user judgments as to the degree of association between
documents which by their location in the index space are necessarily
associated.
Such an evaluation represents a measure of the ability of theindexing ocheme to preserve the associations in the index space whichusers can detect from the information content as expressed in thenatural language.

Since the retrieval performance which a user can

expect is a function of the degree to which input search requests
correspond (or can be adjusted to correspond) to their respective
optimal forms, and since the performance of an optimal query is
directly related to the consistency of the associations of documents in
the index space, a measure of the latter is indicative of a measure of
the former. While such a procedure does not mecessarily reduce thequantity of subjective data required, for a significant test of a
retrieval system, it offers the potential for providing an increased
measure of experimental control.

Since the requirements for examining

the implications of such a test program are prohibitive with respect tothe scope of this thesis, (by virtue of requiring a large subjective test
effort), this test design is offered as a suggestion worthy of•additional consideration.

5-19
4*

Cutoff-Independent Performance IndicesA.

Derivation

Performance indices for document retrieval systems which are
based on a contingency table description (as introduced in section 2)
assume that a retrieval operation partitions the reference collection,i.e. identifies a retrieved subset.

In the model system consideredin this thesis (vector indexing and cosine correlation query-document
matching), and in other models of interest (see Chapter 4), the resultof a retrieval operation is more accurately described by the
distribution of the matching coefficient over the reference collection
or by the ordering induced on the document set from this distribution.
The use of partition based evaluation parameters for such systems
requires, then, that some decision function (or cutoff criterion) be
introduced into the retrieval process. Operationally, the number of
retrieved documents a user will examine is likely to be dependent on
a number of subjective variables. There is, therefore, considerable
difficulty in the a priori specification of a meaningful partitioning
algorithm.

Por this reason, then, some performance measures arederived here which are functionally dependent on the full ordering of
the reference collection produced by a retrieval operation.

Suchmeasures eliminate the need to introduce any notion of cutoff.
Under the assumption that the ordering induced on the set ofreference documents by the search process M is the principal result •of a retrieval operation and that a set of relevant documents Dp isavailable corresponding to each request q, the objective of a

5-20

retrieval operation may be expressed as follows: a retrieval operation
with respect to a request q is expected to produce an ordering on thereference collection D, such that every member of the set D R is ranked
above all members of the complement of IL with respect to E(lL).
Note that in this f ormulation no emphasis is placed on any
relative order among the members of the set IL of relevant documents.
While such an ordering might in theory seem desirable, the determinationof an unordered set D- is difficult enough by itself, so that impositionof an additional ordering criterion may be impractical. A parti&l order
within Dp may," however, have some significance and, in fact, has been
employed in some of the ASLIB-Cranfield experiments to specify degrees
of relevance.

These in turn lead to the definition of different

subsets D-, but not to the specification of retrieval order withrespect to relevance order.
Given the previously stated definition of the objective of a
retrieval operation, two functions, of the ordering induced on D may be«

defined which are related to the recall and relevance (precision) ofCleverdon.

Consider an ordering induced on D by M such that a one-to-

one mapping exists from D to the dense set of integers from 1 to n(D);increasing rank order in the set of integers then reflects decreasing \connection between the request image and document image.
In this case, define:r*(i) - <— f or 1 '< i < n
n
""• o
o
1 f or n < i < V
o—
—

5-21
(

and

1 for

1 < i < n0

P*(i) - In7^ for n < i < N
i
o—
—
where
ZL « ^(D-j), i.e., the number of relevant documents tooit

the query.under consideration;
N - n(D), the number of documents in the referencecollection; and,i • the rank index induced on D.
The function r(i) is viewed as the number of relevant
documents having rank order less than* or equal to i divided by the
total number of relevant do6uments. Thus, it.is Cleverdonfs recall as
a function of the order induced on D by a retrieval operation.
Clearly, r*(i) is the recall function which pertains when the
retrieval operation produces an ideal ordering oh D.

Similarly, p(i)is the number of relevant documents having rank order less than orequal to i divided by i, with p*(i) defined for the case when allmembiers of BL have a rank index less than every member of D . Hence•ft

9.

for each query q;,..r*(i!). defipes> a .desired (or objective) recall
function, and p*(i) defines a desired precision function.
Since it has been assumed that M induces only, an ordering on
D, as opposed to a metric, these functions are strictly defined only.for discrete values of the rank index i. As it is intended to extend
these functions to a continuous independent variable, that is, to5-22

define a function r*(x) equal to r*(i) for x w.i, a possible anomaly is
noted.

This arises from the fact that it is possible, within theframework of the system, for M to produce a mapping from elements of{qxD3

to the real line. This, in fact, occurs when M is a correla-?

tion process whioh correlates a query image with the set of document
images viewed as vectors in some abstract space. The process of
inducing an ordering from this mapping and then treating this ordering
as a function of a continuous real variable gives the impression ofcoming full circle.

In fact, there is clearly a loss of information

involved since, relative distance between the images of d. and d. is notpreserved by this process. The justification for making this transformation from the domain of M to an ordering index lies in the assumptionthat the order so derived has significance of and by itself.
The extension then to functions of a real variable isaccomplished by defining two functions r*(x) and- P*(x) su °k that:r*(x) « r*(i)for x .-.i, i » 1,2,...,N ;p*(x) -"p*(i) "and further that:( 3£- for j < x < j + 1 , and j integral andoless than nor*(x) »

1 for x > n
o

i:
and

/
— for j < x < $ + 1, and j integral andless tban np*(x) - { *—xfor x > n
o

o

>

5-23
At this point, recall and precision functions may be definedfor the results of a retrieval operation with respect to a particularquery. In particular, let the ranks of each member of the set of
relevant documents D- resulting from applying M to {q. x D } bespecified as:0(i)for i ..1,2,...,no,where j3r(i + 1) >&(x).
In this case:0r q (x) - / 1nfor

1 <X<#(1)f o r # ( l ) < x<j2T(i+l)

1 for x >0(n )*and
0 for 1 <. x<J2f(l)P (x) - / - i for j2f(i) < x < j?(i+1)
n[^for x >j?(n )At this point recall and precision error functions may be
defined by the equations:'

recall error -•' J ( r * ( x ) - rq(x))dxx»1N
precision error = / (p*(x) - p (x))dx
x-1. ';(5-16).

(5-17)

5-24

Since r*(x) iff an upper "bound to r(x) and p*(x) is an upper- "bound top(x), the error functions are always greater or equal to zero.
To evaluate these integrals the unit step function, U « ( x ) is
introduced, defined "by:1

for x > 0!!_., (x) =I0 for x < 0
for which:

U_1(x)dx = fc
- oo

Now r*(x) can "be expressed as:

r*(x) =

-

v

n

'

U_1 (x-1) + U_1 (x-2) + ...-.'+ U_1 (x-nQ) •andr(x) - 1nU^x-j^l)) +U_1(x-2f(2) + .... +U_1(x-J2f(n0)Therefore,
H

h

IT

f (r*(x) - r(x))dx - 1

f

f jU^Cx-i) - ^ ( x - ^ i )i-1 1

i.lN-'
1=1nn- 4° i1. i **).'-

1

^
0

i-1

4

dx

5-25

or
recall error • j? -(5.18)

Thus the integral of the difference between the recall function for a
perfect retrieval and the recall function of an actual retrieval operation is the difference between the actual average rank (0) of themembers of the set of relevant documents D R , and the average rank
(n +1)/2 which would obtain under perfect retrieval.
This parameter may be normalized to the range 0 - 1 by considering the case for which the rank of every member, of D R is numericallygreater than every member of iL. This is clearly the case of maximum
error; therefore:nmax recall erroro••=• L - - U - D

-

n +1
o

i=1
n
;.o (N + N - n + 1)
Q

n

n +1
o

o
Hence:

n +1

9re

0

r>

(5.19)

N -n

is a normalized index of the recall error. As this parameter measuresrecall error, it is desirable to reverse it. Therefore:

n +1
•)

*-'(-

1 -

N - n
0

(-5.20)5-26
is the desired normalized performance index.
The precision error integral may he evaluated .through the useof the unit step function as follows:

P*(x) - i U^Cx-l) + TJ^Cx-2) ++ TJ^(x-nQ)

andp(x) - 1 j ir/x-pO)) + ^ ( ^ ( 2 ) ) + .... + u^Cx-jzrc^))
Now
r

J

V

x

dx - In h - In. a—
X-oo
Therefore:N
precision error » /r (p*(x) • p(x))dx

i
no

N

L. j "x1

U^Cx-i) - U(x-#i)
—

I

•

I

i=1 1
ii

n

^T In j2f(i) - ' J
i-1
or

In i

i-1
n

precision error « In .| |jZf(i) - In ( n ! ). (5*21)i-1
This index may be normalized to lie in the range 0 - 1 lay5-28difference between these two over-all measures lies in the weighting
given to the relative position of the relevant documents in the orderedretrieval list.

The recall index (equation (5.20)) weights rank orderuniformly, and is therefore equally sensitive to the rank of every
relevant document.

The precision index (equation (5.25)), however*,weights initial ranks more strongly, and is therefore more sensitive tothe system1 s belmvp*j*r as reflected by the initial distribution of
retrieved documents.
The recall and precision indices, derived here depend on theassumption that the ordering induced *on D by M is a full order, i.e.,that it cajx be represented by a one-to-one mapping from D to the dense
set of integers from 1 to n(D).

In general this may not be the case ...:.

since a partial order rather than a full order may result from a given
retrieval operation; therefore a method for defining document rank inthis event is required.
The most natural way of treating documents which are equivalent• under a partial retrieval ordering is to give.each member of theequivalent set the average of the ranks which would apply to the set
members if they were differentiable. J Hence, if• M induces the partial
order.: d1 > dg > |d ,d ,d-"^ > d g .,on a set D = {d-j f4 2 , d 3 f d 4 f d 5 f d 6l ,ranks are assigned in the sequence: 1,2,4,4>.4>6.
In the derivation above of the normalized rank recall (eq.
(5.20)) and the normalized log precision (eq.,(5*23)) it was assumed.that all members of the set of relevant documents D R were of equal value.
Consider now an extension of these indic6s*/by assuming that a partial
ordering on D- is specified*which reflects degree of relevance, i.e.,

5-29
\

>

\ > ' "

>J\

where D R £ D R and > implies "more relevant than.11 In this case theiobjective of a retrieval operation may be defined as follows: aretrieval operation with respect to a query q. and a partially ordered
set of relevant documents IL is'expected to produce an ordering on thereference collection D., such that every member of the set D R
before all members of the sets D_

is ranked
ifor which i < k, and that all

members of D^ are ranked before members of iL.
it

Corresponding to thisJR.

definition,, expressions for r*(x), p*(x), r (x), and p (x) may be
defined in a manner analogous to those previously used.-

The develop-

ment of the performance indices for this case is* more cumbersome thanfor the case presented above... As the situatiQn to which these extended
indices are applicable is not normally considered to be of general,interest their derivation is omitted.
B.

Experimental Use
The performance measures developed in this section have beenused to evaluate the results of a variety of experiments conducted with.
the SMART system.

11 12'
As one might expect from the" formulation, therange of the normalized recall index is rather limited;..i.e. a random
retrieval yields an expected recall index of .5, hence one would
suspect results observed in practice to be close to 1.0.

In fact, theobserved range of this index from a variety of SMART system experiments
is from about .9 to 1.0, with an average near .97* . The normalized precision index however, being more dependent on the initial part of the5-30
retrieved sequence, exibits a reasonable range for the search requests
examined to date, and typically varies from .6 to 1.0.

In practice then,to produce a useful range of values for the recall index, one is forced
to expand its scale. A scale expansion of 5> introduced so as to maintain an upper bound of 1.0, produces an observed range for the scaled
recall index similar to that of the precision index. The scaled index
is defined as: *

rn

«

K
Y
1.0 - '5(1-9ri.)nyswhere ris the normalized rank recall defined by equation (5.20).
Two related performance indices may be derived from the two

which have been considered.

These are useful in the case where a par-ticular query is subjected to- a set of retrieval operations (varying
Some system parameter for example) which1 are to be compared.

The recall

error, equation (5*18) was derived as:n= $re cadi error

+ 1 •
^—

Since 0 . - (n +1) / 2, a positive index with an upper bound of 1.0 may
be defined as:
n

~ +1

i.-.0

rank recall

•.

i

«

9
A similar observation for- the case of the derived precision error, equation (5.21), produces the index:

J

5-31

log precisxoa•—

In (a !)
— —o

. m T T tfd)
i-1
The advantage of these indiceslies in the fact that they

are simpler and therefore easier to compute than the normalized' indices.
In addition, the rank recall parameter requires no scale expansion toassume a useful range. The disadvantage of "both these measures is theirdependence on n , the number of relevant documents. As n.. '. varies,,o«ofrom query to query this dependence makes it impossible to average
the unnormalized indices over a set of search requests to produce ameaningful system's evaluation.

5-32
REFERENCES

1.

Swets, J .A., "Information Retrieval Systems", Science, Vol. 141,
July 1963

2. Verhoeff, J., Goffman, W., and Belzer, J., "Inefficiency of the Useof Boolean Functions for Information Retrieval Systems",
Communications of the ACM, Voll 4, No. 12, Dec. 1961
3.

Swanson, D.R., "Searching Natural Language Text hy Computer",
Science, Vol. 132, Oct. i960

4.

Swanson, D.R., "Interrojgating a Computer in Natural Language", •Information Processing 1962, Proceedings of IPIP Congress 62,
Amsterdam North-Holland Publishing. Company, 1963

5.

Swanson, D.R., "Design'of-Experiments, for the Testing of Indexing
Systems", draft manuscript

6.

Cleverdon, C.V., "Report on the Testing and Analysis of an* Investigation into the Comparative Efficiency of Indexing Systems",
ASLIB- Cranfield Research Report, Cranfield, Oct. 1962

7.

Cleverdon, C.W., "The Testing of Index Language Devices", ASLIB
Proceedings, Vol. 15, No. 4, April 1963

8.

Lancaster, P.W. and Mills, J., "Testing Indexes and Index Language
Devices: ASLIB Cranfield Project", American Documentation, Vpl. 15,
No. 1, Jan. 1964

9.

Goffman, W., "A Searching Procedure for Information Retrieval",• Information Storage and Retrieval, Vol. 2, No. 1, Jan. 1964

10. O'Connor, J., "A Review of the Cranfield Project", Journal ofDocumentation, Vol. 17, 1961

5-33
Salton, G., "The Evaluation of Automatic Retrieval Procedures Selected Test Results Using the SMART System", American
Documentation, Vol. 16, No. 3, July 1965
Rocchio, J., and Engel, M., "Test Design and Detailed Retrieval
Results", Report ISR 8, The National Science Foundation,
Harvard Computation Laboratory, Dec. 19^4