XII-1

XII. The Evaluation Problem in Relevance Feedback SystemsbyHarold A. Hall and Nelson H. Weiderman

Abstract
The problem of evaluating relevance feedback systems is discussed in
the context of the operating SMART document retrieval system.

A ranking effectand a feedback effect are defined and are related to the changes that occur inprecision and recall during successive feedback iterations. An evaluation
scheme which isolates the feedback effect is presented.

1.

Introduction
The SMART document retrieval system is a user-oriented system in which

a list of documents is presented to the user in response to a natural language
query.

In any such system the practical assumption is made that the user will

be unable on his first try to formulate a query which is optimal for his particular needs. In light of this, a document retrieval system must take advantage
of computer-user interaction in order to reformulate the original query to obtain more desirable results. In an operating system the specific search strategy
is initially unspecified so that it may be adapted to the needs of the user, [l]One strategy is to use relevance feedback. [2,3,b]That is, the user

is presented with a number of documents and is asked to specify those which are
pertinent to his interests. The terms in the documents judged relevant arethen added to the terms of his original query to move the query in the document1.

For detailed information on the SMART document retrieval system, see [l]XII-2space to an area where additional relevant documents are present. This iterative procedure may be continued until the type and amount of information desired is retrieved.

The assumption is made that documents of a similar

nature lie in close proximity to one another in the document space. [2]Although the user's job is simply to make relevance judgments, a
relevance feedback system may be varied by changing many parameters, e.g.
the number of documents fed back, the relevance weighting factors used, theuse of negative feedback (deletion of concepts appearing in documents notdeemed relevant), etc. It is the purpose of this study to examine thecriteria with which a relevance feedback system (using a given set of parameters) may be evaluated.

2.

The Present Evaluation System
A "perfect" document retrieval system would retrieve all those

documents which are relevant and none which are not relevant. To measure
the extent to which a system approaches this ideal situation, the following
two measures have been devised:
Recall =Number of relevant documents retrieved
Total number of relevant documents_. .
Number of relevant retrievedr£r1
Precision • —---——-----—-—•-—---———— : L5J
Total number retrieved
Using a given ranking of documents together with their relevance judgments,
one may calculate recall and precision after each n documents retrieved.
These points are plotted on a graph with recall on the abscissa and precisionon the ordinate as in Fig. 1«

For a given document ranking the precision andrecall remain at zero until a relevant document is found, at which time recall becomes l/r and precision becomes l/n, where r is the total number ofRank

Relevant

1
2
3
h.
5
6
?
8
9
10
11
12
13
lU
15
16
17
18
19
20

X

X

X
X

X

RecallPrecision

0.0
0.2
0.2
0.2
O.k
O.k
O.k
0.6
0.8
0.8
0.8
0.8
0.8
0.8
1.0
1.0
1.0
1.0
1.0
1.0

.0000
.5000
• 3333.2500.Uooo• 3333.2857• 3750.kkkk.1+000
.3636
.3333
.3076
.2857
.3333
.3125
.29U1
.2777
.2684
.2500

1

.6 L
2

2 .5
in

/| ^ ^ ^

0

/1

A

UJ

•

°= .3
0.

.2

!
p
^
V
' >i

1

L

1

1

1

-J
.4

1
.5

1
.6

j
.7

1
.8

1
.9

1
1.0

RECALL
Pig. 1:

Peak-Interpolated Recall-Precision GraphXII-1*

relevant documents in the collection and n is the number of documents
retrieved.

Recall now remains constant while precision decreases until

another relevant document is found, at which time the recall jumps to2/r and precision becomes 2/n*, and so forth. The result is a set of points
arranged on r vertical lines equally spaced along the abscissa*
A smooth curve is obtained by interpolating between therpointswhich represent the relevant documents (the peaks of the graph if thepoints are joined), and the point (0,1) if the first document is not relevant or the point (0,0) if the first document is not relevant.

Graphs ofthis type are generally averaged over a number of queries at twenty pointsof recall at intervals of 0.05»
Two points should be made about these graphs. First, only
points are used in their construction.

r+lThis may cause serious difficulties

when the number of relevant documents is small. For example, if there is only
one relevant document, it is meaningless to ask what the precision is at
any value of recall other than zero or one; hence at all other points ofrecall, the value for precision is interpolated.

Second, it should be

noted that graphs constructed in this manner do not represent absolute recall
and precision.

In many cases this fact causes little or no difficulty forevaluation, since only relative differences between various plots are being
considered.

It is restrictive only in cases in which one would like to knowwhat the precision and recall are after a certain number of documents havebeen retrieved.
graphs.

This particular information is not available from theseXII-5

In computing standard recall and standard precision it is necessary to
pick a cut-off value to distinguish between documents retrieved and documents
not retrieved.

Since it is desirable to use a measure of retrieval efficiency

which is independent of the distinction between retrieved and nonretrieved
documents, the present system uses recall-like and precision-like measures,
termed normalized precision and normalized recall, which take values between
zero and one, and can be interpreted as approximations to average standard
recall and average standard precision for large document collections. Specifically, if R.

is standard recall andoP.

is standard precision afterjJdocuments retrieved, we have
N
norm

N /

N
j

0=1
where

N

norm

N /

*j

j=l

is the total number of documents in the collection. [6,7]3. The Problem
In reappraising an evaluation technique the basis for the reappraisal consists in a thorough examination of the problem being considered—in this case, relevance feedback.

The aim of a document retrieval system

is to maximize the number of relevant documents retrieved while at the sametime minimizing the number of non-relevant documents retrieved; i.e., tomaximize recall and precision.

Therefore, the aim of a relevance feedback

system should be to maximize the number of relevant documents found using
relevance feedback over and above the number of relevant documents foundwithout such a system.

In other words, for a given number of documents

retrieved using relevance feedback one wishes to retrieve more relevant

xil-6

documents than would have been retrieved had the user looked at the same
number of documents after an initial ranking.
To this end it is the job of an evaluation scheme to compute precision and recall for the initial search and the feedback iterations insuch a way that meaningful comparisons can be made between them.

In partic-

ular, one must distinguish between two phenomena occurring simultaneously
to change precision and recall. First, there is the relative change in recall and precision due to a shift in document rankings from one iteration
to the next, herein called the ranking effect.

Second, there is the re-lative change in recall and precision which occurs when new relevant documents are found in successive iterations, herein called the feedback effect.
Unfortunately, there is no way of distinguishing these two effects using
the peak-interpolated precision-recall curves. In fact, the ranking effectcompletely swamps the feedback effect.
Evidence in support of this assertion is available in the datacollected by Messrs. Riddle, Horwitz, and Dietz in a prototype study of
relevance feedback, [h]After each query perturbation, documents wereranked in correlation order without regard to whether any given document
was retrieved on a previous iteration or not. Fifteen documents were retrieved on each iteration. For the particular set of parameters--namely
increasing alpha strategy with cosine correlation—which were judged optimal in the study using an initial search and three feedback iterations, it
was found that of thirty-four queries tested, eleven of them retrieved allof the relevant documents on the initial search, twelve others retrieved
no new relevant documents after the initial search, and for only elevenxil-7

were new relevant documents retrieved as a result of relevance feedback*From

the same data it was found that relevant documents retrieved on the initialand successive searches increased an average of 5.5 positions in the rankings
by the third iteration. On the other hand, for the same thirty-four queries,
only sixteen new relevant documents, out of ninety-two relevant documents retrieved, were retrieved as a result of relevance feedback.
Before embarking on a plan for an alternate evaluation technique,the distinction between the ranking effect and the feedback effect and thereasons for making any distinction at all should be made clear. The ranking
effect is due to a change in the ranks of relevant documents already retrieved.
Since the retrieved documents axe the very documents used to perturb the queryin the first place, their correlations with the perturbed query will undoubtedly
increase for successive iteration, and these documents will tend to move up
in ranking from one iteration to the next. Assume, in order to isolate theranking effect, that no new documents are retrieved for successive iterations,and that all relevant documents are weighted equally in each iteration. Then,in the limit, the iterated query will approach the centroid of these relevant
documents, since the original query, unless weighted each time, would become
negligible in its effect. The ranking effect is of significant interest in the
study of Rocchiofs notion of an optimum query and its generation by a request
optimization algorithm. [2] Hence the ranking effect measures the extent towhich a query has been perturbed toward the centroid of the set of previously
retrieved documents.
To isolate the feedback effect, one must hold rankings of previously
retrieved relevant documents constant while retrieving documents not previously
evaluated by the user. Hence the feedback effect measures the effectiveness ofxil-8the perturbed query in bringing new relevant documents to the attentionof the user.
The fact that these two effects should be separated is clear*
Certainly one should distinguish between the case in which successive
iterations do present new relevant documents to the user, and the case inwhich they do not*

It is therefore obvious that determination of the feed-back effect is essential in the evaluation of a general purpose relevance
feedback system for document retrieval. For this reason, an evaluation
scheme which isolates the feedback effect from the more prominent ranking
effect is presented.

U.

The Solution
Although the retrieval system is not so restricted, assume forpurposes of illustration that the number of documents retrieved at any one
time is equal to some constantk.

The proposed system then behaves asfollows:
The user submits his request.

In general, the system matches therequest against a subset of the document collection and ranks the documents
in correlation order.

It returns to the user those kcorrelate most highly with the query*documents which

The user now examines the retrieved

documents and assesses their relevance to his request. Using these relevance judgments, the system generates a new query and then ranks the documents with respect to this new query.
those

k

The system now presents to the usermost highly ranked documents which the user has not already seen.

Thus, after again making his relevance judgments, the riser will have considered2kdifferent documents. The number of iterations allowed is aparameter of the system.

XII-9For evaluation purposes, the documents retrieved on the initial search
are ranked

1

to

k

rankedk+1

toforth.

Thus a set of rankings might appear as in Fig. 2. A stylized recall-

2k

throughout, those retrieved on the first iteration arefor each iteration "beginning with the first, and so

precision graph for this system appears in Fig. 3 in which recall and precision are plotted after k, 2k, 3k,..., nk

documents, wherenis the total

number of searches.
Consider the following formalism.
the ith iteration afterjDefinedocuments retrieved.

precision on the ith iteration afterjR..

to be the recall on

Similarly

documents retrieved.

P..

is theThe objectiveof a relevance feedback system as stated earlier is now the maximizationof the differences, afterj

documents retrieved, between the number of

relevant documents retrieved on the ith iteration and the number retrievedon the initial search.
find

max

In terms of recall and precision the objective is to(R. . - R-.)
ij
Oy

and

s.p.c.
for eachjas(P. . - P_)
ioOys.p.c.
i ranges fromiterations. R 0 . and P
j

max

1 to

n , wherenis the number ofare recall and precision, respectively, after

documents retrieved on the initial search; and the abbreviation s.p.c.

indicates that the maximums are to be taken over all jsystem parameter changes.
If R

is the set of all recall differences, a graph of the points of R

might appear as in Fig. k.

(Points are joined to produce continuous curves.)

A similar graph is constructed in Fig. 5 for P, the set of precision differences. The objective is therefore, in terms of the graphs, to maximize
distances between the R-jand

P-j curves.

XII-10In terms of Fig. 3, the differences between numbers of relevant documents found are taken along the dashed lines, with vertical displacement
indicating increased precision and displacement to the right indicating increased recall. It should be noted that although it is hoped that both
recall and precision will increase from one iteration to the next, it ispossible for one or both to decrease.
Since new documents are retrieved each time, rather than old documents in new order, the ranking effect is eliminated, and all the improvement between curves on the graphs of Figs. 3, k, and 5 is due to relevance
feedback.

Normalized recall and normalized precision are computed andbased on the rankings indicated above.

5.

Preliminary Results
The evaluation scheme was tested on two document collections, theeighty-two document American Documentation Institute (ADI) collection derived from abstracts of papers on information retrieval, and the two hundred
document Cranfield collection derived from abstracts of papers on aerodynamics.

Identical input parameters were used for the two collections;that is, the user is presented five new documents each time and on each of
three iterations the weights of the concepts in the original query and theweights of concepts in newly retrieved relevant documents were added to thequery of the previous iteration.
For this particular choice of parameters, the results show a significant difference in relevance feedback performance between the ADI and the
Cranfield collections. This difference is illustrated in the R-j and P-j

XII-11

Fig. 2
Hypothetical Document Rankings for k=3«
(Cross-hatched areas designate documents r e t r i e v e d . )

.6

•5h
k/
^3rd Iteration
2nd Iteration
1st Iteration

2.3
U
LLI

oc .2

Initial Search

.lh
JL

-L

-L

.4

.5

.6

.7

_L

-L

J

.8

.9

1.0

RECALL
Pig* 3s

Stylized Recall-Precision GraphXII-12I i= 0Stylized R-j Graph of Recall DifferencesFig.

hStylized P-j Graph of Precision Differences
Pig. 5xil-13

curves of Figs. 6 and 'J.

In the Cranfield collection, relevance feedback

accounts for an increase in standard recall, averaged over forty-two
queries, of .0857 at a retrieval level of twenty documents. The corresponding increase for the ADI collection, averaged over 35 queries, isonly .0053*

In the Cranfield collection, average precision increased by.027U at a retrieval level of twenty documents, while in the ADI collection,
it increases by only .001^.

Thus, for this particular set of parameters,

the Cranfield collection is ten to twenty times more effective in increasing
precision and recall due to relevance feedback.
Several reasons may be suggested for this difference in performance.
Since the document representations of the two collections were constructedby the same technique (document vectors consisting of thesaurus concept
classes), it appears that the difference in performance is a result of the
document collections themselves.

In particular, the Cranfield collection

has, in general, both longer queries and longer documents than the ADI
collection.

This may indicate that relevance feedback performance is, inpart, a function of how detailed are the representations of documents andqueries with respect to the actual documents and queries. The differencein performance may also be due to a closer clustering of relevant documentsin the Cranfield collection than in the ADI collection.
Differences in document collections and the determination of a setof parameters which yield optimum retrieval using relevance feedback areareas for further investigation, but are not the object of this study. The
applications of the evaluation scheme are presented merely to illustrate
its effectiveness in distinguishing the feedback and ranking effects. Pre-XII-1^CRANFIELD

<

o
UJ

ADI
.06
-1
-1
<

.04
.02

UJ
(T

0
-.02

X
10
RANK

15

J*

20

Increase in recall due to the feedback effect in
the Cranfield and ADI Collections
Fig. 6

XII-15

CRANFIELD

<
UJ

ADI

Increase in precision due to the feedback effect in
the Cranfield and ADI Collections
Fig. 7

xil-16

vious results have indicated that the combined ranking and feedback effects
produce significant increases in recall and precision. [6] The results ofFigs. 6 and J indicate that the feedback effect was negligible in producing
increased recall and precision in the ADI collection, whereas in the Cranfield collection, the feedback effect is definitely evident.

6.

Conclusion
In some iterative or comparative procedures in document retrieval-such as searching for an optimum query or comparing various correlation coefficients—the measure of effectiveness of the procedures is the extent towhich the rank of the documents increases.
The point of view taken herein is that for a relevance feedback
system the measure of its effectiveness should be a measure of how many
new relevant documents are retrieved as a result of feedback.
From examination of results previously obtained in relevance feedback, it is clear that the present evaluation scheme does not include thisimportant measure. The measures of precision and recall do not separate
the effect of increasing the ranking of documents from the effect of retrieving new relevant documents.
The evaluation scheme presented herein has several advantages.
First, it isolates the feedback effect from the more prominent ranking
effect by keeping retrieved document rankings constant. As a consequence,
one is forced to use the convention that once a document is retrieved, it
remains retrieved in the evaluation. This is consistent with the actual
environment in which such a system would be used. Second, the system offers

XII-17

the advantage of presenting absolute measures of precision and recall,rather than possibly unreliable interpolated values. That is, instead ofusing

r+1 points (where r

is the number, usually a relatively small one,of documents relevant to a particular query) to plot a graph of precisionand recall as is presently done, it is possible to use a large number ofpoints by computing precision and recall at each level of retrieval. This
technique enables greater discrimination between similar cases. Third,
the system clearly illustrated the precision-recall trade-off by separating these two measures as in Figs, k and 5. Finally, the evaluation
permits comparisons of precision and recall at a fixed number of documents
retrieved.

XII-18

References[l]G. Salton and M. E# Lesk, "The SMART Automatic Document
Retrieval System—An Illustration," Communications of theACM, Vol. VIII, No. 6, June, 196k.

[2]

J. J. Rocchio, Harvard University Doctoral Thesis, Report
ISR-10 to the National Science Foundation, Chapters 3, 5*[3]J. J. Rocchio and G.Salton, "Search Optimization and
Iterated Retrieval Techniques," Proceedings of the Fall
Joint Computer Conference, Las Vegas, November, 1965*

Ik]

w. Riddle, T. Horwitz, and R. Dietz, "Relevance Feedbackin an Information Retrieval System," Report ISR-11 to NSF,
Chapter 6.

[5]

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

[6]

G. Salton, "The Evaluation of Automatic Retrieval Procedures—Selected Test Results Using the SMART System,"
American Documentation, Vol. XVI, No. 3, July, 1965*[7]

0* Salton, Automatic Information Retrieval, unpublishedmanuscript (class notes), Chapters 1, 9*