A NEW niEDREI'ICAL FRAMEWRKFUR INFORMATION REIRIEVALC J van Rijsbergen
Department of Computing Science
University of Glasgow

A new franework based on a non-classical logic is proposed for investigating IR. The paper motivates theuse of a particular conditional logic as the 'right' logic for IR. A new principle, the logicaluncertainty principle, is proposed, to deal with the inherent uncertainty associated with applicable
inferences.
1.

PREFACEIn the last few years, I have become increasingly dissatisfied with the state-of-the-art in information
retrieval. I have reluctantly concluded that the fundamental basis of all the previous work is wrong.
Almost all of the previous work in Information Retrieval (including my own) has been based on theassumption that a formal notion of meaning is not required to solve the information retrieval problems.
Typically, researchers have assuned that one could get by, by only considering absence or presence of word
tokens in text together with counting information about the distriootion of words. Although such an
approach has been successful up to a point, it has become clear that further advances in the effectivenessof retrieval by such teclmiques are not possible. My observation is that performance based on statisticalteclmiques has reached its theoretical limit and any attempts to achieve further inl>rovements are a wasteof time. This is not to say that systems based on these techniques are not worth building; on the contrary,
because it is the best we have to date. But to wild a new generation of Information Retrieval
systems, a new theory will be needed.

2.

INIRODUCTION

This paper is to be seen as describing a new theoretical framework for investigating information retrieval.
The details at this stage are not conq>letely worked out; sane further details are given in
Van Rijsbergen (1986). For sane years now, I have felt the need to describe such a framework. It isespecially iqlortant if one wants to develop' information retrieval beyond the mere keyword approach. In
the closing pages of my earlier book on Information Retrieval (Van Rijsbergen, 1979) I said the following:"It has never been assuned that a retrieval system should attempt to 'understand' the content of adocunent. Most Information Retrieval systems at the moment merely aim at a bibliographic search.
Permission to copy without fee all orpart of this material ls granted provided that the copyriQht notice of the•organization of the 1986-ACM Conference
on Research and DevelopMent ln Information Retrieval" and the title of the
publication and its date appear.
1986 Organization of the
1986-ACM
ConferenceanRe•earchandDevelopment
in
Information
Retrieval

194

ACM SIGIR Forum

44

Vol. 51 No. 2, July 2017

Docunents are deemed to be relevant on the basis of a superficial description. I do not suggest that itis going to be a simple matter to program a cooplter to understand docunents. What is suggested is thatsome attempt should be made to construct something like a naive model, using more than just keywords, ofthe content of each docunent in the system. 'The more sophisticated question-answering systems do something
very similar. They have a model of their universe of discourse and can answer questions about it, and.
can incorporate new facts and rules as they become available".
When I wrote the above passage, I had no idea that progress in that direction was going to be so slw.

Themain obstacles appeared to be an adequate coopltable model of meaning, and its use in information
retrieval operations. It was argued that even if we had an appropriate semantics for text, and it could becomputed efficiently, we still would not know how to use it to retrieve docunents in response to requests.
I would now like to counter this objection by saying that theof semantics
appropriate
logic. I am not alone in thinking this; Cooper (1978) in his book on logico-linguistics would probably
make the same claim. Such a logic would be based on a formal semantics for text. The semantics would
provide a limited representation of the meaning of any text blt it would not be the meaning. A logic
would then be interpretable in that semantics. It leaves me to say how such a logic can help in the
retrieval of relevant docunents. To understand this, one IWSt think of docunents as sets of sentences
which are interpreted in the semantics, and think of queries as sentences too, the latte1;" usually a single
sentence. The single primitive operation to aid retrieval is then one of uncertain implication. In theextreme case, it would be logical implication, which through its interpretation in the formal semantics
is logical consequence. That is, a docunent is retrieved if it logically implies the request. However,as we all know, doc::unents rarely i.q>ly requests; there is always a measure of uncertainty associated withsuch an implication. And so, a notion of probable, or approximate, implication is needed where a plausible
inference instead of a strict inference is made, am the plausibility quantified through some measure.
Modelling the information retrieval process in this way goes beyoro the keyword approach, and specifies,
once and for all, \that relationship between a docunent and a request is to hold to compute probablerelevance. The importance of this new way of looking at Information Retrieval derives from the realisationthat with such a framework, Information Retrieval can advance with new developnents in formal semantics fortext. Starting with a keyword analysis which is a primitive semantics, we can go on to use our logic nomatter how sophisticated our semantics is. At all times, we are attempting to infer requests (treated as
sentences) from statements in the docuDents. The inference is possible because we have an interpretationof sentences in a docunent, we define this interpretation and can increase its complexity at will.
It is important to realise that the above approach is similar to the one adopted in database querying andquestion-answering. It is similar in that in all cases, the answer is obtained through a process oflogical satisfaction, i.e. looking at a coomon interpretation for premises and consequent. It is different
in that in the case of· Information Retrieval, a request is typicallysentence (i.e. contains novariables) and the relationship computed between a dOC\Illent (the premises) and the request (the consequent)is paranount i.e. if the relationship is sufficiently strong, the docunent is retrieved. In the case of
Data Base Management Systems, a request is typicallysentence (contains variables), the semantics
giving an instantiation of the request, wich is an answer.
3.

CLASSICAL INFORMATION REI'RIEVALTo begin with, I would like to say \that Information Retrieval is. Let us asSI.Ille that there is a large
store of documents on a variety of topics. A user of such a store will have a need to know certain things,
things that he does not know at present. He therefore expresses his information need in the form of arequest for information. Information Retrieval is concerned with retrieving those docl.ltlents that arelikely to be relevant to his information need as expressed by his request. It is likely that such a

195

ACM SIGIR Forum45

Vol. 51 No. 2, July 2017

retrieval process will be iterated, since a request is only an

expression of an information need,It
is important to realise that certain words in the above description are used carefully to avoid mis-

and the documents retrieved at one point may help in improving the request used in the next iteration.

understanding the idea of information retrieval.
Let us spell out the way in lilhich the description is to be interpreted. A request for information istranslated into a request for documents. The·are assumed to contain the information, therefore
the information is only retrieved indirectly. A request is an imperfect expression of a user's information
need; only a user will be able to tell whether a docunent contains the information he is seeking. If it
does contain the information sought then the docunent is considered relevant to the user's informationneed. This implies that docunents are not relevant
request; that is, identical requests subnitted by
two different users can be satisfied in different ways, one docunent may be relevant to one user and not
to the other. Relevance is here connected firmly to aboutness, a docunent is not relevant because of its
colour or shape. It is relevant because it is about the information sought.
In specifying a model for information retrieval, a small number of entities and concepts need to be defined.
Superficially, this would appear to be a simple matter. The entities and concepts are docunent, request,
property of a docunent, and relevance. Anyone can give COillliOnsense definitions of these; unfortunately,is required is a formal definition so that an Information Retrieval system can be formally specified
and therefore implemented on a computer.
Let us take a docunent as a set of sentences. Therefore, wen a docunent is considered for retrieval, thesentences in the docunent are considered individually or perhaps jointly. In considering them, one islooking for a relationship between them and the request. Such a relationship needs to be computable if
the Information Retrieval system is a computer-based one. If we take a request ·to be a sentence then therelationship to be computed is one between a set of sentences and a single sentence. This relationshipmust ·be such that it enables one to use it to determine whether a docunent is likely to be relevant or not.
I use 'likely' because we are assuming that relevance is user dependent and a request is an imperfecteXpression of an information need.
Fran a system's point-of-view, the computation of the relationship between docunent and request is central.
How is one to specify this relationship? There are several ways of doing this, each one has irrq;>lications
for bM one represents a docunent
a query. Ideally, one would like this representation to be separated
fran the relationship computation; of course, this has proved to be almost impossible. in what follows,
I propose that the right representation is given by a formal semantics for text (perhaps a Montague-stylesemantics, see Dowty, et al, 1981). The detailed specification of a semantics will be the subject of alater paper. The relationship between a docunent and a request will be formalised as a logical implication
to which a measure of uncertainty is attached. To motivate this 'implication' I shall give two
examplesin which standard Information Retrieval models are re-expressed in terms of uncertain implication.

4.

BOOLEAN RE'IRIEVAL

It is assuned that docunents are represented by index terms, or keywords, and that requests are logicalcanbinations (using AND, OR, 001') of these terms. A docunent is deemed likely to be relevant, and hence

retrieved, if the index terms in the docunent satisfy the logical_ expression in the request.

For example:

D1 • [A,B]
n2 •

[B,C]

n

[A,B,C]

3

•

A,B,C

index terms

196

ACM SIGIR Forum

46

Vol. 51 No. 2, July 2017

oretrieved because o is true Unplies Q is true11o2 , o:3

not retrieved.

The index terms are, in fact, the semantics, and indexing is seen as mapping a piece of text into its
formal semantics. Formally, an index term is true for a docunent if i t occurs in the set representing thedocunent.
Notice the use of the closed world assunption here, that the absence of an irdex term in a doc1.111ent isassuned to imply that it is false for that dOCllllent. The example makes clear that the relation coqlllted
between 0 and Q is one of logical implication. This is a simple set-up and COIIIIIOnly used in practice.
Unfortunately, it does not model the uncertainty of relevance.
5.

<Xl-oRDINATION lEVEL MATOIING

Just as in the exanple of Boolean retrieval above, doclll1ents are asstmed to consist of sets of index terms,
rut requests are now also sets of index terms. The relationship between a doctJDent and a request is now
computed in terms of the irdex terms they have in COIIIIIOn. The likelihood of relevance is taken to be
directly proportional to the nunber of index terms shared. For example, o , 0 , 0 as before,
1 2 3

Q

-

[A,B,C]I'\n (o'"\ Q)

1
2

-

Q)

n (o

-

n (03 ."'\ Q)

2

2

n(.)

number in set

3This relationship can be described in terms of the probability of a logical implication, so that,n (0 n Q) is proportional to the probability of 0 4 Q. 'What is a probability of 0
Q? Thisfirstly depends on how one interprets ' -> 1 • It is not to be interpreted as the material implication:
0 :::t Q, which is the usual truth-functional connective, only false when 0 is true and Q is false.
1, it is easy to understand that
Intuitively, whatever the precise meaning of 1
o_,.q , or that0 ..,t. Q • The problem is that when 0 -,t.l Q we rtiight still want to retrieve 0 because of its likelihoodof relevance. To IOOdel this uncertainty of relevance, we use uncertainty of
If we. asstJDe
P(OQ) • P(Q \ D) , then with D and Q as sets we have:P(O•P(Q 1\ D)P(O)n(Q/\ D)n(D)Treating n(D) as constant, we get the relationship that P(D __., Q) is proportional to the level of coordination.
6.

A <DNDmONAL IDGIC FOR INFORMATION REIRIEVALIn re-expressing the two well known retrieval models, Boolean and Co-ordination, as examples of conp.1tationof logical implication, I have made the case (in part) that the fundamental retrieval operation is oneof logical implication. Probabilistic retrieval can also be modelled as uncertain logical implication. For
this the reader is referred to Van Rijsbergen (1986). This logical implication is not one of material
implication, the usual truth-functional connective A ":::> B , which is true in all cases except when A istrue and B is false. To illustrate the difference between our earlier
B and A ::> B

197

ACM SIGIR Forum

47

Vol. 51 No. 2, July 2017

let:me give a
eX811'ple. First, let us assune that the probability of a conditional of the form
'If A is true theit B • is a conditional probability. Now consider a die and two events, A the event'a nunber less than 3 will be rolled' and B the event 'an even nunber will beThen for the two 'inplications' we get:P(A/\ B)
P(A)

P(A_,B)
P(A ::> B)•

P(A v B)

•

•

1

2

5

- 6

This shows that by interpreting the probability of a conditional as a conditional probability rather thanthe probability of a material implication we get widely differing results. Of course, I wuld maintainthat the conditional_ probability interpretation in the context of Information Retrieval is the right one.
Utere is another major reason wy a conditional naJSt not be identified with the material inplication inlogic. When using probabilistic inference, we want to ensure that the following soundness criterion
holds (Adams, 1975) : It is impossible for the premises of an inference to be probable. while its
conclusion is improbable. To illustrate a violation of this, we take the well known inference:
Given "'A we can infer A ::> B. [Remember that we can logically infer a consequent fran an antecedent,
whenever interpretations making the antecedent true also make the consequent true.] In our example,
whenever "-A is true, A will be false and hence A 'J 8 will be true independent of B's truth value.
If we identified
B with A => 8 , then such an inference could easily violate the soundness
criterion. It is easy to show situations (see diagran below) where P( _,A) is large andP(A --+B) • P(B I A) (probability of consequent) is small. In other words, altb:>ugh
1' - A infer A::::» B ' is valid ""A infer A _,B 1 should not be, if we take the probabilistic
soundness criterion seriously.

P( -..A)

large

P(B I A) -> 0

A conditional logic will, therefore, in general, be different fran a classical logic (Harper, et al, 1981).
It is my contention that such a conditional logic (and there are several formulations) is the correct one
for information retrieval.
7.

IDl 00 WE EVAUJATE P(sq)?

First, let us consider the case without probabilities. To analyse this case, we will need to introduce
possible-world semantics. An intuitive understanding of a possible world is that it is a C01J1>letespecification of how things are, or might be, down to the finest semanticallydetails (Bradley and
Schwartz, 1979). For our purposes, we will identify docunents with possible worlds. This will raise
problems of finiteness and structure which we will ignore for the moment.
Let s be a partial description of a docunent, this might be a set of sentences, or just a single index
term, q will be a request. In
whether to retrieve a doeunent, we would need to evaluate sq,

198

ACM SIGIR Forum48

Vol. 51 No. 2, July 2017

that is, whether s ->q is true or not. If s is true in a docunent d then s - . q is true
providing q is true. If s is not true in a doeunent then we go to the nearest docunent d' to din which it is true and consider lotlether q is true. If q is true in d' then s
q is true in d,otherwise it is false.
To give a silq>le exanple, s might be an index term, q the sane or a different index tenn. If s • q ,s
q is true follows trivially for those docUnents in ...ttich q occurs. The more interesting case iswhen s.r# q • In this case, to establish s
q in d find the nearest doc.unent d' in which s occurs
and check for the occurrence of q. It is
to realise that because of the primitive nature of thesemantics, an exanple such as s • F'C!R'mAN , q • PROGRAlfliNG lANGUAGE for which s - t q is directly truein a more cooplex semantics, can only be handled indirectly.
The above process illustrates what is tlOW' widely known as thesummarised as follows:(Mellor, 1976).

It might be

To evaluate a cotditional, first hypothetically make the minimal revision ofyour stock of beliefs required to assune the antecedent. Then, evaluate theacceptability of the consequent on the basis of this revised body of beliefs.
Note the meaning of a cotditional is not truth-functional under the above interpretation, i.e. its truth
does not simply depend on the truth valuation of s and q in one world. It has bec.ane an intensional
notion.
In docunent retrieval, we are often faced with the situation where s
q is assuned false because sdoes not logically imply q • 'Dlat is, asSURing the truth of the sentences (index terms) in a docunent wecannot arrive at q • Boolean retrieval is an excellent elC81lple: given a truth valuation for the terms
describing a
we retrieve those docunents which i.lrply q (make q true for that valuation). Whatis suggested here, is that a given docunent should be revised in a minimal way that makes s true. If,
after that revision, q is true, then s
q is true and d should be, retdeved. There aJ;e a I1llllberof ways of making this revision. One could restrict the revision to selecting a nearest docunent in whichs is true, in wbich case, no interaction from the user would be required. Or, one could involvethe user in expanding the infonnation contained in the document under consideration. Or, finally, one
could do document expansion automatically using information already stored in the system. We will returnto this notion of minimal revision when we attempt to formalise it.
Turning tlOW' to the probabilistic case, to evaluate P(s ._, q) , we revise the probability function P
P' in a minimal way, so that P'(s) • 1 • We then have that:q)•P'(q) •q) •a truth valuation:

An exaq>le of such a revision is to make P(swhere x,yv(x)are index terms and v

P(q \ s) •

v(y)

•

we gettoP(x -">x)
P(y

•
•

1
P(x

In the ease of Boolean semantics,•y)

In other words, a query consisting of the index term x, is related to a docunenty by P(x \ y).

If we restrict our worlds to docunents already present, then we can interpret this as:n(x ,. v)n(y)the frequency of the co-occurence of x and ydivided by the frequency of y.
/

199

ACM SIGIR Forum

49

Vol. 51 No. 2, July 2017

Of course, docunents and queries are far more corrplex than is asstmed above. It is not clear yet how one
deals with arbitrary complex docunents and queries. Generalising from the simple index term approach wewould need to specify a formal semantics in \ohich docunents and queries would be interpreted. To evaluates ->q "WOuld require a change in the interpretation function so thatinterpretation, and s ,.....;,)q true, if q was true as well.

8.

swould be true under the newlDGIC OF UNCERTAINlY

In evaluating the truth of yxevaluating P(y ......;) x) , we are dependent on a notion of nearness(closeness) between worlds or docunents. It is interesting to examine this in a little more detail.
Remember our prime concern is to establish that ' y - x' , or that y-9 x , with sufficiently large
probability. I f for the current docunent, we look at the effect of changing/revising our current
world and look at
x in the revised world. These changes are to be made in a minimal way •.

There is another "'lay of looking at this revision process which may be more appropriate in the Information
Retrieval context. I would like to generalise the Ramsey test and state a new principle.

Given any two sentencesxandLogical Uncertainty Principle
y ; a measure of the uncertainty ofy _.., x relative

to a given data set, is determined by the minimal extent to which we have to add
information to the data set, to establish the truth of y __, x •This is a slight generalisation of the foregoing. It denies that one can assess
x with certainty if
one has to revise the data set. It says nothing about how 'uncertainty' or 'minimal' might be quantified.
It specifically relativises truth to a given data set. The semantics of the data have been left
unspecified too. Nearness has been replaced by a measure of information.
evaluated is suggested in Van Rijsbergen (1986).
9.

How this measure might be

OONCLUSION

In this paper, I have given a new framework for Information Retrieval based on non-standard logic. The
fundamental primitive operation relating docunents and queries is taken to be logical implication. This
is not a truth functional notion in the classical sense, but rather can only be evaluated by considering
truth in other possible worlds. A new logical uncertainty principle -is stated to characterise uncertainty
associated with any logical implication; thereby quantifying the uncertainty of relevance.

I would like to thank Bruce Croft for his helpful comments in writing this paper.

Adams, E.W. (1975) The logic of conditionals, Dordrecht: Reidel.
Bradley, R. and Schwartz, N. (1979) Possible Worlds, Oxford: Basil Blackwell.
Cooper, W.S. (1978) Foundations of Logico-Linguistics, Dordrecht: Reidel.
Dowty, D.R., Wall, R.E. and Peters, S. (1981) Introduction to Montague Semantics, Dordrecht: Reidel.
Harper, W.L., Stalnaker, R. and Pearce, C. (1981) (eds) Ifs, Dordrecht: Reidel.
Mellor, D.H. (1976) (ed) Foundations: Essays in Philosophy, Logic, Mathematics and Economics: F P Ramsey,
London: R.K.P.
Van Rijsbergen, C.J. (1979) Information Retrieval, 2nd edition, London: Butterworths.
Van Rijsbergen, C.J. (1986) A
logic for information retrieval, The Computer Journal (in press).

200

ACM SIGIR Forum

50

Vol. 51 No. 2, July 2017