In this paper we present the technical details of the retrieval system with which we participated at the CLEF09 Ad-hoc TEL task. We present a retrieval approach based on multiple indexes for di erent languages which is combined with a conceptbased retrieval approach based on Explicit Semantic Analysis. In order to create the language-speci c indices for each language, a language detection approach is applied as preprocessing step. We combine the di erent indices through rank aggregation and present our experimental results with di erent rank aggregation strategies. Our results show that the use of multiple indices (one for each language) does not improve upon a baseline index containing documents in all languages. The combination with concept based retrieval, however, results in better retrieval performance in some of the cases considered. For the bi-lingual tasks the nal retrieval results of our system were the 5th best results on the BL dataset and the second best on the BNF dataset.
In this paper we extend this model to be able to handle corpora containing documents in multiple languages and moreover documents containing elds in di erent languages. Our approach is directly motivated by the CLEF Ad-hoc TEL task. Here the target collection contains documents in di erent languages and the task is to nd relevant documents in all languages for given topics. Our hypothesis is that retrieval can be improved by translating topics to all languages of the corpus, performing a language speci c search for each translation and aggregating all the results for the single indices into one nal ranking.
Another important question we address in this paper is whether concept- and MT-based techniques can be successfully combined to increase the performance of CLIR compared to conceptbased and MT-based techniques alone.
For both problems, i.e. retrieval using multiple indices and combination of MT-based and concept based retrieval, relevance measures computed by di erent models have to be combined to an aggregated relevance score. A common approach to this problem that we also use in this paper is rank aggregation. This means that the nal scores of each model are used as input values for the aggregation function. In the following we will describe the main techniques used in related work to combine di erent retrieval approaches.
In order to combine concept-based retrieval and term-based retrieval, Muller and Gurevych [
Croft [
The results of these di erent combination approaches show that evidence coming from di erent sources can be aggregated to achieve better performance of the overall retrieval system. In the context of our participation on CLEF this year, we investigate whether these techniques can also be used for the Ad-hoc task on the TEL datasets. Overall, we build on the system we presented at CLEF2008, which achieved a reasonable performance using concept based retrieval based on Explicit Semantic Analysis.
Our main contributions in this paper are the following ones:
We extend both MT-based and concept-based retrieval into truly multi-lingual settings where not only the document collection can contain multiple languages but a document itself can contain elds in di erent languages. The main innovation is here that we maintain separate indices for each language and apply our combination strategies on the retrieval engines for each of these language-speci c indices. Our results show that for the CLEF Ad-hoc TEL task we get a similar performance compared to a baseline system based on a single index, but no signi cant improvement over it.
We also present an approach by which MT-based and concept-based retrieval (by ESA) can be combined through rank aggregation. This combination e ectively increases the performance of the retrieval system for the bi-lingual task on the BL dataset using French topics and the ONB dataset using English and German topics.
The paper is structured as follows: In the Section 2 we describe our retrieval system and de ne MT-based retrieval, concept based retrieval as well as di erent aggregation approaches. In Section 3 we describe the used datasets and the preprocessing of the data. In Section 4 we present the experiments on the Ad-hoc TEL task using topics from CLEF2008, in Section 5 using topics from CLEF2009. We conclude in Section 6. g n i x e d n I h c r a e S en ed fr …
(en)
(de)
en ed fr …
ESA ESA
ESA (en) ESA (de) ESA (fr) ESA
The main idea behind our approach is to use multiple indices (one for each language under consideration, which are all the common European languages). These are indices of elds of documents in di erent languages as well as concept indices of documents. The basic idea is to combine retrieval results based on the di erent indices. Figure 1 illustrates the di erent indices and processing steps which will be described in more detail in the following sections. But rst we introduce some notation. 2.1
In the remaining article we use the following notations:
L = f ; ; ; : : :g: A set of languages.
D = fd1; : : : ; dng: A text corpus consisting of multi-lingual documents. The function f (d) selects all the document fragments of d in language . D = ff (d1); : : : ; f (dn)g de nes a restriction of corpus D where all document consist of their fragments in language . C = fc1; : : : ; cmg: A set of concepts that de ne a concept space. Each concept has a textual description. We use ci both to refer to concept ci as well as to the description of ci. The intended meaning will be clear from the context.
T = ft ;1; t ;2; : : :g: A set of topics in language that will be used to construct queries to the retrieval system. Each topic represents a certain information need. for the translation of a topic t to language we will use the notation t ! .
Statistics of a term w in document d of corpus D: { TFd(w): Term frequency of w in document d. { jdj: Document length of d. { DF(w): Document frequency of w in corpus D. { TF(w): Term frequency of w in corpus D. { n = jDj: Number of documents.
{ jd^j: Average document length in corpus D. 2.2
In our settings, the document corpus consists of multi-lingual documents which contain content in multiple languages. In our approach we assume that the parts of a document which are in di erent languages are identi ed and labeled appropriately. This is essentially the way how the f function described above is realized. This makes the application of language detection approaches necessary before indexing the documents (we will rely on di erent indices per language). In our settings the parts correspond to the elds of the documents in the TEL dataset which can be in di erent languages. In order to identify the language for each eld, we exploit a language detection approach based on character n-grams models. The probability distributions for character sequences of the size n are used to classify text into a set of languages. We used a classi er provided by the Ling Pipe Identi cation Tool1 which was trained on corpora in di erent languages as described in Section 3. 2.3
In the most simple case, the CLIR problem can be formulated as bilingual retrieval: given a topic t in language and a set of multi-lingual documents D, nd relevant documents in D . If all document fragments in D are of language then D = D , which is the most common scenario. In this case a MT system translating text from language to can be used to reduce the problem to mono-lingual retrieval by translating topic t to a topic t ! in language . Mono-lingual retrieval models can then be used to de ne the relevance of documents in D to the translated topic t ! .
In our approach we extend the bi-lingual setting to multiple languages. As shown in Figure 1 the rst step is building indices for each language that contain all terms of documents in D . This means that index I only contains information about text in language . In the retrieval step, each topic is simultaneously translated into all languages and each translation of the topic is matched to the corresponding index. This results in a di erent ranking for each language. An overall ranking is computed through di erent aggregation approaches of these rankings which will be described in more detail in Section 2.5.
The matching of the translated topic to the language speci c index is based on a monolingual retrieval model. In this paper we use models that have been implemented in the Terrier2 framework.
For mono-lingual IR, we use the following retrieval models:
DLH13 BB2
Score(t; d) := X TFt(w) w2t
TFd(w) log TFd(w)jd^jjDj + :5 log 2 TFd(w)(1 jdjTF(w)
TFd(w) )
jdj TFd(w) + :5
LemurTF IDF
As an instance of concept-based CLIR we build on the CL-ESA approach previously presented
in [
In our retrieval system each document is mapped by ESA into a conceptual representation (the Wikipedia article space) which can be understood as an interlingua-based representation abstracting from languages which is inherently able to represent documents with elds in di erent languages. As shown in Figure 1 we follow two di erent approaches to build the index. One approach maps whole documents to the Wikipedia article space using ESA without considering that documents can contain di erent languages. The second approach classi es each eld of a document into a corresponding language and then maps each eld eld into a concept vector using the a language-speci c ESA instantiation.
We compare the performance of these approaches in our experiments. In both cases we rely on a single index for concept based retrieval, as the multiple languages are already considered in the concept mapping. 2.4.1
Explicit Semantic Analysis (ESA)
ESA classi es given document d with respect to a set of explicitly given external categories C.
Gabrilovich and Markovitch [
In essence, Explicit Semantic Analysis takes as input a document d and maps it to a highdimensional real-valued vector space. This vector space is spanned by a concept space C = fc1; : : : ; cmg in language such that each dimension corresponds to concept ci. This mapping is given by the following function: : D ! RjC j with
(d) := hAS(d; c1); : : : ; AS(d; cm)i
The function AS expresses the association strength between d and the concept ci. In the original
ESA model AS is de ned by sum of TF.IDFci values of all words of wj 2 d based on the textual
description of concept ci. In previous work we examined the performance of di erent association
strength functions for CLIR tasks [
log w2d jcij
jCj DF(w) 2.4.2
Cross-lingual ESA (CL-ESA)
In this section we present the extension to ESA called CL-ESA (Cross-language Explicit Semantic
Analysis). This is a relatively straightforward extension of ESA to a cross-lingual setting which we
presented before in [
CL-ESA relies on the principle that concept vectors computed with respect to the Wikipedia database in one language can be translated into concept vectors with respect to another Wikipedia database relying on Wikipedia's language links3. This is done by mapping each dimension corresponding to article a in Wikipedia W to the dimension corresponding to article b in Wikipedia 3Cross-language links are those that link a certain article to a corresponding article in the Wikipedia database in another language.
W so that there exists a language link from a to b. This means that article a and b are textual descriptions of the same concept. Given this mapping it is for example possible to compare documents in language and based on the mapped concept vector.
In general the concept space that is used for CL-ESA needs textual descriptions of all concepts in all supported languages. We will refer to the description of concept ci in language by ci; . For a multi-lingual document d CL-ESA is de ned as follows:
AS(d; ci) := X AS(d ; ci; ) 2L (1)
When CL-ESA is instantiated using the Wikipedia database, the articles have to be restricted to the articles having cross-language links to articles in all languages in L. Then all concepts represented by an article in any language have descriptions in all other languages given by the linked articles, which is needed for our model. In the following m ! : W ! W de nes the function mapping articles from W according to language links to W .
Given a target language for the concept representation of a multi-lingual document d with respect to Wikipedia W = fa1; a2; : : :g, the association strength de ned in Equation 1 can be instantiated to Wikipedia by:
ASW (d; ai) := X AS(f (d); m ! (ai))
2L
Intuitively this is the association strength of a multi-lingual document d to a concept c represented by the Wikipedia article ai in language . This value is de ned by the sum of the association strength of all fragments f (d) in languages to the concept description of c in language . This description is given by the article in W to which ai links to. 2.4.3
Retrieval using CL-ESA Using the above de ned association strength function, a mapping concept vectors can be de ned as follows:
(d) := d~ = hAS(d; c1); : : : ; AS(d; cm)i
Given the vector representations of topics and documents, similarity measures in vector space can
be used to determine the relevance of documents to topics. In our previous work we de ned the
following relevance function [
rel(t; d) := ( ( (q)); ( (d)));
where is a projection function which reduces the dimensionality of the vector. This is done
for performance issues as e cient indexing is not possible without the reduction. In our framework
we use ambs(d~) which selects the m dimensions with highest values in d~, as this reduction function
was shown to achieve good performance in CLIR tasks [
de nes the vector space similarity. We used the cosine similarity that is de ned as of documents or topics to cosine = < ~t; d~ > k~tkkd~k 2.5
In our framework we aggregate two di erent kinds of rankings for a topic t. First, as we deal with multi-lingual documents and due to our separate language-speci c indexing approach, for each language 2 L there is a ranking that expresses the relevance based on the text parts in language . Second we compute a ranking based on the concept representation of topics and documents. In our framework we chose a two step rank aggregation approach. We rst combine all text-based rankings and nally combine the resulting ranking with the concept-based ranking. In the following we describe di erent rank aggregation methods which we used for either the rst or the second step of rank aggregation. More details will be presented in Section 4. where R is a set of rankings and (r) a weighting function. In our experiments we use the following variations of this weighting function:
Normalization using max score: (r) := 1=maxscore(r) Before the aggregation, each ranking is normalized to values in [0; 1]. This is done by dividing each ranking score by the maximum score.
Normalization using the number of retrieved documents: (r) := jrj= Pr02R jr0j where jrj is the number of retrieved documents of ranking r. This weight corresponds to the share of the number of retrieved documents for one ranking to the total number of retrieved documents for all rankings.
A priori weights based on language: (r ) := P ( ) This weighting function can applied to our rst step of rank aggregation. In this case each ranking r is weighted by the apriori probability for a document to be in a certain language . We use the share of text parts in language in relation to all text parts in the corpus a apriori probability P ( ). 2.5.2
Support Vector Machine Aggregation As alternative approach to linear aggregation we considered rank aggregation based on Support Vector Machines (SVMs). For a given topic or document, a feature vector can be built by using the relevance score returned by each index. This is then used as input for a SVM classi er that predicts the relevance of the document on the basis of a combination of the ranking scores. This means that the results of each retrieval step on the di erent indices are used as feature values. The classi cation model is trained by using the relevance assessment available for the corpus. Each relevant document for a topic de nes a positive training example, each non-relevant a negative one.
Using a linear kernel the model of the classi er corresponds to linear aggregation. By using non-linear kernels this can be extended to non-linear rank aggregation. In Section 4 we describe experiments with linear kernels and radial basis function kernels. 3
Evaluation 3.1 3.1.1
TEL Dataset In this section we rst introduce all datasets we used for our experiments. Then we describe the evaluation methodology and the evaluation measures. Finally we brie y present some details about our implementation.
The TEL dataset was provided by the European Library in the context of the CLEF 2008/2009 ad-hoc track. This dataset consists of library catalog records of three libraries: the British Library (BL) with 1,000,100 records, the Austrian National Library (ONB) with 869,353 records and the Bibliotheque Nationale de France (BNF) with 1,000,100 records. While the BL contains a majority of English records, the ONB dataset of German records and the BNF dataset of French records, all collections also contain records in multiple languages. Each record consists of elds which again Field title subject alternative abstract
Description The title of the document Keyword list of contained subjects Alternative title Abstract oft the document may be of di erent languages. Not all of these elds describe the content of the record but contain also meta data such as the publisher name or year of publication.
As the CLEF topics are only targeted at the content elds, we rst identi ed all content elds. Table 1 contains a list of the selected elds and the average count of each eld for a record. Further we reduced additional noise by removing non-content terms like constant pre x or su x terms from elds, e.g. the pre x term Summary in abstract elds.
In order to be able to use the library catalog records as multi-lingual documents as de ned in Section 2 we also had to determine the language of each eld. Our language detection approach is based on the language tags provided for 100.0% (BL), 89.916% (ONB), 81.64% (BNF) of all records as well as on the text-based language detection approach described in Section 2. Our analysis of the datasets showed that relying merely on the language tags introduces many errors in language assignment. First there are records tagged with the wrong language. Second, as there is only one tag per record, language detection based on tags is not adequate for records containing elds in di erent languages. Our language detection model determines the language for each eld based on evidence from tags and from text based classi cation. Table 2 contains the language distribution in the TEL datasets based on the tags (Tag) as well as on our detection model (Det). A manual evaluation using a random selection of records showed that performance of the language detection approach on elds is reasonable. 3.1.2
Wikipedia Database For concept-based retrieval we used the Wikipedia database in English, German and French as concept space. As we rely on bijective mappings between articles across languages for CL-ESA, we selected only those articles that are connected via cross-language links between all three Wikipedia databases. In this case every article is a concept having textual descriptions in English, German and French, namely the article text. Using the snapshot by 03/12/2008 for English, 06/25/2008 for French, and 06/29/2008 for German, we obtained the aligned collection of 166,484 articles in all three languages. 3.1.3
Training Corpora for Language Detection The language detection framework requires su ciently large corpora in all languages the classier is trained for. We rely on the Leipzig Corpora Collection4, which contains texts collected
Test Size (characters) Accuracy Test Size (characters) Accuracy from the web and newspapers, and the JRC-Acquis Multilingual Parallel Corpus5, which contains documents published by the European Union translated in various languages. 3.2 3.2.1
For language detection we used the n-gram language classi er included in the Ling Pipe software collection6. The classi er was trained using the Leipzig and JRC-Acquis corpora. When a certain language was available in both corpora we preferred the data of the Leipzig Corpus, as this showed better results in a cross validation on the training data.
We conducted multiple tests for verifying the e ectiveness of the language detection model. The results showed that using a 5-gram model and a 100,000 character training is optimal in our case. Table 3 contains the classi cation results using di erent data sizes measured by the character size. The results show that the classi er achieves high performance of more than 97% accuracy for text containing more than 32 characters. As this is given for most elds in the TEL dataset this classi er is applicable for the language detection task in our framework. 3.2.2
Document Preprocessing We used the following methods for the preprocessing of documents: Tokenizer As tokenizer we used a standard white space tokenizer. All non-character tokens were deleted. For Wikipedia articles we also deleted all wiki markup.
Stop-Word Filtering We used standard stop word lists in the languages English, German, Finnish, French, Italian, Portugese, Swedish, which were taken from the University of Neuchatel7, and Danish, Spanish, Dutch and Norwegian, which were taken form Ranks.nl8. Stemmer We used the Snowball Stemmers9 to stem terms in English, German, French, Danish,
Dutch, Finnish, Italian, Norwegian, Portugese and Swedish.
Fields in other languages than those mentioned above were not preprocessed using stemmers or stop word lists. 3.3
The relevance assessments for the search task are provided by CLEF, resulting from a pooled manual evaluation. As evaluation measure we report mean average precision (MAP), precision at a cuto level of 10 (P@10) and recall at a cuto level of 100 (R@100).
6http://alias-i.com/lingpipe/ 7http://members.unine.ch/jacques.savoy/clef/ 8http://www.ranks.nl/resources 9http://snowball.tartarus.org In our implementation we used di erent third party software tools as well as own implementations. For text based retrieval including inverted indexes and scoring models we used the Terrier IR framework. For translating the topics to various languages we used the machine translation service provided by Google10. We used our own implementation of CL-ESA for concept-based retrieval11. We also implemented an inverted concept index that allows e cient retrieval based on the concept representations of topics and documents. For example, for the ONB dataset the inverted concept index has the size of approx. 26 GB and the average processing time of a topic is approx. 135 seconds. 4
Experiments on CLEF08 Ad-hoc Topics In this section we present the results of experiments using the CLEF08 Ad-hoc topics. As relevance assessments are available for these topics we used this task to optimize our system in respect to the retrieval model and the aggregation functions.
In all experiments we relied on the mono-lingual task, i.e. English topics for BL dataset, German topics for ONB and French topics for BNF. As all of these datasets contain documents in di erent languages, cross-lingual retrieval can be applied to nd relevant documents in other languagesl. The mono-lingual task can therefore also be used to optimize the multi-lingual setting we propose in our framework. 4.1
First we conducted experiments to optimize the retrieval models for MT based IR. As this is based on mono-lingual retrieval we compared the performance of di erent State-of-the-Art retrieval models. The hypothesis here was that good performance in mono-lingual retrieval should also result in good performance in cross-lingual retrieval.
We rely on the retrieval models provided by the Terrier framework in our work. We selected the best retrieval model for each dataset according to MAP and got the following best retrieval results on the di erent TEL datasets: MAP of .34 on the BL dataset using model DLH13, MAP of .22 on the ONB dataset using model LemurTF IDF and MAP op .30 on the BNF dataset using model BB2. In the remainder of this paper we will report results relying on the best retrieval model for each dataset. 4.2
As described above we de ned two aggregation steps in our model. First the results of multiple text-based indexes are aggregated and afterwards the aggregated score is combined with conceptbased retrieval score. In the following experiments we used again the CLEF2008 topics for the Ad-hoc mono-lingual task. The rst aggregation step was evaluated on all three TEL datasets. For the evaluation of the second step we only performed experiments on the BL dataset. 4.2.1
Linear Aggregation for Multiple Indexes The baseline for the proposed retrieval using multiple indexes is given by retrieval on a single index of all text in the documents without language classi cation. The performance of this baseline is shown in the rst row of Table 4.
As described in Section 2 we used di erent normalization and weighting models for linear aggregation of the multiple indexes. Table 4 contains all results of aggregation without normalization, using max score and using the number of retrieved documents of each index and aggregation using a priori weights.
10http://translate.google.com 11http://code.google.com/p/research-esa Baseline (single index) Multiple Indexes (no norm.) Multiple Indexes (max score norm.) Multiple Indexes (num ret norm.) Multiple Indexes (a priori)
MAP .34 .25 .07 .34 .34
The results clearly show that our approaches to aggregate the results of the multiple indexes are not able to beat the baseline using a single index. Normalization based on the number of retrieved documents as well as a priori weights can both be used to achieve comparable performance in respect to MAP, P@10 and R@100. The results indicate that linear aggregation based on the multiple indexes seems not be able to improve the overall performance in this task.
As alternative approach to linear combination we experimented with Support Vector Machine based aggregation. To balance the ratio between the training data, we used all relevant documents for all topics as positive samples and randomly selected non-relevant documents as negative samples to achieve a ratio of positive/negative samples of 1/2.
As SVM implementation we used LIBSVM12. Using the SVM type C-SVC (c=1) with a radial basis function kernel, the training data could be classi ed using a 5-fold cross validation with precision of .61 and recall of .42. However when using the trained model for the actual retrieval the MAP was very low with .01. When using a linear kernel, which would lead to a classi er that is comparable to linear aggregation, we were not able to learn the model as the learning algorithm did not terminate. Our assumption is that using these kernel functions it is not possible to separate the positive and negative samples in the feature space. This would also explain the bad performance of the resulting retrieval system. It might be possible to use SVMs for rank aggregation by using other kernels, but in the scope of this paper we did not investigate that idea any further. 4.2.2
Linear Aggregation with Concept-Based Retrieval
In the technical report of last year, we presented results only based on concept-based retrieval using
ESA [
In our nal experiments using the CLEF08 topics we investigated the combination of MT
based retrieval and concept-based retrieval. As for example suggested in [
Experiments on CLEF09 Ad-hoc Topics The CLEF09 Ad-hoc topics are similar to the topics from CLEF08. The 50 topics have the same format consisting of two elds, a short title containing 2-4 keywords and a description of the information item of interest in terms of 1-2 sentences. The objective is to query the selected target collection using topics in the same language (mono-lingual run) or topics in a di erent language (bi-lingual run) and to submit the results in a ranked list ordered with respect to decreasing relevance. In line with these objectives we submitted results of six di erent runs to CLEF08. These are the results of querying English, German and French topics to the BL, ONB and BNF datasets.
The results of our experiments are presented in Table 5. The results using multiple indexes
show that this approach was not able to beat the baseline. Using a single index for the TEL
records without language classi cation and topics only translated into the main language of each
dataset achieved better performance compared to our approach based on indexes for each language
and multiple translations of the topic to the matching languages. Another result is that the
combination of concept-based retrieval to the MT-based retrieval was able to improve the retrieval
in some cases. The improvement was signi cant according to a paired t-test with con dence level
.05 for French topics on the BL dataset and English and German topics on the ONB dataset.
However in many cases the performance was similar to the baseline without statistical signi cance
of the di erence. We could therefore not reproduce the strong improvements e.g. presented in [
We also combined Machine Translation based retrieval with concept-based retrieval. The results showed that we were able to improve the baseline through the combination in some cases. However the improvement on the CLEF Ad-hoc task were not as strong as reported on other experiments in related work.
Acknowledgments This work was funded by the Multipla project sponsored by the German Research Foundation (DFG) under grant number 38457858.