ISR-9
August, 1965
XXIII.

RELEVANCE FEEDBACK IN INFORMATION RETRIEVALJ * J . Rocchio

SUMMARY
In evaluating the performance of a document retrieval system
one must attempt to isolate the critical variables which determine systembehavior. For this purpose a model is introduced which identifies indexing,
search request formulation,, and request-document matching as the three
primary functions of an automatic retrieval system.

Search request formu-

lation,, the responsibility of the users of the system, Is considered to be
the variable with the greatest potential variance.

In view of this, theidea of the optimization of search requests is believed to constitute a
primary possibility toward better control In evaluating indexing andrequest-document matching.

Investigation into request optimality leads Inturn to a method for improving search requests in an operational framework.
For this purpose the notion of interaction between a user and an information
retrieval system by means of relevance feedback is introduced. A processof request modifications is developed based on a sequence of retrieval
operations, such that after each operation the user Is allowed to communicate
his evaluation to the system. This information Is used as a basis foraltering the user's query. The modification algorithm is developed below
and some preliminary results are presented.

XXIII-2
1. System ModelA document retrieval system is assumed in which the index transformation consists of mapping documents and requests from the natural language
to multi-dimensional property vectors in an abstract space. The model isbased on the SMART retrieval system, in which a text is represented as anumerical vector in a concept space. The index transformation is effected
via a thesaurus mapping from word stems to concepts which may be augmented
by several other text processing techniques, for example, phrase identification and hierarchical transformations. The end product of the index
transformation is however a vector in the concept space in which the weightof concept i (that is, the ith component of the vector) is indicative of thefrequency of this concept in the original document.
The retrieval or searching process consists in matching a request
image against the set of document images which constitute the store. Various
matching strategies are possible; we will assume here that the information
contained in the index image of a test is represented by the orientation of
the concept vector in the concept space (that is, the matching process is
assumed independent of the magnitude of the concept vector) • Retrieval
therefore consists in locating the set of documents having an orientation(angular position) similar to that of the request image.

2.

Request Formulation
The process of request formulation is a complex one and depends onparticular attributes of the requestor, such as his knowledge of the contentsof the store, his knowledge of the indexing and searching processes of the

XXIII-3
system, his familiarity with the topic matter being searched, his personal
preferences as to vocabulary and style, etc.

In effect, the user must makea statistical decision based on his personal experience as to what request
is most likely to produce results useful to him.

Clearly the a priori

likelihood of a request satisfying the user's needs varies over a wide range
for any given retrieval system. For example, a user who needs to knowwhether a particular document is contained in the store can formulate arequest which will satisfy this need with perfect certainty, for example,
by submitting a request identical with the document in question. At theother end of the spectrum is the user who needs information on a topic
unfamiliar to him.

Clearly the probability of his being able to formulatea request which will retrieve the best set of documents satisfying his
information needs is very small.
Operationally then, information requests submitted to a retrieval
system vary over a wide spectrum of a priori likelihood of satisfying theuser's needs. It is then pertinent to consider techniques of reducing thisvariance in two distinct contexts. First, in an operational sense one would
like to process requests which"are optimized with respect to the cost of
retrieval, the cost of optimization and the value of the information to theuser.

Second, in the evaluation of information retrieval systems, it isdesirable to isolate the effect of the indexing process on retrieval performance from the effects due to request formulation. Thus the gross resultsof retrieval experiments carried out with a sample set of requests can beused to evaluate the indexing discipline with respect to that particularsample of requests.

If it were possible, however, to define an optimal

XXIII-4
request corresponding to any given request (for some fixed index transformation), retrieval results based on optimal requests would provide a muchclearer evaluation of the power of the indexing technique, since performancevariations due to request malformation would be eliminated.

3. Request Optimization
To define an optimal request, it is necessary to operate with an
explicit formulation of the request-document matching process• In accordancewith the system model outlined above, an appropriate matching function isthe cosine correlation of the request image and the set of document images
in the store. The cosine correlation of two vectors is defined by

r a&= i^k= cos (i'5) •Since the vector images produced by the index transformation arelimited to having nonnegative concept weights, this correlation induces aranking on elements of the store, equivalent to their angular distance fromthe request vector; (that is, 0 < f> < 1 corresponds to an angular separationof from 90 to 0 degrees).
Corresponding to any retrieval request Q, we assume the existence ofa subset D R , ( D « c D ) , of the set of documents contained in the store D.
This set is the set of documents relevant to the request Q and must be
specified outside the context of the retrieval system.
Having defined D R , an ideal request may be defined as one which
induces a ranking on the elements of D such that all members of Dr, are ranked
higher (that is, have a higher correlation) than all other elements of D.

XXIII-5
Since relevance is a subjective attribute of a given request-document
set pair, determined in theory by the individual requestor, there Is no
certainty that an ideal request (as defined above) in fact exists for agiven request.

In such a case one might say that the Indexing is definedfrom the point of view of the particular user,, since it does not allow
distinctions equivalent to those he can make. This of course will be thenorm rather than the exception, since the indexing process is designed toreduce rather than preserve information*

For this reason an unambiguous,

optimal request is defined as a function of D R , D, and the index transformation, which is unique for every nonempty unique subset DR of D.
An optimal request corresponding to a given subset D R of a store D,
under an index transformation T, is that request which maximizes thedifference between the mean of the correlations of the relevant documents(members of D R ) and the mean of the correlations of the nonrelevant documents(members of D not In D D ) .
rt
In mathematical terms the o p t i m a l r e q u e s t v e c t o r Qf corresponding
to a s e t DR C D i s defined as t h a t v e c t o r Q f o r which

i

ft

r

ft

is maximum, where n~ = n(DR) the number of elements in D^, and n = n(D) the
total number of elements in the store.
If we wish to consider only requests having nonnegative components(this corresponds to the assumption originally made about index images inthe system under consideration), then the problem is modified to maximizing
C subject to Q_. > 0.

XXIII-6
S u b s t i t u t i n g for p(Q,D,), and using vector notation r e s u l t s in

V ^

^ •E

Di

D.

c = -L/Q\ •i- n 0 VlQ!

D.€DR Pdll

! D il

R

or
D,

7

I

G =

IQI

D ^

1
S
»i

-—x
In
r R

° »i*\ NSince t h i s i s equivalent to G = Q • A, where Q i s a u n i t vector, c l e a r l y
Q. = kA (k being an a r b i t r a r y s c a l a r ) , orQ

optu =oIn

0 D ^ R lDil°"r'0 D X lDi'

it

1

1

It

Further, a simple proof shows that C is maximized subject to Q. > 0 (where
i ranges over all coordinates of Q) for the vector
Q , for Q , > 0
opt.
opt.
~
r
J

Q
=<
opt±
0

l

- l

for Q , < 0
opt±

Hence, under the assumptions made, an unambiguous optimal (for thecriterion stated) query exists corresponding to any nonempty subset D R of D.
In evaluating the effectiveness of automatic information retrieval systems,
this formulation of an optimal request provides the ability to isolate the

XXIII-7

effects of indexing from variances due to request formulation.

In i

an optimal request measures the ability of the indexing transformatii
differentiate a particular set of documents from all the others inore,

where the particular set in question, is assumed to have some intrinsic
association, specified independently of the system, that is, the sonsistsof the documents judged to be relevant to some particular topic.

U*

Relevance Feedback
The formulation of the optimal query corresponding to aset of documents has no direct implication on operational informal
retrieval, since the set of documents in question is the object of
retrieval search.

Thus there is no a priori way to make an optima

since having the ability to do so would eliminate the need for retri<This kind of circularity suggests a strong analogy to feedback control
theory.

Thus if we consider a sequence of retrieval operations si

with an Initial query Qf), which Is then modified on the basis of the output
produced by the retrieval system, using Q r as input, in such a way •modified query Q- is closer to the optimal query for this user, aanalogy to a sequential feedback system can be drawn.

Let the user -which of the retrieved documents (resulting from the search using (,.
relevant and which are not.
to the retrieval system.

This information constitutes an error sis

On the basis of the error and the origina.'i

it is then possible to produce a modified query (new command input)that the retrieval output will be closer to what the user desires, o;XXIII-8
that the modified query will in effect be closer to the optimal query forthis user's needs. The effectiveness of this process will depend on how good
the initial query is, and on how fast the process of iteration converges tothe optimal request.
On the basis of the formulation of request optimality, we then seeka procedure for using the relevance feedback from an initial retrieval operation to produce an improved query. Let Q Q be the original retrieval request,
and let the results of the retrieval operation be a list in correlation orderof the documents whose images are most closely related to Q p . The user
examines this list and specifies which of the documents in it are relevant
and which are not. Since the modification is to be based only on a sampleof the relevant documents (assuming that some are missing from the retrieved
list associated with Q Q ) , the modified request will be formed by adding tothe original query cL an optimal query vector based on the feedback information. The resultant vector (the new query) should thus be a better
approximation to the optimal query than Q0, and should therefore produce
better retrieval when resubmitted.
Hence we seek a relation of the form

Q 1 = f(QQ,R,S) ,where Qis the original query, R is the subset of the retrieved set which

the user deems relevant, and S is the subset of the retrieved set (based on
QQ) which the user deems nonrelevant. The form suggested immediately by theabove is

XXIII-9

1

2

3=1

1=1

where r^ = n(R), n ? = (S), R = |RpR2,...,Rn \ > S = {^pSg, ...,SnW

and all vectors are unit vectors. Thus Q- is the vector sum of the original
query vector plus the optimal vector to differentiate the members of the set
R from those of the set S.

In other words, Q. is the vector sum of Q 0 plus

the optimal vector for the subset of the store for which the user has provided relevance information.
The above equation may be rewritten in the formQl = n l n 2 Q 0 + n2 Z_x

V n l L V

R.£R

S.^S

l

l

Q-. may be restricted to having nonnegative components by setting
Q1# for Q ^ > 0

Q

l< = 10

for Q. < 0xi

The above represents the basic relation for request modification
using relevance feedback*This relation can be modified in various ways

by imposing additional constraints. For example, the weighting of theoriginal query (Qn) could be a function of the amount of feedback, such thatwith large amounts of feedback the original query has less effect on the

XXIII-10
resultant than with small amounts of feedback.

Another constraint, forexample, might be to regulate the number of nonzero components of the modified query on the basis of the degree of overlap of a component among therelevant set which is feedback.

Clearly there are a large number ofvariations to this basic relation which might be tried.
The modification process described is of course amenable to iterationand hence can be written in the general form

Q. n = f(Q.,R.,S.) ,l+ll' 1' l 'where Q. is the ith query of a sequence, and R, and S. are the relevant andnonrelevant subsets respectively, identified in response to retrieval withquery Q..

It is expected that the rate of convergence of such a sequence toa near optimal query will be rapid enough to make the process economical;
however, this will be investigated experimentally.

In any case, the con-vergence rate can be estimated by the user, since it is reflected in thestability of the retrieved output*
The user's original query serves to identify a region in the index
space which should contain relevant documents. Since he has no detailed
knowledge about the characteristics of the document images in the store, It
is unlikely that the vector image of his query Is optimally located. By
identifying relevant documents in the region, the user provides the systemwith sufficient information to attempt to produce a modified query which is
positioned centrally with respect to the relevant documents, while maintaining
maximum distance from the nonrelevant documents. This is possible, however,
only insofar as the index images of the relevant set are differentiable fromthose of the nonrelevant set.

XXIII-11
In a theoretical framework, the request optimization process focuseson the power of the index transformation to distinguish sets of associateddocuments within the store by eliminating variances due to particular query
formulation*

In an operating context, relevance feedback provides atechnique whereby the system user can extract the full power of the index
transformation to his retrieval problem, at the cost of iteration (possibly
on a sample collection from a large store) .

5. Initial Experimental Results
To test the effectiveness of the technique of relevance feedback asoutlined above, some experiments have been conducted using the SMART
retrieval system.

A set of 17 requests which had been run through various

processing options of the SMART system was used as a test sample. For eachrequest the output resulting from a cosine correlation run using the SMART
thesaurus (version 2) was examined. From the initial portion of theretrieved list (source documents having high correlations), two sets of
documents were selected, one containing relevant documents and one containing
rionrelevant documents. The vector images of the documents (given by the
SMART thesaurus) together with the image of the request were used as input
to a FORTRAN program which produced a modified vector suitable for input toSMART-The request modification algorithm used was as follows. The firststep of the process applied the optimal request algorithm directly to
produceXXIII-12
n

n

l

2

/
Q

n n

l 2 Q 0 + Q 2/^ R i "" D liL S i^
i=l
1=1

l^

where R.(i=l,n-) constituted the relevant subset identified, and S.(i=l,n0)
i

l

l

£

f

the nonrelevant subset , (the R. s and S.'s being normalized vector images
9

i

i

u

of the documents in question under the index transformation). Since the
SMART system is designed to operate on document and query images having
nonnegative components only, the vector Q. was modified by setting

! =<
!1 .

Qx

for Q

> 0

0

f o r Qx < 0i

A further modification was introduced to keep the modified queryfrom becoming too specialized to the relevant set which was fed back. This
modification was incorporated since relatively small amounts of feedback were
to be tested.
The problem was therefore designed to allow a nonzero component in
the resultant query image if and only if it occurred in Q and was either(a) in Qor (b) occurred in at least ru/2 of the images of the relevant set,

and in more relevant vectors than nonrelevant vectors.
The amount of feedback, that is, the number of relevant and nonrelevant documents returned was varied from request to request with the two
sets kept roughly equivalent.

In some cases, where there were only a few

relevant documents to a particular request, only the relevant documents wereXXIII-13

Document
Rank

Document
Number

1
2

167
166

3"

1

Correlation

User Feedback.4-6

not relevant
not relevant

188

.A3
.AO

U

221

.38

relevant

5
6

3U
55

.38
.37

-

7

79

.36

relevant,(a)Retrieval results using original queryn
I-R Indexing" including user feedback

Retrieval Results
Using Original Query-——

Ranks of
Relevant
DocumentsiDocument
NumberRanks of,> ,' Document
Relevant,,
numbernDocuments!

Correlation

221

13

3
80
AS
126

.25
.21

23

Results Using Query
Modified by User Feedback

l

A
7

15
17

-

.38
.36

79

]

1

79

.54

2

221

.A'7

.26

A

3

.26

5
6

126
80

.33
.31
.30

:

j

AS

25
1

Recall1.976

Precision .728(b)Correlation j

Recall
1

Query Processing Using Relevance Feedback

J

.991

Precision .928

Comparison of search results using
original and modified queries

Figure 1.17
I|XXIII-14

iDocumenti RankDocument
Number

1
2

351
353
350

•5

Correlation

User Feedback

.65
.42

relevant

163
82

4
5
6

1
208

7
8

225

9
10

54

relevant.41.36

relevant

.35
.32

-

.27

not relevant

.25
-24

not relevant--

not relevant
.21
335
1
Retrieval results using original query for"Pattern Recognition" including user feedback
i

(a)

|

—

_

_

_

Results Using Query
Modified by User Feedback

Retrieval Results
Using Original QueryRani?: s of
Relevant
Documents

Document
NumberCorrelation

Ranks of
Relevant
Documents

1

351

.65

1

2

353

•42

2

350

.60

3

350

•41

3

353

• 55

4

163

.36

5

163

.37

6

1

•32

6

1

.32

9

54

.24

7

54

.29

26

205

.17

11

314

.23

27

224

.17

16

205

.19

33

314

.16

17

39

.19

L 3A

39

.12

30

224

.16

i
I

j

Recall.972
Precision .864(b)JDocument
_
- . .
... ,
: Correlation
Number1
i.66
351

Recall.989
Precision .923

Comparison of search results using
original and modified queries

Query Processing Using Relevance Feedback
Figure 2

XXIII-15; Document
1 RankDocument
NumberCorrelation

U s e r Feedback

1

157

.42

relevant

2

165
362
296
308

.4-0

relevant

.39
.37
.37
.37
.36
.36

not relevant

3
4
5
6

307
226
88

7

1

8
(a)

not relevant
not relevant-|

Retrieval results using original query"Analog-Digital" including relevance
feedback

Results Using Query
Modified by User Feedback

Retrieval Results
Using O r i g i n a l Query
Ranks of1 Relevant
Documents

re levant" rDocument \ n-. .

.
Numberi Correlation

1

157

.U2

2

165

A
19
21

rr

Ranks of
Document
Relevant
Number| Documents

Correlation

296

CO

-40

1
2

157

.56

296

.37

3

• 53

U2
46

.27
.26

U
A0

165
U2

.U2
.20

Ljo

!

Recall.984\

Precision .870
(b)

Recall.983

Precision .918

Comparison of search results using
original a n d modified queries

Query Processing Using Relevance Feedback
Figure 3

XXIII-16
H
M

X3

3

cd O
r H 'Li
0
PH
h 0.)

cd
co a r-,•H O C3
U -H
W

•• JH
CO O CD
3
O H
O
f-l
3 0 5
cd d • H
CO »H W
0 CO
J2 O 3
FH
O cy

>

:^

nj
0 CO
*H
0
QH - H• H JH
T5 0
O
3

o
co
0
•H
PH

0

M
o

i-S

ro

3 7 j ^
C*» 0 CO0 -P

to

H C*« CO
0
cd
•H 0
3

+3 o a*,H d
0
C! cd JH
H

r-

>

0 ,O
d
h rH
G
'V 1 p$ a0
H > * to

I vp

H ^
i>
cd
o T5 r H
H

H
cd

o
0)
*i

-<*•

CN

0

0
r-1 >HJH

CH
0>GO • H
3 rO" O
CO O
f-H ^
^3
0
0
CO U )
0 cd• H <L,o JH 0•H 0>
CQ d cd•H Q > ^
O
a) TJ
d
•M
{X, cd

>
a

-T
0
r-i
3

bfl

•H
r>H

XXIII-17

ci H

O
03 J *
CD o
•H cd
U £>
0 n 3 ^
2 CD CQ
Of 0) -P

CO

tx,

H

CO
Q)

0 3
o a'
+3 a 0
•H
aJ U
05
•H

r

a 0> ~a

H

rH

a
0(4
Pn

O

JH

v.O

d

>» CO

H ,£

3

« % £

303
O

CD

C>

M

<y

H

O

CO

c^

vO

a
o
•H
CO
•H
O
0

*-.

Pi

cv

O

T3
0

CD

CO

b£)

>

0

cd

o

U
©

0
>

• H 3 05
CO Of^-x
•H
O TJ

a)
PL,

CM

o

rr;

a
05

c
f-H

n3 rH
o 0
a) •H U

CO T3
3 O
CO S
*H

Li

0

3

•H
fr.

mil-isidentified to see what would happen under these circumstances. Figures 1,
2, and 3 show the results of one iteration of the search request modification process for three different queries•

In the first two cases there issubstantial improvement in both the recall and precision evaluation measures(shown for the original and modified query), while in the third case only theprecision measure is increased.

It is important to note that while the query

modification process improves the performance with respect to the relevant
documents identified by the user, as one would expect, it also in general
Improves performance with respect to other relevant documents. This is
illustrated in Figs • U and 5, which show precision versus recall averaged
over a sample of 17 search requests. Figure 4- is the result of averaging theinterpolated precision for each request at recall values of 0.1 k, forintegral values of k from 1 to 10. Figure 5 is a precision versus recall
curve for the same set of 17 queries produced in a different way, This plot
results from choosing a cut-off after m consecutive nonrelevant documents(m ranging from 1 to 20), and averaging the precision and recall values foreach request at each cut-off point to get a single average point which isplotted.
The general conclusion which can be tentatively drawn at present isthat relevance feedback provides a powerful tool for improving performanceat the cost of iteration of a request through the system.