X-l

X.

A Relevance Feedback System
Based onDocument Transformations

S. R. Friedman, J. A. Maceyak, and S. F. Weiss

Abstract
An information retrieval system using relevance feedback to modify
the document space is proposed.

A suitable algorithm is exhibited that

achieves high precision and recall.

1.

The Problem
An information retrieval system can be viewed as consisting of adocument collection together with procedures for accessing and retrieving
the documents in the collection. For evaluation purposes, the main goal ofsuch a system can be taken to be the retrieval of all documents in thecollection relevant to a request presented by a user. Hence, the problem
of retrieval is to relate the user's need to a collection of information.
How efficiently this relation can be generated depends in general on how
the document collection is organized.
In traditional retrieval systems, i.e. libraries, books are groupedby subject matter according to some classification system such as the Dewey
Decimal System or the Library of Congress System.

Such classification systems

divide human knowledge into categories such as physics, biology, etc. The
virtue of all such classification systems is that books similar in content
will often be located physically close to each other on the library shelves.

X-2

Libraries can be characterized as being static document spaces.
That is, documents are assigned permanent positions in the document spaces.
Static document spaces suffer from two major weaknesses. First,
given a classification system, it is possible to construct a request suchthat documents relevant to that request may not be located close to eachother. For example, the topic "aerodynamics of birds" might be discussed
in books which are primarily concerned with aerodynamics and only slightly
concerned with birds, or, alternatively in books which are primarily concerned with birds and only tangentially with their aerodynamics*
Second, given a classification system, it is possible to imagine adocument which is inherently difficult to classify. For example, should
Churchfs Calculi of Lambda-conversion be placed with computing texts or withpure mathematics texts?

The book relates to both areas.

Hence, static document spaces impose a classification system on theuser which may not always suit his needs. The userfs success with such asystem varies as a function of how much his needs agree with the subject
categories determined by the classification.
Most automated retrieval systems have inherited the static document
space. These systems are normally more flexible than libraries, in that subject categories are permitted to overlap. However, the fact remains that documents are assigned permanent positions in the space. Hence, as with libraries,
documents relevant to a given request might lie far away from each other inthe space.
In the SMART system, the classification of a document is based on
the importance of certain concepts in the document. A document is thenrepresented by a vector whose elements are the relative weights of theseconcepts.

A query is similarly represented. Hence, the query vector can

X-3

be thought of as positioned in the document space with access to all documents close to it. Since the user might not phrase his original query inthe best possible manner, relevance feedback systems have been suggested
to improve system operations. Most of these systems are based on successive
modifications of the query vector using feedback information from the user.
One such system described by Salton and Rocchio [h] has been implemented by
Riddle, Horwitz, and Dietz. [2] The main weakness of the system lies in
its inability to retrieve all documents relevant to a query when these documents do not lie close together in the document space.
The present study addresses itself to the question of whether arelevance feedback system cam be devised that will retrieve such documents.
The solution proposed is based on the use of a dynamic document space.
Every user who submits a search request is given access to the standard
document space. Subsequently, the document space is distorted in response
to feedback information received from the user in an attempt to bring relevant documents closer to the query. Hence, the query is kept static, andthe document space is altered. The standard document space is then nolonger viewed as an absolute structure, but as an initial structure which
can be altered to better suit the personal classification scheme of the user.
An implementation of such a relevance feedback system on the CDC l6oh
is described here. The system has been tested for the 82-document ADI collection using queries for which a priori relevance judgments are available.

2.

The Implementation
The initial task in implementing a relevance feedback system based

x-i*

on document modification is to devise an algorithm that distorts the document space to bring relevant documents close to the query*

The algorithm

actually used is based on the assumption that concepts which are strong(highly weighted) in the documents judged relevant by the user and weakin the documents judged non-relevant tend to characterize relevant documents.
Hence, the weights of these concepts should be raised in all documents inwhich they occur so as to increase the correlation between these documents
and the query.

Similarly, it is assumed that concepts which are strong

in the non-relevant documents and weak in the relevant documents tend tocharacterize non-relevant documents and should be decreased in all documents
in which they occur in order to lower the correlations.
The problem remains of how the concept weights should be raised
or lowered.

It seems natural that the amount of alteration for a concept

should depend on how much that concept characterizes the relevant or nonrelevant documents already seen by the user. That is, if a concept isjudged to be a good positive discriminator (i.e. strong in relevant documents, weak in non-relevant documents), it should be raised by an amountproportional to how strong it is in the relevant documents. Similarly,
concepts judged to be good negative discriminators (i.e. strong in nonrelevant documents, weak in relevant documents), should be lowered by anamount proportional to how strong they are in the non-relevant documents.
It also seems desirable to insist that the amount of alteration of a concept weight for a document should be proportional to that weight.

That is,if a concept which is marked as a good discriminator is very weak for aparticular document, then it should not be altered much since it doesnft

/

X-5

really characterize that document. On the other hand, if it is strong in
the document, then it should be altered more since it provides a bettercharacterization of the document.
These considerations were used to determine the final form of thealgorithm:a) Enter request. Retrieve the 10 documents having highest
correlation with the query.
b)

Use a priori relevance judgments to determine relevant andnon-relevant documents.

c) Compute R., N., and D. whereR.

The sum over all relevant documents of the weights of concept i
The number of relevant documentsNi

Sum over all non-relevant documents of the weights of concept i
The number of non-relevant documents

D. = R. - N.
iii

= The discrimination value of concept i.

d) Choose those concepts which seem to be good discriminators
between relevant and non-relevant documents, i.e. thosefor which |D. | >5. To these concepts, add all concepts which

occur in the query.
e) For the

i

i for

obtained in d), compute

1 2 ^F. , FT , F^ where1i_Weight of concept i in query
The sum of the weights of all concepts in query

F2
i

=

Sum of the weights of concept i in relevant documents
Sum of the weights of all concepts in relevant documents„3i_ Sum of the weights of concept i in non-relevant documents
Sum of the weights of all concepts in non-relevant documents

X-6

These three numbers are measures of the importance of conceptiin the query, the relevant documents, and the non-relevant

documents respectively.
f) For the i obtained in d), compute T. where
T.

= ajS

T.

• - OLJH , if D < & and if the query does not have con-

cept

a F. y if D > 8 , or if the query has concept i.

i.

g) Alter the document space by changing the weights of the conceptsi

obtained in d ) .

w? < — w. + w?T. if document
relevant, where w?
jj has not been judged non-is the weight of concept

i for document

and where the left arrow denotes assignment. If documentjhas been judged non-relevant, all its concept weights are set
to zero. This step has the effect of moving documents judged
non-relevant as far from the query as possible.
h) Return to a) using the same query and the altered document space.
Actually g) is performed during the search in step a). Thisloop is continued until the user is satisfied with his results
or until he gives up.
The algorithm makes use of three parameters: 8, QL, a • 8 is the
cut-off point for discrimination values. High values for 8 lower thenumber of good discriminators, aand OL are the respective weights given

to the query and to the relevant and non-relevant documents to denote theirimportance in adjusting the document space.
The algorithm was originally intended to use the cosine correlation
function for correlating the query to documents. The cosine correlation

X-7

function i s given bymE(qidi)

i=l

where mis the number of indexing concepts, q.

anddare the weightsof the iconcept in the query and documents vectors respectively. However,

early experiments with the algorithm gave better results with a modified
version of the cosine function.

In this version, the denominator is kept

constant (i.e. equal to its value in the initial search) through all updatesof the document space. This modification has the effect of magnifying allchanges to the document vectors. It was decided to experiment with each ofthese correlation functions in the algorithm.
The algorithm was implemented by modifying existing relevance feedback programs which used query altering.

Queries from the ADI collection

were processed using various choices for a , oc , 6 and correlation function.
After processing 11 queries, the program obtains precision-recall curves
averaged over all 11 queries. These curves are given in Figs. 1 through 6.

3. Experimental Results
In general, modification of the document space using relevance
feedback information leads to significantly better results than modification

x-8of the query. The highest averages of normalized precision and normalized
recall achieved by Riddle, Horwitz, and Dietz using query modification are•755^ and .8386 respectively.

Corresponding averages using document mod-ification are .8576 and .8871 for the modified cosine correlation function
and .7987 and .8806 for the standard cosine correlation function. This
improvement can also be seen by comparing Figs. 1 and 7. Pig. 1 gives
recall-precision curves averaged over 11 requests using document space modification.

Fig. 7 gives typical corresponding curves for query modification.

Tables 1 and 2 show the reason for this improvement.

Table 1 lists

the relevant documents retrieved by query modification and by document modification.

For queries 11, 12, lk,

and 15, document modification techniques

retrieved more relevant documents. Table 2 gives the documents retrieved
by both techniques for these queries and the number of concepts each such
document has in common with the relevant documents retrieved by only document modification techniques.

In most cases, this number is 1, indicating

very little similarity between the documents retrieved by both techniques
and those retrieved by only document modification. Hence, the improved results achieved by document modification are due to its ability to retrieve
documents unlike each other but relevant to the query.
Figs. 1 through 6 show the effect of different values of& onrecall-precision curves averaged over 11 requests. The curves for the third
iteration for8equal to 3 and 5 are almost identical and are better than

the third iteration curves for& equal to U .

Also, the curves for thesecond iteration for

6equal to 3 are better than the curves for thesecond iteration for

6equal to 5* Hence, smaller values of

the relevant documents to converge faster to the query.

8 causex-9

QueryNo.

9
10
11
12

DOCUMENT NUMBERSQUERY MODIFICATION
DOC. MODIFICATION
Retrieved

Not Ret.

Retrieved

Not Ret.

50,82

50,82
29,39,250,1150,2,39

43

79,81,8

4 3,79k42,9,25,7

4,25,7,^2,9

13

1,1^,37,27

80,65

1,37,65

Ik

20

33

20,33

15
26

11,37

36,6,32,67

11,37,6

5

5

28

69,9,48,70

69,9>8,70

11,29
81,8

14,27,80

32,36,67

Comparison of relevant documents retrieved byquery modification and document modification.
Table 1Query
No.

Retrieved by Queryand Doc. Mod.

Retrieved only byDoc. Mod.

No. of Concepts
in common

11
12

43
4
4
4
4

79
25

1
1
1

7
9
42

3
2
1
1
3

14

20

15

11

33
6

37

6

Relationship between documents retrieved byboth techniques and those retrieved only by document modification.
Table 2

X-10

|.0|-

o—o—a

•—•—•
A—A—*
o—o—o
a—D—O

_

*CL
•91

XQ

2 .6h

>

D

\

(A

* .4r-aoD- _ *«> - • -Xfc.

g .3k * ^ #Initial SearchFirst Iteration
Second Iteration
Third Iteration

^A

N ^

\

•ah
.1
J

I

I

I

I

.5

I

L

.6 .7 .8 .9 1.0

Recoilai * °2 " 1 ' 5 = 3> modified cosine

Document Space Modification
ADI Collection - Averages over 11 Requests
Fig. 11.0 r°—o—o^

.9
.8

V X°^

X

-~X

V

.7
c
.2 .6
CO

5 s
°-.4

\

•v

.3

Xo

A

X

\ «

.2
1

1 .1 .2 .3 .4 .5 .6 .7 .8 .9 1.0
10

1Recalla= a= l , 5 = 3 , modified c o s i n eDocument Space Modification
Fig. 2

fr

4
Oh

D

D

^o^g

9k
8h

H

b o

A>^

VN

A

5|-

•

A

3
2

_l

I

I

I

I

.1 .2 .3 .4 .5

I

I

I

I

.6 .7 .8 .9 1.0

Recalla=aI= l, 6 = li, modified cosine

Document Space Modification
Fig. 3

»

X-13

1.0
.9^
.8

X

*N \

7h

\ O

I I

Q

<>vX

.2
.1
J

I

I

I

I

I

L

.2 .3 .4 .5 .6 .7 .8 .9 1.0

Recall
L = O. - 1, 5 = 3, standard cosinea.
Document Space Modification
Fig. 1*

A

.Op
•9r
•8r
•7r
•6r
5
r
•4r
•3r
•2r
.1

.2

.3

i

i

I

I

I

.4

.5

.6

.7

.8 .9 1.0

1Recalla= a= 1, 5 = 5 * standard cosine

Document Space Modification
Fig. 5

L

X-15

1.0
.9

D—-D

D.

.8

•s.7|
|

v\.

*

o
o> .5 h

a.

' \ ,

•\

.4

A

O

.3
.2
.1
J

L

J

L

•

••

J

L_^

.1 .2 .3 .4 .5 .6 .7 .8 .9

Recalla= a= 1, 8 = 11, standard cosine

Document Space Modification
Fig. 6

i.ok
•

o_o

o

w
Q

0

^

O

\

.2

'

'

'

'

'

'

'

I

I

L__

.1 .2 .3 .4 .5 .6 .7 .8 .9 1.0

RecallTypical results using query modification
ADI Collection - 11 requests
Fig. 7

X-17

Figs, k to 6 give average recall-precision curves achieved by using
the standard cosine correlation function. Comparison with Figs. 1 to 3
shows that the modified cosine correlation function yields much better
results.

The modified cosine correlation function causes the relevant

documents to converge faster to the query.

In fact, as can be seen fromthe graphs, modified cosine achieves, on the average, better recall and precision after 2 iterations than standard cosine achieves after 3»
Experiments performed on the effect of varying
quite disappointing.

oc

and

oc

are

The results are extremely erratic and do not seem toyield any general conclusions about the effects of oc
particular, the use of different values of a

and

oc

and oc . In
for each iteration

causes undesirable instabilities such as relevant documents being very
nearly retrieved on the second iteration and then being moved far from thequery on the third iteration.

The results foroc

and ocequal to 1

are the best ones obtained in this investigation.

k*Conclusions
The effectiveness of relevance feedback is enhanced by the use ofa dynamic document space. Such a space enables relevant documents to bebrought close to each other and close to the query.

Moreover, this study

exhibits a relevance feedback algorithm based on document modification thatconsistently achieves better recall and precision than the algorithm basedon query alteration suggested by Salton and Rocchio, and implemented by
Riddle, Horwitz, and Dietz.

X-18

These conclusions suggest further areas for investigation. First,
there is a definite need for a theoretical study of document modification.
The present study presents a particular algorithm that works well. However,this algorithm is not necessarily optimal. Theoretical investigation
might uncover such an algorithm.
Second, a study should be made of the efficiency of document modification.

It is clearly a more time consuming method than query modifi-

cation, since changes must be made to the entire document collection as
opposed to being made only on the query.

However, further investigation

might show that document modification can be implemented without too greata loss in efficiency over query modification.

In this case, the improved

results achieved by document modification would justify the extra expenditure of computing time.
Third, an investigation should be made into the possibility ofusing both query and document modification.

The results achieved in thisstudy might be further improved by such a hybrid technique.

x-19

References[l]E. M. Keen, "Evaluation of Relevance Feedback Methods",
Report ISR-11 to the National Science Foundation, Cornell
University, June 1966.

[2]

T. Horwitz, R. Dietz, 0. W. Riddle, "Relevance Feedbackin an Information Retrieval System", Report ISR-11 to
the National Science Foundation, June 1966.

[3]

J. J. Rocchio, "Harvard Doctoral Thesis", Report ISR-10
to the National Science Foundation, Harvard Computation
Laboratory, June 1965.

[h]G. Salton, J« J. Rocchio, "Information Search Optimization
and Iterative Retrieval Techniques", AFIPS Conference
Proceedings, Vol. 27, Part 1, FJCC, 1965*[5]

G. Salton, Automatic Information Retrieval, Class Notes,
Computer Science ^35, Cornell University.