In our previous participation at CLEF in 2003 [3], we have tested the use of an association thesaurus to enhance query translation. We have only use the association thesaurus to add some new terms to the proposed translation terms. In our current participation, we have tried another use of such a thesaurus: we do not enlarge the query, but rather we use it to modify the weighing of a given translated query. Our basic idea is the selection of the best term translation using query context and association thesaurus from the corpus. Last year, we have neglected the study of the matching function and the influence of the weighting scheme. For this participation we will also focus on this aspect: we have test the Derivation From Randomness (DFR) against Okapi measure and some other classical IR weighting. We also promote the use of a surface-syntactic parser. All documents are first transform by the parser. The stemming is then proposed by the parser. Finnish is an agglutinative language, and using such an NL parsing enable to correctly split the glued words into separated correct indexing terms.
The paper present first the training experiments performed on 2003 collection in part 2. In part 3 we discuss the monolingual results. Then, in part 4, we present the technique used for bilingual results and present hypothesis based on the results.
In this part, we present some training we have achieved using monolingual corpus of CLEF 2003. We have mainly used the Finnish and French corpus. The purpose of this training is to select the best weighting scheme for the given CLEF document collection.
All experiments are grounded on the classic vector space model. Goal of experiment is to compare the probabilistic model of Okapi with Derivation From Randomness model, versus more classical weightings. This comparison will be done on two different languages.
Basically, the final matching process is achieved by a product between query vector and document matrix, which computes the Relevant Status Value (RSV) of all document against the query. For a query vector Q = (q i ) with a dimension of t term i ∈ [1..t], and a index document matrix of
.n], the RSV is computed by:
We keep this matching process for all tests, the changes are in the documents and query processing to select indexing terms, and in the weighting scheme. We recall here the scheme that is inspired by the SMART system. We suppose the previous processing steps have produced a matrix D = (d i,j ). Usually, the value d i,j is only the result of term t i counting in the document D j , called term frequency tf ij . Each weighting scheme can be decomposed in three steps: a local, a global and a normalization step. The local is related to only one vector. All these transformations are listed in table 1. For all measure we use the following symbols: weight of term i of query q
The global weighting is related to the matrix, and then it is a weighing which takes into account the relative importance of a term regarding the whole document collection. The most famous is the Inverse Document Frequency : Idf. The table 2 lists the global weighting we have tested. Okapi and DFR are not global weighting per se but rather complete weighting scheme themselves. In our X-IOTA system, they are computed at the same time than global weighting, and it is technically feasible to use them with a local and a final normalization. DFR is presented in the next part.
The Okapi measure described in [5,4], uses the length of the document, the function L(), and also a normalization by the average length of all documents in the corpus, the function A(). This length is related to the number of indexing terms in a document. The Okapi measure uses 2 constants values called k 1 and b. Finally, the last treatment is the normalization of the final vector.
n
A weighting scheme is composed by the combination of the local, global and final weighting. We represent a weighting scheme by 3 letters. For example, nnn is only the raw term frequency. The scheme bnn for both documents and queries leads to a sort of Boolean model where every term in the query is considered connected by a conjunction. In that case the RVS counts the terms intersection between documents and queries. The c normalization applied to both document and query vector leads to the computation of the cosine between these two vectors. This is the classical vector space model if we use the ltc scheme for document and queries. The scheme nOn for the documents, and npn with the queries, is the Okapi model, and the use of nRn for document and nnn for the queries is the DFR model. For these two models, constants have to be defined.
Notice that the c normalization of the queries, leads to divide the RSV for this query by i q 2 i . For each query this is a constant value which does not influence the relative order of answered document list. It follows that this normalization is useless for queries and should not be used. In the next section we briefly present the derivation from Randomness weighting that seems to give best results, and that we have used for all CLEF 2004 runs.
This weighting scheme has been proposed by Gianni Amati in [1] (with a small error in the definition of the value f * t,d ). Theoretical discussions about this approach can be found in [2]. Figure 4 sum up the results we obtain using this weighting scheme, on the CLEF2003 queries for training using the formula described in [1]. The formula is given by:
The value d * ij is a normalization by the length L(D j ) of the document D j regarding the average size of all document in the corpus : awr(D j ). A constant value c adjusts the effect of the document length in the weight.
For this participation of CLEF, we have test this weighting scheme against another set of other computation. We present these results on Finnish and French collection.
In these experiments, we have first tested the influence of stop words (SW) and stemming. We have not tested the influence of the surface syntactic parser, because the parsing was not available the time we have made these tests. The test performed here is done on the Finnish collection with 2003 queries. As the best results is of course, obtained with stop word and stemming, we have then tested the influence of the c constant in order to find out when we reach the optimum. The treatment we apply to both documents and queries is given by:
The first step is filtering the relevant tags from documents or queries. Then we transform XML special characters to their ISO counterpart. We delete all diacritic characters, and change to lower case. At this stage we still have special Finnish characters and accents. We eliminate common words using a list provided by Savoy1 and then suppress all accents from characters. We apply a Finnish stemmer also proposed by Savoy and modifies to accept XML input/output to produce the final vector. For the queries, we have used the following fields: FI-title FI-desc FI-narr. For documents only the text field has been used. When we examine DFR formula, one can see that when a term does not appear in document d, then only d i,j is null. Then d * i,j is also equal to zero. If we strictly apply the formula in that case, the weight of the term is still not null and is equal to the formula (4). For practical reason, we have replaced this residual value by zero. This approximation reduces the size of the inverse file, because we do not store null values in file. In fact we have applied the following weighting:
Table 5 show results for some variation in the constant c. We can notice that optimum value is about c = 0.84. This optimization gain 1.21 points referring neutral value c = 1. One can also notice that we obtain more documents in the first 1000 answer for c = 2, but the average precision is lower, which means that they are not well sorted.
The conclusion of the use of this weighting is that a good constant c value seems to be 0.83. In the rest of the test, we will use the approximated value c = 0.8.
For the Okapi weighting, we have use the same value as in [1], that is k 1 = 1.2, and b = 0.75. In table 9, we have also tested some other value for the French collection: it seems these values are on average good ones.
We have tested all combination of the following weight: bnn: This is the binary model. Terms presents are associated to the value 1, and 0 otherwise.
The cosine is the finale normalization. When both used in document and queries, it ensure true vector space model matching, ie. only angle between query et document vector is used. This weighting suppose a log distribution of frequency.
ntc: This is the classical tf*idf measure. We used with queries, the idf is taken from the document collection, not the query collection.
The same classical measure using log on term frequency.
The log tf*idf without the cosine normalization.
atn: Normalization with the local maximum term frequency is used with idf.
The double natural log is used in place of the simple one in ltn.
npn: It is the idf variant use for the Okapi system.
nRn: This is the name for Derivation from randomness.
nOn: This is the name for the Okapi probabilistic weighting.
Results are sum up in the table 6. We notice that the derivation from randomness model is very stable again the query weighting and that it has the best results in the majority of query weighting. We have the decided to use it for CLEF 2004
For training, we have used the French corpus of CLEF 2003. We have used our own stemmer, and our own list for removal of common French terms. In this collection, there are 3 sets of documents. For each collection we have selected the following fields: lemonde94 TITLE TEXT, and TI KW LD TX ST for sda 94 and 95. For the queries, we have selected the fields FR-title FR-desc FR-narr. We have tested the same combination of weighting schemes as the one tested in the Finnish collection. The results are in the Finally, we have taken the best weighting query scheme for the Okapi model (nOn) and we have computed some variation of the two constant k 1 and b. The results are in the table 9. The best values are obtained with the couple (1, 0.75) which confirm the choice usually taken for this measure.
In this language, we also demonstrate the stability of the DFR measure (nRn) which performs better than other query weightings, except with binary queries (bnn). We obtain the best average precision with the inverse document frequency (ntn).
We have not performed any special treatments for the queries, like removing terms that are not related to the theme (ex: document, retrieved, etc). The results show that a natural language analysis of the query to remove these empty words should improve the results.
In this part, we comment the results we have obtained at CLEF 2004. We have participated to the monolingual track on French, Finnish and Russian. As we promote the use of syntactic parsing, we 9: k 1 and b variation for nOn ntn have submitted mono lingual run all using surface syntactic parsing. Because of time constrains, we have not trained the system with the parsed collection. So we can only compare with CLEF 2003 without natural parsing.
After each parsing, we have transformed the output into a common XML simplified format. One of the main interests in using a natural language parser is the correct normalization of words, the correct detection of compound nouns and correct filtering using lexical categories. For all run, we have choose the derivation from randomness weighting with the constant value fixed to c = 0.8, according to the training experiments. No special treatments are done on queries.
These characteristics are important for language which has a morphological derivation like French and Finnish. For all language, we have filtered only nouns, proper noun, verb and adjective. For French, we have used the XIP system from XEROX. After this filtering, we still remove some terms using a stop list, and used also a French stemming. The French queries are weighted using ntn. Hence we only modify the weight according to the inverse document frequency. This computation is of course performed using document corpus. The average precision is 44%, which is not an absolute good result. This value is a little lower than our training.
When we examine more closely the results, we discover a big discrepancy between queries. Figure 1, shows the histogram repartition of the 29 queries (from 201 to 250 without 227). There are a lot of query that are either very low precision level (18 queries under 20%) of very high (13 upper 80%).
For the Finnish monolingual run, we obtain an average prevision of 53%, witch is better than the results obtained on CLEF 2003. The histogram in figure 2 shows that 10 query are above 90%, in fact exactly 5 queries reach 100% of precision.
We have use also a surface syntactic parser for the Russian collection, but we cannot compare yet with a more simple raw term indexing because we do not have a Russian stemmer and stop list. The average result of 35% is the lowest for all three languages. Query precision repartition in figure 3 shows that a lot of query (12) have very low precision (under 10%).
The conclusion that we draw is the good behavior of DFR weighting, and probably the benefit of using a surface syntactic parsing on Finnish. In this language, the parser is able to "unglue" terms and so could achieve better results. We cannot investigate more our results, because we should compare on the same collection the use of the syntactic surface parsing.
Bilingual results are obtained by translating the topics using general dictionaries built by compiling several bilingual dictionaries available online (see section 4.1). Then, we experimented 2 methods of translation (see sections 4.2). Both methods take the topic vectors as input and outputs a new translated topic vector.
We compiled 6 bilingual translation dictionaries (see figure 4) using several resources available in house or from Internet. Each resulting dictionary associates a word form to a set of translations and is stored as an XML file (see figure 5). These dictionaries where compiled from the following sources:
• the Bilingual French-English dictionary from the university of Rennes 1, freely available at http://sun-recomgen.med.univ-rennes1.fr/Dico/,
• the FeM dictionary (French English Malay), freely accessible at http://www-clips.imag. fr/cgi-bin/geta/fem/fem.pl?lang=fr,
• the French English dictionary available for the participants on the CLEF web site,
• dictionary entries from the Logos website2 ,
• the "engrus" English Russian dictionary available on many web sites3 .
As for the French-Russian, French-Finnish and English-Finnish dictionaries, the only available online resource we used is the Logos web site. As it is the only online service we used (other data was available off-line), we chose to only extract entries that were present in the topics to be translated in order to avoid high loads on a public web site. This explains the very small size of these dictionaries.
As French and English were our topic languages of choices, we also reverted the merged French-English dictionaries.
For each bilingual task we participated in, we propose 2 methods of translation. Both methods take the topic vectors as input and outputs a new translated topic vector.
The first method substitutes each term by all of its available translations. The weight associated to each translation is equal to the weight of the original term divided by the number of available translation (see figure 6).
As one may see in figure 5, many different translations may be found for a single term. Hence, we tried to develop a strategy to give more importance to the "correct" translation(s). For this, we tried to take some context into account, without changing anything to the available lexical resource.
For this, we needed contextual information in each language. Hence, we automatically built an association thesaurus (as exposed in [3]) for each language from the available monolingual documents (see figure 7).
Each association thesaurus is as a graph linking terms. Each arc in the graph links 2 terms that "regularly"4 appear in the same context. For this experiment, 2 terms are said to be in the same context when they appear in the same document.
For our experiment, we assume that terms that are close to each others share some common semantic. We also assume that their "correct" translations should also share the same semantic. Hence, we used these association thesaurus to know if terms and translations share some semantics. Hence, we chose to associate each translations t i,j of a term c j with a weight w ti,j depending on its distance (d ti,j ) with the translated context. The distance of a translation to the translated context is given by formula 5.
where t k,l ∈ T l and T l is the set of translation of the term c l and d(t i,j , t k,l ) is the minimal distance in the target thesaurus between t i,j and t k,l (5) w ti,j = w j /d i,j if d i,j = 0 w j /|T j | if d i,j = 0 where w j is the weight of the source term c j in the source vector (6)
Figure 8 shows a sample resulting translated vector. One may notice the higher weight of the selected translations (e.g. interest → ИНТЕРЕС).
CLIPS results on the bilingual tasks are rather disappointing, with interpolated recall-precision averages at 0.00 dropping from 57.68% (Monolingual Russian) to 17.1% with simple topic translation (Bilingual English-Russian: CLIPSENRU1) and even to 8.59% with filtered topic translation (CLIPSENRU2).
The main reason for this drop is certainly due to the lack of wide coverage bilingual lexical resources. The dictionaries we used were very small and did not provide translations for many terms of the topics. This is especially true for French to Russian and Finnish lexical resources where 60% to 70% of the source terms are not translated. However, English to Russian lexicon was a little better, and about 18% of the terms remain without translation. Figure 7: Size of the association thesaurii However, this does not explain the drop in interpolated recall-precision averages when filtering the translations through the association thesaurii, as it does not change the set of translations, but only the weight of those translations. Moreover, when manually evaluating the weighted translation, one usually agree with the translation that are chosen.
We think that 2 factors explains theses drops:
• First, in the simple topic translation method, the weight of each translation is divided by the number of translations for the source term. This lowers the relative importance of terms that bear many translations, (which is usually the case of general nouns or support verbs).
• Second, when raising the weight of "correct" translations by way of the association thesaurii, we also raise the weight of such general terms. Hence, we give more importance to terms that do not bear any thematic closeness with the requested documents (and this is especially the case with CLEF topics that are instructions usually containing "find documents reporting on. . . " or "find information on. . . ").
All run are performed on the collection parsed using a syntactic surface parsing. Best monolingual results are obtained for the Finnish collection, probably because of the correct word splitting. We have to redo the tests with no analyzer to have a strong conclusion on its use in an IR context/ Bilingual results are disappointing but they are partly explained by the difficulty in finding wide coverage lexical resources for languages in which we previously had no experience whatsoever.
The filtering of translations through association thesaurii is rather interesting, even if we did not have enough time to use it appropriately. This technique may also be interesting in translation selection tasks or, with adaptation, on lexical disambiguation tasks. It's main interest in such tasks comes from the fact that it does not require any special training data (like parallel documents or manually disambiguated corpora) as association thesaurii may be computed automatically from the corpus. Hence such technique may easily bring some result in those tasks in any language, provided that monolingual data is available as well as an automatic process to lemmatize such corpora.