This paper describes our approach to the 2006 Adhoc Monolingual Information Retrieval run for French. The goal of our experiment was to compare the performance of a proposed statistical stemmer with that of a rule-based stemmer, speci cally the French version of Porter's stemmer. The statistical stemming approach is based on lexicon clustering, using a novel string distance measure. We submitted three o cial runs, besides a baseline run that uses no stemming. The results show that stemming signi cantly improves retrieval performance (as expected) by about 9-10%, and the performance of the statistical stemmer is comparable with that of the rule-based stemmer.
We have recently been experimenting with languages that have not been studied much from the IR perspective. These languages are typically resource-poor, in the sense that few language resources or tools are available for them. As a speci c example, no comprehensive stemming algorithms are available for these languages. The stemmers that are available for more widely studied languages (e.g. English) usually make use of an extensive set of linguistic rules. Rule based stemmers for most resource-poor languages are either unavailable or lack comprehensive coverage. In earlier work, therefore, we have looked at the problem of stemming for such resource-poor languages, and proposed a stemming approach that is based on purely unsupervised clustering techniques.
Since the proposed approach does not assume any language-speci c information, we expect the approach to work for multiple languages. The motivation behind our experiments at CLEF 2006 was to test this hypothesis. Thus, we focused on mono-lingual retrieval for French (a language which we know nothing about), and tried our statistical stemming approach on French data.
We give a brief overview of the proposed statistical stemming algorithm in the next section. We outline our experimental setup in Section 3, and discuss the results of the runs that we submitted. 2 2.1
Distance functions map a pair of strings s and t to a real number r, where a smaller value of r indicates greater similarity between s and t. In the context of stemming, an appropriate distance measure would be one that assigns a low distance value to a pair of strings when they are morphologically similar, and assigns a high distance value to morphologically unrelated words. The languages that we have been experimenting with are primarily su xing in nature, i.e. words are usually in ected by the addition of su xes, and possible modi cations to the tail-end of the word. Thus, for these languages, two strings are likely to be morphologically related if they share a long matching pre x. Based on this intuition, we de ne a string distance measure D which rewards long matching pre xes, and penalizes an early mismatch.
Given two strings X = x0x1 : : : xn and Y = y0y1 : : : yn0 , we rst de ne a Boolean function pi (for penalty) as follows: pi = 0 if xi = yi 0 1 otherwise i min(n; n0) Thus, pi is 1 if there is a mismatch in the i-th position of X and Y . If X and Y are of unequal length, we pad the shorter string with null characters to make the string lengths equal.
Let the length of the strings be n + 1, and let m denote the position of the rst mismatch between X and Y (i.e. x0 = y0; x1 = y1; : : : ; xm 1 = ym 1; but xm 6= ym). We now de ne D as follows:
D(X; Y ) = n m + 1 m n X i=m 2 1 i m if m > 0;
Note that D does not consider any match once the rst mismatch occurs. The actual distance is obtained by multiplying the total penalty by a factor which is intended to reward a long matching pre x, and penalize signi cant mismatches. For example, for the pair hastronomer, astronomicallyi, m = 8; n = 13. Thus, D3 = 86 ( 210 + : : : + 2131 8 ) = 1:4766. 2.2
Using the distance function de ned above, we can cluster all the words in a document collection into groups. Each group, consisting of \similar" strings, is expected to represent an equivalence class consisting of morphological variants of a single root word. The words within a cluster can be stemmed to the `central' word in that cluster. Since the number of natural clusters are unknown apriori, partitive clustering algorithms like k-means are not suitable for our task. Also, the clusters are likely to be of non-convex nature. Graph-theoretic clustering algorithms appear to be the natural choice in this situation because of their ability to detect natural and non-convex clusters in the data.
Three variants of graph theoretic clustering are popular in literature, namely, single-linkage,
average-linkage, and complete-linkage [
We used the Smart [
For the remaining three runs, we used three variants of the statistical stemming method described above. Since our approach is based on hierarchical agglomerative clustering (as described above), the threshold value used in the clustering step is an important parameter of the method. Earlier experiments with English data have shown that 1.5 is a reasonable threshold value. We generated two retrieval runs by setting the threshold to 1.5 and 2.0 respectively (Cd61.5, Cd62.0).
For the third run, the stemmer was created based on a subset of the data. A lexicon was constructed using only the LeMonde section of the document collection, and this was then clustered as described above to determine the stem classes. Since the lexicon was smaller, the clustering step took less time for this run. The motivation behind this experiment was to study how performance is a ected when a subset of the lexicon is used to construct the stemmer in order to save computation time.
After the relevance judgments for this data set were distributed, we performed two additional experiments: rst, we tried setting the clustering threshold to 1.0; and secondly, we used the French version of Porter's stemmer2 in place of our statistical stemmer. The results obtained for all the o cial and uno cial runs are given below.
Run ID Cbaseline Cd61.0 Cd61.5 (o cial) Cd61.5 (obtained) Cd62.0 Cld61.5 Porter
T+D+N T+D+N T+D+N T+D+N T+D+N T+D+N T+D+N
MAP 0.3196 0.3465 (+8.4%) 0.3454 (+8.1%) 0.3509 (+9.8%) 0.3440 (+7.6%) 0.3342 (+4.6%) 0.3480 (+8.9%)
Rel. ret.
1,616 1,715 1,709 1,708 1,737 1,678 1,705
R-Precision 31.30% 34.85% 34.35% 34.26% 34.78% 32.81% 34.71%
The o cial results for the run labelled Cd61.5 do not agree with the evaluation gures that we obtained by using the distributed relevance judgment data. We therefore report both the o cial gures and the numbers that we obtained in Table 1.
The two most promising runs (Cd61.5 and Porter) were analyzed in greater detail. Paired t-tests show that stemming (using either strategy) results in signi cant improvements (at a 1% level of con dence) over the baseline (no stemming), but the di erences between the rule-based and statistical approaches are not statistically signi cant. Also, some loss in performance results when the stemmer is generated from a subset of the corpus (run Cld61.5).
This con rms our hypothesis that the proposed stemming approach, which does not assume any language-speci c information, will work for a variety of languages, provided the languages are primarily su xing in nature.
1http://www.unine.ch/info/clef/ 2downloaded from http://www.snowball.tartarus.org/algorithms/french/stemmer.html