Proceedings of the 2004 IEEE
Conference on Cybernetics and Intelligent Systems
Singapore, 1-3 December, 2004��

Non-Relevance Feedback Document Retrieval
Takashi Onoda

Hiroshi Murata

Seiji Yamada

System Engineering Res. Lab.
Central Research Institute ofElectric Power Industry
2-11-1, Iwado Kita, Komae-shi,
Tokyo 201-8511 JAPANE-mail: onoda@criepi.denken.or.jp

System Engineering Res. Lab.
Central Research Institute ofElectric Power Industry
2-11-1 Iwado Kita, Komae-shi,
Tokyo 201-8511 JAPANE-mail: murata@criepi.denken.or.jp

National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-ku,
Tokyo 101-8430 JAPANE-mail: seiji@nii.ac.jp

Abstract— This paper reports a new document retrieval
method using non-relevant documents. From a large data setof documents, we need to find documents that relate to humaninteresting in as few iterations of human testing or checking
as possible. In each iteration a comparatively small batch of
documents is evaluated for relating to the human interesting.
We applied active learning techniques based on Support Vector
Machine for evaluating successive batches, which is called relevance feedback. Our proposed approach has been very useful for
document retrieval with relevance feedback experimentally. The
relevance feedback needs a set of relevant and non-relevant documents to work usefully. However, the initial retrieved documents,
which are displayed to a user, sometimes don’t include relevant
documents. In order to solve this problem, we propose a new
feedback method using information of non-relevant documents
only. We named this method “non-relevance feedback document
retrieval”. The non-relevance feedback document retrieval isbased on One-class Support Vector Machine. Our experimental
results show that this method can retrieve relevant documents
using information of non-relevant documents only.

Initial Search:
Input Query

Search &Ranking

Feedback
Check
relevant or
non-relevant
NonRelevant
Documents

Relevant
Documents

Display top
N rankeddocuments

I. I NTRODUCTION

Fig. 1.
Image of the relevance feedback documents retrieval: The grayarrow parts are made iteratively to retrieve useful documents for the user.
This iteration is called feedback iteration in the information retrieval researcharea.

As Internet technology progresses, accessible information
by end users is explosively increasing. In this situation, we cannow easily access a huge document database through the web.
However it is hard for a user to retrieve relevant documentsfrom which he/she can obtain useful information, and a lotof studies have been done in information retrieval, especially
document retrieval [1]. Active works for such document retrieval have been reported in TREC (Text Retrieval Conference) [2] for English documents, IREX (Information Retrieval
and Extraction Exercise) [3] and NTCIR (NII-NACSIS Test
Collection for Information Retrieval System) [4] for Japanese
documents.
In most frameworks for information retrieval, a vector
space model in which a document is described with a highdimensional vector is used [5]. An information retrieval 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 first trial, interactive approach to modify the query vector
by evaluation of the user on documents in a list of retrieved
documents. This method is called relevance feedback [6] andused widely in information retrieval systems. In this method, auser directly evaluates whether a document is relevant or nonrelevant in a list of retrieved documents, and a system modifies
the query vector using the user evaluation. A traditional way
to modify a query vector is a simple learning rule to reduce thedifference between the query vector and documents evaluatedas relevant by a user(see Figure 1).
In another approach, relevant and irrelevant document vectors are considered as positive and negative examples, andrelevance feedback is transposed to a binary class classification problem [7]. For the binary class classification problem,
Support Vector Machines(which are called SVMs) have shown
the excellent ability. And some studies applied SVM to thetext classification problems [8] and the information retrieval
problems [9]. Recently, we have proposed a relevance feedback framework with SVM as active learning and shown theusefulness of our proposed method experimentally[10].
The initial retrieved documents, which are displayed toa user, sometimes don’t include relevant documents. In thiscase, almost all relevance feedback document retrieval systems
work hardly, because the systems need relevant and non-

0-7803-8643-4/04/$20.00 © 2004 IEEE

456

Initial Search:
Input Query

Search &Ranking＋１

Feedback?

NonRelevant
Documents

Check
relevant or
non-relevant

??
?

?
?

Origin
Display top
N rankeddocuments－１?

Fig. 2. 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 nonrelevant documents, ordinary relevance feedback methods can not feed backthe information of useful retrieval.

relevant documents to construct a binary class classification
problem(see Figure 2).
While a machine learning research field has some methods
which can deal with one class classification problem. In theabove document retrieval case, 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 “nonrelevance feedback document retrieval”, because we can use
only non-relevant documents information. Our proposed nonrelevance document retrieval is based on One Class Support
Vector Machine(One-Class SVM)[11]. One-Class SVM cangenerate a discriminant hyperplane that can separate the nonrelevant 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 OneClass SVM algorithm in the next section briefly, and propose
our document retrieval method based on One-Class SVM inthe third section. In the fourth section, in order to evaluate theeffectiveness of our approach, we made experiments using a
TREC data set of Los Angels Times and discuss the experimental results. Finally we conclude our work and discuss our
future work in the fifth section.
II. O NE -C LASS 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 class from

Fig. 3. One-Class SVM Classifier: the origin is the only original memberof the second class.

the origin. Then the standard two-class SVM techniques are
employed.
One-class SVM [11] 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 intoa feature space H using an appropriate kernel function, andthen 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 R Nand  is the number of observations. Let Φ : X → H be akernel map which transforms the training examples to feature
space. The dot product in the image of Φ can be computed byevaluating some simple kernelk(x, y) = (Φ(x) · Φ(y))
such as the Gaussian kernelk(x, y) = exp

x − y2
c

(2)


.

(3)

The strategy is to map the data into the feature spacecorresponding to the kernel, and to separate them from theorigin with maximum margin. Then, To separate the data set
from the origin, one needs to solve the following quadratic
program:1
1 
w2 +
ξi − ρ
min

N
2
ν i
w∈H,ξ∈R ρ∈R
subject to(w · Φ(xi )) ≥ ρ − ξi ,ξi ≥ 0.

(4)Here, ν ∈ (0, 1) is an upper bound on the fraction of outliers,
and a lower bound on the fraction of Support Vectors.

457

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 besmall. The actual trade-off between these two is controlledby ν. For a new point x, the value f (x) is determined byevaluating 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
−
i

(6)

i

and set the derivatives with respect to the primal variablesw, ξi , ρ equal to zero, yielding
αi xi ,
(7)
w =
i

αi

=


1
1
− β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)αi k(xi , x) − ρ .
(9)f (x) = sgni

Substituting Eqn. (7) and Eqn. (8) into Eqn. (6), we obtain the
dual problem:1
αi αj k(xi , xj )
(10)
min
α
2 i,j
1 
subject to0 ≤ αi ≤ ,αi = 1.
(11)ν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 ρ byexploiting that for any such α i , the corresponding pattern x isatisfiesαj xj · xi .
(12)
ρ = (w · xi ) =If we had required ρ ≥
0 from the start, we would have ended
up with the constraint i αi ≥ 1 instead of the corresponding
equality constraint in Eqn. (11), 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 theSchölkopf etc algorithms. The LIBSVM is available at
http://www.csie.ntu.edu.tw/˜cjlin/libsvm.
III. N ON - RELEVANCE F EEDBACK D OCUMENT R ETRIEVALIn this section, we describe our proposed method of document retrieval based on Non-relevant documents using Oneclass SVM.
In relevance feedback document retrieval, the user has theoption of labeling some of the top ranked documents according
to whether they are relevant or non-relevant. The labeled
documents along with the original request are then given toa supervised learning procedure to produce a new classifier.
The new classifier is used to produce a new ranking, which
retrievals more relevant documents at higher ranks than theoriginal did(see Figure 1)[10].
The initial retrieved documents, which are displayed toa user, sometimes don’t include relevant documents. In thiscase, almost all relevance feedback document retrieval systems
does not contribute to efficient document retrieval, because thesystems need relevant and non-relevant documents to constructa binary class classification problem(see Figure 2).
The One-Class SVM can generate discriminant hyperplane
for the one class using one class training data. Consequently,
we propose to apply One-Class 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 basedon 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.
Step 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].

jNote that if ν approaches 0, the upper boundaries on the
Lagrange multipliers tend to infinity, i.e. the second inequality constraint in Eqn. (11) become void. The problem thenresembles the corresponding hard margin algorithm, since thepenalization of errors becomes infinite, as can be seen fromthe primal objective function Eqn. (4). It is still a feasible
problem, since we have placed no restriction on ρ, so ρ canbecome a large negative number in order to satisfy Eqn. (4).

Step 3:Determination of non-relevant documents area
based on non-relevant documents
The discriminant hyperplane for classifying nonrelevant documents area is generated by using One-458

Non-relevant
documents area

The feature of our One-Class SVM based non-relevant
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 thesystem got the opposite information from a user, the systemshould select the information, which is far from the opposite
information area, for displaying to the user. However, in
our case, the classified non-relevant documents by the user
includes a request query vector of the user. Therefore, if we
Discriminant function select the documents, which are far from the non-relevant
documents area, the documents may not include the request
query of the user. Our selected documents (see Figure 5) isFig. 4. Generation of a hyperplane to discriminate non-relevant documents expected that the probability of the relevant documents for thearea: Circles denote documents which are checked non-relevant by a user. user is high, because the documents are not non-relevant and
The solid line denotes the discriminant hyperplane.
may include the query vector of the user.

w

Non-relevant
documents area

IV. E XPERIMENTS

A. Experimental setting
We made experiments for evaluating the utility of our interactive document retrieval based on non-relevant documents
Discriminant function using One-Class SVM described in section III. 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
Fig. 5.
Mapped non-checked documents into the feature space: Boxes TREC [2]. The data set has about 130 thousands articles.
denote non-checked documents which are mapped into the feature space. The average number of words in a article is 526. This data
Circles denotes checked documents which are mapped into the feature space. set includes not only queries but also the relevant documents
Gray boxes denotes the displayed documents to a user in the next iteration.
These documents are in the “not non-relevant document area” and near the to each query. Thus we used the queries for experiments.
Our experiment used three topics for experiments and show
discriminant hyperplane.
these topics in Table I. These topics do not have relevant
documents in top 20 ranked documents in the order of cosine
Class SVM. In order to generate the hyperplane, the distance between the query vector and document vectors.
One-Class SVM learns labeled non-relevant docu- Our experiments set the size of N of displayed documents
ments which are evaluated in the previous step (see presented in Step 1 in the section III 10 or 20.
Figure 4).
We used TFIDF [1], which is one of the most popular
Step 4:Classification of all documents and Selection of methods in information retrieval to generate document feature
vectors, and the concrete equation [12] of a weight of a term
retrieved documents
The One-class SVM learned by previous step canclassifies the whole documents as non-relevant or
not non-relevant. The documents which are discrimTABLE I
inated in “not non-relevant area” are newly selected. T OPICS , QUERY WORDS AND THE NUMBER OF RELEVANT DOCUMENTS IN
From the selected documents, the top N ranked
THE L OS A NGELS T IMES USED FOR EXPERIMENTS
documents, which are ranked in the order of the
topic
query words# of relevant doc.
distance from the non-relevant documents area, are306
Africa, civilian, death34343
police, death88
shown to user as the document retrieval results of383
mental, ill, drug55
the system (see Figure 5). Then return to Step 2.

w

459

TABLE II

t in a document d w td are in the following.
wtd= L×t×u

T HE NUMBER OF RETRIEVED RELEVANT DOCUMENTS AT EACH

(13)

ITERATION : THE NUMBER OF DISPLAYED DOCUMENTS IS 10 AT EACH
ITERATION

1 + log(tf (t, d))(TF)
1 + log(average of tf (t, d) in d)

L

=

t

= log(u=n+1) (IDF)df (t)
1

uniq(d)0.8 + 0.2 averageof uniq(d)# of retrieved relevant doc.
Proposed method
VSM Rocchio
1
0
0
–
0
0
–
1
0
–
–
0
–
–
0

topic 343
# of iterations
1
2
3
4
5

# of retrieved relevant doc.
Proposed method
VSM Rocchio
0
0
0
1
0
0
–
0
0
–
0
0
–
0
0

topic 383
# of iterations
1
2
3
4
5

# of retrieved relevant doc.
Proposed method
VSM Rocchio
0
0
0
1
0
0
–
0
0
–
1
0
–
–
0

(normalization)

The notations in these equation denote as follows:d• wt is a 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.
In our experiments, we used the linear kernel for One-class
SVM learning, and found a discriminant function for the Oneclass SVM classifier in the feature space. The vector spacemodel of documents is high dimensional space. Moreover, thenumber of the documents which are evaluated by a user issmall. Therefore, we do not need to use the kernel trick andthe parameter ν (see section II) is set adequately small value(ν = 0.01). The small ν means hard margin in the One-ClassSVM.
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 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 Qi by evaluation of a user using the following equation.

Qi+1 = Qi + α
x−β
x,
(14)
•

x∈Rr

topic 308
# of iterations
1
2
3
4
5

x∈Rn

where Rr is a set of documents which were evaluatedas relevant documents by a user at the ith feedback, and
Rn is a set of documents which were evaluated as nonrelevant documents at the i feedback. α and β are weights
for relevant and non-relevant documents respectively. In thisexperiment, we set α = 1.0 ，β = 0.5 which are known
adequate experimentally.
B. Experimental results
Here, we describe the relationships between the performances of proposed method and the number of feedback iterations. Table II gave the number of 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 Rocchiobased method at each feedback iteration for comparing toproposed method in table II.
We can see from this table that our non-relevance feedback
approach gives the higher performance in terms of the numberof iteration for retrieving relevant document. On the other
hand, the Rocchio-based 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, andRocchio-based feedback method can not work well when thesystem can receive the only non-relevant documents information.
Table III gave the number of retrieved relevant documents ateach feedback iteration. At each feedback iteration, the system
displays twenty higher ranked “not non-relevant documents”,
which are near the discriminant hyperplane, for our proposed
method. We also show the retrieved documents of Rocchiobased method at each feedback iteration for comparing toproposed method in table III.
We can observe from this table that our non-relevance
feedback approach gives the higher performance in terms ofthe number of iteration for retrieving relevant documents, andthe same experimental results as table II about Rocchio-based
method and VSM.
In table II, 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

460

TABLE III
T HE NUMBER OF RETRIEVED RELEVANT DOCUMENTS AT EACH
ITERATION : THE NUMBER OF DISPLAYED DOCUMENTS IS 20 AT EACH
ITERATION

topic 306
# of iterations
1
2
3
4
5

# of retrieved relevant doc.
Proposed method
VSM Rocchio
1
1
0
–
–
0
–
–
0
–
–
0
–
–
0

topic 343
# of iterations
1
2
3
4
5

# of retrieved relevant doc.
Proposed method
VSM Rocchio
1
0
0
–
0
0
–
0
0
–
1
0
–
–
0

topic 383
# of iterations
1
2
3
4
5

# of retrieved relevant doc.
Proposed method
VSM Rocchio
1
0
0
–
1
0
–
–
0
–
–
0
–
–
0

distance between a query vector and document vectors in
VSM. In table III, 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 theexperimental results of table II with the results of table III,
we can observe that the small number of displayed documents
makes more effective document retrieval performance thanthe large number of displayed documents. In table II, theuser had to see thirty documents by finding the first relevant
document about topic 343 and 383. In table III, 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 useful for an interactive document
retrieval.
V. C ONCLUSION
In this paper, we proposed the non-relevance feedback
document retrieval based on One-Class SVM using only nonrelevant 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 theLos Angels Times showed that the proposed method gave aconsistently better performance than the compared method.

Therefore we believe that our proposed One-Class SVM based
approach is very useful for the 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, thesystem will switch from our non-relevant feedback method
to ordinary relevance feedback document retrieval method
immediately. When one see this procedure, one may thinkthat there are few chances of using our non-relevant feedback
method in an interactive document retrieval. However, we
guess that our non-relevant feedback method has a lot ofchances in the interactive document retrieval. Because it isvery hard for the interactive document retrieval to find relevant
documents using a few keywords in a large database. For
instance, please consider a case where you want to searchpatent 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 nonrelevance 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 non-relevant” documents areaand near the discriminant hyperplane of One-Class SVM ateach feedback iteration. However, we do not discuss how theselection of documents influence both the effective learningand the performance of information retrieval theoretically. This
point is our future work.
R EFERENCES[1] R. B. Yates and B. R. Neto, 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] G. Salton and J. McGill, Introduction to modern information retrieval.
McGraw-Hill, 1983.
[6] G. Salton, Ed., Relevance feedback in information retrieval. Englewood
Cliffs, N.J.: Prentice Hall, 1971, pp. 313–323.
[7] M. Okabe and S. Yamada, “Interactive document retrieval with relational
learning,” in Proceedings of the 16th ACM Symposium on Applied
Computing, 2001, pp. 27–31.
[8] S. Tong and D. Koller, “Support vector machine active learning withapplications to text classification,” in Journal of Machine Learning
Research, vol. 2, 2001, pp. 45–66.
[9] H. Drucker, B. Shahrary, and D. C. Gibbon, “Relevance feedback
using support vector machines,” in Proceedings of the EighteenthInternational Conference on Machine Learning, 2001, pp. 122–129.
[Online]. Available: citeseer.nj.nec.com/443262.html[10] T. Onoda, H. Murata, and S. Yamada, “Relevance feedback with active
learning for document retrieval,” in Proc. of IJCNN2003, 2003, pp.
1757–1762.
[11] B. Schölkopf, J. Platt, J. Shawe-Taylor, A. Smola, and R. Williamson,“Estimating the support for a high-dimensional distribution,” Microsoft
Research, One Microsoft Way Redmon WA 98052, Tech. Rep. MSRTR-99-87, 1999.
[12] R. Schapire, Y. Singer, and A. Singhal, “Boosting and rocchio applied totext filtering,” in Proceedings of the Twenty-First Annual International
ACM SIGIR, 1998, pp. 215–223.

461