ZIJ • fixperlmental Keaulta
The results of this study are presented in five general
sectionssa)

A comparison of the improvement in retrieval per-formance observed for the Craafield 200 document collection
with that obtained for the ADI (32 document collection uaed
by Riddle, Horwitz, and Dietz *b)

K

An investigation of strategies that use only H 9 t

the set of relevant documents retrievedf to update thequery*The different algorithms are obtained by varying

the parametersn,«,and <X in the query-update formula*

The "increasing alpha strategy" of Kiddle, Horwitz, andDietz is included among the methods tested*c) An investigation of the effect of the number of
documents given to the user for feedback on each iteration*d)

An investigation of strategies that use both rele-vant and non-relevant documents retrieved to update thequery*
e)An investigation of the retrieval characteristics

of selected subgroups of queries** A*

Comparison of the Cranfield and ADI Collections

The initial search results, before feedback, for thetwo collections are essentially the same except at theends of the recall-precision curves*

Below 30/ recall, theprecision of the ADI initial search is from 2 to 7% better
than that of the Cranfield initial search*

Above 80% recall

the precision in the Cranfield initial search is from 2 to6£ better*
33

This result is interesting because there is reason to
expect that performance in the Cranfield collection would
be worse•

Cleverdon and Keen point out that in a col-lection with a higher "generality number", that is, witha higher ratio of relevant documents to collection sizetJ
performance is better with respect to precision li 181.
The average generality number of the ADI collection isover twice that of the Cranfield collection*

The gener-

ality number in a collection of practical size would beeven lower than that of the Cranfield collection.
Because the initial search results differ, the total
performance improvement caused by feedback in the recallprecision curve is used for comparison of the two collections.

All thirty-five queries are used to search the

ADI collection.

The "increasing alpha strategy" of Riddle*

Horwits, and Dietz is the update formula, and five documents are given the user on each iteration.
Figure 3 shows the differences in total performnnce
precision for all recall levels between the initial searchand the first and second feedback iterations for eachcollection.

In the Cranfield collection, relevance feed-back causes greater improvement than in the ADI collection.
Also, the second iteration results in a greater improvement
over the first in the 200 document collection.

The dif-

ference in generality between the collection would be
expected to cause less improvement in the larger collection

35

N»5
increasing alpha strategy"

'••i

o
A

ADI
Cranfield

1st iteration
2nd iteration

25

20
c
arC

Q>

>

O

15

C

ail

-•

c
o 10

CO

oQ>
• w

a.
•5

<*

40

60

100

% recall
Improvement Over Initial Search
ADI and Cranfield Collections
Total Performance .Recall-Precision Curves

Figure 3

36
The greater effect of relevance feedback in the Cranfieldcollection could toe due to any or all of the following
factors:a)

The difference in subject and in the language ofthe subject*

It ia possible that the terminology of

aerodynamics ia 'harder1! that is, more limited end preciBef than the vocabulary of the newer field of computerscience. Retrieval of documents from a harder subject
area would be expected to be better.
b)

The difference ia collection scope.

The ADI col-lection covers a wider subject area within computer science
than does the Cranfield collection within aerodynamics. A
narrower subject area should provide better retrieval.
c)

The difference in variability within the collection.

The 200 documents were chosen from 1400 documents concernedwith aerodynamics.

The 82 document collection consisted ofshort papers presented at a single conference.

Since theCranfield 200 documents vary more in such parameters as
vector length and terminology, relevant documents uiii^ht
be easier to distinguish from non-relevant documents.
d)

The difference in query construction and relevancejudgments mentioned in Section III.

It is encouraging tofind that in the more realistic Cranfield environment»
relevance feedback causes more rather than less Improvementin performance.
£f#Strategies Uaing Relevant Documents Only

Two of the experiments of Riddle, Horwitz, and Dietz [11 ]are repeated for the Cranfield collection.

To simulate their

37
experiments with equation
is varied;nDof Section IV, the parameter O6

ia kept equal to 1, and

^

and

*

equal

Both the "increasing alpha'1 and "constant alpha11

to 0*

strategies are employed*
Figure 4 clarifies the effect of the "increasing alphastrategy" and the "constant alpha strategy" for the first9
second, and third iterations of a feedback run% evaluating total performance.

The

R°

column shows the factors

which multiply a relevant document retrieved on the initial
search,Rshows the multipliers affecting a relevant

document which is not retrieved until the first iterationf
2
and

R

shows the multipliers affecting a document not re-trieved until the second iteration*

Figure 4 assumes thata document once retrieved is retrieved on all succeeding
iterations; in the experimental system this assumption is
generally correct*
It is clear that both the constant and increasing alphastrategies give a document retrieved on an earlier iteration more significance in later queries*

On the third

iteration, the constant alpha strategy assigns to a document
retrieved on the initial search three times the significanceit gives a second iteration document (the respective multipliers are 3 and 1)* The increasing alpha strategy
assigns to an initial search document twice the significanceof a second iteration document (the respective multipliers
are 6*and 3)«
vious query

This effect stems from the use of the prev}, as an element in the equation*

To assign

38

TOTAL PERFORMANCE

iter

Q,

1

1

2

1

3

3

1

6

1

' . 1

2

1

3

1

1

1

2

1

3

1

FEEDBACK EFFECT .

1

1"feedback increment"

2

1

3

1

"increasing alpha strategy""constant alpha strategy""Q0 strategy"

R1

R°
1

0

0
2

0

3

5
0

1

R2

2

0
l
2

3
1

0

0
1

1
0

1
1

0
1

Effects of 'Relevant Only* on the Multipliersof Documents Retrieved on Three Successive Iterations

Figure 4-

1

0

39
the same significance to relevant documents whenever they
are retrieved, it is necessary to substitutevjin the formula; that is, to letm« 1equation \f

u • 0

and

for

Qj

in

This is called the "Q

strategy" in Figure 2*

Riddlef Horwitz, and Diets *•* report that for the 82

document; collection, the "increasing alpha strategy11 performs
somewhat better than the constant slpha stratagy«

In theCranfield collection, the three strategies shown in Figure
2 give essentially the same results whenW • 5*

vi strategy with different relative values ofalso does not change performance*

Using theo> ando^Query update parameters(in equation D) for the six experiments performed are shownin Figure 5*

Among all six experiments, the differencesin normalized precision and recall are less than 0*75%
for all iterations*
In total performance9 six strategies using only relevant documents differ very little*

Three additional •rele-vant only9 algorithms are compared using feedback effectevaluation*to1

One of these strategies sets

in formula D*

o^

and

n

equal

This strategy, called Feedback Incre-

ment, is not equivalent to the constant alpha strategy
because the feedback effect evaluation provides new documents for feedback on each iteration*

Figure 5 shows that

the Feedback Increment strategy gives the same weighting
effects as does the Q

strategy*

These two strategies are

identical on the first iteration, but on subsequent iterations the feedback effect evaluation may retrieve different
documents*

40
N 5

* » n a" N ' V 0 ' |I"0

TOTAL PERFORMANCE

n •

.';

1

w

«<

0

1

increasing alpha2

constant alpha

1

0

1

Q o strategy

0 .

1

1

Q

weighting query double

0

2

1

Q

weighting query half'

0

.1

2

Q

weighting query six times

0

6

1

1

- 0

1

1

4

1

0

n

. ,

FEEDBACK EFFECT
Feedback increment*

Feedback Q +Feedback Rocchio +

•

n n
r

o

Query Update Parameters for Relevant Only Strategies
7 Using Only Relevant Documents

Figure 5i41Another strategy using feedback effect evaluation,
called *LQ+% gives added weight to the original query oneach iteration by setting u> equal to 4 (o^ » 1, n • 1 ) . A
third strategy is Rocchio + , the Rocchio strategy without
non-relevant documents.

In effect, ot equals n n

and nequals n , so o^ and n vary with each query.
Differences in feedback effect among these threemethods are trivial.

For the two overall measures and therecall-precision curves, the largest difference is 1.25
per cent.

The document curves are more sensitive in generalto performance differences, especially in recall.

Thelargest difference is 3% in recall at a 40 document cut-off.
Most differences in all measures favor the Q + strategy.
The 200 document collection seems quite insensitive tovariations in the parameters n, *>, andOL• The considerations

mentioned in section VI-A are probably relevant here also.
This insensitivity indicates that perhaps the performancefor the Cranfield collection is more stable in general thanfor the ADI collection.

Evidence of comparative stability

is also reported by Lesk and Salt on l1^-*. The performancedifferences between automatic use of the word stem thesaurus
and a regular subject-area thesaurus (see Section II) areless pronounced in the Cranfield 200 collection than in the
ADI collection.
It is evident from the reported experiments that theweight assigned to the original query has little effect onretrieval.

This finding tends to support the conclusion of

42
i i2l
Crawford and Maimer l J that the original query is notneeded after the initial search (Section III). The advantage of their strategy over equation B is probably nob causedby the omission of the initial query when relevant documents are foundt but by the non-relevant document feedback used when no relevant documents are found (see SectionVI-D).
C . Amount of Feedback Output
The number oi documents fed to the user is a criticalparameter in a relevance feedback system*

Of course, per-formance improves when the user supplies more information*
This improvement must be evaluated in terms of the extra
effort required of the user*
Figure 6 shows the totaL performance of the "increasingalpha strategy11 when 5* 10« and 15 documents are fed to theuser for relevance judgments*

The total performance im-provement between the 8 - 5 and N * 10 curves mi^ht justify doubling the number of relevance judgments the user must
make; that is* a hypothetical tfaverage,f user might be willingto double his effort to achieve such an improvement*Tri-pling the feedback to produce Che N • 15 curve might not
be justified by total performance* especially at the highrecall end of the curve*
Caution is necessary in interpreting the feedback
effect evaluation whenN

is varied* because the feedback

effect evaluation gives an unfair advantage to runs using
few documents for feedback*

When five documents are used

for feedback* ranks 1-5 are frozen on the first iteration

43•• Initial search

o

N. «

5

A

N - 10—

1st iterationoN - 15—

2nd iteration

100

40

60

% recall•Number of queries (out of 42)
r e t r i e v i n g no relevant i n the f i r s t N:
N

N

10

N

15

11
Varying the Number of Feedback Documents
Total Performance Recall-Precision Curves

Figure 6

44
and ranks 1-10 on the second (see Section V-C).

When tendocuments are fed back, howeverf ranks 1-10 are frozen on
the first iteration and ranks 1-20 on the second.

The dif-

ference in results caused by increasing the number of documents fed back is therefore minimized by the feedback
effect process«Recall-precision curves for the feedback effect are
not presented in this section, because the minimizing effect described above is averaged into different recall
levels for different queries.
query

a

For example, assume thathas four relevant documents and querybhastwo. . 3ach query retrieves the first relevant document withrank 8.

When five documents are used for feedbackf each re-trieves the first relevant document with rank 6.

When tendocuments are used^ of course rank 8 is ffrozen1 by the
feedback effect evaluation.

Consider the effect of these

queries on the^recall-precision averages for the first iteration.

When ten documents are used for feedback% neither

query improves these averages.
£

When five are used, query

improves the recall-precision averages from 5% to 2 %recall, but queryb

improves £ he recall-precision aver-ages from 5% to 50% recall.
Thus it is hard to Judge the significance of any difference in results caused by differences in feedback output.
Figure 7 shows the document curves for two iterations offeedback withalgorithm.

Nequal to 5f using the Feedback Increment

Figure 8 uses these curves as a norm for compar.

45

HP

9

o
o
CsJ

!
•a

>

>>
CO

c
o

•o

c
10

03

r~
03

o

<D
QL

i

Vto
CD

O
00

<D
*r-

>

r>
o

C
QJ

C

a>
3
O

O
Q

CD
S~

</>
4->

4->

',

4->

t-

E

T-*

6

•*->

(/>

r^

.

JiZ

V
to

O

c

r—

QJ
E
=J

v.
o>
•»LU

o
o

o

'
!
•

•<->

vo

. 3

u

o
c
•—9

$ Q 9

0)

E
01

eedb

•r—
to
•rU
QJ
SQ.

<J 6

r-

• -"

O

.

iO)

•

jQ

O
CM

u o j . s p a u d uo L L^ D9a

Sfc

luaouad

E
3

46

8

10. 12. 14! 16

18

201:20 40 60 80 100 120 140 160 180
number of documents retrieved
Feedback Effect Document Curves
Recall and Precision Differences
Varying the Number of Documents Retrieved(N=5 normal, N=2 and N=10 compared)
Figure 8i47
ison with the results of less feedback and of more feedback*The document curves of Figure 7 are represented in

Figure 8 by the straight line at zero difference•differences between
and between
The

N-2

N-10

and

and

N-5

N-5

The

for two iterations

for one iteration are graphed.

N-2 differences* indicated by *&\are positiveat first because ranks 3-5 are frozen for theN-5

curve•

This initial advantage fades after 10 documents and theN-2

results are lower than the

The

N-10

N-5

norm thereafter.

curves for both iterations are affected by the

feedback effect evaluation.

The first iteration gains

higher performance thanafter 13 documents. The se-

N-5

cond iteration curves cross the

N-5

ments! even with ranks 1-20 frozen.

norm after 15 docuAfter 40 documents

have been retrieved, the differences in both recall andprecision for the first iteration are slight; theN-10

advantage on the second iteration is slight but consistent.
After 20% of the collection has been searched, thedifferences in «feedback effect observed in Figure 8 arequite low.

However* the marked improvement in early re-trieval caused by additional feedback might Justify theadditional user effort and system output required, especially if further feedback iterations are desired,
Moreover, it is important to note that certain users get
no benefit from any feedback strategy using only relevant
documents.

These are the users who find no relevant in

the firstN

documents retrieved.

For

N-5* 10, and 15%

47 a
the number of queries retrieving no relevant on the initial search is given in Figure 6, in the table below thegraph.

This table probably explains much of the perfor-

mance difference among the three strategies.
queries in theN«5

Elevencase produce the same low perfor-

mance on the initial search, first iteration, and second
iteration.
curves.

These low results are averaged into all the N-5

The

N»10

curve is pulled down by only five such

48
queries* and the N-15 curve by only two*In the i«»5 caaef

one quarter of the uaera are not assisted by the chosen
feedback strategy* a large proportion for a practical
retrieval system*

For these unlucky users, feedback ofmore documents is worth the effort*
A variable feedback strategy is here proposed whichmight save effort to the average user and give better tiervice for more effort to the user who does not find a relevant document early in the initial search*

Kach user is

fed retrieved documents until he finds one relevant document that he hasn't seen on any previous iteration*The

relevant document found is immediately used to produce a
new query.

The success of this strategy depends on theability of a single relevant document to improve the retrieval performance*
Figure 9 shows the total performance results of two
iterations where the "user" is instructed to search theretrieved documents until he finds one new relevant document or until he has seen 15 documents*

The " A " curve in

Figure 9 shows what happends when the user is instructed
to find two new relevant documents*

Only one iteration of

the latter scheme was run because several queries do nothave four or more relevant documents*
The first iteration feeding back one relevant document
begins near the N-15 curve of Figure 6 but by 50% recall has
dropped near the first iteration N»5 curve* which has beensuperimposed on Figure 9*

The table below the graph shows

49
that the "average" user had to scan only four documents
for feedback in order to achieve the performance displayedin the first iteration "oM curve.

By contrastf each user

looked at exactly 5 documents to produce the first iteration N«5 curve.

The first iteration strategy of feedingback only one relevant document gives equal or better performance for less average effort.
The second iteration "o" curve requires the averageuser to search 5*9 more documents^ or a total of 9*9 documents*

This curve drops below the first iteration N«10

curve (10 documents scanned) at roughly 55% recall (thefirst iteration N-10 curve from Figure 6 is superimposed
on Figure 3).

The user desiring high precision and who may

be less interested in high recall might be wise to feedback one relevant document for each of two iterations.

How-

everv the user needing higher recall should instead lookat ten documents retrieved on the initial search.
statements*apply to the "average" user).

(TheseIt is also seenfrom the table below the graph that for the second iteration "o" curve one quarter of the users cannot find a new
relevant documentf and thus after the first iteration theseusers search 15 documents to no avail.

Such performance

would be quite annoying in practice.
The average user who searches for two relevant documents in the initial output looks at 7 documents.

His

recall-precision curve ( " A " ) drops below the first iteration N-10 curve at 65% recall.

Although 9 out of 4>2 users

50
initial searcho feedback 1 new relevant
1st iteration
A feedback 2 new relevant
2nd iteration(no character) superimposed curves from figure 6, 1st iter
. 100
%

P
r
e
c
i
s
i
o
n

20

100

40

% Recall1 relevant
Initial 1st iter
outputoutputAvg. no. of documents searched
No. of users (of 42)
not finding n new
relevant in the first
15 documents retrieved

4.0

5.9

2

11

2 relevant
Initialoutputcombinedstrategy
Initialoutput7.0

6.4

Variable Feedback
Feeding Back Only the First or First Two
New Relevant Documents Found Within theFirst Fifteen Documents Retrieved, Total
Performance, Q 0 Strategy,
Figure 9

51
do not find two relevant documents in the first 1!?* *11
but two of them find one relevant to feed back to thesystem*The user who feeds back two relevant documents on one
iteration ( W A w ) achieves better performance than does theuser who feeds back one relevant document on each of two
iterations (second iteration w o M ) .

This result shows thatthe second relevant document retrieved on the initial
search is more valuable for feedback than the first now
relevant retrieved on the first iteration by the total performance retrieval method*

Feeding back one relevant doc-

ument on the first iteration evidently pushes down acme
relevant documents that are valuable for retrieval*Thisfinding provides a strong argument against the proposed
variable feedback strategy, at least where high recall isdesired*Perhaps some sort of combination strategy might

be optimalj for instance9 the user could be instructed tofeed back all relevant documents in the first five retrieved,
but if none ere found in the first five to keep looking andfeed back the first relevant document found*
One iteration of feedback effect performance of variable feedback and of the combined strategy described above
is presented in Figure 10*

The differences between vari-able feedback (feeding back one relevant) and constantH»5 feedback are graphed (o )*After nine documents havebeen retrieved the feedback advantage using the first relevant document for feedback is evident*

The combination

strategy (graphed *) that retrieves at leaat five documents

52

*

>>
o>

CD

+j
03 > >* - r—

^£

u

fX5

J3
•o
QJ

•P C
i/> O

QJ

CD

c: °
O i-

i3
Or,

**0>
p.Q
03
•r-

• r - <D
4-> 4->
03 »r—

C• r - 4->
- O CO

S03>

CO

IteDaj

CM

*-

O

r-

E *-

O «rU*f-CO}U9DU9dS3aN3U3dJIQ

U0J.SJ.D9Ud ^ U 9 D ^ 9 d '53shows a greater improvement t>ver N+5 than Joes variable
feedback*

This result shows that this variable feedback

algorithm is advantageous only for those queries that retrieve no relevant among the first 5 documents*

For thosethat do retrieve relevant within the first five documents*
the constant i**5 strategy gives better feedback effect reW
sulta* Figure 9 shows that the combination strategy requires
the average usdr to look at 6.4 documents, as compared to the
4*0 documents retrieved by variable feedback*\Total performance and feedback effect results support
three conclusions about feedback strategies that use only
relevant documents:
First* retrieving more documents does improve both typesof performance (except where the rank-freezing of feedback
effect evaluation prevents any improvement)*

further*notable improvement can be obtained by searching further
if no relevant documents are retrieved in the first N*
Second* the total performance for 5% 10• and 15 documents indicates that whenM

is constant for all queries*

the average increment of improvement obtained tends to become smaller as more documents are used for feedback*Third* however* a comparison of the variable feedback
and combination strategies show that the first relevant
document retrieved generally does not contain enough information for retrieval* and that documents retrieved soonafter #the first (N«5) can add useful information*

In theirstudy cited in Section III* Crawford and Melzer used only
one 0very relevant1 document for retrieval*

The finding of

this study would indicate that if several documents are

54
almost equally relevant, all of them should be used.
These three conclusions lead to a recommendation that
N be set to some value that most users would consider reasonable,
but that for some queries N should be raised until at least one
relevant document is retrieved. This recommendation endorses
the ,fcombination strategy" for a retrieval system using only
relevant documents.
D)

Strategies Using Non-Relevant Documents

Rocchio's update formula (equation A) considers theinformation contained in the set of non-relevant documents
retrieved (S) to be as important as that contained in theset of relevant documents retrieved (R). If this is thecase, the strategies so far examined disregard half theavailable feedback information.

Further information from

non-relevant documents retrieved on the initial search might
help those users who retrieve no relevant documents on theinitial search (see Section III and reference 6).

Figure 6shows that there are eleven such users out of 42 when N equals

5.
However, problems arise in using the non-relevant documentsin the SMART experimental system.

There is no provision for

negative weights in the query vector*

Also, queries and documents

cannot be normalized to the same length for query updating.

Thereis some danger, therefore, that the query will be reduced tonearly the zero vector when the documents of S are sub tracted
from it*

Riddle, Horwitz, and Dietz *• ^ try to avoid

thisdanger in their "negative heuristic strategy" by feeding backonly the first two non-relevant documents retrieved.

55
The Rocchio strategy adjusts the multipliers for eachquery so as to weight the original uuery, the sum of therelevantf and the sum of the non-relevant equallyf anduses all retrieved documents•
This study compares the Rocchio and fnegative heuristic1
strategies using total performance and feedback effect measures•
All comparisons are made withcompares the QNequal to 5*

Figure 11

strategy (see Section VI-B) with a strategy

called 9Dec Hi f t that decrements each query by subtractingfrom it the first retrieved non-relevant document.

In thequery update formula (equation D), the parameter values andeffective update formulas for these strategies ares
(J i 7c » 0, m - 1, o6« l, jx • o, n

Dec Hi?

m Nf a. - 0

n • 0 9 * « 1* oCm 1, p • -l $ n• Nf n. - 1

Figure 11 shows that the average results are consistently
better for the wdec hiw strategyf especially on the second
iteration.
For this experiment, the implications of the total
performance normalized precision and recall results given
in Figure 12 seem inconsistent with those of the recallprecision curves of Figure 11.

On the first iteration, therecall-precision curve for the dec hi strategy is above

56
0

A

Qo
dec hi

initial search
1st iteration
2nd iteration

—

100

20

40

SO

SO

100

% recallDecrementing the Highest Non-relevant Document
Total Performance Recall-Precision Curves'

Figure 11
Init

Normalized Recall

Q

88%

90

90

Dec High
Dec 2 Hi

88
88

8?
85.

90
89

68
68
68

75
76
75

76
81
80

^0

Normalized Precision

Dec High
Dec 2 Hi

Normalized Results for Non-relevant Document Strategies
Total ir'erformance, Figure 12

57
that forQ

at all recall levels*

Howeverf the normal-

ized recall for the first iteration is lower for dec hi,
although precision is one percent higher*(On the second

iterationf the normalized recalls are the same* and thenormalized precision for dec hi is five percent higher).
This apparent paradox can be understood by considering thenormalized recall measure*
Each document retrieved is assigned a "rank" in orderof retrieval (rank 1 is the document retrieved first)*
The normalized recall measure is based on the sum of theranks of all relevant documents in the search*

A changein rank affects this measure equally regardless of themagnitude of the rank*

That ie% a change from rank 195

to rank 191 is equivalent to a change from 5 to 1 in its
effect on normalized recall*normalized precision.

The same is not true for

It seems evident that while the dec

hi strategy increases the rank (1 is considered highest)of some of the relevant documents* it decreases the ranksof others that are* on the average, of lower rank already*This explains the phenomenon of higher precision at alllevels of recall but lower overall normalized recall*Figure 13 shows how much the dec hi strategy helps the
11 users who receive no relevant documents in the first 5
on the initial search*

For the "inc only" strategy* theinitial search and all subsequent iterations are the samefor these 11 users} the precision being about 10 percent*Feeding back one non-relevant document fetches at least one

58
relevant document on the first iteration for 7 of these
11 users*

For some of these queries9 so^ne low ranking

relevant documents are pushed still lower at first.

The

relevant documents which are raised to the first 5* however! provide a second iteration query which often raises
these same low documents again.

The first iteration curvethus shows the most improvement at low recallf while thesecond iteration shows great improvement all along therecsll-preciaion curve.
Since the improvement in total performance for the 11"bad* queries is so striking, it is natural to wonder whether
this strategy Is helping or hurting the other 31 users.
Figure 14 shows a different curve for the dec hi andQ^strategies run only on the 51 queries that retrieve atleast one relevant in the first 5 documents.

A point above

the zero line indicates that dec hi is better thanthat recall.

Q

atBoth iterations are better for dec hif es-

pecially at the high recall end of the curve* where theydiffer by as much as six percent.

Since the dec hi strat-

egy improves the results even for the "good" queries, aheuristic strategy that selects only some of the queries(as does the "negative heuristic strategy" of Riddlet HorwitZi and Dietz) for the dec hi algorithm appears unnecessary
in this environment.
Figure 15 represents a total performance difference
curve ^comparing the "dec hi" strategy with the alternativeof decrementing the query by subtracting the two highest
non-relevant documents retrieved on each iteration (called

59

N - 5 •—• initial search
and Q Q strategy first iteration
1st iteration
2nd iteration

100

40

SO

80

100

% recallDecrementing the Highest Non-Relevant Document
on Eleven Bad Queries
Total Performance Recall-Precision Curves

Figure 13

60

. «

1st iteration

N - 5

2nd iteration

20

40

SO

80

100

% recall(Dec Hi) - (Q0)
For the 3i Good Queries, a Comparison Between
Decrementing the Highest Non-Relevant
and Incrementing the Relevant Only
Total'Performance Difference/••

Figure 14

61"dec 2 hi")•It shows that decrementing only one non-relevant gives generally better results; the largest difference being a five percent hump at 40% recall in thesecond iteration*

In Figure 12 the normalized measures

show the same relationship; the dec 2 hi strategy is one
or two percent lower on each iteration than is dec hi*

Thisresult may be due to the danger mentioned earlier, that the
non-relevant documents may be subtracting out most of thequery*(Only one query completely disappears using thisstrategyf and it is erased also by the dec hi and Rocchiovs
algorithms*)

It might be possible to overcome this "dis-appearing query" phenomenon by juggling the parameters n*,»f c* t andii« without introducing the complications of

Rocchio9s normalizing method*
It was mentioned in Section VI-C that much of the improvement between the N*10 and the N«5 curves of Figure
6 might be caused by the improvement on the six queries
that fetch a relevant document within the first 10 but not
the first *> on the initial search*

Seven users of the un-

lucky 11 are helped by the dec hi strategy; that is, the dec
hi strategy provides useful feedback for one more user thandoes the relevant document strategy with N-10,

It is per-tinent to ask if the dec hi algorithm has* in fact* attained
the total performance of the N*10 curve*

Figure 16 shows adifference curve between the N»10 curve of Figure 6% and thedec hi curve of Figure 11*

The N-10 curve is higher for the

first iteration$ over five percent higher at the high recall end of the curve*This is understandable in view ofthe lowering of low-ranking relevant documents on the first62

N

1st iteration
2nd iteration(Dec Hi) - (Dec 2 Hi)
A Comparison of Decrementing
the Highest or the Two Highest Non-Relevant Documents
pn Each Iteration •Tptal Performance Difference

Figure 15

63'i

1st iteration— — ~ 2nd iteration•MO-5
0 . , 20

X

40

i

60

80

100

% recall(Feedback 10) - (Dec Hi)
A Comparison Between Feeding Back 10 Documents
but Increasing Relevant Only,and Feeding Back 5 Documents
but Decrementing the Highest Non-Relevant .
Total Performance Difference

Figure 16

64
iteration, discussed earlier in this section*

For thesecond iteration,'the dec hi curve is slightly better at
the low recall end and only slightly worse at recalls between sixty and ninety percent.

Considering that the dec

hi curve only requires half as much user effort (5 documents scanned instead of 10), the total performance results strongly favor this non-relevant document retrieval
strategy.
She feedback effect results are not as encouraging.
Using the two overall normalized measures and the recallprecision curves, three strategies are compared end theirdifferences tested with the two significance tests described in Section V-A, the T-Test and the WSfi Test.

The

three strategies that are compared in feedback effect performance ares
Feedback Dec Hit

The Dec Hi strategy with the

feedback effect retrieval method, using thefirst retrieved non-relevant document.
Rocchio:

Rocchiofs recommended strategy (with-out normalised vectors) using all retrieved
documents.
Q • t

The strategy described in Section VII-B,

that gives added weight to the original queryand uses only relevant documents.
The differences in feedback effect recall-precision
curves among these strategies are not significant.

Thelargest differences found were 1.5% in the first iteration,.

65
significant at the 30% level! and 2.Q& in the second iteration! significant at the 11% levels

The largest difference

between <i • and any other strategy was 1.2%f significant at
the CA% level.

These significance figures were obtained

Uoins the leas conservative T-test.

Figure 1? shows thedifferences among the three strategies in normalised recall and normalized precision.

The feedback effect results

agree with the total performance results in showing a drop
in normalized precision for the two non-relovant document
strategies on the first iteration.
ference between

Q •The five percent dif-

and feedback Dec Hi is significant

at the 60£ level9 and the six percent difference between<t • and Hocchio is significant at the 3% level* according
to the T-test.

Howeverf theftilcoxonSigned-Rank Test

(WPH) indicates that the two algorithms do not give significantly different results. The significance level comparing Q • and feedback Dec Hi is 46%* and that comparing< + and Kocchio is 9b%*
These different significance levels muat be consideredin the light of the characteristics of the two significancetests * The T-test takes account of magnitude * the VVGfi test
considers only rank*

3videntlyf differences favoring Q •and differences favoring the non-relevant document strategy
are mixed in rankv producing insignificant results on theW£R test.

Yet* some of the results favoring Q • (not all,because the ranks are mixed) must be very large in magnitudet
to give significant indications on the T-test.

Thust for

66

Normalized
Precision

Normalized Recall

Difference

T
Test

WSR
Test

Difference

%

T
Test

Iter
1

6.1

3.4

24.1

2.9

15.4

Iter
2

4.4

17.7

48.9

2.0 .

43.0

Iter
1

5.4

5.7 • 98.5

2.1

31.4

Iter
2

• 7.0

9.4

3.0

29.6

%

Q + strategyminus
Rocchio strategy

Q + strategy
minus
Dec Hi strategy-45.6

Statistical Comparison of Feedback EffectRelevant and Non-Relevant Document Strategies
Normalized Recall and Precision

Figure 17

67some queries, the Rocchio and Feedback Dec Hi algorithms
must be much less effective thanu +as measured by nor-malized recallf while remaining effective as measured bynormalized precision.
The normalized recall obtained by feedback effect evaluation shows the same behavior as the total performance
normalized recall on the first iteration*

Both evaluation

methods lead to the conclusion that the use of non-relevant
documents for feedback apparently raises the ranks of fairly
high-ranking relevant documentsf and at the same time lowers
the ranks of some low-ranking relevant documents on thefirst iteration*
The significance levels obtained by comparing the firstand second iteration results to the initial search result
within the strategies are very informative*

Figures 18 and19 show the performance of algorithms

and Rocchio

respectively*

Q +The significance of the gap between the ini-tial search and each iteration is testedf using the moreconservative WSR test*
Looking at the three recall-precision graphs* the average performance of the three algorithms seem quite similar*
In fact* the differences in average performance ere not significant*Yet* the significance levels displayed in Figure

18 differ greatly from those displayed in Figure"19*
For theQ •strategyf the differences between theinitial search and each feedback iteration are significant*On the first iteration* the two overall measures and theprecision differences from 20% through 50$ recall are
significant at the 5%"level or less, and only at 70 and68

Rocchio Algorithmo initial search— A — first iteration— A — second iteration50\

Rocchio:
Qj+I = n r n s Q i + n s 2ri-n r 2sj-

10 20 30 40 50 60 70 SO 90 100
RecallFirst Iter Minus
Initial Search

Second Iter Ivlinus Second Iter Minus
Initial SearchFirst Iter
% Dif% Sig% Dif% Sigferencenificance ference nificance% Dif-% Sig-

ferencen;ificanceNormalized
Recall

-3.0

60.0

,-0.8

23.5

' ,2.2

17.4

Normalized
Precision

-0.1

55.5

.1.6

20.8

1.8

8.0

1.0
2.1
2.3
2.9
3.2
3.1
3.1

51.8
25.8
14.9
10.4

1.6
2.8
3.2
4.1
4.3

30.7
12.4

4.5

• 28.7
12.0

0.6
0.7
0.9
1.2
1.1
1.4
* 2.3

8.5
5.7
7.4

1.5
1.3
1.1

3.6
3.1
1.9
5.1 . •
10.9
5.7
3.1
11.8
8.5
17.1

RecallLevel 10%
20%
30%
40%

50%
60%
70%
80%
90%
100%

4.3
4.4
4.2

8.8
47.7
43.2
22.1
19.1
21.1

'

5.4
5.8
5.1
5.3

5.3
2.2
3.0

Comparison of F i r s t and Second I t e r a t i o n s to I n i t i a l Search
Differences and Significance Levels - Rocchio Algorithm
Feedback Effect Recall-Precision Curves *Figure 18

69
!
A

Q0*

A>.

Algorithm

60?—^<AN
Qi<.| = Qi + 4 Q 0 + 2 r j
v ^ ^
\
^ ^ A
Q
\ \\

50

° initial search— A — « : , r s * iteration—^""second iterationco•5 «0h
a
ha

CL

301
26 iO

20 50 4 0 5 0 30 7 0 SO SO 100
RecallF i r s t I t e r Minus
I n i t i a l Search% Dif% Sigference nixieance
Normalized
RecallNormalized
Precision
RecallLevel 10%
20%
30%
40%
50%
60%
70%
80%
90%
100%

Second Iter Minus
Initial Search

Second Iter Minus
First Iter

% Dif- % Sigference nificanceference% Significance% Dif-

5.1

0.6

3.7

0.1

0.6

24.9

2.7

1.8

3.6

0.5

0.9

16.5

1,0
1,8
2, 2
3.0

6.8
4.3
1.5
0.5
0.8
5.7
29.
18.
6.

1. 8
2. 5
3. o
3, 7
3. 7
5- 7
4. 4
4. 9
5.

1.3
0.8
0.9
0.4
1. 1
2. 8
19. 5
4, 5
2. 4
2.6

0.8
0.7
0.8
0.7
0. 6
2. 1
2. 0
1.7
2. 0
1.7

11.2
17.7
25.0
26.4
40.7
7
7
4
3
9.8

3« 1
3.
2. 4
3. 2
3> 6
3. 6

6.1

6
5.2

Comparison of First and Second Iterations to Initial Search
Differences and Significance Levels - Q + Algorithm
Feedback Effect Recall-Precision Curves
Figure 19

70
80% recall are the precision differences not significant
at the 10%'• i-levdi-• •On the second iterationf the per-formance difference is significant at the 5% level forall points except 70% recall.

For the Rocchio strategy,

howeverf only one measure (precision at 5>0% recall) showsa significant difference between the first iteration andinitial search at the 10% level or less** ' Even on thesecond iteration, only six of the twelve differences are
significant at the 10% level or leas* two at the 5% levelor ico6«Significance results for the feedback Dec Hi

strategy are similar*
When comparing first and second iterations* the Q •results are no longer more significant than the Rocchio
results*

In fact* the Rocchio results are significant(10% level or less*) for eight of the twelve measures} theQ • result8 for only five.

The significant improvement

between first and second iterations occurs at the high recall end of the Q • curve* while the improvement for the
Bocchio strategy is more evenly distributed*
This difference between strategies in the significanceof the improvement over the initial search leads to a general conclusions

Performance on all measures is less con-sistent for the non-relevant document strategies than for
the Q «• strategy*

However* since the average magnitude of•For these comparisonsf a one-tailed significance level isappropriate, since performance is expected to improve. To
obtain one-tailed values, the reported two-tailed values
must be divided by two* That is* the probability that thefirst iteration is no better than the initial search is £j£or less except at 75~and 60% recall*

71
this improvement is equal for the three algorithms (fromthe significance resultB presented in Figure !>)% it mustbe true that the Rocchio and Dec Hi strategies are betterfor some queries and worse for others than is the moreoonsistantQ •strategy*

The total performance results of Figure 13 indicatethat the queries that retrieve no relevant documents on
the initial search are helped by the non-relevant feedback strategies*

Figure 20 supports this conclusion withevidence that even using feedback effect evaluation% the
Rocchio strategy provides better performance on these elevenquerieso

Figure 14 adds the information that on the aver-age i the total performance on the remaining 31 queries is
not hurt by negative feedback.

The preceding paragraphleads to the conclusion that in feedback effect the Rocchio
strategy gives worse performance on some of these queries*
This conflict between total performance and feedback effectresults requires further investigation of subgroups ofqueries*
The document curve differences presented in Figure 21
provide new information about the performance of the negative feedback strategies*

The

Q •

strategy is taken as

the norm* and the Rocchio and Feedback Dec Hi differences
from

'*) •

are graphed*

For the first fifteen or so docu-

ments retrieved* both Rocchio and Feedback Dec Hi aresuperior in feedback effect performance tou +•After 40

documents have been retrieved„ both are much worse thanC^*N •- 5initial search (Q.+ strategy firsto°. iteration)
first iteration
second iteration% 20 F% Recall

Rocchio Strategy
On Eleven Bad Queries
Feedback Effect Recall-Precision Curves

Figure 20
•

%

R
S
C
A
L
L

o Rocchioo Rocchio
A Dec HiA Dec Hi4

3
2

Q0+* first iteration
Q 0 +, second iteration
Q0+f first iteration
Q0+* second iteration

1
0
-1
-2

!
'

-3
-4

-5

• i .J. >

±

I

1

1 — J

fi

i

8

1 J

1 J

60
100
140
number of documents.
Recall and Precision Differences
Comparing Rocchio and Dec Hi Strategies» 7 8 9

11

13

15

17 19 20

to Q + norm
Feedback Effect Document Curves• Figure 21

180

74
in recall, though about the same in precision.

The recall-precision curves of Figures 18 and 19 average out these
two extremes, and lose the significant information.
Figure 20 strongly supports the conclusion implied bynormalized recall, that on the first iteration non-relevant
document strategies tend to raise some relevant documents,
but to lower others that are already low in rank.

The aver-age advantage of the non-relevant document strategies appears
early in the retrieval process.
has been scanned, therecall.

Q •After 20% of the collection

strategy is clearly superior in

The rank-freezing of the feedback effect/evaluation

affects the ranks of the earliest documents retrieved, so
the recall-precision curves of the non-relevant document
strategies appear superior in total performance but only
equal in feedback effect.

Normalized recall expresses thelater large drop in recall which overwhelms the earlier
advantage of negative feedback.

Thus, the document curves

support and clarify the tentative deductions made from theless detailed measures presented earlier.
Total performance comparisons encourage the use ofalgorithms that employ negative feedback of non-relevant
documents.

However, the feedback effect results indicatethat the performance of negative feedback algorithms ishighly variable.

These findings encourage a search for ameans ot predicting the appropriate strategy for a given
query*For this reason the characteristics of selected

subgroups of queries are explored in the following section.

lb

B.

Characteristics of Query Subgroups

To investigate the performance of positive and negative
feedback in more detail, the available queries are split
several ways into pairs of query subgroups*

Bach sub-group pair represents a contrast based on one or two
characteristics•

For example, all queries with four or

fewer relevant documents might form one subgroup of apair, and all queries with five or more relevant documents might constitute the contrasting subgroup of thatpair*

The six queries that retrieve all relevant docu-

ments with rank 5 or less on the initial search are omitted
from analysis because relevance feedback cannot improve
the feedback effect performance<on these queries*

Figure22 lists the characteristics used for selection and describes
some subgroups for which comparisons are reported*
Each subgroup is statistically compared to the contrasting subgroup using the Wilcoxon Rank Sum test (seeSection V).

All findings of less than 10% significanceare reported in this section*

If the word •null* is usedin the WRS column of a figure* the significance level ofthe indicated comparison is greater than ten percent* andthe 'null hypothesis8 of no difference between subgroups
is supported*

Although significance level from five toten percent are not normally considered meaningful* they
are reported here for two reasons.

First, the WRS test

is conservative when too many ties in rank occur, and thedata contains ties*

Second* the numbers of queries in each

76
Selection
Characteristic

Group Name
(Size)

InitialSearchRetrieval

Eleven Baden)

No relevant documents are retrieved
with rank 5 or less on 'the initial
search.

Twenty-Five,(25)

Some but not all relevant documents
are retrieved with rank 5 or lesson the initial search.

Good Performance(16)

At least one feedback strategy retrieves all relevant documents withrank 15 or less v/ithin three iterations.

Bad Performance(20)

No feedback strategy retrieves all
relevant documents with rank 15 orless within three iterations.

Relevance
Feedback
Performance

Correlationof Modified
Query with
Original
QueryGroup Description

Six subgroups are chosen. The number of queries in each is given in
the following table:

Strategy
Iteration
Low
High
Q +

Relevance
Feedback
Strategy«5>
Rocchio(15)
High-Lowor
Low-High
Number of(17)
Concepts in
Original Queryand
Number of
Relevant
SimilarDocuments

(19)

1
17
19

V

Rocchio2 ° 1-2
1 2
1-2
16 13 16 1917
20 17 20 17 19

The Q + strategy retrieves more documents with rank 15 or less in three
iterations.
The Rocchio strategy retrieves more
documents'with rank 15 or less inthree iterations.
Queries having relatively many relevant documents and relatively few
concepts' or vice versa:
Prom 2-3 relevant and 7+ concepts (2)From 4-5 relevant and 10+ concepts (5)From 5-6 relevant and 3-6 concepts (5)7+ relevant and 3-7 concepts (5)Queries having a number of 'concepts
and a number of relevant documents
similar in magnitude:
From 2-4 relevant and 3-6 concepts (8)'From 4-6 relevant and 7-9 concepts (6)6-h relevant and 8+ concepts (5)Some Query Subgroups InvestigatedFigure 22

77
subgroup is low, and statistical significance is difficult
to prove for small samples.

For these reasons signifi-

cance levels from five to ten percent may indicate areasfor productive investigation using larger query collections
and perhaps more sophisticated statistical techniques*
Twenty-two variables are used for WHS comparisons withineach subgroup pair*

Two are not generated by the search

process; the number of concepts in the initial query andthe number of relevant documents (2 vars«)«

The threesearch-related measures used are correlation of the modified
query with the original query, feedback effect normalized
recall * and feedback effect normalized precision.

Nor-malized recall and precision are calculated for the initial
search (2 vara*) and all three measures are calculated for
two iterations of two feedback strategies• the positive
feedbackQ +strategy and the Rocchio algorithm*whichuses negative feedback (12 vara*)*For normalized recall

and precision, the improvement caused by feedback over the
initial search is used for comparison to remove the effectof initial search differences between subgroups•

To provide

a direct comparison between positive and negative feedback,the differences between thew •and Rocchio strategies innormalized recall and precision for two iterations are used
(4 vara*)»Finally, the difference between the first andsecond iteration correlation of the modified query with theoriginal query is calculated for each strategy (2 vara*)*Obviously significant relationships such as the difference

78
in number of relevant documents between queries with fouror fewer and queries with five or more relevant documents
are not reported*
Normalized recall and normalised precision were chosen
for the subgroup comparisons because they are overall measures of retrieval*

However* the analysis in the previous

section indicates that the normalized figures are notrepresentative of overall performance as indicated by therecall-precision curves and the document curves*

In par-ticularv normalized recall shows a large drop for the
Rocchio strategy, and neither recall nor precision reflects
the initial advantage of the Rocchio strategy displayed in
Figure 21*

Therefore, the normalized measures may not be

the best choice for meaningful comparison of positive andnegative feedback*Figures 24, 28, and 29 in this section display recallprecision curves*

Unfortunately, significance teste between

subgroups for recall-precision curves are not available*
However, in three subgroup pairs, selected by strategy,
performance, and number of relevant documents, • iVilcoxon
Signed Rank tests of the difference between the

QQ+

Hocchio strategies within each subgroup were made.

and
All

differences were significant in both strategy subgroups; nodifferences were significant in any other subgroup*
In the figures of this section, the averag? values ofvariables as well as the WR8 probabilities are presented*
It should be noted that the WHS probabilities do not indicate

79
the significance of differences in average valuet but thesignificance in differences in rank sum when all queries
in both subgroups are ranked*

The average value is reported

because it is a more familiar figure and conveys more intuitive meaning than the rank sum*
The first subgroup pair listed in Figure 22 is familiarfrom the previous section.

Figure 13 and 20 present total

performance and feedback effect recall-precision curves
for the •eleven bad1 group, both showing an advantage forthe nocchio strategy«

Figure 23 presents some of the sig-

nificant WHS findings for this group.

The average numberof relevant documents for the eleven bad queries is 4,3*
contrasting with 5*6 for the remaining twenty-five queries.
The WHS probability that these subgroups represent populations that have the same distribution of number of relevant documents is less than ten percent, so the difference
is of doubtful significance.

When theQQ+

improvement iscompared to the Rocchio improvement9 the normalized recall
and precision indicate an advantage for the
in both subgroups.

Q +strategy,This finding contradicts the recall-precision curves presented earlier, and is misleading forthe reasons stated early in this section.

The meaningfulconclusion to be drawn from Figure 23 is that the differences in feedback improvement between subgroups are notsignificant except for the first iteration of thestrategy.

QQ+

That is0 the performance of the Hocchio strategy

does not depend on whether or not relevant documents are

80•Eleven Bad1 Group:.

Eleven queries that retrieve no relevant documents with rank
5 on theinitial search. •(1

Twenty-Five queries that retrievesome "but not all relevant documents
within rank 5 on the initial search.

Twenty-Five Group:

Eleven Bad

Twenty-Five

WHS
Probability

Number of Relevant Documents

4.3

5.6

<10%

InitialSearch

NR
NP

76.4
42.8

88.0
72.0

<02
- <01

Improvement NR
Q+ Strategy NPoImprovement NR
Rocchio
NP

0.0
-0.2

5.2
4.6

<05
<02

-18.7
-0.5

3.3
3.2

<10
null

1.7
-0.3

5.3
5.0

null
null

-10.9
-2.1

3.5
3.7

null
null

100.0
95.9
4.1

78.5
78.8
-0.4

<01
<01
<02

59.7
50.2
9.4

43.8
45.8
-0.1

<01
null
<01

r

First
Iter«

SecondIter

Improvement NR
Q0+NPoImprovement NR ,RocchioNP
Q0+•'.•.'.

Iter 1Strategy Iter 2
Correlation
Iter 1-2
of modified
query with
Rocchio
Iter 1
original
Strategy Iter 2
query
Iter 1-2

Characteristics ofSubgroups Selected By Initial Search Retrieval

Figure 23

61available for feedback.

This conclusion agrees with therecall-precision curves for this subgroup.

It should be

noted that the low average normalized figures for theeleven bad queries are due to a single queryf query J4,
that is destroyed by all negative feedback strategies.
Since magnitude is reflected in the averages but not in the
ARS test, query 5^ bas a disproportionate effect on the
average figures but does not similarly bias the probabilities.
The comparisons using correlation of the modified querywith the original query show stronger differences between
subgroups than the performance comparisons.

The Rocchio

strategy changes the query more in both subgroups, as expected.

The

^ •

strategy changes the eleven queries not

at all on the first iteration and very little on the second.
The figure for the first iteration correlation minus thesecond iteration correlation indicates that the eleven bad
queries tend to move further away from the original queryon the second iteration, but the twenty-five queries tend
to stay about the same distance from the original query.
The direction of the Rocchio strategy comparisons is thesame as that of theare much weaker.

Q +comparisons, but all correlations

The eleven bad queries change significantly

less than the twenty-five on the first iteration, but on thesecond the amount of change no longer differs. The tendency
for the eleven bad queries to move further away from theoriginal query on the second iteration is stronger for the
Rocchio strategy, so that the second iteration change compensates for the lack of change in the first Iteration.

62
Figure 24 presents feedback effect recall-precision
curves for the subgroups selected by performance*

Those

curves seem to indicate not only better initial search performance % but also greater first iteration improvement for
the good performance group.

The precision level of thegool performance group drops less as recall increases thanthat of the bad performance group*

The normalized recall

and precision reported in Figure 25 indicate better initial
search but slightly worse first iteration feedback for thegood performance group.

The first and second iteration

feedback improvement differences are not significant*It

is interesting to note that the eleven bad queries on initial
retrieval had fewer relevant documents than the remaining
twenty-fivet but the bad performance group tends to havemore relevant documents than the good performance group•
Also noteworthy is the significant tendency of the second
iteration flocchio quory to move iurther away from theoriginal query in the bad performance groupf as thoughsearching farther afield for relevant documents*
tendency is not observed for the

Q +

This

strategy•

Figure 26 describes the general behavior of the raodified queries in relation to the initial query*For bothstrategies the first iteration and second iteration queries
tend to be eladlar in correlation with the originsr query*
For theQ + strategy^queries that don9t move far*from theoriginal query on the first iteration tend to move farther
on the second| this tendency is much weaker for the fioochio

83

#
o
&
o
o

Bad performance group
Good performance group
Second iteration
First iteration
Initial search

60 h

50

40

30.

20

10 L

J8

.J.

10 20 30 40

50 60

70

80 90 100

% Recall
Subgroups Selected. By 'Performance
Feedback Effect Recall-Precision Curves
Rocchio Strategy

Figure 24-

84

Good Performance Group:

Sixteen queries that retrieved all
relevant documents with rank greaterthan 16 in three iterations of atleast one feedback strategy.

Bad Performance Group:

Twenty queries that did not retrieve
all relevant documents with rank
greater than 16 in three iterationsof any feedback strategy*

Good
Performance

• '

Bad
Performance

WES
Probability•

Number of Relevant Documents

4.5

5.7

<10%

Correlation of
Modified querywith original,
Rocchio Strategy

50.9
51.1
-.2

46.8
41.6
5.2

null
null
<02

Iter 1
Iter 2*Iter 1-2•

InitialSearchNP

90.6. 70.5

79.5
57.1

<01
<10

NR
; NP

2.2
2-9/

4.8
5.4

null
null

NP

-5.5
-0.5

-1.9
0.1

null
null

. Improvement,
cond V
Strategy

NR
NP

'5.8
5.2

4.7
5.4

null
null

Iter

NR
NP

-0.9
2.5

-0.9
1.4

null
null

• '•.. • N R

TM.-e*. Improvement,
Iter? V Strategy •Improvement,
Rocchioq- Improvement,
Rocchio'-••','••••:•' NR•

Characteristics ofSubgroup? Selected By Performance

Figure 25

85

WHS
Probability
Correlation of Modified
Query with Original.

First Iter./Second IterFirst Iter./Iter 1-Iter 2
Second Iter/Iter 1-Iter 2

<01%
<01
null

Correlation of Modified
Query with Original.SocchioFirst Iter./Second IterFirst Iter./Iter 1-Iter 2
Second Iter/Iter 1-Iter 2

<01
<10
null

Correlation of Modified
Query .with OriginalQ + / Rocchio

First Iter
Second Iter
Iter 1 - Iter 2

<05
null
<01

V

: Cross-probabilities for
Correlation of Modified Query
With Original Query i

Figure 26

86strategy*

Q+

The first iteration correlations for tho

strategy and Rocchio strategy tend to vary similarly* thesecond iteration queries are no longer related; but the
movement between first and second iterations strongly
tends to be in the same direction* 'Figure 27 reports the characteristics of five of thesix subgroups chosen by correlation of the modified querywith the original query.

For theQ •strategy on both

iterations* queries that are more correlated with theoriginal query tend to have fewer relevant documents andinferior performance*

These findings can be explained by

the behavior of the eleven queries that do not retrieve
relevant documents initially*

For the Rocchio strategy,

there is a slight counter-tendency for queries that remain
more correlated with the original on the second iteration
to have more rather than fewer relevant documents*

The

significant findings for the Rocchio strategy concern the
direction of query change between first and second iterations*

Queries that move further from the original query

tend to have more relevant documents and poorer performance*

This tendency agrees with the earlier finding in

Figure 25a

The subgroups chosen on the basis of

Q •

query

change between first and second iterations are not shown
because for all variables the differences between subgroups
support the null hypothesis*
Thus far no relationships explaining the differencesin performance between positive and negative feedback have

87

Initial Search
Normalized
Normalized
RecallPrecision

NumberRelevant
Correlation of
Modified Query ' First
with Original
Iter

Low
High
WRS

Second
Iter

Low
High

V

WRS
Correlation of
Modified Query First
with OriginalIter
Rocchio
Second
Iter
*

• •

•

•

"

'

•

.

'

•

Low
High
WRS

88.2
81.1
<10%

5.9
4.5
<10%

90.4

6.3
4.3
<01

.

5.1
5.3
null

Low
High
WRS

4.9

Low
High
WRS

4.3

5.4
<10

79.7
<05

73.7
53 v?
<01%
76.5
52.3

<01

84.6
84.3
null

60.9
null

80.3
89.1
null

58.4
68.2
null

92.5
.77.2

74.2
53.1

<01

<01

65.7

'

I

Iter I
minus
Iter 2

5.9<05

Characteristics Of
Subgroups Selected By
Correlation of Modified Query
With Original Query

Figure 27

I86
been observed.

No subgroup pair has shown significant

difference** on the four final variablesp difference between

Q •iterations*and Rocchio strategies for first and second
The strategy subgroups were chosen in an

attempt to explore these differences from the opposite
directionf to select the queries that display differences
between positive and negative feedback and see if theyalso show other differences•superior performance withThirteen queries showing

Q •and fifteen showing better

performance with Rocchio were selected; the remaining eight
queries showed no difference between strategies•
Figures 28 and 29 show the feedback effect recallprecision curves for each strategy in each group*
Q •group| theQ•

In thestrategy causes slight improvementon the first iteration and more improvement on the second
over the initial search, but the Hocchio strategy degrades
performance•

The initial search performance of the Hocchio

group is higher than that of therecall*Both theQ +Q •group until 70%

and Hocchio strategies improve per-formance in the Hocchio group, but the Hocchio improvement
is greater•

In Figure 29 the initial search on the remaining

queries is graphedf showing that initial performance is far
superior for those queries that have equivalent performanceon both strategies*

Figure 30 shows a similar pattern inthe normalised recall and precision*
Improvement caused by the Q +In all cases, thestrategy is statisticallyequivalent in the two groups, but the Hocchio strategy

89

Q0+ Strategy, Second Iteration
Q0+ Strategy, First Iteration
Rocchio Strategy, Second Iteration
Rocchlo Strategy, First Iteration
Initial Search •

A
B
O

o

%

40

P
r
e
c
'i
s
i
o
n

30 L

20 L

10 L
10 20 $0 40

50 60 70 80 90 100% Recall
Subgroups Selected By Strategy
Q + Group
Feedback Effect Recall-Precision Curves
Comparing Positive and Negative Feedback

Figure 28

90
a
D
A

O

60

o

Rocchio Strategy, Second Iteration
Rocchio Strategy, First Iteration
Q + Strategy, Second Iteration
O + Strategy, First Iteration
Initial Search
Initial Search on Queriesin neither the Q + groupor the Rocchio group

50

40

30

20

10
10 20 30 40 50 60 70 80 90 100% Recall
Subgroups Selected By Strategy
Rocchio Group
Feedback Effect Recall-Precision Curves
Comparing Positive and Negative Feedback

Figure 29

91

Q:
R:
Q-R:
Q + Group:
Rocchio Group:

Q0+ strategy
Rocchio strategy
Q + strategy minus Rocchio strategy
Thirteen queries that have better performance with the Q + strategy.
Fifteen queries that have better perfor• mance with the Rocchio strategy.
Qo* Rocchio
V/RS
Group Group Probability

InitialSearchFirst
Iter

SecondIter

Normalized Recall
Normalized Precision

83.9
58.6

82.1
60.3

null
null

Normalized
Recall

Q
R
Q-R

2.9
-16.3
19.2

3.3
2.8
0.5

null
<01%
<01

Normalized
Precision ,

Q
R
Q-R

1.9
-12.0
13.9

1.5
7.2
-5.7

null
<01
<01

Normalized
Recall

Q
R
Q-R

4.5
-14.7
19.2

3.2
7.5
-4.3

null
<01
<01

Normalized
Precision

Q
R
Q-R

4.2
-10.6
14.8

1.4
null '<01
10.7 '-9.3 <01Comparison of 'Positive and Negative Feedback
In Subgroups Selected by Feedback Strategy

Figure 30

92
de ;radea performance in theQ •group*

Sxcept for nor-malised recall in the first iterationf the Rocchio strategy
improves•performance in the Rocchio group more than the*^0+strategy does*

The hypothesis of greater variability

in performance with the Rocchio strategy is again reinforced*
Unfortunately| the WHS tests show no differences betweon theQ •performance*

and Rocchio groups except in feedback

The indication of the recall-precision curves

that the Rocchio group is superior on the initial search is
not supported by the normalized measures*

No differencesin number of concepts* in number of relevant documents* orin query correlations are found*To further investigate strategy differences * threesubgroup pairs are chosen based on feedback improvement in
the normalized measures*

One subgroup includes all queries

that oho* feedback improvement over the initial search for
all measures; normalized recall and precision for two iterations of both strategies*

There are only thirteen queries

in this groupi because of the zero change in the 'eleven bad1
queries with theQ +strategy and the firat iteraDion nor-malized recall plunge often encountered with the Rocchio
0

strategy*

The contrasting subgroup of the 'All Measures9

pair contains the twenty-three queries that have zero or
negative improvement on any measure*

Two other subgrouppairs are chosen similarly* one by feedback in improvementon all. measures of the performance of the Rocchio strategy(17 queries improved on all Rocchio measures * 19 did not)*93
and the other by feedback improvement for theegy (16 queries improved on all

w •

Q +

strat-

measures, 20 did

not)*
Figure 31 displays the significant differences forthe three subgroup pairs*

A tendency for the improved

queries to be less correlated-with the original query is
seen in the All Measures pair.

This tendency is even moresignificant in the pair based on

Q +measures, but it

disappears in the H0cchio Measures pair*

The Eleven

Bad1 queries that retrieve no relevant documents on theinitial search account in part for these findings*

Noneof the queries in thefEleven 3adf group are in the 'AllQ •Measures9 group*

However, three of the eleven bad

queries improve on all Rocchio measures*

The eleven bad

queries have high correlations with the original query,especially on the first iteration of thewhen the correlation equals

1Q^f

strategy

for all eleven queries*

The differences in correlation in theQ •Measures sub-group pair cannot be entirely explained by the elevenqueries, however*

The eleven queries do not improve inboth the All Measures and the
the

Q +

0^+

Measures pairs, yetdifferences in correlation are more significant

than the All Measures differences*
Again an a priori choice of subgroup pairs forces
significant differences in the performance of negative andpositive feedback strategies*

Figure 31 shows no significant

94
All Measures Group:

Improved on all normalized measures
for two iterations of both Rocchio
and Q + strategies.(15 queries)

Not All Group:

Zero or negative improvement on any
measure, any strategy, any iteration.
(25 queries)

All Q + Measures Group:

Improved on all normalized measures.for two iterations or the Q + strategy. (16 queries)

Not All QQ+ Group:

Zero or negative improvement on any
Q + measure. (20 queries)

All Rocchio Measures Group:

Improved on all normalized measures
for two iterations of the Rocchio
strategy. (17 queries)

Not All Rocchio Group:

Zero or negative improvement on any
Rocchio measure. (19 queries)

All
Not
Measures All

V

Iter
1
2

Iter
1-

NR
NP

Iter
2

•

0
'.

All Qo+
WRS Measures

Not
All
Qo+

All
Rocchio
WRS Measures

Not All
Rocchio WRS

82.5
77.8 89.1 =1%
77.9
90.8 <1%
80.6'75.9 88.7 <176.0 90.5 <1
45.7
41.1
54.6 <142.2 52.2 <5Rocchio 1
40.5
50.0
<10
2
42.8
42.2 47.8 null
Correlation of Modified Query With Original Query

87-5
87.1
51.2
48.5

null
null
null
null

-2.0
-5.6

15.2
10.0
15.1
8.8

<1%
<1
<1
<1

NR
NP

-0.4
-1.2

11.5 null
4.8 <5

2.6
12.5 null
0.1
4.7 null
8.4 null -0.2 , 9.5 null
-0.8
3.2 null -0.5
-1.6
2.9 null
Q_+ Strategy Minus Rocchio Strategy

-4.0
-6.7

Comparison of Negative and Positive Feedback
In Subgroups Chosen by Feedback Improvement
Figure 31

95relationship in the
between the

Q +

Q •

Measures pair with the differences

and Rocchio strategies.

Howeverf in the

Rocchio Measures pair all strategy difference measures
show relationships significant at the one percent level.
The relationships in these two subgroup pairs support theconclusion drawn from Figures 28 through 30 that the Rocchio
performance variability creates the performance differences
between strategies.

A tendency for the thirteen queries

that improve on all measures to favor the Rocchio strategy
is significant only for first iteration precision improvement © This tendency supports the difference in recnlImprecision,* curves observed in Figures 28 and 29«

In thesefigures the Rocchio strategy improves the Rocchio groupmore than theQ •strategy improves theQ • group on

the first iteration.
Except for a tendency explained by initial search retrieval , no relationships have been found that can predict
feedback improvement for the
strategy.

Q •strategy or the Rocchio

However, the lack of a relationship between

feedback improvement and initial search performance isencouragingf since it indicates that relevance feedback
causes as much improvement in original queries providing
inadequate information as it causes in initially wellphrased queries.
Neither the experimental nor the analytical approachisolates a single variable that predicts performance differences between negative and positive feedback.

At this95 apointi although several aspects of retrieval behavior havebeen detailed, initial search performance seems to be the96
only effective predictor of final results*

However* itseems anomalous that neither of the search-independent
variables is related to any performance variable*

No sub-group pair shows any difference in number of concepts inthe original query, and differences in number of relevant
documents are significant at the ten percent level orinsignificant*Subgroups based on the number of concepts

or on the number of relevant show no relationship withany variable.
Number of concepts is a measure related to the lengthof the queryf and indicates the amount of detail withwhich the user has specified his needs*

The number of

relevant documents is an indication of how wide a subject
area the user's query is intended to specify within thegiven document collection*

Although these two variables

are theoretically important to retrieval* each has noindividual relationship to performance* and they are notrelated to each other*

Therefore, it seems probable thatthe number of concepts in the original query and the number of relevant documents have some Joint relationshipto retrieval behavior*

In fact* Figure 32 shows that thesetwo variables combined are the desired predictor of performance differences between negative and positive feedback*Two contrasting subgroups are chosen based on the relationship of the number of concepts to the number of
relevant*

In the 9Similar1 group the two numbers are

97
either both'lowf both hight or both in mid-range.

The con-trasting 'High-low| Low-high1 group contains those queries
with Tew relevant end many concepts or with few concepts
and many relevant*

The Similar group attains sii^nificnntly

better performance with tie Rocchio strategy than does theHigh-lowv Low-high group.

The differences between theand Rocchio strategies favor the

Q •

Q •

strategy in the High-low, Low-high group and the Rocchio strategy in the Similargroup*In short| every significant relationship in Figure

30 is echoed in Figure 32. The fact that some Figure 32
relationships are weaker can be attributed in part to theeight •neutral1 queries omitted from Figure 30 but included

98•Similar1 Group:

Number of concepts in original queryand number of relevant documents are
similar in magnitude;
From 2-4 relevant and .from 3-6 concepts,
from 4-6 relevant and from 7-9 concepts,
6 or more relevant and 8 or more concepts.

1High-low, Low-high1 GrQup:

Few concepts and many relevant or
few relevant and many concepts. Not
meeting the criteria of the 'similar'group.
High-low
Low-high

Similar

WRS
Probability

Normalized Rec all
Normalized Pre cision

82.2
60.0

86.4 .
65.8

null
null

Normalized
Recall

R
Q-R

4.8
-10.7
15.6

2.5
3.1
-0.5

null
< 10%
<01

Normalized
Precision

Q
R
Q-R

3.5
-6.8
10.3

1.6
5.8
-4.2

null
<05
<01

Normalized
Recall

.Q
R
Q-R

6.1
-10.4
16.5

2.5
7.7
-5.2

.null
<05
<01

Normalized
Precision

Q
R
Q-R

5.4
-6.1
11.5

1.6
9.0
-7.5

null
<02
<01

*

InitialSearch
First
Iter
•

Second
Iter

••' '

Q

.

Comparing Positive and Negative Feedback
In Subgroups Selected By
Number of Concepts in Original Query
and'Number of Relevant Documents
Figure 32

99
in Figure 32*

Three of these fall in the Similar group;

the remaining five in the contrasting groups

The average

differences in Figure 32 compare favorably to those in
Figure 31.

Except for first iteration normalized recallf

the differences between the Similar and High-low, Low-highgroups fcre as great or greater than the differences between
queries that improve on all Hocchlo measures and those that
don't•The joint relationship of query size and number of relevant documents is of little use for prediction in an operating retrieval system, since the number of relevant documents in the collection is not known at the beginning of thesearch*However, some estimator of the number of relevant

documents might be available to the system before feedback*The user could be asked to state whether he intends his
query to be specific or general, and some users might evenbe able to estimate the number of relevant documents available*

In a larger collection the number of relevant docu-

ments retrieved on the Initial search might be useful for
prediction as the number of relevant documents available.
In this collection the number of relevant retrieved by theoriginal query when N equals 5 correlates highly with the number of relevant documents in the collection*

Spearman1s co-efficient of rank correlation is significant at the one percent level *> K

However, the number of relevant documents

retrieved can range from 0 to ^ only, and this range does notprovide sufficient information for prediction of differences in
performance of negative and positive feedback strategies*

100
rt'hen the number of relevant retrieved and the number ofconcepts are used to predict strategy differencesf the WKS
test results support the null hypothesis.

Neverthelessf asearch for a predictive relationship between query sizeand some estimator of the number of relevant documents
might well be profitable in a larger collection.
The results in Figure 32 indicate the possibility of
taking advantage of the performance differences between
negative and positive feedback by choosing in advance theappropriate strategy for each query.

Another approach is

to develop a single algorithm that causes feedback improvement on all queries.

With this possibility in mind, the factors

causing the failure of the Kocchio algorithm on some queries
in the High-lowt Low-high group shoula be investigated.
It is evident from earlier results that the inferior riocchio
performance on some queries is not caused by a failure to
retrieve relevant documents on the initial search.

In factf

the possible obliteration of the initial query by subtractionof non-relevant documents does not appear to be a general
problem.

Only query 34 is reduced to zero by the Roochio

strategy*

All other queries gain in length on the first

iteration.

Of the ten queries that lose some concepts$

sevengain in performance from the change.
The data presented in this section does not directly indicate

the causes of the variability of the Rocchio strategy.

In

Section •VII-C a hypothesis consistent with all experimental
results is advanced to explain the contrasting behavior of
positive and negative feedback.