ISR-8
December 196k

III-l

III.

PERFORMANCE INDICES FOR DOCUMENT RETRIEVAL SYSTEMS
Joseph Rocchio

Summary
The SMART system is designed to provide a flexible test bed forevaluating a variety of potentially useful methods of automatic content.analysis in information retrieval.

SMART is primarily a document retrieval

system; however, many of the analysis techniques employed are also applicableto other phases of information retrieval, including fact retrieval andquestion-answering systems. This section introduces a generalized model ofthe system and derives several evaluation indices which will be used todetermine the influence of the various system parameters.

1.

The Model
A document retrieval system employing fully automatic indexing may

be characterized by the following elements:(a) a set of reference documents in the natural language (D);(b) a set of retrieval requests in the natural language (Q);(c) an index language L;(d) a transformation T from the natural language to the index
language which operates on members of the set Dj(e) a transformation T ! (possibly the same as T) which maps
retrieval requests to the index language L; and1II-2(f)

a search function S whose domain is the cardinal productof elements of the set Q with those of the set D, andwhose range is such that S induces at least a partial
order on the set D *In the SMART system the index language L may be considered to be aproperty space. The transformations T and T1 may take several forms. For
example, natural language word stems may be mapped one-to-one into elementsof L or, alternatively, T may be a composite transformation resulting froma many-to-many mapping of word stems to elements of L (thesaurus transformation) followed by mappings from L to L (hierarchy).

In addition, theresulting image of a document d^ 6 D under a given transformation T can beeither a binary property vector in L or a numeric vector. The searchfunction S used in SMART may also be controlled, but is basically characterized by a correlation process involving a request image and the set ofreference document images.
A retrieval operation in terms of this model consists in applying
the search function S to the cardinal product T(D) X T(q), q e Q. One may
consider the ordering induced on D from the range of S to be the result of
the retrieval operation, or one may introduce a decision function G whose
domain is the range of S and whose range is the positive integers, ouch a
decision function partitions D into disjoint subsets, normally consistingof a retrieved subset and its complement with respect to D.

In the generalcase C may, however, introduce a multi-level classification.
To evaluate the effectiveness of a retrieval operation, it isnecessary to introduce a subjective element. Let us assign to each request

III-3q, a subset Dq of D which is the set of reference documents "relevant" toq.

The specification of this subset for a given q may in general be an

ill-defined process. In an operational framework, Dq is that subset of R
which the originator of the request q would choose if he were given theopportunity of making an exhaustive search on D.

Alternatively, one may

consider that corresponding to each request q, an ordering of D is defined
which reflects the "degree of relevance" of each document in R to therequest*In this case one may still identify a relevant subset D

byconsidering those members of D for which the degree of relevance exceeds
a given threshold.
Assume for the present that for each q in Q a subset D q of relevant
documents is known or, alternatively, a partial ordering of D exists whichreflects the degree of relevance. The object of the document retrieval
system is to produce a subset D1 (or induce a partial order on D) whichq
is identical to D

(that is, equivalent to the partial order determined by

the degree of relevance). Evaluation of a retrieval system then requires
a determination of hew each of the system elements affects the degree towhich this objective is met for all members of Q*
The most commonly used performance indices of document retrieval
systems are the recall and relevance ratios introduced by Cleverdon inconnection with the ASLIB-Granfield project.

These measures are basedon having an objective set Dq of relevant documents for each query presented
to the system.

After a retrieval operation which produces a two-way classi-

fication of D into a retrieved subset D a and its complement with respect
to D, the following parameters are obtained:III-4(a)n(Dr) = total number of relevant documents;(b) n(Da) = total number of retrieved documents; and(c)n(DK-±D D Qa) = total number of relevant retrieved documents.
7
Using these parameters one can define:*<Dq n D a )recall =n(D^andn(Dq n D a )relevance =(also sometimes
called"precision")

TT—N

\

&'

Clearly, recall as defined by Cleverdon is a measure of the
inclusiveness of the set D a with respect to the set D , while relevance isa measure of the exclusiveness of the set D

with respect to the complementof D . It should be noted that the joint behavior of these parameters is
required to judge performance intuitively,, i.e., a recall of 1 or a precisionof 1 alone does not imply satisfactory performance; however, if both recall
and precision are 1, then D a = Lc, .
It must also be noted in connection with these parameters that thedecision function C of the model is required to specify the retrieved subset
Da«

In many respects this is undesirable because an additional variable isthen introduced into the system.

In fact, when evaluating the various

content analysis techniques, including the structure of the index language
L and of the transformations T and T ! , it is desirable to introduce as few
extraneous constraints as possible*

This suggests that one should deal

III-5
directly with the search function S.

Another justification for so doingis the fact that the decision function is usually determined subjectively,in the sense that in practice the needs of a particular user dictate its
characteristics.
In practice, the decision function G can easily be eliminated,because the search function S can be used to induce a partial ordering on
D directly; a user could then request that the results of the retrieval
operation be presented to hira in this induced order. If this were done,
the user could examine any desired subset of this ordered set, specifying,in effect, the "retrieved subset" a posteriori by the number of documents
examined.
In view of these considerations a set of performance indices has
been developed which may be applied directly to the ordering induced on D
by a retrieval search S.

2.

Evaluation Indices
Under the assumption that the ordering induced on the set ofreference documents by the search process S Is the principal result of a
retrieval operation and that a set of relevant documents Dq is available
corresponding to each request q, the objective of a retrieval operation may
be recast in the following form;a retrieval operation with respect to arequest q is expected to produce an ordering on the reference collection D,such that every member of the set Dn is ranked above all members of thecomplement of DQ with respect to D(D ).

III-6Note that in this formulation no emphasis is placed on any relative
order among the members of the set D q of relevant documents. While such anordering might in theory seem desirable, the determination of an unordered
set D

is difficult enough by itself, so that imposition of an additional

ordering criterion may be impractical. A partial order within D g may,
however, have some significance and, in fact, has been employed in some of
the ASLIB-Cranfield experiments to specify degrees of relevance. These inturn led to the definition of different subsets D q , but not to the specification of retrieval order with respect 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) of Cleverdon. Consider
an ordering induced on D by 8 such that a one-to-one mapping exists from D
to the dense set of integers from 1 to n(l); increasing rank order in theset of integers then reflects decreasing connection between the request
image and document image.
In this case, define:—for 1 < i < n nr*(o =r°- - °1 for nQ < i < N
and
1 for 1 < i < nQ
p*(i) = < no-T- for n 0 < i < N

v3

III-7
wheren= n(D ), i.e., the number of relevant documents tothe query under consideration;

N = n(D), the number of documents in the referencecollection; andi = 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 documents. Thus, it is Cleverdon's recall as a function of theorder induced on D by a retrieval operation.

Clearly, r#(i) is the recall

function which pertains when the retrieval operation produces an ideal
ordering on D.

Similarly, p(i) is the number of relevant documents having

rank order less than or equal to i divided by i, with p#(i) defined for thecase when all members of D have a rank index less than every member of D .
qq
Hence for each query q, r*(i) and p#(i) define a desired (or objective)
recall function and a desired precision function.
Since it has been assumed that S induces only an ordering on D, as
opposed to a metric, these functions are strictly defined only for discretevalues of the rank index i.

As it is intended to extend these functions to

a continuous independent variable, that is, to define a function r*(x)equivalent to r~*(i), a possible anomaly is noted.

This arises from the factthat it is possible, within the framework of the system, for S to produce a
mapping from elements of [q X D} to the real line. This, in fact, occurs

Ill-8when S is a correlation process which correlates a query image with the setof document images viewed as vectors in some abstract space. The processof inducing an ordering from this mapping and then treating this ordering
as function of a continuous real variable gives the impression of coming
full circle• In fact, there is clearly a loss of information involved since
relative distance between the images of dj_ and d- is not preserved by thisprocess. The justification for making this transformation from the domain
of S to an ordering index lies in the assumption that the order so derived
has significance of and by itself.
The extension then to functions of a real variable is accomplishedby defining two functions r*(x) and p*(x-) such that:r*(x) = r*(i)'or x = i, i = 1,2,••.,N;
p*(x) - p*(i)and further that;3

r*(x) = \for j < x < j + 1
j i n t e g r a l and less than n

1 for xv.
and- for j < x < j + 1

p*(x) - {j integral and less than n— for x > nxoIII-9At this point, recall and precision functions may be defined forthe results of a retrieval operation with respect to a particular query*
In particular, let the ranks of each member of the set of relevant documentsD

resulting from applying S to {q x D} be specified as:0(i)for i = 1,2,... ,n 9

where 0(i+ l) > 0(i).
In this case:
0 for 1 < x < 0(1) ;rq(x)-~- for 0(i) < x < 0(i+ l);
0

1 for x > 0(n );
•—

o

and
0 for 1 < x < 0(l);Pq(x)- for 0(i) < x < 0(i+ l) ;
n
\x

_

0

At this point, a recall error and a precision error may be definedby considering:N
recall error =)(r*(x) - r (x))dx;

X=l
and

precision error =J (p*U) - pq(x))dx
x=l

111-10Since r*(x) is an upper bound to r(x) and, similarly, for p*(x) and p(x),these errors are always greater or equal to zero.
To compute these integrals we introduce the unit step function
U ^(x) defined by:1

for x > 0;U^x) for x < 0;and note that:b\ U^1(x)dx = b .
00

Now r*(x) can be expressed as:r , (x)=^ V_±(xori1) + 0 _ 1 ( x - 2) + • • • + U_ ] _(x- n 0 )andr ( x ) = — U _ x ( x - 0 ( 1 ) ) + U _ x ( x - 0 ( 2 ) ) + ••• + U _ x ( x - 0 ( n c )Therefore,a0(r*(x) - r(x))dx = ~

Y
i=l

N
J

U . ^ x - i ) - U _ x ( x - 0 ( i ) dx
1)(i) - i

III-llorn +1
recall error = 0 -2>i.e., the integral of the difference between the recall function for perfect
retrieval and the recall function which results for an actual retrieval isjust the difference between the average rank 0 induced on the members of theset of relevant documents D

by the retrieval operation, and the* mean of

the ranks which a perfect retrieval would induce*
To normalize this parameter to the range 0-1, consider the casefor which the rank of every member of the set D
member of DQ•

is greater than every

This is clearly the case of maximum error; hence:

n

1

°
V-1

/

«££>-u-i)

max recall error ~

\

n +]
o

°i=i
n
—

n +1
(N+N- n Q + 1)

max recall error = N - n 0

Therefore,(n0-D
N - rio
is a normalized index of over-all recall error*

As this index is measuring

recall error, it is desirable to reverse it. Hence:111-12o - (VJb
1IN - Q -will be the index of recall performance*
The precision error can be expressed in terms of the unit step
function as follows:

P*(x) = i U_x(x- 1) + U_ 1 (x-2)•• + U_x(x - n 0 )and»(x) =U ^ x - 0(1)) + U ^ x - 0(2)) + ••• + ^ ( x - 0(no))

Now,

U_ l( x- a) f

In b - In

00

Therefore,N
precision error =(p*(x) - p(x))dx

nn

-I

N

x (U_x(x- 1) - U_1(x- 0(1)) j

1=1 1

Y
1=1

In 0(i) - In i

111-13Y
L

In 0(i; - V
•'

i

i= 1

In i;

— i

i-1

precision error = In

T 0(i) - In nc 1
i=lAgain, by the same consideration, this index may be normalized tolie in the range 0 - 1 by dividing by the maximum precision error* Thiserror must be:nmax p r e c i s i o n e r r o r = Ino
| T N - i + 1 - In n 1

i=l
In T:
7 - In n^ 1
1\1 - n Io

= In ' nNo

The normalized index of precision error is, therefore:noIn "["]" °(i) - ln n0l
i=l
pe =

In

III-M
Again, since this is an index of error, an index of performance isobtained by considering 1 - pe, i.e.,

In ]~T 0(i) - In n0«.
* & )will be the index of over-all precision performance*
Since both these indices reflect over-all performance, a value of
1 for either implies a value of 1 for the other, in opposition to theconventional recall and relevance ratios• The difference between these
two over-all measures lies in the weighting given to the relative positionof the relevant documents in the retrieved rank list.. The recall index
weights rank order uniformly, since it is sensitive to each relevant document.

The precision index, however, weights initial ranks more strongly,

since it is sensitive to having a high percentage of relevant documents in
the initial part of the retrieved list.
The recall and precision indices derived here depend on theassumption that the ordering induced on D by S was a full order, i.e., thatit could be represented by a one-to-one mapping from D to the integers from
1 to n(D) . As this may not be true in general, since a partial order rather
than a full order may result, a method for defining document rank in thiscase is required*
The most natural way of treating documents which are equivalent
under a partial order induced by S is to give each member of the equivalent
set the average of the ranks which would apply to the set members if theyII I-15
were differentiable.

Hence, if S induces the partial orderd± > d 2 > (d 3 ,d^,d 5 | > d6; on a set D = j d ^ d ^ d ^ d ^ d ^ d ^ andD= i d., ,dr,d/c , the rank assigned to d-, would be 1 and to d^ would be 1+,

and to d/ would be 6.
In addition, these performance Indices may be extended to the casein which there is a partial ordering of the set of relevant documents D,, .
In this case, the objective of a retrieval operation would need to be
redefined to take account of this partial ordering.
relevant documents tordering on D

where D

Assume that a set offor a query q is defined, and that, further, a partial

is specified which reflects degree of relevance, i.e.,

G D Qx and > implies Mmore relevant than."In this case, one may
idefine the objective of a retrieval operation as follows: a retrieval
4

operation with respect to a query q and a partially ordered set of relevant
documents D a is expected to produce an ordering on the reference collection
D, such that every member of the set D

is ranked higher than D
q

i

, and
i+l

that all members of D

are ranked higher than D^.
^
q
Corresponding to this definition, expressions for r*(x), p*(x),qr.(x), and p (x) could be defined in a manner analogous to those definedqq
above. The development of the indices for this case is more cumbersome
than the case previously considered and will not be presented here* The
only significant difference which arises is due to the fact that a relevant
document d^ in subset D q

may have lower retrieval rank than a document d•Ill-16
in subset D Q , where the partial ordering on D

is such that D q ^ > DQt .

This necessitates considering only the positive differences between the
retrieval ranks of the relevant documents and the corresponding ideal
retrieval ranks*

To illustrate^ consider a case whereD = d dq { r 2' d 3'V d 5' d 6JandD

q = {dl'd2'd3J > \={Vd5'd^ 'let the retrieval order be d, ,cU,d_,d, ,cL,cL ,...

n(DQ

)

/

i=n(Dc )+n(D01(i)-i+

1= 1/. Then]0 ( 1 ) - i = (1+5+3- 1+2+3)+ U + 2 + 6 ) - U+5+6) = 3 + ( - 3 ) = 0 ,i=n(D.
q)+lieven though there is clearly a departure from ideal retrieval.. By considering
only positive differences, the result would be a retrieval error of 3-

Thesame observations apply to the precision index.

3• Experimental Use
These indices have been used to evaluate the results of a variety
of experiments conducted with the SMART system*

As one might expect fromthe formulation, the range of the recall index is rather limited; i.e., arandom retrieval would produce a recall index of .5, hence one would suspectIII-I7
observed results to be near 1.0.

In fact, the observed range is from about.9 - 1.0 with the average probably close to .97. The precision index,
however, has a reasonable range for the requests examined to date, andtypically varies from .6 - 1.0.

In practice, then, one is forced to expand

the scale of the recall index, so that a range 0 - 1 is no longer maintained.
For the results obtained to date a scale expansion of 3>, introduced so as
to maintain an upper value of 1.0, produces a range for the recall index
similar to that of the precision index. The scaled recall index has, therefore,
been defined as:l.o - 5(i.o-x),
where x is the normalized recall index.
Two related performance indices may be derived from the two whichhave been considered.

These are useful in the case where a particular query

is subjected to a set of retrieval operations which are to be compared.
It may be remembered that the recall error was found as:

n +1
recall error = 0 - — ~ — •n +1
Since 0
= — - — , an index with a maximum value of 1 may be defined as
max
2
n +1
o
rank recall =20Ill-18
A similar observation for the case of the derived precision error
produces a precision index:
log n Ilog precision.
olog TT o(i)i=iThe advantage of these indices lies in the fact that they aresimpler and, therefore, easier to compute than the normalized indices, andthat the rank recall takes on a wider range for the results which have been
observed. The disadvantages of both these measures is their dependence on
n 0 , the number of relevant documents for the query in question. Thisdependence makes it impossible to average these indices over a set of
queries and thus their usefulness is limited*

REFERENCES
1*

Gleverdon, C. W., "Report on the Testing and Analysis of an Investigation
into the Comparative Efficiency of Indexing Systems," ASLIB-CrarifieldResearch Report, Cranfield (October 1962).