SCIS & ISIS 2010, Dec. 8-12, 2010, Okayama Convention Center, Okayama, JapanA Kernel for Interactive Document Retrieval Basedon Support Vector Machines
Hiroshi Murata∗ † , Takashi Onoda ∗ and Seiji Yamada† ‡∗ Central Research Institute of Electric Power Industry

2–11–1 Iwado kita, Komae-shi, Tokyo 201–8511 Japan
Email: {murata,onoda}@criepi.denken.or.jp† The Graduate University for Advanced Studies (SOKENDAI)
2–1–2 Hitotsubashi, Chiyoda-ku, Tokyo 101–8430 Japan
Email: murata@nii.ac.jp‡ National Institute of Informatics
2–1–2 Hitotsubashi, Chiyoda-ku, Tokyo 101–8430 Japan
Email: seiji@nii.ac.jp
Abstract—This paper describes an application of support
vector machines (SVMs) to interactive document retrieval using
active learning. We show that an SVM-based retrieval has an
association with conventional Rocchio-based relevance feedback
by a comparative analysis. We propose a cosine kernel, which
denotes cosine similarity, suitable for an SVM-based interactive
document retrieval based on the analysis. We confirm the effectiveness of our approach when we adopt Boolean, TF, and TFIDF
to represent the document vectors. Our proposed approach, inparticular, TF representation, shows better performance, which
is demonstrated experimentally.

I. INTRODUCTION
With the development of information technology, theamount of text data is increasing explosively and document
retrieval is expected to become more sophisticated. The taskof finding several relevant documents is known as document
retrieval. It can also be defined as a task to find as many
relevant documents as possible, even if the system strains auser. This latter task is the focus of our study. Document
retrieval systems, which use information on interactive user
feedback, have been studied in many ways [3] [4].
In most frameworks for information retrieval, a vector spacemodel (VSM) is used in which a document is described using
a high-dimensional vector [10]. An information retrieval system using a VSM computes the degree of relevance between
a query vector and document vectors by using the cosine
similarity of the two vectors, and then provides a list of
retrieved documents to a user.
In general, since a user rarely describes a query precisely
in the first attempt, an interactive approach has been proposed
to modify a query vector on the basis of a user’s evaluationof documents in a list of retrieved documents. This method iscalled relevance feedback [9] and is used widely in information retrieval systems. In this method, a user directly evaluates
whether a document in a list of retrieved documents is relevant
or irrelevant, and the system modifies the query vector on thebasis of the user’s evaluation. A conventional way to modify
a query vector is through a simple learning rule that reduces1316

the difference between the query vector and the documents
evaluated as relevant by a user.
A method of relevance feedback based on VSM is the Rocchio algorithm [9]. A new query vector Q m+1 is calculatedusing the following equation:
Qm+1 = Qm + β
x−γ
x.
(1)
x∈Rm
r

x∈Rm
n

Here, x represents document vectors, and R rm and Rnm are
document sets that are determined as relevant and irrelevant
when feedback is obtained m times. β and γ are parametersthat adjust the relative impact of relevance and irrelevance.
The Rocchio algorithm evaluates the degree of relevance using
the cosine similarity between a new query vector Q m+1 anddocument vectors.
Another approach has been proposed in which relevant
and irrelevant document vectors are classified as positive andnegative examples for a target concept based on classification
learning [7]. Some studies have proposed that support vector
machines (SVMs) [13] with excellent ability to classify examples into two classes can be applied to classification learningof relevance feedback [2].
We have proposed a relevance feedback framework withan SVM for active learning and experimentally demonstrated
the usefulness of our proposed method [8]. In contrast to aconventional relevance feedback system which shows a list of
the most relevant documents to a user, our system provides alist of the most relevant documents that are difficult for the
SVM to classify. In such a system, the degree of relevance isevaluated using a signed distance from the optimal hyperplane.
It is not clear how the signed distance in the SVM hascharacteristics of the VSM. Hence, we formulate the degreeof relevance using signed distance in the SVM and make acomparative analysis with the Rocchio algorithm. We proposea cosine kernel which expresses distance in the SVM using
cosine similarity.
In the remainder of this paper, we describe an information
retrieval system using an SVM-based relevance feedback inoptimal
hyperplane

signed distancew ⋅x + bw

where αi ≥ 0 represents Lagrange multipliers. The minimization over w and b can be achieved by the following
differentiation:
∂L
∂L
=0
= 0.
∂b
∂w
Therefore we have the conditions

relevant
documents
area (plusdirection)irrelevant
documents
area (minus
direction)

αi yi = 0i=1 αi yi xi .
w=
i=1

x

(6)
(7)

By using the previous results we obtainw

W (α) =αi ≥ 0(i = 1, . . . , ),section II and propose the cosine kernel in section III. To
evaluate the effectiveness of our approach, we present theresult of experiments performed using a TREC data set insection IV. Finally, we introduce related work in section V
and conclude our work in section VI.
II. SVM-BASED INTERACTIVE DOCUMENTRETRIEVAL
A. SVM-based relevance feedback
Figure 1 shows the concept of relevance feedback basedon an SVM. In Figure 1, white and black circles represent
documents that have been decided as relevant and irrelevant,respectively. Let us consider decided document vectors x ihaving class labels yi = ±1; a linear classifier for an
undecided document vector x is of the form
(2)

The signed distance between the decided documents andhyperplane (margin) is
w · xi + b
min
.
i
||w||

(3)

The minimum distance between decided documents and hyperplane is|w · xi + b|
min
.
(4)
i
||w||
Here, we add the constraint min i |w · xi + b| = 1; thus,
Equation (4) can be rewritten as 1/||w||.
The hyperplane having maximum margin can be foundby solving the following quadratic programming problem
τ (w) = ||w||2 , which is subject to the inequality constraints
yi (w · xi + b) ≥ 1(i = 1, . . . , ).
We construct a Lagrangian for solving the above equation
as follows:
L(w, b, α) =
1||w||2 −αi (yi ((xi · w) + b) − 1)
2
i=1

(8)

subject toRelevance feedback based on SVM

f (x) = w · x + b.

1 
αi αj yi yj (xi · xj )2 i,j=1


αi −

i=1

margin area
Fig. 1.




(5)

1317




αi yi = 0.

(9)

i=1

The documents x i at αi = 0 have no influence on
optimizing the hyperplane. Only the documents x i that are
shown by circles on dashed lines in Figure 1 decide theoptimal hyperplane. These documents are obtained under thecondition α > 0. This α i > 0 data are called support vectors.
The distance between the document and optimal hyperplane
is defined as the degree of relevance in SVM-based relevance
feedback.
B. Comparative analysis of relevance feedback
The signed distance between the optimal hyperplane andan undecided document vector, which is shown by a double
circle in Figure 1, can be expressed as
w·x+b
||w||

||w||||x|| cos θw + b||w||b= ||x|| cos θw +
||w||
=

(10)

where θw is the angle between w and x.
Hence, labels of relevant and irrelevant documents are y i =1 and yi = −1 respectively,w=
αj xj −
αk xk
(11)
j

k

where j and k are indices of relevant and irrelevant documents
respectively.
The query update equation of the Rocchio algorithm, as
shown in Equation (1), can be transformed as follows:
Qm+1 = Q0 +
βxj −
γxk
(12)
j

k

where Q0 is the initial query vector which is derived from auser’s initial input query.
Comparison of Equation (11) and (12) shows that the vector
w equation of SVM-based relevance feedback is equivalent
to query update equation of the Rocchio algorithm when theinitial query vector is the zero vector.

Initial retrieved documents are determined by
The degree of relevance determines the documents to be
retrieved initially. The cosine similarity of the initial queryis used in an SVM-based relevance feedback and Rocchio
algorithm to determine the degree of relevance. Therefore,
initially retrieved documents contain words of the initial queryand there is negligible difference between Equation (11) and(12).
Moreover, in equation (11), vector w only consists of
documents of support vectors for which α i = 0. However,most documents have a tendency to become support vectors
experimentally.
The above discussion suggests that the equation of vector
w for an SVM-based relevance feedback is equivalent to thequery update equation of the Rocchio algorithm, and vector
w is similar to the updated query vector of the Rocchio-based
relevance feedback.
Furthermore, in Equation (11), SVM-based method decides
weights of individual document vectors as α i . This weight αi
is calculated to minimize structural risk under zero empiricalrisk. On the other hand, in the Rocchio-based method, theindividual document vectors have the same weights as β andγ. These parameters are decided by trial and error.
C. Improvement of document representation based on comparative analysis
In the previous section, we showed that equation w of
relevance feedback based on an SVM is equivalent to thequery update equation of the Rocchio algorithm. The degreeof relevance in SVM-based method evaluates ||x|| cos θ wfrom Equation (10) because unique values of w and b are
determined from decided document vectors. On the other
hand, the degree of relevance in Rocchio-based method is
evaluated as cos θq which denotes cosine similarity of theangle θq between the document vector and query vector.
The comparison suggests that the degree of relevance in the
SVM-based method increases as the target document vector||x|| is large. This means that the degree of relevance increases
with large ||x|| rather than small θ w . Therefore, a document
which has many words has high relevance, and a document
which has fewer words has low relevance. To avoid thisproblem, we define the degree of relevance in the SVM-based
method as genuine cosine similarity cos θ w . A simple method
to realize this is by normalizing a document vector.
III. PROPOSAL OF COSINE KERNEL BASED ON
COMPARATIVE ANALYSIS
We substitute a kernel K for the dot product in Equation(8). The kernel corresponds to a dot product in some feature
space that is related to the input space via a nonlinear map Φwhich can have a high dimensionality,
K(x, x ) = Φ(x) · Φ(x ).

(13)

1318

By using K, the classifier takes the form (cf. Equations (2),(7))
f (Φ(x))= w · Φ(x) + b=
αi yi Φ(xi ) · Φ(x) + b
i=1

=




αi yi K(xi , x) + b.

(14)

i=1

The dual optimization problem of Equation (8) is rewritten to
maximize
W (α) =


1 αi αj yi yj K(xi , xj ),2 i,j=1


αi −

i=1

(15)

with the same constraints.
We consider that the kernel K(x, x  ) has cosine similarity
when the angle between the two vectors x and x  is θ suchthatx · x
K(x, x ) = cos θ =.
(16)||x||||x ||It can be seen from this equation that using cosine similarity
as a kernel is equivalent to normalizing the document vector.
We call this the cosine kernel.
IV. EXPERIMENTS
A. Experimental setting
The document data set we used is a set of articles in an
ad hoc task, which was widely used in the 6th, 7th and8th text retrieval conference (TREC). The data set has about
530,000 newspaper articles. Each TREC provides 50 retrieval
problems and information on relevant documents for each
retrieval problem. Hereafter, we call the retrieval problem the“topic.” In our experiments, 150 topics are tested. Each topic
has three tags: a title tag, a description tag, and a narrative tag.
The title tag has two or three terms to describe the topic. The
description tag introduces the topic. The narrative tag reports
the topic. Our experiments used two or three terms of the title
tag as a query. Our experiments also removed stopwords andcreated stemming for documents and queries
We adopted Boolean, TF, and TFIDF methods to represent
the document vector. The adopted TFIDF is as follows:w(t, d) =log(tf(t, d) + 1)N
log.
log(uniq(d))
df(t)

(17)

The notations used in the above equation are as follows:• w(t, d) is the weight of a term t in a document d,• tf(t, d) is a frequency of a term t in a document d,• N is the total number of documents in a data set,
• df(t) is the number of documents including a term t,• uniq(d) is the number of different terms in a documentd.
We use the selection rule of displayed documents proposedin [8], which are displayed to a user for their classification.

optimal
hyperplane

0.4

irrelevant
documents
area

0.3

P

w

Boolean cos
Boolean
TF cosTF
TFIDF cos
TFIDF

relevant
documents
area

0.2

0.1

margin area
0

1

2

3

4

5

6

7

8

9

number of feedback iterations

Proposed selection heuristics

Proposed Selection Rule All documents are mapped onto
the feature space. The learned SVM classifies the documents
as relevant or irrelevant. The documents that are decided to be
relevant and within the margin area of the SVM are selected.
The top N ranked documents, which are ranked using the
distance from the optimal hyperplane, are displayed to a user
as results of the system’s information retrieval (see Figure 2
in which circles represent evaluated documents, squares represent non-checked documents, and black squares represent
selected documents ). This rule is expected to achieve mosteffective retrieval performance. We propose the use of thisrule for retrieval document based on relevance feedback.
The size N of retrieved and displayed documents at each
iteration was set as 10 or 20. The feedback iterations m were
decided by the total number of displayed documents. In theseexperiments, we set the total number of displayed documents
to 100, which includes initial search documents. When thesize N of retrieved and displayed documents at each iteration
is 10, the feedback iterations m are between one and nine.
When N is 20, the feedback iterations m are between one
and four.
To compare the learning performance of our proposed
method with other methods, we evaluated the following criterion.
P30: Precision within the top 30 documents, which isthe proportion of relevant documents in the top 30
documents [5].
To compare the retrieval performance of our proposed methodwith the other methods, we evaluated the following criterion.
P:
Precision of all displayed documents, where

Fig. 3.
Results of retrieval performance using criterion P (displayed
documents N = 10).
0.4

0.3

Boolean cos
Boolean
TF cosTF
TFIDF cos
TFIDF

P

Fig. 2.

0.2

0.1

0

1

2

3

4

number of feedback iterations

Fig. 4.
Results of retrieval performance using criterion P (displayed
documents N = 20).

TABLE IC OMPARISON OF DISPLAYED VECTOR LENGTHS ||x|| USING SVM WHEN
m = 1, N = 10.

mean median min
max
SD
Boolean 23.0
16.1
2.6
118.7
20.1
TF
248.4
77.7
3.5 12258.6 724.2
TFIDF
29.1
16.2
3.2
228.4
32.9
SD:Standard Deviation

Nrel
Ndis
where Nrel denotes the number of relevant documents among
all displayed documents and N dis denotes the total numberof displayed documents.

In these figures, zero in a number of feedback iteration
implies the performance of the initial retrieval, bold lines
indicate the results of the cosine kernel, and solid lines
indicate the results of a linear SVM.

B. Experimental results
Figures 3 and 4 show the values of P. Figures 5 and 6 show
the values of P30.

These figures suggest that the cosine kernel shows better
performance, in particular, when used with the TF method(comparison of lines with crosses in figures).

P =

1319

V. RELATED WORK

0.7

0.6

0.5

Boolean cos
Boolean
TF cosTF
TFIDF cos
TFIDF

P30

0.4

0.3

0.2

0.1

0
0

1

2

3

4

5

6

7

8

9

number of feedback iterations

Fig. 5. Results of learning performance using criterion P 30 (displayed
documents N = 10).
0.7

0.6

0.5

Boolean cos
Boolean
TF cosTF
TFIDF cos
TFIDF

P30

0.4

0.3

0.2

0.1

0
0

1

2

3

4

number of feedback iterations

Fig. 6. Results of learning performance using criterion P 30 (displayed
documents N = 20).

C. Discussion
The above figures suggest that TF representation helps
to achieve a large improvement in document retrieval. TF
representation is strongly influenced by the vector length.
Table I shows a comparison of displayed vector lengths ||x||using SVM when m = 1, N = 10. This table shows that TF
representation has some large length vectors compared withother representations. We consider these large vectors to havea negative impact on retrieval accuracy. The cosine kernel
evaluates the angle between vectors; hence, the cosine kernel
improves retrieval performance.
On the other hand, Boolean and TFIDF approaches gradually becoming reduce the efficiency of results as iteration
progresses. For this reason, the classification accuracy of thediscriminant hyperplane by an SVM gradually increases due
to an iteration feedback process, and the display order is notchanged by ||x||.

1320

Several studies have been conducted for an SVM-based relevance feedback. Drucker et al. applied an SVM for relevance
feedback and confirmed its effectiveness when there are few
relevant documents in the document database[2]. They experimented with differences between document vectors the rateof change of relevant documents in the document database.
However, they did not discuss the degree of relevance indetail. We show the effectiveness of the cosine kernel by acomparative analysis with the Rocchio-based method.
Tong and Koller studied active learning for text classification based on an SVM [12]. They proposed a sample
selection for effective cutting of the version space based on
margin and experimentally showed its effectiveness. However,they discussed only the application of text classification; they
did not inspect the method from the viewpoint of interactive
document retrieval.
The weights in the Rocchio-based method are decided bytrial and error, even for the improved method[1] [11]. We showthat the weights based on an SVM are decided by means ofsimilarity between an SVM-based relevance feedback and the
Rocchio-based method.
In the study of text classification applying Rocchio-based
method, an automatic decision of weights was made by
maximizing the break-even point in which recall is equal
to the precision[6]. This method needs training documents
and evaluation documents; hence, the application of relevance
feedback is difficult.
A study was also conducted to decide the weights for relevance feedback [5]. The study proposed a method to decide
feedback weight α which decides the balance between queries
and feedback documents, in Kullback-Leibler divergence retrieval model by machine learning. In this study, the weight
α is decided by logistic regression using features selected byheuristics. However, this method needs training queries, and αchanges with the queries. Our proposed method automaticallydecides weights using feedback results. Therefore, our method
is more feasible.
VI. CONCLUSION
In this paper, we propose a cosine kernel which denotes cosine similarity, suitable for an SVM-based interactive
document retrieval based on a comparative analysis with a
Rocchio-based method.
Our proposed approach, in particular, TF representation,shows better performance, which is demonstrated experimentally.
R EFERENCES[1] C. Buckley and G. Salton: Optimization of relevance feedback weights,
Proc. of the 18th annual Int. ACM SIGIR Conf., pp. 351–357 (1995).
[2] H. Drucker, B. Shahrary, and D. C. Gibbon: Support vector machines:
relevance feedback and information retrieval, Information Processingand Management, 38, pp. 305–323 (2002).
[3] P. Ingwersen: Information Retrieval Interaction, Taylor Graham (1992).

[4] J. Koenemann and N. J. Belkin: A case for interaction: a study ofinteractive information retrieval behavior and effectiveness, Proc. 27th
Annual SIGCHI Conf. on Human factors in Computing Systems, pp.
205–212 (1996).
[5] Y. Lv and C. Zhai: Adaptive relevance feedback in information retrieval,
Proc. of the 18th ACM CIKM, pp. 255–264 (2009).
[6] A. Moschitti: A study on optimal parameter tuning for Rocchio textclassifier, Proc. of the 25th European Conf. on Information Retrieval
Research (ECIR03), pp. 420–435 (2003).
[7] M. Okabe and S. Yamada: Learning filtering rulesets for ranking
refinement in relevance feedback, Knowledge-Based Systems, 18, 23, pp. 117–124 (2005).
[8] T. Onoda, H. Murata, and S. Yamada: SVM-based interactive document
retrieval with active learning, New Generation Computing, 26, 1, pp.
49–61 (2008).
[9] G. Salton Ed.: Relevance feedback in information retrieval, pp. 313–
323, Englewood Cliffs, N.J.: Prentice Hall (1971).
[10] G. Salton and J. McGill: Introduction to modern information retrieval,
McGraw-Hill (1983).
[11] A. Singhal, M. Mika, and C. Buckley: Learning routing queries in aquery zone, ACM SIGIR Forum, 31, pp. 25–32 (1997).
[12] S. Tong and D. Koller: Support vector machine active learning withapplications to text classification, J. of Machine Learning Research, 2,
pp. 45–66 (2001).
[13] V. Vapnik: Statistical learning theory, Wiley, New York (1998).

1321