Inference Networks for Document Retrieval
Howard Turtle and W. Bruce Croft
Computer and Information
Science Department
University of Massachusetts
Amherst, MA 01003

Abstract

The use of inference networks to support document retrieval is introduced. A
network-baseadretrieval model is described and compared to conventional probabilistic and Boolean models.
1

Introduction

Network representations have been used in information retrieval since at least the early
1960’s. Networks have been used to support diverse retrieval functions, including browsing[TC89], document clustering [CroSO], spreading activation search [CK87], support for multiple search strategies [CT87], and representation of user knowledge [OPCSS] or document
content [TS85].
Recent work suggests that significant improvements in retrieval performance will require
techniques that, in some sense, “understand” the content of documents and queries [vR86,
Cro87] and can be used to infer probable relationships between documents and queries. In
this view, information retrieval is an inference or evidential reasoning process in which weestimate the probability that a user’s information need, expressed as one or more queries, is
met given a document as “evidence.” Network representations show promise as mechanisms
for inferring these kinds of relationships [CT89,CK87].
The idea that retrieval is an inference or evidential reasoning process is not new.
Cooper’s logical relevance [Coo’ll] is based on deductive relationships between representations of documents and information needs. Wilson’s situational relevance [Wi173] extends
this notion to incorporate inductive or uncertain inference based on the degree to whichdocuments support information needs. The techniques required to support these kinds ofinference are similar to those used in expert systems that must reason with uncertain information. A number of competing inference models have been developed for these kinds ofexpert systems [KL86,LK88] and several of these models can be adapted to the document
retrieval task.

In the research described herq we adapt an inference network model to the retrieval

task. The use of the model is intended to:lSupport the use of multiple document representation schemes. Research has shownthat a given query will retrieve different documents when applied to different repre-

Permission
to copy without
fee all part of this material
is granted provided
that the copies
are not made or distributedfor directcommercial advantage,
the ACM copyrightnotice and the titleof the publicationand its date appear,and notice
is given that copying is by permissionof the Associationfor
Computing Machinery.
To copy otherwise,or to republish,
requiresa fee and/or specificpermission.
(Cl

ACM SIGIR Forum

1990

ACM

o-89791-408-2

124

90

0009

1

$1.50

Vol. 51 No. 2, July 2017

sentations, even when the average retrieval performance achieved with each representation is the same. Katzer, for example, found little overlap in documents retrieved
using seven different representations, but found that documents retrieved by multiple representations were likely to be relevant [KMT+82].
Similar results have beenobtained when comparing term- with cluster-based representations [CH79] and termwith citation-based representations [FNL88].
ll

Allow results from different queries and query types to be combined. Given a single
natural language description of an information need, different searchers will formulatedifferent queries to represent that need and will retrieve different documents, evenwhen average performance is the same for each searcher (MKN79,KMTS82].
Again,
documents retrieved by multiple searchers are more likely to be relevant. A description of an information need can be used to generate several query representations (e.g.,
probabilistic, Boolean), each using a different query strategy and each capturing different aspects of the information need. These different search strategies are known toretrieve different documents for the same underlying information need [Cro87].
Facilitate flexible matching between the terms or concepts mentioned in queries andthose assigned to documents. The poor match between the vocabulary used to express
queries and the vocabulary used to represent documents appears to be a major causeof poor recall [FLGD87]. Recall can be improved using domain knowledge to match
query and representation concepts without significantly degrading precision.

The resulting formal retrieval model integrates several previous models in a single theoreticalframework; multiple document and query representations are treated as evidence which is
combined to estimate the probability that a document satisfies a user’s information need.
In what follows we briefly review candidate inference models, present an inference
network-based retrieval model, and compare the network model to current retrieval models.
2

Inference

networks

The development of automated inference techniques that accommodate uncertainty has
been an area of active research in the artificial intelligence community, particularly in thecontext of expert systems [KL86,LK88]. Popular approaches include those based on purely
symbolic reasoning [Coh85,Doy79], fuzzy sets [Zad83], and a variety of probability models[Ni186,Che88]. Two inference models based on probabilistic methods are of particular interest: Bayesian inference networks [Pea88,LS88] and the Dempster-Shafer theory of evidence[Dem68,Sha76].
A Bayesian inference network is a directed, acyclic dependency graph (DAG) in which
nodes represent propositional variables or constants and edges represent dependence relations between propositions.
If a proposition represented by a node p “causes” or implies
the proposition represented by node q, we draw a directed edge from p to q. The nodeq contains a link matrix that specifies P(qJp) for all possible values of the two variables.
When a node has multiple parents, the link matrix specifies the dependence of that nodeon the set of parents (r,) and characterizes the dependence relationship between that node2

ACM SIGIR Forum

125

Vol. 51 No. 2, July 2017and all nodes representing its potential causes. 1 Given a set of prior probabilities for theroots of the DAG, these networks can be used to compute the probability or degree of belief
associated with all remaining nodes.
Different restrictions on the topology of the network and assumptions about the way inwhich the connected nodes interact lead to different schemes for combining probabilities.
In general, these schemes have two components which operate independently:
a predictive
component in which parent nodes provide support for their children (the degree to which we
believe a proposition depends on the degree to which we believe the propositions that mightcause it), and a diagnostic component in which children provide support for their parents (ifour belief in a proposition increases or decreases, so does our belief in its potential causes).
The propagation of probabilities through the net can be done using information passed
between adjacent nodes.
The Dempster-Shafer theory of evidence, although not originally cast as a networkmodel, can be used as an alternative method for evaluating these kinds of probabilistic
inference networks. Rather than computing the belief associated with a query given a setof evidence, we can view Dempster-Shafer as computing the probability that the evidence
would allow us to prove the query. The degree of support parameters associated with thearcs joining nodes are not interpreted as conditional probabilities, but as assertions thatthe parent node provides support for the child (is active) for some proportion p of the timeand does not support the child for the remainder of the time. For an and-combination wecompute the proportion of the time that all incoming arcs are active. For an or-combination
we compute the proportion of the time that at least one parent node is active. To computethe provability of the query given a document, we examine all paths leading from the
document to the query and compute the proportion of time that all of the arcs on at least
one proof path are active. Given the structure of these networks, this computation can bedone using series-parallel reduction of the subgraph joining the document and query in time
proportional to the number of arcs in the subgraph.
The Bayesian and Dempster-Shafer models are different and can lead to different results.
However, under the assumption of disjunctive rule interaction (so called “noisy-OR”)
andthe interpretationof an arc from a to b as P(bla) = p and P(b17u) = 0, the Bayesianand Dempster-Shafer models will produce similar results [Pea88, page 4461. The document
retrieval inference networks described here are based on the Bayesian inference networkmodel.
The use of Bayesian inference networks for information retrieval represents an extensionof probability-based
retrieval research dating from the early 1960’s (MK601. It has long
been recognized that some terms in a collection are more significant than others and that
information about the distribution of terms in a collection can be used to improve retrieval
performance. The use of these networks generalizes existing probabilistic models and allows
integration of several sources of knowledge in a single framework.
‘Whilethis probability

specificationis generally

referred

to as a link matrix,

it is actuallya tensor.

3

ACM SIGIR Forum

126

Vol. 51 No. 2, July 2017

Figure 1: Basic document inference network
3

Basic

Model

The basic document retrjeval inference network, shown in Figure 1, consists of two component networks: a document network and a query network. The document network represents
the document collection using a variety of document representation schemes. The document
network is built once for a given collection and its structure does not change during query
processing. The query network consists of a single node which represents the user’s information need and one or more query representations which express that information need.
A query network is built for each information need and is modified during query processing
as existing queries are refined or new queries are added in an attempt to better characterize
the information need. The document and query networks are joined by links between representation concepts and query concepts. All nodes in the inference network take on values

4

ACM SIGIR Forum

127

Vol. 51 No. 2, July 2017

from the set {false, true}.
3.1

Document

network

The document network consists of document nodes (di’s), text representation nodes (tj’s),and concept representation nodes (TL’s). Each document node represents a document in
the collection. A document node corresponds to the event that a specific document has
been observed. The form of the document represented depends on the collection and its
intended use, but we will assume that a document is a well defined object and will focus on
traditional document types (e.g., monographs, journal articles, office documents).
Document nodes correspond to abstract documents rather than their physical representations. A text representation node or text node corresponds to a specific text representationof a document. A text node corresponds to the event that a text representation has been
observed. We focus here on the text content of documents, but the network model can
support documents nodes with multiple children representing additional component types(e.g., figures, audio, or video). Similarly, a single text might be shared by more than one
document. While shared components is rare in traditional collections (an example would
be a journal article that appears in both a serial issue and in a reprint collection) and is
not generally represented in current retrieval models, it is common in hypertext systems.
For clarity, we will consider only text representations and will assume a one-to-one correspondence between documents and texts. The dependence of a text upon the document isrepresented in the network by an arc from the document node to the text node.
The content representation nodes or representation nodes can be divided into several
subsets, each corresponding to a single representation technique that has been applied tothe document texts. For example, if a collection has been indexed using automatic phrase
extraction and manually assigned index terms, then the set of representation nodes willconsist of two distinct subsets or content representation types with disjoint domains. Thus,
if the phrase “information
retrieval” has been extracted and “information
retrieval” hasbeen manually assigned as an index term, then two representation nodes with distinct
meanings will be created. One corresponds to the event that “information
retrieval” hasbeen automatically extracted from a subset of the collection, the second corresponds to theevent that “information retrieval” has been manually assigned to a (presumably distinct)
subset of the collection. We represent the assignment of a specific representation concept toa document by a directed arc to the representation node from each text node corresponding
to a document to which the concept has been assigned. For now we assume that the presenceor absence of a link corresponds to a binary assigned/not assigned distinction, that is, there
are no partial or weighted assignments.
In principle, the number of representation schemes is unlimited; in addition to phrase
extraction and manually assigned terms we would expect representations based on natural
language processing and automatic keyword extraction. For any real document collection,
however, the number of representations used will be fixed and relatively small, The potential
domain of each representation scheme may also be unlimited, but the actual number ofprimitive representation concepts defined for a given collection is fixed by the collection.
The domain for most automated representation schemes is generally bounded by some5

ACM SIGIR Forum

128

Vol. 51 No. 2, July 2017

function of the collection size (e.g., the number of keywords cannot exceed the number ofwords in a collection). For manual representation schemes the domain size is limited by the
number of documents, the representation scheme itself (e.g., a controlled vocabulary), andthe amount of time a human expert can spend analyzing each document.
The basic document network shown in Figure 1 is a simple three level DAG in whichdocument nodes are roots, text nodes are interior nodes, and representation nodes are leaves.
Document nodes have exactly one text node as a child and each text node has one or more
representation nodes as children.
Each document node has a prior probability
associated with it that describes theprobabilityof observing that document; this prior probability
will generaily be set tol/(collectionsize) and will be small for real collections. Each text node contains a specification of its dependence upon its parent; by assumption, this dependence is complete, atext node is observed (1; = true) exactly when its parent document is observed (di = true).
Each representation node contains a specification of the conditional probability associated with the node given its set of parent text nodes. This specification incorporates theeffect of any indexing weights (e.g., term frequency for each parent text) or term weights(e.g., inverse document frequency) associated with the representation concept. While, in
principle, this would require O(2”) space for a node with n parents, in practice we use
canonical representations that allow us to compute the required conditional probabilities
when needed. These canonical schemes require O(n) space if we weight the contribution ofeach parent or 0( 1) space if parents are to be treated uniformly.
3.2

Query

network

The query network is an “inverted” DAG with a single leaf that corresponds to the event thatan information need is met and multiple roots that correspond to the concepts that express
the information need. As shown in Figure 1, a set of intermediate query nodes may be
used when multiple queries express the information need. These nodes are a representation
convenience; it is always possible to eliminate them by increasing the complexity of the
distribution specified at the node representing the information need.
In general, the user’s information need is internal to the user and is not precisely understood. We attempt to make the meaning of an information need explicit by expressing
it in the form of one or more queries that have formal interpretations.
These queries may
be generated from a single natural language description (e.g., keywords or phrases for aprobabilistic search, a Boolean representation, sample documents, . . . ) or they may represent additional sources of information (e.g., an intermediary’s description of the user or of
the information need, or feedback provided by the user). It is unlikely that any of these
queries will correspond precisely to the information need, but some will better characterize
the informatjon need than others and several query specifications taken together may be abetter representation than any of the individual queries.
The roots of the query network are query concepts; they correspond to the primitive
concepts used to express the information need. A single query concept node may have several
representation concept nodes as parents. Each query concept node contains a specificationof its dependence on the set of parent representation concepts. The query concept nodes

6

ACM SIGIR Forum

129

Vol. 51 No. 2, July 2017

define the mapping between the concepts used to represent the document collection and theconcepts used in the queries. In the simplest case, the query concepts are the same as therepresentation concepts so each query concept has exactly one parent. In a slightly more
complex example, the query concept “information retrieval” may have as parents both thenode corresponding to “information retrieval” as a phrase and the node corresponding to“information
retrieval” as a manually assigned term. As we add content representations
to the document network and allow query concepts that do not explicitly appear in any
document representation, the number of parents associated with a single query concept will
increase.
A query concept is similar to a representation concept that is derived from other representation concepts (see section 5 for a discussion of derived representation concepts) andin some cases it will be useful to “promote” a query concept to a representation concept.
For example, suppose that a researcher is looking for information on a recently developed
process that is unlikely to be explicitly identified in any existing representation scheme. The
researcher, if sufficiently motivated, could work with the retrieval system to describe how
this new concept might be inferred from other representation concepts. If this new concept
definition is of general interest, it can be added to the collection of representation concepts.
This use of inference to define new concepts is similar to that used in RUBRIC [TS85).
The attachment of the query concept nodes to the document network has no effect on
the basic structure of the document network. None of the existing links need change andnone of the conditional probability specifications stored in the nodes are modified.
A query node represents a distinct query form and corresponds to the event that thequery is satisfied. Each query node contains a specification of the dependence of the query on
its parent query concepts. The link matrices that describe these conditional probabilities are
discussed further in section 3.4, but we note that the form of the link matrix is determinedby the query type; a link matrix simulating a Boolean operator is different than a matrix
simulating a probabilistic or weighted query.
The single leaf representing the information need corresponds to the event that an
information need is met. In general, we cannot predict with certainty whether a user’s
information need will be met by a document collection. The query network is intended tocapture the way in which meeting the user’s information need depends on documents andtheir representations. Moreover, the query network is intended to allow us to combine information from multiple document representations and to combine queries of different types toform a single, formally justified estimate of the probability that the user’s information needis met. If the inference network correctly characterizes the dependence of the informationneed on the collection, the computed probability provides a good estimate.
3.3

Use of the inference

network

The retrieval inference network is intended to capture all of the significant probabilistic dependencies among the variables represented by nodes in the document and query networks.
Given the prior probabilities associated with the documents (roots) and the conditional
probabilities associated with the interior nodes, we can compute the posterior probability
or belief associated with each node in the network. Further, if the value of any variable

7

ACM SIGIR Forum

130

Vol. 51 No. 2, July 2017

represented in the network becomes known we can use the network to recompute the probabilities associated with all remaining nodes based on this “evidence.”
The network, taken as a whole, represents the dependence of a user’s information needon the documents in a collection where the dependence is mediated by document andquery representations. When the query network is first built and attached to the document
network we compute the belief associated with each node in the query network. The initialvalue at the node representing the information need is the probability that the informationneed is met given that no specific document in the collection has been observed and all
documents are equally likely (or unlikely).
If we now observe a single document di andattach evidence to the network asserting d; = true we can compute a new belief for every
node in the network given di = true. In particular, we can compute the probability thatthe information need is met given that d; has been observed in the collection. We can now
remove this evidence and instead assert that some dj, i # j has been observed. By repeating
this process we can compute the probability that the information need is met given eachdocument in the collection and rank the documents accordingly.
In principle, we need not consider each document in isolation but could look for thesubset of documents which produce the highest probability that the information need ismet. While a general solution to this best-subset problem is intractable, in some cases
good heuristic approximations are possible. Best-subset rankings have been considered in
IR (Sti75], and similar problems arise in pattern recognition, medical diagnosis, and truthmaintenance systems. See [Pea881 for a discussion of the best-subset or belief revision
problem in Bayesian networks. At present, we consider only documents in isolation because
the approach is computationallysimpler and because it allows comparison with earlier
retrieval models that produce document rankings consistent with the Probability Ranking
Principle [Rob771 in which documents are considered in isolation.
The document network is built once for a given collection. Given one or more queries
representing an information need, we then build a query network that attempts to characterize the dependence of the information need on the collection. If the ranking produced by
the initial query network is inadequate, we must add additional information to the querynetwork or refine its structure to better characterize the meaning of the existing queries.
This feedback process is quite similar to conventional relevance feedback.
3.4

Link

matrixforms

For all non-root nodes in the inference network we must estimate the probability that anode takes on a value given any set of values for its parent nodes. If a node a has a set ofparents A, = {pr, . . . ,pn}, we must estimate P(a]pi, . . . ,pn).
The most direct way to encode our estimate is as a link matrix. Since we are dealing
with binary valued propositions, this matrix is of size 2 x 2” for n parents and specifies
the probability that a takes the value a = true or a = false for all combinations of parent
values. The update procedures for Bayesian networks then use the probabilities provided
by the set of parents to condition over the link matrix values to compute the predictive
component of our belief in a or P(a z true). Similarly, the link matrix is used to provide
diagnostic information to the set of parents based on our belief in a. As mentioned earlier,

ACM SIGIR Forum

131

Vol. 51 No. 2, July 2017

encoding our estimates in link matrix form is practical only for nodes with a small set ofparents, so our estimation task has two parts: how do we estimate the dependence of anode on its set of parents and how do we encode these estimates in a usable form?
We will describe four canonical link matrix forms, three for the Boolean operators anda fourth for simple probabilistic retrieval. For illustration, we will assume that a node Q
has three parents A, B, and C and that

P(A = true) = a,P(B = true) = b,

P(C = true) = c.

For or-combinations, Q will be true when any of A, B, or C is true and false only whenA, B, and C are all false. This suggesls a Iink matrix of the form

10000000
L, = ( 01111111) *Using a closed form of the update procedures, we haveP(Q = true)=(1 - a)(1 - b)c $ (1 - a)b(l - c) + (1 - a)bc $ a(1 - b)(l - c)tct( 1 - b)c + ab( 1 - c) + abc=

1 - (1 - a)(1 - b)(l -c)

which is the familiar rule for disjunctive combination of events that are not known to be
mutually exclusive. Similar matrix forms can be developed for and (P(& = true) = abc)
and not (P(Q = true) = 1 - u).
If we restrict the parent nodes for any of these logic operators to values 0 or 1 then Q
must also have a value of 0 or 1. If we allow terms to take on weights in the range [0, l] andinterpret these weights as the probability that the term has been assigned to a document
text, then these inierence networks provide a natural interpretation’ior
Boolean retrieval
with weighted indexing. The use of these canonical forms to simulate Boolean retrieval is
discussed in section 4.3
For probabilistic retrieval each parent has a weight associated with it, as does the child.
In this weighted-sum matrix, our belief in Q depends on the specific parents that are true
- parents with larger weights have more influence in our belief. If we let lua, Wb,2u, 2 0 be
the parent weights, 0 5 20~5 1 the child weight, and t = 20~t Wbt wc, then we have a link
matrix of the form
1 pu”+yb)wP
( 0

wculp
t

Evaluation

Jwa+yc)wq.
WbU)g
t

wowp
t

(=‘b+Wc)‘+t~WbSWC)W~ WaWp
t
t

wcwc
UlbZUp1 - w*
tt{Wo+W,)Wq (Wa+Wb)Wq
WP )tt

of this link matrix form results in
P(Q = true)=(%a t wbb t w&q
1

This link matrix can be used to implement a variety of weighting schemes, including
the familiar term weighting schemes based on within-document
term frequency (tj), inverse

9

ACM SIGIR Forum

132

Vol. 51 No. 2, July 2017

To illustrate a tJidf weighting, let & be a
document frequency (idf ) or both (tf.idf).
representation node and let A, B, and C be document nodes. Let, wa, Wb, and wc be thenormalized tf values for A, B, and C, let id& be the normalized idfweight for Q, and let

wq= ‘dfp- (W,+ wb+ WC).
Given our basic model, when A is instantiated,bel(Q)=(1)belief in Q is given by

w0wQ
wa + wb t w,=

tf, - ‘dfq* (WC,+ wb t WC)=

tf, . idfq

wa t wb t WC

which is a form of tf.idf weight. In general, when a document is instantiated all representation concept nodes to which it is attached take on the tfiidf weight associated with the
document/termpair.
The weight at Q has two distinct parts. The first part (id& in our example) acts to set
the maximum belief achievable at a node. If, for some combination of parent values, ourbelief in Q is certain then this component disappears. Note that in this formulation, theidf component is dependent only upon the distribution of the term in the collection, noton the distribution of the term in relevant and non-relevant subsets. Relevance feedback ismodeled as part of the query network and does not affect belief in representation concepts.
The second part (w, + wb + 20, in our example) acts to normalize the parent weights.
Equation 1 is appropriate for the basic model in which only one document is instantiatedat a time. In the extended model of section 5 where multiple roots can be instantiated, thiscomponent is adjusted to normalize for the maximum achievable set of parent weights. In
the general case, where all parents can take any value in the range [O,l], this normalizing
coinponent disappears.
These canonical forms are sufficient for the retrieval inference networks described here,
but many others are possible (see section 4.3 for other examples). Further, when the numberof parents is small (say, less than 5 or 6) we can use the full link matrix if the dependenceof a node on its parents does not fit a canonical form.

4Comparison

with

other

retrievalmodels

The inference network retrieval model generalizes both the probabilistic and Boolean models. Inference networks can be used to simulate both probabilistic and Boolean queries andcan be used to combine results from multiple queries.
In this section we compare the inference network model with probabilistic (sections 4.1
and 4.2) and Boolean (section 4.3) models and show how inference networks can be used
to simulate both forms of retrieval. We then consider how the probabilities required by themodel can be estimated (section 4.4); the estimation problems are essentially equivalent tothose encountered with probabilistic or vector-space retrieval.

10

ACM SIGIR Forum

133

Vol. 51 No. 2, July 2017

Figure 2: Inference network for binary independence model
4.1

Probabilistic

retrievalmodelsConventional probabilistic models [vR79,SM83] rank documents by the probability that eachdocument would be judged relevant to a given query, P(relevant]di).2
This is, in many ways,
similar to computing the probability that a user’s information need is met given a specificdocument, P(l]d;). The principal differences between conventional probabilistic models andthe model described here are: 1) most probabilistic models do not explicitly represent thequery, 2) conven$ional probabilistic models do not distinguish between a document and its
representations but treat a document as a single vector, and 3) the inference network model
depends less upon Bayesian inversion than probabilistic models, Bayesian inversion is justone way to estimate P(l]d;) (or P(Q]di) in the case of a single query).
In this section we summarize the major differences between the inference network andconventional probabilistic models by comparing the network model to the binary independence model. In the next section we provide a formal comparison of the inference networkmodel with a recent probabilistic model that explicitly represents documents and queries.
An inference network that corresponds to the binary independence model [vR79] isshown in Figure 2. A document is represented by a vector whose components are indexing
or representation concepts (d; = { rr,. . . , T,}). The set of concepts considered is generally
restricted to the subset that actually occurs in the query. Comparing this network with thatshown in Figure 1, we see that in the binary independence model, the document network
is represented by a single level of representation nodes and the query network consists of asingle relevance node. In order to implement this network we must somehow estimate theprobability of relevance given the set of parent representation conkepts and this estimate
must incorporate all of our judgments about the probability that a representation concept
should be assigned to a document, about the semantic and stochastic relationships between
representation concepts, about the relationship between concepts named in the query andassigned to documents, and about the semantics of the query itself. This dependence iscomplex and its estimation is not a task we could expect users to perform willingly or‘Most drobabilistic
models do not actually compute P(relevant(d.),
but simply rank documents using
some function that is monotonic with P(relevantld,).
Like Fuhr ([Fuh89]), we believe that an estimate of
the probabilityof relevance is more useful than the ranking by itself. A ranked list of documents in which
the top ranked document has a probabilityof relevance of 0.5 should be viewed differently
than a similar
list in which the top ranked document has a probabilityof relevance of 0.95.

11

ACM SIGIR Forum

134

Vol. 51 No. 2, July 2017

reliably.
One approach to simplifying the estimation task is to invoke Bayes’ rule SO that weneed only estimate the probability that each representation concept occurs in relevant or
non-relevant documents. This approach does not help to provide initial estimates of theprobability distributions since these “simpler” estimates must still incorporate all of thejudgments required for the “hard” estimate. The advantage of this approach is that, given
samples of relevant and non-relevant documents, it is easy to compute P(ri) for the relevantsample and to use the result as an estimate of P( T;Jre 1evant = true). We can use a similar
estimate for P(r; Irelevant = false). Given a set of independence assumptions and estimatesfor P(d;) and P( re 1evant = true) we can compute P(relevantld;).3
Estimating P(relevantId;)
without the use of Bayes’ rule would be.extremely difficult.
Essentially the same procedures can be used to estimate P(QIdi). The main difference
between the two estimates is that instead of using the representation concepts directly wemust compute P(cjlr,)
and compute an expected value for P(cjldi) in order to estimate

P(Ql4).

The question remains, however, whether estimates of P(relevantldi) or P(Qldi) obtainedin this way match users’ intuition about the dependence. The fact that relevance feedback‘does improve retrieval performance suggests that the estimates of P(relevantld;) do capture
at least some of the dependence, but these estimates are generally based OR a small numberof relevant documents and are necessarily rather coarse.
While it is clear that estimating P(relevantld;)
directly from a small number of documents is impractical, it may be possible to obtain estimates of P(QITQ). Users may, forexample, be able to assign importance to the concepts in their query and may be able toidentify significant interactions between concepts. These estimates could improve the initial estimate and might be used in conjunction with the estimates derived from training
samples.
A second approach to simplifying the estimation task is to identify the different typesof judgments that enter into the overall estimate and to develop estimates for each typeof judgment separately. The model presented here represents one decomposition in which
the task of estimating the probability that a given document satisfies an information needconsists of judgments about the relationship of a document to its text, the assignment ofrepresentation concepts to the text, the relationships between query and representation
concepts, and the relationship between queries, query concepts, and the information need.
Other decompositions are certainly possible and can be accommodated within the samegeneral framework. The set of relationships presented here incorporates those judgments
most important for current generation document retrieval systems.
When viewed this way, the probabilistic and inference models use two similar approaches
to the same estimation problem. The probabilistic model uses a single, general purpose
rule and makes assumptions about term dependence in order to estimate P(relevantld;).
The model presented here views the problem of estimating P(l(di) as consisting of a set of
logically related estimates. Each estimate is made independently using procedures specific to
3P(di)
document

and P(relevant= hue) do not play a majorrole in probabilistic
ranking but are required to compute P(relevant(d,).

models that

only

producea12

ACM SIGIR Forum

135

Vol. 51 No. 2, July 2017

Figure 3: Inference network for the RPI model
the type of estimate; the “probabilistic”
estimate of P(Qllr~) is simply one component of theoverall estimate. The component estimates are then combined in a manner consistent withthe dependence relationships represented in the inference network to provide an estimate
Of P(lldi).

4.2

Comparison

withthe RPImodel

To further clarify the relationship between the inference network model and the probabilistic
model, we will compare the inference network model with Fuhr’s model for retrieval withprobabilistic indexing (RPI model) [Fuh89]. T o simplify the comparison, we will temporarily
adopt Fuhr’s notation. Letdm
X

represent a document in the collection,
be the binary vector (51,x2,. . . , z,) in which each Zi
corresponds to a document descriptor (representation

concept),

fk

represent the query, andR

represent the event that a document is judged relevant to a query.

All variables are binary valued. In this model, P(zi = Ildm) is interpreted as the probability
that a descriptor ri is a “correct” indexing of d,. Let X be the set of possible values for x,
where IX]*< 2”.
The network shown in Figure 3 corresponds to the probability distributionJ’(R,fk,sl,..-,%I,&)=

P(Rlfk,dm)=

P(Rffk, 21, . . . ,x,)P(qldm). . . %#mP(fdWm).

We will evaluate this expression for a given document and query so fk and d, are known

13
ACM SIGIR Forum

136

Vol. 51 No. 2, July 2017and the distribution

reduces toAssuming that the descriptors are assigned independently,
P(Xl471)=nthat isP(zilhn)r

l<i<n
--

the basic ranking expression for the network of Figure 3 isEquation 2 is equivalent to the basic ranking expression used by Fuhr [Fuh89, equation 91.
Equation 2 can be expanded to the product form

P(RIfk$dm)=P(RIfk)n (Fui-+s(l
l<i<n
-_

t

_uim))(3)

where= P(Si = l(R,fk)
qi = P(Zi = 1)
= P(Zi = IId*)*uim?%k(Strictly speaking, the network corresponding to equation 2 should have a single node x in
pIace of 21,. . . , z, since equation 2 makes no independence assumptions. Independence is,however, assumed in all derivations based on equation 2 so we have chosen to show it in
the network.)
Using the same notation and variables, the network of Figure 1 can be reduced to the
network of Figure 4. This inference network is described by the probability distribution
P(R,fk,n,.--,G,,&,)=

P(Rl4n)=P(R(fk)P(fk(x,,. . . ,x,)P(xlldm).

. . P(x,,ld,n)P(dm).

Comparing Figure 4 with Figure 3 we see that in the inference network model the query
does not appear as a separate prior (root) but is explicitly conditioned on the representation
concepts. Again, d,,, is given, so we haveJ’(Wm) = P(RlfdP(fkl%. . . ,z,)P(xlb&n).. .f’(znl&).
Applying

Bayes’ rule we get

14

ACM SIGIR Forum

137

Vol. 51 No. 2, July 2017

L

Figure 4: Example inference network
Assuming that the x; are distributed independently
ment of the 2; is independent of the query (5)P(Xl,.

. .,xn)=in documents (4) and that the assignn

p(xi>

(4)

n

p(xiifk)(5)

lli<_nP(~l,...,Glfk)

=

lli<n

we have
P(Rl&)=

P(Rifk)P(fk)

c
xfg

fl
l<i<n
--

Py$P(x;ldm).

The application of Bayes’ rule essentially inverts the network of Figure 4 to obtain theequivalent network shown in Figure 54. Note that the use of Bayes’ rule here is to allow us
to derive a closed-form ranking expression that can be compared with the RPI model. In
practice, we would use an estimate of P(fklq, . . . , x,) and would not invert the network.
‘While the networks in Figures 4 and 5 are equivalent in the sense that the computed probability
distributions are ihe same, Figure 5 does not lend itself to normal belief network updating procedures. In orderto produce the new P(z;lf~.,d,,,)link matrix and the new prior P(f,)
we must make use of the assumed
value of P(L).
In essence, when we invert the network we fold the prior probabilityof d, into the newlink matrix and extract a new prior for the query. This means that to test the effect of a change in P(L),we would have to recompute the link matrices at each z, and compute a new P(fk).
With the network in
Figure 4, we can change our assumed value for P(d,) without changing the probability information stored
at each node.

15

ACM SIGIR Forum

138

Vol. 51 No. 2, July 2017

Figure 5: Effect of inversion
Equation

6 reduces toIf we let
pik

=

p(zi

=

llfk)

Qi

=

P(,;

=

1)

Uim

=

P(Zi = lldm)

we get the ranking expression
Y(Rldm)=P(Alfk)P(fk)

n
l<i<n
-_

(Elii-

+ scl

I

-

Ui,,,))(7)

Equation 7 differs from equation 3 in that pik is conditioned only on the query and not on
R and the resulting probability is normalized by P(fk). The difference in conditioning forp;k arises because the network of Figure 4 implicitly assumes that x and R are conditionally independent given the query, that is, x cannot influence our assessment of relevance
except through its effect on the query. The network of Figure 3 assumes that x and fk
are independent, but not necessarily conditionally independent given R, that is, x and thequery can influence our assessment of relevance independently.
Under the assumption of
conditional independence
and the pik terms are identical. P(fk) is constant for a given query and does not affect the
ranking so, under the assumption of conditional independence, the rankings produced by
the two models are identical.
The networks in Figures 3 and 4 help to clarify the differences between the probabilistic
and inference network retrieval models. In the network of Figure 3, the query is modeled

16

ACM SIGIR Forum

139

Vol. 51 No. 2, July 2017

as a separate variable that is related to the possible document descriptions through thespecification of P(R(x, fk). Th e network of Figure 4 explicitly models the dependence ofthe query on the document representation and the dependence of relevance on the query.
Again, the network of Figure 4 asserts the independence of the document representation andrelevance given the query; the document representation cannot influence the probability of
relevance except through its influence on the query.
The principal difference between the two models, then, lies in the dependencies assumed.
While we have chosen Fuhr’s model as the basis for comparison, network forms could be developed for the many other probabilistic formulations. The chief advantage of the inference
network model is that it allows complex dependencies to be represented in an easily understood form and it allows networks containing these dependencies to be evaluated without
development of a closed form expression that captures these dependencies.
4.3

BooleanretrievalUsing the canonical link matrix forms of section 3.4 we can implement Boolean retrieval asfollows. For clarity, we assume that the query and representation vocabularies are identicalso we can omit query concepts from the network. We also assume that when one document
is instantiated all remaining documents are set to false.
1. Use a canonical or matrix at each representation node. When a document is instantiated, all representation concepts to which it has been attached will have bel(ti) = 1.
All remaining representation concepts have bel(rj) = 0.
2. Build an expression tree for the query. The root of the tree is the query and all arcs
in the tree are directed toward the root. The leaves of this tree will be representation
concepts and the interior nodes will correspond to expression operators. At each
operator node use the canonical link matrix form for that operator. Attach this tree
to the document network.
3. Using the evaluation procedure described in section 3.3, instantiate each document inturn and record the belief in the query node. Any document for which bel(Q) = 1
satisfies the query, any node for which bel(Q) < 1 does not.
Under the assumptions above and using binary indexing, bel(Q) can only have values Cl or
1 and the inference network simulates a conventional Boolean system exactly. If we relax
the requirement that all uninstantiateddocuments be set to 0, then only documents forwhich bel(Q) = 1 satisfy the query and all remaining documents have a small but non-zero

WQ).

The same probabilistic interpretationof the Boolean operators applies equally well toweighted indexing. Using the approach described in section 3.4 we can incorporate indexing
weights by replacing the or link matrix at the representation concept nodes with a weightedsum matrix incorporating the appropriate tf and idf weights. In this case, when a document
is instantiated, all representation nodes to which it is attached take on the tf.idf weight forthat term/document
pair and all remaining representation nodes take on be1 = 0. These
weights are then combined using the closed-form expressions of section 3.4. In short, the

ACM SIGIR Forum

140

Vol. 51 No. 2, July 2017

tf.icIf weights are interpreted as probabilities and are combined using the normal rules fornegation and for disjunctive or conjunctive combination of sets in an event space. As aresult, the inference network model provides a natural interpretation of Boolean operationsin probabilistic terms and of the meaning of indexing weights.
The binary nature of the retrieval decision in Boolean systems is frequently cited as aof the probabilisticdrawback [Cro86,SM83,Sd88].
W e can relax our strict interpretation
semantics of the Boolean operators by allowing the number of parents=true to influence
our belief. For example, we can choose a value n 5 c 5 M and interpret the and operator
to mean

P(Q.,d = true]n parents = true)=

1

P(Q,,d = true]L parents = true)=

I-

P(Qand = true]no parents = true)=of’(Q,, = true]n parents = true)=P(Q,, = true(k parents = true)

=

1
k
;,

p(Qov = truelno parents = true)

=

0

5,

k

0 < IC< uand the or operator to mean

0 < k < uSince a node implementing the not operator has exactly one parent, its interpretationisunchanged. Under this interpretation, when c = 00 the operators have their normal Booleaninterpretation.
As c decreases, our belief in Q depends increasingly on the number of parents
that are true. When c = n the distinction between and and or has disappeared and thelink matrices for both operators are the same. The use of this parent weighting scheme isquite similar to the extended Boolean retrieval or p-norm model [Sa188,SM83]. The two
approaches are equivalent when c = n and p = 1 and when c = p = 00; the resulting
probability and similarity functions are monotonic for n < c < 00 and 1 < p < 00.
4.4

Estimating

the probabilities

Given the link matrix forms of section 3.4, we now consider the estimates required forthe basic model of Figure 1. The only roots in Figure 1 are the document nodes; theprior probability associated with these nodes is set to l/(collectionsize). Estimates are
required for five different node types: text, representation and query concepts, query, andinformation need.
Text nodes. Since text nodes are completely dependent upon the parent document
node, the estimate is straightforward.
Since there is a single parent, a matrix form can beused; li is true exactly when di is true so
L text =

1 0
(

01

1 *

This matrix form is the inverse of that used for not.

ACM SIGIR Forum

141

Vol. 51 No. 2, July 2017

Note that the distinction between document and text nodes is not required for the basicmodel and we often ignore text nodes for clarity. Text nodes are required if we support
sharing of text by documents and to support the extended model of section 5 which includes
citation links and document clustering. If we allow document nodes to share text nodes,
then an or matrix is appropriate, ti is true when any parent is instantiated.
Representation
concept nodes. Link matrix forms for representation concepts werediscussed in section 3.4. For binary indexing and unweighted terms an or-combination canbe used. For tj, idj, or tj.idj weights a weighted-sum link matrix is used.
Query concept nodes. As we have seen, previous indexing research can be incorporated directly in the document network. The query network, particularly the links between
representation and query concepts is less well understood. Here we are interested in estimating the probabilistic dependence of concepts mentioned in the user’s query upon the
representation concepts. Most current retrieval models view these two sets of concepts as
identical under the assumption that the user knows the set of representation concepts andcan formulate queries using the representation concepts directly. Under this assumption,
the same link matrix as for text nodes should be used.
Research suggests, however, that the mismatch between query and indexing vocabularies
may be a major cause of poor recall [FLGD87]. While our initial implementation is limited
to linking query concepts to “nearly” equivalent representation concepts using a weightedsum combination rule, it would appear that improved estimates of the dependence of query
concepts on representation concepts could markedly improve performance. Two areas ofresearch bear directly on improving the quality of these estimates: automatic thesaurus
construction and natural language research aimed at extracting concept descriptions fromquery text, identifying synonymous or related descriptions, and resolving ambiguity.
Query nodes. The dependence of query nodes on the query concepts is more straightforward. For Boolean queries we use the procedure described in section 4.3. For probabilistic
queries we use a weighted-sum matrix. In both cases we can adjust link matrix values if wehave information about the relative importance of the query concepts.
Informationneed. The information need can generally be expressed as a small numberof queries of different types (Boolean, m-of-n, probabilistic, natural language, . . .). Thesecan be combined using a weighted-sum link matrix with weights adjusted to reflect any user
judgments about the importance or completeness of the individual queries.
5

Extensions

to the

basic

model

The basic model described in section 3 is limited in at least two respects. First, we haveassumed that evidence about a variable establishes its value with certainty. Second, we
have represented only a limited number of dependencies between variables. In this section
we will see that these limitations can be removed.
5.1

Uncertain

evidence

The only use of evidence in the basic model is to assert that a document has been observed(d; = true). During query processing we assert each document true and rank documents

19

ACM SIGIR Forum

142

Vol. 51 No. 2, July 2017

Figure 6: Document clustering model
based on the probability that the information need is met. Evidence is attached to a node
a in a Bayesian network by creating a new evidence node b as a child of a. This new node bthen passes a likelihood vector (both components of a likelihood ratio) to a. Since evidence
is expressed in terms of likelihood we are not restricted to the values trtle and false but
need only specify the likelihood of a = true and a = false given the evidence summarized atb. Thus we can “partially”
instantiate nodes in the network when the evidence we have is
not sufficient to establish the value of a proposition with certainty. This uncertain evidence
can be used to model citation and document cluster information.
Documentclustering.
A variety of document clustering techniques have been developed for information retrieval [vR79]. Document clustering is generally used to finddocuments that are similar to a document that is believed relevant under the assumptionthat similar documents are related to the same queries. Our use of cluster information issomewhat different since we do not retrieve clusters, but we can incorporate cluster information by treating cluster membership as an additional source of evidence about document
content. In the fragment shown in Figure 6, document texts tl, t2, and t3 are indexedusing representation concepts ~1, r2, ~3, and ~4. Documents t2 and t3 have been identified as part of cluster cl; both texts are linked to a cluster node and the cluster node islinked to the representation concepts that define the cluster. The cluster node is similar
to a conventional cluster representative.
Documents tl and t2 are indexed by the same
representation concepts (rr and ‘2) and, if we assume equivalent conditional probabilities,
would be ranked equivalently in the absence of the cluster node. With the addition of thecluster node, however, a new representation concept (rs) is associated with t2 by virtue of
its cluster membership. Assuming that ta contributes positively to the belief in q, iz would
be ranked higher than tl. In practice, the links between documents and clusters are notrepresented in the network; evidence is attached to all clusters to which a document has
been assigned when that document is instantiated.

20

ACM SIGIR Forum

143

Vol. 51 No. 2, July 2017

Citationand nearest neighbor links. A variety of asymmetric relationships between
pairs of documents can also be represented. These relationships are similar to clusteringin that they use an assumed similarity between documents to expand the set-of representation concepts that can be plausibly associated with a text. They differ in that they areordered relations defined on pairs of documents rather than an unordered, set membership
relationship between documents and clusters.
One example of this kind of relationship is the nearest neighbor link in which a document
is linked to those documents judged to be most similar to the original. A second example isbased on citations occurring in the text. Citation links may be useful if the type of reference
can be determined to allow estimation of the probabilistic dependence between the nodes.
Again, these links are not explicitly represented in the network; evidence is attached to a
document’s nearest neighbors and citation partners when the document is instantiated.
5.2

Additional

dependencies

In the basic model, we assume that there are no dependencies between documents, between
texts, between representation concepts, between query concepts, or between queries. While
independence assumptions like these are common in retrieval models, it is widely recognizedthat the assumptions are unrealistic.
In addition to the document cluster and citation
information which is modeled as evidence, we would like to explicitly represent the term
dependencies embodied in conventional term clusters and thesauri.
The basic mechanism for representing these dependencies is unchanged, we identify theset of nodes upon which a given node depends and characterize the probability associatedwith each node conditioned on its immediate parents. When adding these new links, however, we must be careful to preserve the acyclic nature of the inference network. Bayesianinference networks cannot represent cyclic dependencies, in effect evidence attached to any
node in the cycle would continually propagate through the network and repeatedly reinforce
the original node. In the basic model, no cycles are possible since nodes are only linked tonode types that are lower in the DAG. The introduction of these new dependencies makes
cycles possible.
Inference networks provide a natural mechanism for representing dependencies between
representation concepts and between query concepts. Several automatic clustering techniques produce structures that can be used in an inference network. For example, dependence trees or Chow trees [vR79,Pea88] contain exactly the term dependence information
required for an inference network in a form that is guaranteed to be cycle-free,
These networks can also be used to represent probabilistic thesaurus relationships. These
relationships extend those of a conventional thesaurus by including conditional probability
information.
For example, a conventional thesaurus might list “house pet” as a broader
term for “dog” and “cat”; the network representation will include a specification of theprobability’ that “house pet” should be assigned given a document containing Udog” or“cat” in isolation, neither term, or both terms.
Synonyms, related terms, and broader terms can be represented by creating a new node
to represent the synonym or related term class or the broader term and adding the newnode as a child to the relevant representation concept nodes. We will generally prefer to21

ACM SIGIR Forum

144

Vol. 51 No. 2, July 2017add these nodes as part of the query network since their presence in the document network
would represent a computational burden even when not used in a query. Although generally
less useful, narrower term relationships can also be represented.
6Conclusion

The retrieval model presented here provides a framework within which to integrate several
document representations and search strategies. We are currently refining the model andconducting experiments to compare search performance based on this model with that ofother models and to compare performance of potential representations and search strategies.
Acknowledgments
This work was supported in part by OCLC Online Computer Library Center, by the Air
Force Office of Scientific Research under contract 90-0110, and by NSF Grant IRI-8814790.
References(CH79]

W. Bruce Croft and D. J. Harper. Using probabilistic models of document
retrieval without relevance information. Journal of Documentation, 35:285-295,
1979.

[Che88]Peter Cheeseman. An inquiry into computer understanding. Computational
Intelligence, 4:58-66, February 1988. Article is part of a debate between logic
and probability schools in AI.

[CK87]Paul R. Cohen and Rick Kjeldsen. Information retrieval by constrained spreading activation in semantic networks. Information Processing and Management,
23(2):255-268, 1987.

[Coh85]

Paul R. Cohen. Heuristic Reasoning About Uncertainty:
gence Approach. Pitman, Boston, MA, 1985.

[Coo71]W. S. Cooper. A definition of relevance for information retrieval. Information
Storage and Retrieval, 7:19-37, 1971.

[Cro80]

W. Bruce Croft. A model of cluster searching based on classification. Znformalion Systems, 5:189-195, 1980.

[Cro86]

W. Bruce Croft. Boolean queries and term dependencies in probabilistic retrieval
models. Journal of the American Society for Information Science, 37(2):71-77,
1986.

[Cro87]

W. Bruce Croft. Approaches to intelligent information retrieval. Information
Processing and Management, 23(4):249-254,

An Artificial

Intelli-

1987.

22

ACM SIGIR Forum

145

Vol. 51 No. 2, July 2017

[CT871

W. Bruce Croft and Roger II. Thompson. 13R: A new approach to the design of
document retrieval systems. Journal of the American Society for Information
Science, 38(6):38%404, November 1987.

[ CT891

W. Bruce Croft and Howard Turtle. A retrieval model incorporating
links. In Bypertest ‘89 Proceedings, pages 213-224, 1989.

[Dem68]A. P. Dempster. A generalization of Bayesian inference.
Statistical Society B, 30:205-247, 1968.

PM’91

John Doyle. A truth maintenance system. Artificial
1979.

[FLGD87]

G. W. Furnas, T. K. Landauer, L. M. Gomez, and S. T. Dumais. The vocabulary problem in human-system communication.
Communications of the ACM,
30(11):964-971, November 1987.

[FNL88]

Edward A. Fox, Gary L. Nunn, and Whay C. Lee. Coefficients for combining
concept classes in a collection. In Proceedings of the Eleventh Annual Intemational ACM SIGIR Conference on Research and Development in Information
Retrieval, pages 291-308, New York, NY, 1988. ACM.

[Fuh89]

Norbert Fuhr. Models for retrieval with probabilistic
Processing and Management, 25( 1):55-72, 1989.

[KL86]

Laveen N. Kanal and John F. Lemmer, editors.
ligence. North-Holland,
Amsterdam, 1986.

[KMT+82]

J. Katzer, M. J. McGilI, J. A. Tessier, W. Frakes, and P. DasGupta. A studyof the overlap among document representations. Information
Technology: Research and Development, 1:261-274, 1982.

[LK88]

John F. Lemmer and Laveen N. Kanal, editors.
ligence 2. North-Holland,
Amsterdam, 1988.

[LS88]

S. L. Lauritzen and D. J. Spiegelhalter. Local computations with probabilities
on graphical structures and their application to expert systems. Journal of theRoyal Statistical Society B, 50(2):157-224, 1988.

[MK60]

M. E. Maron and J. L. Kuhns. On relevance, probabilstic
mation retrieval. Journal of the ACM, 7:216-244, 1960.

[MKN79]JournalIntelligence,

hypertextof the Royal

12(3):231-272,

indexing.

Uncertainty

Uncertainty

Informationin Artificial

in Artificial

indexing

Intel-

Intel-and infor-

Michael McGill, Mathew Koll, and Terry Noreault. An evaluation of factors. affecting document ranking by information retrieval systems. Technical report,
Syracuse University, School of Information Studies, 1979. Funded under NSFJST-78-10454.

[Nil861

Nils J. Nilsson. Probabilistic

logic. Artificial

Intelligence,

28( 1):71-87, 1986.

23

ACM SIGIR Forum

146

Vol. 51 No. 2, July 2017

[OPC86]

Robert N. Oddy, Ruth A. Palmquist, and Margaret A. Crawford. Representation of anomalous states of knowledge in information retrieval. In Pmeedingsof the 1986 ASIS Annual Conference, pages 248-254,1986.

[Pea881

Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, 1988.

[Rob771

S. E. Robertson. The probability ranking principle in IR. Journal
tation, 33(4):294-304, December 1977.

[Sal881

Gerard Salton. A simple biueprint for automatic boolean query processing.
Information Processing and Management, 24(3):26%280, 1988.

[Sha76]

Glen Shafer. A Mathematical
1976.

[SM83]

Gerard Salton and Michael J. McGill.
Retrieval. McGraw-Hill,
1983.

[Sti75]K. H. Stirling. The effect of document ranking on retrieval system performance:
A search for an optimal ranking rule. Proceedings of the American Society for
Information Science, 12:105-106, 1975.

[TC89]

Roger H. Thompson and W. Bruce Croft. Support for browsing in an intelligent
text retrieval system. International
Journal of Man-Machine Studies, 30:639668, 1989.

[TS85]

Richard M. Tong and Daniel Shapiro. Experimental
tainty in a rule-based system for information retrieval.
Man-Machine Studies, 22:265-282, 1985.

[vR79]

C. J. van Rijsbergen.

Butterworths,

1979.

[vR86]

C. J. van Rijsbergen. A non-classical logic for information
Journal, 29(6):481-485, 1986.

retrieval.

(Wi173]Patrick Wilson. Situational
471, 1973.

[Zad83]

Lotfi A. Zadeh. The role of fuzzy logic in the management of uncertainty
expert systems. Fuzzy Sets and Systems, 11:199-228, 1983.

Theory of Evidence. Princeton

Information

Introduction

Retrieual.

relevance. Informationof Documen-

University

Press,

to Modem information

investigations of uncerInternational
Journal ofComputer

Storage and Retrieval, 9:457in

24

ACM SIGIR Forum

147

Vol. 51 No. 2, July 2017