- Apl -APPENDIX 1
1:

Miscellaneous Formulae

Recall/precision interpolation procedures(see A III.3.2.1)(a)linear interpolation
the given recall/precision points nearest the required recall level
are linked; the highest given recall may be linked to the point 100%R f
0%P, and the lowest given recall to the point 0%R, 100%P.
(For our ordinary
coordination level output the last two are not d o n e ) .
The formula for precision for a specified recall value V is.
, _„ , /f„n - , ,T7N + (no docs above V - no docs below V ) .
no docs below V +((V - recall below V) * ,—•—-— )(recall above V - recall below V)(b)pessimistic interpolation
precision at a required recall level is the maximum precisionachieved at any given higher recall point.
(This also assumes that if there
are several precision values for the same recall, the best of these precision
values is selected).
If precision above the highest given recall pointis required this is taken as the precision of the last given recall/precision
point. (This last is not needed for completely ranked output).
2

Salton's term discrimination function Q (see B II.1.4)

Let VJI be the set of terms (term vector) for document j , and VJ_A be theweight (e.g. within-document frequency) of term i in document j . The centroidof all the document points in the collection N is defined as the centre ofgravity or 'mean 1 document C, where1C=N—NvE
j=lij

If the similarity between pairs of documents k and j is measured by a vector
matching function r(V^fV-;) (say cosine correlation, see item 3 b e l o w ) , wherer ranges from 1 for complete similarity to 0 for complete dissimilarity,
the compactness Q of the document space isQ=£r ( C , V j ) , 0 <= Q <= N

j=li.e. as the sum of similarities between each document and the centroid.
The
contribution of term m to the document space is then represented by Q m - Q,
where Q is the compactness of the document space with m deleted. If m isa good discriminator Q m > Q, i.e. Q m - Q > 0; if bad Q m - Q <; 0.
3Similarity and dissimilarity functions for classification and matching(see B III.2 and B IV.1.1.1)(a)cosine correlation
let v. and Wj^ be two vectors; then the similarity r

ist
T,

rvw

i-i/ t ,ii=l(vT2i>

v. w .
x

x

t:

ii=l

(w )

i

between the vectors

- Ap2 -(b)Jaccard (Tanimoto)using the notation of (a)Ev.w.

i=ix xr
vwttt_„v£ v. +£ w. - £v.w.
1=1
1=1
1=1
more simply, for binary vectors X and Y, we define the similarity S ™ between
the vectors asSXY=X n Y

XUY(c) normalised symmetric difference
for binary vectors X and Y, given Dice's similarity coefficient
sxy=

2|XHYI|X| +|Y|D
we d e f i n e t h e d i s s i m i l a r i t y D
XY as

XYDX

XY

2 IXOYI|X A Y |~|X | + |Y||X| + |Y|

When used for retrieval matching (a) is referred to as cos, (c) as dis.
4Class definitions (see B III.2)(a) stringstarting from a given term we take the term most similar
to it, then that term most similar to the latter, terminating either
by looping or at a specified maximum length(b) starstarting from a given term we take that term (or terms) most similar
to it, in descending order of similarity, terminating at a specified
maximum size.
(c) clique
starting from a given term we take other terms with a similarity
greater than some threshold to all the current members.
(d) clumpfrom a given starting division of the set of terms into a putative
clump A and its complement B (e.g. between a single term and therest), we seek to minimise the 'cohesion function'SABSAA,

NA 2 - NASAA_100
P*SAA
NA Z - NA

where SAB and SAA are the totals of similarity connections between
the members of A and B, and between the members of A, respectively,
NA is the number of terms in A, and P is a constant.
Note that as used, classes were derived by the methods for each member of
the term vocabulary to be grouped. Note also that once classes are formedthe internal pattern of similarity connections is disregarded, and that
duplicate classes may be conflated.

- Ap3 -5

Weighting formulae (see B III.l and B III.2)

Given within-document frequency
f.. = the frequency of term i in document j
posting frequencyp.

= the total frequency of term i over the collection

collection frequencyn.

= the number of documents containing term idocument lengthd.

= the total of within-document frequencies of terms in document j

term lengtht.

= the number of terms in document jandP= the total postings in the collection
N= the total number of documents in the collection,
we define
the within-document frequency weight of a term asw= f. . ;ID
the description length weight of a term as
w = 10 - intpt (i^J) and w = f. . (10 - intpt (^3)
)
tot
ID
tot
(where tot = the next multiple of 10 above max f. and max d. respectively)
for term length and document length weights respectively;
the file length weight of a term asw=log (—i-)

and w = - log(—*-)

for collection frequency and posting frequency weights respectively.
Note that in the actual implementation the former is interpreted asw= - log 0 (J-—)
2 max n,^Further' the program uses the function F(n.) to determine the weight of aterm with collection frequency n. whereF(n.)=lm, where 2™"< n. <= 2 m .
l

Now given relevance frequencyr.

= the frequency of term i in a query over the set of relevant
documents for the queryand R = the total number of relevant documents for the query.
we definethe relevance weight of a query term asw= r.
lor asw=log •= logf(Fl)5±<£)n/__]

(F2)

- r-j
LA

- Ap4 -or as

w = log(F3)( -Bi—)

or as

(R^q)
w = log(F4)
ri|_ - r-jn.
N - T\AV(M_T3 J.
v- )
R+ rj

Note that these are the retrospective versions of the formulae; when theformulae are to be applied predictively we add 1 to Fh, and to the various
components of the other formulae as follows:
r. + h,n. - r. + h, R - r. + h, N - n. - R + r. + h,R + 1, N - R + 1, n. + 1, N - n. + 1 ,ll

N + 2,The treatment for special cases in the retrospective application of Fl - F4
is given in the following table:

CaseD

Definition

Documents
in whichterm occurs

Functionsto whichcase applies

Implicationsof case tor document
when term is:
PresentAbsentr = o

Non-relevant
only

F1,F2,F3,F4

Bad

Indifferentn-r » oRelevant
only

F2,F4

Good

Indifferent

R-r = 0

All relevant
and someothers

F3,F4

Indifferent

Bad

N-n-R+r = 0 Some relevant F4and allothersIndifferent

Goodn-r = 0
R-r = OAll relevant
and noothers

F4GoodBadr = O
No relevant
N-n-R+r = O and allothers

F4

Bad

Good

"Bad" means that the document should never be retrieved, i.e. should be atbottom rank;"Good" means that the document should always be retrieved, i.e. should beat top rank;"Indifferent" means that the document should be unaffected, i.e. should beat the rank determined by its other terms.
Case E combines B and C; case F, A and D.
Casesc through F apply to functions F3 and F4, in which term absence isexplicitly recognised.