Knowledge-Based Systems 18 (2005) 117–124
www.elsevier.com/locate/knosys

Learning filtering rulesets for ranking refinement
in relevance feedback
Masayuki Okabea, Seiji Yamadab,*ab

Toyohashi University of Technology, 1-1 Tempaku, Toyohashi, Aichi 441-8580, Japan
National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda, Tokyo 101-8430, Japan
Received 14 November 2002; accepted 6 April 2004
Available online 18 January 2005

Abstract
In this paper we propose an approach for refining a document ranking by learning filtering rulesets through relevance feedback. Thisapproach includes two important procedures. One is a filtering method, which can be incorporated into any kinds of information retrieval
systems. The other is a learning algorithm to make a set of filtering rules, each of which specifies a condition to identify relevant documents
using combinations of characteristic words. Our approach is useful not only to overcome the limitation of the vector space model, but also toutilize tags of semi-structured documents like Web pages. Through experiments we show our approach improves the performance of
relevance feedback in two types of IR systems adopting the vector space model and a Web search engine, respectively.
q 2005 Elsevier B.V. All rights reserved.
Keywords: Filtering rulesets; Ranking refinement; Relevance feedback

1. Introduction
As seen in the development of knowledge management
systems or WWW search engines, Information Retrieval(IR) is one of the core technologies to exploit valuableknowledge from huge electric documents stored in digital
libraries or the Internet. Since users have a wide range ofobjectives, IR systems need to be able to change their
behaviors according to personal requests, goals andinterests. The most difficult problem to achieve such
adaptive behavior is to translate a user’s ambiguous
requirements into a concrete query. As many researches
have pointed out so far, it is usually difficult for novices to
input a set of keywords, which focuses on a specific topic
they want to find—selecting good keywords or finding
effective keyword combinations is not an easy task. Some ofgeneral search engines recently support for users to input
additional keywords by showing several relational words,
which are prepared by analyzing the history of transactions
stored in their databases. This function, however, relatively* Corresponding author. Fax: C81 342 122 562.
E-mail addresses: okabe@mc.tut.ac.jp (M. Okabe), seiji@nii.ac.jp(S. Yamada).
0950-7051/$ - see front matter q 2005 Elsevier B.V. All rights reserved.
doi:10.1016/j.knosys.2004.04.011

works well if a user is searching a major topic like ‘Linuxfor macintosh’. However, for more specific topic like ‘Linuxdrivers for the wireless LAN card on macintosh’, they do
not suggest any alternative or additional keywords.
Expressing search intents are a problem of how tocharacterize documents a user wants to find. Such a problem
has been considered mainly under the research of relevance
feedback [1], which is the most successful framework of
improving retrieval effectiveness with iterative human help.
Since a user has only to input an initial query and mark somerelevant documents during a retrieval process, this technique can reduce users effort and enables them to find acluster of topically related documents efficiently. In mostcases, relevance feedback is realized by using the vector
space model because of its simplicity and effectiveness.
However, it has been pointed out that the vector spacemodel cannot represent logical and proximity word relations
which are useful to identify a document precisely [2].
Although there are several retrieval models which can adopt
word relations [3,4], they are not so powerful that they can
become alternative ways to the vector space model.
Meanwhile, recently many of machine learning techniques have been tested in document categorization
problems where each document is automatically118

M. Okabe, S. Yamada / Knowledge-Based Systems 18 (2005) 117–124

categorized into pre-defined classes, and revealed to besuperior to classify documents. In spite of their potential,none of them has been applied to relevance feedback so far.
It is not clear that those machine-learning techniques canimprove the effectiveness of traditional relevance feedback
based on the vector space model. In order to investigate thispoint, we extend a process of relevance feedback by
incorporating a rule-based document filtering. Document
filtering is based on a set of rules which describes theeffective propositional and proximity word relations to
identify documents a user wants to find.
In short, the aim of this paper is to propose a method for
improving the performance of a traditional method of
relevance feedback by applying a document filtering
method. Through experiments we show our approach
improves the performance of relevance feedback in two
types of IR systems which adopt the vector space model anda Web search engine.
The reminder of the paper is organized as follows. In
Section 2 we first describe a traditional method of relevance
feedback which adopts the vector space model as an IRmodel. Then, we incorporate additional procedures of
document filtering into the process of a traditional method.
Section 3 explains a ruleset—representation and its learningalgorithm. Section 4 presents experiments to evaluate theeffectiveness of our method. In Section 5 we analyze several
rulesets. Finally, Section 6 concludes our work.

Many researches have tried to improve the performanceof this relevance feedback so far by proposing methods forcalculating word weights [6] and selecting good training
examples [7]. Although some good weighting methods havebeen proposed [8], the vector space model has a criticallimitation that it cannot utilize any word relation. To
overcome this limitation, we considered exploiting usefulword relations.
Word relations such as simple and–or relation, order ina document, proximity between words and so on are very
useful to characterize a document. Several researches in thefield of machine learning have recently demonstrated theirusefulness in the task of document filtering, which is aprocess of filtering through large stores of textual data,such as categorizing Web pages into a pre-defined classes,
or selecting a set of specific news or e-mail from a streamof constantly arriving data (e.g. net-news or mailmagazine) [2,9–11].
Following these researches, we use boolean andproximity relation to improve the performance of standard
relevance feedback. However, we cannot adopt theirinductive learning algorithm directly because they assume
a large amount of training data sets, which cannot be
obtained in relevance feedback environment. Thus, wedeveloped a learning algorithm, which is suitable to exploit
word relations in the process of relevance feedback. We
describe it in Section 4. Before describing our learningalgorithm, we explain how to apply the knowledge learned
by our algorithm.

2. Relevance feedback with rule-based ranking
refinement
2.2. Ranking refinement with rule-based filtering
2.1. To overcome the limitation of standard relevance
feedback
Relevance feedback [5] is a framework for efficiently
collecting relevant documents by repeating humanevaluation and query modification. Though several
retrieval models have been applied to this framework,
the vector space model is one of the best models to
make a practical system because of its simplicity andeffectiveness. In this model, a query is modified based on
the following formula
QiC1 Z Qi C

NC
NK
1 X
1 X
C
D
K
DK:
NC jZ1 j
NK jZ1 jOnce a retrieval system returns a document ranking, auser evaluates some part of the result and can find NC
numbers of relevant documents and NK numbers of nonrelevant ones. An IR system automatically updates aquery vector Qi using those documents—each document
is represented by DC(if relevant) and DK(if nonjjK
relevant) in the above formula. DC
ðD
Þ
is
a
vectorwhosejjcomponents are the weight (such as tf$idf value) of all
the words included in a document.

Our approach for utilizing word relations is to incorporate additional procedures to exploit and to apply word
relations into standard relevance feedback. This extension
does not lose any advantage of standard method. Fig. 1
shows the outline of our relevance feedback model.
Following the explanation of this figure, we introduce ourapproach.
1. Initial search. At the beginning of a retrieval a user
inputs a query (usually a few words) to an IR system.
Setting an appropriate initial query is an important factorof relevance feedback because an initial query is a basisof following relevance feedback processes, and it affects
the total effectiveness of the process.
2. Evaluation and feedback. If a user cannot find enoughrelevant documents from the result of initial search,he/she starts a relevance feedback process by marking
relevancy of each document he/she has already checked.
A system stores those documents as training documents
for learning of rulesets.
3. Analysis of training documents. In this stage, a systemanalyzes training documents to make statistical analysis
for query modification and to extract effective word

M. Okabe, S. Yamada / Knowledge-Based Systems 18 (2005) 117–124

119

Fig. 1. Relevance feedback with ruleset filtering.

relations for a ruleset. We explain more concrete
procedures in the following.
† Expansion of keywords. Keywords inputted by a user
at initial search are too few to modify a query and to
make a ruleset. Thus, a system selects additional
keywords from training documents. There are several
methods for the selection [12,13]. We do not careabout which method to use here.
† Extraction of word relations. Using expanded keywords, a system prepares a set of word relations
appearing in training documents. These relations areused to make rulesets.
4. Learning rulesets. After analyzing training documents, asystem constructs a ruleset by our learning algorithm.
We explain the learning algorithm in detail in Section 3.
5. Query modification and next search. A system modifies aquery using expanded keywords, and then makes a new
document ranking using the modified query.
6. Ranking refinement. Before showing a new document
ranking, a system refines the ranking using a ruleset.
Refinement procedure is simple. As shown in Fig. 2, asystem checks a document from top of the ranking. Only
if a document is identified as non-relevant by a ruleset,
the document is moved to the lowest rank of the ranking.
After all, this procedure classifies documents with thepreservation of the order of each document ranking.
This refined ranking is shown to a user. If he/she does notsatisfy the ranking, he/she repeats from the evaluation
procedure of this process.

explain description of a ruleset and a learning algorithm indetail.
3.1. Rule representation
A ruleset is a set of rules, each of which is represented in
the form of Horn clause. A rule consists of two parts—ahead part and a body part. For all the rules, a head part isrepresented in a unique form, ‘rel(A):-.’ (.is a body part).
It means a document A is relevant if it satisfies a condition
described in a body part. A body part is a conjunction of thefollowing two types of literals.
ap(A, wi)This literal is true iff a word wi appears in adocument A.
near(A, wi, wj) This literal is true iff both words wi and wj
appear within a sequence of n words
somewhere in a document A. We do notcare about the appearance order of those
two words.
Each literal describes a feature, which is useful tocharacterize a document. Combining several features, a ruleprovides requirements for identifying a document as
relevant. In general, as the number of documents to becovered increases, we need more rules if we want to specify

This process can be used not only to overcome thedrawbacks of traditional relevance feedback, but to improve
the performance of many kinds of IR systems.
3. Learning rulesets
In Section 2, we described an overview to learn and apply
a ruleset in the process of relevance feedback. Here, weFig. 2. Ranking refinement.

120

M. Okabe, S. Yamada / Knowledge-Based Systems 18 (2005) 117–124

each document precisely. Thus, a ruleset usually consists ofseveral rules like below](relðAÞ : -apðA; mammalÞ; nearðA; species; protectÞ:relðAÞ : -apðA; speciesÞ; nearðA; mammal; protectÞ:This ruleset means that a document A is relevant if aword ‘mammal’ appears in A, and ‘species’ and ‘protect’closely appear in A, or ‘species’ appears in A, and ‘mammal’and ‘protect’ closely appear in A.
3.2. An extension for semi-structured documents
Information resources are not only plain texts, but semistructured ones like Web pages, which are decorated with aset of tags (e.g. a tag set of HTML). Since some of themwork well as features to discriminate documents [14,15], we
extend above literals by adding an argument of region,
which specifies a position of a literal in a document withseveral kinds of tags. The meaning of each tag is slightly
changed as follows.

For example, we can choose the following tags which
can be instances of region for Web pages.
† title. This specifies an area surrounded by !TITLEO
and !/TITLEO tags.
† anchor. This specifies an area surrounded by !A
HREFZ.O and !/AO.
† head. This specifies an area surrounded by !HnO and!/HnO tags (nZ1–4).
† para. This specifies an area surrounded by !PO and!/PO tags.
We can obtain the following ruleset with extended
literals(relðAÞ : -apðA; title; mobileÞ; apðA; anchor; PDAÞ:relðAÞ : -nearðA; para; palm; osÞ:This ruleset means that a Web page is relevant if a word
‘mobile’ appears in the title and ‘PDA’ appears in an anchor
text, or ‘palm’ and ‘OS’ closely appear in the same
paragraph.

ap(A, region, wi)This literal is true iff a word wiappears within a region of region ina document A.
near(A, region, wi, wj) This literal is true iff both of words
wi and wj appear within a sequenceof n words somewhere in a region ofregion of a document A. We do notcare about the appearance order of
those two words.

3.3. Learning algorithm
Fig. 3 shows our learning algorithm to make a ruleset.
This algorithm generates a set of rules under the separateand-conquer strategy [16]. According to this strategy, one
rule is made at a time. When a rule is generated, it is added toa rule set R, and relevant documents covered with thisrule are removed from EC. This procedure continues until

Fig. 3. Learning algorithm.

M. Okabe, S. Yamada / Knowledge-Based Systems 18 (2005) 117–124

EC becomes empty. A rule starts from an empty conjunctionof conditions, and develops by adding a gainful literal one
after another until it excludes all the elements of EK. Gainful
literals are selected from a set C of candidate literals, which
are prepared by inserting keywords into the two types offeatures. The procedure to prepare literals is as follows.
1. For each of keywords, make an ap literal.
2. For each combination of keywords, make a near literal.
3. Examine these literals are true or not in each training
document and record those information.
For a brief example, if there are the following keywords
fmammal; species; protectg;
this algorithm first prepares a set of literals like below
98apðA; mammalÞ nearðA; mammal; speciesÞ >>=<;apðA; speciesÞ nearðA; species; protectÞ
>>;:apðA; protectÞ nearðA; protect; mammalÞ
The most gainful literal has the highest value of
information gain calculated by the following formula [17]42
42
G Z e4after fIðebefore ; ebefore Þ K Iðeafter ; eafter Þg;e4Iðe4; e2Þ Z Klog2 4 2 ;
e Ce
2
4
2
The e4
before ; ebefore ; eafter ; eafter are, respectively, the numbers of relevant and non-relevant documents covered withthe before and after appending a literal.
Rule construction using information gain is efficientbecause it is basically greedy search. However, in this type ofsearch, it sometimes selects a bad literal and stops before
completion. Thus, we incorporated backtracking mechanism
into this algorithm. Backtracking is a mechanism to avoid
deadlock of search. In our algorithm deadlock occurs when
there is no literal to be selected on the way of rule
construction. In such a case, this algorithm stops the present
search and restart from the first literal selection. The point
here is that our algorithm restarts from the first literal
selection. Normal backtraking restarts from one previous step
selection. However, this method often makes a futile searchbecause we empirically observed the importance of the firstliteral selection is much higher than the second, third or theother ones. Thus, our backtracking method can avoid much
redundant search compared to the normal backtracking.

documents. In both experiments, relevance feedback was
conducted following the procedures described in Section 2.
4.1. Experiment 1: IR with a traditional system
4.1.1. Settings
In this experiment, a query is a vector of word weights.
Query words are initially set to five words, and 15 words areautomatically added after first feedback. After every
feedback, those 15 words are replaced by a set of new 15
words selected from training documents with a simple
query expansion method [18]. Word weights are calculated
by a method which is proven to be quite effective in theframework of the vector space model [6], and are modified
by the formula shown in Section 2 after every feedback.
As a document database, we used a set of newspaper
articles (The Los Angels Times, about 130,000 articles, ave.
526 words/article), which is a part of TREC-7 collection[19]. This collection provides topics (subjects of retrieval, or
test questions) and relevance judgments (lists of relevant
documents for each subject). We selected 20 topics in which
each has more than 40 relevant documents because
relevance feedback is usually used to collect not a few
relevant documents.
In order to evaluate the effectiveness of our approach, wetested two types of relevance feedback. One is a feedback
based only on query reformulation (we call this VSM). The
other is a feedback based not only on query reformulation,but on filtering with a ruleset (we call this RULE). In eachcycle, we carried out four iterations of feedback. At each
feedback, top 10 documents were used as training documents(except for the documents which had already been seen).
Training documents were accumulated for the next feedback
to be used to create a new query and a new ruleset.
4.1.2. Results
Fig. 4 shows the average performance of 20 topics. We
conducted four feedbacks about one topic. The horizontal
line means the number of feedbacks and the vertical line
means the average of the three-point average precision
for 20 topics. Three-point average precision is the meanof precisions at recall 0.25, 0.5, 0.75, where recall is defined

4. Experiments
We evaluated our method in two types of IR systems. One
is a traditional IR system, which uses the vector space model
as a retrieval model and a newspaper collection as database.
The other is a Web search engine. We use this as arepresentative of systems, which retrieve semi-structured

121

Fig. 4. Average performance of 20 topics.

122

M. Okabe, S. Yamada / Knowledge-Based Systems 18 (2005) 117–124

as the proportion of relevant documents that are retrieved
from the collection, and precision is the proportion of
retrieved documents that are relevant. This value is often used
to evaluate the total performance of retrieval methods.
The effects of RULE are rising after the third feedback
because we cannot usually get enough relevant documents
which are necessary to create a good ruleset at an early stageof feedback. Comparing the third results with the fourthones, RULE keeps improving the performance though VSM
has no improvements as seen in the graph. Actually, it istestified in another experiments that RULE can keep
improvements much longer than VSM. In addition, RULE
can improve the performance of a certain topics which VSM
cannot improve.
Table 1 compares three-point average precisions of the
rankings that each of two systems VSM and RULE
produced after nth feedback (nZ1–4). In the table, TOPIC
corresponds to the topic number provided by the TREC. INI
is the results of the initial retrieval. The effectiveness of
RULE for a topic considerably differs from each other. For
more than half of topics, RULE improves retrieval
performance compared to VSM. Though some topics haveno improvements or even worse results, those effects aremuch less than the improvements of other topics.
Table 2 shows another values which are the number of
relevant documents included in training documents, If a user
conducts the procedures described in Section 2, thesenumber correspond to the number of relevant documents
which he/she actually found during a retrieval process.
Different from the results of threes-point average precision,
RULE can get more relevant documents than VSM inalmost all the situation.
Table 1Comparison of VSM and RULE (three-point average precision)
Topic

301
304
306
315
332
335
343
349
354
358
360
366
367
368
370
374
383
390
393
398
Ave.

INI

0.36
0.11
0.09
0.04
0.17
0.73
0.10
0.10
0.14
0.38
0.20
0.01
0.00
0.53
0.04
0.08
0.04
0.26
0.03
0.51
0.20

VSM

RULE

1

2

3

4

1

2

3

4

0.56
0.08
0.01
0.03
0.39
0.78
0.04
0.54
0.06
0.42
0.29
0.30
0.00
0.74
0.04
0.25
0.02
0.69
0.05
0.70
0.30

0.57
0.11
0.02
0.05
0.43
0.78
0.07
0.49
0.05
0.36
0.37
0.38
0.00
0.63
0.01
0.39
0.06
0.66
0.26
0.60
0.32

0.52
0.12
0.03
0.04
0.45
0.79
0.07
0.52
0.04
0.35
0.38
0.31
0.00
0.51
0.06
0.40
0.12
0.61
0.22
0.69
0.31

0.53
0.11
0.02
0.05
0.45
0.78
0.07
0.48
0.04
0.36
0.32
0.38
0.00
0.45
0.06
0.41
0.11
0.60
0.27
0.65
0.31

0.53
0.10
0.01
0.04
0.38
0.65
0.04
0.64
0.11
0.41
0.18
0.08
0.00
0.80
0.04
0.07
0.02
0.72
0.01
0.55
0.27

0.55
0.24
0.11
0.05
0.39
0.58
0.08
0.42
0.06
0.37
0.55
0.13
0.00
0.83
0.01
0.43
0.06
0.68
0.06
0.52
0.31

0.68
0.32
0.03
0.04
0.71
0.73
0.12
0.56
0.07
0.37
0.47
0.10
0.00
0.50
0.11
0.47
0.14
0.67
0.08
0.67
0.34

0.67
0.35
0.06
0.05
0.72
0.84
0.11
0.70
0.09
0.55
0.36
0.33
0.00
0.85
0.05
0.39
0.05
0.65
0.24
0.72
0.39

Table 2Comparison of VSM and RULE (the number of relevant documents intraining sets)
Topic

301
304
306
315
332
335
343
349
354
358
360
366
367
368
370
374
383
390
393
398
Ave.

INI

4
3
1
2
6
9
2
4
2
8
6
3
0
8
0
5
2
6
1
6
3.9

VSM

RULE

1

2

3

4

1

2

3

4

9
7
2
2
16
19
3
13
7
13
11
9
0
17
0
10
2
16
8
16
9.0

13
8
2
3
25
26
4
16
10
14
14
11
0
21
4
12
7
23
13
22
12.4

15
8
2
3
34
32
4
17
11
14
14
12
1
22
5
15
9
27
15
25
14.2

17
9
2
3
43
34
4
18
11
14
14
14
1
22
6
19
11
29
16
26
15.7

8
6
2
2
16
19
5
13
11
13
12
5
0
18
0
11
3
16
9
15
9.2

16
11
3
3
25
27
7
17
13
16
17
8
0
26
4
16
5
23
11
17
13.2

22
12
3
3
35
32
8
19
16
20
19
9
1
30
6
22
8
28
12
23
16.4

28
13
5
4
45
35
11
21
21
23
19
14
1
35
6
24
12
32
16
27
19.6

4.2. Experiment 2: IR with a web search engine
4.2.1. Settings
In this experiment, we use a Web search engine as IR
system in Fig. 1. Since we have no standard IR model in thiscase, we compare the quality of original rankings (hit lists)
with refined ones, which is filtered by our rulesets. As in theprevious experiment, we used 20 topics which are parts oftest questions in the TREC-8 Small Web Track [20], andmanually judged 50 Web pages from top-ranked ones. To
make a refined ranking, we remake a ruleset which is used tofilter the rest of documents in the original ranking after
finishing judgment of 10 Web pages. Thus we make a newruleset four times in each cycle. A retrieval cycle with nofiltering, namely, a cycle of checking an original hit list iscalled WSE. The other cycle, which iteratively makes anduses a ruleset, we call this cycle RULE. We used the Google
search engine1 as a test Web search engine, which isrecognized as one of the most powerful search engines.
Fig. 5 shows an interface which mediates for a search tointeract with a Web search engine. This interface provides
several functions like check buttons for marking therelevancy of each item in a hit list. It also makes a ruleset
based on the above marking, and filter a hit list returned by a
Web search engine.
4.2.2. Results
Table 3 compares the number of relevant documents
which are found after nth feedback in each cycle of WSE
1

http://www.google.com

M. Okabe, S. Yamada / Knowledge-Based Systems 18 (2005) 117–124

123

Fig. 6. The number of relevant pages.

that our system effectively worked, and a bad one that oursystem did not work well.

Fig. 5. Interface for relevance feedback on the Web.

and RULE. TOPIC and INI indicates the same meaning as
in the previous experiment.
The difference in the number of relevant pages constantly
increases after the first feedback for every topic as seen in
Fig. 6. Moreover RULE is superior to WSE in all thesituations though the performance differs for each topic. Asan average result, RULE got about five relevant Web pages
more than WSE after the fourth feedback (after finishing themarking of 50 Web pages).

5. Discussion
As seen in the results of the previous two experiments,
the retrieval with our system enhanced the effectiveness formost topics. We show two types of examples, a good one
Table 3Comparison of WSE and RULE
Topic

INI

401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
Ave.

2
6
3
3
2
7
2
6
7
4
1
3
6
4
8
7
5
4
5
5
4.5

WSE

“Income Tax Evasion
This query is looking for investigations that havetargeted evaders of US income tax.”
This is a precise description of no. 332 topic used in the firstexperiment. Relevant documents for this topic include words
like ‘income’, ‘tax’, ‘evasion’ ‘fraud’, ‘court’, ‘trial’, ‘illegal’and so on. Those words, however, appear frequently in somany and various types of documents. In VSM, many
documents about ‘fraud crime’ and ‘illegal crime’ which are
not related to this topic are retrieved. In contrast, RULE
carefully selected documents using a ruleset shown in Table 4.
This ruleset emphasizes proximity relations among words,
which actually filter out much non-relevant documents.
In the second experiment, topic no. 12 shows very goodresults. The description of this topic is as follows.
“Airport Security
What security measures are in effect or are proposed to
go into effect in airports?.”

RULE

1

2

3

4

1

2

3

4

6
8
10
5
4
14
3
11
10
7
8
8
9
8
13
12
9
9
10
12
8.8

11
8
17
7
6
20
7
14
11
10
15
9
12
9
15
15
10
11
13
17
11.9

13
8
23
10
6
28
13
19
14
14
15
11
16
10
23
23
12
14
14
23
15.5

13
9
31
15
6
32
19
24
15
20
19
14
18
11
27
27
15
15
16
29
18.8

6
8
11
7
3
14
9
12
10
9
7
9
9
6
11
14
10
9
10
12
9.3

10
9
18
10
6
21
13
19
13
13
10
16
12
12
17
18
15
14
13
19
13.9

15
14
26
11
7
29
20
25
15
15
14
22
16
17
22
24
17
23
17
27
18.8

22
19
35
15
10
35
27
28
22
21
14
27
19
21
28
29
20
28
18
35
23.7

The objective of topic 412 is ‘to identify a specific airportand describe the security measures already in effect or
proposed for use at that airport’. WSE returns many nonrelevant Web pages which introduce ‘the security, which
travelers must prepare,’. In contrast, RULE carefully
selected documents using a ruleset shown in Table 5. This
ruleset emphasizes single words by tags, and utilizes
proximity relations to specify the meaning of words. For
example, ‘faa’ and ‘system’ in the fourth rule are very
abstract words in general. Considering together, however,‘faa’ indicates the federal aviation administration in
Table 4
A ruleset for topic no. 332
rel(A):- near(A, charge, hunter), ap(A, count)rel(A):- near(A, income, evasion)rel(A):- ap(A, evasion), near(A, tax, hunter)rel(A):- near(A, evasion, convict), ap(A, illegal)rel(A):- near(A, convict, charge)

124

M. Okabe, S. Yamada / Knowledge-Based Systems 18 (2005) 117–124

Table 5
A ruleset for topic no. 412
rel(A):- ap(A, anchor, screening)rel(A):- near(A, para, security, system), ap(A, title, airport)rel(A):- near(A, para, security, airports), near(A, para, security, access)rel(A):- near(A, para, security, airports), near(A, para, faa, system)

Table 6
A ruleset for topic no. 411
rel(A):- ap(A, anchor, shipwreck)rel(A):- ap(A, anchor, shipwreck), ap(A, anchor, salvaging)

the United State, and ‘system’ indicates a system about
aviation, especially security system in airports.
As these examples show, rulesets work very well if themeanings of keywords can be straiten by pairing two words.
In spite of the usefulness of rulesets, we must care aboutsome noisy rules, which may sometimes be built. A ruleset
shown in Table 6 is an example ruleset that did not work
well. This ruleset is built for topic no. 411 which has thefollowing description.
“salvaging, shipwreck, treasure
Find information on shipwreck salvaging: the recovery
or attempted recovery of treasure from sunken ships.”
Relevant pages for this topic include various types ofpages such as links, bulletin board, news and individual
home pages. This ruleset is too general to select pages
appropriately because it uses only two keywords which are
generally insufficient to restrict relevant pages.

6. Conclusion
We proposed an approach for refining a document
ranking by learning filtering rulesets through relevance
feedback. Relevance feedback can be regarded as a processof producing a refined document ranking. Our approachdirectly refines a document ranking by removing nonrelevant documents based on a ruleset. Experiments showthat our learning algorithm can extract useful word
relations, which are effective to identify relevant documents
accurately. Analyzing rulesets learned through relevance
feedback, we confirmed how each rule restricts relevant
documents. We also showed that the possibility to apply ourapproach into relevance feedback with Web search engines.
To utilize tags more effectively is future work.

References[1] G. Salton, C. Buckley, Improving retrieval performance by relevance
feedback, Journal of the American Society for Information Science 41(1990) 288–297.

[2] W.W. Cohen, Text categorization and relational learning, in:Proceedings of the Twelveth International Conference on Machine
Learning, Morgan Kaufmann, Los Altos, CA, 1995, pp. 124–132.
[3] G. Salton, E.A. Fox, E. Voorhees, Advanced feedback methods in
information retrieval, Journal of the American Society for Information
Science 36 (3) (1985) 200–210.
[4] D. Haines, W.B. Croft, Relevance feedback and inference networks,
in: Proceedings of the Sixteenth Annual International ACM SIGIR
Conference on Research and Development in Information Retrieval,
1993, pp. 2–11.
[5] J.J. Rocchio, Relevance feedback in information retrieval, in:
G. Salton (Ed.),, The SMART Retrieval System: Experiments in
Automatic Document Processing, Prentice-Hall, Englewood Cliffs,
NJ, 1971, pp. 313–323.
[6] C. Buckley, The importance of proper weighting methods, in:Proceedings of ARPA Human Language Technology Workshop’93,
Morgan Kaufmann, Los Altos, CA, 1994, pp. 349–352.
[7] M. Mitra, A. Singhal, C. Buckley, Learning routing queries in a query
zone, in: Proceedings of the Twentieth Annual International ACM
SIGIR Conference on Research and Development in Information
Retrieval, 1997, pp. 25–33.
[8] C. Buckley, G. Salton, Optimization of relevance feedback weights,
in: Proceedings of the Eighteenth Annual International ACM SIGIR
Conference on Research and Development in Information Retrieval,
1995, pp. 351–357.
[9] J. Callan, Document filtering with inference networks, in: Proceedings of
the Nineteenth Annual International ACM SIGIR Conference
on Research and Development in Information Retrieval, 1996, pp.
262–269.
[10] T. Joachims, Text categorization with support vector machines:
learning with many relevant features, in: Proceedings of the TenthEuropean Conference on Machine Learning, vol. 1398 of LNAI,
Springer, Berlin, April 21–23 1998.
[11] D.D. Lewis, An evaluation of phrasal and clustered representations on
a text categorization task, in: Proceedings of the Fifteenth Annual
International ACM SIGIR Conference on Research and Development
in Information Retrieval, 1992, pp. 37–50.
[12] J. Xu, W.B. Croft, Query expansion using local and global document
analysis, in: Proceedings of the Nineteenth Annual International ACM
SIGIR Conference on Research and Development in Information
Retrieval, 1996, pp. 4–11.
[13] A. Singhal, M. Mitra, C. Buckley, Improving automatic query
expansion, in: Proceedings of the 21st Annual International
ACM SIGIR Conference on Research and Development inInformation Retrieval, Query and Profile Modification, 1998, pp.
206–214.
[14] W.W. Cohen, W. Fan, Learning page-independent heuristics for
extracting data from Web pages, Computer Networks (Amsterdam,
Netherlands: 1999) 31 (11–16) (1999) 1641–1652.
[15] M. Okabe, S. Yamada, Interactive web page filtering with relational
learning, in: Proceedings of the First Asia-Pacific Conference on WebIntelligence, 2001, pp. 443–447.
[16] J. Fürnkranz, Separate-and-conquer rule learning, Artificial Intelligence Review 13 (1) (1999) 3–54.
[17] J.R. Quinlan, R.M. Cameron-Jones, Induction of logic programs:
FOIL and related systems, New Generation Computing, Special issue
on Inductive Logic Programming 13 (3/4) (1995) 287–312.
[18] M. Okabe, S. Yamada, Interactive document retrieval with relational
learning, in: Proceedings of Sixteenth ACM Symposium on Applied
Computing, 2001, pp. 27–31.
[19] E. Voorhees, D. Harman, Overview of the Seventh Text REtrieval
Conference, 1998.
[20] E. Voorhees, D. Harman, Overview of the eighth Text REtrieval
Conference, 1999.