In this paper we describe the methodology, architecture and implementation of the information retrieval system we have developed for the Robust WSD Task at CLEF 2008. Our system is based on an extensive query preprocessing step for homogenisation of the corpus queries. The preprocessing of queries includes: rstly, an query expansion step based on Wordnet Synonsyms or an Associative Index, secondly a query translation step based on corpus article cooccurrence in Wikipedia, and thirdly a standard disjunct index search in the CLEF corpus. The crosslanguage enabled system behaves thereby as much as possible fair over di erent languages. We apply the same preprocessing steps, independent of the query and corpus language, to all queries.
The CLEF 2008 robust task has aimed at combining semantic and information retrieval. The
goal of the task was to test whether WSD can be used bene cially for retrieval systems. For this
the organizers provided document collections annotated with word sense disambiguation (WSD)
from previous CLEF campaigns. The english documents and the queries have been annotated by
the winning WSD system from the previous year by [
Our approach for this task is based on the following methodology: Firstly, we build an index for the document corpus. Secondly, for each query we generate a list of hierarchical disjunct query terms in the corpus language, and thirdly, we use these query terms to search in one of the corpus index: plain document index, WSD document index, and MST network index. The plain document index was used to calculate the result without WSD information, the WSD document index to get the task result including WSD information and at last a the MST network index for retrieval with implicetly disambiguation for baseline comparison. Altough we have deployed only a single run from our system to the challange, we discuss the idea behind the whole system architecture and lessons learned also for the crosslanguage task.
In order to compare di erent translation and disambiguation strategies our goal was to provide a fair approach to crosslanguage retrieval: each query is preprocessed in the same way independent of the query and target language. In other words: the system aim was to build a cross language retrieval system which is fair across di erent languages Fig. 1(a). The positive bias for English queries, resulting from their formulation in the corpus language, is reduced yielding to more comparable, more fair results between di erent languages.
Within our retrieval system we exploit cooccurrences on corpus level to achive thid fair cross language retrieval under these conditions. For the experiments in this task we used the English and Spanish Wikipedia1. For the mapping between the articles from one language to the other language we have extracted the cross-language links between the spanish articles and their english counterparts. Every query was then processed as shown in Fig 1(b): Firstly, we queried the Wikipedia index in the query language. Secondly, we used the appropriate english articles to extract signi cant english query terms. Thirdly, we used these query terms to query one of the CLEF indexes (see Sections 2.3).
Corpus Query Terms
English Query
Spanish
Query English Wikipedia
Spanish Wikipedia (a) Fair Crosslanguage Retrieval
(b) Corpus Cooccurrence Exploitation
The remaining contribution is structured as follows: Section 2 provides an overview on our system in terms of index structures and methodology used. Section 3 details the query processing technique which is at the heart of our approach. Results are outlined in Section 4 and Section 5 concludes this contribution with an future outlook. 2
The whole system is based on a number of di erent indexes as shown in Figure 2. The Multilingual Wikipedia Index and the Associative Index apply thereby at the query preprocessing layer and the Plain, WSD and MST Index are the di erent indexes of the task corpus data. The whole system was implemented in Java, based on the Apache Lucene2 text search engine library. This search engine library provides a high performance text retrieval engine for arbitrary, con gurable indexes.
1http://www.wikipedia.org 2http://lucene.apache.org
Query
Query Preprocessing Associative
Wikipedia
Plain
WSD
MST
For statistical corpus analyse we have developed a dictionary modul in Java. The calculation of
term weighting functions like TFIDF[
As discussed in the introduction we perform query preprocessing on every incoming query independent of the query language. The indexes we have build for query preprocessing are the Multilingual Wikipedia Index and the Cooccurrence Association Index. 2.2.1
Multilingual Wikipedia Index One important component of the system is the multilingual Wikipedia index. This index is created using the English and Spanish Wikipedia data. If an article is available in both langugae versions it is added to the multilangual Wikipedia index and an internal reference between the english and spanish text is created. Thus it is possible to search in one language and retrieve the article in the other language. To build this index the public available XML dumps are parsed and indexed. No special treatment was applied to the article text. The MediaWiki content was indexed as is without processing, stemming or stop-word removal. 2.2.2
Cooccurrence Association Index
One standard procedure applied for query expansion is the usage of term cooccurrence statistics.
This approach calculates a weigthing scheme between terms based on their cooccurrence within
all documents of an corpus. The basic rationale behind this calculations is the assumption that
statistically signi cant cooccurrences have a good chance to be synonyms[
The cooccurrence network in our system is based on the Wikipedia multilingual index. For each language of this corpus (english and spanish) a separate term-term network is computed. The weights between terms are calculated by using an similarity measure based on the cosine similarity. Only cooccurrences within a prede ned token vicinity are used and additionaly the distances between two terms within an Wikipedia article also contribute to the term similarity weights. Each term-term network is then stored in an associative index for fast retrieval of adjacent terms. 2.3
In this section we describe the di erent indexes we have created to retrieve the news articles from the CLEF corpus. Each of the following CLEF index contains all documents from the Los Angeles Times (1994) and Glasgow Herald (1995) dataset. From the documents only the content was processed, title or other metadata has been ignored. 2.3.1
Plain Document Index For the plain text variant, the data has been processed by the default Lucene indexing chain. The newspaper plain text has been tokenized by whitespaces and then transformed to lower case. The dictionary containes about 600000 terms and tokens and the overall index uses 3.4G disk storage. The analysis of the term dictionary revealed a interesting artefact of the corpus in the vocabulary growth function. One easily discover that there are two di erent underlying datasources for the corpus (see Fig. 3(a)) - the LA Times (1994) and the Glasgow Herald (1995) with a slightly di erent vocabulary. A growth function for a homogen corpus would look like a single continous growing logarithmic function without an in exion point. The reason for this in exion point is the addition of two di erent logarithmic functions - one for each newspaper. The reason for the di erent logarithmic functions is the cultural di erence and therefore a di erent word pool between Scotland and California.
StringTerms IntegerTerms ByteTerms For the word sense disambiguated variant, we used the available WSD information to compute the synonyms for the document terms. To maximize the impact of the WSD information we decided to only take the WordNet Sense with highest WSD value from the data if the term was annotated with more than one sense. All found synonym terms were indexed at the same position within the document as the original term to prevail phrase queries. Simply speaking, the Lucene index is a document term matrix. Each document is thereby represented as a vector of terms. Lucene does further allow to put more than one term on every term vector position. All terms on the same position are then transparently interchangeable. For example the term baby and the synonym infant indexed on the same position makes it possible, that the phrase query baby food would retrieve all documents, where either baby food or infant food occurs as phrase. This behavior comes from the way as Lucene processes phrase queries: Firstly, all documents are searched with a \boolean and query" for all terms in the phrase. Secondly, Lucene retrieves the \distance" inbetween the terms within the term vector of all matching documents. Thirdly, if the \distance" inbetween the query terms is one, then the phrase matches. Thats the reason why terms at the same position are completly interchangeable in phrase queries. Again no additional processing other than case normalization were applied. 2.3.3
MST Network Index For the maximum spanning tree (MST) network index we extracted, based on the part of speach (POS) tags in the corpus, only nouns from each newspaper article. Note that the focus on nouns is necessary due to the fact that otherwise the following network calculations became inpracticable and nouns carry the most valuable information. After stemming and stopword removal we ended up with an adequate list of nouns per document. To identify signi cant cooccurring terms and we test the statistical evidence by a chi-square test of independence for with the following contingency table (Tab. 1). The values A, B, C and D are the respective counts of the terms based on the scope: A the total number of terms in the corpus, B the number of occurences of the term , C number of terms associated with the term and D the number of terms wich occure with term and .
Corpus Distribution Cooccurring with 8 A C
B
D
Statistically signi cant tuples are then used to construct a document cooccurrence network. Each document is therefore described by a term network which contains only corpus signi cant term tuples where both terms occure in the document. At this level all term networks are fully connected if one takes all cooccurrences on document level into account. To prune the networks we used only the 50 top most tuples. Note that the tuple ranking is based on a corpus wide level and so the globally most signi cant tuples are used for each document and the xed number of tuples leads to a corpus based \length" normalisation.
To index these networks it is necessary to serialize the term graphs into a term sequence. A general graph has no explizit start node, neither an intuitive walking strategy to visit every node. A solution to the travelling salesman problem (TSP) starting at a speci c term, would lead to a reproducable term ordering, but the TSP is NP hard and therefore not computable in reasonable time. The serialization of trees is deterministic and so we transform the network in a tree and then serialize the tree in in x order. As a rst heuristically transformation of the network into a tree we calculate the maximum spanning tree, based on the cooccurrence weights, of the term network. Note that higher weights stand for statistically more signi cant cooccurring terms. The resulting tree was then serialized in in x order starting by alphabetically lower node of the most signi cant term tuple.
Each query is rst processed and special characters are removed, like for example interpunctation. Query terms that contain underscore charaters or terms enclosed with quotation marks are treated as phrases. For these phrases the word order is maintained throughout the whole process. After the tokenization process all query terms are removed that are found in a language speci c stop word list. For the query expansion the individual terms are used as start nodes in the term network calculated from the cooccurrence associative index. Adjacent terms from this network were then included in Find reports on pesticides in baby food report reports pesticides baby food report study story paper (a) Stopword Removal
(b) Wordnet Query Expansion report report annual
technical (c) Associative Query Expansion the query, restricted by thresholds: maximum number of terms and minimal similarity value.
One can see that the associative expanded query terms are quite di erent for the term report. The reason for this is that the associative results are computer generated based on cooccurrence statistics and the Wordnet expansion is based on human edited synonyms. Note that we have discovered, that for other terms the results are fully \overlapping" between the association and the wordnet method. Althought extensive evaluations are depending we are con dent, that the association method is very helpfull for query expansion. 3.3
After the query terms has been preprocessed and optionally the query has been expanded by synonyms or cooccurrences, each query terms is translated to the search corpus target language. For this task. we have applied this processing to both spanish and english queries, even if the target language is english. This is done to achieve optimal fairness for each query language.
Each term forms a search query within the multilingual Wikipedia index restricted to the language of the query. From the search result set the ids and the score of the top 50 results were collected. Using these ids the english version of the Wikipedia articles are retrieved from the index. All term from these articles are extracted and a weight for each term was aggregated. The weight for each term were calculated using the score of the article multiplied with the inverse document frequency of that term. For all terms from all top articles the aggregated weight was used to sort the result terms. From this sorted list of terms the top 5 were selected and used to build the nal query for the target index.
A major advantage of this approach is that it relies only on term distribution statistics to\translate" english and spanish terms into english query terms. No additional knowledge base, like an dictionary are used. Note that the presented results have been reached without extensive tuning. 3.4
The collected and translated query terms, developed by the whole query preprocessing pipeline as shown in Fig. 4 with or without the optional query expansion and multilingual steps, are then used to build up a hierarchical disjunction query. Depending on the task either the index with or withoud WSD information was then searched with this disjunction query. The default Lucene scoring algorithm, based on TFIDF, was used to calculate the rank of the retrieved articles. 0% 5% 10% 15% 20% 25% 30% 35% 40% 45% R5−0P%reci5si5o%n 60% 65% 70% 75% 80% 85% 90% 95% 100%
Ad−Hoc Robust Monolingual English Test Task − Distribution of the Topics of the Experiment
(b) Comparison Median R-Precision
Based on the original system implementation we haven't been able to successfully apply WSD information. Although the results are slightly better for a number of queries, we have not been able to show a statistically signi cant improvement.
Ad−Hoc Robust Word Sense Disambiguation Monolingual English Test Task − Box plot of the Topics of the Experiment
As one of our best system con guration we have applied at the CLEF 2008 Robust Task the Associative Pipeline as shown in Fig. 6(a). For this pipeline we used the associative query expansion modul, the english Wikipedia translation modul. The query terms developed by this process haven then been applied as disjunct query terms to the CLEF Plain Index with the results shown in Fig. 6(b). As mandatory by the task we also have applied the WSD Version of this run with the pipeline shown in Fig. 7(a) and the results shown in Fig. 7.
Ad−Hoc Robust Monolingual English Test Task − Box plot of the Topics of the Experiment
Motivated by the fact that our system failes by a hight number of queries we tried to gure out whats the reason for this. We have identi ed a bug in our system in the preprocessing pipeline of the Wikipedia Index, which we have xed for later runs. De ated by the suboptimal results
Ad−Hoc Robust Word Sense Disambiguation Monolingual English Test Task − Distribution of the Topics of the Experiment 00% 5% 10% 15% 20% 25% 30% 35% 40% 45% R5−0P%reci5si5o%n 60% 65% 70% 75% 80% 85% 90% 95% 100%
(b) Comparison Median R-Precision we also evaluated the impact of the methodology of beeing fair to every language. As shown in Fig. 8(a) started to evaluate the impact of the earlier noted bug in our implementation. Without the improvements we lost about 6 to 7 percentage precision for our Wikipedia methodology in comparance to \direct" retrieval without the Wikipedia normalisation. Unfortunately, the impact of the parsing problem biased our applied result signi cantly. The improved system is now about 2 to 3 percentage points worse than the \direct" retrieval baseline, and therefore we know that our system can perform signi cantly better. One can see in Fig. 8(b) our system now performs always better than the earlier version, what makes us con dent that will be able to resolve the remaining di erence, or in other words the costs for the methodology will be insigni cant. unstripped stripped
Direct No QE No QE 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1
Wordnet QE Associative QE
No QE 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 (a) Negligible Methodology Impact The central point in our methodology is that the system is able to do fair cross language retrieval. Therefore we have evaluated the system performance on spanish queries. For this test we have used the pipeline shown in Fig. 9(a) with Wordnet Query Expansion and the Spanish Wikipedia and Plain CLEF Index. The performance of the retrieval task is shown in Fig. 9(b). Again the \optimal" performance of the system is the \direct" english method WN Min.EN.
The crosslanguage retrieval performance is shown in this Figure as WN Plain.ES. One can see that this crosslingual system performance ist nearly the same as the WN Plain.EN monolingual performance, from which one can derive, that our system is, as intended, also competitive for the crosslingual case. 5
In this working note we have outlined our retrieval system for fair crosslanguage retrieval. Although we have applied only on the monolingual task we have been able to show, that our system perform as good as for the monolingual task in the crosslingual setup. Further we have shown that this fairness condition is not a major constraint. For the applied results we have not been able to show a signi cant improvement for the retrieval task when using word sense disambiguation information. The reason for this is probably, that the system is still not optimal for the retrieval task without WSD so the expected improvement through WSD might be lost by still undiscovered systematical faults of the system.
One of our next steps will be a deeper analysis of a number of Wikipedia articles as cooccurrence corpus. Although we have already looked up a number of articles we have not been able to develop
WN Plain EN
WN Plain ES (b) Crosslanguage Retrieval Comparison explezit characteristics to select the optimal cooccurring articles from the Wikipedia. Another important improvement to our system would be a more sophisitcated preprocessing module for our indexes.
The Know-Center is funded within the Austrian COMET Program - Competence Centers for Excellent Technologies - under the auspices of the Austrian Ministry of Transport, Innovation and Technology, the Austrian Ministry of Economics and Labor and by the State of Styria. COMET is managed by the Austrian Research Promotion Agency FFG.