Interactive Document Retrieval with Relational Learning
Masayuki Okabe and Seiji Yamada
CISS, IGSSE, Tokyo Institute of Technology
4259 Nagatuta Midori-ku
Yokohama, JAPAN{okabe, yamada}@ymd.dis.titech.ac.jp

Keywords
information retrieval, relevance feedback, relational learning

ABSTRACTThis paper describes an approach to enhance the eﬀectiveness of human help in interactive document retrieval, where
the system supports the user to ﬁnd documents eﬀectively
through relevance feedback. At present vector space model
is a typical representation method to realize relevance feedback. However it can neither express relationship such as
proximity nor keep several features separately. We supplement these defects with a set of rules, which are constructed by relational learning and used to identify relevant
documents. The learning algorithm consists of separateand-conquer strategy and top-down heuristic search withlimited backtracking. Background relations are made only
from keywords, thus constructed rules represent useful keyword combinations to search relevant documents. We evaluate the eﬀectiveness of our approach on document retrieval
experiments using a test bed database. The results show ourmethod enhances both eﬀectiveness and eﬃciency compared
to a normal method with only query vector.

1. INTRODUCTION
Document retrieval is an essential part of an IR (Information
Retrieval) system which has recently become an indispensable tool to utilize a large number of electronic documents.
One of the important requirements for the system is eﬀective search through human computer interaction becauseof the limitation of fully automatic IR. Such approach has
been studied under relevance feedback[9], which is a commonly accepted process of improving retrieval eﬀectivenesswith human help. The system with relevance feedback usually repeats retrievals until the user satisﬁes his informationneed. After each retrieval, he is asked to judge a small partof the results and indicate relevant documents from them.
These documents will be used to extract valid information
so as to return newly better results. Since the eﬀectiveness

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
SAC 2001, Las Vegas, NV
Copyright 2001 ACM 1-58113-324-3/01/02 ..$5.00

of relevance feedback signiﬁcantly depends on the extraction method, several ones have been proposed[5, 10]. However they are based on statistical ways, which hardly extract
structural patterns such as the positioning of the words indocuments. Recently machine learning techniques has beentested in IR and revealed to be hopeful for more eﬀective
IR.[1, 2, 3]
In this paper, we propose an eﬀective extraction method
using relational learning. Relational learning is a machinelearning technique developed mainly in ILP(Inductive Logic
Programming)[7], which is superior to learn relational patterns such as protein secondary structure. We applied thistechnique to the extraction of characteristic document structures. They are represented in the form of logical rules which
consist of propositional and proximity relations[6] amongwords in documents. We use these rules in order to decide
whether a document is relevant to our need or not, thus wecall them decision rule. Our learning algorithm constructs
as many rules as possible until they cover all the relevant
documents. This strategy is very eﬀective since every relevant document doesn’t have the same feature. To verify
the structural relation is promising information for precise
IR, we fully implemented our IR system which integrated
relevance feedback and relational learning. Then we makeexperiments in which we applicate our approach to a traditional statistical IR system.
The reminder of the paper is organized as follows. Section 2
describes the interactive process and the way how to apply
relational learning. Section 3 describes the representationand the learning algorithm for decision rule. Section 4 mentions experiments and the results using a test bed databaseof newspaper.

2. INTERACTIVE RETRIEVAL PROCESS
Recent high capacity hardwares allow us to manage larger
document databases than before. Information retrieval fromsuch databases becomes diﬃcult when we want to obtain as
many of relevant documents as possible. In such a situation,
we usually have to iterate search by changing query in orderto minimize the reviewing of documents. Interactive process
is useful for such a task and relevance feedback is the mostsuccessful method until now. It can shield the user from thedetails of the query formulation and break down the search
operation into a sequence of small search steps by utilizing
human feedbacks[11].

Document Database

Initial Input

Query Vector
matching
requestgenerate

Decision Rule

Retrieval Systemmodifyranking

Results
relevant
documents

non-relevant
documents
evaluation

modifyThe use of decision rule is the unique point of this research,which has not been tested before. The rules are constructedby the algorithm based on relational learning. They arecomposed of several rules and each rule mainly represents
the characteristic positioning of keywords. We describe themin the next section.

3. DECISION RULE
This section explains decision rule in detail. We deal withthe construction of the rules as learning problem, in which
relevant and non-relevant documents are training examples.

3.1 Rule representation
We use horn clause to represent rules. The body of a ruleconsists of the following relations.

No.1 document1
No.2 document2
No.3 document3
No.4 document4
No.5 document5

No.1 document2
No.2 document4
No.3 document5
No.4 document1
No.5 document3

Figure 2: Ranking modiﬁcation
We can represent various features of documents by combining these relations. Here is an example set of rules.



Relevant feedback was developed with vector type query(wecall this query vector ) and has been one of the best match
representations. It is a popular retrieval model nowadays,
thus we use it as a basic interactive retrieval model and integrate our decision rule into this model. Figure 1 shows
the model. Here we describe the outline of the process.
For precise procedures are explained in Section 4. At ﬁrst
the user inputs initial query(generally a few words) into thesystem. Then the system makes a vector whose elements
are the weights of input words. With that vector, the system ranks all the documents in the database and returns
the results to the user. After the user evaluates a certain
group of documents, if he is satisﬁed with the results, thisretrieval process ﬁnishes. If not, he can ask the system toreturn another results by indicating each relevancy of thejudged documents. According to this information, the system modiﬁes the vector and ranks all the documents again.
In addition to this process, in our model a set of decisionrules is generated. As shown in Figure 2, we use them tochange the document ranks attached by the vector matching. The documents which satisfy the condition of the rules
have higher rank with this method.

Modified ranking withdecision rules: matched with decision rule: not matchedNo.1 .............
No.2 .............
No.3 .............
..............................
..............................
..............................

Figure 1: Interactive retrieval process

Original ranking
with query vectorrel(A) :- ap(A, mammal), near(A, species, protect).
rel(A) :- ap(A, species), near(A, mammal, protect).

They mean that a document A is relevant if “mammal”
appear in A and “species”, “protect” closely appears in A,
or “species” appears in A and “mammal”, “protect” closely
appears in A.

3.2 Learning algorithm
Figure 3 shows the learning algorithm for decision rule. Thisalgorithm generates a set of rules under the separate-andconquer strategy[4]. According to this strategy, one rule ismade at a time. When a rule is generated, it is added toa rule set R and relevant documents covered with this ruleare removed from E + . This procedure continues until E +becomes empty.
A rule starts from a empty clause and develops by adding
a gainful literal one after another until it excludes all theelements of E − . Gainful literals are selected from a set C of
candidate literals, which is prepared by inserting keywords
into the two types of relations. The procedure to prepare is
as follows.
1. For each of keywords, make ap literal.
2. For each combination of keywords, make near literal.
3. Examine these literals are true or not in each example
document and record these information.
For a brief example, if there are the following keywords,{mammal, species, protect}a set of literals like below is prepared.

89< ap(A, mammal) near(A, mammal, species) =ap(A, species) near(A, species, protect): ap(A,;
protect) near(A, protect, mammal)• ap(A, wi ) : This literal is true iﬀ a word wi appears ina document A.

The most gainful literal has the highest information gain
calculated by the following formula[8].

• near(A, wi , wj ) : This literal is true iﬀ both words wi
and wj appear within a sequence of 5 words somewhere
in a document A. We don’t consider the order of thewords in near literal.

⊕⊕G = e⊕
af ter {I(ebef ore , ebef ore ) − I(eaf ter , eaf ter )}e⊕I(e⊕, e) = −log2 ⊕e + e

InputE + : relevant documents
E − : non relevant documents
C : literal candidates
OutputR : a set of decision rules
Variablerule : a rule
S : exception literals
Initialize
R ← empty
S ← empty
rule ← rel(A) :Repeat
if rule exclude all the documents of E − then· add rule to R and rsemove documents
covered by rule from E +if E + becomes empty then exit
else initialize rule and S
else
for each literal in C except ones in S,
calculate information gain G
if no literal such as G > 0 then exit
if rule is empty clause then exitelse
· initialize S· append the ﬁrst literalin the body of rule to S
· initialize ruleelse
· add the most gainful litaral to rule and S
Figure 3: Learning Algorithm⊕The e⊕
bef ore ，ebef ore ，eaf ter ，eaf ter are respectively the numbers of relevant and non-relevant documents covered withthe rule before and after appending a literal.

Rule construction using information gain is eﬃcient because
it is greedy. However it sometimes selects bad literal andstops before completion. Thus we incorporated a backtrackmechanism into this algorithm. Backtrack occurs when there
is no literal to select despite rule still covers non-relevant
documents. For such an occasion, this algorithm tries again
from the ﬁrst literal selection. This method usually avoids
redundant search.

Ltu

1 + log(tf )1 + log(average tf in text)
N +1)= log(
df
1=nw
0.8 + 0.2
average nw per document
=

nw
tf

:
:

number of unique words in text
term’s frequency in text

N
df

:
:

total number of relevant documents
number of documents that contain the term

Lnu weighting = L ∗ u
Ltu weighting = L ∗ t ∗ uTable 1: Term weights
more than 40 relevant documents. Judgments are the recordof relevant articles for each topic.

4.2 Retrieval steps
Here are the steps involved in the use of decision rule.
1. Initial search : Create query vector whose elements are
the weight of 5 keywords selected from the topic statement, and set the same weight to each keyword. Using
this vector, rank all the documents in a database which
are represented as Lnu weighted vectors.
2. Judging 20 documents from the top of the results, prepare a set of training documents(E+ and E − in section3) for feedback.
3. Pick up 3 words from E + which have the top 3 highest
value v calculated by the following formula.
v = ( average tf in E + ) × ( df in E + )tf and df are the same in Table 1. This procedure iscalled query expansion which is necessary for eﬀective
IR because the user usually doesn’t know the usefulwords beforehand.
4. Modiﬁes the query vector q according to the following
formula[11].
qnew = qold +Xd − dnotd∈E +4. EXPERIMENTS AND RESULTS
We made retrieval experiments for testing our algorithm according to the process described in section 2.

4.1 Test collection
We used a test collection provided by the TREC[13] as a
document database. It is a popular collection used in various
IR researches. From this collection, we selected a set ofnewspaper articles(The Los Angels Times, about 130,000
articles, ave. 526 words/article). We also used a set of topics
and their judgments attached to this database. Topics are
the statements described about requirements for relevant
documents. We selected 20 topics from them which haved is a Ltu weighted vector made from each documentin E + . dnot is a Ltu weighted vector made from themost high ranked non-relevant document in E − . Using
modiﬁed query vector, rank all the documents.
5. According to the learning algorithm described in section 3, make a set R of decision rule s. Using R, change
the ranking of all the documents.
6. Goto step2.
Step 1 is a manual procedure and the other was automatically done by the system. Lnu and Ltu weighting methods

1

1

Precision Difference

Precision

0.8
retrieval1
retrieval2
initial search

0.6

0.4

0.2

0

0.5

0

-0.5

-1
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

1

2

3

4

5

6

7

8

RecallFigure 4: recall−precision curve after 1 feedback

Figure 6: precision diﬀerence after 1 feedback
1

1

Precision Difference

0.8Precision

9 10 11 12 13 14 15 16 17 18 19 20
Topic Number

retrieval1
retrieval2
initial search

0.6

0.4

0.5

0

-0.5

0.2

-1

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20
Topic Number

RecallFigure 5: recall−precision curve after 4 feedbacks

Figure 7: precision diﬀerence after 4 feedbacks

are shown in Table 1. The combination of vector and thisterm weighting is one of the best statistical way in modern
IR[12].

the curve is its location in a graph. The curve of retrieval1
always lie over retrieval2 in both graphs. This means thatdecision rule enhances the eﬀectiveness of relevance feedback.

In order to evaluate the eﬀect of decision rule, we carriedout two series of the above steps for each topic. The one isa retrieval with decision rule(act no.5 step), the other is a
retrieval without decision rule(don’t act no.5 step). In each
retrieval, we repeated the above steps until 4 feedbacks(4loops) ﬁnished.

Figure 6 and Figure 7 shows the performance for each topic.
Let p1 and p2 be the average precision at 3 recall point(0.25,
0.5, 0.75) of retrieval1 and retrieval2 respectively, precision
diﬀerence is calculated as follows.

4.3 Results
We used recall and precision measures to evaluate retrieval
eﬀectiveness, where recall is deﬁned as the proportion of
relevant documents that are retrieved from the collection,and precision is the proportion of retrieved documents thatare relevant. Suppose that we examined x documents andfound y relevant documents from them. If there are z relevant documents in the whole collection, recall and precision
are calculated as follows.
yyRecall =P recision = ,xzFigure 4 and Figure 5 shows the recall−precision curves
made of the results after 1 and 4 feedbacks. This curveis commonly used to evaluate the total performance of amethod, in which the precision value is plotted at each recall value ranging from 0.1 to 1.0. In our experiment, theprecision is the average value of 20 topics. The curve indicated by retrieval1 shows the performance of the retrieval
with decision rule, and retrieval2 shows the one without
decision rule. The criterion to evaluate the performance of

P recision Dif f erence = p1 − p2
After 1 feedback, decision rule works well for only a few topics. After 4 feedbacks, however, half of topics have positive
diﬀerence and no topic has negative diﬀerence.

4.4 Analysis
According to the results, it reveals that the eﬀect of decision
rule diﬀers from every topic. In this section, we present a
good example set of decision rules and a bad one which
are constructed during retrievals. The following is a sample
topic in which decision rule worked very well. Here is thestatement of the topic.
− “Income Tax Evasion
This query is looking for investigations that have targeted evaders of U.S. income tax ...”
Relevant documents for this topic relatively often use thewords of ’income’, ’tax’, ’evasion’, ’fraud’, ’court’, ’trial’, ’illegal’. However there are so many other documents using
these words. Thus query vector retrieved much documents
concerned with “fraud crime”, “illegal crime”, “supreme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).

rel(A) :- near(A,blood,alcohol),ap(A,caus).
rel(A) :- near(A,blood,alcohol),near(A,car,kill).
rel(A) :- near(A,accident,legal).
rel(A) :- near(A,three,kill).
rel(A) :- near(A,automobil,kill).

Table 2: An example set of eﬀective decision rule

Table 3: An example set of ineﬀective decision rule

court”, most of which have no relation to this topic. In
contrast, decision rule listed in Table 2 distinguished documents precisely because it makes various features matchingclosely to relevant documents.

Annual International ACM SIGIR Conference on
Research and Development in Information Retrieval,
pp.2-11 (1993)

The next example is a representative of bad decision rule.
The statement for this topic is as follows.
− “blood-alcohol fatalities
What role does blood-alcohol level play inautomobile accident fatalities? ...”The rule set showed in Table 3 seems to be very eﬀective
for this topic. However the fourth rule spoils the other rules
because the combination of ’three’ and ’kill’ is no relation
to this topic. This is mainly caused by adding ’three’ inautomatic query expansion step. Avoiding such fail is futurework.

5. CONCLUSION
We applied relational learning to document retrieval which
utilizes interaction between human and computer throughrelevance feedback. We proposed the use of decision rule
made with relational learning technique, and presented theirrepresentation and learning algorithm. We ﬁnally evaluatedtheir eﬀectiveness compared to a statistical method on retrieval experiments.
Our learning method constructs eﬀective rules combinedwith good keywords and good relations which general users
scarcely create. Our method also can be useful for searching
web pages in the WWW because Web pages are structured
text and seem to have useful relations. Thus we are developing an IR system using relational rules in the WWW.

REFERENCES[1] Caliﬀ, E.M.: Relational Learning of Pattern-Match
Rules for Information Extraction, Proceedings of the
Sixteenth National Conference on Artificial
Intelligence, pp.328-334 (1999)[2] Chen, H.: Machine Learning for Information Retrieval:
Neural Networks, Symbolic Learning, and Genetic
Algorithms, Journal of the American Society for
Information Science, Vol.46, No.3, pp.194-216 (1995)[3] Cohen, W.W.: Text categorization and relational
learning, Proceedings of the Twelfth International
Conference on Machine Learning, pp.124-132 (1995)[4] Furnkranz, J.: Separate-and-Conquer Rule Learning,
Artificial Intelligence Review, Vol.13, No.1 (1999)[5] Haines, D., Croft, W.B.: Relevance feedback andinference networks, InProceedings of the Sixteenth[6] Keen, E.M.: Some aspects of proximity searching intext retrieval system, Journal of Information Science,
Vol.18, No.2, pp.89-98 (1992)[7] Muggleton, S.: Inductive logic programming, New
Generation Computing, Vol.8, No.4, pp.295-318 (1991)[8] Quinlan, J.R., and Cameron-Jones, R.M.: Inductionof Logic Programs: FOIL and Related Systems, New
Generation Computing, Vol.13, Nos.3,4, pp.287-312(1995)[9] Rocchio, J.J.: Relevance feedback in information
retrieval, In The SMART Retrieval
System-Experiments in Automatic Document
Processing, Prentice Hall, Inc., pp.313-323 (1971)[10] Salton, G., Fox, E.A., and Voorhees, E.: Advanced
feedback methods in information retrieval, Journal of
the American Society for Information Science, Vol.36,
No.3, pp.200-210 (1985)[11] Salton, G. and Buckley, C.: Improving Retrieval
Performance by Relevance Feedback, Journal of theAmerican Society for Information Science, Vol.41,
No.4, pp.288-297 (1990)[12] Singhal, A., et al.: Pivoted document lengthnormalization, In Proceedings of the Nineteenth
Annual International ACM SIGIR Conference on
Research and Development in Information Retrieval,
pp.21-29 (1996)[13] Voohees, E.M., Harman, D.: Overview of the Seventh
Text REtrival Conference(TREC-7), In Proceedings of
the Seventh Text REtrieval Conference, NIST Special
Publication (1999)

BIOGRAPHICAL NOTES
Masayuki Okabe is a Ph.D. student in the Department ofComputational Intelligence and Systems Science at Tokyo
Institute of Technology. His research interests include machine learning, intelligent information retrieval.
Seiji Yamada is an Associate Professor in the Departmentof Computational Intelligence and Systems Science at Tokyo
Institute of Technology. His research interests include artiﬁcial intelligence, planning, machine learning for a robotics,
intelligent information retrieval in the WWW, human computer interaction.