This year, we have participated on Ad-Hoc Robust Multilingual track with the aim to evaluate two issues of CLIR systems. Firstly, this paper describes the method followed for query expansion in a multilingual environment by using web search results provided by the Google engine in order to increment retrieval robustness. Unfortunately, the results obtained are disappointing. The second issue reported is relative to the robustness of several usual merging algorithms. We have found that 2-step RSV merging algorithms perform better than others algorithms when geometric precision is applied.
Robust retrieval has been a task in the TREC evaluation forum [
Pseudo-relevance feedback has been traditionally used to generate new queries from the results obtained from a given source query. In this way, the search is launched twice: one for obtaining ¯rst relevant documents wherefrom new query terms are extracted, and a second turn to obtain ¯nal retrieval results. This method has been found useful to resolve queries producing small result sets, and is a way to expand queries with new terms that can make the scope of the search wider. But pseudo-relevance feedback is not that useful when queries are so di±cult that very few or no documents are obtained at ¯rst stage (the so-called weak queries). In that case, there is a straighforward solution: use another and richer collection to expand the query. Here, Internet plays a central role: it is a huge amount of web pages where almost any query, no matter how di±cult it is, may be related to some subset of those pages. This approach has obtained remarkable results in monolingual IR systems evaluated in TREC conferences. Unexpectedly, in a multilingual scenario the obtained results are very poor and we think that our implementation of the approach must be tunned for CLEF queries, in spite of our conviction that an intensive tuning work is unrealistic for real-world systems. In addition, such as we suspected, the quality of the expanded terms depend on the selected language.
On the other hand, we have evaluated several merging algorithms from the perspective of robustness: round-Robin, raw scoring, normalized raw scoring, logistic regression, raw mixed 2step RSV, mixed 2-step RSV based on logistic regression and mixed 2-step RSV based on bayesian logistic regression. We have found that round-Robin, raw scoring and methods based on logistic regression perform worse than 2-step RSV merging algorithms.
The rest of the paper has been organized into three main sections: ¯rst, we describe the experimentation framework, then we report our bilingual experiments with web-based expansion queries, and ¯nally we describe the multilingual experiments and the way the geometric precision a®ects to several merging algorithms.
In this section we describe brie°y the architecture of the multilingual system, translation approaches, query preprocessing and merging approaches.
Our Multilingual Information Retrieval System uses English as the selected topic language, and the goal is to retrieve relevant documents for all languages in the collection, listing the results in a single, ranked list. In this list there is a set of documents written in di®erent languages retrieved as an answer to a query in a given language, English in our case. There are several approaches for this task, such as translating the whole document collection to an intermediate language or translating the question to every language found in the collection. Our approach is the latter: we translate the query for each language present in the multilingual collection. Thus, every monolingual collection must be preprocessed and indexed separately. The preprocessing and indexing tasks are described below. 2.1
In CLEF 2006 the multilingual task is made up by six languages: Dutch, English, French, German, Italian and Spanish. The pre-processing of the collections is the usual in CLIR, taking into account lexicographical and morphological idiosyncratic of every language. The pre-processing is summarized in table 1.
² English has been pre-processed as usually done in past years. Stop-words have been
eliminated and we have used the Porter algorithm[
Preprocessing
Decompounding Translation approach
Once collections have been pre-processed, they are indexed with the IR-N [
1Snowball is a small string-handling language in which stemming algorithms can be easily represented. Its name
was chosen as a tribute to SNOBOL. Available at http://www.snowball.tartarus.org
2Reverso is available on-line at www.reverso.net
3FreeTrans is available on-line at www.freetranslation.com
² Round-Robin fashion. The documents are interleaved according to rank obtained for each
document by means of monolingual information retrieval processing. Thus, given a
multilingual collection and N languages, the ¯rst document for each monolingual retrieval list
will constitute M ¯rst documents, the second document of each list will constitute the next
M documents, and so on. In this case, the hypothesis is the homogeneous distribution of
relevant documents across the collections. This merging process decreases precision about
40% because of the merging process [
RSVi0 =
RSVi
max(RSV )
; 1 <= i <= N
{ A variant of the previous method is to divide each RSV by the di®erence between the
maximum and minimum document score values [
This year we have selected the following merging algorithms: round-Robin, raw scoring, normalized raw scoring, logistic regression, raw mixed 2-step RSV, mixed 2-step RSV based on logistic regression and mixed 2-step RSV based on bayesian logistic regression:
RSVi0 =
RSVi ¡ min(RSV )
max(RSV ) ¡ min(RSV )
; 1 <= i <= N
² Original 2-step RSV merging strategy consists of calculating a new RSV (Retrieval Status
Value) for each document in the ranked lists at every monolingual list. The new RSV,
called two-step RSV, is calculated by reindexing the retrieved documents according to a
vocabulary generated from query translations, where words are aligned by meaning, i.e.
each word is aligned with its translations [
Although the proposed algorithm to align phrases and translations at term level works well, it does not obtain fully aligned queries. In order to improve the system performance when some terms of the query are not aligned, we generate two subqueries. The ¯rst one is made up by the aligned terms only and the other one is formed with the non-aligned terms. Thus, for each query every retrieved document obtains two scores. The ¯rst score is obtained by using the 2-step RSV merging algorithm over the ¯rst subquery. In contrast, the second subquery is used in a traditional monolingual system with the respective monolingual list of documents. Therefore, we have two scores for each query, one is global for all languages and the other is local for each language. Thus we have to integrate both values. As a way to deal with partially aligned queries (i.e. queries with some terms not aligned), we have used raw mixed 2-step RSV and logistic regression: { Raw mixed 2-step RSV method:
RSVi0 = ® ¢ RSVialign + (1 ¡ ®) ¢ RSVinonalign
where RSVialign is the score calculated by means of aligned terms, as original 2-step
RSV method shows.On the other hand, RSVinonalign is calculated locally. Finally, ® is
a constant (usually ¯xed to ® = 0:75).
{ Logistic regression: [
P rob[Di is reljranki; rsvi] = 1 + e®+¯1¢ln(ranki)+¯2¢rsvi
e®+¯1¢ln(ranki)+¯2¢rsvi The coe±cients ®, ¯1 and ¯2 are unknown parameters of the model. The usual methods when ¯tting the model tend to be maximum likelihood or iteratively re-weighted least squares methods. Because this approach requires ¯tting the underlying model, the training set (topics and their relevance assessments) must be available for each monolingual collection. In the same way that the score and ln(rank) evidence was integrated by using logistic regression (Formula 4), we are able to integrate RSV align and RSV nonalign values:
P rob[Di is relj£] = e®+¯1¢ln(ranki)+¯2¢rsvialign+¯3¢rsvinonalign
1 + e®+¯1¢rsvialign+¯2¢rsvinonalign where £ = ranki; rsvialign; rsvinonalign and RSVialign and RSVinonalign are calculated as Formula 3. Again, training data must be available in order to ¯t the model. This is a serious drawback, but this approach allows integrating not only aligned and non-aligned scores but also the original rank of the document:
P rob[Di is relj£] =
e®+¯1¢ln(ranki)+¯2¢rsvialign+¯3¢rsvinonalign+¯4¢rsvilocal 1 + e®+¯1¢ln(ranki)+¯2¢rsvialign+¯3¢rsvinonalign+¯4¢rsvilocal (6) where rsvilocal is the local rank reached by Di at the end of the ¯rst step, and £ = rsvilocal; ranki; rsvialign; rsvinonalign; rsvilocal. (3) (4) (5) ² In addition, this year we have used bayesian logistic regression such as is implement in BBR package4. 3
Expanding user queries by using web search engines such as Google has been successfully used for improving robustness of retrieval systems over collections in English language. Due to the multilinguality of the web, we have assumed that this could be extended to additional languages, though the smaller amount of non-english web pages could represent an important drawback. In ¯gure 1 the process for query expasion by using the Internet is drawn. The process is splitted into the following steps: 1. Web query generation. First, we take the original query and generate a set of words that will be used to search the web. Since queries in CLIR contain title and description ¯elds, it is important to de¯ne how terms are taken from these ¯elds. Depending whether we consider the title ¯eld or the description ¯eld, the generation of the query varies: 4BBR software available at http://www.stat.rutgers.edu/ madigan/BBR.
² From title. Experiments expanding queries based just on the title ¯eld take all the terms in the ¯eld in lower case joined with the AND operator. ² From description. For those experiments where the description ¯eld is the source of terms to generate the web query, a selection of terms has to be done. For that, stop words are removed (using a di®erent list according to the language the description is written in) and the top 5 ranked terms are taken to compose, as for the title ¯eld, an AND query. The score computed for each term to rank them obeys the following formula: wk =
(Fk=Dk)1:5 log(maxf2000; Dkg) (7) where wk Fk Dk is the weight of term k is the frequency of term k (number of ocurrence in the description ¯eld) is the document frecuency of term k (number of ¯elds the term appears in) 2. Web search Once the web query has been composed, the web search engine is called to retrieve relevant documents. For this, the Google API (Application Programming Interface) enables the use of its search engine facilities inside our programs. Thus, we can automate the process of query expansion through Google using its Java API. This web search is done specifying the language of the documents expected for the retrieval. Therefore, a ¯lter on the language is set on the Google engine. 3. Term selection from web results Google returns documents in order of relevance in groups of 10 items; our implementation takes into account the 20 top ranked items (thus, the ¯rst two pages of search results). Each item points to an URL but also contains the so-called \snippet", which is a selection of text fragments from the original pages containing the terms involved in the web search (i.e. the query terms). This kind of summary is intented to let the user better follow those links that are of its real interest. In our implementation of query expansion by using web documents we have performed experiments using just the snippets as retrieved text in order to propose new query terms, and also experiments where terms are selected from full web page content (dowloading the document from the returned URL).
In both cases (selection of terms from snippets or selection from full web pages), the ¯nal set of terms is the composite of those 60 terms with the highest frequency after discarding stop words. Of course, in the case of full web pages, the HTML tags are also conveniently eliminated. To generate the ¯nal expanded query, terms are repeated according to its frequency (normalized to that of the least frequent term in the group of 60 selected terms).
As an example of the queries generated by the described process, for a title with words \inondation pays bas allemagne" the resulting expansion would produce the text: pays pays pays pays pays pays pays pays pays pays pays pays pays pays pays pays pays bas bas bas bas bas bas bas bas bas bas bas bas bas allemagne allemagne allemagne allemagne allemagne allemagne allemagne inondations inondations inondations france france france inondation inondation inondation sud sud cles cles belgique belgique grandes grandes histoire middot montagne delta savent fluviales visiteurs exportateur engag morts pend rares projet quart amont voisins ouest suite originaires huiti royaume velopp protection luxembourg convaincues galement taient dues domination franque xiii tre rent commenc temp monarchie xii maritime xive proviennent date xiiie klaas xiie ques connu or sinter ans anglophones 3.1
For every language we have generated four di®erent collections of queries, one without expansion and three with web-based expansion: 1. base { No expansion, the original query is used and its results taken as base case 2. sd-esnp { Expansion using the original description ¯eld for web query generation and ¯nal terms selected from snippets 3. st-esnp { Expansion using the original title ¯eld for web query generation and ¯nal terms selected from snippets 4. st-efpg { Expansion using the original title ¯eld for web query generation and ¯nal terms selected from full web pages
Results obtained are discouraging as all our expansions lead to worse measurements of both Rprecision and average precision. Figures 2 and 3 show graphically values obtained when evaluating on these measures. For technical reasons the expansion of type st-efpg for Dutch was not generated.
In a robust evaluation the key measure should the geometric average precision since it emphasizes the e®ect of improving retrieved documents on weak queries, as the task itself de¯nes. For future work we plan to study the value obtained on such a measure when using expanded queries and when merging retrieved items in a multilingual retrieval, as it is di±cult to explain the godness of our approach on the robust task without it.
From the results above some conclusions can be extracted. The main one is that the title ¯eld is a much more suitable source of items for a web-based expansion. Indeed, for many authors the title can be considered as the set of query terms that the users should pass to a search engine. Thus, web query generation from the description ¯eld even using sophisticated formulae is, as results re°ect, a worse choice when a title ¯eld is available.
The second observation is on the fact of very similar results independently on the ¯nal selection of terms, that is, it seems that the decision of taking ¯nal terms either from snippets or from full web pages text does not determine signi¯cant di®erences on results obtained. This issue needs further investigation since expanded queries are quite di®erent on the last half of the selected terms (those that are less frequent) and these results make us think of the system not pro¯ting from the full set of terms passed.
As last underlined point, we ¯nd that results depends on the language under study. We think this is due to di®erences on the size of existing collections of pages for each language found in the web, and that could explain the slightly better results in the case of English compared to the rest of languages. 4
As the section 2 is depicted, the merging algorithm is the only di®erence between all our multilingual experiments. Table 2 show the obtained results in terms of 11-pt average precision, R-precision and the new measure geometric precision. From the point of view of the average precision, the more interesting result is the relatively poor result obtained by the methods based on machine learning. Thus, mixed 2-step RSV-LR and mixed 2-step RSV-BLR performs slightly worse than mixed 2-step RSV-LC in spite of this last approach does not use any training data. As usual, logistic regression performs better than round-Robin and raw scoring, but the di®erence is not as relevant as other years. Thus, we think that di±cult queries are not learned as good as usual queries, probably because, given a hard query, the relation between score, ranking and relevance of a document is not clear at all, therefore machine learning approaches are not capable to learn a good enough prediction function. In the same way, this year there are not only hard queries, but also very heterogeneous queries too, from the point of view of average precision. Thus, the distribution of average precision is very smooth and it makes more di±cult extracting useful information from the training data.
Since the 2-step RSV overcomes largely the rest of tested merging algorithms when they are evaluated by using geometric precision measure, we think that 2-step RSV merging algorithm is better suited than other merging algorithms in order to improve the robustness of CLIR systems. In this way, if we use geometric precision to evaluate de CLIR system, the di®erence of performance between results by using 2-step RSV and the rest of merging algorithms is higher than by using traditional 11Pt-AvP or R-precision measures. 5
We have reported our experimentation for Ad-Hoc Robust Multilingual track CLEF task about web-based query expansion for other languages than English. Firstly, we try to apply the expansion of queries by using web search engine such as Google. This approach has obtained remarkable results in monolingual IR systems evaluated in TREC conferences. But in a multilingual scenario the obtained results are very poor and we think that our implementation of the approach must be tunned for CLEF queries, in spite of our belief in that an intensive tuning work is unrealistic for real-world systems. In addition, such as we suspected, the quality of the expanded terms depend on the selected language. The second issue reported is relative to the robustness of several usual merging algorithms. We have found that Round-Robin, raw scoring and methods based on logistic regression performs worst from the point of view of robustness. On the other hand, 2-step RSV merging algorithms perform better than the others algorithms when geometric precision is applied. Anyway, we think that the development of a robust CLIR system does not require special merging approaches, it "only" requires good merging approaches. Maybe that other CLIR problems such as translation strategies or the development or an e®ective multilingual query expansion should be revisited in order to obtain such a robust CLIR model. 6
This work has been supported by Spanish Government (MCYT) with grant TIC2003-07158-C0404.