III-l

III.

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 and discussed. examined. Performance characteristics of a good evaluation measure are The suggested measure Pr„
N

(P<R/n)

, (the probability under

the hypergeometric distribution, that the precision could be strictly less than that precision attained, where drawn, R = number relevant in the sample n = size of sample drawn) is

N = total number in collection and

introduced and tested against the various criteria needed for a good evaluation measure. A statistical test of significance is explained.

1.

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 the averaging 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 not receive different amounts of credit, although just by random

III-2

chance it is easier to get a relevant document for a query with 30 relevant than for one with 4 relevant* 5) It has not been determined how to handle the evaluation of 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 effectiveness over many queries. On a recall-precision graph, the points of recall where However, the

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

only 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 coincide with 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 this

problem 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 must occur tends further to distort the measure of effectiveness. But even over

in-;

Ranks of Relevant Documents

o
CVJ

^ —
C J -

„m

o
CVJ

<fr

Q_

O

Total No. of Relevant Documents

CO

<fr

CVJ

c o

a)
3

>
Q>

(Z

a
o

Query Number

CX

O"

c o Ct

sz CL o *~ C D c o
if)

ILO

o

<D Q_ 1
w_

al
O C D

(T

C D

o o

o:

III-4

points that coincide with equal recall, different values can be obtained by different methods of averaging. Even at these common points, the values No correlations are made in the pre-

being averaged are somewhat in doubt.

cision values for the generality number ( G = number of Relevant/total numj ber 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 sense

is decreased in a way which preserves the

observed 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 not been 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 by comparing the number of relevant documents retrieved to to total number of relevant documents, while precision measures this performance by comparing the number of relevant retrieved documents to the total number of retrieved. These intuitively seem to be the best measures Their biggest drawback is A good measure

of performance available.

that they are two unique values not one. should reflect both. 2l

The generality number, as stated before, reflects the degree of effect that pure random chance selection will have on the method of retrieving relevant documents for a certain 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 and effectiveness. Any system which is effective at all should

have 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 query q there

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

If, at random, 20

documents are drawn from that urn without replacement, the probability that less than 3 relevant documents are chosen completely at random is

P

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

t P ^ 2 Q 0 CR =0>

=

C

+

l

t

r20s,18Ck K j

0

20

,2oo.
l
2

r

200

)
l

( )
20

200

0;

20^

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

CR<3) = P R

2QQ

CR/n<3/n) = P R

20Q

The higher this probability is, the less likely it would be that This measure could be evalu-

the precision achieved was obtained by chance. ated at any point

n (equals the number of documents retrieved) that might

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

m/n to (m + l)/n
+ 1

, this value goes
to P H 2 00

H 2QQ('P<^m

^/n)

which

is

e

lual

^<m^

9 0 n^ R m + !) where
P

H , 2 0 0 ( R < m ) = PH,200CR

= m

"1}

+ P

H,200CR

= m

"2) + • • •+

P

H,200CR =

0)

III-6

and ^ O O ^
1 1

^

= P

H,200 C R = m )

+

^^QO01

= m 1}

'

+

' ' •

+ P

H,200 ( R "

0)

"

When

P„ ^^^CR<m) is subtracted from

P^ 2pnCR<m+l)

the answer is always positive P CR<m+l) . PH CR/n<P<m/n = p )

since one more single hypergeometric probability is added to Since P P CR<m) < P tR<m+l)

is equivalent to stating that

(P<m+l/n = p 2 ) , and

p. <p 2 , then as precision increases the perform* -nance

measure increases. This same argument holds for recall because

P

H,200(r<m)

= P

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

As the recall increases from

m/r

to

m+l/r

more probability is added to the

measure and it therefore increases. The probability itself incorporates the generality number and it will be shown 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 Some measures for arbitrarily

to testing procedures and analyzing of results. 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 pass are 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.

Number Relevant

Number Drawn

Measure

1 2 3 3 3 3 3 3 3 4 5 5 5 6 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2Q 21 22 23 24 25 26 27 28 29 30

0.94000 0.99668 0.99983 0.99935 0.99844 0.99698 0.99490 0.99212 0.98859 0.99868 0.99988 0.99980 0.99968 0.99997 0.99999 0.99999 0.99999 0.99999 0.99998 0.99998 0.99998 0.99997 0.99997 0.99996 0.99995 0.99994 0.99992 0.99990 0.99988 0.99985

Performance Results for up to 30 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 feedbeick

pass would evaluate the measure as

Method I Conditions n = 190 number relevant = 8

Method II Conditions n = 190 number relevant = 10

Performance would thereafter reflect exactly the same measures as if conditions for 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 the statistical properties of this average and therefore slight differences in the average 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 the queries are a sample drawn from a set of queries and that the test results show that at any point n a population of queries divides into a multinomial p. of being the most successful.

distribution where method i has probability 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 of

being correct in a decision if in reality the methods are exactly alike, S D

III-9 T h r e e Methods M M M
_ L

Five Queries
O

Q

Q 2 Q 3 Q^ Q 5

Z

At point

n

= 1, 1 document retrieved

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

l

M2 1 0 0 0 0

M

3

i

Q

l

0 1 0 0 0

0 0 1 1 1

Q Q

2 3

% Q5

For each n. = i, for each method Example:

i documents retrieved, sum over queries

\
N N

2 3 =

1 2 3

T
1 1 0

M

2

M

3 5 5 5

1
2

3 2 3

2

20 *20 = N = 200 : 200

1 2

3 1

1 2

5 5

1
this time, for total for methods,
M„

Again, sum, over Total:

n.

M 1 147 Estimate:
p

M, "2 320

"3 533 1000

l

for

M

l

147 1000 320 "1000 533 "1000

.147 .320 .533

P

2 3

for M 2 for M 3

P

Sample Calculation Table 2

111-10

one can only state the "probability" of being correct in choosing method 3 in the example given if the ratio 0 specified 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 P /p 9 C=0). is actually greater than some

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 largest p. 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 Evaluation of 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.