Relevance Feedback
In An Automatic Document Retrieval SystemA Thesis
Presented to the Faculty of the Graduate SchooloX Cornell University for the Degree ofMaster of Science in Computer SciencebySleanor Ro&e Cook IdeJanuaryf 1969

Biographical Sketch
Eleanor Ide, born in Flint, Michigan on September 7*
19^0, earned a Bachelor of Arts Degree with Distinctionand High Honors in Sociology from the University of Michigan
in 1962*

She was a research assistant for one year at thePopulation Studies Center, University of Michigan, and acomputer programmer for three years studying adaptive logicand pattern recognition at IBM Systems Development Division,Endicott, New York*

There she co-authored with Doctor Cyril

J. Tunis "An Unsupervised Adaptive Algorithm,11 in IEEE
Transactions on Electronic Computersf Volume SC - 16 #12f
December, 1967* and co-invented with Dr. Tunis and Mitchell
P. Marcus the 'Adaptive Logic System for Unsupervised
Learning1 described in Patent Application IBM Docket
EN966005, now being filed*
Eleanor Ide, a member of Phi Beta Kappa, Sigma Delta
Epsilon, and the Association for Computing Machinery, ispresently employed as a Senior Systems Analyst by Hydra
Computer Corporation in Raleigh, North Carolina**ii

Dedication
This thesis is gratefully dedicatedto my husband% Robert Idef whose help
and patience made my graduate work
possible*iii

Acknowledgments

The author wishes to acknowledge
the programming support of RobertWilliamson, and the advice and encouragement of Profeasor Gerard
Salton and Michael Keen,

The freecomputer time supplied by Hydra
Computer Corporation is also appreciated*iv

iv

Abstract
Many automatic document retrieval systems represent
documents and requests for documents as numeric vectorsthat indicate the subjects treated by the document or query.
This study investigates relevance feedback, a process thatallows user interaction with such a retrieval system.

The

user is presented with a small set of possibly relevant
documents, and is asked to judge each as relevant or nonrelevant to his request*

The numeric vectors representing

the judged documents are usedto modify the numeric vector
representing the query, and the new query vector is used toretrieve a more appropriate set of documents*

The relevance

feedback process can be iterated as often as desired*

Severalfeedback algorithms are investigated in a collection of 200
documents and 42 queries*

Two distinct viewpoints are takenin evaluation; one measures the movement of the query vector
toward the optimum query defined by Kocchio* the othermeasures the retrieval experienced by the user during thefeedback process*Several performance measures are reported

from each evaluation viewpoint.

Both evaluation methods

indicate that relevance feedback is an effective process*All algorithms tested that use only relevant document
vectors for feedback provide equally good retrieval*

Suchalgorithms should supply additional documents to any userv

who judges every document presented for feedback to be
non-relevant*Algorithms using non-relevant document vectors

for feedback improve the retrieval obtained by these users
without requiring additional relevance judgments.
The relevance feedback algorithms tested are based on
the assumption that the vectors representing the documents
relevnnt to a query are clustered in the same area of thedocument space.

The conclusion that no tested relevance

feedback algorithm is completely appropriate for the experimental environment is supported by a hypothesis that
explains the observed contrasts between the behavior ofstrategies using only relevant documents for feedback and thatof strategies using non-relevant documents.

This hypothesis

states that for most queriesf some relevant document vectors
are separated from others by one or more non-relevant document
vectors.

The implications of this result for future researchin relevance feedback, partial search or multi-levelstrategies, multiple query strategies, request clustering*and document vector modification are discussedf and usefulevaluation measures and new algorithms for these areas aresuggested*vi

Table Of Contents
Page
Biographical Sketchii

Dedicationiii

Acknowledgmentsiv

Abstractv

Table of Contentsvii

List of Illustrations

ix

Introduction

1I.

Automatic Document Retrieval Systems

3

II • User Interaction With an On-LineRetrieval System
III. -Prior Investigations of the Relevance

8Feedback Retrieval Algorithm

14IV.

Environment of the Reported Experiments

19V.

Evaluation of Retrieval Performance

23A.

Measures of Performance

23

Bo

Statistical Significance Tests

28Co

The Feedback Effect in Evaluation

29ViaExperimental ResultsA.

33

Comparison of the Cranfield and ADI
Collections
Strategies Using Relevant Documents

33

Only36

Co

Amount of Feedback Output

42

D»Strategies Using Non-Relevant Documents -^A

Bo

Characteristics of ^uery Subgroups

75

Bovii

PageVII•

Recommendations Based on Present and Prior
Experiments
A*

101

Relevance Feedback Recommendations forConcept Vector Document Classification
Systems

101

B#Evaluation of Relevance Feedback Experiments

106

Co

Feedback of Non-Relevant Documents

130b

D#Partial Search and Multiple W,uery
Algorithms

1^7

Summary

199viii

List of Illustrations.Pap*
x'i -urtt ill

FigureFigure2t
3«

Figure <nFigureFigure5*

6:

Figure7*

Figure8:

Figure9*

Figure 10t

Figure H iFigure 12i
Figure 13t

Aa Illustration of the Interpolation.Method Used for the %uasi-Cleverdon
iieeall-Precision Averages

27

Aa Illustration of the Interpolation
Method Jsed for the Neo-Cleverdon
Recall-Precision Averages.
Improvement oyer Initial fleareh* ADI
and Cranfield"Collections
Sffects of fRelevant Only1 on the Multipliers of Documents Retrieved onThree Successive Iterations•

36

Query Update Parameters for Relevant
Only Strategies* Using Only Relevant
Documents•

40

Varying the Number of ieedback Documents! Total Performance Recall-Precision
Curves432735

Recall and Precision Document Curves9Feedback Increment Strategy*Feedback Effect Document Curvesf Recalland Precision Differences f Varying theNumber of Documents Retrieved (N«5 normal % N-2 and N-10 compared)•46

Variable Feedback; Feeding Back Only
the First or Fir^t Two New Relevant
Documents Found Within the First Fifteen Documents Retrieved| Total Performance * Q Strategy*50

Variable Feedback and Combination Strategy Compared to N«5 :*ormf Kecall andPrecision Difference^* Feedback EffectDocument Curves*

52

Deere:: anting the Highest Non-Relevant
Document,Total Performance RecallPrecision Curves*-56

Normalized Results for iNon-i elevant
Strategiesf Total Performance*

56

Deoremonting the Highest Non-Relevant
Document on Kleven Bad queries* Total
Performance Recall-Precision Curves*

59

45

Figure 14:

Figure 15:

Figure 16:

Figure 172

Figure 16:

Figure 19«

Figure 20:
Figure 21:

Figure 22:
Figure 23:

Figure 24:

Figure 25*(Dec Hi) - (vto) For the 3-Good
Queries, a Comparison Between Decrementing the Highest tfon-Kolevnatand Incrementing the Relevant Only,
Total Performance Difference•

60(Dec Hi) • (Dec 2 Hi) A Comparison ofDecrementing the Highest or the Twohighest Non-Relevant Documents on Sach
Iteration, Total Performance Difference*

62(Feedback 10) - (Dec Hi) A Comparison
Between Feeding Back 10 Documents but
Increasing Relevant Only, and Feeding
Back *> Documents but Decrementing theHighest Non-Relevant* Total Performance
Difference*

63

Statistical Comparison of Feedback Sffeet Relevant and Non-Relevant Document^trnte^ies, Norma Used Recall and Precision*

66

Comparison of First and Second Iterations to Initial Search Differences andSignificance Levels - Rocchio Algorithm,Feedback ?;ffect Kecall-Preci^ionCurves. 4

68Comparison of First and Cecond Iterations to Initial Tearch Differences andSignificance Levels - '^ + Algorithm,
Feedback Effect Jtecall-Precision Curves*

69

Rocchio Strate<yr on Eleven Bad Queries,
Feedback Effect Recall-Precision Curves*

12

Recall and Precision Differences Comparing Rocchio and Dec Hi Strategies to Q • .
norm, Feedback Effect Document Curves*
oSome Query Subgroups Invent!gated•73
76

Characteristics of Subgroups Selected By
Initial Search Retrieval*bO

Subgroups Selected by Performanco, Feedback ?;ffect Recall-Precision Curves,
Rocchio Strategy

83

Characteristics of Subgroups Selected
By Performance*

84

Page
Figure 26:
Figure 27:

Figure 28:

Figure 29:

Figure 30:

Figure 31:

Figure 32:

Figure 35:

Figure 34:

Figure 35*

Figure 36i

Cross-probabilities lor Correlation ofModified v^uery with Original ^uery.

8b

Characteristics of Subgroups Selected By
Correlation of Modified ^uery With Originalv>;uery.

87

Subgroups Selected By Strategyf .c + Groupt
Feedback Rffect Recall-Precision curves,
Comparing Positive and Negative Feedbacks

69

Subgroups Selected By Strategy, iiocchio
Groupf Feedback Effect Kecall-Precision
Curves, Comparing Positive and NegativeFeedback.

90

Comparison of Positive and Negative
Feedback in Subgroups Selected By Feedback
Strategy-

91

Comparison of Negative and Positive
Feedback in Subgroups Chosen by Feedback
Impr ovement.

9^Comparing Positive and Negative Feedback
In Subgroups Selected By Number ofConcepts in Original Query and Number ofRelevant Documents.

98

Examples of Performance Equivalence
Between queries as Defined by Different
Interpolation Methods*

112

Twenty-Point Interpolation From SxampleQ
Query A Using Five Different Interpolation
Methods

114

Comparison of Two Evaluation Methods,
Total Performance Evaluation withc^uasi-Cleverdon Interpolation and Feedback
Effect Evaluation with Neo-Cleverdon
Interpolation, Comparable Strategies,
N m 5

121

An Example of an Individual ^uery With m
Separate Clusters of Relevant Documents*,
Q • and Hocchio Strategies

144-x1Page
Figure 57:

Example of Poor iiocchio Performance
Caused by Non-Relevant Document Feedback

Figure 58:

An Example of Good fiocchio Performanceon Separate Clusters of Relevant Documents

145a

A General Two-level Cluster Feedback
Algorithm

169

Figure 59:

Figure 40: Three Relevant Documents Forming Three
Separated Clusters

176

Figure 41: A Multiple Query Algorithm

184eX11