For our fourth participation in the CLEF evaluation campaigns, our first objective was to propose an effective and general stopword list and a light stemming procedure for the Portuguese language. Our second objective was to obtain a better picture of the relative merit of various search engines when processing documents in the Finnish and Russian languages. Finally, based on the Z-score method we suggested a data fusion strategy intended to improve monolingual searches in various European languages.
Table!1 (bottom part) also compares the number of relevant documents per request, with the mean always being greater than the median (e.g., for the English collection, the average number of relevant documents per query is 8.93 with the corresponding median being 4). These findings indicate that each collection contains numerous queries, yet only a rather small number of relevant items are found. For each collection, 50 queries were created. Relevant documents cannot however be found for each request and each language. For the French collection, Query #227 does not have any relevant items; for the English collection, these requests are #203, #220, #225, #227, #234, #243, #244 and #250; for the Finnish corpus: Queries #206, #227, #231, #240, #247; for the Russian corpus: Queries #204, #205, #206, #208, #217, #219, #222, #223, #229, #236, #240, #243, #246, #247, #248, #249, and for the Portuguese corpus: Queries #216, #220, #227, #240.
During the indexing process of our automatic runs, we retained only the following logical sections from the original documents: <TITLE>, <HEADLINE>, <TEXT>, <LEAD1>, <TX>, <LD>, <TI> and <ST>. From the topic descriptions we automatically removed certain phrases such as “Relevant document report …”, “Find documents …” or “Trouver des documents qui parlent …”.
In order to define general stopword lists, we first created a list of the top 200 most frequent words found in
the various languages, from which some words were removed (e.g., Roma, police, minister, president, Chirac).
From this list of very frequent words, we added articles, pronouns, prepositions, conjunctions or very frequently
occurring verb forms (e.g., to be, is, has, etc.). We created a new one for the Portuguese language, adding it to
last year's stopword lists
English French Size (in MB) 154 MB 244 MB # of documents 56,472 90,261 # of distinct terms 524,788 332,872 Number of distinct indexing terms / document Mean 136.45 127.10 Standard deviation 99.34 103.85 Median 116 92 Maximum 1,882 2,645 Minimum 5 1 Number of indexing terms / document Mean 200.72 176.47 Standard deviation 162.90 155.47 Median 162 125 Maximum 5,248 6,720 Minimum 6 1
Minimum
Once high-frequency words were removed, an indexing procedure generally applied a stemming algorithm in
an attempt to conflate word variants into the same stem or root. In developing this procedure for various
European languages
More sophisticated schemes were already proposed for the removal of derivational suffixes (e.g., “-ize”,
“ably”, “-ship” in the English language), as for example the stemmer developed by
Diacritic characters are usually not present in English collections (with certain exceptions, such as “résumé” or “cliché”). For the Finnish, Portuguese and Russian languages, these characters were replaced by their corresponding non-accentuated letter. For the Russian language, we converted and normalized the Cyrillic Unicode characters into the Latin alphabet (the Perl script is available at www.unine.ch/clef/).
Finally, most European languages manifest other morphological characteristics, with compound word
constructions being just one example (e.g., handgun, worldwide). In Finnish, we encounter similar
constructions as such as “rakkauskirje” (“rakkaus” + ”kirje” for love & letter) or “työviikko” (“työ” + ”viikko” for
work & week). Recently,
In order to obtain a broader view of the relative merit of various retrieval models, we first adopted a binary indexing scheme in which each document (or request) was represented by a set of keywords, without any weight. To measure the similarity between documents and requests, we computed the inner product (retrieval model denoted “doc=bnn, query=bnn” or “bnn-bnn”). In order to weight the presence of each indexing term in a document surrogate (or in a query), we would account for the term occurrence frequency (denoted tfij for indexing term tj in document Di, and the corresponding retrieval model is denoted: “doc=nnn, query=nnn” or “nnn-nnn”) or we might also account for their frequency in the collection (or more precisely the inverse document frequency, denoted by idfj). Moreover, we found that cosine normalization could prove beneficial, and in this case, each indexing weight could vary within the range of 0 to 1 (retrieval model notation: “ntc-ntc”). In Table 3 wij represents the indexing weight assigned to term tj in document Di, n to indicate the number of documents in the collection and nti the number of distinct indexing terms included in the representation of Di.
Other variants might also be created. For example, the tf component could be computed as 0.5 + 0.5 · [tf /
max tf in a document] (retrieval model denoted “doc=atn”). We might also consider that a term's presence in a
shorter document provides stronger evidence than it does in a longer document, leading to more complex IR
models; for example, the IR model denoted by “doc=Lnu”
wij = Inf1ij · Inf2ij = (1 - Prob1ij) · –log2[Prob2ij] Prob1ij = tfnij / (tfnij + 1)
with tfnij = tfij · log2[1 + ((C · mean dl) / li)] Prob2ij = [1 / (1+lj)] · [lj / (1+lj)]tfnij
with lj = tcj / n where wij indicates the indexing weight attached to term tj in document Di, li the number of indexing terms included in the representation of Di, tcj represents the number of occurrences of term tj in the collection and n the number of documents in the corpus. In our experiments, the constants b, k1, avdl, pivot, slope, C and mean dl were fixed according to values listed in Table!2.
English wi j = [ln(ln(tfi j) + 1) + 1] . idfj wi j = wi j = ((k1 + 1) ⋅ tf i j)
ln(tf i j) + 1 t  (ln( tf i k) +1) k =1
2 (K + tf i j) nnn atn npn Lnu ntc wi j = tfi j wi j = idfj . [0.5+ 0.5.tfi j / max tfi.] wi j = tfi j . ln[(n-dfj) / dfj] wi j = wi j = Ê1 + ln(tf i j) ˆ ËÁ ln(mean tf) + 1˜¯ (1 - slope) ⋅ pivot + slope ⋅ nt i
tf i j ⋅ idf j t  (tf i k ⋅idf k ) k =1 2 wi j = (ln(tfi j) + 1)⋅ idf j t  ((ln(tfi k ) + 1) ⋅ idf k )
2 k=1 wi j =
(ln(ln(tf i j) + 1) + 1) ⋅idf j (1 - slope) ⋅ pivot + slope ⋅ nt i
To evaluate our approaches, we used the SMART system as a test bed running on an Intel Pentium III/600 (memory: 1 GB, swap: 2 GB, disk: 6 x 35 GB). To measure the retrieval performance, we adopted the noninterpolated mean average precision (computed on the basis of 1,000 retrieved items per request by the TRECEVAL program). We indexed the English, French, and Portuguese collections using words as indexing units. The evaluation of our two probabilistic models and nine vector-space schemes are listed in Table 4 for the French and Portuguese corpus, and in Table 5 for the English collection.
In order to represent Finnish and Russian documents and queries, we considered the n-gram, and word-based indexing schemes. The resulting mean average precision for these various indexing approaches is shown in Table 5 (Finnish word-based indexing with decompounding), in Table 6 (Finnish based on the 5-gram or the 4gram indexing scheme) and in Table 7 (Russian corpus both word-based and 4-gram indexing). In these tables, we depicted in bold the best performance under given conditions (with the same indexing scheme and the same collection). From an analysis of these results, it can be seen that when the number of search terms increases (from T, TD to TDN), so usually does retrieval effectiveness (except for “bnn-bnn” or “nnn-nnn” IR models). When considering the five best retrieval schemes (namely, Prosit, Okapi, “Lnu-ltc”, “dtu-dtn” and “atn-ntc”), Tables 4 and 5 show that the improvement is around 29% when comparing title-only (or T) with TDN queries for the Portuguese collection, or of 22.1% with the English corpus or 16.6% for the French collection. When considering the Finnish language (Table 6 and right part of Table 5), we can see that 4-gram indexing scheme usually performs better than both 5-gram indexing (e.g., with the TD queries, 4-gram: mean MAP of the five best IR models is 0.5278 vs. 0.4729 with 5-gram indexing approach, a performance difference of 11.6% in favor of the 4-gram model) or better than the word-based indexing model (mean of 5 best IR models of 0.4692, with a performance difference of 12.5% in favor of the 4-gram indexing approach). There are of course exceptions to this rule (e.g., for TD queries and “ntc-ntc” model, the 5-gram indexing scheme results in slightly better performance than the 4-gram strategy, 0.4472 vs. 0.4466). As illustrated in Table 7, for the Russian language the wordbased indexing scheme provides better retrieval performance than do the 4-gram schemes (based on the five best search models, for TD queries the mean MAP of the five best retrieval is 0.3646 vs. 0.2774 for the 4-gram indexing scheme, a difference of 31.4%). For the Finnish language, we also indexed documents and the queries using words and “words” composed only of consonants. With this indexing scheme, the term “rakkaus” is indexed under both “rakkaus” and “rkks”. In this experiment, before removing all vowels, we applied our Finnish stemming stemmer. The mean average precision achieved by this indexing strategy was always lower than the corresponding word-based approach (see second column of Table 6 under the label “word & CC”). We must recognize that the Finnish language, with its rich inflectional morphology and its frequent irregularities, resulted in many difficulties for our simple stemming approach.
It was observed that pseudo-relevance feedback (blind-query expansion) seemed to be a useful technique for
enhancing retrieval effectiveness. In this study, we adopted Rocchio's approach
The results depicted in Table 8 (depicting our best results for the Okapi model) indicate that the optimal parameter setting seemed to be collection-dependant. Moreover, performance improvement also seemed to be collection dependant (or language dependant), with the Portuguese corpus showing an increase of 6% (from a mean average precision of 0.4835 to 0.5127), 5.2% for the English collection (from 0.5422 to 0.5704), 3.8% for the Russian collection (from 0.3800 to 0.3945), and 3.5% for the French corpus (from 0.4685 to 0.4851). For Russian Query Model \ # of queries Prosit doc=Okapi, query=npn doc=Lnu, query=ltc doc=dtu, query=dtn doc=atn, query=ntc doc=ltn, query=ntc doc=ntc, query=ntc doc=ltc, query=ltc doc=lnc, query=ltc doc=bnn, query=bnn doc=nnn, query=nnn the Finnish corpus and 4-gram indexing scheme, the query expansion approach did not improve the mean average precision, while with word-based indexing scheme, the best improvement was of 4.4% (0.4773 vs. 0.4984). Using the Prosit model (see Table 9), similar conclusions can be drawn. In this case however, the blind query expansion improves the mean average precision for all collections.
Using the same query expansion technique (Rocchio in this case), various IR models have resulted in varying degrees of evolution when increasing the number of terms to be included in the expanded query. To illustrate this phenomenon, Figure 1 depicts the evolution of the mean average precision of four different IR models (French corpus, and using the 3 best ranked documents). When we increased the number of terms to be included in the expanded query, the “dtu-dtn” model showed a small but constant improvement. With this IR model, each parameter setting produced a retrieval performance not that far from the best one. A similar evolution can be seen from the “Lnu-ltc” model, with a greater improvement however. When compared to the Okapi or Prosit models however, performance levels achieved were lower. For the Prosit model as well as for the Okapi scheme, the mean average precision increased, reached a maximum point and then subsequently fell slowly (with a greater variability for the Prosit model however). When a few terms were added to the original query however, the Prosit model usually performed at lower levels than did the Okapi. When this number of additional terms P A M
Prosit dtudtn
Okapi Lnu-ltc was increased however, the Prosit model tended to result in better mean average precision than did the Okapi scheme. However, when more than 100 terms are added, the Okapi model produced a better retrieval effectiveness than the Prosit model.
MAP after blind query-expansion (French corpus) 0 10 15 20 30 40 50 60 75 Number of terms added (from the 3 best ranked documents) 100
For the each language, we may assume that different indexing and search models would retrieve different
pertinent and non-relevant items and that combining different search models should improve retrieval
effectiveness. More precisely, when combining different indexing schemes we would expect to improve recall due to the
fact that different document representations may retrieve different pertinent items
In order to combine two or more indexing schemes, we evaluated various fusion operators, and their precise
descriptions are listed in Table 10. For example, the Sum RSV operator indicates that the combined document
score (or the final retrieval status value) is simply the sum of the retrieval status value (RSVk) of the
corresponding document Dk computed by each single indexing scheme
In addition to using these data fusion operators, we also considered the round-robin approach, whereby in turn we take one document from all individual lists and remove duplicates, keeping the most highly ranked instance. Finally we suggested merging the retrieved documents according to the Z-score, computed for each result list. Within this scheme, for the ith result list, we needed to compute the average of the RSVk (denoted Meani) and the standard deviation (denoted Stdevi). Based on these values, we would then normalize the retrieval status value for each document Dk provided by the ith result list by computing the deviation of RSVk with respect to the mean (Meani). In Table!10, Mini (Maxi) denotes the minimal (maximal) RSV value in the ith result list.
Sum RSV
SUM (ai . RSVk)
SUM (ai! .!(RSVk! / ! M a xi))
SUM [ai! .!((RSVk! - ! M i ni) / (Maxi! - ! M i ni))] ai!.![((R S Vk!-!Meani)!/!Stdevi) ! + ! d i] with di = [(Meani! - ! M i ni)!/!Stdevi]
Finally, in Table 12 we show the exact specifications of our 12 official monolingual runs. These experiments were based on different data fusion operators (mainly the Z-score and the round-robin schemes). Although we expected that combining the Okapi and the Prosit probabilistic models would provide good retrieval effectiveness, for some languages (e.g., French or Russian), we also considered other IR models (e.g., “dtu-dtn“ or “Lnu-ltc”). We also sent some runs with longer queries formulations (TDN) in order to increase the number of relevant documents to be found per language. In the “UniNEfi1” run, we removed all documents appearing in the year 1994 (in order to search all newspaper articles that described events occurring in the year 1995. However, 66 (over 413) relevant items have been published in year 1994).
In this fifth CLEF evaluation campaign, we proposed a general stopword list and stemming procedure for the Portuguese language. Currently it is not clear if a stemming procedure, such as the one we suggested whereby only inflectional suffixes were removed from nouns and adjectives, could result in better retrieval effectiveness than a stemming approach that takes both inflectional and derivational suffixes into account. In order to achieve better retrieval results, we used a data fusion approach based on the Z-score, where it was required that document (and query) representation be based on two or three indexing schemes.
Acknowledgments
The author would like to also thank the CLEF-2004 task organizers for their efforts in developing various European language test-collections. The author would also like to thank C. Buckley from SabIR for giving us the opportunity to use the SMART system. This research was supported by the Swiss National Science Foundation under Grant #21-66 742.01.