Two-stage language models for information retrieval.
The optimal settings of retrieval parameters often depend on both the document collection and the query, and are usually found through empirical tuning. In this paper, we propose a family of two-stage language models for information retrieval that explicitly captures the different influences of the query and document collection on the optimal settings of retrieval parameters. As a special case, we present a two-stage smoothing method that allows us to estimate the smoothing parameters completely automatically. In the first stage, the document language model is smoothed using a Dirichlet prior with the collection language model as the reference model. In the second stage, the smoothed document language model is further interpolated with a query background language model. We propose a leave-one-out method for estimating the Dirichlet parameter of the first stage, and the use of document mixture models for estimating the interpolation parameter of the second stage. Evaluation on five different databases and four types of queries indicates that the two-stage smoothing method with the proposed parameter estimation methods consistently gives retrieval performance that is close to---or better than---the best results achieved using a single smoothing method and exhaustive parameter search on the test data.
INTRODUCTION
It is well-known that the optimal settings of retrieval parameters
generally depend on both the document collection and the query.
Permission to make digital or hard copies of all or part of this work for
personal 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, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
SIGIR'02, August 11-15, 2002, Tampere, Finland.
For example, specialized term weighting for short queries was studied
in [3]. Salton and Buckley studied many different term weighting
methods used in the vector-space retrieval model; their recommended
methods strongly depend on the type of the query and the
characteristics of the document collection [13]. It has been a great
challenge to find the optimal settings of retrieval parameters automatically
and adaptively accordingly to the characteristics of the
collection and queries, and empirical parameter tuning seems to be
inevitable in order to achieve good retrieval performance. This is
evident in the large number of parameter-tuning experiments reported
in virtually every paper published in the TREC proceedings
[15].
The need for empirical parameter tuning is due in part from the
fact that most existing retrieval models are based on certain pre-
assumed representation of queries and documents, rather than on
a direct modeling of the queries and documents. As a result, the
"adaptability" of the model is restricted by the particular representation
assumed, and reserving free parameters for tuning becomes a
way to accommodate any difference among queries and documents
that has not been captured well in the representation. In order to
be able to set parameters automatically, it is necessary to model
queries and documents directly. This goal has been explored recently
in the language modeling approach to information retrieval,
which has attracted significant attention since it was first proposed
in [9].
The first uses of the language modeling approach focused on its
empirical effectiveness using simple models [9, 7, 2, 1]. Recent
work has begun to develop more sophisticated models and a systematic
framework for this new family of retrieval methods. In [4],
a risk minimization retrieval framework is proposed that incorporates
language modeling as natural components, and that unifies
several existing retrieval models in a framework based on Bayesian
decision theory. One important advantage of the risk minimization
retrieval framework over the traditional models is its capability of
modeling both queries and documents directly through statistical
language models, which provides a basis for exploiting statistical
estimation methods to set retrieval parameters automatically. Several
special language models are explored in [6, 4, 16], and in all
uses of language modeling in IR, smoothing plays a crucial role.
The empirical study in [17] reveals that not only is retrieval performance
generally sensitive to the setting of smoothing parameters,
but also that this sensitivity depends on the type of queries that are
input to the system.
In this paper, we propose a family of language models for information
retrieval that we refer to as two-stage models. The first stage
involves the estimation of a document language model independent
of the query, while the second stage involves the computation of
the likelihood of the query according to a query language model,
which is based on the estimated document language model. Thus,
the two-stage strategy explicitly captures the different influences of
the query and document collection on the optimal settings of retrieval
parameters.
We derive the two-stage models within the general risk minimization
retrieval framework, and present a special case that leads
to a two-stage smoothing method. In the first stage of smoothing,
the document language model is smoothed using a Dirichlet prior
with the collection language model as the reference model. In the
second stage, the smoothed document language model is further
interpolated with a query background language model. we propose
a leave-one-out method for estimating the first-stage Dirichlet
parameter and make use of a mixture model for estimating the
second-stage interpolation parameter. Evaluation on five different
databases and four types of queries indicates that the two-stage
smoothing method with the proposed parameter estimation method-
which is fully automatic-consistently gives retrieval performance
that is close to, or better than, the result of using a single smoothing
method and exhaustive parameter search on the test data.
The proposed two-stage smoothing method represents a step toward
the goal of setting database-specific and query-specific retrieval
parameters fully automatically, without the need for tedious
experimentation. The effectiveness and robustness of the approach,
along with the fact that there is no ad hoc parameter tuning in-
volved, make it very useful as a solid baseline method for the evaluation
of retrieval models.
The rest of the paper is organized as follows. We first derive the
two-stage language models in Section 2, and present the two-stage
smoothing method as a special case in Section 3. We then describe,
in Section 4, methods for estimating the two parameters involved
in the two-stage smoothing method. We report our experimental
results in Section 5. Section 6 presents conclusions and suggestions
for future work.
2. TWO-STAGE LANGUAGE MODELS
2.1 The risk minimization framework
The risk minimization retrieval framework is a general probabilistic
retrieval framework based on Bayesian decision theory [4].
In this framework, queries and documents are modeled using statistical
language models, user preferences are modeled through loss
functions, and retrieval is cast as a risk minimization problem. The
framework unifies several existing retrieval models within one general
probabilistic framework, and facilitates the development of
new principled approaches to text retrieval.
In traditional retrieval models, such as the vector-space model [12]
and the BM25 retrieval model [11], the retrieval parameters have
almost always been introduced heuristically. The lack of a direct
modeling of queries and documents makes it hard for these models
to incorporate, in a principled way, parameters that adequately address
special characteristics of queries and documents. For exam-
ple, the vector-space model assumes that a query and a document
are both represented by a term vector. However, the mapping from
a query or a document to such a vector can be somehow arbitrary.
Thus, because the model "sees" a document through its vector rep-
resentation, there is no principled way to model the length of a doc-
ument. As a result, heuristic parameters must be used (see, e.g., the
pivot length normalization method [14]). Similarly, in the BM25
retrieval formula, there is no direct modeling of queries, making
it necessary to introduce heuristic parameters to incorporate query
term frequencies [11].
One important advantage of the risk minimization retrieval frame-work
[4] over these traditional models is its capability of modeling
both queries and documents directly through statistical language
modeling. Although a query and a document are similar in the
sense that they are both text, they do have important differences.
For example, queries are much shorter and often contain just a few
keywords. Thus, from the viewpoint of language modeling, a query
and a document require different language models. Practically, separating
a query model from a document model has the important
advantage of being able to introduce different retrieval parameters
for queries and documents when appropriate. In general, using statistical
language models allows us to introduce all parameters in a
probabilistic way, and also makes it possible to set the parameters
automatically through statistical estimation methods.
2.2 Derivation of two-stage language models
The original language modeling approach as proposed in [9] involves
a two-step scoring procedure: (1) Estimate a document language
model for each document; (2) Compute the query likelihood
using the estimated document language model (directly). The two-stage
language modeling approach is a generalization of this two-step
procedure, in which a query language model is introduced so
that the query likelihood is computed using a query model that is
based on the estimated document model, instead of using the estimated
document model directly. The use of an explicit and separate
query model makes it possible to factor out any influence of queries
on the smoothing parameters for document language models.
We now derive the family of two-stage language models for information
retrieval formally using the risk minimization framework.
In the risk minimization framework presented in [4], documents
are ranked based on the following risk function:
Z
Z
#D
Let us now consider the following special loss function, indexed
by a small constant #,
c otherwise
where #Q -#D # R is a model distance function, and c is a
constant positive cost. Thus, the loss is zero when the query model
and the document model are close to each other, and is c otherwise.
Using this loss function, we obtain the following risk:
Z
#D
Z
is the sphere of radius # centered at #D in the parameter
space.
Now, assuming that p(#D | d, S) is concentrated on an estimated
value - #D , we can approximate the value of the integral over #D by
the integrand's value at -
#D . Note that the constant c can be ignored
for the purpose of ranking. Thus, using A # B to mean that A and
B have the same effect for ranking, we have that
Z
p(#Q | q, U) d#Q
When #Q and #D belong to the same parameter space (i.e.,
#D ) and # is very small, the value of the integral can be approximated
by the value of the function at -
#D times a constant (the
volume of S #D )), and the constant can again be ignored for the
purpose of ranking. That is,
#D | q, U)
Therefore, using this risk we will be actually ranking documents according
to p( - #D | q, U), i.e., the posterior probability that the user
used the estimated document model as the query model. Applying
Bayes' formula, we can rewrite this as
#D | U) (1)
Equation 1 is our basic two-stage language model retrieval for-
mula. Similar to the model discussed in [1], this formula has the
following
#D , U) captures how well the estimated
document model -
#D explains the query, whereas p( - #D | U)
encodes our prior belief that the user would use -
#D as the query
model. While this prior could be exploited to model different document
sources or other document characteristics, in this paper we
assume a uniform prior.
The generic two-stage language model can be refined by specifying
a concrete model p(d | #D , S) for generating documents and a
concrete model p(q | #Q , U) for generating queries; different specifications
lead to different retrieval formulas. If the query generation
model is the simplest unigram language model, we have the
scoring procedure of the original language modeling approach proposed
in [9]; that is, we first estimate a document language model
and then compute the query likelihood using the estimated model.
In the next section, we present the generative models that lead to
the two-stage smoothing method suggested in [17].
3. THE TWO-STAGE SMOOTHING
query, and denote the words in the vocabulary.
We consider the case where both #Q and #D are parameters of unigram
language models, i.e., multinomial distributions over words
in V .
The simplest generative model of a document is just the unigram
language model #D , a multinomial. That is, a document would be
generated by sampling words independently according to p(- | #D ),
or
p(d | #D ,
Y
Each document is assumed to be generated from a potentially different
model as assumed in the general risk minimization frame-
work. Given a particular document d, we want to estimate #D . We
use a Dirichlet prior on #D with parameters #1 , #2 , . , # |V | ),
given by
#(
Y
The parameters # i are chosen to be #
a parameter and p(- | S) is the "collection language model," which
can be estimated based on a set of documents from a source S . The
posterior distribution of #D is given by
p(#D | d, S) #
Y
p(w | #D ) c(w,d)+-p(w | S)-1
and so is also Dirichlet, with parameters #
Using the fact that the Dirichlet mean is # j /
k #k , we have that
p-(w | -
Z
p(w | #D )p(#D | d, S)d#D
w#V c(w, d) is the length of d. This is the Dirichlet
prior smoothing method described in [17].
We now consider the query generation model. The simplest
model is again the unigram language model #Q , which will result
in a retrieval model with the Dirichlet prior as the single smoothing
method. However, as observed in [17], such a model will not
be able to explain the interactions between smoothing and the type
of queries. In order to capture the common and non-discriminative
words in a query, we assume that a query is generated by sampling
words from a two-component mixture of multinomials, with one
component being #Q and the other some query background language
model p(- | U). That is,
p(q | #Q , #,
Y
where # is a parameter, roughly indicating the amount of "noise"
in q.
Combining our estimate of #D with this query model, we have
the following retrieval scoring formula for document d and query
q.
p(q | -
#D , #,
Y
Y
In this formula, the document language model is effectively smoothed
in two steps. First, it is smoothed with a Dirichlet prior, and second,
it is interpolated with a query background model. Thus, we refer to
this as two-stage smoothing.
The above model has been empirically motivated by the observation
that smoothing plays two different roles in the query likelihood
retrieval method. One role is to improve the maximum likelihood
estimate of the document language model, at the very least assigning
non-zero probabilities to words that are not observed in the
document. The other role is to "explain away" the common/non-
discriminative words in the query, so that the documents will be
discriminated primarily based on their predictions of the "topical"
words in the query. The two-stage smoothing method explicitly de-couples
these two roles. The first stage uses Dirichlet prior smoothing
method to improve the estimate of a document language model;
this method normalizes documents of different lengths appropriately
with a prior sample size parameter, and performs well empirically
[17]. The second stage is intended to bring in a query background
language model to explicitly accommodate the generation
of common words in queries.
The query background model p(- | U) is in general different from
the collection language model p(- | S). With insufficient data to estimate
p(- | U), however, we can assume that p(- | S) would be a
reasonable approximation of p(- | U). In this form, the two-stage
smoothing method is essentially a combination of Dirichlet prior
smoothing with Jelinek-Mercer smoothing [17]. Indeed, it is very
easy to verify that when with just the Dirichlet
prior smoothing, whereas when
Mercer smoothing. Since the combined smoothing formula still
follows the general smoothing scheme discussed in [17], it can be
implemented very efficiently. In the next section, we present methods
for estimating - and # from data.
Collection avg. doc length max. doc length vocab. size -

Table

1: Estimated values of - along with database characteristics.
4. PARAMETER ESTIMATION
4.1 Estimating -
The purpose of the Dirichlet prior smoothing at the first stage is
to address the estimation bias due to the fact that a document is an
extremely small amount of data with which to estimate a unigram
language model. More specifically, it is to discount the maximum
likelihood estimate appropriately and assign non-zero probabilities
to words not observed in a document; this is the usual role of language
model smoothing. A useful objective function for estimating
smoothing parameters is the "leave-one-out" likelihood, that is, the
sum of the log-likelihoods of each word in the observed data computed
in terms of a model constructed based on the data with the
target word excluded ("left out"). This criterion is essentially based
on cross-validation, and has been used to derive several well-known
smoothing methods including the Good-Turing method [8].
Formally, let be the collection of docu-
ments. Using our Dirichlet smoothing formula, the leave-one-out
log-likelihood can be written as
#-1(- |
Thus, our estimate of - is
which can be easily computed using Newton's method. The update
formula is
where the first and second derivatives of #-1 are given by
and
Since g # 0, as long as g #= 0, the solution will be a global max-
imum. In our experiments, starting from value 1.0 the algorithm
always converges.
The estimated values of - for three databases are shown in Table
1. There is no clear correlation between the database characteristics
shown in the table and the estimated value of -.
4.2 Estimating #
With the query model hidden, the query likelihood is
p(q | #,
Z
Y
In order to estimate #, we approximate the query model space by
the set of all N estimated document language models in our col-
lection. That is, we will approximate the integral with a sum over
all the possible document language models estimated on the collec-
tion, or
p(q | #,
Y
is the smoothed unigram language
model estimated based on document d i using the Dirichlet
prior approach.
Thus, we assume that the query is generated from a mixture of N
document models with unknown mixing weights {# i } N
. Leaving
what we really want is not to
maximize the likelihood of generating the query from every document
in the collection, instead, we want to find a # that can maximize
the likelihood of the query given relevant documents. With
estimate, we would indeed allocate higher weights
on documents that predict the query well in our likelihood function;
presumably, these documents are also more likely to be relevant.
With this likelihood function, the parameters # and {# i } N
can
be estimated using the EM algorithm. The update formulas are
and
5. EXPERIMENTS
In this section we first present experimental results that confirm
the dual-role of smoothing, which provides an empirical justification
for using the two-stage smoothing method for retrieval.
We then present results of the two-stage smoothing method using
the estimated parameters, comparing it to the optimal performance
from using single smoothing methods and an exhaustive parameter
search.
5.1 Influence of Query Length and
Verbosity on Smoothing
In [17], strong interactions between smoothing and the type of
queries have been observed. However, it is unclear whether the
high sensitivity observed on long queries is due to a higher density
of common words in such queries, or to just the length. The
two-stage smoothing method assumes that it is the former. In order
to clarify this, we design experiments to examine two query
factors-length and "verbosity." Specifically, we consider four different
types of queries, i.e., short keyword, long keyword, short ver-
bose, and long verbose queries, and compare how they each behave
with respect to smoothing. As we will show, the high sensitivity is
indeed caused by the presence of common words in the query, and
this provides an empirical justification for the two-stage smoothing
method.
We generate the four types of queries from TREC topics 1-150.
These 150 topics are special because, unlike other TREC topics,
they all have a "concept" field, which contains a list of keywords
related to the topic; these keywords serve well as the "long key-
word" version of our queries. Figure 1 shows an example of such a
topic (topic 52).
Title: South African Sanctions
Description: Document discusses sanctions against
South Africa.
Narrative:
A relevant document will discuss any aspect of
South African sanctions, such as: sanctions
declared/proposed by a country against the South
African government in response to its apartheid
policy, or in response to pressure by an individual,
organization or another country; international
sanctions against Pretoria imposed by the United
Nations; the effects of sanctions against S. Africa;
opposition to sanctions; or, compliance with
sanctions by a company. The document will identify
the sanctions instituted or being considered, e.g.,
corporate disinvestment, trade ban, academic boycott,
arms embargo.
Concepts:
1. sanctions, international sanctions,
economic sanctions
2. corporate exodus, corporate disinvestment, stock
divestiture, ban on new investment, trade ban,
import ban on South African diamonds, U.N. arms
embargo, curtailment of defense contracts,
cutoff of nonmilitary goods, academic boycott,
reduction of cultural ties
3. apartheid, white domination, racism
4. antiapartheid, black majority rule
5. Pretoria

Figure

1: Example topic, number 52. The keywords are used
as the "long keyword" version of our queries.
We use all of the 150 topics, and generate the four versions of
queries in the following way:
1. short keyword: Using only the title of the topic description
(usually a noun phrase) 1
2. short verbose: Using only the description field (usually one
sentence).
3. long keyword: Using the concept field (about 28 keywords
on average).
4. long verbose: Using the title, description and the narrative
field (more than 50 words on average).
Occasionally, a few function words were manually excluded, in order to
make the queries purely keyword-based.
The relevance judgments available for these 150 topics are mostly
on the documents in TREC disk 1 and disk 2. In order to observe
any possible difference in smoothing caused by the types of docu-
ments, we partition the documents in disks 1 and 2 and use the three
largest subsets of documents, accounting for a majority of the relevant
documents for our queries. The three databases are AP88-89,
WSJ87-92, and ZIFF1-2, each about 400MB-500MB in size. The
queries without relevance judgments for a particular database were
ignored for all of the experiments on that database. Four queries do
not have judgments on AP88-89, and 49 queries do not have judgments
on ZIFF1-2. Preprocessing of the documents is minimized;
only a Porter stemmer is used, and no stop words are removed.
Combining the four types of queries with the three databases gives
us a total of 12 different testing collections.
To understand the interaction between different query factors and
smoothing, we examine the sensitivity of retrieval performance to
smoothing on each of the four different types of queries. For both
Jelinek-Mercer and Dirichlet smoothing, on each of our 12 testing
collections we vary the value of the smoothing parameter and
record the retrieval performance at each parameter value. The results
are plotted in Figure 2. In each case, we show how the average
precision varies according to different values of the smoothing parameter

From these figures, we see that the two types of keyword queries
behave similarly, as do the two types of verbose queries. The retrieval
performance is generally much less sensitive to smoothing
in the case of the keyword queries than for the verbose queries,
whether long or short. Therefore, the sensitivity is much more correlated
with the verbosity of the query than with the length of the
query. Indeed, the short verbose queries are clearly more sensitive
than the long keyword queries. In all cases, insufficient smoothing
is much more harmful for verbose queries than for keyword
queries. This confirms that smoothing is indeed responsible for
"explaining" the common words in a query, and provides an empirical
justification for the two-stage smoothing approach.
We also see a consistent order of performance among the four
types of queries. As expected, long keyword queries are the best
and short verbose queries are the worst. Long verbose queries
are worse than long keyword queries, but better than short key-word
queries, which are better than the short verbose queries. This
appears to suggest that queries with only (presumably good) key-words
tend to perform better than more verbose queries. Also,
longer queries are generally better than short queries.
5.2 Effectiveness of the Two-stage
Smoothing Method
To evaluate the two-stage smoothing method, we first test it on
the same 12 testing collections as described earlier. These collections
represent a very good diversity in the types of queries, but
the databases are all homogeneous and relatively small. In order to
further test the robustness of the two-stage smoothing method, we
then test it on three much bigger and more heterogeneous TREC
collections. These are the official ad hoc retrieval collections used
in TREC-7, TREC-8, and the TREC-8 small web track. The official
TREC-7 and TREC-8 ad hoc tasks have used the same document
database (i.e., TREC disk4 and disk5 excluding the Congressional
Record data), but different topics (topics 351-400 for TREC-7 and
401-450 for TREC-8). The TREC-8 web track and the TREC-8
official ad hoc task share the same 50 topics. Since these topics do
not have a concept field, we have only three types of queries: short-
short-verbose, and long-verbose. The size of these large
collections is about 2GB in the original source. Again, we perform
minimum pre-processing - only a Porter stemmer was used, and no
precision
lambda
Sensitivity of Precision (Jelinek-Mercer, AP88-89)
short-keyword
long-keyword
short-verbose
long-verbose0.10.30.5
precision
lambda
Sensitivity of Precision (Jelinek-Mercer, WSJ87-92)
short-keyword
long-keyword
short-verbose
long-verbose0.10.30.5
precision
lambda
Sensitivity of Precision (Jelinek-Mercer, ZF1-2)
short-keyword
long-keyword
short-verbose
long-verbose0.10.30.5
precision
prior (mu)
Sensitivity of Precision (Dirichlet, AP88-89)
short-Keyword
long-Keyword
short-Verbose
long-Verbose0.10.30.5
precision
prior (mu)
Sensitivity of Precision (Dirichlet, WSJ87-92)
short-keyword
long-keyword
short-verbose
long-verbose0.10.30.5
precision
prior (mu)
Sensitivity of Precision (Dirichlet, ZF1-2)
short-keyword
long-keyword
short-verbose
long-verbose

Figure

2: Sensitivity of Precision for Jelinek-Mercer smoothing (top) and Dirichlet prior smoothing (bottom) on AP88-89 (left),
WSJ87-92 (center), and Ziff1-2 (right).
stop words were removed.
For each testing collection, we compare the retrieval performance
of the estimated two-stage smoothing parameters with the best results
achievable using a single smoothing method. The best results
of a single smoothing method are obtained through an exhaustive
search on its parameter space, so are the ideal performance of the
smoothing method. In all our experiments, we use the collection
language model to approximate the query background model.
The results are shown in Table 2. The four types of queries are
abbreviated with the two initial letters (e.g., SK for Short-Keyword).
The standard TREC evaluation procedure for ad hoc retrieval is
followed, and we have considered three performance measures -
non-interpolated average precision, initial precision (i.e., precision
at recall), and precision at five documents. In all the results,
we see that, the performance of two-stage smoothing with the estimated
parameter values is consistently very close to, or better than
the best performance of a single method by all the three measures.
Only in a few cases, the difference is statistically significant (indi-
cated with a star).
To quantify the sensitivity of the retrieval performance to the
smoothing parameter for single smoothing methods, we also show
(in parentheses) the median average precision at all the parameter
values that are tried 2 . We see that, for Jelinek-Mercer, the sensitivity
is clearly higher on verbose queries than on keyword queries;
the median is usually much lower than the best performance for
verbose queries. This means that, it is much harder to tune the
# in Jelinek-Mercer for verbose queries than for keyword queries.
Interestingly, for Dirichlet prior, the median is often just slightly
below the best, even when the queries are verbose. (The worst
cases are significantly lower, though.) From the sensitivity curves
in

Figure

2, we see that as long as we set a relatively large value
2 For Jelinek-Mercer, we tried 13 values {0.01, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5,
0.6,0.7,0.8,0.9,0.95, 0.99}; for Dirichlet prior, we tried 10 values {100, 500,
800, 1000, 2000, 3000, 4000, 5000, 8000, 10000}.
for - in Dirichlet prior, the performance will not be much worse
than the best performance, and there is a great chance that the median
is at a large value for -. This immediately suggests that we
can expect to perform reasonably well if we simply set - to some
"safe" large value. However, it is clear, from the results in Table
2, that such a simple approach would not perform so well as
our parameter estimation methods. Indeed, the two-stage performance
is always better than the median, except for three cases of
short-keyword queries when it is slightly worse. Since the Dirichlet
prior smoothing dominates the two-stage smoothing effect for
these short-keyword queries (due to "little noise"), this somehow
suggests that the leave-one-out method might have under-estimated
-.
Note that, in general, Jelinek-Mercer has not performed as well
as Dirichlet prior in all our experiments. But, in two cases of verbose
queries (Trec8-SV and Trec8-LV on the Trec7/8 database),
it does outperform Dirichlet prior. In these two cases, the two-stage
smoothing method performs either as well as or better than
the Jelinek-Mercer. Thus, the two-stage smoothing performance
appears to always track the best performing single method at its
optimal parameter setting.
The performance of two-stage smoothing does not reflect the
performance of a "full-fledged" language modeling approach, which
would involve more sophisticated feedback models [4, 6, 16]. Thus,
it is really not comparable with the performance of other TREC sys-
tems. Yet some of the performance figures shown here are actually
competitive when compared with the performance of the official
TREC submissions (e.g., the performance on the TREC-8 ad hoc
task and the TREC-8 web track).
These results of the two-stage smoothing method are very en-
couraging, especially because there is no ad hoc parameter tuning
involved in the retrieval process with the approach. Both - and #
are automatically estimated based on a specific database and query;
- is completely determined by the given database, and # is deter-
Database Query Best Jelinek-Mercer Best Dirichlet Two-Stage
AvgPr (med) InitPr Pr@5d AvgPr (med) InitPr Pr@5d AvgPr Initpr Pr@5d
Database Query Best Jelinek-Mercer Best Dirichlet Two-Stage
AvgPr (med) InitPr Pr@5d AvgPr (med) InitPr Pr@5d AvgPr Initpr Pr@5d
Web Trec8-SV 0.203 (0.191) 0.611 0.392 0.267 (0.249) 0.699 0.492 0.253 0.680 0.436

Table

2: Comparison of the estimated two-stage smoothing with the best single stage smoothing methods on small collections (top)
and large collections (bottom). The best number for each measure is shown in boldface. An asterisk (*) indicates that the difference
between the two-stage smoothing performance and the best single smoothing performance is statistically significant according to the
signed rank test at the level of 0.05.
mined by the database and the query together. The method appears
to be quite robust according to our experiments with all the different
types of queries and different databases.
6. CONCLUSIONS
In this paper we derive general two-stage language models for
information retrieval using the risk minimization retrieval frame-
work, and present a concrete two-stage smoothing method as a
special case. The two-stage smoothing strategy explicitly captures
the different influences of the query and document collection
on the optimal settings of smoothing parameters. In the first stage,
the document language model is smoothed using a Dirichlet prior
with the collection model as the reference model. In the second
stage, the smoothed document language model is further interpolated
with a query background model.
We propose a leave-one-out method for estimating the first-stage
Dirichlet prior parameter and a mixture model for estimating the
second-stage interpolation parameter. These methods allow us to
set the retrieval parameters automatically, yet adaptively according
to different databases and queries. Evaluation on five different
databases and four types of queries indicates that the two-stage
smoothing method with the proposed parameter estimation scheme
consistently gives retrieval performance that is close to, or better
than, the best results attainable using a single smoothing method,
achievable only through an exhaustive parameter search. The effectiveness
and robustness of the two-stage smoothing approach,
along with the fact that there is no ad hoc parameter tuning in-
volved, make it a solid baseline approach for evaluating retrieval
models.
While we have shown that the automatic two-stage smoothing
gives retrieval performance close to the best results attainable using
a single smoothing method, we have not yet analyzed the optimality
of the estimated parameter values in the two-stage parameter space.
For example, it would be important to see the relative optimality of
the estimated - and # when fixing one of them. It would also be
interesting to explore other estimation methods. For example, -
might be regarded as a hyperparameter in a hierarchical Bayesian
approach. For the estimation of the query model parameter #, it
would be interesting to try different query background models. One
possibility is to estimate the background model based on resources
such as past queries, in addition to the collection of documents. Another
interesting future direction is to exploit the query background
model to address the issue of redundancy in the retrieval results.
Specifically, a biased query background model may be used to rep-
resent/explain the sub-topics that a user has already encountered
(e.g., through reading previously retrieved results), in order to focus
ranking on the new sub-topics in a relevant set of documents.

ACKNOWLEDGEMENTS

We thank Rong Jin, Jamie Callan, and the anonymous reviewers for
helpful comments on this work. This research was sponsored in full
by the Advanced Research and Development Activity in Information
Technology (ARDA) under its Statistical Language Modeling
for Information Retrieval Research Program, contract MDA904-
00-C-2106.



--R

Information retrieval as statistical translation.





A hidden Markov model information retrieval system.
On the estimation of 'small' probabilities by leaving-one-out
A language modeling approach to information retrieval.
Relevance weighting of search terms.



Pivoted document length normalization.



--TR
Term-weighting approaches in automatic text retrieval
Pivoted document length normalization
Improving two-stage ad-hoc retrieval for short queries
A language modeling approach to information retrieval
A hidden Markov model information retrieval system
Information retrieval as statistical translation
A vector space model for automatic indexing
Document language models, query models, and risk minimization for information retrieval
Relevance based language models
A study of smoothing methods for language models applied to Ad Hoc information retrieval
On the Estimation of ''Small'' Probabilities by Leaving-One-Out

--CTR
Mark D. Smucker , James Allan, Lightening the load of document smoothing for better language modeling retrieval, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Donald Metzler, Estimation, sensitivity, and generalization in parameterized retrieval models, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
L. Azzopardi , M. Girolami , C. J. van Rijsbergen, User biased document language modelling, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
James Allan , Courtney Wade , Alvaro Bolivar, Retrieval and novelty detection at the sentence level, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
Hugo Zaragoza , Djoerd Hiemstra , Michael Tipping, Bayesian extension to the language model for ad hoc information retrieval, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
M. Winslett , K. Chang , A. Doan , J. Han , C. Zhai , Y. Zhou, Database research at the University of Illinois at Urbana-Champaign, ACM SIGMOD Record, v.31 n.3, September 2002
Rong Jin , Joyce Y. Chai , Luo Si, Learn to weight terms in information retrieval using category information, Proceedings of the 22nd international conference on Machine learning, p.353-360, August 07-11, 2005, Bonn, Germany
Donald Metzler , W. Bruce Croft, Combining the language model and inference network approaches to retrieval, Information Processing and Management: an International Journal, v.40 n.5, p.735-750, September 2004
Xiaohua Zhou , Xiaohua Hu , Xiaodan Zhang , Xia Lin , Il-Yeol Song, Context-sensitive semantic smoothing for the language modeling approach to genomic IR, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Guihong Cao , Jian-Yun Nie , Jing Bai, Integrating word relationships into language models, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
Tao Tao , ChengXiang Zhai, Mining comparable bilingual text corpora for cross-language information integration, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Seung-Hoon Na , In-Su Kang , Ji-Eun Roh , Jong-Hyeok Lee, An empirical study of query expansion and cluster-based retrieval in language modeling approach, Information Processing and Management: an International Journal, v.43 n.2, p.302-314, March 2007
Paul Ogilvie , Jamie Callan, Combining document representations for known-item search, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
Jaime Teevan , David R. Karger, Empirical development of an exponential probabilistic model for text retrieval: using textual analysis to build a better model, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
Xiaoyong Liu , W. Bruce Croft, Cluster-based retrieval using language models, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
Jianfeng Gao , Haoliang Qi , Xinsong Xia , Jian-Yun Nie, Linear discriminant model for information retrieval, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
Thomas R. Lynam , Chris Buckley , Charles L. A. Clarke , Gordon V. Cormack, A multi-system analysis of document and term selection for blind feedback, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
Jianfeng Gao , Jian-Yun Nie , Guangyuan Wu , Guihong Cao, Dependence language model for information retrieval, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
Ying Zhao , Justin Zobel, Searching with style: authorship attribution in classic literature, Proceedings of the thirtieth Australasian conference on Computer science, p.59-68, January 30-February 02, 2007, Ballarat, Victoria, Australia
Jian-Yun Nie , Guihong Cao , Jing Bai, Inferential language models for information retrieval, ACM Transactions on Asian Language Information Processing (TALIP), v.5 n.4, p.296-322, December 2006
Jianfeng Gao , Chin-Yew Lin, Introduction to the special issue on statistical language modeling, ACM Transactions on Asian Language Information Processing (TALIP), v.3 n.2, p.87-93, June 2004
Joyce Y. Chai , Chen Zhang , Rong Jin, An empirical investigation of user term feedback in text-based targeted image search, ACM Transactions on Information Systems (TOIS), v.25 n.1, p.3-es, February 2007
ChengXiang Zhai , John Lafferty, A risk minimization framework for information retrieval, Information Processing and Management: an International Journal, v.42 n.1, p.31-55, January 2006
Wessel Kraaij , Jian-Yun Nie , Michel Simard, Embedding web-based statistical translation models in cross-language information retrieval, Computational Linguistics, v.29 n.3, p.381-419, September
interpolation;risk minimization;two-stage smoothing;parameter estimation;leave-one-out;mixture model;two-stage language models;dirichlet prior