Relevance Feedback Document Retrieval using Non-Relevant Documents
TAKASHI O NODA , † H IROSHI M URATA † and S EIJI YAMADA ††This paper reports a new document retrieval method using non-relevant documents. From a large data
set of documents, we need to find documents that relate to human interesting in as few iterations of humantesting or checking as possible. In each iteration a comparatively small batch of documents is evaluated for
relating to the human interesting. This method is called relevance feedback. The relevance feedback needs
a set of relevant and non-relevant documents. However, the initial presented documents which are checked
by a user don’t always include relevant documents. Accordingly we propose a feedback method using information of non-relevant documents only. We named this method non-relevance feedback. The irrelevance
feedback selects a set of documents based on learning result by One-class SVM. Results from experiments
show that this method is able to retrieve a relevant document from a set of non-relevant documents effectively.

Initial Search:
Input Query

1. Introduction
As Internet technology progresses, accessible information by end users is explosively increasing.
In this situation, we can now easily access a huge
document database through the web. However itis hard for a user to retrieve relevant documentsfrom which he/she can obtain useful information,
and a lot of studies have been done in information retrieval, especially document retrieval 1) . Active works for such document retrieval have beenreported in TREC (Text Retrieval Conference) 2)
for English documents, IREX (Information Retrieval and Extraction Exercise) 3) and NTCIR (NIINACSIS Test Collection for Information Retrieval
System)4) for Japanese documents.
In general, since a user hardly describes a precise query in the first trial, interactive approach
to modify the query vector by evaluation of theuser on documents in a list of retrieved documents.
This method is called relevance feedback 6) and usedwidely in information retrieval systems. In thismethod, a user directly evaluates whether a document is relevant or non-relevant in a list of retrieved
documents, and a system modifies the query vector
using the user evaluation.
In another approach, relevant and irrelevant document vectors are considered as positive and negative examples, and relevance feedback is transposed
to a binary class classification problem 7) . For thebinary class classification problem, Support Vector
Machines(which are called SVMs) have shown the

Search &Ranking

Feedback?

NonRelevant
Documents

Check
relevant or
non-relevant

??
?

?
?

Display top
N rankeddocuments?

Fig. 1 Image of a problem in the relevance feedback documents retrieval: The gray arrow parts are made iteratively to retrieve useful documents for the user. This iteration is called feedback iteration in the information retrieval research area. But if the evaluation of the user has
only non-relevant documents, ordinary relevance feedback methods can not feed back the information of useful retrieval.

excellent ability. And some studies applied SVM tothe text classification problems 8) and the information retrieval problems 9) . Recently, we have proposed a relevance feedback framework with SVM
as active learning and shown the usefulness of our
proposed method experimentally 10) .
The initial retrieved documents, which are displayed to a user, sometimes don’t include relevant
documents. In this case, almost all relevance feedback document retrieval systems work hardly, because the systems need relevant and non-relevant
documents to construct a binary class classification
problem(see Figure 1).
While a machine learning research field has somemethods which can deal with one class classification problem. In the above document retrieval case,† Central Research Institute of Electric Power Industry†† National Institute of Informatics

1

we can use only non-relevant documents information. Therefore, we consider this retrieval situation
is as same as one class classification problems.
In this paper, we propose a framework of an interactive document retrieval using only non-relevant
documents information. We call the interactive
document retrieval “non-relevance feedback document retrieval”, because we can use only nonrelevant documents information. Our proposed
non-relevance document retrieval is based on One
Class Support Vector Machine(One-Class SVM) 11) .
One-Class SVM can generate a discriminant hyperplane that can separate the non-relevant documents which are evaluated by a user. Our proposed
method can display documents, which may be relevant documents for the user, using the discriminant
hyperplane.
In the remaining parts of this paper, we explain
the One-Class SVM algorithm in the next section
briefly, and propose our document retrieval method
based on One-Class SVM in the third section. In
the fourth section, in order to evaluate the effectiveness of our approach, we made experiments using a
TREC data set of Los Angels Times and discuss theexperimental results. Finally we conclude our workand discuss our future work in the fifth section.

＋１

Origin－１

Fig. 2 One-Class SVM Classifier: the origin is the only
original member of the second class.

evaluating some simple kernelk(x, y) = (Φ(x) · Φ(y))(2)
such as the Gaussian kernelx − y2k(x, y) = exp.
(3)c
The strategy is to map the data into the feature
space corresponding to the kernel, and to separate
them from the origin with maximum margin. Then,To separate the data set from the origin, one needs
to solve the following quadratic program:
1
1 w2 +minξi − ρν iw∈H,ξ∈R ρ∈RN 2
subject to (w · Φ(xi )) ≥ ρ − ξi ,ξi ≥ 0.

(4)Here, ν ∈ (0, 1) is an upper bound on the fractionof outliers, and a lower bound on the fraction of
Support Vectors.
Since nonzero slack variables ξ i are penalized in
the objective function, we can expect that if w andρ solve this problem, then the decision function
f (x) = sgn ((w · Φ(x)) − ρ)(5)will be positive for most examples x i contained in
the training set, while the SV type regularization
term w will still be small. The actual trade-off
between these two is controlled by ν. For a new
point x, the value f (x) is determined by evaluating
which side of the hyperplane it falls on, in feature
space.
Using multipliers αi , βi ≥ 0, we introduce a LagrangianL(w, ξ, ρ, α, β) =1
1 w2 +
ξi − ρ2ν iαi ((w · xi ) − ρ + ξi ) −βi ξi (6)−

2. One-Class SVM
Schölkopf et al. suggested a method of adapting
the SVM methodology to one-class classification
problem. Essentially, after transforming the feature
via a kernel, they treat the origin as the only member of the second class. The using “relaxation parameters” they separate the image of the one classfrom the origin. Then the standard two-class SVM
techniques are employed.
One-class SVM11) returns a function f that takes
the value +1 in a “small” region capturing most of
the training data points, and -1 elsewhere.
The algorithm can be summarized as mapping
the data into a feature space H using an appropriate kernel function, and then trying to separate
the mapped vectors from the origin with maximum
margin(see Figure /reffig:One-ClassSVM).
Let the training data be
x1 , . . . , x(1)belonging to one class X, where X is a compact
subset of RN and  is the number of observations.
Let Φ : X → H be a kernel map which transforms the training examples to feature space. The
dot product in the image of Φ can be computed byiiand set the derivatives with respect to the primal
variables w, ξi , ρ equal to zero, yielding

2

w=



αi xi ,The initial retrieved documents, which are displayed to a user, sometimes don’t include relevant documents. In this case, almost all relevance feedback document retrieval systems does
not contribute to efficient document retrieval, because the systems need relevant and non-relevant
documents to construct a binary class classification
problem(see Figure 1).
The One-Class SVM can generate discriminant
hyperplane for the one class using one class training data. Consequently, we propose to apply OneClass SVM in a “non-relevance feedback document
retrieval method”. The retrieval steps of proposed
method perform as follows:
Step 1: Preparation of documents for the first
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. In our method, the top N ranked documents are selected by using cosine distance between the request query vector and each document vectors for the first feedback iteration.

(7)

i

1
1 
αi =
− βi ≤ ,αi = 1.
ν
ν
i

(8)

In Eqn. (7), all patterns {x i : i ∈ [], αi > 0}
are called Support Vectors. Using Eqn. (2), the SV
expansion transforms
the decision function
Eqn. (5)f (x) = sgn
αi k(xi , x) − ρ .
(9)iSubstituting Eqn. (7) and Eqn. (8) into Eqn. (6),
we obtain the dual problem:1minαi αj k(xi , xj )
α 2
i,j
1 
subject to 0 ≤ αi ≤ ,αi = 1.
(10)νiOne can show that at the optimum, the two inequality constraints Eqn. (4) become equalities if α i andβi are nonzero, i.e. if 0 < α ≤ 1/(ν). Therefore,
we can recover ρ by exploiting that for any such α i ,the corresponding pattern x
i satisfiesρ = (w · xi ) =αj xj · xi .
(11)
jStep 2: Judgment of documents
The user then classifiers these N documents
into relevant or non-relevant. If the user labels all N documents non-relevant, the documents are labeled “+1” and go to the next step.
If the user classifies the N documents into relevant documents and non-relevant documents,
the non-relevant documents are labeled “+1”
and non-relevant documents are labeled “-1”and then our previous proposed relevant feedback method is adopted 10) .

Note that if ν approaches 0, the upper boundaries
on the Lagrange multipliers tend to infinity, i.e. thesecond inequality constraint in Eqn. (10) become
void. The problem then resembles the corresponding hard margin algorithm, since the penalizationof errors becomes infinite, as can be seen from theprimal objective function Eqn. (4). It is still a feasible problem, since we have placed no restrictionon ρ, so ρ can become a large negative number inorder to satisfy Eqn. (4). If we had required ρ ≥ 0from the start, we would have ended up with theconstraint i αi ≥ 1 instead of the corresponding
equality constraint in Eqn. (10), and the multipliers
αi could have diverged.
In our research we used the LIBSVM. This is
an integrated tool for support vector classification
and regression which can handle one-class SVM using the Schölkopf etc algorithms. The LIBSVM isavailable at http://www.csie.ntu.edu.tw/˜cjlin/libsvm.

Step 3: Determination of non-relevant documents area based on non-relevant documents
The discriminant hyperplane for classifying
non-relevant documents area is generated byusing One-Class SVM. In order to generate thehyperplane, the One-Class SVM learns labeled
non-relevant documents which are evaluated in
the previous step (see Figure 3).

3. Non-relevance Feedback Document Retrieval

Step 4: Classification of all documents and Selection of retrieved documents
The One-class SVM learned by previous step
can classifies the whole documents as nonrelevant or not non-relevant. The documents
which are discriminated in “not non-relevant

In this section, we describe our proposed methodof document retrieval based on Non-relevant documents using One-class SVM.

3

Non-relevant
documents areaw

not include the request query of the user. Our selected documents (see Figure 4) is expected that theprobability of the relevant documents for the user
is high, because the documents are not non-relevant
and may include the query vector of the user.
4. Experiments

Discriminant function

4.1 Experimental setting
We made experiments for evaluating the utility of our interactive document retrieval based on
non-relevant documents using One-Class SVM described in section 3. The document data set we used
is a set of articles in the Los Angels Times which is
widely used in the document retrieval conference
TREC2) . The data set has about 130 thousands articles. The average number of words in a article
is 526. This data set includes not only queries but
also the relevant documents to each query. Thus we
used the queries for experiments. Our experimentused three topics for experiments and show these
topics in Table 1. These topics do not have relevant documents in top 20 ranked documents in theorder of cosine distance between the query vector
and document vectors. Our experiments set the sizeof N of displayed documents presented in Step 1 inthe section 3 10 or 20.
We used TFIDF1) , which is one of the most popular methods in information retrieval to generate
document feature vectors, and we adoped the equation of TFIDF in the reference 12) .
In our experiments, we used the linear kernel for
One-class SVM learning, and found a discriminantfunction for the One-class SVM classifier in the feature space. The vector space model of documents
is high dimensional space. Moreover, the numberof the documents which are evaluated by a user issmall. Therefore, we do not need to use the kernel
trick and the parameter ν (see section 2) is set adequately small value (ν = 0.01). The small ν means
hard margin in the One-Class SVM.
For comparison with our approach, two information retrieval methods were used. The first is
an information retrieval method that does not use
a feedback, namely documents are retrieved using
the rank in vector space model(VSM). The second

Fig. 3 Generation of a hyperplane to discriminate non-relevant
documents area: Circles denote documents which arechecked non-relevant by a user. The solid line denotes
the discriminant hyperplane.

Non-relevant
documents areaw

Discriminant function

Fig. 4 Mapped non-checked documents into the feature
space: Boxes denote non-checked documents which aremapped into the feature space. Circles denotes checked
documents which are mapped into the feature space.
Gray boxes denotes the displayed documents to a user
in the next iteration. These documents are in the “notnon-relevant document area” and near the discriminant
hyperplane.

area” are newly selected.
From the selected documents, the top N ranked documents, which are ranked in the order of the
distance from the non-relevant documents area,
are shown to user as the document retrieval results of the system (see Figure 4). Then returnto Step 2.
The feature of our One-Class SVM based nonrelevant feedback document retrieval is the selection of displayed documents to a user in Step 4. Our
proposed method selects the documents which are
discriminated “not non-relevant” and near the discriminant hyperplane between “non-relevant documents and “not non-relevant documents. Generally if the system got the opposite information froma user, the system should select the information,
which is far from the opposite information area, fordisplaying to the user. However, in our case, theclassified non-relevant documents by the user includes a request query vector of the user. Therefore,
if we select the documents, which are far from thenon-relevant documents area, the documents may

Table 1 Topics, query words and the number of relevant documents in the Los Angels Times used for experiments
topic
query words# of relevant doc.
306
Africa, civilian, death34343
police, death88383
mental, ill, drug
55

4

Table 2 The number of retrieved relevant documents at each
iteration: the number of displayed documents is 10 ateach iteration
topic 308
# of retrieved relevant doc.
# of iterations
Proposed method VSM
Rocchio
1
1
0
0
2
–
0
0
3
–
1
0
4
–
–
0
5
–
–
0
topic 343
# of retrieved relevant doc.
# of iterations
Proposed method VSM
Rocchio
1
0
0
0
2
1
0
0
3
–
0
0
4
–
0
0
5
–
0
0
topic 383
# of retrieved relevant doc.
# of iterations
Proposed method VSM
Rocchio
1
0
0
0
2
1
0
0
3
–
0
0
4
–
1
0
5
–
–
0

Table 3 The number of retrieved relevant documents at each
iteration: the number of displayed documents is 20 ateach iteration
topic 306
# of retrieved relevant doc.
# of iterations
Proposed method
VSM Rocchio
1
1
1
0
2
–
–
0
3
–
–
0
4
–
–
0
5
–
–
0
topic 343
# of retrieved relevant doc.
# of iterations
Proposed method
VSM Rocchio
1
1
0
0
2
–
0
0
3
–
0
0
4
–
1
0
5
–
–
0
topic 383
# of retrieved relevant doc.
# of iterations
Proposed method
VSM Rocchio
1
1
0
0
2
–
1
0
3
–
–
0
4
–
–
0
5
–
–
0

feedback approach gives the higher performance interms of the number of iteration for retrieving relevant document. On the other hand, the Rocchiobased feedback method cannot search a relevant
document in all cases. The vector space model
without feedback is better than Rocchio-based feedback. After all, we can believe that proposed
method can make an effective document retrieval
using only non-relevant documents, and Rocchiobased feedback method can not work well when
the system can receive the only non-relevant documents information.
Table 3 gave the number of retrieved relevant
documents at each feedback iteration. At each feedback iteration, the system displays twenty higher
ranked “not non-relevant documents”, which arenear the discriminant hyperplane, for our proposed
method. We also show the retrieved documents of
Rocchio-based method at each feedback iteration
for comparing to proposed method in table 3.
We can observe from this table that our nonrelevance feedback approach gives the higher performance in terms of the number of iteration for
retrieving relevant documents, and the same experimental results as table 2 about Rocchio-based
method and VSM.
In table 2, a user already have seen twenty documents at the first iteration. Before the fist iteration, the user have to see ten documents, which
are retrieved results using cosine distance between
a query vector and document vectors in VSM. In

is an information retrieval method using conventional Rocchio-based relevance feedback 6) which is
widely used in information retrieval research.
The Rocchio-based relevance feedback modifies
a query vector Q i by evaluation of a user using thefollowing equation.

Qi+1 = Qi + α
x−β
x,
(12)
x∈Rr

x∈Rn

where Rr is a set of documents which were evaluated as relevant documents by a user at the ith
feedback, and R n is a set of documents which were
evaluated as non-relevant documents at the i feedback. α and β are weights for relevant and nonrelevant documents respectively. In this experiment, we set α = 1.0 ，β = 0.5 which are known
adequate experimentally.
4.2 Experimental results
Here, we describe the relationships between theperformances of proposed method and the numberof feedback iterations. Table 2 gave the numberof retrieved relevant documents at each feedback
iteration. At each feedback iteration, the system
displays ten higher ranked “not non-relevant documents”, which are near the discriminant hyperplane, for our proposed method. We also show the
retrieved documents of Rocchio-based method ateach feedback iteration for comparing to proposed
method in table 2.
We can see from this table that our non-relevance5

large database. For instance, please consider a casewhere you want to search patent information related
your research. In the first, you input a few keywords
to find your interesting patent information. And
then you can see too many patent documents. Can
you find your interesting information in them easily? We think it is very difficult to find interesting information in the top 100 documents. Therefore, we
believe that our proposed non-relevance feedback
method is useful for an effective interactive document retrieval.
This paper proposed that the system should display the documents which are in the “not nonrelevant” documents area and near the discriminant
hyperplane of One-Class SVM at each feedback iteration. However, we do not discuss how the selection of documents influence both the effective learning and the performance of information retrieval
theoretically. This point is our future work.

table 3, the user also have seen forty documents at
the first iteration. Before the fist iteration, the user
also have to see ten documents to evaluate the documents, which are retrieved results using cosine distance between a query vector and document vectors
in VSM. When we compare the experimental results of table 2 with the results of table 3, we canobserve that the small number of displayed documents makes more effective document retrieval performance than the large number of displayed documents. In table 2, the user had to see thirty documents by finding the first relevant document about
topic 343 and 383. In table 3, the user had to see
forty documents by finding the first relevant document about topic 343 and 383. Therefore, we believe that the early non-relevance feedback is usefulfor an interactive document retrieval.
5. Conclusion
In this paper, we proposed the non-relevance
feedback document retrieval based on One-ClassSVM using only non-relevant documents for a user.
In our non-relevance feedback document retrieval,the system use only non-relevant documents information. One-Class SVM can generate a discriminant hyperplane of observed one class information,so our proposed method adopted One-Class SVM
for non-relevance feedback document retrieval.
This paper compared our method with a conventional relevance feedback method and a vector space model without feedback. Experimental results on a set of articles in the Los Angels
Times showed that the proposed method gave aconsistently better performance than the comparedmethod. Therefore we believe that our proposed
One-Class SVM based approach is very useful forthe document retrieval with only non-relevant documents information.
If our proposed non-relevant feedback document
retrieval method find and display relevant documents for a user, the system will switch fromour non-relevant feedback method to ordinary relevance feedback document retrieval method immediately. When one see this procedure, one may
think that there are few chances of using our nonrelevant feedback method in an interactive document retrieval. However, we guess that our nonrelevant feedback method has a lot of chances in
the interactive document retrieval. Because it isvery hard for the interactive document retrieval tofind relevant documents using a few keywords in a

References
1) Yates, R. B. and Neto, B. R.: Modern Information
Retrieval, Addison Wesley (1999).
2) TREC Web page: http://trec.nist.gov/.
3) IREX: http://cs.nyu.edu/cs/projects/proteus/irex/.
4) NTCIR: http://www.rd.nacsis.ac.jp/˜ntcadm/.
5) Salton, G. and McGill, J.: Introduction to modern
information retrieval, McGraw-Hill (1983).
6) Salton, G.(ed.): Relevance feedback in information
retrieval, Englewood Cliffs, N.J.: Prentice Hall, pp.
313–323 (1971).
7) Okabe, M. and Yamada, S.: Interactive Document
Retrieval with Relational Learning, Proceedings ofthe 16th ACM Symposium on Applied Computing,pp. 27–31 (2001).
8) Tong, S. and Koller, D.: Support Vector Machine
Active Learning with Applications to Text Classification, Journal of Machine Learning Research,
Vol. 2, pp. 45–66 (2001).
9) Drucker, H., Shahrary, B. and Gibbon, D. C.: Relevance Feedback using Support Vector Machines,
Proceedings of the Eighteenth International Conference on Machine Learning, pp. 122–129 (2001).
10) Onoda, T., Murata, H. and Yamada, S.: RelevanceFeedback with Active Learning for Document Retrieval, Proc. of IJCNN2003, pp. 1757–1762 (2003).
11) Schölkopf, B., Platt, J., Shawe-Taylor, J., Smola,
A. and Williamson, R.: Estimating the Support
for a High-Dimensional Distribution, Technical Report MSR-TR-99-87, Microsoft Research, One Microsoft Way Redmon WA 98052 (1999).
12) Schapire, R., Singer, Y. and Singhal, A.: Boosting
and Rocchio Applied to Text Filtering, Proceedingsof the Twenty-First Annual International ACM SIGIR, pp. 215–223 (1998).

6