We participated in the CLEF 2001 monolingual, bilingual, and multilingual tasks. Our interests in these tasks are to test the utility of applying Chinese word segmentation algorithms to German decompounding, to experiment with techniques for combining translations from diverse resources, and to experiment with different approaches to multilingual retrieval. This paper describes our retrieval experiments.
At CLEF 2001, we participated in the monolingual, bilingual, and multilingual tasks. Our interest in monolingual task is to test the idea of treating the German decompounding problem as that of Chinese word segmentation and applying Chinese word segmentation algorithms to split German compounds into their constituent words. Our interest in cross-language is to experiment with techniques for combining translations from diverse resources. We are also interested in different approaches to the multilingual retrieval task and various strategies for merging intermediate results to produce a final ranked list of documents for a multilingual retrieval run. In our experiments, we used English and Chinese topics. In translating the topics into the document languages which are English, French, German, Italian, and Spanish, we used two machine translators, one bilingual dictionary, two parallel text corpora, and one Internet search engine.
We submitted several official runs to the multilingual, bilingual, and monolingual tasks and performed more unofficial runs. To differentiate the unofficial runs from the official ones, the IDs of the official runs are all in uppercase, and IDs of the unofficial runs are all in lowercase. The unofficial runs are those evaluated locally with the official release of the relevance judgments for CLEF 2001.
We present an algorithm to break up German compounds into their constituent words. We treat the German decompounding problem in the same way as the Chinese word segmentation problem which is to segment a string of characters into words. We applied the Chinese segmentation algorithm as described in section 4.1 to decompose German compound words. First, we created a base German word lexicon consisting of all the words, including compounds, found in the German collection for the multilingual task. The uppercase letters were changed to lower case. Second, we identify all possible ways to break up a compound into its constituent words found in the base German lexicon. Third, we compute the probabilities for all possible ways to break up a compound into its constituent words, and choose the segmentation of the highest probability. For example, a compound c = = of splitting into w4w5 is estimated by p(c2) p(w4w5) p(w4) p(w5). If p(c1) is larger than p(c2), then = = = = = where w1 a1a2, w2 a3a4, w3 a5a6, w4 a1a2a3, and w5 a3a4a5 are German words. The probability c = = = = = a1a2a3a4a5a6 may be split into either c1 a1a2=a3a4=a5a6 w1w2w3, or c2 a1a2a3=a4a5a6 w4w5, c the compound is split into the three words w1, w2, and w3; otherwise it is split into the two words w4 and w5. = tf tf tf document collection. That is, p(wi) (wi)= Pkn=1 (wk), where (wi) is the number of times word wi c = = of splitting into w1w2w3 is computed as p(c1) p(w1w2w3) p(w1) p(w2) p(w3), and the probability n occurs in the collection, including the cases where wi is a consituent word in compounds; and is the number of As in Chinese word segmentation, the probability of a word is estimated by its relative frequency in the German unique words, including compounds, in the collection.
We submitted two official German monolingual runs labeled BK2GGA1 and BK2GGA2, and two official Spanish monolingual runs labeled BK2SSA1 and BK2SSA2. The first run used title, description, and narrative fields in the topics, while the second run used title and description only. The stopwords were removed from both documents and topics, compounds were split into their constituent words, then words were stemmed using the Muscat German stemmer. Both the compounds and their constituent words were kept in indexing. Both runs were carried out without query expansion. The results are in table 2. The monolingual runs for the other three languages were Run ID Language Average Precision Overall Recall bk2eea1 English 0.5553 95.33% (816/856) bk2ffa1 French 0.4743 98.84% (1198/1212)
BK2GGA1 German 0.4050 92.63% (1973/2130) bk2iia1 Italian 0.4370 95.83% (1194/1246)
BK2SSA1 Spanish 0.5302 95.06% (2561/2694) evaluated locally and the results are in table 1.
Run ID BK2GGA1 BK2GGA2 bk2gga3 bk2gga4 bk2gga5
Topic Fields T,D,N T,D T,D,N T,D,N T,D,N
+stemming, +decompounding +stemming, +decompounding +stemming, –decompounding –stemming, +decompounding –stemming, –decompounding
92.63% 88.31% 90.94% 89.81% 88.12%
0.4050 0.3683 0.4074 0.3594 0.3673
In this section we will describe the pre-processing of the Chinese topics and translation of the Chinese topics into English. and p(Wj) S = : : : n For example, let C1C2 Cn be a fragment of Chinese text consisting of Chinese characters. Suppose = : : : one of the segmentation for the Chinese text is Si W1W2 Wm, then the probability of this segmentation is
We first break up a Chinese sentence into text fragments consisting of only Chinese characters. Generally there are many ways to segment a fragment of Chinese text into words. We segment Chinese texts in two steps. First, we examine all the possible ways to segment a Chinese text into words found in a Chinese dictionary. Second, we compute the probabilities of all the segmentations and choose the segmentation with the highest probability. The probability of a segmentation is the product of the probabilities of the words making up the segmentation. computed as follows:
The segmentation and de-segmentation of the Chinese topics result in a list of Chinese words for each topic. We translate the Chinese topic words into English using three resources: 1) a Chinese/English bilingual dictionary, 2) two Chinese/English parallel corpora, 3) a Chinese Internet search engine. First, we look up each Chinese word in a Chinese-English bilingual wordlist prepared by the Linguistic Data Consortium and publicly available from http://morph.ldc.upenn.edu/Projects/Chinese/. The wordlist has about 128,000 Chinese words, each paired with a set of English words. If a Chinese word has only one, two or three English translations, we retain them all, otherwise we choose the three translations that occur most frequently in the Los Angeles Times collection which is part of the document collections for the CLEF 2001 multilingual task.
We created a Chinese-English bilingual lexicon from two Chinese/English parallel corpora, the Hong Kong
News corpus and the FBIS corpus. The Hong Kong News corpus consists of the daily Press Release of the Hong
Kong Government in both Chinese and English during the period of from April, 1998 through March, 2001. The
source Chinese documents and English documents are not paired. So for each Chinese document, we have to
identify the corresponding English document. We first aligned the Hong Kong News corpus at the document level
using the LDC bilingual wordlist. Then we aligned the documents at the sentence level. Unlike the Hong Kong
News corpus, the Chinese documents and their English translations are paired in the FBIS corpus. The documents
in the FBIS corpus are usually long, so we first aligned the parallel documents at the paragraph level, then at the
sentence level. We adapted the length-based alignment algorithm proposed by Gale and Church [
From the aligned pairs of Chinese/English sentences, we created a Chinese/English bilingual lexicon based
on co-occurrence of word pairs across the aligned sentences. We used the maximum likelihood ratio measure
proposed by Dunning [
For the Chinese words that are missing in the two bilingual lexicons, we submitted them one by one to
Yahoo!China, a Chinese Internet search engine at http://chinese.yahoo.com. Each entry in the search result pages
has one or two sentences that contain the Chinese word searched. For each Chinese word, we downloaded all the
search result pages if there are fewer than 20 result pages, or the first 20 pages if there are more than 20 result
pages. Each result page contains 20 entries. From the downloaded result pages for a Chinese word, we extracted
the English words in parentheses that follow immediately after the Chinese word. If there are English words found
in the first step, we keep all the English words as the translations of the Chinese word. And if the first step failed
to extract any English words, we extracted the English words appearing after the Chinese words. If there are more
than 5 different English translations extracted from the result pages, we keep the top three most frequent words
in the translations. Otherwise we keep all English translations. We refer interested readers to the paper in [
The English translations of the Chinese topics were indexed and searched against the LA Times collection. We submitted two Chinese-to-English bilingual runs, one using all three topics fields, and the other using title and description only. Both runs were carried out without pre-translation or post-translation query expansion. The documents and English translations were stemmed using the Muscat English stemmer. The performance of these two runs are summarized in table 3. The results of the cross-language runs from English to the other four languages Run ID BK2CEA1 BK2CEA2
Topic Fields T,D,N T,D
BK2CEA1 bk2cfa1 bk2cga1 bk2cia1 bk2csa1
Topic Fields T,D,N T,D,N T,D,N T,D,N T,D,N
We participated in the multilingual task using both English and Chinese topics. Our main approach was to translate the source topics into the document languages which are English, French, German, Italian, and Spanish, perform retrieval runs separately for each language, then merge the individual results for all five document languages into one ranked list of documents. We created a separate index for each of the five document collections by language. The stopwords were removed, words were stemmed using Muscat stemmers, and all uppercase letters were changed to lower case. The topics were processed in the same way.
For the multilingual retrieval experiments using English topics, we translated the English topics directly into French, German, Italian, and Spanish using both Systran translator and L&H Power translator. The topic translations of the same language from both translators were combined by topic, and then searched against the document collection of the same language. So for each multilingual retrieval run, we had five ranked list of documents, one for each document language. The five ranked lists of documents were merged to produce the final ranked list of documents for each multilingual run.
Our merging strategy is to combine all five intermediate runs and rank the documents by adjusted weights. Before we merge the intermediate runs, we made two adjustments to the estimated probability of document relevance in the intermediate runs. First, we reduced the estimated probability of document relevance by 20% (i.e, multiplying the original probability by .8) for the English documents retrieved using the un-translated English source topics. Then we added a value of 1.0 to the estimated probability of relevance for the top-ranked 50 documents in all monolingual runs. After these two adjustments to the estimated probability, we combined all five intermediate runs, sorted the combined results by adjusted probability of relevance, then took the top-ranked 1000 documents for each topic to create the final ranked list of documents. The aim of making the first adjustment is to make the estimated probability of relevance for all document languages comparable. Since translating topics from the source language to a target language probably introduces information loss to some degree, the estimated probability of relevance for the same topic may be slightly underestimated for the target language. In order to make the estimated probabilities for the documents retrieved using the original topics and using the translated topics comparable, the estimated probabilities for the documents retrieved using the original topics should be slightly lowered. The intention of making the second adjustment is to make sure that the top-ranked 50 documents in each of the intermediate results will be among the top-ranked 250 documents in the final ranked list.
For the multilingual retrieval experiments using Chinese topics, we translated the Chinese topics word by word into English, French, German, Italian, and Spanish in two stages. First, we translated the Chinese topics into English using three resources: 1) a bilingual dictionary, 2) two parallel corpora, and 3) one Chinese search engine. The procedure of translating Chinese topics into English was described in section 4. The English translations from the source Chinese topics consist of not sentences but words. Second, we translated the English words into French, German, Italian, and Spanish using both Systran translator and L&H translator for lack of resources to directly translate the Chinese topics into these languages. The rest is the same as for multilingual experiments using English topics.
We submitted four official multilingual runs, two using English topics and two using Chinese topics. The official runs are summarized in table 6. The multilingual run labeled BK2MUEAA1 was produced by combining the monolingual run bk2eea1 (.5553), and four cross-language runs bk2efa1 (.4776), bk2ega1 (.3789), bk2eia1 (.3934), bk2esa1 (.4703). The multilingual run labeled BK2MUCAA1 was produced by combining five crosslanguage runs, BK2CEA1, bk2cfa1, bk2cga1, bk2cia1, and bk2csa1. The performance of these five cross-language runs using Chinese topics is presented in table 5.
The problem of merging multiple runs into one is closely related to the problem of calibrating the estimated probability of document relevance and the problem of estimating the number of relevant documents with respect Run ID BK2MUEAA1 BK2MUEAA2 BK2MUCAA1 BK2MUCAA2
T,D
0.3424 0.3029 0.2217 0.1980 to a given query in a collection. If the estimated probability of document relevance is well calibrated, that is, the estimated probability is close to the true probability of relevance, then it would be trivial to combine multiple runs into one, since all one needs to do will be to combine the multiple runs and re-rank the documents in the estimated probability of relevance. If the number of relevant documents with respect to a given query could be well estimated, then one could take the number of documents from each individual run that is proportional to the number of estimated relevant documents in each collection. Unfortunately neither one of the problems is easy to solve.
Since merging multiple runs is not an easy task, an alternative approach to this problem is to work on it indirectly, that is, transform it into another problem that may be easier to solve. There are two alternative approaches to the problem of multilingual information retrieval. The first method works by translating the source topics into all document languages, combining the source topics and their translations in document languages, and then searching the combined, multilingual topics against a single index of documents in all languages. The second method works by translating all documents into the query language, then performing monolingual retrieval against the translated documents which are all in the same language as that of the query.
We applied the first alternative method to the multilingual IR task. We translated the source English topics directly into French, German, Italian, and Spanish using both Systran translator and L&H Power translator. Then we combined the English topics with the other four translations of both translators into one set of topics. The within-query term frequency is reduced by half. We used the multilingual topics for retrieval against a single index of all documents. The performance of this run labeled bk2eaa4 is shown in table 7. For lack of resources, we Run ID bk2eaa3 bk2eaa4
Topic Language English English
were not able to apply the second alternative method. Instead, we experimented with the method of translating the French, Italian, German, and Spanish documents retrieved in the intermediate runs back into English, and then carring out a monolingual retrieval run. We did not use Systran translator or L&H Power translator to translate the retrieved documents into English. We compiled a wordlist from the documents retrieved, then submitted the wordlist into Systran. The translation results of the wordlist were used to translate word by word the retrieved documents into English. The overall precision is .3648 for this run labeled bk2eaa5. 6
We have tested the idea of treating the German decompounding problem in the same way as the Chinese word segmentation problem. The decompounding of German compound words did not improve precision. We believe the problem is that the decompounding algorithm failed to consistently decompose German compounds into their consitituent words. We observed that multi-word compounds are sometimes split into single words and shorter compounds. We also presented a method for combining translations from three different translation resources which seems to work well. We experimented with three approaches to multilingual retrieval. The method of translating the documents retrieved in the intermediate runs back into the language of the source topics, and then carring out monolingual retrieval achieved better precision than the other two methods.
This research was supported by DARPA (Department of Defense Advanced Research Projects Agency) under research contract N66001-97-8541; AO# F477: Search Support for Unfamiliar Metadata Vocabularies within the DARPA Information Technology Office.