9.

2.

Logistic Models

2.1

General description

The object of a probabilistic retrieval model is to provide
some method of estimating the probability that a particular document
is relevant.

The information which is to be used to obtain thisestimate is essentially the specific combination of index terms
assigned to (or present in) the particular document.

Thus from the point of view of the probabilistic model, any
two documents with exactly the same set of index term assignments areindistinguishable.

The index terms in effect serve to allocate

documents to exclusive classes or cells, each all being defined bya particular combination of terms.
is the probability
jPj

The probability of relevancethat a randomly

selected document in cell

will be relevant.

A "pure" probabilistic approach would require past evidence
about the relevance of documents from any particular cell, in orderto make statements about new documents in that cell.

But since mostcells are empty and most of the rest contain only one or two documents,
this is not in general possible in information retrieval.
usual

So theprocedure has been to devise a model on the basis of someassumptions of independence between index terms, which
relationships between the various probabilities pj.

implyAssuming

such a model means that the estimate of p • for cell j may bebased on evidence about the relevance of documents from other cells.
For example, in the Robertson/Sparck Jones model, strong independence
assumptions are made; as a consequence, the estimate ofpj

uses

evidence from all previously-judged documents containing any oneof the terms that define cell j.

The model or class of models proposed here actually reverses
part of this process.

Instead of making independence assumptions andderiving relationships between thepn-fs,
dabout theserelationships.

it makes direct assumpumptions

10.

Tb© relationships are expressed in terms of the logistictransform of the probabilities, so the class of models might generally
be described as "logistic".

One particular model in the class, the"independent logistic" model, is roughly equivalent to the Robertson/
Spark Jones model.

Dependencies between terms can also be introduced.

Further, the framework includes a natural range of estimation methods,
as will be seen.

2.2

Mathematical Description

2,2#1

Notation and likelihood function

We assume that there ared

distinguishable classes (or cells)of documents.

We also assume that in unit time, the number of documents

in classnj,

thej,nfj

cj,

and that

It will be seen below that theparticular

has a Poisson distribution with mean

are independent.

assumption about theniis not important.

We also assume that theprobability of a document being relevant given that it is in class jis Pj.

The number of relevant documents in cell jcalled kj.

in unit time is

It is not hard to see that, conditional on

will have a binomial distribution with parameters pj

Using vector notation n_ is thewith entries nj,
hood function for£c_ given

andkj

rij.

d-dimensional column vector

p_t c_, k_ etc.

similarly

andrtj,We can write down the likeli-

k and n_dk.
L(-gjojk,n) =•3Jkj

i = i!

(n .-k J((l-p.)c.)° J
J J(n .-k .) !
J 3-ce11.

and the log-likelihooddftfe, £» K n) =)[_klogV. + (n^.-kJlog(l-p_.)+ n. log a.

3 = 1- Cj ~ log k.\- log (rij-kj)! j

The logistic models are models of the form (log —— ) ei-p.
where m isa vector subspace of K . For brevity we will just talkabout the model

If we reparametrize by writingP.
ir • = log — —Jfor 1 < j < d1-P.
3then the log-likelihood becomes

dl(l>

\_kfj

£» h n) = )~ njl°g(1+enJ)+nlog

3 =1->- log k.\ - log (n.-k.)\2.2.2a.- Oj

JEstimation
If we consier the maximum likelihood estimates (m.l.e.)

ir and c (assuming) we see that the m.l.e.

IT eand does not depend on YY\. . The m.l.e.
T^—mand is thatofof c is nof TT if it exists is denotedp c iTL which maximises—evdf(p) = f(kc.n^j= /tn9p)=7n l (1+eP{&„*.. "- n.log(l+eL VVj °9 vj) ^J)

J = ^(The existence of the m.l.e.

is discussed below.)

(1)

12.

We may easily Introduce Bayesian ideas into this model.

Ingeneral, we multiply the likelihood function by some factor which
describes the prior distribution, thus obtaining the posteriordistribution.

Then instead of a maximum likelihood estimate, we

may consider a maximum posterior estimate (or posterior mode)..
f(g)This will introduce an additive factor into the function
which must be maximised - an example is given below.

There are several possible ways of finding a maximum, i.e.
of deriving the maximum likelihood or maximum posterior distribution
estimates.

2.2.3

It is necessary, however, to use an

iterative procedure.

Existence of estimates
Considering the maximum likelihood estimates, it is very

convenient to define
elements are then..

such that N_ £ = 0.

# to be the diagonal matrix where diagonal
Now suppose there is a vector a eThen clearly f(p_+v)= f(pja necessary condition for the existence of anthat there is no non-zero
this condition onNand£ e Tfls.t.

N_ £ =form.l.e.
£.

will ensure that f(p)a11£.• H e n c e

for jr_ isImposing
is strictly

concave and hence has at most one finite maximum and that any
stationary value of
toensure /p e

is a maximum but it is not sufficient

has a maximum in

It is unlikely that there is any easily verified conditionon

HL> K a n d

W* which is equivalent to the existence of an(although some results can be proved).

m.l.e.

Further, it is likely thatin many practical situations, for some models which one might want
to use, them.l.e.

does not exist.

The Bayesian prior, however,may be used as a mechanism to ensure the existence of an estimate(now a maximum posterior estimate).
2.2.4

Discussion
The above descibes a general class of models for theprobabilities

p .. The particular model is expressed as a linear

13.

subspaceof the space generated by the logistic transforms IT .
JAn appropriate way to obtain estimates of the parameters of any
model from data would be the maximum likelihood method.
this method will notnecessarily

However,possess solutions at all,particularly where there is little data.

We may further introduce

prior information into the model by standard Bayesian methods, andmaximise the posterior distribution rather than the likelihood.
This procedure may be used to force the existence of a solution.
Also, the more restricted the model (i.e. the smaller the dimension
of Y H >, the more likely it is that the maximum likelihood method
will give a solution.
In section 2.3 this formalism is used to set up an "independence"model roughly equivalent to the Robertson-Sparck Jones model.

Wethen discuss the possible theoretical advantages and disadvantagesof the class of models defined here.

Given the form of the class of models, the question
naturally arises : under what conditions should one try to relax
or restrict the model (i.e. increase or reduce its dimension)?
In section 4 we return to this question in theoretical terms.

2.3

Example : the Independent

We now consider

Logistic Modela specific model which corresponds, in somesense, to the Robertson/Sparck Jones model.

Our basic assumption is that probability of relevance
will be modelled by a simple sum-of-weights, each weight being
associated with one of the matching terms.

That is, we will assume

that7T .

=wW,+ WtoJ
whereIand ( W > are the quantities to be estimated, and the sum

is over all query terms
cell j.

of *d, as required.

twhose presence defines the particularThis model can be simply expressed as a vector subspace

14.

Q as theTo formulate this model more precisely, we define

T c Q as a set of terms defining a

set of query terms, andparticular cell,i.e. those documents containing all the terms TQ*T.

and none of the terms(In fact each "cell" may be subdivided

by the presence or absence of terms other than query terms; however,give this model, such subdivision

makes nodifference to themaximum likelihood estimates derived from (1).) In order to deal
with the W

weight in the formula fortdummy term

TT ., we may define awhich occurs in all documents, and which

automatically included in T.

*T=Thenisis defined as follows :wt/(2)t eT
S o , from ( 1 ) ,f(w)~\log (1 + exp(Lt eT^ >> ~ Wwt ))t e TTsQn^ log (1 + exp(w,x-,t e T
T:teT

t eQ

T:teTterm

TcQk^is the total number of relevant documents assigned tot.

TheWs which maximizef(W) give the maximum likelihood

estimates of the IT'S.
We may add a Bayesian prior : suppose for example that the W
are assumed to be independent, normally distributed with means y,r2and common variance a(the means may, for example, be derived
from the traditional collection frequency weights). Then thefunction to be maximised is :w,log(l+e teT
teQ

T:tzTTcQ)

-15.

2.4

Comparison of present models with previous approaches

We first describe how the Independent Logistic model might beapplied in a practical situation, and then discuss its apparent
advantages and disadvantages, in comparison with the Robertson/
Sparck Jones model.

We also discuss its possible extension to deal

with term dependence.

It should be pointed out that the comparison between the present
and previous approaches is not intended to provide a simple decision
between the two.

Rather we hope to shed some light on the wholeproblem, by looking at it from different points of view.

2.4.1

Possible application of the independent logistic model

We assume a relevance feedback situation : that is, we assume
an initial search which has revealed some relevant documents.
want touse this information to estimate the w'sWe(by maximising

expression (3) or (4)), so as to derive an improved ranking of thedocuments on the next run.

The next run may be on the same collection(as in retrospective searching) or a new one (as in SDI).

The result of the initial search is a small number (typically)of documents known to be relevant, also a small number (perhaps zero)of documents known to be non-relevant, and the large bulk of thecollection of unknown relevance status.

Perhaps the obvious way to

use this data in a probablistic model would be to use only thedocuments of known relevance status in each cell in the derivationof estimates.

However, it has been common in earlier systems to

use the known relevant as such and all the remainder (known-nonrelevant and unknown) as "non-relevant".
"complement"This is known as theprocedure (Harper and Van Rijsbergen, 1978).

The

justification for this procedure is that almost all the unknown
are certainly non-relevant; the resulting increase in precisionof the estimates is likely to far outweigh the slight bias resulting.
(Some experiments by Harper and Van Rijsbergen, using another formula,support this view).

16.

We assume, then, that the complement procedure is adopted
for the Independent logistic model; this has consequences which arediscussed below.

In that case, the quantities we need in order to maximise
expression (3) or (4) are :

(a)

2>

kT i.e. the total numberof known relevant

T:teT
documents assigned to each term

(b)

t.

rirpt i.e. the total number of documents, known orunknown, in each individual cell T.

As indicated above, the estimates of the w'smeans of an iterative

would be obtained bymaximisation algorithm.

The particular

procedure used in our experiments is described in section 3.3.

2.4.2

Main points of comparison

We mayindicate the main differences betweeen the independent

logistic model and the Robertson/Sparck Jones model :(a)

The new model requires a litte more data, namely
the individual ft™ values (as opposed to the totalfor each term)(b)

The new model uses an iterative algorithm

for obtaining

the estimates, rather than a simple formula.

The effectof this will depend very much on the number of query terms|| Q I , since the procedure requires manipulation ofQ || xQ \matrix.

This it may affect computation

time insignificantly for a 4-term query, but require a
totally unrealistic amount of time for a 40-term SDIprofile.

aThe methods used and the resources requiredin the present experiments are discussed in section 3.

17.

The independence assumptions of the new model areconsiderably weaker than those of the Robertson/Sparck
Jones model.

The definition of TfL

givenby expression(2) is equivalent to assuming, in some sense, that thedegree of dependence of any set of terms is the same in
the non-relevant set as it is in the relevant set (Robertson/Sparck Jones assume nodependence in either set).

One major advantage claimed for the logistic models in
the medical context is that the estimation process does
not involve assuming that the sample on which the estimatesare based is random : it is only necessary to assume thatthe items in the sample from a given cell are a random
sample of items in that cell.

This property should

confer a considerable advantage on the logistic models,since the estimation sample is drawn on the basis ofcell membership.

However, it appears that this advantage

is nullified by the use of the Complement method for nonrelevant documents (for which there is no equivalent
in the medical application).

The major reason for the choice of the maximum likelihood
method of estimating parameters is its mathematicaltractability.

Maximum likelihood estimates do have anumber of desirable properties, but these properties tend
to be asymptotic : that is they only hold absolutely forlarge samples.

The estimation method used in the Robertson/

Sparck Jones model (i.e. the "#.5" formula, expression (1)in section 1.2) was chosen on the basis of a specificproperty of unbiasedness; this is also an asymptotic
property, but the small-sample error is not too great,-2-1since it varies with nrather than nfor sample
size n.

The Bayesianprior is a very much more flexible device

than the equivalent in the Robertson/Sparck Jones method,

18.

namely theweights.

"+ 0.5" in the formula for calculating
Different choices of the meansvu

reflect

different assumptions about possible prior indications
2of term value; different choices of the variance areflect different assumptions about the reliance to beplaced on these prior indications.

Some experimentswith different values are discussed in section 3.
(g)

Finally, the model itself is more flexible.

Thus wecan consider the addition of a new term, or of aterm-pair(to allow for term-dependence not conforming

to the independence assumptions) by simply adding anappropriate dimension to j7[as anew component of m.

(Adding a term-pairdoes not conflict with theindependence assumptions discussed in (c) above, since
A & B—>-4

applies to both the relevant and the non-relevant set) .

Thus we see that the logistic model, or class of models,differs from previous approaches in a number of interacting
theoretical and practical ways.

Section 3 is devoted to a seriesof experiments with various versions of the logistic model on
two test collections.