R D at NTCIR 2 Ad-hoc Task:
Relevance-based Superimposition Model for IR
Teruhito KANAZAWA
University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japantkana@nii.ac.jp
Atsuhiro TAKASU, Jun ADACHINational Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
takasu, adachi @nii.ac.jp

Abstract
This paper describes our evaluation experiments
for NTCIR 2 ad-hoc task. We developed a retrieval system using the Relevance-based Superimposition (RS)model, in which document vectors are modified basedon the relevance of the documents. The major focus of
this year is on combination of the RS model and query
expansion (QE). We submitted fully automatic ad-hoc
results brought by different parameter settings.
Keywords: NTCIR, information retrieval, vector
space model, document vector modification, RS model,
query expansion

query expansion. This combination is expected to improve the effectiveness complementarily.

2. System Overview
is designed as a full-text retrieval system
based on the vector space model [1].
Formal definition of the vector space model is thefollowing. The query
consists of searching terms.
The similarity between the query and the document d is defined as follows:d(1)

1. Introduction(2)
We have proposed a method named the Relevancebased Superimposition model, in which document
vectors are modified based on the relevance of the documents. In this model, relevant documents are organized into document sets when the index table is created and supplementary index terms are chosen foreach document set.
For evaluation, we developed a retrieval system using the RS model, named(RetRieval system for
Digital Documents), which is a full-text retrieval system designed based on the vector space model. Figure
1 depicts the process flow of.
The RS model shows better retrieval effectivenessby solving the semantic ambiguity caused by varianceof expression among the documents. This ambiguity isa serious problem especially in retrieval from scientificpapers written by various authors. On the other hand,query expansion has been proposed as one method ofsolving the semantic ambiguity of queries. At NTCIR
2, we focused on combination of the RS model and: factor based on the term frequency in a document.
: factor based on the document frequency containing the term.
: factor based on the term cooccurrence statistics.

2.1. Parsing
We employ ChaSen 1.51[2] as the Japanese morpheme analyzing program, for extracting and stemming terms. Hereafter, terms extracted from documents are called ‘index terms,’ and those extracted
from queries are called ‘searching terms.’ Index terms
are extracted from the titles, abstracts and free keywords given by the authors of papers. Their SGML
tags in the NTCIR corpus are,andrespectively. We use only the Japanese portions ofDatabase

Query

Extracting searching terms

Extracting index terms

Weighting searching terms

Weighting index terms

Generating query vector

Extracting relevanceof documents

Generating original document vectors
Generating
representative vectors

Modifying document vectors

Process based on the RS model

Scoring
Ranking
OutputFigure 1. The process flow of R2 D2
records and extracted about 530,000 kind of terms
from the corpus. On the other hand, we eliminatedmeaningless phrases such as ‘I want to retrieve the papers describing ...’ from queries automatically using
heuristic rules.

Furthermore, we considered normalization using
document length. Equation 5 can be generalized to:

tf

(6)

2.2. Factor based on term frequency
We have evaluated three kinds of functions that are
based on the concepts of term frequency:
tf

(3)
tf

and (4)tf(5)Equation (5) was identified as the most effective
method in the preliminary experiment [3, 4].
Figure 2 (a) and (b) illustrates the difference between Equations 3 and 5. The factor given by Equation(5) is bounded within 1.0, while the factor given by theconventional Equation (3) grows proportionally as tf
grows. We think that term frequency is not so important when the documents are rather short, as the NTCIR documents are. It can be generally said that documents that contain all search terms are more desirable
than those documents that contain only a few of thespecified terms. Thus, the conventional Equation (3)is not suitable for our purposes from this viewpoint.

We optimized the parameters and the function withTREC 3 and NTCIR 1 corpus, and used
,
,
tf .

120

1

100

0.8

80
0.6
60
0.4
40
0.2

20

0
1 2 3 4 5 6 7 8 910

0
1 2 3 4 5 6 7 8 910

Eq.(5) Proposed

Figure 2. Term-weighting functions

2.3. Factor based on document frequency
We evaluated two factors:
df

and

df

(7)
(8)

where stands for the number of documents and df
for document frequency of term t . Equation 8 was
identified as more effective in the preliminary experiment.

2.4. Analyzing a query and weighting searching terms
extracts search terms from the query using
the same method as that applied to documents andweights terms by automatic relevance feedback. It isdifficult to estimate the importance of search terms because a query tends not to have much information for
statistical estimation. Rocchio’s feedback process [5]is one effective method to weight search terms; however, there seems no assured method to tune parameters adapted to the database. We evaluated some otherweighting methods in our preliminary experiments andused one described below in.
The weightof the query term t is calculated based on the cooccurrence with other query
terms [6]:

df
where

(9)
d

of kinds of query term
appearing in document ddocument set in whichterm t appears

idea is different from traditional cluster-based methods, in which the document clusters are usually exclusive. These methods assume that documents can beclassified into orthogonal clusters by the frequencies
of terms, but a more natural assumption allows a document to belong to several topics. This difference inassumptions will reflect on the recall of retrieval.
For example, when there are two clusters, such as‘image processing’ and ‘neural networks’, in an exclusive clustering model, a document on ‘image processing using neural networks’ will belong to one orother of them. If this document is assigned to the cluster of ‘image processing’, we cannot retrieve it with aquery about ‘neural networks’. On the other hand, in
the RS model, this document can belong to both clusters; hence, this problem does not occur.
Let us define the RS model more formally. In the
RS model, each document is represented by a feature
vector. Term frequencies are often used as the feature.
Suppose that a document database contains a set of
documents d dd and their feature vectors
are.
In the RS model, documents in the database form
clusters. Note that one document may
be contained in more than one cluster in the RS model,
while clusters in other methods are often mutually exclusive. Figure 3 schematically depicts an example
of document clusters in the RS model. At this point,
we must decide what kind of relevance we will use to
make clusters. The principle of the RS model is independent of the source of relevance information, andour choice will depend on the kind of database and thetypes of elements in it. For instance, the following elements can be candidates for the source of relevance
information:
keywords given by the authors,
references, hyperlinks,

Let us describe this function briefly. It can be said
that a document that contains many query terms islikely to be relevant to the query. The Equation (9)makes the weight greater for those query terms thatappear in documents containing many of the specified
query terms, in other words, the weight of an important term becomes greater.

3. RS model
3.1. Model Overview
The proposed RS model is designed according to
the document vector modification approach. Thismodel partitions the documents so that the relevant
documents fall into the same cluster. However, thebibliographic information, such as author name,publication date, and journal title.
In our experiments with the NII Test Collection, described in this figure and the following section, weconstructed the clusters based on the free keywords
given by the authors of documents. Suppose that there
are two keywords A and B. Then there are two clusters
corresponding to A and B, respectively. Cluster
consists of documents that contain the keyword A andthe same relationship holds for
and B. In the figure, the document d is in cluster, since it contains
only the keyword A, while the document d is both inand inbecause it contains both keywords A
and B.

1

Keyword A

4

3

2

A

A, B

smaller when the variance of the arguments is large. If
the function is too strongly conjunctive, there will be
fewer supplemental terms. We must, therefore, use experiments to select and evaluate the appropriate function.

5

B

B

3.3. Document Vector Modification
RVG
1

document set CA
by keyword A

2document set CBby keyword B

Figure 3. Representative vector generation

3.2. Representative Vector Generation
Using the clusters, the document feature vector ismodified in two steps: representative vector (RV) generation and feature vector modification by RVs. The
first step is to construct the RV of each cluster. The RV
corresponds to the feature vector of document clusters
and has the same dimension as document feature vectors. RV of cluster is constructed from the feature vectors of documents in . Currently, we haveproposed five kinds of representative-vector-generator(RVG) functions, based on the -family distributions[7], which derive the th component of RV as follows:[ ] maximumd,

The second step is modification of the document
vector using the RVs of the clusters to which the document belongs. Figure 4 depicts this step schematically.
In this case, the document vector
is modified using, because document d belongs to cluster, whilethe document vector
is modified using bothand.
We assume that important index terms for a document d are any terms that occur frequently in any
cluster to which d belongs, as well as terms occurring
frequently in d itself. This characteristic is considered
to be ‘conjunctive’.
Currently, we propose five kinds of documentfeature-vector-modifier (DVM) function. In order todefine the DVM, we first define the vector of a cluster
set
that consists of clusters to which document dbelongs. Let
denote the set of RVs that belong to
the clusters belonging to .
Then the th component of the vector of
can bedefined in the following five ways:[ ] maximum,[ ] Root-Mean-Square,[ ] mathematical mean,[ ] Square-Mean-Rootand[ ] minimum[ ] Root-Mean-Squared[ ] mathematical meand[ ] Square-Mean-Root
and

d

.

,
,
3

[ ] minimum

1

d

2

5

4

,

where
stands for the th component of the feature
vector of document d andfor the number of documents contained in the cluster .
The first three functions are more ‘disjunctive’ andthe value of the function tends to become larger whenthe variance of the arguments is large, so that the influence of noise appears stronger. On the other hand,
the last two functions, [ ] and [ ] are more ‘conjunctive’ and the value of the function tends to become

DVM

1

CA

2

CB

Figure 4. Document vector modification

Let
represent the feature
vector of a document d and let
represent the vector of the cluster set. The
modified document feature vector
is then defined
as
,
where
is the superimposing function. We haveevaluated some members of the -family of distributions forand ‘maximum’ is identified as the mosteffective method.

4. Query Expansion
We employ an automatic QE method via relevance
feedback. Expansion terms are chosen from the top
document retrieved using the original query. , thenumber of expansion terms is adjusted in our preliminary experiment with NTCIR 1 and TREC.
We found that most effective parameters areboth for NTCIR 1 and TREC 3 SJM corpus, and has much influence on the retrieval effectiveness. Then we examined the improvements with
NTCIR 2 obtained by QE when changed.

5. Results
There are 851,218 keywords and 90,761 of themappear in more than four documents. We do not use
smaller clusters containing less than five documents
since they tend to cause errors.
Table 2 shows the effectiveness of the RS model& QE. The average precision without RS nor QE is0.2841. QE improves results by 2%, and RS doesby 6%. The most effective QE parameters are, however, the difference between the average precisions using(the best for NTCIR 2)
and(the best for NTCIR 1 and TREC 3) isonly 0.3%.
The combination of RS and QE achieves 9% improvement that is more than the summation of theirindividual effectiveness.

6. Discussion
The factor
based on the term cooccurrence
statistics works well for most of queries, however, it
fails to find important terms in some cases. For example, when it analyzes topic 118 “Distance education
support systems using TV conferencing,” it weights‘distance’ and ‘TV’ twice as much as ‘education.’ Thisestimation does not correspond to the intension.
Query 101 “Development of hepatitis B vaccines bygenetic engineering techniques” is one of the inappropriate cases for RS. The parser does not distinguish ‘B’and ‘non-B’, hence documents about “hepatitis non-A
non-B” are recognized by the system as relevant to thequery. It makes the RS model modify the feature vectors of documents containing keyword “hepatitis nonA non-B” improperly, and documents about hepatitis
non-A non-B are retrieved. From this, we noticed theimportance to treat suffixes and postfixes more carefully. We need to investigate phrasal indexing.
Query 112 “I want papers about discharges inducedby high power CO2 lasers” is another inappropreatecase. The most relevant document cluster to the query,in other words, the cluster whose feature vector is thenearest to the query vector, is one of the documents
containing keyword “laser induced lighting.” 19 of
37 documents in this cluster are relevant to the query,hence this cluster has positive effect to improve theretrieval precision. On the other hand, the 3rd most
relevant cluster is of documents containing keyword“CO2 laser” that is broader concept than “laser induced lighting” and not reflect the content of somedocuments in the cluster. Only 6 of 62 documents
are relevant, and it may behave as a source of noise.
It is possible to screen out noisy clusters by comparing the concreteness of supplemental terms with keywords. For such a technique, a method to statisticallyextract a concept hierarchy is required, because no thesaurus can cover all keywords or all index terms.
Query 145 “Papers that discuss how the locationsof public libraries affect their use,” is a inappropreatecase for QE. Expansion terms are ‘come to the library’, ‘books’, ’ building’, and so on. All of them
are related to ‘library’ but not to ‘location.’ Then documents discussing about library generally, which are
not relevant to the query, are retrieved, and it degrades
the precisions of retrieval. This is the drawback of automatic QE. Interactive feedback can solve this problem. We think that the RS model makes interactive
relevance feedback easy by outputting keywords as interim results and requiring the user to select appropriate keywords.
The combination of the RS model and QE seems
to work well. Those two methods improve the retrieval effectiveness complementarily, in other words,
QE refines the query and that enhances the effectiveness of the RS model. In some cases, the combinationachieves larger gain on effectiveness than the summation of ones of the RS and QE (ex. for Q.139, the combination achieves 247% higher average precision than
one of the baseline, while the RS model does +73%
and QE does +33%). In some other cases, failure ofone method is covered by the other (ex. for Q.101, thecombination gives 8% higher precision, while the RS
doeslower).

7. Conclusion
In this paper, we showed the effectiveness of the
proposed RS model and of the combination with QE.
The RS model achieves 6% superiority over the base-Table 1. Improvements obtained by query expansion
baseline
QE

NTCIR 1.3059
.3270 (+7%)

TREC 3 SJM.2318.2578(+11%)

Table 2. Performance of the RS model and query expansion
Run

QE
no
yes
no
yes

RS
no
no
yes
yes

avg prec.2841.2886 (+2%).3020 (+6%).3103 (+9%)

R-prec
.3147
.3282
.3353
.3402

P@10 docs
.5510
.5551
.5571
.5653

P@100 docs
.1996
.2120
.2165
.2310

#q

avg+0.05
16
18
22
21

#q

avg 0.05
75
4
5

Table 3. Average precisions for some notable queries
baseline
QE
RS
RS+QE
Positive cases for RS
Q.115: I want papers about videostreaming techniques.
.1271.1216 ( 4%).1527 (+20%).1805 (+42%)
Q.139: Documents will report on the “ sick building syndrome,” which includes an allergic reaction to chemicals
such as formaldehyde.
.3105.4123 (+33%).5382 (+73%).7663(+247%)
Q.143: Papers that mention visually impaired persons’ use of library computer terminals or information retrieval
systems.4389.4868 (+11%).5167 (+18%).5256 (+20%)
Inappropriate case for RS
Q.101: Development of hepatitis B vaccines by genetic engineering techniques.4299.4645 (+8%).3801 ( 12%).4647 (+8%)
Positive cases for QE
Q.112: I want papers about discharges induced by high power CO lasers.
.3912.4119 (+5%).2870 ( 27%).4215(+8%)
Q.125: I would like to learn about the antimicrobial activity of electrolytic acid water.
.5391.5957 (+10%).5720 (+6%).6466 (+20%)
Inappropriate cases for QE
Q.128: Are there any documents about coagulase-negative Staphylococci that cause infectious diseases?
.6070.3771 ( 38%).5975 ( 2%).4069( 32%)
Q.145: Papers that discuss how the locations of public libraries affect their use.4373.2997 ( 32%)
.4166 ( 5%).2393 ( 45%)

line, and the combination of RS and QE achieves 9%
improvement. Those two methods improve the retrieval effectiveness complementarily.
For the future work, it is necessary to consider circumstances where databases are used for which keywords are not given. We plan to investigate automatic
keyword extraction.

Society for the Promotion of Science.

Acknowledgment[2] “Japanese Morphological Analyzer ‘ChaSen’(inJapanese) ,This research is supported by the ‘Research for the
Future’ Program JSPS-RFTF96P00602 of the Japan

References[1] G. Salton and M. McGill, Introduction to Modern
Information Retrieval, McGraw-Hill, 1983.

.

[3] T. Kanazawa, “An Information Retrieval Method
using a Relevance-based Superimposition Model,
Master’s thesis, Graduate School of Engineering,
University of Tokyo, 1999.
[4] T. Kanazawa, A. Takasu, and J. Adachi, “Effectof the Relevance-based Superimposition Model on
Information Retrieval,” IPSJ Database workshop
2000 (IPSJ SIG Notes), Vol. 2000, No.69, 2000DBS-122, pp. 57–64, Iwate, July 2000.
[5] C. Buckley, A. Singhal, and M. Mitra, “Using
Query Zoning and Correlation Within SMART:TREC 5,” Proc. TREC 5, Gaithersburg, MD,
1996.
[6] T. Kanazawa, “
at ntcir: using the relevancebased superimposition model,” NTCIR Workshop
1 Proc., pp. 83–88, Tokyo, Aug. 1999.
[7] Y. Hayashi, “On a New Data Model suitable
fpr Intellectual Accesses by Personal Preference,”
IPSJ database workshop ’98 (IPSJ SIG Notes),Vol. 98, No.58, 98-DBS-116(2), pp. 381–388,
July 1998.