For its rst birthday, the LIC2M has participated to the Small Multilingual Track of CLEF 2003. Our system is based on a deep linguistic analysis of documents and queries and on an original search algorithm inherited from the Spirit (EMIR) system. With a partially developed system, we obtained average results that will serve as a baseline for us in our future participations to IR evaluations.
The linguistic analyzer is itself composed of a set of modules customized with resources. The combination of modules and resources (dictionaries, set of categories..) depends on the language.
English corpus
corpus
search results for
French merging strategy global results
search results for Spanish original topic query processing
The indexing process can be described as follows: each document from a collection is rst processed through the linguistic analyzer, according to the language it is written in. The output of the linguistic analyzer is a stream of tokens, each token being a set of three pieces of information: lemma1, category and position. Position means o set of the word relative to the beginning of the document. The pair (lemma, category) is considered as a term. Each distinct pair is used as an entry in the index. The indexer stores for each entry, the documents containing the term, and the positions of the terms in each document. Four indexes are built, one for each language.
The query process performs the following tasks: the topic is processed through the linguistic analyzer; pairs (lemma, category) from the stream of tokens are considered at this stage as concepts and concepts are reformulated into four sets of terms, one for each target language, using monolingual and multilingual reformulation dictionaries.
The search engine then sends requests to the four indexes to get a list of the documents containing the largest number of query terms, and merges the four lists obtained. The search engine takes into account the original concepts and their weights to score the document. 3
The linguistic processing is a fundamental part of the system. We decided to base all the processing of our system on a deep linguistic analysis designed to extract precise information from the structure of texts. We will see below that this goal is not yet fully reached since all modules are not completely implemented or fully functional.
1Here and in the rest of the paper, a lemma is a normalized form and can group several lemmas (in the linguistic sense) of strict synonyms.
Figure 2 shows the organization of the modules in the linguistic processing chain. The input is a raw text in a given language2 converted to Unicode.
Tokenization
Dictionary search or default categories Idiomatic expressions
Fullform dictionary Trigram/bigram
matrices Rules
PoS tagging
Stopper
Stoplist
Named entities Syntactic analysis
Grammar rules
Complex terms
The rst step is the tokenization of the text in order to nd word and sentence breaks. Next, tokens are searched in a full form dictionary. If they are found in the dictionary, they are associated to their lemmas and are given all the morphosyntactic categories associated with this form.
It should be noted that our system uses a speci c set of morphosyntactic categories that makes it quite di erent from other systems: the categories are positional, meaning that the category itself allows to distinguish which words can appear before or after another words. For example, for French, there are pre-nominal adjectives and post-nominal adjectives. The positional properties of this large set of categories (137 for French, 120 for English, 100 for Spanish and currently only 38 for German) will allow a very e ective disambiguation, as we will see below.
If a token is not found in the dictionary, it is given a default set of morphosyntactic categories based on some typographical properties: a token beginning with an uppercase letter will obtain the categories of proper nouns, for example.
After tokenization, the idiomatic expressions are detected and replaced by a single token. Idiomatic expressions are phrases or usual compound nouns that are in our dictionary. They can be non-contiguous like phrasal verbs: "switch the light on" is replaced by "switch-on the light (on)" (the information about the preposition is kept because it will be used during syntactic analysis). The detection of idiomatic expressions is performed by applying a set of rules, that are triggered on speci c words and tested on left and right contexts of the trigger (note that the same technology is used for identifying named entities and compounds).
After these steps, each token have several possible morphosyntactic categories. The goal of the part-of-speech tagger is to drastically reduce the number of possible categories for each word. We will see below that our technology should be able to obtain results at the level of state of the art systems without any statistics. Unfortunately, this module was not ready at the time of the 2Our language and encoding identi er has not been used for CLEF as the language and encoding of each given corpus are already known. Even if some texts of one language's corpus are actually in another language (for example, some LATimes texts are in Spanish), we have decided to ignore this point.
CLEF campaign and thus we only remove functional and too frequent words with stoplists. We then kept all other tokens with content word categories.
The fth step uses the same algorithms as the idiomatic expressions step, with a speci c set of rules, to extract the named entities like people or locations names. The extracted tokens groups are replaced by a single token. This module has quite good results with a precision 80% and a recall around 60% depending on the language and the entity type. This evaluation has been done for English (5,000 texts), French (5,000 texts) and Spanish (50 texts) using a set of manually annotated texts.
The resulting text should then be used to do a syntactic analysis Again, this module was not ready at the time of CLEF and thus was not used. We will see in section 8 that we hope to improve our results in a future evaluation by using all the modules our system is designed to work with.
The last step of the linguistic analysis is the extraction of compound nouns. These compounds are important indicators for information extraction but also for a lot of other tasks. This module also relies on the rule-bases technology used to extract idiomatic expressions and named entities. Since no syntactic analysis is performed, every compound corresponding to a pattern (like Noun Preposition Noun) described in a rule is kept without any tense or genre agreement checking.
The results of the linguistic processing that we described above contain linguistic data of various levels that are used as well for the documents indexing (section 4) and for the queries processing (section 5). 4
The search engine described in section 6 relies on basic functions which give access to raw
information on the collection. E cient implementation of these basic functions allow an easy use of
the global system. We built inverted les (containing, for each term found in the collection of
documents, a list of all documents containing this term), using the Lemur toolkit (V2.01) [
The statistics of the index results are given for each corpus in table 1, indicating for each language the size of the corresponding corpus, the number of documents in the corpus, the total number of terms that where indexed (including single terms and compounds), the number of distinct single terms indexed, the number of distinct compounds indexed, the total size of the index les (as kept on disk), and the memory size that is used to load the index (includes term and document lists and lookups on the index les). Because indexes are too big to t in memory, all information is not loaded but stays in les. Looks up are used to hold the o set of each entry. fre eng ger spa
It can be can noted that the total size of indexes is larger than the original text (except for German). Our indexes are not very compact because of the great number of compound terms (which increases the size of vocabulary and add many entries in indexes). We have noted that we actually need 800 Mo to load the four indexes and run a request.
In future versions of our system, we will replace the Lemur toolkit with a more e cient implementation, allowing a smaller memory footprint to store the vocabulary, a transaction model to manage both read and write access (to index new les while executing retrieval request) and handling of Unicode text. 5 5.1
Each query is rst processed through the linguistic analyzer corresponding to the query language, as described in section 3. The three elds of the query (title, description, narrative) are kept for this analysis.
The result is a query composed of a list of elements that can be a lemma, associated with its part-of-speech (limited to nouns, verbs, and adjectives); a named entity, associated with its type; a compound, in a normalized form, associated with its part-of-speech4.
The query is then ltered using a stoplist containing meta-words (words used in the narrative to describe what are relevant documents, such as : \document", \relevant" etc.). These meta-words stoplists have been built on the basis of CLEF 2002 topics, from a rst selection using frequency information, and revised manually.
No deep semantic analysis has been performed on the narrative, to take into account, for instance, the negative descriptions of the topics (\documents that contain ... are not relevant "). Some negative descriptive elements have then been kept in the nal queries.
After this processing, the query is a list of indexing elements, in the original language of the topic. These elements are called the concepts of the query. 5.2
The list of query concepts is augmented with additional knowledge, using external resources (such as monolingual and bilingual reformulation dictionaries) and using the corpus to search as a reference (the indexes are used to lter out words inferred by the reformulation).
4The system still being under development, the compounds were not properly taken into account, especially in query expansion and translation, and were just used for monolingual search.
The reformulated query is then a list of the original query terms, called query concepts, and a list of inferred terms, called search terms. Each search term is linked to a query concept, and a weight is associated to the link. An example of query reformulation is presented in gure 3 at the end of this section. 5.2.1
Translation In order to query a corpus in a language di erent from the original query language, a translation of the query terms is performed, using bilingual dictionaries. Each term of the query is translated into several terms in target language. The translated words form the search terms of the reformulated query. The links between the search terms and the query concepts can also be weighted by a con dence value (between 0 and 1) indicating the con dence in the translation. In this rst version, all translations were assigned the same weight.
In the small multilingual task, the only language pair for which we did not have a bilingual dictionary is the Spanish/German pair. For this pair, we used a two-step translation, using a pivot language (terms are rst translated from topic language to the pivot language, and then from pivot language to target language). In this case, the con dence in the translation is the product of the con dences of the two successive translations. For the submitted runs, we used only one pivot language for the Spanish/German pair (chosen language was French), but a concurrent use of di erent pivot languages could also be used for this translation. 5.2.2
Monolingual reformulation A semantic expansion was also performed to increase the lexical variety of the query concepts, using monolingual reformulation dictionaries (containing mostly synonymy information).
In the runs we submitted, this semantic expansion was only performed for monolingual query expansion. In a more general approach for crosslingual retrieval, several combinations of multistep translation and monolingual expansion can be imagined. We plan to test several of them on the CLEF 2003 data. 5.2.3
Topical expansion
The semantic expansion described in the previous section is mainly based on synonyms. [
The selection of such words is based on a network of lexical cooccurrences. For French, the
only language for which we tested this kind of expansion, this network was built from a 39 million
word corpus made of 24 months from the Le Monde newspaper (see [
This network is used in a three-stage process that relies on a kind of bootstrapping. First, a set of words from the network that are strongly linked to the considered query are selected. The strength of this link is set by the number of words of the query the word from the network is linked to (3 words in our experiments). Most of these words, which are called expansion words, are topically close to the query but some of them also represent noise. The next stage aims at discarding this noise. It consists in selecting the words of the query that are the most representative of its topic. This selection is based on the words resulting from the rst stage: we assume that a query word is a signi cant one if it has contributed to the selection of a minimal number of expansion words (2 words in our experiments). The nal stage is identical to the rst one, except that the expansion is done from the selected words of the query and not from all its plain words.
5According to [
Moreover, the number of expansion words is arbitrarily set to 10 to avoid swamping the initial words of the query.
This topical expansion was applied to the 60 French topics of CLEF 2003. A set of expansion words was produced for 42 of them. This set was empty for the other ones, which means that it was not possible in these cases to build from the network of cooccurrences a signi cant representation of the topic of the query. As an example, the result of the topical expansion of the topic C164, Les condamnations pour tra c de drogue en Europe (European Drug Sentences), is the following list of words: famende, infraction, prison, delit, proces, penal, crime, juge, cocane, sursisg.
Une lettre piegee pour Arabella Kiesbauer. Trouvez des informations sur l'explosion d'une lettre piegee dans le studio de la presentatrice Arabella Kiesbauer de la cha^ne de television PRO 7. Le 9 juin 1995, une lettre piegee envoyee par des extremistes de droite et destinee a la presentarice noire Arabella Kiesbauer ...
linguistic processing lettre-N pieger-V Arabella-NP Kiesbauer-NP Arabella Kiesbauer-PER explosionN studio-N presentatrice-N cha^ne-N television-N professionnel-N informations sur l'explosion-N studio de la presentatrice-N cha^ne de television-N ... monolingual reformulation translation reformulation lettre-N pieger-V Arabella-NP Kiesbauer-NP Arabella Kiesbauer-PER explosion-N studio-N presentatrice-N cha^ne-N television-N ...
lettre-N correspondance-N courrier-N billet-N pli-N pieger-V Arabella-NP explosion-N manifestation-N expansion-N studio-N chambre-N appartement-N presentatrice-N cha^ne-N television-N lettre-N pieger-V Arabella-NP Kiesbauer-NP Arabella Kiesbauer-PER studio-N presentatrice-N cha^ne-N television-N ...
letter-N Arabella-NP Kiesbauer-NP Arabella ...-PER studio-N announceur-N newscaster-N newsreader-N presenter-N chain-N channel-N line-N program-N range-N ridge-N string-N television-N
The original topic is transformed, during the query processing, into four di erent queries, one for each language. The search is performed independently for each of theses queries on the index of the corresponding language. 1,000 documents are retrieved for each language. The 4,000 retrieved documents from the four corpora are then merged and sorted by their relevance to the topic. Only the rst 1,000 are then kept. We present in the following sections the search technique and the merging strategy. 6.1
For each expanded query, the search is performed by retrieving from the index of the corresponding language, for each search term of the query, the documents containing the term. A term pro le is then associated to each document: this pro le consists in a binary vector of size the number of search terms of the query, each component of which indicating the presence or absence of the search terms in the document. The frequency of the term in the document is not used: we consider that if a document contains relevant information with respect to a topic, then the document is relevant, event if the document contains other material that is not relevant to the topic (a visualization step can then select the relevant parts and show them to the user). However, further version of the search engine will also be able to take the frequency of the term in the document into account, to make the search engine more suitable to standard evaluation procedures.
Since we kept, in the expanded query, the links between the search terms and the query concepts, we can associate to each document a concept pro le, indicating the presence/absence of each query concept in the documents.
The retrieved documents are then classi ed, grouping in the same cluster the documents that share the same concept pro le. This classi cation is motivated by at least two reasons: it makes it easy to merge the results from di erent languages (see following section) and the visualization of the results is more e cient: the clustering of the results, and the association of a concept pro le to a cluster makes it easier for the user to search the results (a cluster corresponding to a non-relevant subset of query concepts can simply be ignored). 6.2
Given that a concept pro le is associated to each class, the merging strategy is quite straightforward: since the concepts are in the original query language, the concept pro les associated to the classes are comparable, and the classes having the same pro le are simply merged.
The classes are then sorted by their relevance to the query. For this purpose, we use the idf (inverse document frequency) weights of the terms, de ned for a term t by the formula idf (t) =
N log df (t) , where df (t) is the document frequency of the term (i.e. the number of documents containing the term) and N is the total number of documents in the corpus.
The rst idea is to use the idf weights of the terms in each language, and compute the weight of a concept by some combination of the weights of the terms derived from the concept, and then associate a weight to a concept pro le derived by the concepts it contains. However, in this case, the weights computed for the di erent languages are not comparable (idf of the terms depend of the corpora).
We decided to compute a crosslingual pseudo-idf weight of the concepts, using only the corpus composed of the 4000 documents kept as the result of the search. The idf weight of the concepts is computed on this corpus, using only information contained in the concept pro les of the classes and the size of the classes. A weight can then be associated to each concept pro le by computing the sum of the weights of the concepts present in the pro le.
The classes are then sorted by their weights: all documents in a class are given the weight of the class (the documents are not sorted inside the classes). The list of the rst 1000 documents from the best classes is then built and used for the evaluation.
We used this simple weighting procedure, but a lot of other procedures can be imagined. We plan to test several more sophisticated weighting schemes, using in particular the document frequency of the search terms and the con dence weight in the expansion associations.
n o ii s c e r P 1 0.8 0.6 0.4 0.2
As expected, our system exhibits its best results for monolingual retrieval. It shows that we still have work to do on our reformulation process and its resources. Concerning the resources, we see that the French-Spanish dictionary, used to reformulate between French and Spanish but also as a pivot language for Spanish to German and German to Spanish, needs particular attention as the number of relevant documents retrieved when using it is very low.
Concerning monolingual reformulation, we submitted two runs for French topics: one with only semantic expansion of queries and the other one with semantic and topical expansion of queries. The results for these two runs were globally very similar: in the rst case, 1543 relevant documents were returned with a R-precision of 0.1425 while in the second case, 1551 relevant documents were returned with a R-precision of 0.1438. However, the two sets of relevant documents are not identical since their intersection only contains 1305 documents. Topical expansion brings new relevant documents but also discards relevant documents brought by semantic expansion in the same proportion. More precisely, Table 2 shows that it favors monolingual retrieval while it has a negative impact on crosslingual retrieval.
Considering this observation, we tested if a combination of the two runs could lead to improve results. We adopted a basic strategy: the two lists of documents were interleaved in the decreasing order of their score; only one occurrence of each document was kept and the resulting list was cut at 1000 documents. 1730 relevant documents were returned with a R-precision of 0.1443. From the viewpoint of the number of relevant documents, the bene t is low (+179 documents, i.e. an increase of 11.6%) but not insigni cant. Moreover, most of the relevant documents that could be caught by our combination of runs were actually caught. However, from the viewpoint of R-precision, the bene t is not signi cant, which probably means that the rank of most of the new relevant documents is high. 8
Despite the numerically modest results of our system, our participation to CLEF'2003 is an encouragement for the future. Indeed, in a short period we implemented a tokenizer, a morphosyntactic analyzer, a named entities recognizer, an indexer and a search engine. All this work was done with a multilingual methodology that necessitated to gather several monolingual and bilingual resources. However, our system still requires more work both on the technology and the resources.
Some work has already been done: we have implemented a new method to store our dictionaries. A rst version of the morphosyntactic tagger works but will need to be replaced for a more speede cient one. Some other work have started: we are currently working on the syntactic analyzer that will extract nominal and verbal chunks and nd dependencies inside the chunks and between them. This last part will allow to nd compound nouns with better precision that our current method. These compound nouns are a fundamental part of our search algorithm and thus their current lack probably takes a great part in our current poor results. They will also permit to have a better multilingual search due to the noise introduced by a word by word translation. In the next year, we will also extend our languages coverage to three new languages and introduce monolingual and crosslingual relevance feedback.