In this paper we proposed several merging strategies to merge the result lists of each intermediate runs in distributed MLIR. The prediction of retrieval effectiveness was used to adjust the similarity scores of documents in the result lists. We introduced three factors affecting the retrieval effectiveness, i.e., the degree of translation ambiguity, the number of unknown words and the number of relevant documents in a collection for a given query. The results show that the normalizedby-top-k merging with translation penalty and collection weight outperforms the other merging strategies except the raw-score merging.
Multilingual Information Retrieval abbreviated as MLIR facilitates the uses of queries in one language to access
documents in various languages. Most of the previous approaches
In real world, multilingual document collections are distributed from various resources, and managed by
information retrieval system of various architectures. How to integrate the results from heterogeneous resources
is one of the major issues in MLIR. Merging result lists of individual languages is a commonly adopted
approach. Document collections of each language are indexed and retrieved separately, and the result lists of
each document collection are merged into a multilingual result list. The goal of result lists merging is to include
as more relevant documents as possible in the final result list and to make relevant documents have higher ranks.
Several attempts were done on this problem
Lin and Chen
In this paper, we will explore several merging strategies. The basic idea of our merging strategies is adjusting the similarity scores of documents in each result list to make them more comparable and to reflect the confidence in retrieval effectiveness. We assume that the importance of each intermediate run depends on their retrieval performance. We introduced three factors affecting the retrieval effectiveness, i.e., the degree of translation ambiguity, the number of unknown words and the number of relevant documents in a collection for a given query. The rest of this paper is organized as follows. Section 2 describes our merging strategies. Section 3 shows the IR model and query translation technique. Section 4 discusses the experimental results. Section 5 concludes the remarks. 2
We aim to include as more relevant documents as possible in the final result list and to make relevant documents have higher ranks during merging. If a result list contains many relevant documents in the top ranks, i.e., it has good performance, the top ranked documents should be included in the final result list. On the other hand, if a result list has few or even no relevant documents, the final result list should not contain many documents from this list. Thus, the higher performance an individual run has, the more important it is. However, without the priori knowledge of a query in advance, it is challenging to predict the performance of an individual run for each document collection. The similarity score between a document and a query is one of a few clues that are common used. A document with higher similarity score seems to be more relevant to a specific query. Because document collections are various and the underlying IR systems may be different, the similarity scores of a query with different collections cannot be compared directly. The basic idea of our merging strategies is adjusting the similarity scores of documents in each result list to make them more comparable and to reflect the confidence in retrieval effectiveness. The characteristics of the underlying IR model, the effects of the query translation and the statistics of individual document collection will be addressed in the following subsections. 2.1
Similarity scores reported by different information retrieval systems may differ a lot from each other. In
vectorbased IR model, the similarity score defined by cosine formula ranges from 0 to 1, but the score may be much
larger than 1 when Okapi system
Similarity score reflects the degree of similarity between a document and a query. A document with higher similarity score seems to be more relevant to the desired query. However, if the query is not formulated well, e.g., inappropriate translation of a query, a document with high score may still not meet users’ information needs. When the result lists are merged, those documents that have high, but incorrect scores should not be included in the final result list. Thus, the effectiveness of each individual run has to be considered in the merging stage.
When query translation method is used to deal with the unification of language usages in queries and documents, queries are translated into target language and then the target language documents are retrieved. We can predict the multilingual retrieval performance based on the translation quality. Intuitively, using English to access English collection is expected to have better performance than using it to access other collections. Similarly, using a bilingual dictionary of more coverage is expected to be better than using dictionary of less coverage. Less ambiguous queries have also higher tendency to achieve better translation than more ambiguous queries. Normalization in Section 2.1 just reflects the same comparison basis, but does not consider the above issues. Two factors, i.e., the degree of translation ambiguity and the number of unknown words, are used to model the translation performance. For each query, we compute the average number of translation equivalents of query terms and the number of unknown words in each language pair, and use them to compute the weights of each cross-lingual run. The following formula is proposed to determine the weights.
Wi = c1 + c2 × 51 − Ti 2 + c3 × 1 − Unii .
50 where
Ti is the average number of translation equivalents 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, and
c1, c2 and c3 are tunable parameters, and c1+c2+c3=1.
(1)
How many relevant documents there are in a collection for a given query is also an important factor for
measuring retrieval effectiveness. If a document collection contains more relevant documents, it could have
more contribution to the final result list.
In our approach, a collection weight of a document collection with a query is defined as follows. A document collection is viewed as a huge document and represented as a collection vector. The ith element in a collection vector is the document frequency df of the ith index term in the collection. Similarly, the ith element in a query vector is the frequency of the ith index term in the query. Since document collections are in different languages, we do not use inverse collection frequency icf, which is analogous to idf. Cosine similarity formula shown as follows is used to compute the collection weight, which is included to the merging weight.
CWi =
Wi' = Wi + c4 × CWi m ∑ qtf ij × df j j=1 m ∑ qtf ij2 × j=1 m ∑ df j2 j=1 (2) (3) where
Wi is the merging weight described in Section 2.2, CWi is the collection weight of a target collection for query i, c4 is tunable parameter, qtfij is the term frequency of index term j in query i, dfj is the document frequency of index term j in a target collection, and m is the number of index terms. 2.4
Now three factors, i.e., the degree of translation ambiguity, the number of unknown words and the number of relevant documents for a given query in a document collection, are proposed to determine the retrieval effectiveness. We use linear regression to predict the retrieval effectiveness according to the three factors. The original similarity score of a document is normalized by normalized-by-top-k method, and the score of the predicted precision is added to the normalized score. Documents from all collections are sorted according to the adjusted similarity scores and the top ranked documents are reported. 3
In the experiments, Okapi IR system was adopted to index and retrieve documents. The weighting function was
BM25
English queries were used as the source language queries and translated into target languages, i.e., French, German and Spanish. A dictionary-based approach was adopted. For each English query term, we found its translation equivalents by looking up a dictionary. The first two translation equivalents with the highest occurrence frequency in the target language documents were considered as the target language query terms. If a query term does not have any translation equivalents, the original English query term was reserved in the translated query. The dictionaries we used are Ergane English-French, English-German and English-Spanish dictionaries. They are available at http://www.travlang.com/Ergane. 1 http://www.unine.ch/info/clef/
We submitted four runs in CLEF 2003 Small-multilingual task. All runs used title and description fields. The details of each run are described in the follows.
1. NTUm4Topn
The result lists were merged by normalized-by-top-k merging strategy. The average similarity score of the top 100 documents were used for normalization. 2. NTUm4TopnTp
In this run, translation penalty was considered. The similarity scores of each document were first normalized by the average similarity score of the top 100 documents and then multiplied a weight determined by formula (1). The values of c1, c2 and c3 were 0, 0.4 and 0.6, respectively. In query translation, an English query term which did not have any translation equivalents by dictionary lookup was also used to retrieve target language documents. If such an English term occurs in the target language documents, it can be viewed as a word similar to the other translated words when the merging weight is computed. Table 1 lists the number of English query terms that do not have translation, but occur in target language collection. 3. NTUm4TopnTpCw
In this run, the collection weight was also considered. We used formula (2) to adjust the similarity score of each document. The values of parameters were the same as run NTUm4TopTp. The value of c4 was 0.5. 4. NTUm4TopnLinear
We used linear regression to determine the weights of the three variables, including the average number of translation equivalents of query terms, the portion of unknown words in a query and the collection weight of the target collection, to predict the performances of each intermediate run. CLEF 2001 and 2002 test sets were used as training data to estimate the parameters. The original similarity score of a document was normalized by normalized-by-top-k method, and the score of the predicted precision was added to the normalized score.
The results of official runs are shown in Table 2. To compare the effectiveness of our approaches with the
past merging strategies, we also conducted several unofficial runs that used raw-score merging, normalized-score
merging and round-robin merging strategies. The average precision of optimal merging proposed by
English -> Spanish 5
Merging problem is critical in distributed multilingual information retrieval. In this paper, we proposed several merging strategies to integrate the result lists of collections in different languages. We assume that the importance of each intermediate run depends on their retrieval performance. We introduced three factors affecting the retrieval effectiveness, i.e., the degree of translation ambiguity, the number of unknown words and the number of relevant documents in a collection for a given query. Normalized-by-top-k avoids the drawback of normalized-score merging. The experimental results show that considering translation penalty and collection weight improves performance. We also used linear regression to predict the retrieval effectiveness. The performance of using the merging weight predicted by linear regression is similar to normalized-by-top-k. The performances of our merging strategies were better than normalized-score merging and round-robin merging, but were worse than raw-score merging in single IR system environment. However, raw-scoring merging is not workable if different information retrieval systems are adopted.