Query Expansion with the Minimum Judgement
Masayuki Okabe† and Seiji Yamada††
Query expansion is one of feedback techniques in information retrieval, which needs a certain amount of relevance information that costs high in terms of human effort. In this paper
we propose a method of query expansion which utilizes human help but with the minimum
cost. Our purpose is to reduce users’ cost when judging the relevancy of documents as much as
possible using Transductive Learning. We describe this learning method is used to predict therelevancy of documents with no manual judgement based on only a fraction of true relevance
information. We also show the role of the learning in our query expansion procedure. Compared with traditional query expansion methods, our method show the distinct effectivenessof query expansion, especially in the top 10 or 20 documents.

a user. In this paper we present the potential performance of user feedback with the minimum judgement in the case of query expansion. Compared with traditional query expansion methods, our method differs in the procedure of finding relevant documents. Althoughtraditional ones depend on a user efforts in thisprocedure, our method uses transductive learning and try to reduce much of the user’s effort.
Since our method extends only that procedure,it can be embedded in the most of query expansion methods.
In practical situation using relevance feedback, the initial retrieval documents usually include few relevant ones, thus effective feedback
is not available in most cases. To cope withthis problem, Onoda et. al6) tried to apply
one-class SVM(Support Vector Machine) to relevance feedback. Using one-class SVM, an IR
system is able to utilize non-relevant documents
only to improve accuracy of retrieve. This approach is similar to ours in terms of appliying amachine learning method to reduce user’s costin IR, however their study does not utilize query
expansion and the minimum judgement.
The reminder of this paper is structured asfollows. In section 2 we describe the two fundamental techniques for our query expansion
method. In section 3 we explain the procedure of our method which builds transductive
learning into normal expansion procedure. In
section 4 we compared the effectiveness of our
method with two other traditional query expansion methods. In section 5 we investigate theresult of each topic in detail. In settion 6 wesummarize our findings.

1. Introduction
Query expansion is a sort of techniques tohelp a user re-formulate queries in IR (Information Retrieval) systems. Many of query expansion methods use relevance information fromthe user to perform expansion well1) . For thosemethods, the quality of query expansion significantly depends on the amount of assessed
documents which are judged relevant or nonrelevant by a user. However such informationis generally too expensive to be elicited a lot
from a user as discussed in many retrieval experiments2)∼4) . We consider appling machinelearning techniques to IR systems is one solution of the problem, especially Transductive
Learning5) is well-suited to the situation wherea lot of relevance information cannot be expected. In contrast to normal inductive learning, the advantage of this learning method is
to utilize unlabeled data for complementing thelack of labeled data. In our case, labeled data
corresponds to the relevant documents given bya user, and unlabeled data corresponds to the
documents whose relevancy is unknown. To
utilize the similarity between labeled and unlabeled documents, this learning method try to
predict the relevancy of unlabeled documentswith more accuracy even based on a fraction oftrue relevance information.
So far, many of query expansion methods aredeveloped, however they haven’t paid much attention to the cost of relevancy judgement by† Toyohashi University of Technology†† National Institute of Informatics

1

Table 1 Term’s score for query expansion³

wpqt =rtnt
R
N

XVTCKPYVTCKP

Learner

:
:
:
:

rt
nt −rtR − N −R´

t +0.5)/(R−rt +0.5)∗ log (nt −r(rt +0.5)/(N −nt −R+rt +0.5)

the number of seen relevant documents containing term t
the number of documents containing t
the number of seen relevant documents for query q
the number of documents in the collectionModel

XVTCKPYVTCKP

YVGUV

XVGUV

Learner

Model

YVGUV

XVGUV
Fig. 2 Transductive Learning

Fig. 1 Inductive Learning

Xtrain ⊂ X and labels Ytrain ⊂ Y are given
as training examples. Learner will produce amodel to predict labels for the rest of data
points Xtest (test examples). Using the modelin inference phase, we can finally get those labels Ytest as shown in Fig.1.
In contrast to the inductive learning, transductive learning uses not only Xtrain but also
Xtest in the learning phase as shown in Fig.2.
More over, inference phase is not separated
from learning. Learning and inference are conducted at the same time in transductive setting.
Transductive learner presume labels of test
examples using some similarity between labeled
and unlabeled data points in order to complement the lack of training examples. Transductive learning is well-suited to the setting that
|Xtrain | is very small.
So far, several transductive learning methods realizing the above concept have been proposed12) . Spectral Graph Transducer is oneof such methods, and showed the best performance against k-nearest neighbor and transductive support vector machine. This learning
method is a transductive version of k nearestneighbor classifier, which defines the problemof labeling unlabeled examples as an optimization problem and solves it as normalised graphcuts with constraints. Since this method provides good approximation to the solution forthe constrained ratiocut problem, the computational cost of learning is not so high. We use
SGT as a transductive learner in our query expansion system.

2. Basic Methods
Our query expansion method is based on two
basic techniques. We explain them in this section.
2.1 Query Expansion
While various query expansion techniques areproposed so far7)∼9) , wpq method is often used
as a standard method1),10) . We use this method
as our basic query expansion techniques for the
discussion in this paper. It calculates the scoreof each term appeared in relevant documents
based on the formula shown in Table 1. The
second term in this formula is called the Rebertson/Spark Jones weight11) . As seen in thisformula, score of a term depends on the numberof relevant documents which are usually given
by a user. The quality of those information
affects the quality of terms selected as query
expansion.
2.2 Transductive Learning
The setting of transductive learning is almost
the same as the normal inductive learning. The
learning task is defined on a data set X of npoints (~x1 , ~x2 , ..., ~xn ). Each data point has adisired classification label Y = (y1 , y2 , ..., yn ).
if we assume data points as documents, ~xi isa document vector and yi is a relevance judgement. For simplicity, we set the labels yi arebinary, i.e. yi ∈ {+1, −1}. +1 and −1 means
relevant and non-relevant respectively.
Normal inductive learning consists of twophases, learning phase and inference phase. In
the learning phase, a subset of data points

2

+PKVKCNSWGT[+PHQTOCVKQP4GVTKGXCN
5[UVGO*KV.KUV٤FQEWOGPVFQEWOGPV
FQEWOGPV
FQEWOGPV

7UGT,WFIGOGPV

6TCPUFWEVKXG
+PHGTGPEGGZRCPFGFSWGT[

SWGT[GZRCPUKQP

Fig. 3 Query Expansion Procedure

In the hit-list of Fig.3, a dashed circleof ranked in the 20th document and adashed cross ranked in the 50th document
represent judgements by transductive inference.

3. Query Expansion Procedure
Fig.3 shows the procedure of our query expansion system. We explain each step in the
figure.
( 1 ) Initial Search: A user gives a query to
Information Retrieval System.

( 4 ) Select terms to expand initial query:
Based on the formula described in section
2, our system calculates the score of terms
in relevant documents found in the previous step, and selects a certain number of
expansion terms.

( 2 ) Judgement of Documents in HitList: IR system returns a hit-list indicating the retrieval documents ranked
in the ordering of relevance. The user
checks the contents from the top ranked
document in the hit-list, judging whether
those documents are positive(relevant) or
negative(non-relevant) until he/she willfind at least one each relevant and nonrelevant example.
While the most of other relevance feedback and query expansion systems assumes that a user marks ’relevant’ or’non-relevant’ more than 20 documents,
it is very unrealistic setting because mostof the users are lazy to give a mark toeach document.

( 5 ) Re-input of expanded query and thenext search: New hit-list are shown tothe user by inputting the expanded query.
In the above procedures, we naturally introduced transductive learning
into query expansion as the effective way
to automatically generate a lot of relevant
documents. Thus we do not need to modify a basic query expansion procedure andcan fully utilize the potentioal power ofthe basic query expansion.
The computational cost of transductive learning is not so much. Actuallytransductive learning takes a few seconds
to label 100 unlabeled documents andquery expansion with all the labeled documents takes also a few seconds, Thus
our system can expand queries sifficiently
quick in practical application.

( 3 ) Learning to mark unlabeled documents: Using transductive learning, unlabeled documents are marked their relevance judgements based on a few correct markings by the user. Our system
assumes those documents which are originally unlabeled but finally labeled bytransductive learning documents as correct documents when the system calculates the score of terms for expansion.

4. Experiments
In this section, we provide empirical evidence
on how our query expansion method can be3the test data set whose relevancy is unknowm
beforehand.

used to improve the performance of information retrieval. We compare our method withsome other traditional methods.
4.1 Settings[Data set and Retrieval system] We choose
Okapi13) as the retrieval system and TREC814) as the data set. TREC-8 contains about
520,000 documents extracted from the databaseof “Foreign Register”, “Financial Times”, “LosAngels Times” and “Foreign Broadcast Information Service”. As a preprocessing, we removed stopwords and applied stemming foreach document. We use 50 topics (No.401-450)
from TREC-8 Ad-Hoc track as queries for evaluation. Each topic has a TOPIC field in its
description and we use all of the terms appearing in that filed as a initial query.
We use BM25 in Okapi for the weight function. It is of the formX
(k1 + 1)tf (k3 + 1)qtf(1)w(1) ·(K + tf )(k3 + qtf )[Other Methods] We compared our query expansion method with two other methods described below.
normal : This method simply uses only one relevant documents judged by hand. This is sometimes called incremental relevance feedback2),3) .
We represent this method as normal in the following description.
pseud : This method is called pseud relevance
feedback, which assumes top n documents as relevant ones. we set 30 for n in our experiments.
30 is the best value in our preliminary experiments. We represent this method as pseud inthe following description.
4.2 Results
Table 2 shows the precision of top n(=10∼100)
ranked documents obtained after query expansion. Each value is averaged by topics. In thistable, sgt-0.1 represents our proposed method
using spectral graph tranceducer. 0.1 is an estimate value of the number of true relevant documents in training and test data set. This value
is one of the parameters of the sgt learning machine. We tested 0.1∼0.9 for this parameter andfound 0.1 is the best value in our experiment unless we change this value for each topic. Actully
the optimal values are different from topics andfrom the number of expansion terms. Althoughpractically it’s not easy to estimate the optimalvalue for each topic before query expansion, weshow the result in the case that we could findthe optimal value for each topic. We represent
it sgt-opt. For comparison, we also show theperformance of initial retrieval(represented asinit) in the table.
The results show that only our method
achieves the meaningful improvements since remaining two methods show few improvements
or get worse than initial retrieval. The numbers {nqe = 2,4,6,8,10} next to the name ofeach method in table 2 are the number of added
terms to initial query. This number does nothave much effect on the performance of retrieval
in each method. Our method shows good performance especially in the upper part of top
100 ranking. Since top 10 or 20 ranking is very
important in practical retrieval situation, thisproperty is useful for actual IR systems.

T ∈Q

where Q is a query containing terms T , tf isthe frequency of occurrence of the term withina specific document, qtf is the frequency of theterm within the topic from which Q was derived, and w(1) is the Robertson/Spark Jones
weight of T in Q described in section 2. In (2),
K is calculated
¶
µ by
dl
(2)
K = k1 (1 − b) + b
avdl
where dl and avdl denote the document lengthand the average document length measured insome suitable unit, such as word or sequenceof words. In our experiments, we set k1 =1.2, k3 = 1000, b = 0.75, and avdl = 135.6.
[Relevance Judgements] As described before, we only use the relevance information of
one top ranked relevant and non-relevant document. If we find none of relevant or nonrelevant document within top 10 documents,
we exclude those topics from evaluation because
we cannot apply our proposed method for such
topics. There are 9 exceptive topics in our experiments.
[Training and Test data] We use top 100
documents as Training and Test data for transductive learning. Training data is a set of two
documents whose relevance information can be
known manually. Remaining 98 docuemnts are4

normalpseud

sgt-0.1

sgt-opt

nqe
2
4
6
8
10
2
4
6
8
10
2
4
6
8
10
2
4
6
8
10

init

Used as relevant
True relevant
Accuracy

Table 2 Precision of Top n ranking after query expansion
Top n Ranking
10
20
30
40
50
60
70
80
0.393
0.332
0.281
0.251
0.239
0.226
0.214
0.203
0.383
0.312
0.271
0.237
0.218
0.215
0.204
0.195
0.393
0.304
0.267
0.241
0.216
0.198
0.188
0.180
0.390
0.290
0.254
0.227
0.209
0.195
0.182
0.173
0.407
0.307
0.252
0.232
0.210
0.198
0.186
0.175
0.405
0.348
0.308
0.273
0.250
0.236
0.218
0.205
0.434
0.370
0.324
0.291
0.273
0.253
0.238
0.226
0.456
0.373
0.337
0.307
0.280
0.262
0.246
0.231
0.459
0.387
0.344
0.307
0.285
0.265
0.249
0.234
0.461
0.376
0.330
0.304
0.287
0.264
0.252
0.239
0.510
0.404
0.357
0.316
0.288
0.265
0.247
0.233
0.515
0.413
0.351
0.313
0.282
0.261
0.244
0.227
0.532
0.423
0.352
0.314
0.292
0.270
0.248
0.234
0.537
0.434
0.364
0.326
0.297
0.277
0.256
0.239
0.539
0.422
0.366
0.328
0.302
0.271
0.257
0.240
0.622
0.485
0.414
0.373
0.343
0.322
0.299
0.278
0.654
0.516
0.440
0.391 0.350 0.326 0.304 0.283
0.661
0.501
0.416
0.370
0.341
0.313
0.285
0.267
0.661
0.507
0.429
0.387
0.346
0.315
0.287
0.267
0.673
0.512
0.434
0.383
0.345
0.316
0.294
0.275
0.441
0.362
0.307
0.284
0.266
0.248
0.235
0.224

90
0.191
0.187
0.172
0.166
0.167
0.198
0.212
0.217
0.221
0.228
0.222
0.217
0.219
0.226
0.227
0.262
0.266
0.249
0.252
0.256
0.207

Table 3 The number of documents used as relevant and its accuracy
normalpseud
sgt-0.1
sgt-opt(2)sgt-opt(4)sgt-opt(6)sgt-opt(8)
1.00
30.00
8.93
23.81
22.10
23.54
27.49
1.00
9.90
4.90
8.68
8.95
8.98
10.00
1.00
0.33
0.52
0.47
0.47
0.46
0.47

In our setting, the performance depends on
the way to assume the relevancy of unjudged
documents because the information of one relevant document is too few to select good terms
for query expansion. It is obvious that theamount and the accuracy of true relevant documents are important factor to make query expansion effective. Thus we investigated thenumber of true relevant documents and calculate its accuracy in each method. We alsocount the number of documents used as relevant. Table 3 shows the result(for sgt-opt(n), n
is the number of expanded terms). In the table,
we can see that normal has perfect accuracy,
however its amount of true relevant documents
is only one. In contrast, pseud has enoughamount of true relevant documents, however
its accuracy is low. Compared with those two
methods, our method is not biased one way inthe tradeoff. If we can appropriately estimate
the number of true relevant documents, we canmake query expansion very effective. As shownin the table, sgt-opt can find twice amount oftrue relevant documents with its accuracy keep
about the same as sgt-0.1.

100
0.182
0.181
0.166
0.162
0.162
0.191
0.202
0.207
0.210
0.217
0.210
0.208
0.209
0.214
0.215
0.248
0.252
0.238
0.240
0.242
0.198

sgt-opt(10)
26.95
10.22
0.49

5. Discussion
We investigated the results in detail, especially how each topic changes its performance
before and after query expansion. Fig.4 shows
the precision improvement in the top 10 documents against initial retrieval about each topic(6 terms expanded). Horizontal line in eachgraph means nth topic in the TREC-8 dataset.
More than half of topics in normal andpsued get worse by query expansion. Query
expansion works for only a few topics. In case ofsgt, topics can be segmented two groups. One
is a group in which query expansion works very
well, the other is a group in which query expansion degenerates retrieval performace. Thisis because misestimate of the number of true
relevant document is input to the sgt learner.
If we can set appropriate estimate values for theparameter, much of the second group of topics
decrease as seen in the graph of sgt-opt.
6. Conclusion
In this paper we proposed a new query expansion method which applies transductive learn-5normalpseud
1Precision difference

Precision difference

1

0.5

0

-0.5

-1

0.5

0

-0.5

-1
401

410

420

430

440

450

401

410

420

Topicssgt-0.1

440

450

430

440

450

sgt-opt1
Precision difference

1
Precision difference

430
Topics

0.5

0

-0.5

-1

0.5

0

-0.5

-1
401

410

420

430

440

450

Topics

401

410

420
TopicsFig. 4 Precision improvement in the the top 10 documents against initial
retrieval (6 terms expanded)ing to predict the relevancy of unlabeled documents. The experimental results showed our
method outperforms initial retrieval and othertraditional methods. We are now developping an algorithm to automatically estimate thenumber of true relevant documents in learning
data sets, which is very important factor forthe performance of query expansion as shownin this paper.

relevance feedback document retrieval, CIS
2004 Proceedings, IEEE, page to appear (2004).
7) Mitra, M., Singhal, M. and Buckley, C.: Improving automatic query expansion, SIGIR ’98
Proceedings, ACM, pp.206–214 (1998).
8) Xu, J. and Croft, W. B.: Query expansion using local and global document analysis, SIGIR’96 Proceedings, ACM, pp.4–11 (1996).
9) Lam-Adesina, A. M. and Jones, G. J. F.: Applying summarization techniques for term selection in relevance feedback, SIGIR 2001 Proceedings, ACM, pp.1–9 (2001).
10) Yu, S. and et al.: Improving pseud-relevance
feedback in web information retrieval using web
page segmentation, WWW 2003 Proceedings(2003).
11) Robertson, S. E.: On term selection for query
expansion, Journal of Documentation, Vol.46,
No.4, pp.359–364 (1990).
12) Joachims, T.: Transductive learning via spectral graph partitioning, ICML 2003 Proceedings, pp.143–151 (2003).
13) Robertson, S. E.: Overview of the okapi
projects, Journal of the American Society
for Information Science, Vol.53, No.1, pp.3–7(1997)
14) Voorhees, E. and Harman, D.: Overview of theeighth Text REtrieval Conference (1999).

References
1) Ruthven, I.: Re-examining the Potential Effectiveness of Interactive Query Expansion,
SIGIR 2003 Proceedings, ACM, pp. 213–220(2003).
2) Aalbersberg, I. J.: Incremental relevance feedback, SIGIR ’92 Proceedings, ACM, pp.11–22(1992).
3) Allan, J.: Incremental relevance feedback for
information filtering, SIGIR ’96 Proceedings,
ACM, pp.270–278 (1996).
4) Iwayama, M.: Relevance feedback with a small
number of relevance judgements: Incremental
relevance feedback vs. document clustering, SIGIR 2000 Proceedings, ACM, pp.10–16 (2000).
5) Vapnik, V.: Statistical learning theory, Wiley(1998).
6) Onoda, T., Murata, H. and Yamada, S.: Non-6