Journal of Natural Language Processing Vol. 21 No. 4translated from: Journal of Natural Language Processing Vol. 19, No. 3, pp. 121–142

Relevance Feedback using Surface and Latent Informationin Texts
Jun Harashima† and Sadao Kurohashi†
Most relevance feedback methods re-rank search results using only the informationof surface words in texts. We present a method that uses not only the informationof surface words but also that of latent words that are inferred from texts. We inferlatent word distribution in each document in the search results using latent Dirichlet
allocation (LDA). When feedback is given, we also infer the latent word distribution
in the feedback using LDA. We calculate the similarities between the user feedback
and each document in the search results using both the surface and latent word
distributions and re-rank the search results on the basis of the similarities. Evaluation
results show that when user feedback consisting of two documents (3, 589 words) is
given, the proposed method improves the initial search results by 27.6% in precisionat 10 (P@10). Additionally, it proves that the proposed method can perform well evenwhen only a small amount of user feedback is available. For example, an improvementof 5.3% in P@10 was achieved when user feedback constituted only 57 words.
Key Words: Information Retrieval, Relevance Feedback, Latent Dirichlet Allocation

1 Introduction
The main purpose of information retrieval (IR) is to rank documents so that users can obtain
information eﬃciently. However, appropriate ranking of documents is diﬃcult to achieve throughone-oﬀ retrievals because user queries are typically short and ambiguous (Jansen, Spink, andSaracevic 2000). For example, the query “Mac price” can be interpreted as the price of a “Mac”(PC), a food item at “McDonalds,” or some other “Mac.” If we do not know what “Mac” refers
to, we cannot rank the documents in a way that satisﬁes user information needs.
Relevance feedback (RF) is a technique that solves this problem by incorporating user feedback
into the IR process. The basic procedure for RF is as follows.
(1) The RF-based system presents the initial search results for a given query.
(2) The user selects some relevant documents from the search results.
(3) The system modiﬁes the search results using this feedback.

† Graduate School of Informatics, Kyoto University* This article has been partially revised for better understanding of overseas readers.

Journal of Natural Language Processing

Vol. 21 No. 4

September 2014

For example, if the system obtains documents about the price of a “Mac” (PC) as user feedback,it assumes that the user is interested in this topic and modiﬁes the initial search results.
There are a variety of RF methods based on diﬀerent retrieval models. Rocchio’s algorithm(Rocchio 1971) and the Ide dec-hi method (Ide 1971) are well-known RF methods for the vector
space model (Salton, Wong, and Yang 1975). In the probabilistic model (Spärck Jones, Walker,
and Robertson 2000), feedback can be used to modify the weight of terms to change or expand
the original query. For language modeling approaches (Ponte and Croft 1998), Zhai and Laﬀerty(2001) proposed a fundamental RF method.
The basic idea behind these methods is the same, i.e., documents that are similar to the
feedback are re-ranked higher. It should be noted that most methods calculate similarities using
information from words that only appear in the feedback and search results. In other words,
these methods do not use information from words that do not appear in the given texts.
However, information from highly probable relevant words can be useful for re-ranking search
results even if the words do not appear in the given texts. Consider the query, “Mac price,” andsuppose that the feedback contains documents about the price of a “Mac” (PC). Although the
feedback may not contain words such as “CPU” and “HDD,” these words are closely related to
the feedback and are, therefore, highly probable. The same is true of other relevant documentsin the search results. Even if a relevant document does not contain words speciﬁc to the feedback
and if it does include closely related to words, these words are highly probable. This information
can be useful for calculating similarities between the feedback and other documents.
In this paper, we propose an RF method that uses the surface information in texts andlatent information contained in the texts. For each document in the search results, we infer
the distribution of words that are highly probable given the latent topics in the document using
latent Dirichlet allocation (LDA) (Blei, Ng, and Jordan 2003). We calculate the similarities
between the feedback and each document in the search results using both surface and latent
word distributions. Then, we re-rank the search results on the basis of the similarities.
The remainder of this paper is organized as follows. In Sections 2 and 3, we explain thelanguage modeling approaches for IR and LDA, which form the basis of the proposed method. In
Section 4, we present the proposed method. Section 5 reports experiments performed to evaluate
the proposed method, and conclusions are presented in Section 6.

922

Harashima and Kurohashi

Relevance Feedback using Surface and Latent Information in Texts

2 Language Modeling Approaches to IR
In this section, we describe the language modeling approaches for IR that form the basis of
our method.

2.1

Overview

Language modeling approaches can be classiﬁed into three types: query likelihood model(Ponte and Croft 1998), document likelihood model (Lavrenko and Croft 2001), and KullbackLeibler (KL) divergence retrieval model (Laﬀerty and Zhai 2001).
In the query likelihood model, a document language model Pdh (·) is constructed for eachdocument dh (h = 1, . . . , H) in the collection. When a query q is submitted by a user, the query
likelihood Pdh (q) is computed using the document model for each dh . Then, the documents inthe collection are ranked according to their likelihood.
In the document likelihood model, a query language model Pq (·) is constructed for a given
query. The query language model is then used to compute the document likelihood Pq (dh ) for
each document in the collection. The documents are then ranked by their likelihood.
In the KL-divergence retrieval model, both a query model Pq (·) and a document model Pdh (·)
are constructed. The documents in the collection are ranked according to the KL-divergence
KL(Pq (·)||Pdh (·)) between these models.

2.2

Language Model Construction

There are several ways to construct a query model and a document model. One method is
maximum likelihood estimation (MLE). The MLE of a word w with respect to a text t (a queryor document) is computed using
PtM LE (w) =tf (w, t)
,
|t|

(1)

where tf (w, t) represents the frequency of w in t, and |t| represents the number of words in t.
Dirichlet prior smoothing (DIR) (Zhai and Laﬀerty 2004) is a well-known construction method.
The DIR of w with respect to t is computed as follows.
PtDIR (w) =

M LE
(w)
tf (w, t) + µPD
all,|t| + µ(2)where Dall represents a collection, and µ represents the smoothing parameter that controls thedegree of conﬁdence for the frequency of w in Dall (rather than in the frequency in t).

923

Journal of Natural Language Processing

2.3

Vol. 21 No. 4

September 2014

Fundamental RF Method

Zhai and Laﬀerty proposed a fundamental RF method for language modeling (Zhai andLaﬀerty 2001). When user feedback F = (f1 , . . . , fG ) is available, they construct a language
model PF (·) for the feedback. Then, a new query model is constructed by interpolating the
feedback model with the original query model that was used to obtain the initial search results.
Finally, they modify the search results using the new query model.
Their experiments demonstrate that their proposed method is eﬀective. However, they only
use the information of words that appear in a text for the RF. In our proposed method, we also
use information about words that do not appear in a text but are highly probable given the latent
topics in the text.

3 LDA
In this section, we explain LDA, which the proposed method uses to determine words thatare highly probable given the latent topics of a text.

3.1

Overview

LDA (Blei et al. 2003) is a popular topic model that is based on the idea that documents are
generated from a mixture of topics, where a topic is a distribution of words. LDA posits thata topic proportion θ = (θ1 , . . . , θK ) for a document can take any value in the (K − 1) simplex.
Therefore, a topic proportion is a point of the simplex as drawn from a Dirichlet distribution.
According to the generative process, the probability of document d in LDA is calculated asfollows:∫
P (d|α, β1 , . . . , βK ) =P (θ|α)( J (K∏ ∑j=1)tf (wj ,d) )P (wj |zk , βk ) P (zk |θ)
dθ,

(3)

k=1

where P (θ|α) represents the probability of θ drawn from a Dirichlet distribution, and the parameter α is a K-vector with components αk > 0 (k = 1, . . . , K). zk represents the k-th topic,
and βk represents a word distribution for the topic. P (wj |zk , βk ) represents the probability of
wj in zk , and P (zk |θ) represents the probability of zk drawn from a multinomial distribution. J
represents the number of words in a vocabulary.

3.2

Parameter Estimation

There are two ways to estimate the parameters: Gibbs sampling and a variational method(Griﬃths and Steyvers 2004; Blei et al. 2003). Gibbs sampling is more popular because it
924

Harashima and Kurohashi

Relevance Feedback using Surface and Latent Information in Texts

determines better parameter values and is simpler to implement. However, Gibbs sampling forparameter estimation takes much longer to execute than variational methods. Therefore, we use
a variational method because search systems should return results as quickly as possible.
First, variational parameters γi = (γi1 , . . . , γiK ) and ϕi = (ϕi1 , . . . , ϕiJ ) are introduced foreach document di (i = 1, . . . , I) in the training data. Note that ϕij = (ϕij1 , . . . , ϕijK ). Then,
optimum parameter values are found by repeatedly computing the following pair of updated
equations:
(
K
(∑
))
ϕijk ∝ βkj exp Ψ(γik ) − Ψ
γik′

(4)

k′ =1

γik = αk +J∑

ϕijk tf (wj , di ),

(5)

j=1

where Ψ is the ﬁrst derivative of the log Γ function.
Next, αk and βk are updated using γi and ϕi . A Newton-Raphson method has been used toestimate each αk (Blei et al. 2003). However, the ﬁxed-point iteration method (Minka 2000) is
a better estimation technique; therefore, we have used updated equations based on this method.
The updated equations for αk and βk , respectively, are as follows:
βkj ∝

I
∑

ϕijk tf (wj , di )i=1∑I
{Ψ(αk + nik ) − Ψ(αk )} oldαk ,αk = ∑Ii=1
i=1 {Ψ(α0 + |di |) − Ψ(α0 )}where nik =∑J

j=1 ϕijk tf (wj , di ), α0 =

(6)
(7)

∑K

old
′
k′ =1 αk , and αk represents αk before the update.

Finally, updates of γi and ϕi for each di and those of αk and βk are iterated until convergence.
When αk and βk have been estimated, we obtain the probability of document di using Eq. (3).
In addition, we can obtain PdLDA(wj ) using the estimated γi and the following equation:i
PdLDA(wj ) ≃iwhere γik /∑K

k′ =1 γik′K∑

βkj γik,∑K′
k′ =1 γik
k=1

(8)

is a distribution over the latent topics of di . We interpolate each βkj

according to the distribution and obtain the probabilities of wj that are highly probable given
di .

925

Journal of Natural Language Processing

3.3

Vol. 21 No. 4

September 2014

Inference of Unseen Documents

LDA is considered a Bayesian extension of probabilistic latent semantic analysis (Hofmann1999). A major advantage of LDA is that it can infer the probabilities of unseen documentsthat are not included in the training data. When we compute the probabilities of an unseen
document dI+1 , the variational parameters γI+1 and ϕI+1 are estimated using Eqs. (4) and (5),respectively. The estimated values obtained using the training document set are used for αk and(wj ) using Eq. (8). In
βk . When γI+1 has been estimated, we can obtain the probability PdLDA
I+1
the proposed method, this advantage of LDA allows us to calculate the probabilities of words
that are highly probable given the feedback.

3.4

LDA in IR

LDA has been successfully used in various ﬁelds such as natural language processing (Bleiet al. 2003), image processing (Fei-Fei and Perona 2005), and speech recognition (Heidel, Chang,and Lee 2007). In the IR ﬁeld, Wei and Croft (2006) incorporated LDA into a query likelihood
model, and Yi and Allan (2009) have incorporated LDA into a document likelihood model.
Zhou and Wade (2009) incorporated LDA into a KL-divergence retrieval model. These methods
construct a language model for each document using LDA and the obtained search results fora given query according to their scores (e.g., query likelihood). In this study, we focus on user
feedback. We construct a language model for the feedback using LDA, which we use to modify
the search results.

4 Proposed Method
4.1

Overview

We propose an RF method that uses surface and latent information in texts. An overview
of the proposed method is illustrated in Figure 1. We refer to the model containing surface andlatent information in text t as a hybrid language model PtHY B (·). First, a query q is submitted
by a user and initial search results Dq = (d1 , . . . , dI ) are obtained (Step 1). Next for eachBdocument di (i = 1, . . . , I) in Dq , a hybrid language model PdHY(·) that contains the document’sisurface and latent information is constructed (Step 2). Then, when the user provides feedback
F = (f1 , . . . , fG ), a hybrid language model PFHY B (·) for F is constructed (Step 3). Finally, a
new query model using the feedback model is constructed, and Dq is re-ranked using the newquery model. Documents that have a hybrid language model resembling the user feedback are
given a higher rank (Step 4). The details of each step are described in the following sections.
926

Harashima and Kurohashi

Relevance Feedback using Surface and Latent Information in Texts

Fig. 1 Overview of the proposed method

It is possible to use latent semantic analysis (LSA) to take advantage of latent information in
texts. We could use LSA on documents in a collection and map the documents to a lower dimensional semantic space. By doing this, the information of words that are highly probable given
the documents can be used. However, this method requires signiﬁcant time to execute because
LSA must be applied to the entire collection and there may be tens of millions of documents. If
documents are added or removed, LSA must be performed again on the entire collection. Anotherdisadvantage of LSA is that it does not naturally infer the probabilities of unseen texts. In the
proposed method, each time search results are obtained, LDA must be performed (Section 4.3).
However, this does not take a long time because the number of documents in the search results
is much smaller than that in the entire collection. In addition, LDA can infer the probabilities
of unseen documents.

4.2

Acquisition of Initial Search Results

In the proposed method, we use a KL-divergence retrieval model (Laﬀerty and Zhai 2001)
to obtain the initial search results for a given query. For each document dh (h = 1, . . . , H)
in the collection Dall , a DIR-based document model PdDIR(·) is constructed in advance. For ahgiven query q, we construct the MLE-based query model PqM LE (·). Then, for each document
containing q in Dall , we compute the KL-divergence between the DIR-based document modeland the MLE-based query model. That is, we deﬁne the score of a document dh for a query q as
initial score(dh , q) = −KL(PqM LE (·)||PdDIR
(·)).
h

927

(9)

Journal of Natural Language Processing

Vol. 21 No. 4

September 2014

The initial search results Dq are obtained by ranking the documents according to their scores.
We use MLE to construct the query model (e.g., Zhai and Laﬀerty 2001). When a query model
is constructed using MLE, the ranking based on the KL-divergence retrieval model is equivalent
to that based on the query likelihood model (Ponte and Croft 1998).

4.3

Hybrid Document Model Construction

B
We construct a hybrid language model PdHY(·) for each document di (i = 1, . . . , I) in Dq .
i

In this model, we consider both the surface and latent information in the documents.
First, an LDA-based document model PdLDA(·) is constructed for each di . We perform LDA oni
Dq to infer the topic distribution in each di , and estimate the parameters αk , βk (k = 1, . . . , K)
and γi for each di . Then, we construct PdLDA(·) using the estimated parameters and Eq. (8). Asi
described in Section 3.2, PdLDA(·) is constructed on the basis of highly probable words given theilatent topics in di .
B
Next, for each di , we construct PdHY(·) by interpolating the constructed PdLDA(·) withii

PdDIR(·) as follows.
i
B
PdHY(w) = (1 − a)PdDIR(w) + aPdLDA
(w),
i
i
i

(10)

where 0 ≤ a ≤ 1. PdDIR(·) is constructed using the words that appear in di . By interpolatingithe two models, our method constructs a document model that contains the surface and latent
information in di .

4.4

Hybrid Feedback Model Construction

We construct a hybrid language model PFHY B (·) for user feedback. First, we perform LDA on
F to infer the topic distribution in F and estimate the variational parameters for F , as describedin Section 3.3. Then, we construct the LDA-based feedback model PFLDA (·) using the estimatedparameters and Eq. (8). Similar to PdLDA(·), PFLDA (·) is constructed on the basis of the highlyiprobable words from the latent topics in F . Finally, PFHY B (·) is constructed in the same mannerB
as PdHY(·).
i

PFHY B (w) = (1 − a)PFDIR (w) + aPFLDA (w),(11)

where PFDIR (·) is constructed using Eq. (2). By interpolating the two models, our method
constructs a feedback model that contains the surface and latent information in F .

928

Harashima and Kurohashi

4.5

Relevance Feedback using Surface and Latent Information in Texts

Re-ranking Search Results

We construct a new query model that is used to re-rank the initial search results Dq . The
new query model PqN EW (·) is constructed by interpolating the original query model PqM LE (·)
with the hybrid feedback model PFHY B (·) as follows:
PqN EW (w) = (1 − b)PqM LE (w) + bPFHY B (w),(12)

where 0 ≤ b ≤ 1.
B
Then, for each di in Dq , we compute the KL-divergence between PdHY(·) and PqN EW (·).
i

That is, the score of document di for query q (given feedback F ) is deﬁned asBre-ranking score(di , q, F ) = −KL(PqN EW (·)||PdHY
(·)).
i

(13)

Finally, we obtain the revised search results by re-ranking the documents in Dq according totheir scores.

5 Experiments
In this section, we present the results of experiments performed to evaluate the proposed
method.

5.1

Test Set

In the experiments, we used the test set from the Web Retrieval Task from the Third NTCIR Workshop (Eguchi, Oyama, Ishida, Kuriyama, and Kando 2002). The test set consistsof 11,038,720 Japanese web pages and 47 information needs.

For each information need,approximately 2,000 documents are rated as highly relevant, fairly relevant, partially relevant
or irrelevant. We can evaluate the ranking of search results using these annotated documents.
Figure 2 gives an example of an information need for the Web Retrieval Task. The meaningof each element is given below.

Fig. 2 Example information need from the Third NTCIR Workshop.

929

Journal of Natural Language Processing

Vol. 21 No. 4

September 2014

NUM Identiﬁcation number of the information need.
TITLE Query submitted to a search engine. Up to three words are provided, listed according
to importance.
DESC A description of the user’s information need in a single sentence.
RDOC Up to three identiﬁcation numbers referring to examples of documents that are relevantto this information need, listed according to importance.
In our experiments, we used the ﬁrst two terms in the ⟨TITLE⟩ tag as the query. We collectedeach document containing a query (Section 4.2). When we used all the terms in the ⟨TITLE⟩,
there were too few documents in the search results. For example, for identiﬁcation numbers 0027,
0047, and 0058, we could only obtain 17, 5, and 14 documents, respectively. For identiﬁcation
number 0061, we could not ﬁnd any documents. This caused unreliable evaluation results. In
other words, if an RF method improved the ranking of the initial search results, the improvement
was not reﬂected by evaluation measures such as precision at 10 (P@10), and we could not
determine how well the method performed. Thus, to obtain a suﬃcient number of documents,
we used only the ﬁrst two terms in the ⟨TITLE⟩ tag. It should be noted that greater than 100
documents was deﬁned as suﬃcient.
We used the documents in the ⟨RDOC⟩ tag as the user feedback. These are relevant documents
selected by assessors and can be treated as user feedback. They were not necessarily included in
the initial search results. In such cases, one may think that these documents should not be used
as user feedback. However, when we evaluated the RF method, we removed these documentsfrom the search results regardless of whether they were included in the initial results (Section 5.3).
In other words, whether these documents were included in the search results was not importantbecause we removed them from the initial search results and the re-ranked results.
We did not use seven of the information needs (identiﬁcation numbers: 0011, 0018, 0032,
0040, 0044, 0047, and 0061) because we were unable to retrieve a suﬃcient number of documents(i.e., 100 documents) for them even when using the ﬁrst two terms as the query. We divided theremaining 40 information needs into development and test data. The development data consistedof 8 information needs (identiﬁcation numbers 0008–0017), which were used to tune our method.
The test data consisted of 32 information needs (identiﬁcation numbers 0018–0063), which wereused to evaluate our method.

5.2

Search Engine

In these experiments, we implemented a search engine that obtained the initial search results
for a given query and re-ranked them using the proposed method. The details of the implemen930

Harashima and Kurohashi

Relevance Feedback using Surface and Latent Information in Texts

tation are as follows.
We used the 11, 038, 720 web pages in our test set as the collection (i.e., Dall ). Each document
was converted into the format presented by Shinzato, Kawahara, Hashimoto, and Kurohashi(2008). In this format, each sentence in a document was segmented into words. Each word wasgiven a representative form using JUMAN (Kurohashi, Nakamura, Matsumoto, and Nagao 1994),
a Japanese morphological analyzer. Then, we constructed the DIR-based document model foreach document. We set the smoothing parameter µ = 1, 000, which is consistent with previous
studies (Zhai and Laﬀerty 2001; Wei and Croft 2006; Yi and Allan 2009).
When given a query, we converted its terms into a representative form using JUMAN, constructed its MLE-based language model, and obtained the initial search results by ranking documents in the collection.
The LDA conﬁguration is given below. We set the initial values of αk (k = 1, . . . , K) to 1,
and the initial value of each βkj (k = 1, . . . , K, j = 1, . . . , J) to random values. The number of
iterations for the variational parameters and that for αk and βk were set to 10. We limited thesize of the vocabulary in LDA, denoted as J, to 100. We selected 100 words on the basis of theirimportance in the search results. Note that the importance of a word w to the search results Dq
is deﬁned as df (w, Dq )∗log(|H|/df (w, Dall )), where df (w, D) represents the document frequency
of w in documents D.

5.3

Evaluation Method

We removed the feedback documents from both the initial and re-ranked results. We canevaluate the performance of an RF method by comparing the initial search results with the reranked results. A common evaluation problem is how to handle documents that users have marked
as relevant (Hull 1993). If the initial and re-ranked results are compared in a straightforwardmanner, the latter have an advantage because documents that are known to be relevant tend to be
re-ranked higher. However, if we remove them from the re-ranked results, they are disadvantaged.
This is especially true if there are few relevant documents. Therefore, we removed the documents
used as user feedback from both results. This allowed us to make a fair comparison between theinitial and re-ranked results.
We evaluated the method using P@10, mean average precision (MAP), and normalized
discounted cumulative gain for the 10 top (re-)ranked documents (NDCG@10) (Järvelin andKekäläinen 2002). When calculating P@10 and MAP, documents that were rated as highly relevant, fairly relevant, and partially relevant were regarded as relevant, while documents rated
as irrelevant and unrated documents were regarded as irrelevant. When calculating NDCG, we
931

Journal of Natural Language Processing

Vol. 21 No. 4

September 2014assessed the relevance score of documents rated highly relevant, fairly relevant, and partiallyrelevant as 3, 2, and 1, respectively.

5.4

Performance of the Proposed Method

We examined the eﬀectiveness of the proposed method in re-ranking the initial search results
using explicit feedback. As described in Section 5.1, we used the test data and the ﬁrst two
terms in the ⟨TITLE⟩ as the query for each information need. We deﬁned the initial search
results as the 100 documents with the highest initial scores and then re-ranked them using the
proposed method. We used the ﬁrst two documents in the ⟨RDOC⟩ tag for each informationneed as the explicit feedback. The average number of words in a document was 3, 589. We
set (a, b, K) = (0.2, 0.9, 50) because this setting obtained the best results in the preliminary
experiment described in Section 5.6.
The results are listed in Table 1(a). INIT represents the ranking of the initial search results,
and OURS represents the re-ranked results using the proposed method. For comparison, we
also show the performance of some baseline methods, ZHAI represents the method by Zhai andLaﬀerty (2001) and OURS (a = 0.0) represents the proposed method without latent information.
ZHAI is essentially the same as OURS (a = 0.0). Both methods construct the feedback modelby modifying the surface word distribution of the feedback using that of the collection. The
diﬀerence lies in the way the word distribution is modiﬁed. The former uses an expectationmaximization algorithm for the modiﬁcation, while the latter uses DIR estimation. In OURS
(a = 0.0), we set b = 0.5. This value was determined in the preliminary experiment.
DIC also represents a baseline method. The proposed method uses information about words
that are highly probable given a text. Dictionaries of synonyms and related words can also
be used for this purpose. DIC is an extension of OURS (a = 0.0); DIC uses synonyms of theTable 1Comparative performance of the proposed method(a) Eﬀectiveness with respect to explicit RF

INIT
ZHAI
OURS (a = 0.0)
DIC
OURS

P@10
0.275
0.297
0.294
0.300
0.351

MAP
0.110
0.114
0.115
0.114
0.148

(b) Eﬀectiveness with respect to pseudo RF

NDCG@10
0.209
0.218
0.221
0.225
0.271

INIT
ZHAI
OURS (a = 0.0)
DIC
OURS

932

P@10
0.294
0.294
0.291
0.300
0.318

MAP
0.116
0.117
0.117
0.117
0.115

NDCG@10
0.233
0.242
0.239
0.245
0.260

Harashima and Kurohashi

Relevance Feedback using Surface and Latent Information in Texts

surface words from the feedback and search results. For this method, we constructed a synonym
dictionary from Japanese dictionaries using the method proposed by Shibata, Odani, Harashima,
Oonishi, and Kurohashi (2008). For the Japanese dictionaries, we used Reikai Shougaku Kokugo
Jiten (Tajika 2001) and Iwanami Kokugo Jiten (Nishio, Iwabuchi, and Mizutani 2002). The
constructed dictionary contained 4,597 entries (e.g., “computer” = “electronic brain”).
The results shown in Table 1(a) indicate that OURS outperformed INIT for all metrics. For
example, the proposed method improved the initial search results by 27.6% in P@10. These results
suggest that the proposed method eﬀectively re-ranked the initial search results. In addition, theproposed method outperformed ZHAI and OURS (a = 0.0), which do not use latent informationfrom texts. This suggests that latent information is useful when re-ranking search results.
We investigated further and conﬁrmed that the proposed method made good use of the words
that did not appear in the feedback but were considered highly probable. Consider the information need shown in Figure 2. The user feedback did not contain the words “religion,” “holiday,”or “bible,” which are related to the information need. As such, ZHAI and OURS (a = 0.0) could
not use these words. In contrast, these highly likely words had a certain degree of probability inthe hybrid language model even though the words did not appear in the feedback. For example,
the method could allocate the probabilities 0.0046, 0.0037, and 0.0024 to the words “religion,”“holiday,” and “bible,” respectively. The probabilities allocated to the words “Christmas” and“easter,” which appeared once in the feedback, were 0.0093 and 0.0060, respectively. Using theseprobabilities, the proposed method raised the score of documents that contained these words.
Although DIC outperformed ZHAI and OURS (a = 0.0), it did not outperform OURS.
This may be due to the coverage of the synonym dictionary. DIC may perform better if widecoverage synonym dictionaries are used. However, constructing such dictionaries is diﬃcult. The
proposed method also needs to know that a word is related to other words; however, unlike
DIC, it does not need any dictionaries. Using LDA, the proposed method dynamically acquires
the required knowledge from the search results. Consider the query “Mac price” described in
Section 1. Suppose that the search results contain words such as “CPU,” “HDD,” “hamburger,”and “potato.” Our method performs LDA on the search results and dynamically acquires theknowledge that “CPU” is related to “HDD,” and “hamburger” is related to “potato.” In addition,even if “HDD” does not appear in a document, the proposed method can assign a certain degreeof probability to the word from other related words, such as “CPU.” Thus, the proposed method
does not require any dictionaries.
The proposed method can also be applied to pseudo RF. In pseudo RF, the top n documentsin the initial search results are assumed to be relevant, and the search results are re-ranked on the933

Journal of Natural Language Processing

Vol. 21 No. 4

September 2014

basis of this assumption. We implemented pseudo RF using the proposed method for n = 10 andcompared the initial results with the re-ranked results. Note that there are no relevant documentsin pseudo RF. Thus, we evaluated the performance of each method using the raw (re-)ranked
results.
The evaluation results are shown in Table 1(b). The results for INIT in this table diﬀer fromthose in Table 1(a) because the documents used as feedback were not removed from the search
results. The proposed method improved the initial search results in P@10 and NDCG@10. For
example, the proposed method improved the initial search results by 8.2% in P@10. These results
demonstrate that the proposed method is a promising candidate for pseudo RF as well as explicit
RF.

5.5

Eﬀect of the Amount of Feedback

In the second experiment, we simulated a situation where only a small amount of user feedback
can be obtained. We investigated how the amount of feedback aﬀected the performance of the
proposed method. In practice, large quantities of user feedback are rarely available. Thus, an
RF method should perform well only when a small amount of user feedback is available. We
incrementally reduced the amount of explicit feedback and observed the change in P@10.
For this experiment, we used seven diﬀerent quantities of explicit feedback: G = 21 , 20 , 2−1 ,2−2 , 2−3 , 2−4 , and 2−5 relevant documents. Note that, for example, G = 21 means that we used
two relevant documents as user feedback. G = 2−1 represents the use of half a document, i.e.,
half the words from the feedback were randomly sampled and only these words were used for RF.
This allowed us to consider the case where part of a document (e.g., title or snippet) is given as
user feedback.
Figure 3 shows the eﬀect of the amount of feedback on the performance of the proposed
method. For comparison, we also present the results of the proposed method without the latent
information (OURS (a = 0.0)). INIT represents the precision of the ranking of the initial search
results. From Figure 3, it is evident that the proposed method performed consistently well. For
example, when one relevant document was given as user feedback, the proposed method improved
the initial search results by 24.5% in P@10. In addition, the proposed method achieved a 5.3%
improvement with only 2−5 documents. When G = 2−5 , there were on average 57 words in the
feedback, i.e., |F | was 57. On the other hand, when G was small, the improvements achieved
by OURS (a = 0.0) were negligible. As G becomes smaller, the amount of available surface
information becomes smaller and the method can not improve the initial search results. On theother hand, OURS uses both surface and latent information. Even when only a small amount934

Harashima and Kurohashi

Relevance Feedback using Surface and Latent Information in Texts

Fig. 3

Eﬀect of the amount of feedbackof feedback is available, OURS improved the initial search results because the method uses more
information.

5.6

Sensitivity to Parameters

The proposed method uses the following three parameters: a, b, and K. Parameter a controls
the reliability of an LDA-based language model in a hybrid language model. Parameter b controls
the reliability of a feedback model in a new query model, and parameter K represents the numberof topics. In our experiments, we set (a, b, K) = (0.2, 0.9, 50) for OURS and b = 0.5 for OURS
(a = 0.0). These values were determined in a preliminary experiment.
In the preliminary experiment, we re-ranked the initial search results using diﬀerent parametervalues and measured the changes in performance using the proposed method. We used thedevelopment data, applied our method with a and b ranging from 0.0 to 1.0 in steps of 0.1 andK ranging from 10 to 100 in steps of 10, and obtained the average of P@10 for all informationneeds. We used the ﬁrst two terms in the ⟨TITLE⟩ as the query and the ﬁrst two documents inthe ⟨RDOC⟩ as the user feedback.
The results of the preliminary experiment are shown in Table 2 and Figure 4. Table 2
summarizes the results with respect to (a, b). The value of each cell in the table is the averageof P@10 obtained for each K. For example, the value of cell (a, b) = (0.1, 0.2) denotes that the
average of P@10 obtained for (a, b, K) = (0.1, 0.2, 10), (0.1, 0.2, 20), . . . , (0.1, 0.2, 100) is 0.286.
The highest value in each column is shown in bold, and the highest value in each row is underlined.
As can be seen from the table, the proposed method achieved the best performance with935

Journal of Natural Language Processing

Vol. 21 No. 4

Table 2

a

0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

0.0
0.288
0.261
0.235
0.211
0.195
0.185
0.174
0.167
0.156
0.152
0.148

0.1
0.300
0.275
0.254
0.227
0.212
0.202
0.192
0.182
0.173
0.168
0.163

0.2
0.313
0.286
0.274
0.253
0.231
0.221
0.214
0.203
0.193
0.184
0.179

0.3
0.338
0.301
0.293
0.277
0.265
0.251
0.240
0.233
0.224
0.219
0.215

September 2014

Sensitivity to (a, b)

0.4
0.325
0.316
0.308
0.299
0.292
0.286
0.283
0.279
0.270
0.262
0.253

b
0.5
0.338
0.340
0.332
0.326
0.321
0.316
0.310
0.306
0.304
0.302
0.295

0.6
0.325
0.369
0.368
0.366
0.360
0.356
0.356
0.355
0.345
0.343
0.345

0.7
0.313
0.400
0.408
0.404
0.403
0.398
0.394
0.393
0.389
0.384
0.389

0.8
0.325
0.430
0.452
0.452
0.437
0.437
0.432
0.430
0.425
0.421
0.413

0.9
0.325
0.462
0.462
0.456
0.455
0.456
0.452
0.444
0.440
0.436
0.427

1.0
0.063
0.455
0.433
0.435
0.437
0.439
0.444
0.449
0.446
0.440
0.431

Fig. 4 Sensitivity to K(a, b) = (0.1, 0.9) or (0.2, 0.9). The results with a = 0.0 (not using latent information) demonstrate that the method performed well with b = 0.3–0.5. On the other hand, the results witha ≥ 0.1 (using latent information) demonstrate that the proposed method performed well withb = 0.8–1.0. The value of b (and the performance with this b) with a ≥ 0.1 is greater than thatwith a = 0.0. This result suggests that latent information increases the reliability of the feedback
model.
Figure 4 illustrates the eﬀect of K on the performance of the proposed method. For clarity,
we only show the results with (a, b) = (0.1, 0.9), (0.2, 0.9), and (0.3, 0.9), which produced good936

Harashima and Kurohashi

Relevance Feedback using Surface and Latent Information in Texts

results (Table 2). According to the result presented in Figure 4, the proposed method performed well with K = 50–70. These results indicate that the proposed method achieves the best
performance with (a, b) = (0.1, 0.9) or (0.2, 0.9), and K = 50–70.

5.7

Execution TimeIn the proposed method, we perform LDA on the search results to construct an LDA-based
document model for each document. We also perform LDA on the feedback to construct an
LDA-based feedback model. Here, we report the execution times of these procedures.
In our experiments, the proposed method took 13.1–16.0 secs to perform LDA on the search
results (100 documents). Note that we implemented LDA using Perl and C. We believe that thisis an acceptable execution time because users typically browse documents in search results toselect relevant documents. This process generally takes at least 1 min. In other words, we canperform LDA on the search results while the users are browsing the documents. Thus, LDA canbe completed before the users re-rank the initial search results.
However, the number of retrieved documents is sometimes greater than 100. If a large numberof documents is retrieved, LDA requires a signiﬁcant amount of time to execute. One way to avoid
this problem is to use only the top ranked documents as the search results. The time requiredfor LDA is not a matter of concern if we use the top 100 documents. Another alternative is toparallelize the estimation of the variational parameters in LDA, a process that takes the majorityof the execution time. Variational parameters for each document are independent of those forother documents. Thus, we can parallelize the estimation of the parameters and reduce the timerequired for the procedure. For example, Nallapati, Cohen, and Laﬀerty (2007) achieved a 14.5
times speedup using 50 cluster nodes. Therefore, it is expected that we can reduce the execution
time based on these studies.
It took less than 1 sec to perform LDA on the feedback. For example, the execution time wasonly 0.1–0.2 secs when using two documents as feedback. Thus, the time required to perform
LDA on the feedback is negligible.

6 Conclusion
We have proposed an RF method using surface and latent information from texts and investigated its eﬀectiveness. Using LDA, our method infers the distributions over words that arehighly probable given the user feedback and each document in the search results. Then, a hybrid
word distribution is constructed by interpolating the latent word distribution with the surface
937

Journal of Natural Language Processing

Vol. 21 No. 4

September 2014

word distribution for the feedback and each document. Finally, documents whose hybrid word
distributions resemble the feedback are regarded as relevant to the user’s information need, andare re-ranked higher. Through our experiments, we conﬁrmed that the proposed method performs well for both explicit and pseudo RF. The proposed method also performs well when onlya small amount of feedback is available.
In future, we intend to use negative feedback in the proposed method. In this study, only
use positive feedback (relevant documents for a query) was used for re-ranking search results;
however, we believe that negative feedback (irrelevant documents) can also be useful.

Reference
Blei, D. M., Ng, A. Y., and Jordan, M. I. (2003). “Latent Dirichlet Allocation.” Jounal of
Machine Learning Research, 3, pp. 993–1022.
Eguchi, K., Oyama, K., Ishida, E., Kuriyama, K., and Kando, N. (2002). “The Web Retrieval
Task and its Evaluation in the Third NTCIR Workshop.” In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information
Retrieval (SIGIR 2002), pp. 375–376.
Fei-Fei, L. and Perona, P. (2005). “A Bayesian Hierarchical Model for Learning Natural Scene
Categories.” In Proceedings of the 2005 IEEE Computer Society Conference on Computer
Vision and Pattern Recognition (CVPR 2005), pp. 524–531.
Griﬃths, T. L. and Steyvers, M. (2004). “Finding scientiﬁc topics.” In Proceedings of the National
Academy of Sciences of the United States of America (NAS), pp. 5228–5235.
Heidel, A., Chang, H., and Lee, L. (2007). “Language Model Adaptation using Latent Dirichlet
Allocation and an Eﬃcient Topic Inference Algorithm.” In Proceedings of the 8th Annual
Conference of the International Speech Communication Association (INTERSPEECH 2007),
pp. 2361–2364.
Hofmann, T. (1999). “Probabilistic Latent Semantic Analysis.” In Proceedings of the 15th
Conference on Uncertainty in Artificial Intelligence (UAI 1999), pp. 289–296.
Hull, D. (1993). “Using Statistical Testing in the Evaluation of Retrieval Experiments.” In
Proceedings of the 16th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 1993), pp. 329–338.
Ide, E. (1971). “New Experiments in Relevance Feedback.” In The SMART Retrieval System:
Experiments in Automatic Document Processing, pp. 337–354. Prentice-Hall Inc.
Jansen, B. J., Spink, A., and Saracevic, T. (2000). “Real Life, Real Users, and Real Needs: A
938

Harashima and Kurohashi

Relevance Feedback using Surface and Latent Information in Texts

Study and Analysis of User Queries on the Web.” Information Processing and Management,
36 (2), pp. 207–227.
Järvelin, K. and Kekäläinen, J. (2002). “Cumulated Gain-Based Evaluation of IR Techniques.”
ACM Transactions on Information Systems, 20 (4), pp. 422–446.
Kurohashi, S., Nakamura, T., Matsumoto, Y., and Nagao, M. (1994). “Improvements of JapaneseMorphological Analyzer JUMAN.” In Proceedings of the International Workshop on Sharable
Natural Language Resources (SNLR), pp. 22–28.
Laﬀerty, J. and Zhai, C. (2001). “Document Language Models, Query Models, and Risk Minimization for Information Retrieval.” In Proceedings of the 24th Annual International ACM
SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2001),
pp. 111–119.
Lavrenko, V. and Croft, W. B. (2001). “Relevance-Based Language Models.” In Proceedingsof the 24th Annual International ACM SIGIR Conference on Research and Development inInformation Retrieval (SIGIR 2001), pp. 120–127.
Minka, T. P. (2000). “Estimating a Dirichlet distribution.” Tech. rep., Microsoft.
Nallapati, R., Cohen, W., and Laﬀerty, J. (2007). “Parallelized Variational EM for Latent
Dirichlet Allocation: An Experimental Evaluation of Speed and Scalability.” In Proceedingsof the 7th IEEE International Conference on Data Maining Workshops (ICDMW 2007),
pp. 349–354.
Nishio, M., Iwabuchi, E., and Mizutani, S. (2002). Iwanami Kokugo Jiten. Iwanami Shoten.
Ponte, J. M. and Croft, W. B. (1998). “A Language Modeling Approach to Information Retrieval.”
In Proceedings of the 21nd Annual International ACM SIGIR Conference on Research andDevelopment in Information Retrieval (SIGIR 1998), pp. 275–281.
Rocchio, J. J. (1971). “Relevance Feedback in Information Retrieval.” In The SMART Retrieval
System: Experiments in Automatic Document Processing, pp. 313–323. Prentice-Hall Inc.
Salton, G., Wong, A., and Yang, C.-S. (1975). “A Vector Space Model for Automatic Indexing.”
Communications of the ACM, 18 (11), pp. 613–620.
Shibata, T., Odani, M., Harashima, J., Oonishi, T., and Kurohashi, S. (2008). “SYNGRAPH: A
Flexible Matching Method Based on Synonymous Expression Extraction from an Ordinary
Dictionary and a Web Corpus.” In Proceedings of the 3rd International Joint Conference on
Natural Language Processing (IJCNLP 2008), pp. 787–792.
Shinzato, K., Kawahara, D., Hashimoto, C., and Kurohashi, S. (2008). “A Large-Scale Web Data
Collection as a Natural Language Processing Infrastructure.” In Proceedings of the 6th International Conference on Language Resources and Evaluation (LREC 2008), pp. 2236–2241.
939

Journal of Natural Language Processing

Vol. 21 No. 4

September 2014

Spärck Jones, K., Walker, S., and Robertson, S. E. (2000). “A Probabilistic Model of Information Retrieval: Development and Comparative Experiments.” Information Processing andManagement, 36 (6), pp. 779–808, 809–840.
Tajika, J. (2001). Sanseido Reikai Shougaku Kokugo Jiten. Sanseido.
Wei, X. and Croft, W. (2006). “LDA-Based Document Models for Ad-hoc Retrieval.” In Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development
in Information Retrieval (SIGIR 2006), pp. 178–185.
Yi, X. and Allan, J. (2009). “A Comparative Study of Utilizing Topic Models for Information
Retrieval.” In Proceedings of the 31st European Conference on Information Retrieval (ECIR2009), pp. 29–41.
Zhai, C. and Laﬀerty, J. (2001). “Model-based Feedback in the Language Modeling Approach
to Information Retrieval.” In Proceedings of the 20th ACM Conference on Information andKnowledge Management (CIKM 2001), pp. 403–410.
Zhai, C. and Laﬀerty, J. (2004). “A Study of Smoothing Methods for Language Models Applied
to Information Retrieval.” ACM Transactions on Information Systems, 22 (2), pp. 179–214.
Zhou, D. and Wade, V. (2009).

“Latent Document Re-Ranking.”

In Proceedings of the2009 Conference on Empirical Methods in Natural Language Processing (EMNLP 2009),
pp. 1571–1580.

Jun Harashima: received his B.Eng. in 2007, and M.Sc. and Ph.D. in Informatics in 2009 and 2013, from Kyoto University. He is currently employed as
an engineer at COOKPAD Inc. His research interests include natural language
processing and information retrieval.
Sadao Kurohashi: received his Ph.D. in Electrical Engineering from Kyoto
University in 1994. He is currently a professor of the Graduate School of Informatics at Kyoto University. His research interests include natural language
processing, knowledge acquisition/representation, and information retrieval.
(Received December 2, 2011)(Revised March 6, 2012)(Accepted May 14, 2012)940