3-1
CHAPTER 3
SEARCH REQUEST FORMEJLATION •
->>

\

1.

Introduction\

The dialogue initiated "by user-generated'inputs to a
document retrieval system is a dynamic communication process thatneeds to he optimized if the system is to provide effective service.
A general "block, diagram of a retrieval system delineating possibleuser-system interfaces is shown in Figure 3«1«

I* will be assumed

that the operational environment of the system allows for real-time
interaction between the user and the system, and that this facility
can be exploited in the implementation of the overall request
formulation process. The block Labeled "query formalizer" may be"• interpreted as an initial preprocessing stage designed to buffer theuser from the internal structure of the system.

Simple processes--;such as error detection (spelling, etc.), as well as-more complex ;.ones (vocabulary aids in the form of suggested synonyms and term
relations), may be incorporated here. *The present section,

however, deals with the implementation of the block labeled "query
modifier".

In particular, it is assumed that the system allows for"iterative searching, and is capable' of automatically modifying theuser's original query on the basis of the results of previous
iterations and of the user's evaluation of these results. To this<end the! concept* of search' request optimality is introduced, and the

QUERIST. :..

V
Display

InitialQueiyinterface

ResponseV
QUERY
FORMALIZER

Adjusted
Query
FormalQuery ^

4

DOCUMENTSEARCH AND

QUERY

STORE

SELECTION

MODIFIER

Output±system-userinterface.

QUERIST
Evaluations

Query Formulation- The User-System Interfaces
Figure 3*1

3-3
role of the query modifier is specifically identified with automaticquery optimization.
In evaluating the performance of a document retrieval system,
one must attempt to isolate the effect of the critical variables
which determine system behavior.

The formalization of the notion ofrequest optimality leads, then, to the ability to measure accurately
the behavior of the indexing function under a given query-document
matching relation, since performance variations due to the malformationof a s.earch request can be eliminated.

In this context, then, ganVfrh

optimization can be a powerful evaluation tool for testing index
language devices.

2. Request Formulation

The process of search request formulation in a document
retrieval system is a complex one and depends on particular attributesof the requestor, such as his acquaintance with the referencecollection, his knowledge of the indexing and searching functions ofthe' system, his familiarity with the topic matter being* searched, his
personal preferences as to vocabulary, style, etc.

In effect, eachuser must must make a statistical decision based on his individual
experience as to what formal request statement is most likely to
produce results useful to him. 'It can be assumed, therefore, thatthe a priori likelihood that a usee's.search request actuallysatisfies his information needs varies- over a wide range for atypical user population.

For example, some users will be able to3-4
express quite explicit formulations of their information needs and canbe expected, therefore, to obtain relevant source documents with a highprobability of success. At the other end of the spectrum, however,there are those users with less explicit information needs or with"
only vague familiarity with the subject area being searched.

Clearly,

this class of users is less likely to be able to formulate searchrequests which will retrieve useful references.
Tinder these assumptions it is then pertinent to consider
techniques for reducing search request variance in two distinct
contexts. First, from an operational viewpoint, one would like toprocess search requests which are optimized with respect to the costof retrieval, the cost of optimization, and the value of theinformation to the user.

Second, in the context of retrieval evaluation,

it is desir^able to isolate explicitly the effect of the request
formulation from the effects of'indexing and request-document matching.
Normally, in testiiog indexing devices one compares gross retrieval
results obtained for some sample set of search requests. The comparisons
so obtained reflect the joint behavior of the test queries and theindexing scheme, but do not provide an explicit comparison of theindexing methods alone.

If it were possible, however, to define an

optimal search request (for a fixed indexing technique), corresponding
to any given test query, the comparative retrieval results for the
optimal requests would provide a much clearer evaluation of the power,of the indexing methods, since performance variations due to request,
malformation, would be eliminated.

3-5
3. Request Optimization~*

To define an optimal search request, it is necessary tostart with an explicit formulation of the model wheih specifies the •retrieval system.

In particular it will be shown that a reasonabledefinition of request optimality is directly related to the retrievalor query-document matching function.

In the model outlined in Chapter

1, it was assumed that the matching criterion for selecting reference
documents in response to input queries is the magnitude, of theangular distance'between the query vector image and the vector imagesof othe ^-.source,'documents. It is now convenient to introduce a querydocument correlation function which is a monotonic function ofangular distance in the'vector space (over the range j0[5 180°).
Assuming, therefore, that the output'of a retrieval operation is apartial ordering of all source document representations in thecollection, D, derived on the basis of the angular distance from the
input query image, the cosinie correlation function,

J0(».*) --pfdU- cos@a,b
can be used to induce the same ordering.

(3-D

Note that the correlation

function is inverse to the angular distance in that Q « 0° maps into
P = 1, and |0| -180

into H » -1. Thus the range 0° < |0| <180°maps into the range*T< £> <*f, .so that increasing angular separation
corresponds to decreasing correlation.

It may also be noted that the

restriction of the vector images to nonnegative components (as is the3-6case under the index representation assumed) results in a restrictionof the range of the angular distance to 0°< |©| < 90?. corresponding toa correlation range of 1 >fi> 0.

It is now necessary to postulate an explicit objective for any
given retrieval operation. And corresponding to any search request representation,.^, it is assumed that there exists a non-empty subset D R(D^C D) of the set of reference document tokens D.

This subset, IL, isthat set of document index images which corresponds to documents in thecollection Ju relevant to the search request. As relevance must be
subjectively defined, the specification of the subset, E L , must be made. outside the context of the" retrieval system.

It is then assumed that \;the information needs of the user can be satisfied by the content of •/...
"those documents whose index images are contained in DR.. The case inwhich E_ is empty, i.e. when there are no useful references in thesource collection, will be considered sepaxately. >The identification of the subset D R is the goal of retrieval.
Since the query-document matching function results in an ordering of thesource collection, an ideal search request can be defined as one which
induces a ranking on the elements of D such that all members of the set,
"EL are ranked above (have a higher" correlation) all other elements of E.
Note that in this definition any degree of relevance or ordering among
the members" of the subset E R with respect to their value to the user isignored.
Since relevance is a subjective; attribute of a given search .
request-document collection' pair, determined in theory by the individual

3-8of the reference collection.

The definition of the optimal request

reflects the partition in terms of the statistical properties of thecorrelations of the query and source document index images.
Let q represent the index image of a search request and d. theindex image of a reference, document (d. * T(D.),D..
mathematical terms, the optimal request vector qIncorresponding to a

subset IL of D is defined as that vector q which maximizes:It..

o-l.^(a.V-JrJJp(5;V
h*\
*lt\

(3-2)

where n - n(iL>) the number of elements in D-, and m - n(D) the total
number of elements in the reference collection.
Substituting forjO(q[9d.) and using vector* notation results in:

5*5n

D

V R

* K-

-

i

;

m n
- 0 Z—

*-di
d

(3-3)

M l il

or:

(3-4)

i - j

151

Id.l
1

MV '

m

n

~ o

(—*

• ^

Prom this last equation it is clear that C is just the dot
product of a unit vector along the direction*of q and a vector which

5-9
is a function of the relevant and nonrelevant partition classes of D.
Thus C may be written as:/

C m 5'aand therefore the vector q which maximizes C is:

40 * k a

or:
d.

*„-*

i

(3.5)

*i<K
with k being an arbitrary scalar.
Two observations can be drawn from the result. First, if
the vector sumations are taken over two arbitrary subsets, say R andS, resulting in:

%

-

*

(3-6)

•

r^R

where n.. = n(R) and n 2 » n(S); then 5s.CS

is that vector which maximizes

the difference "between the mean of its correlations with the members

3-10

of R and the mean of its correlations with the members of S.

Second,it can easily be shown from the definition of the vector dot productthat C is maximized by the vector q*= q! subject to the condition thatthe components of q, be nonnegative.
r

Vy

if

The components of q* are given by:

V°j-° ( j - i . «

if 4

(3.7)

<0

Hence, under the assumptions made, an unambiguous optimal(for the criteria stated) query image exists corresponding to any nonempty subset D_ of D. Further, the equation 3*5 provides an effectivemeans of generating such a query from knowledge of the relevant subset
Dr.. In the evaluation of information retrieval systems and inparticular in the evaluation of the. indexing function, of such systems,
this formulation of an optimal search.request provides the ability toisolate' the effects of indexing from .variances due to request'formulation. An optimal search request measures the ability of theindex transformation to. differentiate a particular set of documents fromall the others of a collection.

In an evaluation situation, where one

assumes prior knowledge of the document subset relevant to each test
query, the retrieval performance of the optimal query corresponding to•the relevant subset provides a direct measure of the ability of thesystem to extract from the index representations of documents the same'kind of information the user can extract from the natural language.

/

3-11
4. Relevance Feedback

The formulation of the optimal query corresponding to aparticular set of documents has no direct implication on operational
information retrieval, since the set of documents in question is theobject of the retrieval search. Thus there is no aOpriori way togenerate an optimal request, since the ability to do so would
eliminate the need for retrieval. This kind of circularity suggests
a strong analogy to feedback control theory.

Consider therefore asequence of retrieval operations which start with an initial query
q . A modified query cL is to be produced based on the original
output, such that (L is a better approximation to the optimal query
for this user than qQ.

Let the user specify which of the retrieved,

documents (resulting- from the search using q ) are relevant andwhich are not.

This information constitutes an error signal to theretrieval system.

On the basis of the error and the original input,

it is then possible to produce a modified query (new command input)
such that the retrieval'output will be closer to whatw$he;user-.degires,©r.<:such that the modified query will be closer to the* optimal query
for this user's needs. The effectiveness of this process will dependon how good the initial query is, and on how fast the. process ofiteration converges to the optimal request.
On the basis of the formulation of request optimality,
we then seek a procedure for using the relevance feedback from an
initial retrieval operation to produce an improved query.

Let qQbe the-original retrieval request, and let the results of the retrieval

3-12

operation be a list in correlation order of the documents whose images
are most closely related to q . The user examines this list andspecifies which of the documents in it are relevant and which are not.
Since the modification is to be based only on a sample of the relevant
documents (assuming that some are missing from the retrieved list
associated with q ) , the modified request will be formed by adding tothe' original query, q , an optimal query vector based on the feedback
information.

The resultant vector (the new query) should thus be abetter approximation to the optimal query than q , and should,
therefore, produce better retrieval when resubmitted.
Hence we seek a relation of the form:

5-, - f(40fH»S)

where q. is the original query, E is' the subset of the retrieved set
which the user deems relevant, and S is the subset of the retrievedset (based on q ) which the user deems nonrelevant.

The form suggested

immediately by the above is:n5, -<*,i0

+«2

i

1_ \

where Hj - n(E), n g = n(s), E -£ry,r 2 ,r± - l \I(3.8)

f_"I , S = ^ ^ , s2,....snl' where all vectors have been normalized to unit length, and oc and OC
are arbitrary weighting coefficients.

3-13
The modified query q.., then, is a weighted vector sum of theoriginal query vector plus the optimal vector to differentiate themembers of the set R from those of the set S.
the vector sum of q

In other words, q*.isplus the optimal vector for the subset of thereference collection for which the user has provided relevance
information.

If equal weight is given to the original query and the

optimal vector based on the feedback information, equation (3?7) ?iay~bewritten in the form:
n

•5i

2 '

h - *1 V o + n2 Z *± " n1 Z *i
1-1

(3.9)

i-1

If q1 is to be restricted to a vector with only nonnegative components,
the following may be used:su - ior i- > o
0

for ^

< 0 .

Figure $.2 provides a two-dimensional geometricalinterpretation of the relevance feedback, request modification
process.

Part (a) shows the initial query q

located between therelevant and non-relevant document vectors. The vector r-s shown inpart (b) is the optimal vector (i.e. the vector which maximizes thefunction C of equation (3.2) ) for differentiating the subset
R •• i x* ,r2l , .from S "• f s,. ,s2 j . Part (c) shows the resultant ofadding q

to the normalized vector sum r-s, wliich results in the new.v. ;:.;• v . • •'•

.

. ••

"..:'.ia) Initial query (q0)> relevant docs. (r1,r?)and nonrelevant docs. (s 1 f s p ).

b) Sum of relevant - sum of nonrelevant
document vectors.

t 51 = V* 5 "*)*
Doc.
r

i

,2
S

1

S

c) Resultant of q 0 + normalized (sumof relevant - sum of nonrelevant).

2

V

*0
0.71
0.92
0.92

1.00
0.92

0.71

0.0

0.38

d) (^Correlations of query vectors
qQ and q1 with doc. vectors.

Geometrical Representation Of Relevance Feedback
Figure 3.2

3-15
query vector q.. • The table compares the correlations of q

and <Lwith the document vectors.
The modifications to an initial query vector which areproduced by the relevance feedback algorithm may receive the followinginterpretation:

concepts, i.e. components of the initial query which

are more significant in the document images of the relevant subset
than in the nonrelevant subset will be. emphasized (i.e. increased inweight and visa-versa).

Thus the weighting of the original query

terms, derived from frequency counting, will be adjusted on the basisof the statistical/evidence derived from the sample output for which
the user provides relevance feedback.

In addition, concepts notincluded in'the original query but which are also useful in *;.'
differentiating the relevant from the nonrelevant documents will be
added to the* modified query iaiage. Such concepts (components of theindex space) can be* expected to be useful in retrieving otherrelevant documents not explicitly identified by the original query,since all* relevant documents (which can be successfully retrieved)
must be sufficiently related to be localized in some region of theindex space.
The basic relation for request modification using relevance
feedback (equation (3«8) ) can be modified in various ways by
imposing additional constraints.' For' example, the weighting of theoriginal query could be a'function of the amount of feedback such thatwith large amounts of feedback, the original query has less effect on
the resultant than with small amounts'of feedback. Another constraint,

3-16

for example, might be to regulate the number of non-zero components ofthe modified query on the basis of the degree of overlap of acomponent among the relevant documents identified by the user. There
are a number of additional variations to this basic relation whichmight be investigated.
The modification process described above for generating q1
from qis amenable to iteration and therefore can be written in the .

general form:

where q. is'the ith query of a sequence, and R

and S

are the relevant

and nonrelevant subsets, respectively, identified in response to
retrieval with query q..

It is expected that the rate of convergenceof such a sequence to a near optimal query will be rapid enough tomake the process economical; however, this is to be investigatedexperimentally.

In any case, the convergence rate' can be estimated by

the user, since it is reflected in the stability of the retrieved output.
The user's original query serves to identify a region in theindex space which should contain relevant dQeuments.

Since he has no

detailed knowledge about the characteristics of the document images inthe store, it is unlikely that the vector image of his query is* w •;;...
optimally located.

By identifying relevant' documents in the region,

the user provides the system with sufficient information to attempt to3-17
produce a modified query which is positioned centrally with respect
to the relevant documents while maintaining maximum distance from thenonrelevant documents. This is possible, however, only in so far as
the index images of the relevant set are different iable from those of
the nonrelevant set.
In this context it is possible that the information needs ofa user might be best satisfied by a multiple rather than a single
search request.

This would be the case, for example, if usefulreferences happened to be mappdddby/theoindex transformation into
several distinct regions of the. index space. Since the user ingeneral has no a priori means of determining whether he should use
a single or a multiple search (other than his own intuition,) it isof interest to consider automatic means for generating multiple
searches. Assume, for example, that the relevant set R identified bya user after an initial retrieval operation contains document images
sufficiently seperated so as to be considered only slightly related.
Figure 3*3 shows an example in two dimensions. Under the circumstances portrayed the relevance feedback adjustment algorithm is notuseful since, in fact, there is no single vector close to both r;rj....v
relevant document images. This suggests that useful information canbe derived by measuring the degree of 'association among the elementsof the relevant subset identified by the user. Such information iscontained in the document-document correlation matrix which characterizes this subset.
Consider, for example, the situation described by the5-H
document-document correlation matrix of Figure 3*4«

It is._ assumed

that the set ft «-J r* ,r0,r2fr.*r- ( has heen identified as a relevant
vi

^

^

4

pj

subset in response to some initial search request, qQ.

These document

images are correlated against each other producing the correlation
matrix shown. If this matrix is used as a hasis for partitioning theset R hy some clustering technique, two subsets R
2
R

-

r

vrA

wi

-^ r e s u l * *-r,. ,rp,r-and

I n "this case then, the system can generate

two new queries by using each of these subsets together with the nonrelevant set S. Thus the following pair of new search requests can beformed:l] « n;n2qQ * n g

£

r± -

n\

r,€R

B±

£

(3-11)

s4€S

i

i

and

51 « ^

n 2 q 0 +;n2

^

£± -

nj'

2

Z.*i
1

f

/ 1\

f

'-

/ 2\

•

^

s±

• ,

(3-12)S.€S •.

1/\

where n. • n(R ;, IL - n(R J, and n 2 - n(Sj.
On the basis of a partition of the relevant subset identifiedby the user, two new search requests have been formed from a single
original.request. Roughly, this procedure amounts to allowing theuser to. identify particular documents in the collection and request
additional references "like" those he has singled out. By examining
the degree of association among the identified documents, it is possible' to determine i f this can be done efficiently with a single searchrequest or whether multiple searching is required.

3-20In a theoretical framework, the request optimization process
focuses on the power of the index transformation to distinguish setsof associated documents within the store by eliminating variances due
to particular query formulation.

In an operating context, relevance

feedback'provides a technique whereby the system user can extract thefull power of the index transformation to his retrieval problem, at thecost of iteration (possibly on a sample collection from a large
document store.)

5.

The Case of No Relevant Documents

The definition of an optimal search request assumed the existrence of a nonempty set of documents relevant to each user's searchrequest.

The relevance feedback query optimization algorithm developed

from the definition: assumes that in response to the retrieval output
generated by an initial query, feedback is received identifying bo£hrelevant and nonrelevant documents." Consider now the case in which
either inhere are no relevant documents in the collection or none are
identified by the user response to the initial retrieval operation.
this case the user is faced with a certain degree of uncertainty.

InIf

he* is interested in ascertaining that there are in fact no useful
documents in the collection, one possibility .open to him is as follows:he'may rephrase his search request and resubmit it.

The relevance feed-back query modification algorithm, whett implemented with no relevant•documents identified, will provide just the kind of adjustment to theorigitial query which is useful in such a Case. The modified query3-21

would be produced by the equationn

2

h - n2% - I! h

^^

i-1

where S ^ s ^ S p ,s £ constitutes those documents originally-

retrieved but judged nonrelevant.
In this case the modified query vector q,. represents avector in the index space which is both related to the original query,and also moved from that region of the index space which was identified by the original retrieval operation. A sequence of suchmodifications allows controlled pertubations within the region of theindex space of interest.

Thus, even in the case where an initial

search provides no relevant documents, the relevance feedback
algorithm can be used to provide helpful query modifications to an
iterative search process.

6. Experimental ResultsA.

Some Sample Search Bequests
To test the effectiveness of the search request modification

process based on relevance feedback as outlined above, some experiments were conducted using the SMART automatic document retrieval .
system. A set of sample search requests and a collection of 405
abstracts from the computer literature originally published in thej.'x.-i '.l.1,." :...} . x-t;'.07.!.p. V L . .;.louo;.:oixic Cor,jliterc (l\L,...-oh *- G o / k ^ b c : ; :\: . r.v :'.*!. .ble f-.>r th:tr. •,.»ir:-)j;:o.""':"''\c/j^)

?-22
IRE Transactions on Electronic Computers (March - September, 1958) was
available for this purpose.

Both the reference documents and eachof the search requests which had been submitted at Harvard in thenatural language were indexed using the SMART thesaurus. As the searchrequests had been used in a variety of previous retrieval experimentswith this collection, relevance judgments'for each query were alsoavailable, representing a full manual search through the complete
reference collection.
A full retrieval ordering of the source documents with respect
to each sample query was available, consisting of the correlation ofeach search request index image with every reference document image..
Prom the initial portion of the retrieved list (ordered by descending
correlations), two sets of documents were specified:

one containing

relevant documents and one containing nonrelevant documents. The vector
index images of each search request, and the images of the documents inthe two associated subsets were used as inputs to a Fortran program
written to implement the query modification process. The output of
this program was a new query vector suitable for input to the SMART
system.

The modified query images could then be correlated with thereference collection and the results compared with those of the original
search requests.
Table 3.1 describes the program steps used to implement therelevance feedback query modification algorithm.

Figure 3*5(a) shows

the English text of a typical query. Figure 3• 5(h) shows the explicit
thesaurus mapping for the terms included in this query and part (c)shows the index image of the query in vector form (see Appendix A for3-23

Read an initial query vector qQ (in integer format),convert it to a unit vector, and store it in the array
Q(l), I - 1,K.

(N is the dimension of the index language

vector space.)
2. Read in the set of relevant document vectors r. ,J

j - 1,1^, convert them to unit vectors, and store themin the array R(l,j), I = 1 ,N; J - 1,HL.

3. Read in the set of nonrelevant document vectors s.,
j - 1,np, convert them to unit vectors, and store themin the array S(l,j), I • 1,H; J » 1,Np.
(Note that since the dimension of the index space wasN • 511 for^thetthesaurusuusdd, and since a document
vector typically has about 35 nonzero components, theprogram actually. handled the vectors in a condensed
format^)4»

Form a new query vector represented by the array:

i

w

-J-1

"J-1

2

5. Normalize Q'to'unit length:

1

N

h

Q1"(I)^Q1.(I)/1-1 •Program Steps for Producing Relevance Feedback
Modified Queries
Table

3.1

6. Convert CL to an integer format array:;• Ift(l) < h ^ ( 1 ) ^ 1 2 ] ,\(where [xj is the largest integer not exceeding x, and
512 is a scaling factor.)•i

7. Apply the screening algorithm to IQ(l) to produce the]resultant modified query vector:
flQ(l) if X ^ I ) V (X2(I) A X (I)) = 1|. IQ(D«^ 0otherwize•where X..(l), X 2 (l), and X,(l) are logical variables
defined "by:X ^ l ) = 1 if Q(I) > 0
N1

X2(I) = 1 if T E(I,J) > [N/2J
x5(i) - 1 if [ E ( I , J ) > [ s(r,j)
J-1

'.J=1

Table 5.1 (continued)'3-25
an explanation of how the concept weights are derived.). The firstpart of the algorithm implements equation (5»9) directly and results
in a new query image as shown in part (d) of Figure 3«5«

The appli-

cation of a screening process to this vector results in a final
modified query image as shown in part (e). The screening process isdesigned to eliminate any negative components in the modified query
image, as well as to reduce the positive nonzero components to thosemost likejy to be useful. This latter feature is incorporated since
the statistical evidence implicit in the user's relevance judgments
may represent a relatively small sample.
Concepts which are retained after screening either a) occur
in the original query, or b) occur in at least half of the relevant
documents identified in addition to "being more frequent in therelevant set than in the nonrelevant set. The screening algorithm
thus serves to prevent the modified query from "becoming too specialized to those relevant documents identified in the initial retrieval
operation.

In addition, reducing the number of nonzero components inthe modified query image'provides increased efficiency. With fewer
components the modified search request requires less storage space andcan be correlated with reference document images with fewer Operations.
Negative components in a modified query imiage represent
propertigs in the index space which are more "significant among thenonrelevant documents retrieved by-the user's original search request,
than among the retrieved relevant documents.

In principle then, there

are no conceptual difficulties in allowing such negative weights. This
is in contrast to generating property vector index representations of26

Automatic Information Retrieval and Machine Indexing.

a) Text of Search Request "I-R Indexing".

Query Term!

Concept Code(s)automatic

119 'information

53, 350

retrieval

26

machine41, 119, 338

indexing

101t) Thesaurus Mapping of Query Terms.

Concept CodeWeight

26

12

41
53
101
119
338
350

4
6
12
16
4
6

c) Compressed Representation of Query Vector.
(Only the components with nonzero weight are shown.)

A Typical Sample Search Request
Figure

3.5

3-27
12 (

13 (-157)

16 (.

17)

26_ ( 202)

29 C -78)

34 (

17)

5 6 C 48)

39 ( - 7 6 )

40 ( 1 2 )

£L [

18)

44 (

12)

47 C 24)

49 C 24)

51 C 47)

57 ;

13)

58 :

37)

59' i:

24)

68 [ - 4 0 )

73 [

74 <i

24)

77 <: -53)

86 (:

25)

93 (:

T01 I: 273)

107 <[-107)

108 (; 126)

110 <i49)

113 ([ 1 2 )

114 (:48)e) •130 (;

12)132 (:

25)

135 (:

13)

143 (;

38)

146 (:

15)

147 (: -55)

38)

119 (: 153) ' 121 <:

24)

17 (

13)

12)

136 ([

24)

142 (;•• 12)'149 (.

49)

158 ( • 24) • 167 (: ; 37)

170 (> 72)

173 (

12)

176 ( • 12)

178 (

13)

179 (

12)

182 (

8)

184 (

12)

202 (

25)

218 ( •' .24)

220 (

12)

237 (

24)

239 ( ' 2 4 )

250 (

12)

260 (

261. (

25)

308 (

24)

338_ <

496 (

25)

497 (

86)

350. ( 101)51)'

353 ( ' 2 4 )14)d) Basic Modified Query' Vector after Relevance Feedback.
(Shown in'compressed form where ' n (w) implies that, componentn has weight w.)

26 ( 202)4^0108 ( n$)110 ( 149)

U9^( 153)558 (550-( 101)

497 ( 86)

14)

18)

52.(

47)

57)

101. ( 275)

H 9 ( 49)

167 ( 57)58 (e) Pinal Modified Query Vector for Request I-R Indexing.
(Produced from the vector shown in part (d) by the screening
process.)

Figure5«5 (continued)

5-28

>

referencefliisirrctfntmtt:documents, where a negative weight would imply that
one could measure the degree to which a certain attribute was. lacking.
For this reason, and because the recognition of negations or exceptions
in search requests would require a high degree of syntactic sophistication, the simulation system (SMART) does not have any facilities forprocessing query or document vector images with negative components.
Such-components ar/ising from the modification algorithm (see Figure
5.5 (d)) were eliminated then, to preserve compatibility with thesimulation system. Allowing negative components in a modified version
of a user's search request would amount to an effective increase in thequantization of the index space.

It may be postulated then that thiswould lead to improved performance. An experimental investigation into
this possibility was not feasible, because it would have required substantial changes in the simulation system.
Figure 5*6 (a) shows the initial portion of the retrieved output generated for the original query "I-R Indexing" which is describedin Figure 5.5*

The relevance feedback used in this example consisted

in identifying the initial two relevant and two nonrelevant documentsin the retrieved list. For reference, the titles of all the relevant
documents for this search request are provided in Table 5«2. Figure
5.6 (b) compares the retrieval results of the original and modified
queries with respect to this full set of six relevant documents which
are in the reference collection.

Note that the modification has sub-stantially improved the performance with*respect to three out of thefour relevant documents not originally identified by the user. Figure •5.7 compares the correlation distributions of the original and relevance

5-29

j

Document
Rank.

Document
Number

1
2
3
4
5
6
7

167
166
188
221
5H
55
79

a)

Correlation

.46

|

!

4
7
15
15
17.
2
5

.40
.58
.58
•57
.56

Relevant

Relevant

Retrieval Results Using Original Query"I-R Indexing" Including User Feedback

Document
NumberResults Using QueryModified by User Feedback

Correlation

221
79
5
80
48
126

, Ranks of • Document
Re levantNumberDocuments

.58
• 56
.26
.26
.25
.21

RecallPrecisionb)

Not Relevant
Not Relevant• 45

Retrieval Results
Using Original QueryRanks of
Relevant
Documents

User Feedback

i

1

79 .

2

221

.47

4
5
6
25

5
126
80
48

-55
.51
.50
.17

RecallPrecision

.976
.728

Comparison of Search Results Using
Original and Modified Queries

Query Processing Using Relevance Feedback for
Search Request n I-R Indexing*1
Figure 3.6

Correlation

-54

.991
.928

30

Doc. No.

Title

3

The Role of Large Memories in Scientific
Communications

48

A Business Intelligence System

19

Machine-Made Index for Technical LiteratureAn Experiment80

Rapid Retrieval of Information

126

How Much Science Can You Have At Your
Fingertips

221

Chemical Structure Searching With AutomaticComputersii:

Titles of Documents Relevant to Search Re.qu.est "I-R Indexing"

Table 3.2

3-31
y

off :
scale

15 T
(Crosshatch indicates
relevant documents)

CO
O
O
CH

O

10 4-

§
5 4-

I
0)

n fe^n

^

1.0

•5

a)

Original Query j

-4

•fS*

.2

I ' -3.1

Correlation

15-H
CO

o
o
O

toff
scale

(Crosshitch indicates
relevant documents)''

10 -r

B

I

5 t

m
1.0

t

•3

m.

.1

Correlationb) Modified' Query !

.V

Correlation Distributions for Search Request "I-R Indexing"
Figure3.7-

3-32
feedback modified queries. •Figures 3-8 and 3.9 compare the retrieval results of two
additional original and relevance feedback queries. Note that for thequery "Analog-Digital" shown in Figure 3.9, one of the relevant
documents

namely document 46, experiences a decrease in its retrieved

rank from 21st to 46th while the raisks of the other relevant documents
are substantially improved.

This may be interpreted as implying thatthe index image of document 46 is less associated (in terms of angulardistance in the index space) with the other relevant documents than it
is with the original query.

In general, this effect occurs, whenever

the index images of the documents relevant to a search request form
distinct clusters in the index space, and when the set of relevant
documents identified by the relevance feedback consists substantiallyof members from only one of these clusters.

In some cases it will be .

possible to identify such situations, and automatically to generate
multiple queries for such search requests. For the case in point,
however, the single document (no. 46) is assumed not to be identified
by the original query.

In this instance, then, there is no effective

way to increase the probability of retrieving it.

Such situations mustthen be interpreted (assuming that there are no grounds on which toquestion a user's relevance judgments), as arising from deficiencies
in the indexing'process or from the in&erent information loss which
necessarily accompanies it.

B. Average Results and Successive Iterations
The query modification procedure as illustrated in the

5-55

I
Document
Rank

Document
NumberCorrelation

1
2

551
555
550
165

.65
•42
.41

5
4
5
6
7
8

9

•32
.27

———
j
Not Relevant ?
Not Relevant I. i
Not Relevant |

. .25

54
555

10

Relevant
Relevant
Relevant
Relevant

..36
• 35

82
1
208
225

User Feedback |

.24
.21

a) Retrieval Results Using Original Query for "Pattern
Recognition" Including User Feedback

Retrieval Results
Using Original QueryRanks of
Relevant
Documents

Document
Number

1

551
555
550
165

!

2

I

5

I
!

6
9

4

.26
I•

27

55
54

Correla- I [ Ranks of j Document
Relevant ! Number
tiohDocuments i

•65
. .42

i
I

.41
• 56

1
2
5

I ' 551| 550• 1 555

5
6
7

163
1

1

.52

54
205
224

• 24
• 17
• 17

11
16

.16

- 17

54
5H
205
59

.12

50

224

5H

-I

59
RecallPrecision

I

Results Using Query
Modified by User Feedback

.972.
.864

RecallPrecision

Correla- j
tion

.66
.60
• 55
• 57

.52
.29
• 25
• 19

.19
.16
.989
.925

L
b)

Comparison of Search Results Using Original and Modified Queries
Query Processing Using Relevance Feedback for
Search Request "Pattern Recognition"?•
Figure 3.8

3-34

1

1

1

; Document
Rank

;

... .

1
2

i
i
i

:
—

.42

7

8

Relevant
Relevant
Not Relevant
Relevant
Not Relevant
Not Relevant

• 40

362
296
308
307
226
88

6

User Feedback

I

. 157
165

3
4
5
'

' Correlation

Document
Number

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

1

a)

Retrieval Results Using Original Query"Analog-Digital" Including .RelevanceFeedbacks

i

.

. -

Results Using QueryModified by User Feedback

Retrieval Results
Using Original Query
Ranks of
Relevant
Documents

Document
NumberCorrela- |tion

Ranks of
Relevant
Documents

Document
NumberCorrelation

1
2
4
19
21

157
165
296
42
46

.42
•40
• 37
.27
.26

1
2
3
4
40 .

296
157
165
42
46

• 58
• 56
• 53
•42
.20

•

•

Recall.983
Precision .918

Recall.984
Precision .870

Query Processing Using Relevance Feedback for Search
Request "Analog-Digital"
Figure 3*9

3-35
examples shown in Figures 3.6 through 3.9 was applied to the full setof search requests available. Average results comparing theperformance of the original and relevance feedback modified queries
are shown in the form of a precision vs. recall graph in Figure 3*10.
Since this means of exhibiting performance is based solely on theranks of the relevant documents resulting from the query-document
correlation process, it does not exhibit the true improvement which
results from relevance feedback modification.

This may be appreciatedfrom the example shown in Figure 3.11, which illustrates another .of
the sample queries. In this case both the original and the.modified
query exhibit ideal performance (i.e. the relevant documents are allranked higher than any nonrelevant documents).

Thus the precision vs.

recall graphs for both cases are identical. The correlation
distribution, however, indicates that, in fact, the modified query
provides greater discrimination of the relevant set from thenonrelevant set.

In any case the average results as shown in

Figure 3«10 indicate that the modification algorithm results insubstantial improvement.
The request optimization procedure as illustrated byequation (3»10) can be used iteratively.

The querist can, if hedesires, provide evaluation information about the output generated
by the first iteration and request that a second query modification
1
1
take place. If R and S are the relevant and nonrelevant subsets*r* The method of construction of such recall-precision plots has
previously been described in detail.4>5

Quasi-Cleverdon
Graph

Modified
Queries
Precision

Precision vs Recall for Initial Queries and Queries Modified "byRelevance Feedback (Averaged Over 24 Search Requests)
Figure

5.IO

3

j

Document
Hank

1

Document
NumberCorrelation

User Feedback

91

• 57
• 56
• 55
.-50

Relevant
Relevant
Relevant
Relevant

•55

—_

!
•

!

i
I

1
2
3
4
5

257
500
94
565
219
547
68

6

7
8

• 29
—

.28
.27

•

i

a)

Retrieval Results Using Original Query for"Random Numbers 11 Including User Feedback

Document
Rank

1
2
5
. 4

5
6
7
8
b)

Document
Number

91 '

94*
500*
257 219 <• •. 2543471

195

Correlation j

• 74
• 73
• .70
.69
• 37
•31

I
i

.26
.26

Retrieval Results for Modified Query

Comparison of Retrieval Results Using Original and Modified
Query for Search Request "Random Numbers"

Figure 3.11

3-38
2
2
identified in response to the original query, and E. and S -are thecorresponding subsets identified in response to the modified query,then, for the second iteration, the sets ET « E1VJE,2 and .ST = S1\JS2
are available for the optimization algorithm.

Basically, twoalternatives are possible: the optimal vector to differentiateTTdocuments in E from documents in S may be used as a perturbation of
the user T s original query; or this vector may be used as a perturbationof the query resulting from the first iteration. In practice this
could be left for the user to decide, depending on his interpretationof the output from the first iteration.
.In the general case the expression for the nth modified queryin which all modifications are made to the original query can be
written:«n-«Vo+0fe"i Z - r ± " s 2 Z _ S i Jr^R T

where RT - \J

R* ST = 0

(3.H)

s. £ ST
1

S 1 , n - n(R T ), n - n(s*), and 0( • and 0<2 are

*—

i-1
i»1
weighting coefficients.

If each modification is made to the preceding resultant query
image, the iteration formula "becomes: ' " • *Si = «lVl + (*21^ r.)-*
T " ** s.€
h SI
€R

1

(3.15)

3-39
Since operationally it is expected that only a few iterations
would ever be used, the differences between these alternative
formulations is not of major significance.

If the user is satisfied

with the relevant documents identified by the previous iterations. andwould, in effect, like to find others which are closely related tothese documents, queries produced by equation* (3*15) would be moresuitable.

If .on the other hand, he is interested in maintaining1 a

broader search, the iterations produced by equation (3.14) will not be
as dependent on the relevant documents previously identified (members'of R T ) .
Average performance results for a second iteration of relevance
feedback produced by each of these alternatives are shown in Figure 3-12.
The results obtained with the original and first iteration queries areincluded for comparison.

As can be seen by these graphs, the results

obtained from using the iteration formula of equation (3*15) aresomewhat better than when the second iteration starts from theoriginal query.

However, in comparing the behavior of thesealternatives on individual queries, there are some cases in which thereverse is true. Figure 3»18 illustrates an example of this. In thiscase it is clear that documents 315 and 264 are not clustered in theindex space with the other relevant documents; and therefore, these
documents suffer more drastically from successive iterations (equation(3-15) ) than from successive modifications to the original query(equation (3*T4) )'•*k

3-42I

C.

Convergence

The performance improvement which results from a query
optimization produced "by relevance feedback modification is a functionof the quality of the initial query, the degree of association of theindex images of the relevant documents, and the amount of feedback.
To investigate the influence of the latter parameters, some additional
experiments were conducted. Figure 3-14 shows the retrieval results asa function of the amount of feedback for the query "IR-Indexing',1 andFigure 3.15 for the query "M9 Natlang".

The document-document

correlation matrix for those ..documents-relevant to the query "IEIndexing" are shown in Figure 3.16.*

Thus-the rapid improvement

obtained even with a small amount of feedback can be attributed to thefact that the members of the relevant set are all closely associated.
In the case of the query "M9 Natlang", this is not true, and the
document-document correlation of the first five relevant documents,
retrieved by the original query indicates this. The relevance judgments
for this query were made, assuming a very general point of view.

Inthis case it might be of use to produce multiple modified queries by
seeking clusters in the relevant set. A possible partition based on •",'
the document-document correlations is shown in Figure 3^6, and thispartition was used to generate two modified queries following equations' (3.11) and (3.12):

The retrieval results for these two modifications

are shown in Figure 3.17. This figure illustrates how each of these
queries is useful in retrieving some relevant- documents.

The fact thatsome of the relevant documents have low correlations with both of the5-44i
J Original*•

Modified Queries

N-1

Query

N-5

!

.

,

25»5

;

\

•

i

R
a
n
. ,k
o.: s
f

6

R.
e,
1
e
1

I

• 1 .

/
V

1

I

1

1

i

5

!

2

<

2

!

5

5

i

5

4

i

6

!

9

|

8

5

9

7

i

10

15

6

15

15

12

15

18

!

16

10

18.

22

!

18

15

i
!

•

!

a

22

29

I

22

16

1

*i.

24

52

26

55

I. *

17

:

20

27

54

24
27

59

56

28

26

52

55

52

44

59

60

50

.46

69

69

66

51

111

87

105

96

251

98

122

275

540

269

157
248

.222

.260

t
D
0
1

j

C

m
e
n
t
3

!

21

i

1 Average Corr.
| of All (19)iRelevant) Documents! Average Corr.
i of ist 19
i Nonrelevant
Documents! Difference

]

• 247

i

. .265

i
i

1

•

•515

.255

.288

.267

-.068

-.053

-.628

-.004

*(N relevant andN nonrelevant documents used for relevance feedback)

Retrieval Performance as a Function of Amountof Feedback for Query'f,M9 Hatlang"
Figure • 3.15

j.

Document
No.

221

3

80

• 48 !

126.24 ! -38
1.0
! -39

•33

• 32

.29

• 30

• 37
• 36

•49

• 42

.40

1.0

.56

• 37

1.0

•41

79
i

221

1.0

.79
3

j 1.0

80
. 48

126

L^l

j

a) Correlation Matrix for Documents Relevant to Query"I-R Indexing".

iDocument
No.

221
223

I
221

223

314

•80

1.0

• 15

• 32

.33

1.0

314
80
|

.19

.09
1.0

I 112

I

• 14
[

•25

i

.13
1.0

|

.15

|

.09

1.0

112

b) Correlation Matrix for a Subset of the Documents• Relevant to Query "M9 Natlang".

D 1 = {221, 3 H , 80}.D2 - ^225, 112}c) Document Clusters Derived from the Matrix of Part (b).
Document-Document Correlation Matricies
Figure

3.16

-46

j

RetrievalWith Relevance Feedback

H - (112, 223}

R - {221, 80, 5143

j Ranks ofj Relevant| Documents

1.1.2
2

I

4
6
9
10

j

U

16
18

22
29
55
55
!

Document
Numberj

Ranks of
Relevant
Documents

i_

1

!

I

Results

With Relevance Feedback|

I

Retrieval

Results

42

51
54
65
166
212

221
223
115
222
185
81
115
5
255
80

Document
Number
!
j

|

1

|

• 221

2

!

3

80

j

6

126

8

5H

10

162

12

48

19

j

25
'

5H
126
162
48
79
116
125
114

3

34

112

81
115
79
222
223
183
113

38
39
40
42
66
84

255

140"

11-6

161

125

299

114
i

Retrieval Results for Two Queries Produced
from Original Search Request "M9 Natlang"
Figure3.17

5-47
modified queries is indicative of the broadness of the relevancejudgments used in specifying I I .
The use of multiple queries in general, must be justified interms of the expected improvement in retrieval performance comparedwith the added cost of an additional search.

Thus in respect tosearch cost, a two-way multiple search is equivalent to an additional
iteration of a single query.

Since the cost of query modification by

relevance feedback" is likely to be a small fraction of the cost of asearch operation, the typical user maximizes:••bis return by supplying
a good relevance feedback sample (i.e. by carefully examining theinitial retrieved output). Multiple searching may, however, bewarranted in those cases where the user must obtain access to every •relevant document.

In such cases one can assume that the value ofobtaining the reference justifies the additional cost.

48»

REFERENCES

Rocchio, J.J. and Salton G., "Information Search Optimization and
Iterative Retrieval Techniques", AFIPS Conference Proceedings, Vol.
27, Part 1, Spartan Books, Washington, D.C. 1965
Curtice, R.M. and Rosenberg, V., "Optimizing Retrieval Results with
Man-Machine Interaction" ,. Center for the Information Sciences,
Lehigh University, Bethlehem, Pennsylvania (1965)
Salton, G., et al., "Information Storage and Retrieval", Reports
ISR-7, ISR-8, National Science Foundation, Harvard Computation Lab.,
June and Dec. 1965
Salton G., "The Evaluation of Automatic Retrieval Procedures Selected Test Results Using the SM&HT System", American Documentation,
Vol. 1£, No. 3, July 1965
Cleverdon, C.W., "The Testing of Index Language Devices", ASLIB
Proceedings, Vol. 15, No. 4, April 1963^""X