III-lIII.

A New Evaluation Measure
J. Joiner and L. Werner

Abstract
The problems of evaluation and the needed criteria of evaluation
measures in the SMART system of information retrieval are reviewed anddiscussed.

Performance characteristics of a good evaluation measure areexamined.

The suggested measure

Pr„ N (P<R/n), (the probability under

the hypergeometric distribution, that the precision could be strictly lessthan that precision attained, wheredrawn,

R = number relevant in the sample

N = total number in collection andn = size of sample drawn) isintroduced and tested against the various criteria needed for a good evaluation measure.

1.

A statistical test of significance is explained.

Introduction
Among the principal obstacles to the evaluation of information

retrieval methods are the following:

1)

Interpolation between points of recall results in errors
which are unsatisfactory in one way or another, depending
upon the type of interpolation used.

2)

A recall-precision curve sometimes gyrates wildly and theaveraging of many curves over queries has questionable reliability.

3L

The statement "method A is better than method B u often
depends upon the value one is measuring.

A unique value

measuring both recall and precision would be best.
4)

Queries with different numbers of relevant documents do notreceive different amounts of credit, although just by randomIII-2chance it is easier to get a relevant document for a querywith 30 relevant than for one with 4- relevant*5)

It has not been determined how to handle the evaluationof feedback methods in relation to the relevant documents
retrieved before feedback.

This report will attempt to discuss and propose solutions to these
specific problems.

2.

Problems of Evaluation
One important aspect of information retrieval is obtaining a value

for a given method which is a true measure of the method1s effectivenessover many queries.

On a recall-precision graph, the points of recall where

one measures this effectiveness are .1, .2, . . . , ,9, 1.0-.

However, theonly points available for a query with n relevant documents are 1/n, 2/n,. . . , n-l/n, n/n.

Obviously, for queries with different numbers of rele-vant documents, one may expect that none of the query ! s points will coincidewith the points .1, .2, . . . , .9, 1.0.

But presently, by interpolation cf

some kine, the precision values are found for each query at these points.
Fig. 1 shows one such method.

There can be no real justification for any

method of interpolation used, for it is impossible to estimate a discrete
function at a nonexistent point.

Therefore, what is needed to solve thisproblem is a new base index for the graph that would involve no interpolation.
An index that would, over many queries with different numbers of relevant
documents, have only common points for all queries.
The averaging of points of recall-precision where interpolation mustoccur tends further to distort the measure of effectiveness.

But even overRanks ofRelevant
Documentsin-;o„mCVJ^ —<frC J -oCVJ

Q_Total No. ofRelevant
Documents<frQueryNumberOCXCOCVJa)

co>

3

Q>

a(ZocoCt

szCLo*~CDcoif)o<Dw_Q_1alO"OCD(TooCDo:ILOIII-4points that coincide with equal recall, different values can be obtainedby different methods of averaging.

Even at these common points, the values

being averaged are somewhat in doubt.

No correlations are made in the pre-cision values for the generality number (jG = number of Relevant/total number in collection), which reflects how easy it would be, under random conditions alone, to select relevant documents.
should control this randomness factor.
that when the generality ratio

A good performance measure

Control should be in the senseis decreased in a way which preserves theobserved performance level, the effect of the generality ratio on a performance measure could be observed.

The measure proposed is known to re-flect the generality number under equal performance but a method of splitting a collection into two collections suggested by R. Williamson has notbeen tested.

3.

Criteria for a Good Evaluation Measure
A good performance measure should fulfill the following criteria:l)Recall values measure the effectiveness of a method bycomparing the number of relevant documents retrieved toto total number of relevant documents, while precision
measures this performance by comparing the number ofrelevant retrieved documents to the total number of retrieved.

These intuitively seem to be the best measuresof performance available.

Their biggest drawback isthat they are two unique values not one.

A good measure

should reflect both.
2l

The generality number, as stated before, reflects thedegree of effect that pure random chance selection will
have on the method of retrieving relevant documents for acertain query.

With this controlled queries can be com-111-5

pared on a more common basis.
3)

In theory Cat the least 1, the measure should appeal to the user
and tester and the values obtained should have a logical range.
A range from 0 to 1 best suits a measure of performance andeffectiveness.

Any system which is effective at all shouldhave values of the measure closer to 1 than to 0.

4.

The Probability Measure
A very large urn is filled with 2Q.0 documents.

For queryare 20 documents that are relevant and 180 that are not.

qthereIf, at random, 20documents are drawn from that urn without replacement, the probability thatless than 3 relevant documents are chosen completely at random isP

E,200 <*<*> = PH,20Q- CR = 2 l t P ^ 2 Q Q (R = U=,20^180
2 K 18 ^C+,2oo.

l20..180
1 K 19/rl 20;

200tt P ^ 2 Q 0 CR =0>

r20s,18CkKj0( ))20^20200l20

This is equivalent to finding the probability by random chance that theprecision is less than 3/20 for
CP<3/20).

FR 2 0 Q CR<3) = P R 2QQ

CR/n<3/n) = P R20Q

The higher this probability is, the less likely it would be thatthe precision achieved was obtained by chance.
ated at any point

This measure could be evalu-n (equals the number of documents retrieved) that might

be wanted for investigation.
As precision increases fromfrom P R 2 0 0 ^ P < m / n ; )and Pt0?

m/n to (m + l)/nH 2QQ('P<^m + 1 ^ / n ) w h i c hise, this value goesl u a l toPH2 00^<m^

9 0 n^ R m + !) whereP

H , 2 0 0 ( R < m ) = PH,200CR = m " 1 } + PH,200CR = m " 2 ) + • • • + PH,200CR = 0 )III-6and^ O O ^ 1 1 ^When= P

H,200 C R = m ) + ^ ^ Q O 0 1 = m'1}

P„ ^^^CR<m) is subtracted fromP^ 2pnCR<m+l)+' ' • + P H,200 ( R "CR<m) < P

PtR<m+l)P(P<m+l/n = p 2 ) , and"the answer is always positivesince one more single hypergeometric probability is added toSince0)

Pis equivalent to stating that

CR<m+l) .
PHCR/n<P<m/n = p )p. <p 2 , then as precision increases the perform*-nancemeasure increases.
This same argument holds for recall because

PH , 2 0 0 ( r < m ) = P H , 2 0 0 C r / R < m / R ) = P H,200 Crecall<m/R) .

As the recall increases fromm/r

tom+l/rmore probability is added to themeasure and it therefore increases.
The probability itself incorporates the generality number and it will beshown by example how this generality affects the measure.

All three of the cri-teria which are most needed by a unique performance measure are therefore combined in this value.

The theoretical range, 0-1, of this measure is also appealing

to testing procedures and analyzing of results.

Some measures for arbitrarily

chosen results are shown in Table 1.
The use of this measure for feedback is the same as without feedback except that when the ranks of the relevant documents retrieved in the first passare frozen the measure adjusts for this by use of a new generality number.
pose for a single query and two methods
number of documents = 200
number of relevant documents = 12

Sup-Ranks of Relevant Documents:
1, 2, 3, 10, 11, 14, 15, 20, 40, 50, 69, 78.

NumberRelevant

NumberDrawn

Measure123333
3334
5556
7
7
7
7
788888888
888

1234
56
78910
1112
13
14
15
16
17
18
19
2Q
21
22
23
24
25
26
27
28
29
30

0.94000
0.99668
0.999830.99935
0.998440.99698
0.994900.992120.98859
0.99868
0.99988
0.999800.99968
0.99997
0.99999
0.99999
0.99999
0.99999
0.99998
0.99998
0.99998
0.99997
0.99997
0.999960.99995
0.99994
0.99992
0.999900.999880.99985

Performance Results for up to30 Retrieved Documents

Table 1II I-8

Suppose that in the first 10 documents Method I produces 4 relevant and Method
II 2 relevant.

Then evaluation starting with this Information on a feedbeickpass would evaluate the measure as

Method I Conditions

Method II Conditionsn = 190n = 190

number relevant = 8

number relevant = 10

Performance would thereafter reflect exactly the same measures as if conditionsfor Methods I and II were starting conditions.

5.

Tests
One method of comparing two or more methods over the same set of queries

in the same document collection would be to average the measure over the number of documents retrieved.

This procedure would give one number for each-method and the highest such number could be stated to represent the best rr.ethod.
The difficulty with this method is that there is no way to know thestatistical properties of this average and therefore slight differences in theaverage of method i vs. method j cannot be proven significant.

With a fixed

set of queries and a fixed collection there is no randomness involved anyway.
Randomness can be introduced into the problem by claiming that thequeries are a sample drawn from a set of queries and that the test results
show that at any pointna population of queries divides into a multinomial

distribution where method i has probabilityp.

of being the most successful.

This procedure is discussed in May T s thesis.

Table 2 shows the suggested

partition of queries and methods over n, the number of documents retrieved.
Table 2 also shows a fictitious set of results.

There is no hope ofbeing correct in a decision if in reality the methods are exactly alike, S DIII-9T h r e e Methods

Z_LAt pointnFive Queries

M M M

QQ 2 Q 3 Q^ Q 5

O= 1, 1 document retrieved

Value 1 given to method which has highest value.. In caseof a tie at some point, choose one of the tied methods by chance.
Example:
lM2

M

0

10

1

0000

100

1001

M

QlQ

2

Q

3%
Q5

For each n. = i,for each method

3ii documents retrieved, sum over queries

Example:\N2-N

3=T11352

1225302351

31

5212

51-M

M

20
*20 =N= 200 :
200

2

3

1

Again, sum, overn.

this time, for total for methods,

M
1M,"2M„

147

320

533

Total:"31000Estimate:
l

147
1000

.147

for M 2

320
"1000

.320

for M 3533
"1000.533

for Mpl

P

2

P

3

Sample Calculation
Table 2

111-10one can only state the "probability" of being correct in choosing method 3
in the example given if the ratio
0P /p 9 C=0). is actually greater than somespecified by the experimenter.
For the example given assuming there is a multinomial distribution

Cwhich is unlikely) and further that

P3/P0 = 1.5 , then the probability

that the choice of method 3 is best is over .98, using Bechhoferls procedures.
It should be stressed that this is not to claim a valid statistical test but
only to give some idea of the possible confidence one could have in choosing
the largestp.

as representing the best method.

III-ll

Bibliography

Bechhofer, R. E. , Elmaghraby, S., and Morse, N., M A Single-sample
multiple Decision Procedure for Selecting the Multinomial Event
which has the Highest Probability", Annals of Mathematical Statistics^, Vol. 30, No. 1, March 1959..
Cooper, W. S. , "Expected Search Length — A Single Measure of Retrieval
Effectiveness Based on the Weak Ordering Action of Retrieval Systems",
American Documentation, January 1968.
Goffman, W., and Newill, y. A., "A Methodology for Test and Evaluationof Information Retrieval Systems", Information Storage and Retrieval,Vol. 3, 1966.
Hodges, J. L., and Lehmann, E. L., Basic Concepts of Statistics, HoldenDay, San Francisco, 19-64.
Lesk, M. E. , "SIG — T h e Significance Programs for Testing the Evaluation Output", Report No. ISR-12 to the National Science Foundation,Section II, Cornell University, Department of Computer Science,
1967.
May,. C , "Evaluation of Search Methods in an Information Retrieval
System", an unpublished thesis for Masterls of Arts degree, June
1968.
Salton, G., and Lesk, M.E., "Computer Evaluation of Indexing and Text
Processing", Report No. ISR-12 to the National Science Foundation,
Section III, Cornell University, Department of Computer Science,
1967.
Williamson, R. E., "A Proposal to Ascertain the Relationship between
the Generality Ratio and Performance Measure", unpublished paper.