V.
A.

Evaluation Of Retrieval Performance

Measures Of Performance

Several average measures of the performance of thetested retrieval algorithms on the 42 Cranfield queries
are used in this report•

Each measure is based on theconcept oi -I'recall" and "precision".

In evaluating an

information retrieval system, an arbitrary cut-off point,
such as r*iik tan or cosine correlation 0.75t is often employed.

Documents above this cut-off point in the ranked

list resulting from a search operation are considered"retrieved".

With such a cut-off, recall is the percent-age of documents relevant to the user that are retrievedt
and precision is the percentage of retrieved documentsthat are relevant*
An ideal retrieval system would provide recall andprecision of 100%, indicating that all relevant documents
are retrieved and no non-relevant documents are retrieved.
In SMAHT experiments an inverse relationship between recall and precision is observed, such that high recall
implies low precision and vice-versa.
The •document curves1 used in this report are graphsof recall and precision at several cut-off points basedon rank; that is, recall and precision after
are retrieved, for several values ofx.

x

documents

The other mea-sures used are not based on specific cut-off points, but
in a sense measure retrieval performance over the entire
document collection.

23

24
Normalized recall and normalized precision are two
measures proposed by Rocchio iyj

that take the average re-call and precision obtained for all possible cut-off points.
If

N

is the number of documents in the collection,

the recall at a cut-off ofj

documents (rank j) andis the precision at a cut-off ofR.

isP.

Jdocuments, normalized
y jrecall and precision are defined as follows L1151
tNd - 1
NJ - 1

For automatic calculation, the following approximations are used in the SMART system LIl5l'*\nNR-l-^~rii~l_n_ii~lnn

MP - 1 -In ^ -yi - 1

In ii~lTn~7NT( nJ (N-n)J
where r<is the rank of the icollection andn)relevant document in theis the number of relevant documents inthe collection for the given query•

A normal overall measure25of retrieval performance has been su^ested
not explicitly displayed in this report:measure • 1 «• £ UK • NP.

L yj

but isNormal overall

The factor of |> gives equal weightto the two component measures*
Anothor overall measure used in many studies of retrieval performance is the recall-precision curve, anaverage plot of precision at each 5% or 10% of recall.
Each query is averaged into each point of the plot.

Toaccomplish this averaging process, an interpolation procedure is needed, since, for example, a query with two
relevant documents can only achieve uninterpolated recall
levels of 50% and 100%.
Two types of recall-precision curve are used in thisstudy.

They are distinguished by the Siethod of inter-polation used.

Both the Quasi-Cleverdon interpolation usedin several previous studies and the Heo-Cleverdon interpolation now used for all evaluation of the SWART system
are described below.
Figures 1 and 2 show two graphs for a hypotheticalquery having 4 relevant documents.

The relevant documents

are assumed to be retrieved with ranks of 4, 6, 12 and 20.
Thus, at 25$ recall, the precision is 25% * at 50? recell,
the precision is 33%% and so on.

However, these values

correspond actually to the highest possible precision pointa,
since they are calculated Just after a relevant document isretrieved.

In this example, after 3 documents are retrieved,

26
the precision is 0%f after 5 documentsf the precision is20%f and GO on.

This range of precision for each recall

level is indicated by the top and bottom points in Figures
1 and 2 at 2$%f 50%f 75%% and 100% recall.

The solid saw-

tooth line connecting these points is not used for interpolation; it is intended to indicate the drop in precision
between the actual recall levels for this query as more nonrelevant documents are retrieved*
The <iuasi-Cleverdon interpolation uses a straight line
between peak points of precision, as indicated by the dashedline in Figure 1*

It has been argued that this interpola-tion is artificially high, since it lies at all points
above the saw-tooth curvef and thusf does not reflect inany way the precision drop as more non-relevant documents
are retrieved*

The Neo-Cleverdon interpolation of Figure 2

projects a horizontal line leftward from each peak point ofprecision, and stops when a higher point of precision isencounteredc

This new interpolation curve (the dashed linein Figure 2) does not lie above the saw-tooth curve at allpoints•

When the precision drops from one recall level

actually achieved to the next, an immediate drop in precision after the first point to the level of the next point
is indicated*

For example* in Figure 2 f the precision value

at 50% recall is 35%* but at 55% recall, the interpolated
value used for the new averages is 25% precision.

When theprecision rises from one recall level to the next, however,the first precision point actually achieved is ignored for27pr30ec25i20

Bi150n10
sawtooth curveinterpolated curve

5 U^Jo 6 joid~zfo

jfo

do

^

sb9b

100% Recall
An Illustration of the Interpolation Method Usedfor the Quasi-Cleverdon Recall-Precision Averages
Figure 1—30L»•»«

25"020J

11510*.sawtooth curve.interpolated curve.

5 'J_405060708090 100% Recall
An Illustration of the Interpolation Method Used for theNeo-Cleyerdon Recall-Precision Averages
8L.-

102030Figure 2

28purposes of interpolation*The achieved precision of ;>v

at 25$ recall in the example of Figure 2 is ignored, andfor all recall levels from 0 to 5>0%, en interpolated precision of 33% is used for the new averages•

The proponentsof the new interpolation argue that this method indicatesin all cases a precision that the user could actuallyachievef if he were to use clairvoyance to retrieve exactly
the right number of documents•
Bo

Statistical Significance Tests

Ceveral statistical tests are reported here usin-s as
input the rank recall, log precision, normalized recall,normalized precision, and 10 points from the feedback effect(Section V-C) recall-precision curve with the lieo-Clev^rIon
interpolation.

The statistical testu are intended to measurethe "significance" of the average difference in values ofthese measures obtained for two iterations or two distinct
search algorithms.

The test results are expressed as theprobability that the two sets of values obtained frooi two
separate runs are actually drawn from samples which havethe sane characteristics.

A small probability value thus

indicates that the two curves are^significantly different.
If this probability for one measure is, for example, 5%,
the difference in the two average values of that measure issaid to be "significant at the 5% level".
Choice of a statistical method for calculating thisprobability is important.

The present study uses three sta-tistical tests, the familiar T-test, the Wilcoxon Signed-

29
Rank Test (&J3;<)t and theftilcoxonRank Sum Test (*KS) L16J#The T-Test and the Ailcoxon Si«ned-Rank Teot are usedin this report to compare the retrieval of one feedback
iteration to another or of one algorithm to anotherf using
all queries*

The T-Test takes account of the magnitule ofthe differences, and assumes that the measures tested arenormally distributed.
assumption*

The WSR test does not make thisMoreover, the ftSR test takes account only of

the ranks of the differences, ignoring their magnitude*
Because this test does not assume normality of the input
and because it ignores some information (magnitudes ofdifferences)% the WSS teat is more conservative than theT-Test*

It is therefore less prone to the error of callinga result "significant" when it is not*Because information

retrieval provides discrete rather than continuous data,
and because only 42 data points (42 queries) are provided*
the more conservative R'SJS test is preferable for the presentevaluation*
The Ailcoxon Hank Sum Test can be used to test unpaired
observations9 and is used in Section VI-1S of this atudy tocompare one subgroup chosen from the 42 queries to a contrasting subgroup of queries*

Like the WSR test, the WHS

test ignores the magnitudes of the results and does notassume a normal distribution*C*

The Feedback Sffect in Evaluation

The assignment of ranks to documents retrieved for feedback is a key factor in the evaluation of retrieval performance*

30
Two methods of assigning these rnak^ have been proposed,
and both are used in the present study*

H?*ll and We/der-man l '* compare and evaluate these two methods*

In pre-vious feedback: investigations, all docutnonta in the collection received new rank** after each iteration and thetop-rankod N documents t*ere used for feedback.

Hall andfteiderman point out that evaluation of this retrieval
technique takes into aocount two effects* which they call"ranking effect" and "feedback effect"•
Relevance Xeedback in effect uaou information from one
or more document descriptors to modify the query descriptor*
The relevant documents used for this purpose will be ranked
higher by the modified query than previouslyt and the nonrelevant documents used will be ranked lower*

The effectof these rank changes in "retrieved" documents is termedthe "ranking effect"*If the r^nkin^ effect ia included

in an overall performance neaaure, the measured change inperformance between feedback iterations is quite impressive*
This large change in "total performance" (including
both ranking and feedback effect) indicates the extent towhich the Initial query has been perturbed toward thecentrold of the relevant documents, and strongly supports
Rocchio*a theory*
Hall and Weiderman state that in an environment where
the user must actively supply relevance judgments for feedback* changes in the ranks of documents which the user has
already se9n are of no interest to him*

The user in such an51
environment is concerned primarily with the "feedbackeffect"; that is, the effectiveness of the modified queryin brin^in^ new relevant documents to his attention*

They

conclude thatt though total performance is a valid measureof the effectiveness of relevance feedback in approachingthe "ideal query", the feedback effect should be isolated
and examined as well*
The present study evaluates total performance and alsomeasures feedback performance in the manner suggested by
Kail and ,*eidermanf discarding the ranking effect andpresenting only the feedback effect•

The ranks of the top

N documents retrieved in each iteration (the documents
used for feedback) arc "frozen" in all subsequent iterations, and only the remainder of the collection is searchedusing the modified query•Thus, in feedback effect evalu-ation, the H documents retrieved on any iteration areguaranteed to be N new documents; that is, documents not
used for feedback on any previous iteration.

Moreover, theperformance measures for the first (second, third) iteration are calculated from a ranked document list in which
the top N (2N, jJN) documents are the sane as those retrieved
previously*

Only the changes in the ranks of documents not

yet seen by the user is measured*Feedback effect evaluation gives overall results thatare deceptively low*

Because the top ranks ore frozen, no

newly retrieved document can achieve a rank higher than thatof any previously retrieved document*

With a constant32
feedback strategyf therefore, on the first (8econdf third)
iterationf the highest possible rank for a new document isN+l (2N+1* 3N+1).

For this reason* the feedback; efloct

evaluation is a misleading measure of the overall performance of the retrieval system* and should be used in conjunction with other evaluation methods*

Islation of thefeedback effect is primarily useful to compare different
feedback strategies from the viewpoint of a user in an interactive retrieval environment.

Figure 35 in Section VII-B

compares total performance and feedback effect evaluation ofsimilar feedback algorithms*
Howeverf one feature of feedback effect evaluation ispsychologically essential to a realistic relevance feedback
system; the guarantee that the N documents retrieved on any
iteration have not previously been seen by the user*For

this reason, new evaluation methods that provide thisguarantee without severely limiting the attainable retrieval
performance should be investigated*

Several such methods

are discussed in Section VII-B*
The results reported in this study include:
Total Performance:
1*

Normalized recall and precision

2.

Recall-precision curves with Quasi-Cleverdon
interpolation*

Feedback Sffect:1.

Normalized recall and precision

2#

Recall-precision curves with Neo-Cleverdon
interpolation*

3*

Document curves at several cut-off points32 a4.

T-testa and Wilcoxon Signed Hank teats of the normalised
measures and of recall-precision curves*

5*

Wilcoxon Rank Sum testa of normalised recall and precision*