XII-1

XII.

Query Splitting Using Relevant Documents Instead of Queries In Relevance Feedback T. Leventhal and R. Miller

Abstract Iterative search procedures permit the user of an information retrieval system to "update" a query following the display of some type of information. Relevance feedback attempts to phrase a theoretically best way of The use of

discriminating between relevant and nonrelevant items. [1]

relevance feedback has many applications in information retrieval. [2] This paper attempts to explore the use of query splitting as a method of relevance feedback. The SMART retrieval system is used. All experiments Evaluation of the

are performed on the Cranfield 200 thesaurus collection.

results of these experiments are based on recall and precision tables. Suggestions are made at the end of the paper for further investigation of the uses of query splitting in information retrieval systems.

1.

Introduction Many experiments have been done with user interaction in automated

information retrieval systems.

The results of these experiments have proPrevious

ven that user interaction increases retrieval performance. [3]

work done by Borodin, Kerr, and Lewis [4] concerned itself with the problem of query splitting. The query splitting algorithm used at the time involved

a relevance judgment of the five documents ranking highest with the original query. Document-document correlations of the relevant documents retrieved

XII-2

were used to group these documents.

If the correlations exceeded a certain

constant, the documents were put into the same group; otherwise, they were separated. A new query was formed for each group using the formula:

4+i - Q i + JK - i\
where r K nonrelevant items retrieved by Q. . Q. is the (i+l)th query for group j , and j , n K Q. is the original query,

is a relevant document in group

are the two highest ranking

Certain modifications of this formula This process

were made for cases where no relevant documents were retrieved. could be repeated for each subsequent query.

Work done by Crawford and Melzer [2] also led to the problem dealt with in this paper. formula
N

A modification was used of the general query update;

v l 1 R. + *i2
i=l where Q. Q. , is the new query being formed, R. are relevant documents, and N. Q.

,

N

i=i

is a query formed prior to

are high ranking nonrelevant " . Y

documents.

Here, all the coefficients were set equal to zero, except

Thus, only relevant documents were used as a new query. As will be seen in the next section, the problem undertaken by this paper is actually a combination of the work done by these two groups of authors. Query splitting will be done using only relevant documents in the

new queries.

XII-3

2.

Motivation and Assumptions Regular query splitting (that done by Borodin, Kerr, and Lewis) and

the use of relevant documents in feedback both, in general, increase retrieval performance as measured by recall and precision. [2,4] By combining

these, it is hoped that this increase in performance remains. It is assumed that the person using the system would be able to tell whether the documents retrieved by his query are relevant or not. a query retrieves documents which fall into separate groups. Sometimes,

There may be

other documents which are also relevant and which would fall into these groups, had they been retrieved. The retrieval of these additional relevant An example is shown in Fig. 1.

documents is the purpose of this project.

It is important that this method of query splitting should only be used where it would contribute to retrieval performance. must hold to make this feedback process at all practical. Many conditions First, the person

requesting a search must be able to make very good relevance judgments. He must also be able to tell if the relevant documents retrieved by his first query would serve as better queries than his original. Query splitting

should only be used if the documents retrieved by the original query fall into distinct groups. If this is not the case, splitting would result in A classical example of this is the query

an overlapping of the searches. about aerodynamics of birds.

Here, a decision as to the use of query splitIf it contains

ting depends upon the nature of the document collection.

books specifically about aerodynamics of birds, then query splitting should not be used. Splitting should be used when the person making the request

would have to settle for books about birds or books about aerodynamics. Another major assumption involved is that the original query does not do very well in retrieving relevant documents. If the original query

XII-H

A X

query q relevant documents relevant documents retrieved and used as new queries

8

CO

A

new queries

Cii)

relevant documents retrieved by new queries

CiiiJ

Illustration of Query Splitting Using Only Relevant Documents as Feedback

Fig. 1

XII-5

does do a good job, then any type of feedback could only result in a little improvement at best. If the original query retrieves no members of a group

of relevant documents, then it is very unlikely that query splitting will help retrieve members of that group. What this project proposes is actually a stronger splitting of the query than was done by Borodin, Kerr, and Lewis. Whereas their method moved

the split queries closer to, but not inside, groups of relevant documents, this project puts the split queries right inside the groups such as shown in Fig. 2. It is hoped chat this method increases the retrieval performance

of the system.

3.

Implementation The experiments are performed on the Cranfield 200 collection which

contains 200 documents and 42 queries. and query vectors is used. using all 42 queries. system. query.

The thesaurus form of the document

First a full search is done on the collection

This search is carried out under the SMART retrieval

At least the top twenty ranking documents are displayed for each The ranks of these documents are determined by the magnitude of the Relevance judgments are made for the

cosine correlation with each query. documents retrieved.

(This has been done for the Cranfield 200 collection).

If a query retrieves two or more relevant documents, the cosine correlation between these documents is determined. control subroutine called by MASTER. This is done using a

The subroutine reads in the query It then locates

number and the relevant documents retrieved for that query.

the document vectors, uses INNER to find their cosine correlations, and prints them. If the original query retrieves no relevant documents or only

one in the top twenty, other methods of feedback are used to increase

CD

original query and relevant documents retrieved by it

CLil

location of new split queries by method of Borodin, Kerr, and Lewis

Cxii) location of new split queries by proposed method

Comparison of Query Splitting Methods Fig. 2

XII-7

retrieval performance. Once the correlations between relevant documents have been determined, the documents are split into groups for each query. will be used as the new queries. These groups

The splitting is done by comparing each

relevant document against the other relevant documents retrieved by the same query and seeing if their cosine correlations are above 0.5. is, the documents are put into the same groups. separate groups. If it

If not, they are put Into For example,

A document may be in more than one group.

if the correlation matrix for documents 34, 35, and 36 was the following:

34 34 35 36 1 0.60 0.38

35 0.60 1 0.58

36 0.38 0.58 1

the groups formed would be (34,35) and (35,36).

This grouping could be done

by programming but since the size of the collection used is small, they are done by hand in the present case. Programming could save time for grouping

documents of larger document and query collections. After the groups are formed, new queries are generated using CRDCEN. If only one document is a member of a group, then the new query is the document itself. The relevant documents for this new query are the same as the If two

relevant documents for the old query from which it was retrieved.

or more documents are members of a group, then a new query is formed by adding the weights of the concepts of each document. Again, the relevant

documents for this new query are the same as the relevant documents for the old query. SMART is again used to do a full search of the collection with the

XII-8

new queries.

Final rankings are obtained and average recall-precision graphs

are done by the computer. The results obtained by the new split queries and an evaluation of these results are contained in the next section.

4.

Evaluation and Results Evaluation is provided by comparing the results obtained by the

first iteration of a conventional relevance feedback run against the results of the split query run. The conventional run uses the sum of the two highest ranking relevant documents retrieved plus the initial query as a new query. Only twenty-four of the forty-two queries in the Cranfield collection produce groups of relevant documents for query splitting* In some

instances all of the relevant documents associated with a query are used to split the query. For this reason only sixteen of the queries provide any

meaningful basis for evaluation. Fig. 3 is a comparison of the recall-level averages of twentyfour queries for the split query search and the conventional feedback search. The higher precision at low recall for the split queries is caused by the use of relevant documents as new queries. These relevant documents are always retrieved first by the split queries. This does not help the user because he is already aware of these documents. At higher recall, the conventional feedback run shows higher precision than the split query run. A better method of evaluation is to use the residual document space for recall-precision graphs. The residual document space contains only those documents which were not shown to the user for relevance judgments after the initial search. This type of evaluation is done for individual

XII-9

1.0 •9| .8 .71

O Conventional A Split Queries

Feedback

c o •.5

•3 .2

.2

.3

1

I

.4

.5

.7

.8

.9

Recall Comparison of Conventional Feedback with Split Queries
Fig. 3

XII-10

queries in the second part of this section. For each of the sixteen queries which are split, there are two oc more lists of ranked documents that are retrieved. A single ranking of docu-

ments is obtained for each original query by merging the lists adcording to document-query correlations. If a document appears in more than one list,

it receives a rank according to its higher correlation. In some cases a query can be split in more than one way depending upon the number of documents initially shown to the user. tested in two ways for the merged lists of documents. This variation is

The increase in rele-

vant documents obtained by the split query run over the conventional feedback run is noted as a function of the number of documents given to the user after the initial search. This is done for the case where no documents are The same thing is done for the residual

dropped from the document space. document collection.

These results are tabulated in Fig. M , consisting of -

three tables resulting from ten, fifteen, and twenty documents being initially shown to the user. The numbers at the top of each column tell whether

the increase is measured for the highest ranking documents among the top five, ten, fifteen, etc. The tables show that query splitting seems to give When

good results when the entire document space is used for evaluation.

the documents which have been previously seen are dropped from the document space (which is a better criterion for evaluation), very little improvement is seen. In most cases, query splitting does no better than the convent:'.onal In some cases, it even does worse. These graphs

feedback technique.

Fig. 5 contains a sampling of recall-precision graphs.

are based on residual collection evaluation for the merged rankings of the split queries. In some cases, one method is better than the other, but nost

XII-11

Query Number

Increase in relevant (no documents dropped from document space) 5 10 __ 15 __ ™ +1 _2 +1 41 f2 — —, +1 fl — -1 -20 „ +1 tl -1 — — — tl — 25

Increase in relevant (previously seen documents dropped) 5 10 20

7 13 15 16 18 24 28 31 39 Totals

+1

— tl

— —

^1 tl

__ —

-1 +1 +2

__ tl +4

__ — —

„ — tl tl tl

-1

—

r1 -

—

User Initially Sees Ten Documents 2 5 7 3 11 34 37 Totals +3 43 tl -1 -1 -1 — 41 tl — tl tl — +1 +1 tl
+i

„ __ —

-i „ —

_2

-1

-1

„ +1

User Initially Sees Fifteen Documents 4 11 13 16 Totals | t4 t2 tl tl +3 tl tl +2 +7 +3 tl tl +2 +7 t3 tl tl tl +6 +3 tl +2 tl +7 tl tl t2 -— tl tl --

User Initially Sees Twenty Documents

Increase in Number of Relevant Documents Retrieved

Fig. 4

2

.0 .9 .8 .7 c o .6 to o .5 0) .4 3 .2
' ' '

O •

Conventional Feedback Split Query

U
.2 .3 .4 .5 .6 .7 .8 .9
' i * I ' I *>

Recall Query 16

1.0
.9 .8 .7

o 6
to

c

o .5 a> . 4 .3 .2 .1

0

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

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

Recall Query 2 8

Recall Query 3 7

Sample Recall — Precision Graphs on Residual Document Space
Fig. 5

XII-13

of the time the differences are so slight that it really does not make any difference.

5.

Conclusions Using just the documents a s split queries instead of using them to ,

modify the split queries does not cause an appreciable change in the results of the project done by Borodin, Kerr, and Lewis. From this it can be con-

cluded that when the documents are added to the query to modify it, they swamp the original query. The original query takes on a minor role.

When using a small homogeneous collection such as the Cranfield 200, the results obtained by query splitting are not significantly different from those of the conventional feedback search. One reason for this is that the Some-

groups of documents existing in the document space may be very small. times only one document belongs to a group.

if this is the case, then there Another

can be no additional relevant documents retrieved in that group.

reason, as stated before, is that sometimes no member of a group of relevant documents is retrieved by the initial query. One suggestion for further research in query splitting is to use different document and query collections. homogeneous collection of documents. The Cranfield 200 is a very small

Query splitting may be more practical

when used on a larger, more varied collection, a situation which is possibly more common. Research can also be done using high ranking nonrelevant docuA very important area of study Knowing when to

ments as negative feedback for split queries.

is determining some sort of query splitting use algorithm.

use query splitting and when not to use it is extremely important in getting good results.

xn-m

References

1

G. Salton, Automatic Information Retrieval, Class Notes, Computer Science 435, Cornell University, 1969. R. G. Crawford and H. Z. Melzer, The Use of Relevant Documents Instead of Queries in Relevance Feedback, Report No. ISR-14 to the National Science Foundation, Section IX, Department of Computer Science, Cornell University, 1968. E. Ide, User Interaction with an Automated Retrieval System, Report No. ISR-12 to the National Science Foundation, Section XII, Department of Computer Science, Cornell University, 1967. A. Borodin, L. Kerr, and F. Lewis, Query Splitting in Relevance Feedback Systems, Report No. ISR-14 to the National Science Foundation, Section VIII, Department of Computer Science, Cornell University, 1968. R. Dietz, T. Horowitz, and W. Riddle, Relevance Feedback in an Information Retrieval System, Report No. ISR-11 to the National Science Foundation, Section IV, Department of Computer Science, Cornell University, 1966. G. Salton, Automatic Information Organization and Retrieval, McGraw Hill, Inc., New York 1968.

2

3

4

5

6