Summary
Several algorithms that allow user internction with
cm automatic document retrieval system by requesting
relevance Judgments of selected sets of documents areinvestigated.

All relevance feedback algorithms tested

improve the average retrieval obtained.

The improvement

caused by relevance feedback is ^re^ter in a larger^ more
realistic document collection (Cranfield 200) than in asmaller and less realistic collection (ADI).
No single feedback strategy is found to Kive superior
retrieval for all queries.

Algorithms using only relevant

documents for feedback can bo made effective for queries
that retrieve no relevant documents on the initial searchin two waysf by supplying additional documents for relevancejudgments or by using non-relevant documents for feedback.
In general$ the performance of negative feedback
algorithms (those using non-relevant documents for feedback)is variable.

Negative feedback gives worse performance onsome queries and better performance on others than the moreconsistent positive feedback strategies.

On the average,

negative feedback moves the query closer to the optimum
query defined by Rocchio than does positive feedbackf but does
not differ significantly from positive feedback from theviewpoint of the user during feedback•A study of selected subgroups of queries provides three200interesting results*

Firstf movement oj the query constructedby the tfocchio strategy further away from the original query
rather than back toward it on the second iteration is related
to poor performance and poor initial oeardh results•

This directionof query movement could be a result of inadequate feedback* or
it could be an attempt to compensate for a poor original query*
Second, the queries for which the Rocchio strategy gives lessimprovement than positive feedback have the worst initial
search performance9 queries for which positive feedback isinferior have much better initial search periormance* andqueries for which negative and positive feedback are equal
have the. be.it initial search retrieval*

Third t queries

having few concepts and few relevant documents and queries
having many concepts and few relevant documents tend to giveless improvement with negative feedback than with positive
feedback*, while queries for which the number of concepts andnumber of relevant documents are directly related give more
improvement with negative feedback*If a predictor of the numberof relevant documents available for each submitted query canbe /oundf this relationship could be used to select the feedback
algorithm appropriate to each query*
The observed contrasting behavior of negative and positive
feedback algorithms can be explained by a hypothesis presented
in Section VTI-C*
Hypothesis)
A hypothesis is presented that explains some of the observed

201
performance differences between the negative feedback strategies
and the positive feedback strategies investigated* and:isconsistent with all experimental results reported*Hypothesist
For most queriesf for every vector v contained in the set
R of relevant document vectors there exints at least one vectors contained in the set S of non-relevant document vectors suchthat for some other vector r contained in R* cos(rfs) is greaterthan cos(vfr)*

Further, for a significant number of queries

the prevalence of such relationships effectively prevents
the retrieval of some relevant documents with reasonable precisionby any relevance feedback strategy*that constructs only one
query on each iteration*
This hypothesis states In effect that the documents relevant
to a single query are usually found in two or more distinct
clusters in the concept vector space9 and that these clustersof relevant documents are separated from each other by non-relevant
documents *Further* it states that for a significant number ofqueries this phenomenon will seriously interfere with theretrieval of some relevant documents regardless of the relevance
feedback strategy employed*

For any collection in which thishypothesis is truef all relevance feedback algorithms tested inthis study are inappropriate for a significant percentage ofretrieval requests*

Algorithms constructing more than one queryon each feedback iteration are necessary in such an environment*
The.anomalous results of the reported comparisons of positivei

201aand negative feedback support the conclusion that the statedhypothesis is true in the Cranfield 200 collection.

Becausethis collection is a carefully chosen subset of a larger
collection representative of a well-definedf technicalf limited
subject area, this conclusion suggests that multiple queryalgorithms or other means of simplifying the distribution ofrelevant document vectors in the vector set being searchedwill be needed in practical automatic retrieval systems#Section VII contains many recommendations for future
research in relevance feedback.

Positive feedback with thecombination feedback strategy that presents more documents
to users that judge no documents relevant on a given iterationis recommended in Section V1I-A for environments similar tothe Cranfield 200 collection.

Non-relevant document feedbackis recommended for users who find no relevant documents aftera maximum number of additional documents have been presented*
Section VTI-B discusses the evaluation problems encounteredin this study.

New global measures similar to normalized

recall and normalized precision are suggestod.

The $uasi-Cleverdon interpolation method is recommended in preference
to Neo-Cleverdon interpolation for recall-precision curves.
Three now evaluation viewpoints for relevance feedback aresuggested, one of which is appropriate to other areas. A
fourth evaluation method is discussed and recommended forgeneral use.
Section VII-D discusses the implications of the conclusion
reached from the hypothesis of Section VII-C for partial
search strategies, multiple query strategies, request clusteringand document space modification.

Two new measures forevaluating the usefulness of a given partition of the document
collection regardless of the partial search algorithm employed
are presented.

The cluster search algorithm used in earlier

studies of Hocchio's olustering algorithm in the SMAHT system
in inap202

is inappropriate where groups of documents relevant to thesame query are separated by non-relevant documents, so a newcluster search algorithm is presented.

This new algorithm

is combined with relevance feedback to form a cluster feedbackalgorithm that creates a different query to search eachdocument cluster.

Several design considerations for multiple

query algorithms, strategies that construct more than one
query to search the same set of documents, are proposed,
criminating in a detailed algorithm simple enough to bemeaningfully tested in a small document collection.

Finally,

request clustering and document space modification are
discussed as possible ways of making multiple query algorithms
unnecessary by additional processing that does not take place
during the search.

An algorithm for permanent adaptive

alteration of the document vectors using queries and relevancejudgments is constructed by analogy to a well-tested algorithm
that performs a similar function in adaptive pattern recognition
systems.