ISR-9
August, 1965
XXII.

XXII-1DISTINGUISHING RETRIEVED FROM NONRETRIEVED
INFORMATION: THE CUT-OFF PROBLEM
S. J. Sillers

1.

The Cut-off Problem

A fully automatic information retrieval system must have thecapacity to recognize those documents which are relevant to a given searchrequest*Although the final decision to accept or to reject a document isa binary one, relevant documents may differ greatly in their pertinence tothe request under consideration. Moreover, since relevance is as yet notmathematically defined, there is generally no clear dividing line between
the relevant and the irrelevant.

Therefore, in a retrieval system a measureis usually employed to quantify the similarity between documents and requests,
and a cut-off point is chosen to separate accepted (that is, hopefully,relevant) and rejected (that is, hopefully, irrelevant) documents.

It is

the problem of choosing this cut-off point which is considered here.

2.

Possible Methods of Solution
In the SMART automatic document retrieval system a correlation

between each given request and each of the documents on file is calculated
after content analysis, by one of a number of possible methods. The documents are then ranked in order of decreasing correlation coefficients.

HII-2The cut-off point has heretofore been chosen by either eliminating all
documents with correlation coefficients below a certain threshold value,or by simply recovering all documents in their ranked order. The first
method appears unsatisfactory for use with the SMART system because of
the heavy dependence of the correlation coefficients on the processing
technique, while the second is practicable only under experimental conditions because of the potentially large size of the file.
A more natural cut-off might be devised through considerationof the behavior of the correlation coefficients as a function of theranks of the documents. Although these ranks are discrete and integralvalued, the correlation points may be plotted, and continuous curve fitted through adjacent points with straight lines, for instance. The curve
so obtained is monotonically decreasing, and has a slope defined everywhere but at the sample points themselves. Standard differencing methods
may be used to study the properties of this curve, and hopefully, to givesome insight into a solution of the cut-off problem.

Figure 1 shows thefirst 20 points of a sample correlation curve. The circled correlation
values correspond to documents actually believed relevant.

XXII-3

Correlation
Coefficients
1,0-.8.

SMART processing method:
S t a t i s t i c a l Phrases
Request:Pattern Reeg.

,6.Jj"•" -15"»V15

2bDocuments Ranks
Ranked Correlation CoefficientsFigure 1
If it is assumed that the break between relevant and nonrelevant
documents manifests itself by some peculiar behavior of the correlation
values, several possible candidates for a cut-off point readily present
themselveSo

The largest drop between successive correlation coefficients

occurs at the point of the minimum (largest negative) first forward difference, while the most radical change in the structure of the curve lies
near the point of maximum magnitude of the second forward differences. Ifa correlation coefficient is considered as the probability that the given
document is relevant, then, since each document is evaluated independently,
the product of the N highest correlation values represents the probability that all of the N corresponding documents are relevant.

XXII-UIn t h i s case a confidence l i m i t must be chosen before the cut-off point canbe determined.

3«

The Computer Program
To investigate the r e l a t i v e merits of the cut-off methods suggested

above, as well as several variants of these methods, a series of cumputations
were made using data obtained in previous experiments employing the SMART
system.

These computations were performed on the 709U computer with a FORTRAN

program designed to allow as much f l e x i b i l i t y as possible in the combinationsof cut-off methods studied during a p a r t i c u l a r run.

The main routine of t h i s

program handles a l l input and output, as well as the computation of evaluations t a t i s t i c s for the r e s u l t s .

The cut-off indices themselves were calculated bya subroutine coded in such a way that additional methods might e a s i l y be i n serted.

The methods included in t h i s subroutine were as follows:(the cut-off point, or l a s t ordered document r e t r i e v e d , i s that document having
the property described)1.

lowest correlation coefficient above a specified threshold;2.

l a s t forward difference with magnitude above a specified threshold;3.

f i r s t forward difference of maximum magnitude;li.

second forward difference of l a r g e s t magnitude if t h i s differencep o s i t i v e ; next point if negative;5.

l a s t second difference with magnitude above a specified threshold if
t h i s difference i s p o s i t i v e ; next point if negative;isxxn-5
6.

last product of correlation coefficients above a specified
threshold; (this product is taken over the ordered coefficients
through the point under consideration).

The data required by the program consist mainly of the ordered correlation values corresponding to each request, for each of the SMART procsing methods considered.

These correlation coefficients, along with theindicies of their associated documents "within the document file, wereentered on punched cards. For the evaluation of the cut-off methods, theindicies of those documents actually deemed relevant to each request(previously determined manually) were also supplied on cards. The remainderof the data included parameters to be used in the designation of the chosen
cut-off methods.
The statistics used in judging the methods were the usual recall
and precision measures, recall, being defined, as the proportion of relevantmaterial actually retrieved, and precision as the proportion of retrieved
material actually relevant. More precisely,*recall=. .

rnumber of relevant documents retrieved
number of relevant documents in f i l enumber of relevant documents retrieved.
" t o t a l number of documents r e t r i e v e d

Since both high r e c a l l and high precision are desired, the program wasused to calculate the sum of these measures as well as the separate values,
so t h a t an o v e r - a l l performance index might be obtained.

To summarize ther e s u l t s , averages of these measures were then calculated over the whole setof document requests for each of the SMART processing methods, as well asover subsets of general and specific r e q u e s t s .

(A general request i s ,roughly, one in which the number of relevant documents i s at l e a s t 10.)

XXII-6lu

Data Sets Examined
The data used in the computations consisted of the ranked correlation

coefficients obtained by eight of the SMART processing methods, four of thesemethods for a t o t a l of 2k requests, and the remaining four methods for 17 r e quests.

The basic document f i l e against which the requests had been comparedconsisted of a set of k0$ a b s t r a c t s of documents published during 195>9 in theIRE Transactions on-Electronic Computers.

Of the requests eight were judged

to be of a general nature and the r e s t specific.

(This i s the p a r t i c u l a rgrouping of the requests used by J. Rocchio and M. Engel in t h e i r report onr e t r i e v a l r e s u l t s obtained with the SMART system.)
In order to reduce the amount of keypunching necessary, i t was assumedt h a t the number of correlation values examined for each case could be taken as
only s l i g h t l y larger than the maximum number of relevant documents associatedwith airy request.

In p a r t i c u l a r , i t was assigned t h a t the 35> highest ranking

correlation coefficients would be s u f f i c i e n t , and t h a t the inclusion of additional
points would not change the r e s u l t s .

This assumption w i l l be found valid by i n -specting the data.
Each set of 35> points was processed by the following ten combinations ofcut-off methods ( l i s t e d in Part 3) and parameters, denoted as runs "A" through"J":" Rocchio, J . , and Engel, M., "Test Design and Detailed Retrieval Results"
Information Storage and Retrieval, Report No. ISR-8 to the National Science
Foundation, Computation Laboratory of Harvard University (December 196U).

XXII-7Runs

MethodParameterABC
DEFGHIJ

12
23h^
5666

«35.02,015.02
.015
.05
.025
.02

For each c u t - o f f method and f o r each of the e i g h t SMART p r o c e s s i n gmethods and a b a s i c s e t of 1? r e q u e s t s , t h e r e c a l l , p r e c i s i o n , ando v e r - a l l measures were averaged over;(a)a l l requests(b)

a l l specific(c)a l l general requests

requests

These results were then averaged over the eight SMART methods. For thefour SMART methods for which seven additional specific requests wereavailable, separate averages were calculated over a total of 16 specificrequests to give some indication of the statistical validity of the results.

5.

Results and Conclusions
The results of these averaging procedures are shown in Figs* 2-6from which the following conclusions may be drawn:
1.

The relative performance of the cut-off methods does not depend
heavily upon the underlying SMART processing methods since thecurves in Figs. 2 and 3 cross infrequently, and retain a consistentshape.

XXII-8Cut-off runs
Harris 2 thesaurus
statistical phrases
hierarchy down
hierarchy up

syntactic phraseso---onull thesaurus
a— --^logical vectors*• --* titles only

Recall Averaged over 17 Requests
Figure 2

XXII-9Cut-off runsoA*-* Harris 2 thesaurus
o statistical phrases
a hierarchy down
* hierarchy up

syntactic phrases
to null thesaurus
a fc logical vectors*-* titles only
Precision Averaged Over 17 Requests
Figure 3

-10

l.U

1.2

A—-a—-ft—-6A-

1.0

0.8

0.60.Ui. recallo precision
A over-all

0.2

0.0

—r--r-~T~

CEF-rGH

T-IJ

Cut-off runs
SMART processing methods included:
Harris 2 thesaurus, statistical phrases, hierarchy down,
hierarchy up, syntactic phrases, null thesaurus,
logical vectors, titles only.
Averages Over Eight SMART Processing Methods
and 17 Requests
Figure hXXII-11l.U
recal]o precision
A over-all— specific requests.-- general requests

1,21.00.8 J

0.6

O.U

0.20.0Cut-off runs
SMART processing methods included:
Harris 2 thesaurus, statistical phrases, hierarchy down,
hierarchy up, syntactic phrases, null thesaurus,
logical vectors, titles only.
Averages Over Eight SMART Methods for Nine Specificand Eight General Requests
Figure 5mi-i2i.U

i1.2„—-&—-.A
1.0J

10.8

0.6

0.1*.
O
A

0.2

0.0-rB

recall—9 specific requests
precision — - 16 specific requests
over-all1— iEF-rG-rTHJ

Cut-off runs
SMART processing methods included:
Harris 2 thesaurus, statistical phrases,
hierarchy down, logical vectors

Averages Over Four SMART Methods, Specific Requests
Figure 6

XXII-13
2*

There i s a definite inverse r e l a t i o n s h i p between r e c a l l and precision^
low r e c a l l corresponding t o high precision, and conversely*

3*

This inverse r e l a t i o n s h i p accounts for the surprising f l a t n e s s of thecurves for the o v e r - a l l s t a t i s t i ch*The same cut-off methods produce the best precision and r e c a l l values
for both specific and general requests, although the r e l a t i v e heightsof the curves leads t o an inverse r e l a t i o n s h i p for the o v e r - a l l s t a tistic,

5*

Higher r e c a l l values account for the fact t h a t the o v e r - a l l s t a t i s t i c
i s higher in the case of specific requests than for general requests*(The precision i s a c t u a l l y higher for the general r e q u e s t s . )6*Increasing the number of specific requests did not change the r e s u l t s
substantively, although the o v e r - a l l s t a t i s t i c was smoothed*

7* Method 6 which tends to even-off the number of documents retrieved
from case to case i s the l e a s t s a t i s f a c t o r y of the methods*
8#

None of the more complicated methods produced o v e r - a l l r e s u l t s subs t a n t i a l l y superior to method 1 which i s perhaps the most i n t u i t i v e l ypleasing of the methods*