Proceedings of the Third NTCIR Workshop

Description of NTU Approach to
NTCIR3 Multilingual Information Retrieval

Wen-Cheng Lin and Hsin-Hsi Chen
Department of Computer Science and Information Engineering
National Taiwan University
Taipei, TAIWAN
E-mail: denislin@nlg.csie.ntu.edu.tw; hh_chen@csie.ntu.edu.tw

Abstract
This paper deals with Chinese, English and Japanesemultilingual information retrieval. Several merging
strategies, including raw-score merging, round-robinmerging, normalized-score merging, and normalizedby-top-k merging, were investigated. Experimental
results show that centralized approach is better thandistributed approach.
In distributed approach,normalized-by-top-k
withconsiderationoftranslation penalty outperforms the other merging
strategies.
Keywords:
Merging
Strategy,
Multilingual
Information Retrieval, Query Translation

1. Introduction
Multilingual Information Retrieval [7] uses aquery in one language to retrieve documents indifferent languages.
In addition to languagetranslation issue, how to conduct a ranked list that
contains documents in different languages fromseveral text collections is also critical. There are two
possible architectures in MLIR – say, centralized anddistributed. In a centralized architecture, a hugecollection that contains documents in different
languages is used. In a distributed architecture,
documents in different languages are indexed andretrieved separately, and all the results are merged
into a multilingual ranked list. Several merging
strategies have been proposed. Raw-score merging
selects documents based on their original similarity
scores. Normalized-score merging normalizes thesimilarity score of each document and sorts all the
documents by their normalized scores. For each
topic, the similarity score of each document isdivided by the maximum score in this topic. Roundrobin merging interleaves the results in theintermediate runs.
In this paper, we adopted
distributed architecture and proposed merging
strategies to merge the result lists.

© 2003 National Institute of Informatics

The rest of this paper is organized as follows.
Section 2 describes the indexing method. Section 3
shows the query translation process. Section 4
describes our merging strategies. Section 5 showsthe experiment results. Section 6 concludes theremark.

2. Indexing
The document set used in NTCIR3 MLIR task
consists of Chinese, English and Japanese documents.
The numbers of documents in Chinese, English, andJapanese document sets are 381,681, 22,927 and236,664, respectively. The participants can use twoor all of these three document collections as thetarget language sets. We used all of these threedocument collections to conduct XÆ CJE
experiments.
The IR model we used is the basic vector spacemodel. Documents and queries are represented asterm vectors, and cosine vector similarity formula isused to measure the similarity of a query and adocument. Appropriate terms are extracted fromeach document in indexing stage. In the experiments,
the <HEADLINE> and <TEXT> sections were used
for indexing. For English, all words were retained,
and all letters were transformed to lower case. The
Japanese documents were first segmented by ChaSen[6]. All words in the above two sections were used
as index terms. For Chinese, we used Chinesecharacter bigrams to index Chinese documents. The
term weighting function for all document sets is
tf*idf.

3. Query Translation
In the experiment, the Japanese queries were usedas source queries and translated into target languages,i.e., English and Chinese. We used CO model [1],which is a hybrid dictionary- and corpus-based

The Third NTCIR Workshop, Sep.2001 - Oct. 2002

method, to translate queries. Since we did not have aJapanese-Chinese dictionary, we used English as anintermediate language in the initial study. The
Japanese queries were translated into English, andthen the translated English queries were furthertranslated into Chinese. The Japanese queries weretranslated into English in the way as follows:(a) The Japanese query was segmented by ChaSen.
(b) For each Japanese query term, we found its
English translation equivalents by looking up aJapanese-English dictionary.
(c) By using co-occurrence information trained fromTREC6 text collection [4], we selected the bestEnglish translation equivalent for each source
query term. We adopted mutual information (MI)[2] to measure the co-occurrence strength
between words. For a query term, we compared
the MI values of all the translation equivalentpairs (x, y), where x is the translation equivalentof this term, and y is the translation equivalent ofanother query term within a sentence. The wordpair (xi, yj) with the highest MI value is extracted,
and the translation equivalent xi is regarded as
the best translation equivalent of this query term.
Selection is carried out based on the order of thequery terms.
Translated English queries were translated into
Chinese using the same method except that English
queries did not need to be segmented. The MI valuesof Chinese words were trained from Academia Sinica
Balanced Corpus (ASBC) [5].

4. Merging Strategies
There are two possible architectures in MLIR, i.e.,
centralized and distributed.
In a centralizedarchitecture, document collections in different
languages are viewed as a single document collection
and are indexed in one huge index file. The
advantage of centralized architecture is that it avoids
the merging problem. It needs only one retrievingphase to produce a result list that contains relevant
documents in different languages. One of problemsof a centralized architecture is that index terms may
be over weighted. In other words, the total numberof documents increases, but the number ofoccurrences of a term does not. In tf*idf scheme, theidf of a term is increased and it is over-weighted.
This phenomenon is clear in small text collection.
For example, the N in idf formula is 22,927 when
English document is used. However, this value isincreased to 641,272, i.e., about 27.97 times larger, if
the three document collections are merged together.
Comparatively, the weights of Chinese index terms
are increased only 1.68 times due to the size of N.
The increments of weights are unbalance fordocument collections in different size. Thus, IR

system may prefer documents in small document
collection.
The second architecture is a distributed MLIR.
Documents in different languages are indexed andretrieved separately.
The ranked lists of all
monolingual and cross-lingual runs are merged into
one multilingual ranked list. How to merge result
lists is a problem. Recent works have proposed
various approaches to deal with the merging problem.
A simple merging method is raw-score merging,which sorts all results by their original similarity
scores and then selects the top ranked documents.
Raw-score merging is based on the assumption thatthe similarity scores across collections arecomparable.
However, the collection-dependent
statistics in document or query weights invalidates
this assumption [3, 8]. Another approach, roundrobin merging, interleaves the results based on therank. This approach assumes that each collection has
approximately the same number of relevant
documents and the distribution of relevant documents
is similar across the result lists. Actually, different
collections do not contain equal numbers of relevant
documents. Thus, the performance of round-robinmerging may be poor. The third approach isnormalized-score merging. For each topic, thesimilarity score of each document is divided by the
maximum score in this topic. After adjusting scores,
all results are put into a pool and sorted by thenormalized score. This approach maps the similarity
scores of different result lists into the same range,from 0 to 1, and makes the scores more comparable.
But it has a problem. If the maximum score is muchhigher than the second one in the same result list, thenormalized-score of the document at rank 2 would bemade lower even if its original score is high. Thus,
the final rank of this document would be lower thanthat of the top ranked documents with very low but
similar original scores in another result list.
Similarity score reflects the degree of similarity
between a document and a query. A document withhigh similarity score seems to be more relevant to thedesired query. But, if the query is not formulated
well, e.g., inappropriate translation of a query, adocument with high score still does not meet theuser’s information need. When merging results, such
documents that have incorrect high scores should not
be included in the final result list. Thus, we have toconsider the effectiveness of each individual run in
the merging stage. The basic idea of our merging
strategy is that adjusting the similarity scores of
documents in each result list to make them morecomparable and to reflect their confidence. The
similarity scores are adjusted by the following
formula.

1
Sˆij = S ij × × Wi
Sk

(1)

Proceedings of the Third NTCIR Workshop

where Sij is the original similarity score of the
document at rank j in the ranked list of
topic i,Ŝij is the adjusted similarity score of the
document at rank j in the ranked list of
topic i,S k is the average similarity score of top k
documents, andWi is the weight of query i in a cross-lingualrun.
We divide the weight adjusting process into two
steps. First, we use a modified score normalization
method to normalize the similarity scores. The
original score of each document is divided by theaverage score of top k documents instead of the
maximum score. We call this normalized-by-top-k.
Second, the normalized score multiplies a weight thatreflects the retrieval effectiveness of the desired topic
in each text collection. Because of not knowing theretrieval performance in advance, we have to guess
the performance of each run. For each language pair,the queries are translated into target language andthen system retrieves the target language documents.
A good translation should have better performance.
We can predict the retrieval performance based on
the translation performance. There are two factors
affecting the translation performance, i.e., the degreeof translation ambiguity and the number of unknown
words. For each query, we compute the average
number of translation equivalents of query terms andthe number of unknown words in each language pair,and use them to compute the weights of each crosslingual run. The weight can be determined by thefollowing three formulas:2 U 
 51 − Ti   
Wi = c1 + c2 ×   + c3 × 1 − i (2)ni  
 50   
 U 
 1    + c3 × 1 − i  
Wi = c1 + c 2 × (3)ni  
 T i  
 U 
1  (4)
Wi = c1 + c 2 ×    + c3 × 1 − i 
n
T


i 

 i  
where Wi is the weight of query i in a cross-lingualrun,
Ti is the average number of translationequivalents of query terms in query i,
Ui is the number of unknown words in query i,
ni is the number of query terms in query i, andc1, c2 and c3 are tunable parameters, andc1+c2+c3=1.
In the experiment, the Japanese queries weretranslated into English, and then the translated
English queries were further translated into Chinese.
Some Japanese query terms have no English
translation, and therefore they cannot be translated
into English and also Chinese. The unknown words
in Japanese-English translation are also unknown inEnglish-Chinese translation. Thus, the number of

unknown words in Japanese-English-Chinesetranslation is the sum of those in Japanese-English
translation and English-Chinese translation.

5. Results
We submitted three JÆCJE multilingual runs andone EÆE monolingual run. All runs use description
field only. The English monolingual run, NTU-E-ED-01, uses official English topics to retrieve English
documents. The three multilingual runs use Japanese
topics as source queries. The Japanese topics weretranslated into English and Chinese by CO Modeldescribed in Section 3. The source Japanese topics
and the translated English and Chinese topics wereused to retrieve Japanese, English and Chinese
documents, respectively. Then, we merged thesethree result lists.
We used different merging
strategies for the three multilingual runs.
1. NTU-J-CJE-D-01
First, we used formula (1) to adjust the similarity
score of each document. We used the averagesimilarity score of top 10 documents fornormalization. The weight Wi was determinedby formula (2). The values of c1, c2 and c3 were
set to 0.1, 0.4 and 0.5, respectively. Then all
results were put in a pool and sorted by the
adjusted score. The top 1000 documents wereselected as the final results.
2. NTU-J-CJE-D-02
The merging strategy is the same as run NTU-JCJE-D-01 except that the weight Wi wasdetermined by formula (3).
3. NTU-J-CJE-D-03
The similarity scores were adjusted bymultiplying a constant weight. The similarity
scores in Japanese-English run multiplied 1.5;
the similarity scores in Japanese-Chinese run
multiplied 0.5; the similarity scores inmonolingual Japanese run were not changed.
These values were trained from the experiments
using dry-run data.
The results of our official runs are shown in Table
1. Table 2 shows the unofficial evaluation ofintermediate monolingual (i.e., Japanese to Japanese)and cross-lingual runs (i.e., Japanese to English andJapanese to English). The relevant assessment ofeach language is extracted from multilingual
assessment file. The performance of run NTU-JCJE-D-02 is slightly better than that of run NTU-JCJE-01. The weight Wi of run NTU-J-CJE-D-02 is
smaller than that of run NTU-J-CJE-D-01 for mostqueries. But it seems not small enough for JapaneseChinese cross-lingual run.
Since the Chinesetranslations of Japanese queries are not translated
well, the performance of Japanese-Chinese crosslingual run is worse. When merging results, theThe Third NTCIR Workshop, Sep.2001 - Oct. 2002

Table 1. The results of official runs
Run

# Topic

NTU-E-E-D-01

32

NTU-J-CJE-D-01

50

NTU-J-CJE-D-02

50

NTU-J-CJE-D-03

50

Scoring Mode
Rigid
Relax
Rigid
Relax
Rigid
Relax
Rigid
Relax

Average Precision
0.20720.25190.08840.08390.09070.0865
0.09340.0893

Recall391 / 444
641 / 741
1211 / 4053
1769 / 6648
1172 / 4053
1719 / 6648
1194 / 4053
1766 / 6648

Table 2. The results of intermediate runsRun
ntu-fr-j-j-d# Topic
45

Scoring Mode
Rigid

Average Precision
0.1506

Recall1064/ 1659

ntu-fr-j-e-d

40

Rigid

0.1269225/456

ntu-fr-j-c-d

48

Rigid

0.0146517/1938

Japanese-Chinese cross-lingual run should havelower weight. The performances of the official
multilingual runs do not differ too much. The best
run is NTU-J-CJE-D-03 whose average precision is0.0934.
The weights trained from dry-run
experiments still perform well in the formal-run.
In order to compare the effectiveness of different
merging strategies, we also conducted several
unofficial runs shown as follows.
1. ntu-fr-j-cje-d-01
The merging strategy is the same as run NTU-JCJE-D-01, but the values of parameters c1, c2
and c3 were set to 0, 0.6 and 0.4, respectively.
2. ntu-fr-j-cje-d-02
The merging strategy is the same as run NTU-JCJE-D-02, but the values of parameters c1, c2
and c3 were set to 0, 0.6 and 0.4, respectively.
3. ntu-fr-j-cje-d-04
The merging strategy is the same as run ntu-fr-jcje-d-01 except that the weight Wi wasdetermined by formula (4).
4. ntu-fr-j-cje-d-raw-score
We used raw-score merging to merge result lists.
5. ntu-fr-j-cje-d-normalized-score
The result lists were merged by normalizedscore merging strategy.
The maximum
similarity score was used for normalization.
6. ntu-fr-j-cje-d-normalized-top10
In this run, we used the modified normalizedscore merging method. We did not consider the
performance drop caused by query translation.
That is, the weight Wi in formula (1) was 1 forevery sub run.
7. ntu-fr-j-cje-d-round-robin
We used round-robin merging to merge result
lists.
8. ntu-fr-j-cje-d-centralized

This run adopted centralized architecture. All
document collections were indexed in one index
file. The topics contained original Japanesequery terms, translated English query terms andtranslated Chinese query terms.
The results of unofficial runs are shown in Table 3.
We used the rigid relevant set to evaluate theunofficial runs. In the official evaluation, theJapanese documents without text were removed fromthe ranked list. We did not remove those Japanese
documents when evaluating our unofficial runs inTable 1. Therefore, the results of unofficial runs
cannot be compared to the official runs. We reevaluated the official runs without removing theJapanese documents without text. The new results ofruns NTU-J-CJE-D-01, NTU-J-CJE-D-02 and NTUJ-CJE-D-03 are shown in the last three rows in Table
3.
Table 3 shows that the performances of ntu-fr-jcje-d-01, ntu-fr-j-cje-d-02, and ntu-fr-j-cje-d-04 aresimilar to those of official runs even the values ofparameters c1, c2 and c3 are changed. The
performance of raw-score merging is good. This isprobably because we use the same IR model and term
weighting scheme for all text collections.
Comparatively, the performances of normalizedscore, round-robin and normalized-by-top-k merging
are poor, especially round-robin merging strategy.
Normalizd-by-top-k is better than normalized–scoremerging. When considering the translation penalty,
the performance of normalized-by-top-k is increased
and is better than the other merging strategies. It
shows that translation penalty is helpful. The best
run is ntu-fr-j-cje-d-centralized, which indexes all
documents in different languages together. In thisrun, most of the top ranked documents are in
Japanese or in English in most topics. Table 2 showsthat the performances of Japanese monolingualProceedings of the Third NTCIR Workshop

Table 3. The results of unofficial runsRun
ntu-fr-j-cje-d-01
ntu-fr-j-cje-d-02
ntu-fr-j-cje-d-04
ntu-fr-j-cje-d-raw-score

Average Precision

Recall

0.08330.08720.08681194 / 4053
1152 / 4053
1124 / 4053

0.08671310 / 4053

ntu-fr-j-cje-d-normalized-score
ntu-fr-j-cje-d-normalized-top10
ntu-fr-j-cje-d-round-robin
ntu-fr-j-cje-d-centralized

0.04920.05140.04471245 / 4053
1257 / 4053
1233 / 4053

0.09731149 / 4053

NTU-J-CJE-D-01

0.08421211 / 4053

NTU-J-CJE-D-02

0.08631172 / 4053

NTU-J-CJE-D-03

0.08911194 / 4053

Table 4. The results of unofficial runs using new Japanese-Chinese run
Average Precision

Recallntu-fr-j-c-d-2
ntu-fr-j-cje-d-01-2
ntu-fr-j-cje-d-02-2
ntu-fr-j-cje-d-04-2
ntu-fr-j-cje-d-raw-score-2

Run

0.02890.08410.08690.08630.0850340/1938
1242 / 4053
1233 / 4053
1229 / 4053
1315 / 4053

ntu-fr-j-cje-d-normalized-score-2
ntu-fr-j-cje-d-normalized-top10-2
ntu-fr-j-cje-d-round-robin-2
ntu-fr-j-cje-d-centralized-2

0.06850.06350.0516
0.09901273 / 4053
1277 / 4053
1225/ 4053
1177 / 4053

Table 5. Normalized-by-top-k with translation penalty (C1=0, C2=0.4, C3=0.6)
Run
ntu-fr-j-cje-d-01-3
ntu-fr-j-cje-d-02-3
ntu-fr-j-cje-d-04-3

retrieval and Japanese-English cross-lingual retrieval
are much better than that of Japanese-Chinese crosslingual retrieval. Therefore, the final result list
should not contain too many Chinese documents.
The over-weighting phenomenon in centralizedarchitecture increases the scores of Japanese andEnglish documents, so that more Japanese andEnglish documents are included in the result list of
run ntu-fr-j-cje-d-centralized.
This makes theperformance better.
In the initial experiments, we use English as apivot language to derive Chinese translationequivalents of Japanese query terms. Experimental
results show that the performance of JapaneseChinese cross-lingual run is very bad. In the further
tests, we translated Japanese queries into Chinese
directly by using BitEx online Japanese-Chinese
dictionary (http://www.bitex-cn.com/). Table 4 lists
the performances of new Japanese-Chinese crosslingual run and multilingual runs. The performance

Average Precision
0.08770.08830.0880Recall1205 / 4053
1203 / 4053
1196 / 4053

of the new Japanese-Chinese cross-lingual run isimproved only a little, i.e., from 0.0146 to 0.0289.
The major reason is that many query terms have notranslation. After analysis, there are 351 distinct
query terms in the description field of Japanesequeries. Among these, total 232 terms have notranslation. The remaining query terms have only
one translation. Furthermore, our system did not
return any documents in the new Japanese-Chinese
cross-lingual run for topics 16, 19 and 23. This isbecause all the translated Chinese terms of thesethree topics are unigrams and our system uses
bigrams as index terms. In such a case, no relevant
document is proposed.
The performance of centralized architecture is still
the best. When considering the translation penalty,
normalized-by-top-k (i.e., runs ntu-fr-j-cje-d-02-2
and ntu-fr-j-cje-d-04-2) is better than the othermerging strategies. Compared to the old translation
scheme, the performances of all merging strategies

The Third NTCIR Workshop, Sep.2001 - Oct. 2002

except raw-score and normalized-by-top-k withtranslation penalty are increased when the Japanesequeries are translated into Chinese by using BitEx
online dictionary. Since the Japanese query terms
have only one Chinese translation, emphasizing thedegree of translation ambiguity part in formulas 2-4
increases the merging weight of Japanese-Chinese
cross-lingual run. That decreases the performance of
normalized-by-top-k with translation penalty. Thus,
we adjusted the values of parameters c1, c2 and c3 to 0,
0.4 and 0.6, respectively. Table 5 shows that theperformances are improved.
In summary, thetranslation penalty is an important factor in merging,
and we should also consider the quality factor of
dictionaries (e.g., its coverage).

6. Concluding Remarks
This paper considers the two architectures in
MLIR. The centralized approach performed well in
all the experiments.
However, the centralizedarchitecture is not suitable in practice, especially forvery huge corpora. Centralized architecture needs
spending more time to index and to retrieve
documents in all languages. Distributed architecture
is more flexible. It is easy to add or delete corpora indifferent languages and employ different retrieval
systems in distributed architecture.
Merging problem is critical in distributed
architecture. This paper proposed several merging
strategies to integrate the result lists of collections indifferent languages.
The experimental results
showed that the performance of normalized-by-top-k
with translation penalty was better than raw-scoremerging, normalized-score merging and round-robinmerging.

References[1] Chen, H.H., Bian, G.W., and Lin, W.C., 1999.
Resolving translation ambiguity and target polysemy
in cross-language information retrieval.
In
Proceedings of 37th Annual Meeting of the Association
for Computational Linguistics, Maryland, June 1999.
Association for Computational Linguistics, 215-222.
[2] Church, K., Gale, W., Hanks, P., and Hindle, D., 1989.
Parsing, Word Associations and Typical PredicateArgument Relations. In Proceedings of International
Workshop on Parsing Technologies, Pittsburgh, PA,
August 1989. Carnegie Mellon University, Pittsburgh,PA, 389-398.
[3] Dumais, S.T., 1993. LSI meets TREC: A Status
Report. In proceedings of the First Text REtrieval
Conference (TREC-1), Gaithersburg, Maryland,
November, 1992. NIST Publication, 137-152.
[4] Harman, D.K., 1997.
TREC-6 Proceedings.
Gaithersburg, Maryland.
National Institute ofStandards and Technology.

[5] Huang, C.R. and Chen, K.J., 1995. Academic Sinica
Balanced Corpus. Technical Report 95-02/98-04.
Academic Sinica, Taipei, Taiwan.
[6] Matsumoto, Y., Kitauchi, A., Yamashita, T., andHirano, Y., 1999. Japanese Morphological Analysis
System ChaSen version 2.0 Manual. Technical
Report NAIST-IS-TR99009, Nara Institute of Scienceand Technology Technical Report.
[7] Oard, D.W. and Dorr, B.J., 1996. A Survey ofMultilingual Text Retrieval.
Technical Report
UMIACS-TR-96-19, University of Maryland, Institutefor Advanced Computer Studies.
[8] Voorhees, E.M., Gupta, N.K., and Johnson-Laird, B.,
1995.
The Collection Fusion Problem.
In
proceedings of the Third Text REtrieval Conference(TREC-3), Gaithersburg, Maryland, November, 1994.
NIST Publication, 95-104.