XI-1

XI.

Document Indexing Based on Relevance Feedback
T. L. Brauen, R. C. Holt and T. R. Wilcox

Abstract
A relatively simple method is proposed in this study for using
accumulated relevance feedback information in an automatic information
retrieval system to improve precision and recall.

This method involves

the dynamic modification of relevant document vectors after each retrieval run.

Experiments on a collection of 425 documents indicatethat this method does improve precision and recall significantly.

Moreexperiments must be conducted to perfect the method for large scale
practical applications.

1.

Introduction
User feedback techniques have been developed in an attempt toachieve higher precision and recall in automatic retrieval systems suchas SMART.

The user gives the system an indication of the relevance to his

query of certain documents.

This information about what the query should

retrieve is used by the system to modify query and document vectors sothat the desired documents are retrieved.

It is hoped that otherdocuments in the same area of the document space will also be relevantto the query.
Current proposals use this relevance information only in theprocessing of one query.

There is, however, reason to believe that thisinformation will also be helpful in the processing of similar queries

XI-2

from other users.

It seems quite reasonable to assume that a number ofknowledgeable users submitting similar queries may select roughly thesame set of documents as relevant to their query.

If this is indeed thecase, it will be of advantage to the system to save relevance informationfor each of the processed queries.

This information can be used as afirst approximation to future users1 responses in the feedback process.
As the relevance information for a given type of query builds up, thisfirst approximation should become a very good one and thus reduce thenumber of feedback iterations necessary to satisfy the users' requests.
The time saved can be used to continue searching for more relevant documents, thereby improving the recall.
Given that feedback information should be retained by the system,
it is clear that normal query modification will not achieve this aim
since queries are not a permanent part of the system.

It is, therefore,

natural to focus one's attention on the document vectors since they area permanent part of any retrieval system.
Some work has been done in the area of document vector modification.
Friedman, Maceyak and Weiss [1] warp the documents closer to the query andthus improve the chances of a better recall performance.
is, however, only temporary.

Davis, Linsky and Zelkowitz [2] also modify

the entire document space in an effort to improve recall.
is permanent.

This modification

The modification

These methods are disadvantageous in that they are time

consuming, the modifications being complicated, and requiring the manipulationof the entire document space.

These two methods would probably not be

feasible in a large retrieval system.

XI-3

2.

MethodThe problem is to find a method which retains the feedback

information, but which is practical in the sense that it uses limited
amounts of time and space regardless of the size of the document
collection.

To achieve these ends the authors propose the following

procedure.

The original query vectorq

is repeatedly modified, using

any of the existing relevance feedback techniques, until a query vectorq

is obtained which retrieves a set of documents D acceptable to theuser.

The terms and weights of the document vectors in D are now

modified to decrease the angle between each document vector

and the original query vactor

q .

d,
x

in D

Since the cosine correlation(formula (1))n(i)

cos (q
j=i

"1

V

j=i

j=i

4- \-\(where d. denotes the jterm weight of vector d.)

is used to determine the correlation between the vectors

and d.,ox
a decrease in the angle between vectors increases their correlation.
For the original query vectorqq

and its relevant documentsd,in D defined above, the document modification process takes place in two
steps.

For each relevant document vector, the query vector is firstnormalized to the "length" of the document vector by making the sum of
weights ofqequal to the corresponding sum for

d..

If

A

is theXI-4

sum of the weights of the query vector, and if

A

is the sum for the

document vector, then the normalized query vector is defined as:

a

= q
o

(A./A ) .
d q

o

(2)

The weights of the relevant document vectord.

are then modified

according to the formula:a(cp - d?)^oId? = d? +1 1

where 0<a<l.

(3)

By normalizing the query vector as in (2) the above modification is basedon vectors of equal length.
means

d.

Since (3) is a linear transformation, thiswill have the same length asfrom shrinking.*d.

and prevents document vectors

a. iq

With 0<a<l, the term

- d.)
o

may be fractional.

Inithis case, the fraction is rounded to the nearest integer.
Of course, in actual systems, a document term whose weightzero is not stored in the document vector.

d.

isThus, if a term appears witha non-zero weight inq
but is absent in d. , the term is added to the^oIdocument vector with a weight proportional to its corresponding weight in
the query vector.

Terms appearing in both the query and document vectors

lead to modifications based directly on (3), while terms appearing in neither
vector are not considered.
a

q

^o

and

d.
i

Fig. 1 illustrates the modification process forin two-space,^

The length of any document vector
Z

d? .

d,

equals the sum of its term weights

From (3)Ja3
1= a3 + a (or3 -

3

3

i

. i

z a = z aDD
E a3 « Z a3
i

D

.

a3)

O

1

1
3

+ a(z q.

Jsince

- z a3)oJ, i

I q3 = Z a3

i

. ^o

D

D

.

3

i

from (2).

XI-5
Term 2

Term 1Document Modification Process
Fig. 1

Two features of the modification process should be noted.

First,

only the vectors of documents judged relevant to the query are modified.
Second, if the same query is submitted by another user, the documents
judged relevant by the first user will be retrieved more quickly because
the modification has increased their correlation with the query vector.
Ideally, most of these documents will also be relevant to the second user,
and retrieval performance will therefore be improved.
Since queries are phrased in precise terms, similar queries may
reasonably be expected to map to similar query vectors.

If user B submits

a query similar to, but not the same as, a query previously submitted byuser Afthe documents judged relevant by user A should be retrieved quickly

for user B.

This is true because the modification process increases thecorrelation between user A's query vector and his relevant document vectors,
and because user B's query vector is similar to user A's query vector.

XI-6

The possibility of improved retrieval performance for resubmitted identicalqueries under the modification process is obvious, but is of limited value.
However, the fact that improved performance may also be expected for
queries that are somewhat similar,but not identical, gives this method
potential for practical application.

This improvement for queries thatare only similar is demonstrated in the experimental results given below.
The method takes little time to execute, and so is not costly to
implement.

Modification of vectors in large systems does, however, raise

the possibility of necessary reclustering for search purposes.
not as large a concern as may perhaps appear *This isIn large systems, the per-centage of document vectors modified for any query will be quite small, andifais small, any changes made for a query will be slight.

Thus,

reclustering need not be undertaken often, and may well be necessary no more
frequently than the reclustering required by the addition of new document
vectors.

3.

The Experiment
The method was tested using two document collections — the Cranfield

200 collection, consisting of 200 documents in aerodynamics, and 42 queries
for which relevance judgments are available, and the Cranfield 400
collection, consisting of 425 documents and 155 queries with relevancejudgments.

The latter is the Cranfield 1400 collection compressed to in-clude only those documents relevant to at least one query.

XI-7

The following is a summary of the test procedure.

The set ofquery vectors, along with a list of their relevant documents, and theset of document vectors are read into the system of testing programs.
The query vectors are ordered in a random sequence and divided into
two groups.

The first group is used by the system to modify the

document vectors while the second group is saved for later comparison.
For each query from the first group, the query vector and allits relevant document vectors are recovered from the query and document vector spaces.

The a priori knowledge of relevant documents forthe query simulates the results of relevance feedback iterations.

Eachrelevant document vector is then modified using the normalized query
vector according to formula (3). The modified document vectors are thenreturned to the document vector space.
When all relevant document vectors for all queries in groupone have been modified, the second group of queries is used to test
the effectiveness of the modification.

Each query from the second

group is submitted to a program which correlates it with vectors in themodified document space.

The ten highest correlating documents are

printed out along with the ranks of the relevant documents.
For each query submitted, global (normalized) precision andglobal (normalized) recall measures are computed.

If there are n

relevant documents in a space of N documents, and if r. is the rankof the irelevant document, the normalized precision is given bynP= 1- I (
C \>
norm
i=l

log r.
r ± -- \)loqi«llog i)
i) // log
log (N'/(N-n)(Nl/tN-n) Jnl)!
logIn!) |(4)

XI-8

and normalized recall is given bynR= 1 - (l/n)(\norm/(r. - i) / (N-n)).
1

(5)

i-1
These normalized measures are used because they reflect the rankingsof the relevant documents over the whole collection rather than rankings
up to some arbitrary point.

This eliminates the need for a subjective

choice of cut-off point which may bias the results. When all queries fromgroup two have been processed, an average normalized precision and recall arecomputed for all queries in the group.
The second group of queries is also correlated with document vectors
in the original, unmodified document vector space, and the same normalized
precision and recall measures are computed.

The average global precisionand the average global recall results for the two sets of correlations arecompared using a t-test.

From this, it is determined whether the differencesin the measures observed over the two sets of runs are significant.

4.

Experimental Results
A number of experiments were performed using the Cranfield 200

collection.

In each run, the set of 42 queries was divided into a groupof 37 queries, used to modify the document vectors, and a group of 5 queries
used to test the effect of these modifications.

Comparison of normalized

recall and precision results for the 5 testing queries submitted to themodified and unmodified spaces shows no significant change in performance.
These results are caused by the small size of the collection.

With 37

queries modifying about 4 relevant documents each, each document is modified
an average of 0.75 times. Thus, significant modification to the document

XI-9

vector space is not achieved, and results are much the same as those forthe original document vector space.

It also appears that few queries

have overlapping relevant documents.

As a result, modifications by

the first 37 queries have only a small effect on the relevant documentsof the 5 test queries.
A number of experiments performed using the Cranfield 400
collection produces more favorable results.

In each run, the set of

155 queries was partitioned into a group of 124 queries, used to modify
the document vectors and a group of 31 queries, used to test the effectof the modifications.

Experiments were run using two randomly generated

partitions, designated A and B and four values of a, ranging from 0.05
to 0.4.

In one special experiment, designated III-A', modifications

were made to a null space in which all document vectors were initialized
to zero, instead of to the Cranfield document vectors.

The results ofthese experiments are shown in Table 1.

;
Run
No.

IA
IIA

!

;

I IB
IIIA
^ ^
IIIB
IVB

-i
a

.05
.10
.10
.25

;

i

I

K Ave Normed P r e c i s i o n H Ave Normed R e c a l l
Mod
%
%
Unmod
Mod
1 Unmod
S p a c e S p a c e ChangeSpace S p a c e Change
.6274
.6274
.5434
.6294

.6788
.7073
.5766
.7182

+8.2
+12.7
+6.1
+8.1

.8891
.8891
.8439
.8891

.5963

+9,8

+2.4
+3.8
+2.2
+4.7

'j&iffy\/M9i,+2.8. 8 4 3 9 . 8 6 7 1 y/A/y/A

yMf / .&5 9 6&0 /A*A/s&\+9.7.25 1 .5434.40 1 . 5 4 3 4

.9100
.9231
.8624
.9309

|

.8439

.8595

Normalized Precision and Recall Results
Table 1*
For run IIIA' modifications were made to the null space.

+1.8

]

XI-10For the first part of this discussion of results, special experiment
IIIA' is ignored.

In all runs, the average normalized recall and precision

values for the modified document space are considerably higher for themodified document space than the corresponding values for the unmodified
space.

A t-test applied to the results presented in Table 1 indicates asignificance level of 0.01 or better in all cases.

Standard deviations overthe global precision and recall values for the 31 testing queries were
calculated for each run.

The standard deviations after the modification

were essentially the same as before.

This indicates that the modifications

provided a uniform improvement across the document space.
As can be seen from Table 1, varying a from 0.05 to 0.4 has no
significant effect on the amount of improvement.

It appears that an in-crease of a from 0.05 to 0.4 produces two conflicting effects on the search
results.

For small values of a only, small changes are made in relevant

document vectors and therefore the modifications have only a small effecton the search results.

The fact that significant improvement is neverthelessachieved indicates that the modifications are mostly beneficial to thetest queries.

In the case of large a rather drastic modifications are madeto the document vectors, and therefore the modifications have a large
effect on the retrieval performance.

At the same time, the drastic extent

of the modifications causes a more sporadic and less consistent improvement.
That is, beneficial modifications become more beneficial to the document
space while any non-beneficial modifications become more harmful.

The

net result is that variations in a in the experiments had little effect.

XI-11

The normalized recall values for the unmodified document space,
as given in the table, are close to 0.9.

Since the maximum possible

global recall is 1.0, a large improvement in the measure cannot be
expected.

In contrast, the global precision for the unmodified space

is about 0.6, leaving room for considerable improvement.

In theexperiments, normalized recall is improved by three per cent on the
average while normalized precision is improved by nine per cent on the
average.

It would appear that this difference between 3 and 9 per centreflects characteristics of the measures and the collection rather
than a characteristic of the method.
The special experiment IIIA1 is different from the rest in thatthe document vectors in the modified space are derived entirely independently of the Cranfield document vectors.

Experiment IIIA1 is

identical with experiment IIIA, except that a dummy document spaceis substituted for the Cranfield document space.

The effect of zero

document vectors is simulated in the dummy space by initializing the
document vectors to a single large term weight which is not used in the
Cranfield collection.

This simulation is necessary so that during

normalization, the query vectors would not be set to zero.

Using thenormalized recall measure in experiment IIIA1, the performance of the
document vectors derived solely from the 124 modifying queries is seen
to be surprisingly good — only 8.4 per cent below the performance of
the unmodified Cranfield document vectors.

One is tempted to hypothesize

that, given a few hundred more queries, the performance of the original
Cranfield vectors would be surpassed.
are necessary to test this hypothesis.

Experiments with larger collections

XI-12The most important overall result of these experiments is the factthat in all cases the modified Cranfield document vectors performed
significantly better than the unmodified vectors. From Table 1, improvements in normalized precision range from 6.1 to 12.7 per cent, while
improvements in normalized recall range from 1.8 to 4.7 per cent. This
seems to indicate that in an actual automatic retrieval system, where avery large number of queries are available for modifications and a can bemade small, this method could be of practical value. These experiments
tend to support the assumption that over a period of time similar query
vectors can be expected to be received requesting similar sets of documents.

5. Discussion
Several interesting aspects of this method should be mentioned.
As non-zero term weights are added to a document vector, the space required
to represent the vector increases.

In the experiments described here, themodifications added enough non-zero terms so that the storage required forthe document space increased by over 25 per cent.

In an operating information

retrieval system, a routine could be used to compress the modified document
space by setting small terms to zero.
With continual modification of the document vectors, the originalindexing information contained in the document vectors is lost. Equation C3)
can be rewritten as follows:d? - tl-ot) d? + aP
i

i

^o

.

(6)

XI-13

From equation (6) it is obvious that after one modification, a document
term

d.

contains the fraction (1-a) of the original document term

information (d.) and the fraction a of query term information (q ) .
Regardless of the values of the original document vector and the relevant
queries, the fraction of original indexing information remaining in adocument vector after n modifications is (1-a) .

For example, inexperiment IVB, where a = 0.4, the fraction of original indexing information
remaining in a document vector after 2 modifications to this document
vector is (1-0.4)

2= 0.36.

In an operating information retrieval system,a should be much smaller than 0.4, possibly on the order of 0.01, sothat a few "noisy" queries cannot seriously damage the document space,i.e., so that the indexing reflects the judgment of a large number ofusers.
In the Cranfield 400 collection, each query is associated with about
8 relevant documents.

Since 124 queries were used for modification, about

992 documents were modified.
modified 2 to 3 times.

On the average, then, each document wasThus, for a = 0.4, the preceding argument indicatesthat less than about 0.36 of the original indexing information remains after
the modifications.

Thus, in experiment IVB, normalized precision and recall

were improved by replacing most of the original indexing information ineach document vector by information derived from 2 or 3 queries.
It may seem disturbing that the information in the original
document vectors, which may have been constructed at considerable expense,
may eventually be lost to the system.

If desired, a simple modification to

the proposed method, such as flagging the original document term weights,
could insure that these terms would remain intact.

However, the advantage

of saving terms which are seldom if every used is not obvious.

XI-14

The results presented above suggest the following areas for research
and application.

Information retrieval centers might collect queries withcorresponding relevant documents. This information could form the basis
for future indexing schemes.
The proposed method might be used in a bootstrapping operation.
A minimal and inexpensive technique is used for the initial indexing of adocument collection. As the system handles more and more queries, theindexing is constantly corrected in a direction which improves performance.
Similarly, in a field where the vocabulary is changing, correction can
automatically be made in the direction of the new vocabulary.
Further research is required to see which of these suggestions isof practical value.

References]

Friedman, S. R. , Maceyak, J. A., and Weiss, S. F., A
Relevance Feedback System Based on Document Transformation, Report No. ISR-12 to the National Science
Foundation, Information Storage and Retrieval, Department of Computer Science, Cornell University, Ithaca,
N. Y., Section X, June 1967.

]

Davis, M., Linsky, M., and Zelkowitz, M. , A RelevanceFeedback System Employing a Dynamically Evolving
Document Space, Computer Science 221 Term Project,
Cornell University, Spring 1968.

XI-16

Appendix

The Normal Precision and Normal Recall measures shown in Table 1 areglobal measures.

It is often also helpful to visualize the effects ofretrieval runs with the use of non-global measures. The usual recall andprecision measures used for this purpose are defined as:

No. of relevant documents retrieved
D p/~i -a T l• ._ .

—

No. of relevant documents, .

No. of relevant documents retrieved
No. of documents retrieved

The measures are computed as each document is retrieved for a given query.
In the test runs, a record was kept of the first ten documents
retrieved for each query.

The following graphs show recall-precision

measures for four randomly chosen queries with respect to the first ten
documents retrieved in the modified and the unmodified document spaces.
For each query, three graphs are included, indicating the effects of document space modification by different values of alpha.

XI-17

Query 47
Modified
a = .05
Unmodified

J i L j_ J i '.2 .3 .4 .5 .6 .7 .8 .9 1.0
RecallFig.

Al

Query 47
Modified
a = .10
Unmodified

J I I I I i L.2 .3 .4 .5 .6 .7 .8 .9 1.0
RecallFig.

A2

XI-18

Query 47

1.0

Modified
a = .25
Unmodified

.9
.8
c-7
•w
2.6
i

I- •

•

£.4

/1

.3
.2
.1

i

J

I

I

.2 .3

I

I

I

I

I

L

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

RecallFig.

1.0 [-<

A3.

Query 115—
KAr\r\\f ioH———^— l Y l U U I I l C U.9a = .05
Unmodified

.8
c

.7

•2.6
"

5

£.4 _

>
>
<>
t^

. - '

.3 -

i

.2

'

%

•

I---

.1
1

1

L_ J

1

1

1

1

1

L_

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

RecallFig.

A4

XI-19Query 115
Modified
a = .1
Unmodified

I
!

I

!.

J I I L.2 .3 .4 .5 .6 .7 .8 .9 1.0
j

I

L

j_

Recall
Fig.

A5

•

• ' \

I
j

i

L

.2 .3

I
t.
J I I I L
.4 .5 .6 .7 .8 .9 1.0

JL

RecallFig.

A6

Query 115
Modified
a = .25
Unmodified

XI-20

Query 17
Modified
a = .05
Unmodified
•

i l -

]AA
/:

.4

/

i

3

• |
!

•2r

I L
I .2 .3 .4 .5 .6 .7 .8 .9 1.0
j

i

L

x J

Recall
Fig.
I-

A7

•

,k- •

Query 17
ModifiedA

a = .1
Unmodifiedi

I I I L.2 .3 .4 .5 .6 .7 .8 .9 1.0
-L

-L J

RecallFig.

A8

XI-21

Query 17
Modified
a = .25
Unmodified

A
j
J

L

J

-L

L

J_

-L

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

RecallFig.

A9Query 99
Modified
a = .05
Unmodified

A.

-L

J

I

I

I

I

L

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

RecoilFig.

A10

Query 99
Modifieda =.l
UnmodifiedII

ii ' I I I i I I L.2 .3 .4 .5 .6 .7 .8 .9 1.0

Recall
Fig.
•

ih-

All

•

Query 99
Modified
a= .25
Unmodified

i

j

i

L

j

I

i

i

I

L

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

RecallFig.

A12