We participated in two tasks: Multi-8 two-years-on retrieval and Multi-8 results merging. For our multi-8 two-years-on retrieval work, simple multilingual ranked lists are first built by merging ranked lists of different languages that are generated by single types of retrieval algorithms. Then, algorithms are proposed to combine these simple multilingual ranked lists into a single ranked list. Empirical study shows that the approach of combining multilingual retrieval results can substantially improve the accuracies over single multilingual ranked lists. Multi-8 results merging task is our primary interest. This task is viewed as similar to the results merging task of federated search. Query-specific and language-specific models are proposed to calculate comparable document scores for a small amount of documents and estimate logistic models by using information of these documents. The logistic models are used to estimate comparable scores for all documents and thus the documents can be sorted into a final ranked list. A set of experiments demonstrated the advantage of the query-specific and language-specific models against several other alternatives. Multilingual retrieval, Crosslingual retrieval, Results merging. The first task as Multi-8 two-years-on is a multilingual retrieval [5,6,9,13,14,15] task, which is to search documents in eight languages with queries in a single language (i.e., English queries in this work). One method is to tune accurate bilingual retrieval results [14,15] (or monolingual results of documents in the same language as queries) and then merge the bilingual retrieval results together. For each bilingual run, previous research [5,14,15] has demonstrated how to do many instances of bilingual retrieval by tuning the methods of translating the query into target language and then generate an accurate bilingual run. Finally, those bilingual runs generated with different methods are merged into a final multilingual ranked list. However, it may not be easy to merge accurate bilingual retrieval results into accurate multilingual retrieval results. One reason is that the ranges and distributions of document scores within these bilingual ranked lists can be very different as quite different retrieval methods have been tuned to generate accurate bilingual results of different languages separately [14,15]. Therefore, it is difficult to merge those bilingual result lists with quite different characteristics.
One alternative approach of generating multilingual retrieval result is to first generate simple bilingual
runs by same type of retrieval algorithm with the same configuration and then merge the bilingual
results into a simple multilingual ranked list. Many simple multilingual results can be obtained by
applying different retrieval algorithms with different retrieval configurations. Finally, those simple
multilingual ranked lists can be combined into a more accurate multilingual ranked list. This method
has been shown to be effective in the work of [
The second task as Multi-8 results merging task is to merge ranked lists of eight different languages
(i.e., bilingual or monolingual) into a single final list. This task is very similar to the results merging
task of federated search [
Previous research in [
Based on this observation, we propose query-specific and language-specific results merging algorithms similar to those of federated search. For each query and each language, a few top ranked documents from each resource are downloaded, indexed and translated to English. Language-independent document scores are calculated for those downloaded documents and a logistic model is built for mapping all document scores in this ranked list to comparable language-independent document scores. Multiple logistic models are built in a similar manner for ranked lists in different languages and comparable scores can be estimated for all documents. Finally, all documents are ranked according to their comparable document scores. Experiments have been conducted to show that query-specific and language-specific merging algorithms outperform several other results merging algorithms. Furthermore, the query-specific and language-specific merging algorithms need to process (i.e., download, index and translate) very limited amount of documents (e.g., 10 per <query, language> pair) to acquire accurate results.
Accurate multilingual retrieval results are generated in this work by combining retrieval results from multiple multilingual retrieval methods. Specifically, we consider retrieval algorithms based on translating queries and retrieval algorithms based on translating documents. This section first describes basic text preprocessing procedures for different languages. Then it presents details of multilingual retrieval algorithms based on query translation and document translation, and finally proposes methods to combine the results from multiple multilingual retrieval algorithms.
Stopword Lists: One of the first steps of preprocessing text documents for information retrieval is to
throw away stopwords. The Inquery stopword list [
Stemming: After stopwords have been excluded, other content words are stemmed by different stemming algorithms. Porter stemmer is used for English words. Dutch stemming algorithm is acquired from2 and stemming algorithms from1 are used for the other six languages.
Decompounding: Dutch, Finnish, German and Swedish are compound rich languages. All words that appear in the CLEF corpus and have lengths of more than 3 are considered as potential base words. In order to avoid too aggressive decompounding, we only consider base words that have higher collection frequencies than the word in consideration. Specifically, linking elements as –s-, -e-, and –en are
2 http://www.snowball.tartarus.org/
considered for Dutch, no linking elements for Finnish, elements as –s-, -n-, -e- and –en- for German
and –s-, -e-, -u- and –o- for Swedish. The same set of decompounding procedure has been used in
previous research [
Parallel corpus for word translation: Online machine translation [
One straightforward multilingual retrieval method is to translate English queries into other languages, and then search those translated queries and merge the retrieval results from different languages into a single multilingual ranked list.
English query words are first translated into words in other languages by using translation matrices built from parallel corpus. Each English word is translated into top three candidates in the translation matrices of other languages. All the three translated words of an English word are associated with normalized weights (i.e., the sum of the weights is 1) according to the weights in translation matrices. One implicit problem of translating words with the help from parallel corpus is that some English words may not have translations as the vocabulary of the parallel corpus is limited. Therefore, we utilize word-by-word translation results from online machine translation software Systran 4 as a complement. As the number of words within the queries (total 60 queries) is limited, the communication cost of acquiring these translations from Systran is small. Specifically, all English queries terms are translated into words in six other languages except Dutch (Systran does not provide translation service from English to Dutch). These sets of translation representations are combined with translations built from parallel corpus while weight of 0.2 is assigned to the translation by Systran and weight of 0.8 is assigned to the translation with parallel corpus.
The translated queries are used to search indexes built in each language. Okapi [
Another multilingual retrieval algorithm based on query translation takes advantage of query expansion by pseudo relevance feedback. Specifically, for resource of each language, query expansion is accomplished by adding 10 most common query terms within top 10 ranked documents of the initial retrieval result. The refined queries are used to generate new ranked lists of the resources and the ranked lists are then merged together.
An alternative multilingual retrieval method is to translate all documents in other languages into
English and apply the same original English queries. This method may have advantage against the
3 http://people.csail.mit.edu/koehn/publications/europarl/
4 http://www.systransoft.com/index.html
retrieval method based on query translation as the translation of longer documents may better represent
the semantic meaning than the translation of short queries. Previous research [
The document translation work is conducted using translation matrices built from parallel corpus. For each word in a language other than English, its top three English translations are considered. Five word slots are allocated to the three candidates of each untranslated word with proportion to the normalized translation probabilities of the three words. All the translated documents as well as the original English documents are collected into a single database and indexed.
Furthermore, the Okapi retrieval algorithm is applied on the single indexed database with original English queries to retrieve documents. Okapi retrieval algorithm without query expansion as well as Okapi retrieval algorithm with query expansion by pseudo relevance feedback (i.e., 10 additional query terms from top 10 ranked documents) is used in this work.
The basic assumption of improving ranking accuracy by combining ranked lists is that relevant
documents are generally retrieved by multiple multilingual retrieval algorithms while different retrieval
algorithms tend to retrieve different irrelevant documents. Similar idea has been successfully utilized in
Metasearch of information retrieval [
Therefore, one simple combination algorithm is proposed to favor documents retrieved by more retrieval methods as well as high ranking documents retrieved by single types of retrieval methods. Let drsk_mj denote the resource-specific raw document score for the jth document retrieved from the mth ranked list for kth query, drsk_m_max and drsk_m_min represents the maximum and minimum document scores in this ranked list respectively. Then, the normalized score of the jth document is calculated as: d sk _ mj =
(d rsk _ mj − d rsk _ m _ min ) (d rsk _ m _ max − d rsk _ m _ min ) score final (d ) = 1 M
∑ wm scorem (d )rm
M m=1
(1)
(2)
where dsk_mj is the normalized document score. After the normalization step, the document scores
among all ranked lists are summed up for a specific document and all documents can be ranked
accordingly. Note that this method can be seen as a variant of the well-known CombSUM [
Doc_fb UniNe
Train 0.384 0.389 0.373 0.383 0.382 0.389 0.401 0.421
Test 0.431 0.434 0.423 0.431 0.432 0.434 0.446 0.449 where Dk+ is the set of the ranks of relevant documents in the final ranked list for kth training query, and rankk+ ( j) is the corresponding rank only among relevant documents. The multilingual retrieval task of CLEF as well as many other information retrieval evaluations uses the MAP criterion to evaluate retrieval accuracy.
In order to avoid the overfitting problem of model parameter estimation, two regularization items are introduced for w and r respectively. Together with the ranking accuracy criterion in Equation 3, the training optimization problem is represented as follows: (w, r)* = argwm,r ax(log K1 ∑k j∈∑Dk+ rankjk+ ( j) − m∑=1 2 * a
M (wm − 1)2
M (rm − 1) 2 − ∑ m=1 2 * b ) where (w, r)* is the estimated model parameters and (a,b) are two regularization factors that are set to 4 in this work. This problem is not a convex optimization problem and multiple local maximal values exist. A common solution is to search with multiple initial points.
After the desired model parameters have been estimated, it can be applied on test queries to combine ranked lists of different retrieval systems. This method is called learning combination method in this work.
Multilingual retrieval results are composed of documents from different languages. Therefore, it is helpful to first investigate the retrieval accuracies of results from single types of languages. Table 1 shows the bilingual retrieval results by translating English queries into other languages and the monolingual retrieval result of English. All the runs have utilized query term expansion by pseudo relevant feedback as described in Section 2. It can be seen that the retrieval accuracies of singe types of languages vary from 0.35 to 0.46. Table 2 shows the monolingual English retrieval result and bilingual retrieval results by translating documents in other languages into English and searching with English queries. Query expansion has been used for this retrieval method and the additional terms are extracted from the top 10 ranked documents among all English documents and the translated documents from other languages. It can be seen that although the retrieval method based on query expansion and the retrieval method based on document expansion generate similar results on several language (e.g., German and Spanish), their effectiveness on some other languages (e.g., Dutch and Finnish) are rather different. Note that the monolingual retrieval results of English with methods based on query translation and document translation are not exactly the same due to different configurations of retrieval methods (e.g., different query expansion methods).
The English monolingual retrieval results and bilingual retrieval results are merged together into a
multilingual ranked list by the raw document scores. Table 3 shows the results of five multilingual
retrieval algorithms on training queries (first 20 queries), test queries (next 40 queries) and the overall
accuracy. It can be seen that multilingual retrieval algorithms based on query translation and algorithms
based on document translation produce results of similar accuracy (i.e., 0.327-0.356), while the
retrieval method based on document expansion that does not use query expansion has a small
advantage. The results from multilingual retrieval system by [
One key step to improve the accuracy of multilingual retrieval result is to combine results of several multilingual retrieval methods. Two combination methods described in Section 2 as equal weight combination method and learning combination method are applied in this work. They are used to combine the results of the five retrieval algorithms described above. The combination results are shown in Table 4. It can be seen that the accuracies of combined multilingual result lists are substantially higher than the accuracies of results from single types of multilingual retrieval algorithms. This demonstrates the power to combine multilingual retrieval results. Detailed analysis shows that although the training combination method is consistently better than the equal weight combination method for the same configurations (i.e., the same number of ranked lists to combine), its advantage is very small. One possible reason is that the accuracies of the five retrieval algorithms are close and it does not make too much difference to adjust the voting weights among them.
The second task we participated in CLEF 2005 is results merging for multilingual retrieval. Two sets of
ranked lists across eight different languages are provided within this task and the goal is to merge these
individual ranked lists together into two single lists with high accuracy. This is a difficult task as: i).
Ranked lists from different languages may have different score ranges due to different retrieval
strategies such as methods of query translation or query expansion [
Previous research [
In this paper, a new approach is proposed to learn query-specific and language-specific models of
translating language-specific document scores into comparable document scores. In particular, a small
set of documents from each language is indexed at retrieval time to compute comparable document
scores, and then a query-specific and language-specific model is trained by both comparable document
scores and language-specific document scores of this small set of documents. By applying these models
on ranked lists of all languages, comparable document scores can be obtained for all the returned
documents and the final ranked list can be achieved. This approach has an advantage to avoid the
requirement of human relevance judgment data for training. It only uses automatically computable
document scores as surrogate of relevance judgment data and thus is similar as the semi-supervised
learning results merging method in federated search [
This section is organized as follows: In section 4.1, an approach of learning query-independent and language-specific logistic transformation merging model is described and a new extension of learning the model by maximizing mean average precision is proposed; In Section 4.2, we describe the new approach of learning query-specific and language-specific result merging algorithm.
To make the retrieved results from different ranked lists comparable, one natural idea is to map all the
document scores into the probabilities of relevance and rank all documents accordingly. Particularly,
logistic transformation model has been successfully utilized in previous study to achieve this goal
[
1 1 + exp(ai rk _ ij + bi dsk _ ij + ci ) ∑ P* (rel | d k _ ij ) log(P(rel | d k _ ij )) k,i, j training procedure of maximizing MAP searches for a set of model parameters that generates the highest MAP value. However, this problem is not a convex optimization problem and multiple local maximal values exist. A common solution is to search with multiple initial points.
The new algorithm of training logistic model for mean average precision is called logistic model with MAP goal in this paper. This is believed to be a more direct method to improve the MAP value of multilingual retrieval system in CLEF and also a better method to reflect users’ preference than training logistic model with MLE criterion.
One particular problem about language-specific logistic transform merging model introduced in Section 4.1 is that it applies the same model on results of different queries from each language. This is problematic when result lists of different queries have similar score distributions but have different distributions of probability of relevance. This suggests that query-specific model should be studied for high merging accuracy of multilingual retrieval.
Previous research has proposed query-specific merging method that uses the two step Retrieval Status
Values (RSV) [
To propose methods that work in stricter environments, we follow the multilingual federated search approach in this research. There exists a resource that contains all documents from one language. These resources provide searching services of their documents.
Query-based sampling method is utilized in this work to learn corpus statistics from each resource with
a particular language [
The above paragraphs describe the procedures to acquire estimated corpus statistics in multilingual
federated search environment. With this information, retrieved documents from individual resources
will be assigned comparable document scores and merged into a single final ranked list. Previous
research [
Comparable document scores based on document translation are acquired by applying a single Okapi retrieval method on all retrieved English documents and all the translated documents from resources with other languages. Specifically, all retrieved documents in languages other than English are first translated into English in word-by-word manner using translation matrices, and then are merged into a single set of documents with documents that are originally in English. Furthermore, this set of documents is indexed and an Okapi retrieval algorithm is applied on this set of documents with corpus statistic from the centralized sample database of English resource. As this results merging method downloads (also indexes and translates) all documents in the given ranked lists, it is called complete downloading method.
Two sets of comparable document scores based on retrieval methods of query translation and document translation are merged together into a single set with the method described in Section 2. Specifically, the two sets of scores are first normalized separately and then are combined into a new ranked list with the equal weight combination method described in Section 2.
It can be noted from the description that a large amount of online costs is associated with the complete downloading result merging algorithm. Within federated search environment, communication cost is associated with downloading each document. Furthermore, computation costs as indexing and translation are also associated to process each downloaded document. These problems are particularly serious as they happen in an online manner. Therefore, a more efficient algorithm is much more desired for operational system.
The key idea to calculate comparable document scores more efficiently is to only calculate scores for a small set of representative documents. Particularly, a small set of retrieved documents from each resource is selected; the above procedure of downloading and calculating new scores based on query translation and document translation is applied on this set of documents. These documents that have both language-specific scores and calculated comparable scores serve as training data for learning a logistic model, which estimates the comparable document scores for other documents that have not been downloaded and indexed.
Generally top ranked documents of retrieved documents from each resource are more probable to be relevant, they are selected for downloading and calculating comparable document scores. Let us assume top L documents from the ranked list of each resource are downloaded to calculate comparable scores. Let the pair (dck’_il, dsk’_il) denote the normalized comparable document score and normalized language-specific score for the lth downloaded document of the ith resource for k’ the query. Let the pair (ak’_i, bk’_i) denote the parameters of the corresponding query-specific and language-specific model. These parameters are learned by solving the following optimization problem to minimize the mean squared error between exact normalized comparable scores and the estimated comparable scores as: ( * ak'_ i , bk*'_ i ) = arg min (a,b)
∑ (dCk'_ il − dk'_ il∈DL ∨DNL
1 1 + exp(a ∗ d Sk '_ il + b ∗1) ) 2 (7) where DL is the downloaded L documents from the resource and DNL is a pseudo set of L documents with pseudo normalized comparable scores zero and pseudo normalized language-specific scores zero. This set of pseudo documents is introduced in order to make sure that the learned model ranks documents in the correct way (i.e., documents with higher language-specific scores are ranked higher in the ranked list with comparable scores than documents with lower language-specific scores). Finally, logistic models can be learned for all resources in the same way. They are applied to all retrieved documents from all resources and the documents can be ranked according to their estimated comparable scores. Note that only language-specific document scores are used in the logistic model in Equation 7 while document ranks in language-specific ranked lists are not considered. This is different from Equation 5, and is used here in order to reduce the number of parameters for the limited amount of data (i.e., the small set of documents with both comparable scores and language-specific scores). Note that exact comparable document scores are available for the documents that have been downloaded and processed. One method to take advantage of these scores is to combine them with the estimated scores. In this work, they are combined together with equal weights (i.e., 0.5).
This section presents the experiment results of different results merging algorithms for ranked lists of
different languages. These results merging algorithms work on two sets of ranked lists from UniNE
5
system [
To improve the merging accuracy, query-specific and language-specific algorithms are introduced. Two types of algorithms are evaluated in this work. The first method downloads all documents from ranked lists of different languages and calculates comparable document scores (C_X). The second method downloads top ranked documents and calculates their comparable documents to build logistic models. These models generate estimated comparable document scores and finally combine the estimated scores with acquired exact comparable scores wherever they are available (Top_X_C05). The experimental results of different variants of these algorithms on UniNE system and HummingBird system are shown in Tables 9 and 10 respectively. Note that both these two algorithms do not require human relevance judgment for training data. Therefore, the results on training query set and test query set are obtained separately without using any relevance judgment data.
It can be seen from Table 9 and Table 10 that both these two query-specific and language-specific merging algorithms substantially outperform query-independent and language-specific algorithms. The accuracies of the two query-specific and language-specific methods (i.e., C_X and Top_X_C05) are close on the UniNE system. It is interesting that the Top_150_C05 method outperforms all C_X runs
on the UniNE system. This means that the combination of estimated comparable scores and exact comparable scores can be more accurate than exact comparable scores in some cases. Detailed analysis shows that the estimation of comparable document scores is related with document scores from ranked lists of UniNE systems. The estimated document scores can be seen as combination results from not only the two retrieval methods that based on query translation and document translation but also the retrieval method of UniNE system. Therefore, the combined results that are related with three retrieval systems may be better than those of exact comparable scores from two retrieval systems. It is encouraging to see that with very limited amount of downloaded documents, the Top_10_C05 method still has more than 10 percent advantage over the query-independent and language-specific result merging algorithms.
It can be seen from Table 10 that the advantage of query-specific and language-specific algorithms over query-independent and language-specific algorithms is even larger for the results on HummingBird system than those on UniNE system. This demonstrates the power of query-specific and language-specific merging algorithms for ineffective ranked lists. It is interesting to note that the Top_X_C05 runs are not as effective as C_X runs on HummingBird System. The reason can be explained that the ranked lists of HummingBird system are not as accurate as those of UniNE systems. The influence of document scores within ranked lists of HummingBird on the estimated comparable score is not as helpful as that from the UniNE system.
This paper describes the algorithms we have studied and proposed for the CLEF 2005 evaluation tasks as: Multi-8 two-years-on retrieval task and Multi-8 results merging task.
For multi-8 two-years-on retrieval task, our focus is to generate and combine multilingual retrieval results that are built from simple bilingual (or monolingual) ranked lists. Specifically, we first generate multiple multilingual retrieval results by merging bilingual (or monolingual) retrieval results of same types of retrieval algorithms, and then combine the multilingual retrieval results together. Several combination methods have been proposed and empirical studies have demonstrated that the combination of multilingual retrieval results can substantially improve the accuracies over single multilingual ranked lists.
The task of Multi-8 results merging task is to merge two sets of eight bilingual (or monolingual for English) ranked lists into multilingual ranked lists. This is the primary interest of our work and we have proposed to apply results merging algorithm of federated search task for this problem. Top ranked documents within each ranked list are indexed and translated to compute comparable document scores. Query-specific and language-specific logistic models are built based on comparable document scores of these documents and also the scores of these documents in language-specific ranked lists. These logistic models have been built to estimate comparable document scores for all documents in ranked lists of different languages, and finally all documents are sorted accordingly. Experiments have shown that the new proposed methods outperform previous research and they only need to process (i.e., download, index and translate) very small amount of documents (e.g., 10 per <query, language> pair) to acquire accurate results.
Although query-specific and language-specific merging algorithm algorithms are much better than previous merging methods, in some cases their accuracies are still not at bilingual levels (e.g., UniNE systems). This suggests the necessity of more sophisticated result merging algorithms for future research.
Research presented in this paper has been supported in part by an ARDA grant under Phase II of the AQUAINT program. Any opinions, findings, conclusions, or recommendations expressed in this paper are the authors’, and do not necessarily reflect those of the sponsor.