CHAPTER 3

Probabilistic models of indexing and searching

1 Introduction
There has been a considerable amount of work in recent years on theprobabilistic theory of document retrieval. The main sources for thepresent paper are the work done in this country on the searching end of theinformation-storage-and-retrieval complex (e.g. Robertson and Sparck Jones,
1976; van Rijsbergen, 1977; Harper and van Rijsbergen, 1978), and the work
done in the United States on automatic indexing using within-document
frequencies of terms (notably by Bookstein and Swanson, 1974, 1975; Harter,
1975a, 1975b; Bookstein and Kraft, 1977). (There is a considerable body ofrelated work by Salton, Yu and associates (e.g. Salton, Wong and Yu, 1976),
but the starting-point for this is rather different, and it will therefore
not be considered further here.)
The present paper arises out of a project currently under way in Cambridge,
involving the three authors. One of the main objects of the project is tobring together these two strands of work on indexing and searching. In
particular, we hope to develop and test a model, within the framework of theprobabilistic theory of document retrieval, which makes optimum use ofwithin-document frequencies in searching. Progress towards this end, boththeoretical and experimental, is described in this paper.
As the work described here depends fairly heavily on previous work (byourselves and others), we propose to spend a little time summarising theearlier theoretical and experimental results.

2 Theoretical background

2.1 Basic concepts
A fundamental part of the probabilistic theory of retrieval, as it hasdeveloped over the last ten years or so, is the Probability Ranking
Principle (Robertson, 1977), which states that for optimum performance on agiven query, a document retrieval system should rank the documents in orderof their probability of relevance (to the query or underlying need),according to the information available to the system. This principle can beproved to hold provided that certain assumptions are made; it will beassumed here.

-36-

The core of the theory lies in the use of probability theory, together withassumptions about the statistical properties of the variables involved, toconstruct various retrieval functions which can be used to rank the
documents in the appropriate order. The first step in such a construction isusually to invert the conditional probabilities using Bayes' theorem, as
follows.
Assume that we have information about documents in the form of a variable X,
and assume that each document is assigned a value x of X. X may be regarded
as a random variable associated with the population of documents. (X may
take values in a multi-dimensional vector space, for example, each dimension
being associated with an index term, and x is then a single vector
describing the assignment of index terms to a particular document.) We haveanother variable of interest, namely the relevance of a document to thequery or underlying need. This variable is assumed in the present paper tobe dichotomous; it is denoted by A, with values 0 (for non-relevant) or 1
(for relevant).
We desire to rank the documents in order of their probabilities of relevance
given the information provided by X, i.e. in order of their values ofP(A=1 i X=x)
It can be shown by Bayesian (van Rijsbergen,1979) inversions that an
identical ranking of the documents is produced by using the function
fx(x i A=1)
V(X=x) = log
fx(x I A=0)
where fx(x i A=a) is the density function of X in the population of
relevant (or non-relevant) documents. If X is a discrete variable, thenfx(x I A=a) = P(X=x i A=a)i.e. the probability of a relevant (or non-relevant) document having thevalue x of X. Since all the variables considered in this paper are discrete,
the form
P(X=x I A=1)
V(X=x) = log
P(X=x i A=0)
will be used.
One extremely useful property of these functions is that the are additive
under independence. That is, if we have two variables X, Y, and wish tocombine the information provided by them, then under assumptions about their
independence in the relevance set and the non-relevance set respectively, we
have

-37-

V((X,Y) = (x,y)) = V(X=x and Y=y)
= V(X=x) + V(Y=y)
In other wordsf the function V forms a suitable basis for a sum-of-weights
matching procedure, whereby each variable has associated with it a weight,
and the total score of a document (by which it is ranked) is the sum of thecomponent weights.
One final transformation is useful. It is often convenient, if a variable
has a natural zero, to make sure that the weight associated with this value
is zero. This can be done by constructing a retrieval function
W(X=x) = V(X=x) - V(X=0)
This function ranks the documents in the same order as V, and is also
additive under independence.
To summarise: If the variable X is multi-dimensional with axes X^f having
vector values x with components x^, then optimum retrieval performance(under the assumptions of the probability ranking principle) is ensured byranking the documents in order of their associated values (scores) of
P(X=x I A=1) P(X=0 | A=0)
W(X=x) = log(1)
P(X=x I A=0) P(X=0 | A = 1)

Further, if independence between components of X is assumed, then\W(X=x) = /_where

W(Xi=Xi)

P(Xi=Xi

i A=1) P(X i = 0 i A=0)

P(Xi=Xi

i A=0) P(X i= 0 | A=1)

W(X.= Xi ) = log(2)

Formula (2) will form the basis for most of the retrieval functions
discussed in this paper.

2.2 Binary independence weights
We now concentrate on the case where each X^ corresponds to the assignment
if index term i to a particular document, and where terms are either
assigned or not, so that X^ has just two values. We define for a given
query:-38-

p = P(t assigned i A=1)
q = P(t assigned i A=0)
Then, from (2) and making the independence assumption, each term can begiven a weightp(1 - q)W(t assigned) = log(3)
q(1 - p)This is the relevance weight used by Robertson and Sparck Jones (1976) andit will be referred to as the binary independence, or BI, weight. The
question of how to obtain information about p and q, upon which any use of
the formula must depend, is discussed in 3.1 - 3.3 below.
2.3 Binary dependence weights
In 1977 van Rijsbergen proposed a weighting scheme which replaced theassumption of independence between index terms by one of partial dependence.
Instead of just considering the absence or presence of individual terms
independently one selects certain pairs of terms and calculates a weight forthem jointly. If one assumes that term i depends significantly on j then adocument will receive a weight proportional tolog

PCX. = x. | X 1 s x 1 f A = 1)iii
P(X i = x± i Xj = Xj , A = 0)

(4)

It is crucial to the calculation of such a weight that one establish
beforehand what are the significant dependencies between pairs of index
terms. The theoretical model described in van Rijsbergen (1977, 1979)
assumes that the important dependencies can be selected by constructing aspanning tree connecting the entire index term vocabulary. The spanning tree
is chosen from a class of possible spanning trees in such a way that it
optimises an objective function. Such a function can be a sum ofsimilarities, where each similarity measures the extent of the dependence ofa pair of terms connected by a link. The optimal spanning tree is thespanning tree for which the sum of similarities is maximised. Once thespanning tree has been established, only those pairs of terms directly
connected are assumed to be significantly connected.
2.4 Harter f s model
The discussion so far relates to recent work on probabilistic models withthe emphasis on the searching process. The work on indexing on which we
propose to draw was developed independently, by Bookstein and Swanson (1974,1975), Harter (1975a, 1975b), and Bookstein and Kraft (1977). There are,however, several points of contact. This discussion will be based chiefly on-39-

Harter f s two papers.
The simple version of Harterfs model states that any content bearing word
will have within-document frequencies which fit a 2-Poisson distribution.
That is, each word will have associated with it an "elite" set of documents(subset of the collection); the within-document frequencies will follow a
Poisson distribution within this elite set, and will follow a second Poisson
distribution in the non-elite set formed by the rest of the documents, so
the observed distribution on the entire collection is a mixture of the two.
The elite set is either identified with, or assumed to be correlated with,the set of documents which would be judged relevant by a requester whose
query was just this single word. (Single term requests only are consideredby Harter.)Harter then develops a method for estimating, for any given word, theparameters of the two Poisson distributions. (The method is discussed
further in 5.4 below.) He then uses a decision theoretic argument to suggest
criteria for deciding whether or not to assign any particular word as index
term to any particular document. These criteria are based on a version of
the probability ranking principle; this fact provides a point of departure
for an attempt to unify the two lines of work.
Following is a condensed mathematical description of those features ofHarterfs model to which we will be referring:
The variable K (with values k) is the number of occurrences of a given word
in a document d. E represents the property of eliteness: E=1 means that the
document belongs to the elite set, E=0 means it does not. The 2-Poissonmodel requires three parameters for each word: the means of the two Poisson
distributions, 1 (elite set) and m (non-elite set), and a mixing parameter hdefined by
h = P(E=1)
It is assumed that1 > m(in effect, this is the definition of the elite set).
The 2-Poisson model says that-40-

exp(-l)lk
P(K=k) = h

exp(-m)mk+ (1-h)k!

k!

The indexing criteria depend on the parameterh exp(-l)lk(5)

P(E=1 i K=k) =h exp(-l) l k + (1-h) exp(-m)mkThere are various versions of the indexing criteria, but the final one
suggested by Harter uses the following definitions:
1 - m

(6)
</(l + m)
is a measure of the separation of the two distributions;(7)

P(E=1 I K=k) + z

is a measure of the "indexability"f or the relative significance of the word
in a document in which it occurs k times. The indexing criterion is thenIndex if and only if b > 0.
The measure of indexability b (Harter1s beta) is arrived at by a somewhat ad
hoc process, and in fact there is clearly a fault in the argument, since b
is alway^ greater than zero (unless h=0, which is a pathological case).
However, Harter also suggests that b might be used as a weight; as we shallsee below, this is one of the experiments we have tried.

3 Previous experimental results

3.1

Upper bounds

One use for a retrieval function such as the binary independence weight (3)which demands relevance information is to indicate an effective upper boundor optimum retrieval performance (Sparck Jones, 1975). This idea requiresthat we know in advance the relevant documents for each query (as isnormally the case with test collections).
Suppose then that for a given query, the entire collection of N documents
contains R that are relevant; a particular term t is assigned to n
documents, of which r are relevant. Then the obvious estimates for p and q

are

-41-

r

n - r

R

N - R

From these and formula (3), we deduce that the binary independence weightassociated with the term should ber (N - R - n + r)
W(t assigned) = log(R - r) (n - r)
For reasons associated with estimation (Robertson and Sparck Jones, 1976) wemore usually use a modified version:(r + 0.5) ( N - R - n+ r + 0.5)W(t assigned) = log(8)(R - r + 0.5) (n - r + 0.5)

This solution to the estimation problem is not ideal (van Rijsbergen, Harperand Porter, in press) but will be used in this paper.
Experiments with (8) applied to the query terms only have consistently givenhigh optimum performance (Robertson and Sparck Jones, 1976; Sparck Jones
1979a, 1979b, 1980). Higher performance still has been achieved with (4)applied to expanded queries (Harper and van Rijsbergen,1978).

3.2 Relevance feedback
Realistically, it may be possible to exploit partial relevance information,in the form of relevance feedback, to improve a search statement for asubsequent search. Considering again the binary independence weights as an
example, suppose that R now represents the known relevant documents (at aparticular stage of the search), of which r are assigned term t. Then again
we may estimate p byr
P = R
The appropriate estimate of q is not so obvious - we may take just those
known to be non-relevant, or all those not known to be relevant. There issome evidence to suggest that the latter is preferable in terms of retrieval
performance (Harper and van Rijsbergen, 1978), so the estimate of q takes
the same form as before:
n - r
q =
N - R

-42-

and the binary independence weight is exactly as before (8).
Two kinds of experiment are possible to evaluate relevance feedback
strategies. The first is to perform an initial search on the document
collection, select the top ranking 10 or 20 documents to provide thefeedback information, and then remove them from the collection for thesubsequent search. This procedure is known as residual ranking (Ide, 1969;
Harper and van Rijsbergen, 1978). The second is to divide the collection
into two parts, obtain feedback information from one half, and do thesubsequent search on the other. This is known as the half-collection method(Robertson and Sparck Jones, 1976).
Experiments of both kinds with formula (8), again using query terms only,
have once more consistently given good results. That is, it is possible toget substantial improvements in performance over non-feedback methods suchas unweighted terms and collection frequency weighting, even given very
little feedback information (Sparck Jones, 1979a, 1979b).

3.3 No relevance information
Croft and Harper (1979) have suggested using the binary independence weight
without gny relevance information. One might, in the absence of suchinformation, give p a constant value (say 0.5), and estimate q by theoverall frequency of the term, i.e.

These estimates, crude (and inconsistent) as they are, nevertheless do havesome val^je. It turns out that when they are incorporated into formula (3),the resulting formula is closely related to the traditional collection
frequency weighting method, which has long been known to give performance
improvements over unweighted terms (Sparck Jones, 1972).
In this paper, we shall regard collection frequency weighting by the formulaW(t assigned) = log (N/n)
as an approximation to the special case of (3) where no relevance
information is available.

-43-3.4 Query expansion
The estimation problems encountered in implementing the independence weights
become more severe for the dependence weights. If only 10 or 20 documents
are used to provide the relevance feedback information it is difficult toobtain reliable estimates for the dependence weights (4). To overcome thisdifficulty a hybrid model was proposed by Harper and van Rijsbergen (1978)
in which dependence information was used to expand the query by selecting
additional search terms from the spanning tree on the index term vocabulary.
Once a query has been expanded the weighting scheme can be that for the BImodel (3).
The feedback strategy for using dependence information between index terms
is therefore now as follows. Construct a spanning tree on the term
vocabulary using the distribution of co-occurrences throughout the entire
document collection. For any given query, certain additional search terms
are selected from the spanning tree by using the query terms as starting
points. For example one could include in the query the nearest neighbour
connected in the tree to each query term. After the query has been expandedin this way relevance weights can be calculated for each query term in theusual way.
Experimental results reported with this strategy have been conflicting. For
some test collections, notably Cranfield 1400, query expansion has worked
reasonably well leading to significant improvements over non-expansion when
performance is measured by residual ranking (Harper and van Rijsbergen, 1978). However, on the UKCIS data no significant improvement wasobserved (Harper, in preparation). This leaves the whole question of theeffectiveness of query expansion unresolved. It was always clear that any
additional terms obtained by expansion would only be as good as the initialquery terms. As yet no good heuristics for selecting query terms ascandidates for expansion have been designed. Nor has the problem of which
additional search terms to include in the expanded query been investigatedsufficiently. It would appear that a thorough investigation of both theselection of 'good1 query terms and further 'good1 search terms is needed.

3.5 Harter's experiments
No test of retrieval performance (like the experiments discussed above) has
been done on the Harter indexing criteria. Instead, Harter compared theindexing generated by his criterion with indexing by a human indexer. Also,rather than use his criterionb > 0

to d e f i n e an index s e t for each document, he simply ranked t h e words foreach document in order of t h e i r b v a l u e s , and observed t h e p o s i t i o n of thehuman-assigned index terms in the ranked l i s t . Thus he used b as a weight-44-

(or something of that nature).
In the experiment, ranking by b value proved to be a reasonable predictionof whether the word had been assigned by the human indexer; in particular,
it was a considerably better prediction than ranking words by k value, thatis simply by number of occurrences.
We do not propose to give a full account of Harter's experiment here, butsome specific aspects should be mentioned. Although the theory deals withany kind 6f textual material, and therefore would have obvious application
to collections of full texts of documents, Harter used a collection of
abstracts only; we have done the same. Harter devised a method for
estimating the parameters 1, m, h of his model, involving the moments of theobserved distribution, and including rules for dealing with exceptional
cases; we have used a similar method.
Finally, Harter chose to do his analysis on words as they occur in texts,
without any stemming or suffix stripping operation. At this point we havedeparted from Harter!s methods. The argument he gives is that different
words fropi the same stem have different distributions. We dispute theargument on two grounds: first, whatever the distributions of the individual
words, the stem itself might be supposed to have a 2-Poisson distribution
and coulc^ therefore reasonably form the basis for a Harter-type analysis;
second, the only final argument would be in terms of retrieval
effectiveness. Given the evidence (in a somewhat different context) that
stemming improves performance, we have decided to perform a stemming
operation before applying the Harter model; but we suggest that some directcomparison would be desirable.

4 Main theoretical results

4.1 Relevance and elitenessIn tackling the problem of developing a Harter-type model for multi-term
queries, we have to consider in some depth the status in the model of theproperty of relevance, and also of the Harter idea of eliteness.
One possible approach would be to assume that there is some property
equivalent to eliteness, but relating to the complete set of terms used in aquery. One would then need to postulate distributions for the various terms
within the elite set and outside it, and perform a complete analysis of theraw occurrence and co-occurrence data for any combination of terms that
occurreq in a request. In general, this analysis would have to be performedat the time of the request, and would have to be repeated if the system or
the userf were to expand the query. It seems, at least superficially, that
this kirfd of process is unlikely to be a practical proposition. Nonetheless,an approach similar to this is taken by Bookstein and Kraft (1977): theysuggest ways of selecting likely combinations of terms beforehand.

-45-

An alternative approach is to associate elite sets with the individual
terms, and assume a more complex model relating the various elite sets tothe one relevance set for the query. This enables the analysis to be
performed as an indexing operation, prior to the processing of requests.
This is the approach adopted here.

4.2 Relations assumed in the model
We assume, then, that each term has associated with it an elite set, andthat the distributions of numbers of occurrences of the term in the two sets
(elite and non-elite) are different (in particular, we assume that both are
Poisson). We assume further that the elite sets for the query terms (andperhaps others) are correlated with relevance to the query, in a manner tobe specified below.
We wish to assume that some of the possible relationships between thevariables of concern to us do not exist; that is, we wish to assume
statistical independence in some cases. There are several different (butequivalent) ways of formulating an assumption of statistical independence,and it is worth indicating the differences and equivalences. Suppose a, b, c
are three events; then the following statements are equivalent:P(a,b i c) = P(a I c) P(b i c)
P(a ! b,c) = P(a I c)
P(b ! a,c) = P(b ! c)
All the statements say (in words) that a and b are independent, given c; or
equivalently, that the only relation between a and b is that implied by c.
Diagrammatically, one might represent the situation under such an assumption
thus:

a

b
/

\
\ /
c

That is, there is assumed to be no direct relation between a and b.
Returning to the 2-Poisson model, we can represent our independence
assumptions thus: Suppose there is a query with relevance property A, withterms t-j, t2» t^ ... each with eliteness E^ and number ofoccurrences K-, then we assume:

-46-

i ^
i

i

E2
'*

i

E3
/

i

A
The various assumptions embedded in this model are:I
The number of occurrences of a term depends only on the property ofeliteness for that termf not on eliteness for any other term or on
relevance.
lis is pr*Thisprecisely equivalent to assumptions made by previous authors withthis model].

II
Eliteness for a given term depends only on relevance, not on elitenessfor any other term.
This is equivalent to the independence assumptions that were used in thederivation of equation (2).
Like ^all independence assumptions, these must be regarded as simplifications
which we make in order to render the mathematical model tractable, and towhich it may be profitable to return with a view to reducing or eliminating
the implied constraints. In fact, Bookstein and Kraft (1977) consider arather more general model which (in the absence of variable A) assumes thatE^ and Ej may be related.
As mentioned above, these assumptions enable us to estimate the 2-Poissonparameters separately for each term, as an indexing operation, and then to
use the results of this analysis in searching.

^•3 2-Poisson independence weights
As with the binary independence model, we need two parameters to describe
the relation between eliteness for a term and relevance. These are as
follows (for a given term)
pf = P(E=1
qf = P(E=1

= 1)
=0)

Now we are in a position to calculate the components of a weight to be
assigned to any specific number of occurrences (value of K) for this term,
according to formula (2). We have:-47-

P(K=k i A=1) = P(K=k I E=1) P(E = 1 I A=1)
+ P(K=k ! E=0) P(E=0 ! A=1)
1
= - (pf exp(-l)lk + (1-p») exp(-m)mk)k!
and similarly for A=0 and q' (the first step in this derivation makes use of
independence assumption I ) . Hence the full expression for W(K=k), according
to formula (2), becomes:
p

kQo

p

oQk

W(K=k) = log(9)where P k = p f exp(-l)l k + (1-pf )exp(-m)mk
Q k = q f exp(-l)l k + (1-qf)exp(-m)mk?Q = pfexp(-l) + d-p')exp(-m)
Q 0 = qfexp(-l) + (1-qf)exp(-m)
If we make independence assumption IIf then this weight (the 2-Poisson
independence or TPI weight) gives optimal retrieval performance according toprobabilistic retrieval theory.
Expression (9) is a pretty alarming one, not so much because of its size andinherent complexity (which is no problem to a computer), as because of thenumber of different bits of information it requires. In particular, it needs
the estimates of 1, m from the Harter-type analysis, query specificestimates of pf and qf (which, like p and q, might be taken from relevance
feedback data), and values of K for each document-term pair. However, there
is a sufficient theoretical justification to attempt some experiments (atleast) on the formula, even if we may subsequently look for some
simplification of it for practical purposes.

4.4 Estimation of TPI
As with BI, we suppose first of all that we have complete relevance
information: that is, we know the set of relevant documents (which have
A=1). Unfortunately, we do not know the elite set for a term exactly: ourknowledge of it is probabilistic, based on term occurrence data. So theestimation of pf and qf is not quite as obvious as that of p and q. The
following argument, however, provides us with plausible estimates.
For a given term, we can calculate the probability that any specificdocument belongs to the elite set, based on the number of occurrences of theterm in the document:-48-

u k = P(E=1 i K=k)
for which an expression has already been given (5).
Given the relevant documents, we wish to estimate
pf = P(E=1 i A=1)
and an appropriate estimate would be
Number of relevant documents in the elite setp.

=
Total number of relevant documents

We do not know the numerator, but we can obtain an expected value for it:
the sum, over the relevant documents, of the probability of each document
belonging to the elite set. Using this value, we can write/_ ^AukV/

A

where in each case the sum is over all documents. Since u^ is the same forall documents with the same K value, we can cumulate by K value:\
Pf = /_ f k u kk(10)

where f^ is the proportion of relevant documents having k occurrences of
the term. Similarly,

\
l = /
!

f

(11)

kuk

where f^ is now the proportion of non-relevant documents having K=k.
Again following the BI example, we may reasonably use estimates of the same
form if we have only partial relevance information. Then f^ in (10) would
be the proportion of known relevant documents having K=k, and in (11) itwould refer to the remaining documents (the complement set).
It is also possible, in the absence of any relevance information, to make-49-

plausible guesses for p' and q f f following the example of Croft and Harper's(1979) guesses for p and q. Some such guesses are discussed below (in 5 , 9 ) .

4.5 Mixability of independence weights
One further comment should be made here about the general weighting scheme
discussed above. The breaking down of formula (1) into its components (2)under independence assumptions does not depend on the various components
being similar in nature. One might, for example, have some components (saywords in text) which have 2-Poisson characteristics, and thus should beweighted according to (9), and others (say assigned index terms or authorsor citations) which are essentially binary, and thus should be weighted
according to (3). The two sets of weights would then (according to thetheory) be strictly compatible, and could therefore be used in combination
in weighted retrieval.
No experiments with such mixings are reported here, but the theoreticalresult is a powerful and potentially important one.

5 Experiments

5.1 Overview of the experiments
In this section, we present the results of a series of experiments on one
test collection. The purpose of these experiments was to test some of thetheoretical ideas discussed above. In particular, we have(a) repeated some earlier experiments using binary independence weights on
unexpanded and expanded queries;(b) performed a Harter-type analysis of distributional characteristics ofterms;(c) tested some simple weighting schemes based on the Harter model (query
terms only);(d) tested the full 2-Poisson independence weights in various ways (query
terms only); and(e) tested the use of some Harter-type indexing criteria.
Descriptions of the test collection used and the experimental method follow.

-50-

5.2 The NPL data
The NPL test collection consists of the titles and abstracts of about 11000
documents, together with a set of queries and corresponding relevanceassessments. The material was originally prepared by Vaswani and Cameron at
the National Physical Laboratory, and this is described on pp. 9-13 of theirreport (1970). For the purpose of experimentation, we have represented eachdocument by a vector of the terms which index it, and the terms are derived
from the title and abstract for the document by discarding the common words(AND, ARE, BY etc.) and applying a stemming algorithm (see Porter, in press)
to the remainder. A document d is therefore indexed by a list of terms t<|,where each t- corresponds to a word stem derived from the^2»original text representative for the document, t^ will have a document
frequency k^, the number of times the stem of tj_ occurs in the document
representative, n^ will denote the number of documents in which t^
occurs, and we will usually drop the suffixes, so that k and n are frequency
parameters of term t.
The queries are set up as vectors of terms in an analogous way, and therelevance assessments consist of vectors of document numbers. The following
table provides a brief summary of the NPL data:

inv
number11429
max length105
min length1
total length
228087average length 19.96

relevance
assessments

queriesdocuments

inv

7491
2511

1
228087
30.45

93
13
2
664
7.14

inv

I

337 I
19 !
1 !
664 i
1.97 !

93
84
1

1735

2083
22.40

2083
1.20

6
1

Thus the third column shows that there are 93 queries, with an average
length of 7.14 terms (total length = 664) ranging from 2 to 13 terms. The
columns headed inv show the statistics for the inverted structures. Thus
the inverse of the term vectors of documents is a set of vectors containing
document numbers, which give the documents in which the various terms occur,and the second column shows that there are 7491 terms in the collection, andeach term occurs in an average of 30.45 documents, the most frequent term(highest n value) occurring in 2511 documents.
A number of changes were made to the original text of the collection in theform in which we received it. About 1900 edits were applied to the text toremove some of the gross typing errors. This task had been beyond theresources of the original investigators. 142 documents were removed which
had been inexplicably duplicated in the collection, and the document numbers
were reduced accordingly. Finally, the queries with empty relevanceassessments were discarded.

5.3 Appropriateness of the NPL test collection
The NPL test collection is an unusually large one. This was important intesting the Harter model, since a substantial amount of term frequency
information was required in order to be able to get good estimates of theparameters 1, m and h for each term. Three points, however, must be made:1) The term frequency information is derived from document abstracts, notfrom the entire document text. Following Harter, we felt that this was
acceptable since, like the document text, the abstract is a piece ofcontinuous prose containing words which will fall into two classes, those
appropriate and those not appropriate for indexing the document. Furthermore
we were naturally interested in the applicability of the model to thetypical IR environment where the document representative will contain little
more than the document abstract.
2) The removal of the common words (AND, ARE, BY etc.) could be left to theHarter model. The list of common words is however short (just 251), and thewords in it are very neutral in meaning, and it was felt to be
unexceptionable to remove them at an earlier stage.
3) The Harter model is being applied here to word stems rather than words.
Harterfs argument for using words is discussed above.

5.4 Estimating the Harter parameters
In deriving 1, m and h for each term, Harterfs estimation method was used,
whereby 1 and m are the roots ofal 2 + bl + c = 0
where

and

a = M 2 - L, b = K - LM, c = L 2 - MK,
M = R 1 , L = R 2 - R-| f K = R 3 + 2R-| - 3R2,

R
1» R2» R 3 b e i n 8 the first three sample moments of the distribution.
And h is given by

M - m
h =
1 - m

-52-

Various degenerate cases can arise, which are dealt with as follows:
if b 2 - 4ac <= 0 set 1=M and m=0,
if m < 0 set 1=L/M and m=0,
and then, unless 0 < h <= 1f set 1=M and m=0, and recompute h.
In fact, for the majority of these terms, one or other of these degeneratecases will apply. This is because, for the low frequency terms, there isinsufficient data to separate out the two Poisson distributions, and theZipfian distribution of the terms guarantees that the majority will be of
low frequency. But this does not necessarily matter, since the 'important1
terms in a collection (those that get used in queries) are usually of highto middle frequency.
As an illustration of the use of Harter's model with the NPL data, thefollowing table gives a list of 40 nearly equifrequent terms taken as acontinuous batch from the term frequency ranking, and arranged by decreasingz, Harter's measure of term effectiveness, equation (6). Each term is given
by a representative word corresponding to the stemterm

z value

1 RESPONSE
2 MAXIMUM

1.41
1.20
1.18
1.09
1.07
1.07
1.03
0.99
0.99
0.94
0.90
0.89
0.84
0.81
0.78
0.78
0.75
0.74
0.73
0.72

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

CHARGEELEMENTCOUPLE
IMPEDANCERECORD
SOURCE
PLASMAAMPLITUDE
VALVECONSTANTCOMPONENTDIRECT
NUMBERAPPROXIMATEFORMULACHANGETERMPERIODterm

21 INCREASE
22 PROBLEM
23 MICROWAVE
24 LINEAR
25 PROPAGATE
26 NEW
27 SIMPLE
28 TECHNIQUE
29 VARIOUS
30 DEPEND
31 PRODUCE
32 EXPRESS
33 DUE
34 INCLUDE
35 POSSIBLE
36 ELECTROMAGNET
37 GIVE
38 ACCOUNT
39 REPORT
40 SEE-53-z value
0.72
0.70
0.69
0.64
0.57
0.57
0.55
0.52
0.46
0.45
0.42
0.40
0.40
0.37
0.35
0.34
0.28
0.26
0.23
0.18

5.5 Presenting the experiments
In each of the experiments in which the queries are matched against the
documents, recall and precision values are obtained using the standard
recall cutoff method (van Rijsbergen, 1979). A result can be presented in
the form of a simple table as follows:
Coordination level match
recallprecision

0
10
20
30

59.91
49.07
37.62
30.59
24.94
20.36
13.22
10.61
7.23
4.72
2.23

no

50
60
70
80
90
100

This shows the percentage precision at the percentage recall values 0t 10... 100 using a coordination level match on the NPL collection. The label(1) will identify the experiment. To abbreviate this table, the recall
column will be omitted, the precision will be given to the nearest percent,the recall 0 value, which is untrustworthy, and the recall 100 value, whichis relatively uninformative, will be omitted, and the whole written on one
line as:
49

38

31

25

20

13

11

7

5

[1] C

where C indicates 'Coordination level match1, and the experiments are
identified by a number in square brackets possibly followed by a letter e.g.
[5x]. When an experiment is being presented merely for comparison, it isprefixed with 'cf.f, thus54
cf. 49

45
38

37
31

31
25

24
20

18
13

15
11

10
7

6
5

[2] log(N/n)[1] C

In [2] each term is given a simple form of collection frequency weight,
namely log(N/n) where N is the collection size.

-54-

5.6 Collection frequency experiments
A number of experiments were performed using the term weight log(N/n)f so as
to provide a basis for compar ison with other retrieval methods. The document
collection was split into two halves, the even numbered documents
constituting one half (the E half), and the odd numbered documents
constituting the other half ( the 0 half). In experiments [2a] and [2p] the 0
half only was used, and in ex periments [2b] and [2q] the E half only. But inexperiments [2p] and [2q] the values of N and n for each term weight were
derived from the whole collec tion, while in experiments [2a] and [2b] they
were derived from the 0 and E halves respectively. The results were as
follows:
57
57
cf. 54

48
49
45

39
39
37

33
33
31

28
28
24

21
21
18

17
17
15

12
12
10

8
8
6

[2p] logCN/n) to 0[2a] log(N/n) 0 to 0
[2] log(N/n)

5657
cf. 54

48
48
45

38
39
37

31
30
31

26
26
24

23
22
18

17
17
15

14
14
10

10
10
6

[2q] log(N/n) to E
[2b] log(N/n) E to E
[2] log(N/n)

f

E to E ! means that the the parameter estimates were derived from the E half
and that the retrieval run was done on the E half, !to E 1 means that they
were derived from the whole collection and applied to the E half, and so on.
Although performance on the 0 and E halves differ from each other and also
from performance on the whole collection, it will be seen that [2a] nearly
equals [2p] and [2b] nearly equals [2q]. This type of equality will beassumed in the sequel, where, in experiments on the half collections
involving the Harter model, the Harter parameters are in fact estimated fromthe whole collection.

5.7 Binary independence weighting experiments
Seven experiments were performed on the BI weight using formula (8). In [3]the BI weights were derived using the entire relevance set. In [3a] the BI
weights were derived from the relevance set in the 0 half and then the
retrieval run was performed on the 0 half. In [3d] the BI weights were again
derived from the relevance set in the 0 half, but then the retrieval run was
performed on the E half. [3b] and [3c] correspond to [3a] and [3d] with 0
and E interchanged. In [3e], the BI weights were derived from the relevant
docs occurring in the top 20 rank positions in a coordination level match on
the E half. The retrieval run was then performed on the 0 half. [3f] is [3e]with 0 and E interchanged.
Experiments [3], [3a] and [3b] can be thought of as providing upper bounds
for retrieval performance using BI weighting. [3e] and [3f] simulate aretrieval situation in which the user discovers relevant documents among theD highest ranking documents by coordination level match (here D=20) f and-55-this relevance information is used by the system in a further retrieval run[3c] and [3d] provide upper bounds on the performance of [3e] and [3f] as D
is allowed to increase to infinity. The results are as follows:
69

59

51

44

37

28

22

16

10

[3]

BI

70
65
59

63
56
50

55
46
40

47
38
33

42
34
29

34
26
22

27
21
18

18
15
12

12
9
8

[3a] BI 0 to 0[3c] BI E to 0[3e] BI E/20 to 0

73
62
60

66
56
52

57
49
43

49
39
35

42
34
30

35
29
25

26
21
17

23
17
14

16
12
10

[3b] BI E to E
[3d] BI 0 to E
[3f] BI 0/20 to E

5.8 Simple weighting from the Harter model
Several simple weighting formulae are suggested (in a somewhat ad hoc
fashion) by the Harter model (simple in the sense that they use the
distributional characteristics of terms, but no individual within-document
frequencies).
The parameter h in the Harter model plays a similar role to collection
frequency (n/N) in ordinary binary indexing. Since collection frequency
weighting is known to be of value, this suggests trying -log h as a weight:
55
cf. 54

45
45

37
37

30
31

25
24

19
18

14
15

10
10

6
6

[4]
[2]

-log hlog(N/n)As predicted, -log h provides a weight comparable in performance tocollection frequency.
Now Harterfs z measure:cf. 5454
cf. 49

45
43
38

37
35
31

31
29
25

24
23
20

18
16
13

15
12
11

10
9
7

6
6
5

[2] log(N/n)
[5] z
[1] C

There are good theoretical reasons (Croft and Harper, 1979) to suggest thata successful term weight will have a collection-frequency type of
distribution. Harterfs z weight does not have this, and the placing of [5]between [1] and [2] indicates that z gives a useful discrimination toequifrequent terms, but does not scale correctly over the entire range ofterms with different frequencies. An attempt can be made to force acollection-frequency type of distribution by multiplying the z weight bylog(N/n). The result is:-56-

cf. 6960
cf. 54

59
50
45

51
41
37

44
33
31

37
26
24

28
20
18

22
15
15

16
11
10

10
7
6

[3]
[6]
[2]

BI
z log(N/n)
log(N/n)This is an attractive result, giving, at the high recall end, a performance
mid-way between the collection frequency weight and the BI upper bound. In
fact, the weight z log(N/n) operating on the half collections will
outperform the relevance feedback experiments E3e] and C3f3:
61
cf. 59

52
50

39
40

34
33

29
29

22
22

18
18

13
12

8
8

[6a]
C3e]

z log(N/n) to 0
BI E/20 to 0

63
cf. 60

54
52

44
43

37
35

32
30

27
25

20
17

15
14

11
10

[6b]
[3f]

z log(N/n) to E
BI 0/20 to E

But it is unfortunate that we have not been able to derive a weight of thiskind directly from the Harter theory.
A more complex (but still ad hoc) weight is the b weight (Harter1s beta)
defined above (7K This does use the individual within-document frequencies,
K, and performs as follows:52
cf. 54

44
43

35
35

30
29

23
23

16
16

12
12

9
9

6
6

[7]
[5]

b
z

60
cf. 60

51
50

41
41

34
33

28
26

20
20

15
15

11
11

7
7

[8]
[6]

b log(N/n)
z log(N/n)

It can be seen that b and z perform in about the same way. This means that
we are not making any effective use here of the within-document information
about each term.

5.9 2-Poisson independence weights
In the formulae of (10) and (11) p ! and qf are derived from a certain set of
relevant documents, and the complement of that set. Calling either set S, p1
and q' are estimated by

\
/

f

kuk

where f k is the proportion of documents in S having k occurrences of termt, and #£ is P(doc inl^ik). The summation here does not involve many
terms, since f^ quickly becomes 0 as k increases.
The experiments conducted with the TPI weighting scheme, equation (9), are-57-

entirely analogous to experiments^] to [3f], and are as follows:

71

60

49

42

35

27

20

15

10

[9] TPI

74
61
57

67
53
48

56
42
38

48
36
32

43
32
28

36
25
21

28
19
16

20
13
10

15
8
6

[9a] TPI 0 to 0[9c] TPI E to 0[9e] TPI E/20 to

74
61
61

64
51
53

55
44
43

49
37
35

42
32
29

35
27
24

26
21
18

22
17
14

17
12
10

[9b] TPI E to E
[9d] TPI 0 to E
[9f] TPI 0/20 to

A comparison with [3] to [3f] shows that usually the TPI in its present form
performs about the same as (perhaps slightly worse than) the BI model.
A simpler approach to the TPI weight is to make plausible guesses for thevalues of p1 and q f . The guesses p!=1 and qf=0 have the merit of simplifying
the formula to k log(l/m) t although as guesses they are not too plausible
since they involve the assumption that for each query term the elite set isthe relevant set. Despite this, k log(l/m) does even worse than we expected.
On the other hand, it was found empirically that log(l/m) as a weight(another simple weighting scheme) does quite well:
32
56

25
46

19
37

16
28

13
23

10
18

9
14

7
10

5
6

[10]
[11]

k log(l/m)
log(l/m)

The natural guess for q? is h. With pf then ranging from 0 to 1, various
performance figures were obtained, which outperformed collection frequency
weighting for pf >= 0.3, and which reached a peak at about p f =0.5. The
pf=0.5 estimate performed as follows:57
cf. 54

48
45

40
37

32
31

26
24

21
18

16
15

11
10

8
6

[12] TPI pf=0.5 q f =h[2] log(N/n)

Comparing experiment [12] with the best simple weight z log(N/n) (neither
using relevance information), we find similar overall levels of performancebut differently shaped curves:
cf. 60cf. 57

50
48

41
40

33
32

26
26

20
21

15
16

11
11

7
8

[6] z log(N/n)[12] TPI pf=0.5 q f =h

5.10 Harter indexing experiments
In the main document collection, and in particular for all the experiments
involving binary indexing, each document is indexed by every term within it.
Instead of using Harter-model ideas to weight the terms, we might follow
Harterfs original suggestion of applying indexing criteria to decide whether
or not to apply a term under given conditions. This could have the effect of
reducing the collection, i.e. of discarding some term assignments previously-58-made.
As has been noted above, Harter's final indexing criterion contains an
obvious mistake, and so cannot be used directly. His other criteria involveassessments of cost to the user, and so again are not accessible to us inthis case. Instead, we tried two very simple criteria:a)Index if and only if P(E=1 i K=k) > P(E=0 | K=k)or equivalently P(E=1 ! K=k) > 0.5b)Index if and only if P(E=1 I K=k) > P(E=1)
r equivalently P(E=1 i K=k) > h!

inor variants on these criteria.
The indexing strategy could then be evaluated by comparing the performancesof the same retrieval method used with the main and the reduced document
collections. With these experiments the results have been entirely negative:
removal of terms from the main file degraded performance, and the more terms
removed, the greater the degradation became.

5.11 Query expansion experiments
Our results on query expansion using the NPL data are disappointing We havenot been able to achieve any significant improvements over non-expansion. We
have repeated experiments done previously in which the query was expanded
and the resulting set of search terms then weighted by BI. Once again the
results have been conflicting. On the one hand when the feedback experimentis evaluated by residual ranking the performance of the expansion does notdiffer significantly from that for non-expansion. On the other hand using
the half-collection technique we found that query expansion degraded
performance. The reason for this remains unclear and needs further
investigation.

6 Discussion
The theory of probabilistic retrieval can be applied to various bits of
information about The documents, the simplest idea is to apply it to query
terms only, and binary indexing (terms present or absent). Beyond this, one
might consider various additional bits of information, in particular, index
terms other than query terms, or within-document frequencies of terms. For
the latter, we can imagine three different ways of using within document
frequency information:(a) locally only, that is, to use the occurrences of terms in a particular
document to aid in the decision whether to retrieve that document or
notj

-59-

(b) globally, that is, to use the statistical properties of occurrence
distribution of terms as a guide to the use'of those terms in retrieval;(c) globally and locally, that is, to combine general statisticalcharacteristics of terms with document-specific information.
The 2-Poisson model on which much of the work in this paper is based does
not have anything to say about possibility (a). It does suggest (in a rather
ad-hoc manner) some possibilites for (b), but principally it leads to (c).
Again, there are two possibilities for (c), namely that we use theinformation for selective term assignment (as suggested by Harter) or forindex term weighting. The major theoretical contribution of this paper isthe development of an appropriate weighting scheme. Experimentally, we havetested some of the ideas on one test collection. All conclusions must be
tentative at best until other collections have been tried. However, theprincipal conclusions to be drawn from this series of experiments are as
follows:
I
There is benefit to be gained from using within-document frequency on a
global basis.
II
The local-and-global use of within-document frequencies appears to havepotential, but does not (in the form proposed here) match simpler
methods.
Ill
Our experiments confirm earlier ones on the difficulty of gaining
substantial improvements by expanding the query.
A possible reason for the slightly disappointing performance of the2-Poisson independence weighting scheme lies in the problem of estimation.
This area is known to cause difficulties with binary independence weights,
and there are many more parameters to estimate with TPI.
Apart from repeating some of the experiments on different collections, wemight therefore suggest two further lines of work. The first is to delve
more deeply into the estimation problems, and the second is to look for abetter theoretical explanation of the performance of the global-only
methods. For the latter it seems likely that these methods work well because
they are related in some way to TPI (as collection frequency is related to
BI).

-60-

REFERENCES
BOOKSTEIN, A. and KRAFT, D. [1977] Operations research applied to document
indexing and retrieval decisions. Journal of the A.CM., 24 no. 3 July
1977, pp. 418-427.
BOOKSTEIN, A. and SWANSON, D.R. [1974] Probabilistic models for automatic
indexing. Journal of the ASIS, 25 no. 5 Sept-Oct 1974, pp. 312-319.
BOOKSTEIN, A. and SWANSON, D.R. [1975] A decision theoretic foundation forindexing. Journal of the ASIS, _26 no. 1 Jan-Feb 1975, pp. 45-50.
CROFT, W.B. and HARPER, D.J. [1979] Using probabilistic models of document
retrieval without relevance information. Journal of Documentation, 35 no. 4
Dec 1979, pp. 285-295.
HARPER, D#J. [1980] Relevance feedback in document retrieval. Ph.D.
University of Cambridge.

Thesis,HARPER, D.J. and VAN RIJSBERGEN, C.J. [1978] An evaluation of feedback in
document retrieval using co-occurrence data. Journal of Documentation, 34
no. 3 Sept 1978, pp. 189-216.
HARTER, S.P. [1975a] A probabilistic approach to automatic keyword indexing.
Part I: On the distribution of specialty words in a technical literature.
Journal of the ASIS, ^6 no. 4 July-Aug 1975, pp. 197-206.
HARTER, S.P. [1975b] A probabilistic approach to automatic keyword indexing.
Part II: An algorithm for probabilistic indexing. Journal of the ASIS, 26
no. 5 Sept-Oct 1975, pp. 280-289.
IDE, E. [1969] Relevance feedback in an automatic document retrieval system.
M.Sc. thesis, Report ISR-15 to the National Science Foundation, Departmentof Computer Science, Cornell University, Ithaca, N.Y., 1969.
PORTER, M.F. [in press] An algorithm for suffix stripping.

Program.

ROBERTSON, S.E. [1977] The probability ranking principle in IR.
Documentation, _33 no. 4 Dec 1977, pp. 294-304.

Journal of

ROBERTSON, S.E. and SPARCK JONES, K. [1976] Relevance weighting of searchterms. Journal of the ASIS, 27 no. 3 May-june 1976, pp. 129-146.
SALTON, G., WONG, A. and YU, C.T. [1976] Automatic indexing using term
discrimination and term precision measurement. Information Processing andManagement, J_2 no. 1 1976, pp. 43-51.

SPARCK JONES, K. [1972] A statistical interpretation of term specificity andits application in retrieval . Journal of Documentation, 28 no. 1 March
1972, pp. 11-21.
SPARCK JONES, K. [1975] A performance yardstick for test collections.
Journal of Documentation, 31 no. 4 Dec 1975, pp. 266-272.
SPARCK JONES, K. [1979a] Experiments in relevance weighting of search terms.
Information Processing and Management, 15 no. 3 1979, pp. 133-144.
SPARCK JONES, K. [1979b] Search term relevance weighting given little
relevance information. Journal of Documentation, 35 no. 1 March 1979, pp.
30-48.
SPARCK JONES, K. [1980] Search term weighting: some recent results.
of Information Science, 1 (in press).

JournalVAN RIJSBERGEN, C.J. [1977] A theoretical basis for the use of cooccurrence
data in information retrieval. Journal of Documentation, 33 no. 2 June
1977, pp. 106-119.
VAN RIJSBERGEN, C.J. [1979] Information Retrieval (2nd ed.). Butterworths
1979
VAN RIJSBERGEN, C.J., HARPER, D.J. and PORTER, M.F. [in press] The selectionof good search terms. Information Processing and Management.
VASWANI, P.K.T. and CAMERON, J.B. [1970] The National Physical Laboratory
experiments in statistical word associations and their use in document
indexing and retrieval. National Physical Laboratory, Teddington. 1970.

-62-