Document Language Models, Query Models, andRisk Minimization for Information RetrievalJohn Lafferty

Chengxiang Zhai

School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213

School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213

ABSTRACTmodel, achieving effects similar to query expansion in more
standard approaches to IR. The relative simplicity and effectiveness of the language modeling approach, together withthe fact that it leverages statistical methods that have beendeveloped in speech recognition and other areas, makes it an
attractive framework in which to develop new text retrieval
methodology.
In this paper we motivate the language modeling approachfrom a general probabilistic retrieval framework based onrisk minimization. This framework not only covers the classical probabilistic retrieval models as special cases, but alsosuggests an extension of the existing language modeling approach to retrieval that involves estimating both document
language models and query language models and comparing the models using the Kullback-Leibler divergence. In
the case where the query language model is concentrated on
the actual query terms, this reduces to the ranking method
employed by Ponte and Croft [17] and others. We also introduce a novel method for estimating an expanded query language model, which may assign probability to words that are
not in the original query. The essence of the new method is a
Markov chain word translation model that can be computed
based on a set of documents. The Markov chain method is
a very general method for expanding either a query modelor a document model. As a translation model, it addresses
several basic shortcomings of the translation models usedby Berger and Lafferty [1], as described in Section 4. The
query models explored in this paper are quite simple, but ingeneral, the role of the query model is to incorporate knowledge of the user and the context of an information need into
the retrieval model.
The paper is organized as follows. In Section 2 we discuss the language modeling approach to IR, and briefly review previous work in this direction. In Section 3 we present
the risk minimization retrieval framework and our extension
to the language modeling approach that incorporates bothquery and document language models. Section 4 presents
the idea of using Markov chains on a documents and words
to expand document and query models, and gives several
examples. This technique requires various collection statistics to be calculated, and we explain in Section 5 how thesecan be calculated at index time. A series of experiments
to evaluate these methods is presented in Section 6, where
we attempt to compare directly to state-of-the art ranking
functions and weighting schemes. Conclusions and the contributions of this work are summarized in Section 8.

We present a framework for information retrieval that combines document models and query models using a probabilistic ranking function based on Bayesian decision theory.
The framework suggests an operational retrieval model that
extends recent developments in the language modeling approach to information retrieval. A language model for eachdocument is estimated, as well as a language model for eachquery, and the retrieval problem is cast in terms of risk minimization. The query language model can be exploited tomodel user preferences, the context of a query, synonomy
and word senses. While recent work has incorporated wordtranslation models for this purpose, we introduce a new
method using Markov chains defined on a set of documents
to estimate the query models. The Markov chain method
has connections to algorithms from link analysis and social
networks. The new approach is evaluated on TREC collections and compared to the basic language modeling approach and vector space models together with query expansion using Rocchio. Significant improvements are obtained
over standard query expansion methods for strong baseline
TF-IDF systems, with the greatest improvements attained
for short queries on Web data.

1.

INTRODUCTION

The language modeling approach to information retrieval
has recently been proposed as a new alternative to traditional vector space models and other probabilistic models.
In the use of language modeling by Ponte and Croft [17],a unigram language model is estimated for each document,
and the likelihood of the query according to this model isused to score the document for ranking. Miller et al. [15]smooth the document language model with a backgroundmodel using hidden Markov model techniques, and demonstrate good performance on TREC benchmarks. Berger andLafferty [1] use methods from statistical machine translation to incorporate synonomy into the document language
Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
SIGIR’01, September 9-12, 2001, New Orleans, Louisiana, USA
Copyright 2001 ACM 1-58113-331-6/01/0009 ...$5.00.

ACM SIGIR Forum251

Vol. 51 No. 2, July 2017

2.

THE LANGUAGE MODELINGAPPROACHof relevance judgments will be available to estimate them on
actual user data. Because of this, Berger and Lafferty generate an artificial collection of “synthetic” data for training.
Second, the application of translation models to ranking isinefficient, as the model involves a sum over all terms in the
document. Third, the translation probabilities are contextindependent, and are therefore unable to directly incorporate word-sense information and context into the language
models.
In the following section we present a formal retrieval framework based on risk minimization and derive an extension of
the language modeling approach just described, which may
ultimately be better suited to semantic smoothing to model
the user’s information need. In Section 4 we then present
a technique for expanding document and query models that
addresses some of the shortcomings of the translation models as used in [1].

In the language modeling approach to information retrieval, a multinomial model p(w | d) over terms is estimatedfor each document d in the collection C to be indexed andsearched. This model is used to assign a likelihood to auser’s query q = (q1 , q2 , . . . , qm ). In the simplest case, eachquery term is assumed to be independent of the other query
terms, so that the query likelihood is given by p (q | d) =m
i=1 p (qi | d). After the specification of a document priorp (d), the a posteriori probability of a document is given byQ

p (d | q) ∝ p (q | d) p (d)and is used to rank the documents in the collection C.
Just as in the use of language models for speech recognition, language models for information retrieval must be“smoothed,” so that non-zero probability can be assigned toquery terms that do not appear in a given document. One of
the simplest ways in which a document language model canbe smoothed is by linear interpolation with a backgroundcollection model p (w | C):p λ (w | d) = λ p (w | d) + (1 − λ) p (w | C)

3. A RISK MINIMIZATION RETRIEVALFRAMEWORKIn an interactive retrieval system, the basic action of thesystem can be regarded as presenting a document or a sequence of documents to the user. Intuitively, the choice of
which documents to present should be based on some notion of utility. In this section we formalize this intuition bypresenting a framework for the retrieval process based on
Bayesian decision theory.
We view a query as being the output of some probabilistic
process associated with the user U, and similarly, we viewa document as being the output of some probabilistic process associated with an author or document source S. A
query (document) is the result of choosing a model, andthen generating the query (document) using that model. A
set of documents is the result of generating each document
independently, possibly from a different model. (The independence assumption is not essential, and is made here
only to simplify the presentation.) The query model could,
in principle, encode detailed knowledge about a user’s information need and the context in which they make their query.
Similarly, the document model could encode complex information about a document and its source or author.
More formally, let θQ denote the parameters of a querymodel, and let θD denote the parameters of a document
model. A user U generates a query by first selecting θQ ,according to a distribution p (θQ | U). Using this model, aquery q is then generated with probability p (q | θQ ). Similarly, the source selects a document model θD according to a
distribution p (θD | S), and then uses this model to generate
a document d according to p (d | θD ). Thus, we have Markov
chains U → θQ → q and S → θD → d.
If C = {d1 , d2 , . . . , dk } is a collection of documents obtained from source S, we denote by θi the model that generates document di . Assume now that for each document di ,there is a hidden binary relevance variable Ri that dependson θQ and θi according to p (Ri | θQ , θi ), which is interpreted
as representing the true relevance status of di with respect
to q (1 for relevant and 0 for non-relevant). The randomvariable Ri is observed when we have the user’s relevancejudgment on di , and is unobserved otherwise. In the following presentation, we will assume that Ri is not observed.

(1)

Miller et al. [15] view this smoothed model as coming from a
simple 2-state hidden Markov model, and train the parameter λ using maximum likelihood estimation. One of themain effects of this type of smoothing is robust estimationof common, content-free words that are typically treated as“stop words” in many IR systems.
A potentially more significant and effective kind of smoothing is what may be referred to as semantic smoothing, wheresynonyms and word sense information is incorporated into
the models. With proper semantic smoothing, a documentthat contains the term w = automobile may be retrieved
to answer a query that includes the term q = car, even if
this query term is not present in the document. Semantic smoothing effects are achieved in more standard approaches to IR using query expansion and relevance andpseudo-relevance feedback techniques. The development ofa well-motivated framework for semantic smoothing is oneof the important unresolved problems in the language modeling approach.
In order to incorporate a kind of semantic smoothing into
the language modeling approach, Berger and Lafferty [1]estimate translation models t (q | w) for mapping a document
term w to a query term q. Using translation models, thedocument-to-query model becomesY X t (q | w) p(w | d)mp (q | d) =

i

i=1 w

Berger and Lafferty [1] report significant improvements overthe baseline language modeling approach through the use oftranslation models.
One of the primary motivations of the present paper is toaddress what we view as several difficulties with the translation model approach to semantic smoothing in the language
modeling framework. First, the translation models t (q | w)
must be estimated from training data. As the models arehighly lexical, it is unlikely that a sufficiently large collection

ACM SIGIR Forum

252

Vol. 51 No. 2, July 2017

Model selection

Query generationUp(q | θQ )will generally force us to make explicit the assumed ranking
criterion and notion of relevance.

R

3.1 Relevance-based Loss FunctionsqθQp(θQ | U )p(R | θQ , θD )Model selection

We now consider the special case where the loss function
L depends only on the relevance variable R; in this case we
can simplify the risk formula and obtain a general ranking
criterion based on the “probability of relevance.”
Let L be definedDoc generation

S

d

θD
p(d | θD )p(θD | S)(

L(θQ , θD , R) =Figure 1: Generative models for queries, documents,
and relevance.

R(d; q)This means that the risk minimization ranking criterion is
now equivalent to ranking based on p (R = 1 | q, d), i.e., theprobability of relevance given q and d. This is the basis of
all the classical probabilistic retrieval models. For example,
the derivation of the binary independent model based onp (R = 1 | q, d) can be found in [18].
Interestingly, the model implicitly used in the language
modeling approach can also be derived based on the probability of relevance p (R = 1 | q, d). See [14] for details of thisderivation. This shows that both the classical probabilistic
retrieval model and the language modeling approach to retrieval are special cases of the risk minimization framework.

L(a, θ) p (θ | U, q, S, C) dθΘwhere the posterior distribution is given byp (θQ | q, U)kY

p (θi | di , S) p (Ri | θQ , θi )3.2 Distance-based Loss Functions

i=1

We now consider another special case, where the loss function L is assumed to depend only on θQ and θD ; thus, given
θQ and θD , it does not depend on R. We will see that this allows us to derive a general probabilistic distance/similarity
retrieval model.
Formally, let L be proportional to a distance or similarity
measure ∆ between θQ and θD , i.e.,

The Bayesian decision rule is then to present the document
list a∗ having the least expected risk:a∗ = arg min R(a | U, q, S, C)a

Now, if we assume that a possible action is to return asingle document a = di , and that the loss function only
depends on θQ , θi , and Ri , the risk can be simplified to
def

X Z Z

R(di ; q) = R(a = di | U, q, S, C) =R∈{0,1}

ΘQ

L(θQ , θD , R) = c∆(θQ , θD )(2)

where c is a cost constant. Intuitively, if the models θ, θ′ arecloser/similar, then ∆(θ, θ′ ) should be small. With this loss
function, we have

L(θQ , θD , R) ×

Z Z

ΘD

p (θQ | q, U) p (θD | di , S) p (R | θQ , θD ) dθD dθQ∆(θQ , θD ) p (θQ | q, U) p (θD | d, S)dθD dθQ

R(d; q) ∝θQ

Clearly, if the whole collection C is presented by making
k sequential decisions, the result will be a list of documents
ranked in ascending order of R(di , q). Equation 2 is ourbasic retrieval formula based on risk minimization.
Note that the independence assumption on the loss function does not usually hold in practice. Indeed, if we wantto account for the similarity or dissimilarity between the
documents in the returned list (consider, for example, themaximum marginal relevance ranking criterion proposed in[6]), such a loss function will not be appropriate. Here we
make this assumption mainly for mathematical convenience.
We have deliberately left the loss function unspecified inorder to achieve generality. We will be able to show thatmany existing operational retrieval models are special casesof the risk minimization framework when a specific loss function is used. A complete specification of the loss function

ACM SIGIR Forum= c0 p (R = 0 | q, d) + c1 p (R = 1 | q, d)= c0 + (c1 − c0 ) p (R = 1 | q, d)Z

p (θ | U, q, S, C) ∝if R = 0
if R = 1

where, c0 and c1 are two cost constants. Then we have

Note that because the query model θQ can encode detailed
knowledge about the user U, the distribution of this relevance variable is in general user-specific.
A possible action of the system corresponds to a list of
documents to return to the user who has issued query q. In
the general framework of Bayesian decision theory, to eachsuch action a there is associated a loss L(a, θ), which ingeneral depends upon all of the parameters of our model,θ ≡ (θQ , {θi }ki=1 , {Ri }ki=1 ). In this framework, the expectedrisk of action a is given by
R(a | U, q, S, C) =

c0
c1

θD

This means that the risk minimization ranking criterion
is now equivalent to ranking based on the expected model
distance. Rather than explicitly computing this distance,
we can approximate it by its value at the posterior mode:b b∝ ∆(θbq , θbd ) p (θd | d, S)

R(d; q) ∝where∆(θq , θd ) p (θd | d, S) p (θq | q, U)

b = arg max p (θQ | q, U)θθbd = arg max p (θD | d, S)
θq

Q

b

θD

Note that the factor p (θd | d, S) includes prior information
about the document, and in general must be included when253

Vol. 51 No. 2, July 2017

w0

comparing the risk for different documents. This is critical when incorporating query-independent link analysis, orother extrinsic knowledge about a document. But, if we further assume that p (θd | d, S) is the same for all d, so does
not affect ranking, we will have the following very general
distance-based (or equivalently, similarity-based) probabilistic model:

❆

b

b b
We can view the vector space model as a special case ofthis general similarity model, where θb and θb are simplydQ

X p (w | θb ) log p (w | θb ) + c
R(d; q) ∝ −

q

d

(3)

w

where cq is a constant that doesn’t depend on the document,
and so doesn’t affect the retrieval performance.
According to this risk formula, the retrieval problem isessentially that of estimating θq and θd . If θq is just theempirical distribution of the query q = q1 q2 ...qm ; that is,

b

b

b

b

X
m

p (w | θq ) = −1
δ(w, qi )m i=1

where, δ is the indicator function, then we obtain

X

b

m

R(d; q) ∝ −1
log p (qi | θd ) + cqm i=1This is precisely the log-likelihood criterion that has been in
used in all work on the language modeling approach to date.
In the remainder of this paper we will develop new query
expansion methods to estimate a model θq , and demonstratethat this model performs significantly better than using theempirical distribution for θq when we use (3) as the risk.

b

4.

b

MARKOV CHAINS FOR EXPANDINGLANGUAGE MODELS❆❆

p(w2 | d1 )✁ p(d | w )❆11✁❆

p (di | w i ) =

❆ ✁

✁
✁

✁
✁

✕
✁

d1

Pp (wp (w| d |)d)p (dp (d))
idIn this section we describe a Markov chain method for
expanding language models for queries and documents, tobe used in the formal framework just described. We begin bymotivating the method in the context of translation models.
We then explain the basic method and provide examples. In
Section 7 we discuss the relationship between the Markov
chain method and other techniques such as link analysis.

i

i

(4)

i

where p (· | d) is the document language model, and wherep (d) is a prior distribution on documents. For example, withhypertext, p (d) might be the distribution calculated using
the “PageRank” scheme [4]. Having chosen a document di ,a new word wi+1 is sampled from it according to p (· | di ).

4.2 Matrix formulation

4.1 Markov chains on words and documents

The algorithm can be cleanly described and related toother techniques using matrix notation. Let N be the number of terms in the word vocabulary, and M the number of
documents in the collection. Let A be the N × M stochastic
matrix with entries Aw,d = p (d | w), where the probability

As noted in Section 2, the translation models of Berger
and Lafferty [1] can significantly improve retrieval performance, but must be estimated from training data. Since
the parameters are highly lexical, an enormous amount of

ACM SIGIR Forum❆b

In this case

q

❆ ✁

✁✕

training data would be required to estimate them. Because
the translation models are context-independent their ability
to handle word sense ambiguity is limited. Moreover, the useof translation models for documents incurs a severe price inthe time to score documents. The Markov chain method
helps to overcome these limitations of the translation model
paradigm.
Our goal is to estimate a query model θq . For this purpose, we will estimate a probability t (q | w) that a word w“translates” to the query term q. Imagine a user looking
to formulate a query for an information need, and suppose,fancifully, that the user has an index available for the text
collection to be searched. The user “surfs” the index in thefollowing random manner. First, a word w0 is chosen. Next,
the index is consulted, and a document d0 containing thatword is chosen. This choice will be influenced by the numberof times the word appears in d0 , and might be also affectedby extrinsic data about the document, such as information
about its author. From that document, a new word w1 issampled, a new document containing w1 is chosen, and theprocess continues in this manner. After each step, there issome chance the user will stop browsing, as the topics of the
documents drift further from the information need.
We now describe the random walk more precisely. The
walk begins by choosing a word w0 with probability p (w0 | U).
At the i-th step, the user has selected word wi . The user
continues the random walk with probability α, generating a
new document and word. With probability 1 − α, the walkstops with word wi . If the walk continues, then a document
di is sampled from the inverse list for wi , according to theposterior probabilityp (w | θD )

w

❆
❆

✁
✁

Figure 2: The Markov chain alternates between
words and documents. For a given document, aword is selected according to the document language
model. For a given word, a document is selected according to the posterior probability.

X p (w | θ ) log p (w | θ )Qp(w1 | d0 )w2

d0term vector parameters estimated heuristically and the distance function is the cosine or inner product measure.
We now consider a specific similarity model as an interesting special case, where θQ and θD are the parameters ofunigram language models (i.e., p(· | θ) is a distribution overa fixed word vocabulary), and the similarity measure is the
Kullback-Leibler divergence∆(θQ , θD ) =❆❆p(d0 | w0 )R(d; q) ∝ ∆(θd , θq )

q

w1

254

Vol. 51 No. 2, July 2017

one. Words with very high p (d | w) tend to be rare and specialized, and not sufficiently general to be useful to improve
the language models. However, the prior p (w | U) acts toselect the more useful and frequent words having high IDF.
At the same time, this prior gives a probabilistic mechanism
for incorporating stop-word lists, or other extrinsic knowledge about the retrieval and query generation process. Thus,
even the one-step chain captures many of the desirable features of term weighting schemes in a probabilistic model.

is calculated as in equation (4). Also, let B be the M × N
stochastic matrix with entries Bd,w = p (w | d) given by the
document language models. Finally, let C be the N × N
stochastic matrix C = A B.
The probability that the chain stops after k steps withword wk = q is given byk(1 − α) αk Cw,qkis the (w, q)-entry of the matrix C k . Therefore,
where Cw,q
the overall probability of generating a word q is given byt α (q | w)

= (1 − α) I + α C + · · · αk C k + · · ·4.4 Incorporating feedbackBecause the Markov chain translation probabilities t(q | w)
generate the query, the resulting expansion model p(w | q)
is fairly general. If query terms have multiple senses, a mixture of these senses may be present in the expanded model(See Figure 3). For semantic smoothing, a more contextdependent model that takes into account the relationshipbetween query terms may be desirable. One way to accomplish this is through a pseudo-feedback mechanism. Supposethat a set of documents D(q) is known (or assumed) to be
relevant to a query q. We can condition the Markov chain topass through this set. For example, in the one-step versionof the random walk, we computew,q= (1 − α) (I − α C)−1w,q
Note that the matrix inverse (I − α C)−1 exists since, as astochastic matrix, α−1 > 1 cannot be an eigenvalue of C.
We define this to be the translation probability of mapping
w to q.
In the same way, we can calculate the probability that theuser stops with document d asht α (d | w)

I + α C + · · · αk C k + · · · A= (1 − α)




i
w,d

= (1 − α) (I − α C)−1 A w,dp (w | q, D(q)) ∝ p (w)While the matrices A and B are sparse, so that the matrix
product C = A B can be computed efficiently, C k quickly
becomes dense as k increases, and the powers cannot becomputed efficiently. However, as k increases, the “topic”
wanders from the initial term w0 , as the probability quickly
spreads out over all terms. Thus, intuitively, the first few
steps of the chain are most important for retrieval purposes.

In this way the expanded language model may be more “semantically coherent,” capturing the topic implicit in the setof documents D(q) rather than representing words related
to the query terms qi in general. An example of this isshown in Figure 3. In Section 6 we report on experimentson TREC data that clearly demonstrate how this method
can improve retrieval performance.

Suppose that q = (q1 , q2 , . . . , qm ) is a query that we wish
to expand. In our framework, this means that we estimate a language model p (w | θbq ). Using the Markov chain
method, this is done by calculating the posterior probabilityof words, according to the translation model for generating
the query and a prior distribution on initial terms selectedby the user. Thus, assuming the query terms are generated
independently,mX

5. INDEXING SCHEMES
Calculation of the Markov chain probabilities on inverted
indices manipulates document language models p (w | d) andtheir posterior probabilities p (d | w). Computing these probabilities at retrieval time can be very expensive, but can bemade more efficient by calculation of various statistics atindex time, as discussed briefly in this section. This sheds
further light on the role of document priors.
Standard indexing schemes store, for each index term w,
a list of document indices in which the term appears, d1 →
d2 → . . . → dn(w) . For information retrieval based on language modeling, we require in addition the number of times
the term appears in the document, and thus store a list
(d1 , c(w, d1 )) → (d2 , c(w, d2 )) → · · · → (dn(w) , c(w, dn(w) )).
To normalize the language probabilities, atPindex time wecompute the total document count c(d) = w c(w, d), andstore this in a document array, together with a document
prior p (d).
In our implementation, we make two passes through the
corpus. In the first pass a term vocabulary, document vocabulary, and document counts c(d) are tabulated. In thesecond pass, the inverted lists and word marginals p (w) arecomputed. Both the word-document and document-wordlists are compressed using the γ-method [20].
ToP
normalize the posterior probabilities, we must calculated p(w | d) p(d). Using the maximum likelihood lan-t α (qi | w) p (w | U)

i=1

A document d can be expanded using the Markov chain ina similar way:p (w | θbd ) ∝ t α (d | w) p (w | U)
To understand how this method should be expected to work,
it helps to consider running the chain for only one step. The
probability of generating a query term
q starting from an
P iinitial word w is equal to p (w | U) d p (qi | d) p (d | w) inthis case. The effect of the probability p (d | w) is similar to
IDF in traditional retrieval methods, since this probability
will be high if the word w appears in only a few documents.
In particular, function words will typically appear in a verylarge number of documents, so p (d | w) will tend to be verysmall for such words. At the other end of the spectrum, if
w appears only in the document d, this probability will be

ACM SIGIR Forump (d | w) p (q | d)d∈D(q)

4.3 Expanding query and document modelsp (w | θbq ) ∝X

255

Vol. 51 No. 2, July 2017wp(w | q)
virus
0.275
ebola
0.197
hoax
0.051
viruses0.034
outbreak
0.034
fever
0.033
disease0.024
haemorrhagic
0.023
gabon
0.022
infected
0.019
aids
0.016
security
0.014
monkeys
0.013
hiv
0.011
zaire
0.011
q = ebola virus (Web)wp(w | q)
star
0.361
wars
0.217
rpg
0.058
trek
0.033
starwars
0.032
movie
0.023
episode0.020
movies
0.015
war
0.014
character
0.013
tv
0.013
film
0.012
fan
0.012
reviews
0.012
jedi
0.008
q = star wars (Web)wp(w | q)
star
0.192
wars
0.137
soviet0.025
weapons
0.023
photo
0.020
army
0.020
armed
0.020
film
0.018
show
0.018
nations
0.017
strategic
0.017
tv
0.017
sunday
0.016
bush
0.014
series0.013
q = star wars (TREC)w
p(w | q)
star
0.170
wars
0.161
senate0.069
strategic
0.050
spending
0.045
initiative
0.039
funding
0.036
vote
0.036
missile0.033
billion0.033
weapons
0.031
cheney
0.030
space
0.028
voted
0.021
missiles
0.020
q = star wars (TREC)
with feedback

Figure 3: Sample query model probabilities using the Markov chain method. As seen in the third table, theprobabilities can be fairly general and include a mixture of topics. Using the feedback approach, conditioning
the chain on a document set obtained in a first pass, the query probabilities become more specialized, as seenin the fourth table.

Pc(w,d)
guage model, this is given by p (w) =d c(d) p(d).
The choice of prior affects the indexing. With a uniform
1
document prior p (d) = |C|, where |C| is the number of documents, we store

p (w) =1
|C|

the Porter stemmer. However, no stopword list was used, inorder to test the robustness of our modeling techniques.

6.1 Effect of the query modelX c(w, d)d

The query model obtained using the Markov chain for
expansion is expected to perform better than the simple
language model predicting the query, as in the Ponte-Croft
work. In order to test this, we compared the retrieval performance of the original maximum likelihood query modelwith that of the query translation model on all three collections. The results are shown in Table 1. The figures foreach model use the best choice of the document smoothing
parameter λ in equation (1), as determined by a simple line
search. In addition to non-interpolated average precision,
which we consider to be the main performance measure, we
include recall at 1,000 documents and initial precision, i.e.,interpolated precision at 0% recall.
Compared with the simple query model, the basic querytranslation model improves average precision and recall significantly and consistently across all three collections. However, using the Markov chain with a seed set of 50 documents, similar to pseudo-feedback, as described in Section 4.4, gives a much greater improvement. For these experiments we use α = 12 and run the Markov chain for only
two steps. The precision-recall curves are shown in Figure 4
for all six runs. In Figure 5, we compare the precision/recallof the basic query model and the expanded model at different settings of the document smoothing parameter λ. The
figures clearly show that the query translation model is better than the simple query model for all settings of λ, andthat the improvement is fairly insensitive to the choice of
this parameter.

c(d)If one chooses a (rather unmotivated) prior where a document’s probability is proportional to its total count c(d) (soa user browses by favoring long documents), then this leadsc(w)to p (w) =, which is simply the corpus unigramw c(w)
model.
Note that in our framework the prior information about adocument enters in two places—in the Markov chain analysis of translation models, and in calculating the risk. We
expect that significant improvements in query models can beobtained by basing the document prior on link-analysis or
higher-level knowledge about the document collection; thisremains an interesting topic for further research.

P

6.

EXPERIMENTAL RESULTS

We evaluated the query model estimation methods described in the previous sections using three different TREC
testing collections: the AP collection on disk 1 (topics 1–50),
the TREC8 ad hoc task collection (topics 401–450 on disks
4&5 – CR), and the TREC8 web track collection (topics
401–450 on Web data). These data sets are representativeof different aspects of TREC. The first is one of the earliest collections used in TREC and has relatively complete
relevance judgments. The last two were selected because
they represent relatively large collections and several published results on them are available. The Web data was also
selected because of its unique document style.
When selecting queries, we set up our evaluation as an
approximation of real world retrieval. Since queries are typically short, we only used the titles of each TREC topic
description. The titles have an average length of 2.5 words,
and typically contain one to four words each. The document
collections were pre-indexed using the approach described in
Section 5. All documents and queries were tokenized using

ACM SIGIR Forum6.2 Query translation models vs. TF-IDF
The effect of query expansion using the Markov chaintranslation model should be compared with query expansion in more traditional retrieval models, such as the vector space model. For this purpose, we implemented a vector space model where the similarity is computed using thedot product and the TF formula is the well-known Okapi
TF [19]. While the Okapi TF is designed to be used in the256

Vol. 51 No. 2, July 2017Collection
AP89
AvgPr
InitPrRecallTREC8 AvgPr
InitPrRecallWEB
AvgPr
InitPrRecallSimple LM
0.188
0.515
1510/3261
0.241
0.620
2791/4728
0.244
0.607
1760/2279

Query Model
0.201
0.500
1745/3261
0.266
0.723
2913/4728
0.275
0.664
1848/2279

Improv.
+7%
−3%
+16%
+10%
+17%
+4%
+13%
+9%
+5%

QM w/ Pseudo
0.232
0.534
2019/3261
0.294
0.676
3368/4728
0.304
0.663
1910/2279

Improv.
+23%
+4%
+34%
+22%
+9%
+21%
+25%
+9%
+9%

Table 1: Comparison of the basic language modeling method with expanded query models. Column three
gives the performance using the Markov chain query translation model; column 5 shows the effect of including
an initial document set (pseudo-feedback) to condition the Markov chain.
Collection
AP89
AvgPr
InitPrRecallTREC8 AvgPr
InitPrRecallWEB
AvgPr
InitPrRecall

TF-IDF+Rocchio
0.230
0.492
2082/3261
0.256
0.637
3154/4728
0.226
0.559
1729/2279

Query Model
0.201
0.500
1745/3261
0.266
0.723
2913/4728
0.275
0.664
1848/2279

Improv.
−13%
+2%
−16%
+4%
+14%
−8%
+22%
+19%
+7%

QM w/ Pseudo
0.232
0.534
2019/3261
0.294
0.676
3368/4728
0.304
0.663
1910/2279

Improv.
+1%
+9%
−3%
+15%
+6%
+7%
+35%
+19%
+10%

Table 2: Comparison of TF-IDF with Rocchio to Markov chain query expansion in the language modelingframework.
the query translation model and the TF-IDF model varies
from collection to collection. Constraining the Markov chain
to use a selected set of documents, obtained during a first
retrieval pass, as described in Section 4, generally gives thebest performance. However, on AP89, the performance ofRocchio and the query translation model are virtually thesame. The greatest gain from the query translation model
comes on the Web data, where the query models achieve a
35% improvement over Rocchio. We note that, although we
use only the title queries, which are very short, our resultson both the TREC8 and Web data using query models arequite comparable to the official TREC submissions, which
use the full queries.

Effect of Query Translation: PR Curves
0.8

ap-non-expand
ap-expandtrec8-non-expand
trec8-expand
web-non-expand
web-expand

0.7

0.6

prec

0.5

0.4

0.3

0.2

0.1

0
0

0.2

0.4

0.6

0.8

7. RELATED WORK

1

recallThere is a large and rich literature on probabilistic models
in information retrieval, and it would not be possible to survey it here. The work presented in this paper is most closely
related to recent developments in the language modeling approach [17, 11, 15, 1]. Important precursors to the language
modeling approach include [3, 18, 8, 10, 21]. The framework based on risk minimization that we have introduced
is very natural and general. We are not aware of any directly comparable framework in the IR literature, althoughseveral early papers discuss indexing schemes designed to
optimize utility measures [16, 7, 2]. The approach that we
present differs significantly from this work in that the central components are probabilistic models of documents andqueries, combined using an explicit loss function according
to Bayesian decision theory. The formal model is meant to
explicitly represent the uncertainty inherent in our model of

Figure 4: Precision-recall curves for all three collections, comparing the simple language model to thequery translation model.

BM25 retrieval function, in practice, we have found thatusing it in the vector space model also tends to give very
good performance. For query expansion, we implemented
a simplified Rocchio, where we add only positive terms to
the query, controlled by three parameters: (1) the numberof documents for blind feedback, (2) the number of terms to
add, and (3) the relative coefficient of the added terms. We
varied these parameters among several values and chose thebest performing parameters for comparison.
It is interesting to see that the relative performance of

ACM SIGIR Forum

257

Vol. 51 No. 2, July 2017

Effect of Query Translation: Precision on Lambda
0.35

Query Translation vs. Rocchio: TREC8
0.8

ap-non-expand
ap-expandweb-non-expand
web-expand
trec8-non-expand
trec8-expand

0.3

trec8-trans-fb
trec8-Rocchio

0.7

0.6

0.5
prec

prec

0.25

0.2

0.4

0.3

0.2
0.15
0.1

0.1

0
0

0.2

0.4

0.6

0.8

1

0

0.2

0.4

lambdaEffect of Query Translation: Recall on Lambda
1

0.8

1

Query Translation vs. Rocchio: Web
0.8

ap-non-expand
ap-expandweb-non-expand
web-expand
trec8-non-expand
trec8-expand

0.9

0.6
recallweb-trans-fb
web-Rocchio

0.7

0.6
0.8
0.5
prec

recall

0.7
0.4

0.6
0.3
0.5
0.2
0.4

0.1

0.3

0
0

0.2

0.4

0.6

0.8

1

0

lambda

0.4

0.6

0.8

1

recallFigure 5: Effect of λ, the document smoothing parameter for linear interpolation. The results indicate that the improvement of the query translation
model over the simple query model is fairly insensitive to the choice of λ.

Figure 6: Precision-recall curves comparing TF-IDF
with Rocchio to the query translation models. The
curves for the two methods on AP89 are nearly thesame, and so are not shown.

b⊤ , so that Bbd,w = c(w, d). LSA computes
the transpose Ab Bb and Bb A,
bprojections onto eigenspaces of the matrices A
building a low-dimensional subspace to represent terms anddocuments. In our method, we work with the closely related matrices A and B. The matrix B is obtained fromb by normalizing the rows. However, the matrix of posteBb by normalizing therior probabilities A is obtained from A
rows only in the case of the rather unnatural document priorp (d) ∝ c(d). But the essential difference is that our methodinterprets the matrix (I − αAB)−1 probabilistically, rather
than using a vector space approach that projects onto subb B.
bspaces generated by the top eigenvectors of A
There is a closer connection to methods from link andcitation analysis. For example, Kleinberg’s “hubs and authorities” technique [13] uses an initial document set D(q)b encoding all outgoing links
for a query, defines the matrix B
b encoding all incoming links to D.
from D, and the matrix A
The “hub score” of a document is then defined in terms ofb Bb (ignoring somethe principal eigenvector of the matrix A

the user and collection, and is an attractive way in whichto think about query and document language models. Aninteresting direction for future work will be to go beyond
the use of a single document and query model (as in MAP
estimation).
The practical implementation of our new query expansion
technique involves using only a small number of steps of a
Markov chain on inverted indices. However, to compare thistechnique to previous work, it is best to imagine using thefull matrix analysis, which involves computing the matrix
inverse (I − αC)−1 , as described in Section 4. When viewed
in this way, there are interesting connections between theMarkov chain approach to building query models, link analysis methods, theory of social networks, and latent semantic
indexing.
Methods based on latent semantic analysis (LSA) [9] workwith the singular value decomposition of the word-documentb having entries Abw,d = c(w, d). Let Bb denotematrix A

ACM SIGIR Forum

0.2

258

Vol. 51 No. 2, July 2017

REFERENCES

details involving normalization). To cast this in terms of
our query expansion method, forward links are replaced bydocument word indices, with language model probabilitiesp (w | d) = Bd,w , and incoming links are replaced by inverted
file indices, with posterior probabilities p (d | w) = Aw,d .
Use of the principal eigenvector of the matrix AB could
give an excellent method for query expansion.
Instead, we have chosen to use the Markov chain leading
to the matrix (I − αAB)−1 , which we believe gives greater
flexibility, as well as numerical stability through smoothing. Intuitively, the first iterations of the walk are mostimportant, and they are emphasized using the parameter α.
The use of this matrix is related to research on social networks carried out nearly 50 years ago; an excellent discussionof these methods is given by Kleinberg [13]. To estimate
the “standing” of an individual in a social network, Katz[12] uses a matrix C where Ci,j is the strength of an “endorsement” of individual j by individual i, and defines thestanding of an individual j as the j-th column of the matrix (I − αC)−1 − I. Very similar measures are defined by
Hubbel [5].

8.

[1] A. Berger and J. Lafferty. Information retrieval as statistical translation. In Proceedings of the 1999 ACM SIGIR
Conference on Research and Development in Information
Retrieval, pages 222–229, 1999.
[2] A. Bookstein and D. Swanson. A decision theoretic foundation for indexing. Journal for the American Society for
Information Science, pages 45–50, 1975.
[3] A. Bookstein and D. Swanson. Probabilistic models for automatic indexing. Journal for the American Society for Information Science, 25(5):312–318, 1976.
[4] S. Brin and L. Page. Anatomy of a large-scale hypertextual
web search engine. In Proceedings of the 7th International
World Wide Web Conference, 1998.
[5] H. Hubbell C.˙An input-output approach to clique identification. Sociometry, 28:377–399, 1965.
[6] J. G. Carbonell, Y. Geng, and J. Goldstein. Automatedquery-relevant summarization and diversity-based reranking.
In IJCAI-97 Workshop on AI and Digital Libraries, 1997.
[7] W. S. Cooper and M. E. Maron. Foundations of probabilistic
and utility-theoretic indexing. Journal of the Association for
Computing Machinery, 25(1):67–80, 1978.
[8] W. B. Croft and D.J. Harper. Using probabilistic models of
document retrieval without relevance information. Journalof Documentation, 35:285–295, 1979.
[9] S. Deerwester, S. Dumais, T. Landauer, G. Furnas, and
R. Harshman. Indexing by latent semantic analysis. Journalof American Society for Information Science, 41:391–407,
1990.
[10] N. Fuhr. Probabilistic models in information retrieval. The
Computer Journal, 35(3):243–255, 1992.
[11] D. Hiemstra and W. Kraaij. Twenty-one at TREC-7: Ad-hoc
and cross-language track. In Proc. of Seventh Text REtrieval
Conference (TREC-7), 1998.
[12] L. Katz. A new status index derived from sociometric analysis. Psychometrika, 18:39–43, 1953.
[13] J. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the Association for Computing Machinery,46, 1999.
[14] J. Lafferty and C. Zhai. Probabilistic IR models based onquery and document generation. In Proceedings of the Workshop on Language Modeling and Information Retrieval,
Carnegie Mellon University, May 31–June 1, 2001.
[15] D. H. Miller, T. Leek, and R. Schwartz. A hidden Markov
model information retrieval system. In Proceedings of the1999 ACM SIGIR Conference on Research and Development
in Information Retrieval, pages 214–221, 1999.
[16] F. Mosteller and D. Wallace. Inference and disputed authorship: The Federalist. Addison Wesley, 1964.
[17] J. Ponte and W. B. Croft. A language modeling approach
to information retrieval. In Proceedings of the ACM SIGIR,
pages 275–281, 1998.
[18] S. Robertson and K. Sparck Jones. Relevance weighting ofsearch terms. Journal of the American Society for Information Science, 27:129–146, 1976.
[19] S. E. Robertson, S. Walker, S. Jones, M. M.HancockBeaulieu, and M. Gatford. Okapi at TREC-3. In D. K. Harman, editor, The Third Text REtrieval Conference (TREC3), 1995.
[20] I. Witten, A. Moffat, and T. Bell. Managing Gigabytes:
Compressing and Indexing Documents and Images. Morgan
Kaufmann, 1999.
[21] S. K. M. Wong and Y. Y. Yao. A probability distribution
model for information retrieval. Information Processing andManagement, 25(1):39–53, 1989.

SUMMARY AND CONCLUSIONS

We have presented a new framework for information retrieval based on Bayesian decision theory. In this framework
we assume a probabilistic model for the parameters of document and query language models, and cast the retrieval
problem in terms of risk minimization. The framework isvery general and expressive, and by choosing specific models
and loss functions it is possible to recover many previously
developed frameworks. In particular, previous approaches
based on language modeling and query-likelihood ranking
are obtained as a natural special case. In this paper we
focus on the use of Kullback-Leibler divergence as loss function, and the estimation of query language models. We introduce a novel method for estimating query models thatuses Markov chains on the inverted indices of a document
collection. This random walk has a natural interpretationin terms of document language models, and results in practical and effective translation models and query language
models. Experiments on standard TREC methods indicate
the usefulness of both the framework and the Markov chain
method, as we obtain significant improvements over standard query expansion methods for strong baseline TF-IDF
methods, with the greatest improvements attained for shortqueries on Web data.

ACKNOWLEDGEMENTS
We thank Jamie Callan, Bruce Croft, Imre Kondor, Victor
Lavrenko, Guy Lebanon, and Roni Rosenfeld for valuable
discussions related to this work. This research was sponsored in part by the Advanced Research and Development
Activity in Information Technology (ARDA) under its Statistical Language Modeling for Information Retrieval Research Program.

ACM SIGIR Forum

259

Vol. 51 No. 2, July 2017