Interactive Document Retrieval with Active Learning

Takashi ONODA, Hiroshi MURATA
Central Research Institute of Electric Power Industry
2-11-1 Iwato-kita, Komae, Tokyo 201-8511, JAPANE-mail: fonoda, muratag@criepi.denken.or.jp
Seiji YAMADA
National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda, Tokyo 101-8430, JAPANE-mail: seiji@nii.ac.jp
is called relevance feedback[11] and used widely in IR
systems. In this method, a user directly evaluates
whether a document is relevant or no-relevant in alist of retrieved documents, and a system modi es thequery vector using the user evaluation. A traditional
way to modify a query vector is a simple learning rule
to reduce the di erence between the query vector anddocuments evaluated as relevant by a user.
Another approach has been proposed that classication learning with relevant and no-relevant document vectors as positive and negative examples
for a target concept[8]. Some studies proposed
SVM(Support Vector Machine) with excellent ability
to classify examples into two classes is applied to classi cation learning of relevance feedback[15][3].
We propose a relevance feedback framework with
SVM as active learning. In contrast that a conventional relevance feedback system indicates a user a listof the most relevant documents, our system provides
a user a list of documents which are hard for SVM
to classify them. This is a kind of active learning
approach and we consider it promising for relevance
feedback.
Okabe and Yamada[8] proposed a frame work inwhich relational learning to classi cation rules wasapplied to interactive document retrieval. Since thelearned classi cation rules is described with symbolic
representation, they are readable to our human andwe can easily modify the rules directly using a sort ofeditor. However we consider SVM dealing with continuous values can do more precise classi cation thansymbolic classi cation rules.
The relevance feedback is similar to what is termed
active learning in that we try to maximize test performance using the smallest number of documents in the
training set[15]. In active learning, we are interested
in maximizing learning performance. Drucker et al.

Abstract
We investigate the following data mining problem
from Information Retrieval: From a large data setof documents, we need to nd those that bind to human interesting in as few iterations of human testingor checking as possible. In each iteration a comparatively small batch of documents is screened for binding
the human interesting. We apply active learning techniques for selecting successive batches.
1 Introduction

As progression of the internet technology, accessible information by end users is explosively increasing. In this situation, we can now easily accsess ahuge document database through the WWW. However it is hard for a user to retrieve relevant documentsfrom which he/she can obtain useful information, anda lot of studies have been done in IR(Information
Retrieval), especially document retrieval[19]. Active
works for such document retrieval have been reported
in TREC(Text Retrieval Conference)[16] for English
documents, IREX(Information Retrieval and Extraction Exercise)[4] and NTCIR(NII-NACSIS Test Collection for IR System)[7] for Japanese documents.
In most frameworks for information retrieval, a vector space model in which a document is described witha high-dimensional vector is used[12]. An IR systemusing a vector space model computes the similarity
between a query vector and document vectors by cosine of the two vectors and indicates a user a list of
retrieved documents.
In general, since a user hardly describes a precise
query in the rst trial, interactive approach to modify
the query vector by evaluation of the user on documents in a list of retrieved documents. This method1applied SVM to the relevance feedback[3]. They areinterested in maximizing the number of relevant documents which are displayed to users at each feedback iteration. However, we are interested in satisfying boththe aim of active learning and the aim of increasing
the number of relevant documents which are displayed
to users at each feedback iteration. The detail of thisdi erence will be described in the third section.
In the remaining parts of this paper, we explain a
SVM algorithm in the second section brie y, and an
active learning with SVM for the relevance feedbackin the third section. In the fourth section, in order toevaluate the e ectiveness of our approach, we madeexperiments using a TREC data set of Las Angels
Times and discuss the experimental results. Eventually we conclude our work and discuss open problem
in the fth section.

where z = (x ; y ) and(z ; f ) = y f (x );(2)and f is the linear discriminant function in some feature space
i

%=

i

min (z ; f )
i

i

y

i i

b;

i

i=1

`
i=1

y

i i

i

tity 8 denotes the mapping from input space X by
explicitly transforming the data into a feature space
F using 8 : X ! F . (see Figure 1). SVM can doso implicitly. In order to train and classify, all that
SVMs use are dot products of pairs of data points
8(x); 8(x ) 2 F in feature space (cf. Eq. (3)). Thus,
we need only to supply a so-called kernel function thatcan compute these dot products. A kernel function kallows to implicitly de ne the feature space (Mercer's
Theorem, e.g. [2]) viak (x; x ) = (8(x) 1 8(x )):(4)
By using di erent kernel functions, the SVM algorithm can construct a variety of learning machines,
some of which coincide with classical architectures:iiiPolynomial classi ers of degree d:k (x; xi ) = ( 1 (x 1 xi ) + 2)d(5)Neural networks(sigmoidal):k (x; xi ) = tanh( 1 (x 1 xi ) + 2)

(6)

 0 kx 0 x k (7)Radial basis function classi ers:k (x; xi ) = exp

i



2

Note that there is no need to use or know the formof 8, because the mapping is never performed explicitly The introduction of 8 in the explanation above
was for purely didactical and not algorithmical purposes. Therefore, we can computationally a ord towork in implicitly very large (e.g. 1010 - dimensional)
feature spaces. SVM can avoid over tting by controlling the capacity and maximizing the margin. Simultaneously, SVMs learn which of the features implied by the kernel k are distinctive for the two classes,
i.e. instead of nding well-suited features by ourselves(which can often be dicult), we can use the SVM toselect them from an extremely rich feature space.
With respect to good generalization, it is often profitable to misclassify some outlying training data points

ii=1;:::;`iX̀ (8(x ) 18(x))+ (3)with w expressed as w = P
8(x ). The quanf (x) = (w 1 8(x))+ b =Formally, the Support Vector Machine (SVM) [17]like any other classi cation method aims to estimate
a classi cation function f : X ! f61g using labeledtraining data from X 2 f61g. Moreover this function
f should even classify unseen examples correctly.
In order to construct good classi ers by learning,
two conditions have to be respected. First, the training data must be an unbiased sample from the same
source (pdf) as the unseen test data. This concerns
the experimental setup. Second, the size of the classof functions from which we choose our estimate f ,the so-called capacity of the learning machine, has tobe properly restricted according to statistical learning theory [17]. If the capacity is too small, complex
discriminant functions cannot be approximated suciently well by any selectable function f in the chosenclass of functions { the learning machine is too simple to learn well. On the other hand, if the capacity
is too large, the learning machine bears the risk ofover tting.
In neural network training, over tting is avoided
by early stopping, regularization or asymptotic model
selection [1, 6, 9, 10].
For SV learning machines that implement linear
discriminant functions in feature spaces, the capacity limitation corresponds to nding a large margin separation between the two classes. The margin % is the minimal distance of training points(x1; y1); : : : ; (x ; y ); x 2 R; y 2 f61g to the separation surface, i.e.
iii

2 Support Vector Machines

i

i

(1)
2

judge the feedback documents. Hence, it is dicult
to use a large number of user judged documents forsupervised learning procedure because the user needs
much e ort to judged the documents. The SVMs havea great ability to discriminate even if the training data
is small. Consequently, we propose to apply SVMs as
the classi er in relevance feedback method. The retrieval steps of proposed method perform as follows:
Step 1: Preparation of documents for the rst
feedback

The conventional information retrieval system
based on vector space model displays the top N
ranked documents along with a request query to
the user.

Figure 1: A binary classi cation toy problem: This
problem is to separate black circles from crosses. The
shaded region consists of training examples, the otherregions of test data. The data can be separated with amargin indicated by the slim dashed lines, implicating
the slim solid line as discriminate function. Misclassifying one training example(a circled white circle) leads
to a considerable extension(arrows) of the margin(fatdashed and solid lines) and this fat solid line can classify two test examples(circled black circles) correctly.

Step 2: Judgement of documents

The user then classi ers these documents into relevant or irrelevant. The relevant documents andthe irrelevant documents are labeled.

Step 3: Determination of the optimal hyperplane

The optimal hyperplane is determined by using
SVM which is learned by labeled documents.

in order to achieve a larger margin between the othertraining points (see Figure 1 for an example).
This soft-margin strategy can also learn nonseparable data. The trade-o between margin size andnumber of misclassi ed training points is then controlled by the regularization parameter C (softness ofthe margin). The following quadratic program (QP)(see e.g. [17, 14]):

P

Step 4: Discrimination all test collection andinformation retrieval

The SVM learned by previous step classi es thewhole documents as relevant or not. The documents which are discriminated relevant and in
the margin area of SVM are shown to user as theinformation retrieval results of the system. If thenumber of feedback iterations is more than m,then go to next step. Otherwise return to Step
2. The m is a maximal number of feedback iterations.

min kwk2 + C =1 s.t. (z ; )  1 0  for all 1  i  ` (8); 0for all 1  i  `leads to the SV soft-margin solution allowing for someerrors.
i

i

`
i

i

i

i

Step 5: Display of thements

nal retrieved docu-

The retrieved documents are ranked by the distance between the documents and the hyperplane which is the discriminant function determined by SVM. The retrieved documents are displayed based on this ranking.

3 Active learning with SVM in IR

In this section, we describe the information retrieval
system using relevance feedback with SVM from an active learning point of view. In relevance feedback, theuser has the option of labeling some of the top ranked
documents according to whether they are relevant or
not. The labeled documents along with the original
request are then given to a supervised learning procedure to produce a new classi er. The new classi er isused to produce a new ranking, which retrievals more
relevant documents at higher ranks than the original
did. In relevant feedback method, the user have to

The feature of our SVM-feedback is the selection of
displayed documents to users in Step 4. Our proposed
method select the documents which are discriminatedrelevant and in the margin area. In the reference [3],Drucker selects the higher ranked documents which
are relevant and far from the discriminant function.
This selection can not keep ecient learning from anactive learning poin of view. In the reference [15],Tong selects the documents which are on or near the3

to classify the labeled documents into relevant or irrelevant, we do not need to use the kernel trick andthe the regularization parameter C (see x2). The VSM
consists of TFIDF. Drucker et al. did not use TFIDF
representation for SVM learning[3].
For comparison with our approach, two IR systemwere used. The rst is a IR system that does not use
feedback. The second is a IR system using traditional
Rocchio-based releveance feedback[11] which is widelyused in IR.
The Rocchio-based releveance feedback modi es aquery vector Q by evaluation of a user using the following equation.

discriminant function. This selection can make ecient learning. However, users feel stress of the selection because it is dicult to display the relevant
documents by the selection. Our selection can be expected that the ecient learning can be kept and users
do not need to feel stress.
4 Experiments

4.1 Experimental settingsi

We made experiments for evaluating the utility of
our interactive document retrieval with active learningof SVM in x3. The document data set we used isa set of articles in the Los Angels Times(about 130
thousands articles, the average number of words in a
article is 526) which is widely used in the document
retrieval conference TREC[16]. This data set includes
not only queries but also the relevant documents toeach query. Thus we used the queries for experiments.
We used TFIDF[19], which is one of the most popular methods in IR to generate document feature vectors, and the concrete equations[13] are in the following.
w= L3t3u
1 + log(tf (t; d))L =1 + log(average of tf (t; d)ind) (tf )N +1
t = log() (idf )df (t)
1u =(normalization)
0:8 + 0:2 average of( ) ( ) w ：Weight of a term t in a document d.
 tf (t; d)：Frequency of a term t in a document d.
 N ：Total number of documents in a data set.
 df (t)：The number of documents including a termt.
 uniq(d)：The number of di erent terms in a document d.

Qi+1 = Qi +

X 0 X
2

x

x Rr

2

x;

(9)

x Rn

where R is a set of documents which were evaluated as relevant by a user at the ithe feedback, andR is a set of documents which were evaluated as
no-relevant in the i feedback. ， are weights forrelevant, no-relevant documents respectively. we set= 1:0， = 0:5 which are known adequate experimentally.
In general, retrieval accuracy signi cantly depends
on the feedback iterations. Thus we changed feedback
iterations for 1, 2, 3, 4 and investigated the accuracy
for each iterations.
We utilized precision and recall for evaluating thethree IR systems[5][18]. The following equations areused to compute precision and recall. Since a recallprecision curve is investigated to each query, we used
the average recall-precision curve over all the queries
as evaluation.
No. of retrieved relevant doc.
Precision = The The
No. of retrieved doc.
TheNo.
of retrieved relevant doc.
recall = The total
No. of relevant doc.
r

n

d
t

uniq duniq ddt

4.2 Experimental results

4.2.1 Comparing of recall-precision performance curve

In this section, we investigated the e ectiveness ofproposed method, when the user judged the top oftwenty ranked documents at each feedback iteration.
In the rst iteration, twenty ranked documents wereretrieved by VSM, which is represened by TFIDF.
Figure 2 show a recall-precision performance curveof SVM-based method, after four feedback iterations.
For comparison, this gure also show the results ofthe conventional feedback method (i.e., Rocchio-based
method) and VSM (i.e., without feedback). The thicksolid line is the proposed method, the broken line is

The size N of retrieved results developed in Step
1 in x3 was set as 20. The feedback iterations was
1, 2, 3 and 4. In order to investigate the in uence of
feedback iterations on accuracy of retrieval, we usedplural feedback iterations.
In our experiments, we used the linear discriminantfunction for the classi er in SVM. The VSM of documents is high dimensional space. Therefore, in order4

Table 1: Average precision using SVM-feedback andRocchio-feedback

1

No. of feedback
iterations
1
2
3
4

Precision

0.8
0.6
0.4

based feedback method degrades the retrieval performances nevertheless the number of feedback iterations
increased from three to four. Hence, we can consider
that the more feedback iterations, the better relevance
documents they can obtain by using SVM-feedback
method. Especially, the proposed method can improve
the performance of conventional feedback method ateach feedback iteration. We believe that the reason ofthese results was that the SVM can nd a more suitable hyperplane for discriminating between relevant
and irrelevant documents as increasing the feedback
iterations. After all, we can believe that the proposed
method can keep e ective learning from active learning point of view.
Furthermore, we compare the performances of proposed method to those of of Rocchiobased feedback
method from an IR point of view. Table 2 shows therelationship between no. of feedback iterations andno. of actual relevant documents in 20 higher ranked
relevant documents in a special case. In this specialcase, ve documents were labeled as relevant documents in twenty documents at the rst iteration. In
almost case, one or two documents were labeled as relevant documents in twenty documents at the rst iteration. We can see from this table that our SVM feedback can increase the number of actual relevant documents which are displayed to the user in proportion toincrease feedback iterations. On the other hand, theRocchio-based feedback method degrades the numberof actual relevant documents nevertheless the number of feedback iterations increased from three to four.
Hence, we can consider that the proposed method cangive the suitable number of actual relevant documents
to the user.

0.2
0
0

0.2

0.4
0.6
Recall

0.8

Average precision
SVM Rocchio
0.2625 0.2250
0.3500 0.2500
0.6125 0.2350
0.6375 0.2250

1Figure 2: The e ectiveness of SVM-feedback: Thelines show recall-precision performance curve by using 20 feedback documents on the set of articles in theLos Angels after 4 feedback iterations. The wide solidline is proposed method, the broken line is conventional feedback method (i.e. Rocchio-based method),
and the solid line is the VSM without feedback.
the conventional feedback method, and the thin solidline was the VSM without feedback.
This gure show that the retrieval e ectiveness ofboth feedback methods, i.e., proposed and conventional feedback method, is improved compared withthat of the non-feedback. In this result, we could conrm that the relevance feedback was useful techniquefor improving the performance of VSM.
Furthermore, this gure also show that the proposed feedback method improves the performancecompared with conventional feedback method at all recall points. Consequently, we conclude that the SVMs
are useful relevant feedback technique improving performance of VSM in this experiment.
4.2.2 Relationships between the performanceand the number of feedback iterations

Here, we describe the relationships between the performances of proposed method and the number of feedback iterations. Table 1 gave the average precision
result as a function of the number of feedback iterations. At each feedback iteration, the system displays
twenty ranked relevant documents. We also show theaverage precision of Rocchio-based method for comparing to proposed method in table 1.
We can see from this table that the SVM feedback
gives the higher performance in proportion to increase
feedback iterations. On the other hand, the Rocchio-

5

Conclusion

In this paper, we proposed the relevance feedback
method with support vector machines (SVMs) for the
information retrieval. Because the SVMs have an excellent ability to discriminate even if the training data
is small, we applied the SVMs to relevance feedback5[6] N. Murata, S. Yoshizawa, and S. Amari. Network
information criterion - determining the numberof hidden units for an arti cial neural networkmodel. IEEE Transactions on Neural Networks,
5(6):865{872, 1994.
[7] NTCIR. http://www.rd.nacsis.ac.jp/~ntcadm/.
[8] M. Okabe and S. Yamada. Interactive document
retrieval with relational learning. In Proceedings

Table 2: In a special case, the relationship between
no. of feedback iterations and no. of actual relevant
documents in 20 higher ranked relevant documents.
No. of feedback No. of relevant
iterations
documents
SVM Rocchio
1
9
11
2
18
13
3
20
12
4
20
11

of the 16th ACM Symposium on Applied Computing, pages 27{31, 2001.

[9] T. Onoda. Neural network information criterion
for the optimal number of hidden units. In Proc.
ICNN'95, volume 1, pages 275{280, 1995.
[10] J. Orr and K.-R. Muller, editors. Neural Networks: Tricks of the Trade. LNCS 1524, Springer
Verlag, 1998.
[11] G. Salton, editor. Relevance feedback in information retrieval, pages 313{323. Englewood Cli s,
N.J.: Prentice Hall, 1971.
[12] G. Salton and J. McGill. Introduction to modern
information retrieval. McGraw-Hill, 1983.
[13] R.E. Schapire, Y. Singer, and A. Singhal. Boosting and rocchio applied to text ltering. In

method. Experimental results on a set of articles inthe Los Angels Times showed the proposed method
gave a consistently better performance than the conventional feedback method. In our experiments we use
TFIDF documents representation as VSM. Drucker
et al. use binary documents representation and TF
representation for estimating the performance of their
proposed method. We plan to apply our proposed
method to the binary representation and TF representation and compare our method with other SVM
based methods(Drucker's method and Tong's method)experimentally.
In this paper, we proposed that the system should
display the documents which are discriminated relevant and in the margin area of SVM at each feedback
iteration. However, we do not discuss how the selection of documents in uence both the e ective learningand the performance of information retrieval theoretically. We would like to propose it as an open problem.

Proceedings of the Twenty-First Annual International ACM SIGIR, pages 215{223, 1998.

[14] B. Scholkopf, A. Smola, R. Williamson, and P.L.
Bartlett. New support vector algorithms. Technical Report NC-TR-1998-031, Department ofComputer Science, Royal Holloway, University of
London, Egham, UK, 1998. Neural Computation
2000.
[15] S. Tong and D. Koller. Support vector machine
active learning with applications to text classi cation. In Journal of Machine Learning Research,
volume 2, pages 45{66, 2001.
[16] TREC Web page. http://trec.nist.gov/.
[17] V.N. Vapnik. The Nature of Statistical Learning
Theory. Springer, 1995.
[18] I. Witten, A. Mo at, and T. Bell. Managing Gi-

References[1] C.M. Bishop. Neural Networks for Pattern Recognition. Clarendon Press, Oxford, 1995.
[2] B.E. Boser, I.M. Guyon, and V.N. Vapnik. A
training algorithm for optimal margin classi ers.
In D. Haussler, editor, 5th Annual ACM Workshop on COLT, pages 144{152, Pittsburgh, PA,
1992. ACM Press.
[3] Harris Drucker, Behzad Shahrary, and David C.
Gibbon. Relevance feedback using support vector
machines. In Proceedings of the Eighteenth International Conference on Machine Learning, pages
122{129, 2001.
[4] IREX.
http://cs.nyu.edu/cs/projects/ proteus/irex/.
[5] D. Lewis. Evaluating text categorization. In Pro-gabytes: Compressing and Indexing Documents
and Images. Van Nostrand Reinhold, New York,

1994.
[19] R. B. Yates and B. R. Neto. Modern Information
Retrieval. Addison Wesley, 1999.

ceedings of Speech and Natural Language Workshop, pages 312{318, 1991.

6