This is the second year in a row we are participating in CLEF. Our aim is to test the performance of a statistical stemmer on various languages. Last year, we tried the stemmer on French; this year, we opted for Hungarian, Bulgarian and Czech. We were unable to complete the Bulgarian task, but submitted official runs for the adhoc monolingual Hungarian and Czech tasks. We find that, for both languages, the performance of the statistical stemmer is comparable to that of an available rule-based stemmer.
2.1
Given two strings X = x0x1 . . . xn and Y = y0y1 . . . yn , we first define a Boolean function pi (for penalty) as follows: pi = 0 if xi = yi 0 ≤ i ≤ min(n, n ) 1 otherwise 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 first mismatch between X and Y (i.e. x0 = y0, x1 = y1, . . . , xm−1 = ym−1, but xm = ym). We now define D as follows:
D(X, Y ) = n − m + 1 m ×
n i=m
1
2i−m
if m > 0,
∞ otherwise
(
Note that D does not consider any match once the first mismatch occurs. The actual distance is obtained by multiplying the total penalty by a factor which is intended to reward a long matching prefix, and penalize significant mismatches. For example, for the pair astronomer, astronomically , m = 8, n = 13. Thus, D3 = 68 × ( 210 + . . . + 213−8 ) = 1.4766. 1 2.2
Using the distance function defined 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. Each of these algorithms are of hierarchical (agglomerative or divisive) nature. In the agglomerative form, the cluster tree (often referred to as a dendogram) consists of individual data points as leaves. The nearest (or most similar) pair(s) of points are merged to form groups, which in turn are successively merged to form progressively larger groups of points. Clustering stops when the similarity between the pair of closest groups falls below a pre-determined threshold. Alternatively, a threshold can be set on the distance value; when the distance between the pair of nearest points exceeds the threshold, clustering stops.
The three algorithms mentioned above differ in the way similarity between the groups is defined. We choose the compete-linkage algorithm for our experiments. 3
We have mentioned earlier that YASS needs no linguistic input as it is a statistical stemmer. However, before running YASS on a new language we need to train it. For training we need a corpus of that language. In the following subsections, we will describe the training procedure of YASS in brief. 3.1
A lexicon is extracted from a given language corpus and clustered. The clustering threshold is learned from the training data. For Hungarian we used 2006 CLEF data for training. For Czech we did not get previous years data and thus we did not train our stemmer for Czech. 3.1.1 The same Hungarian corpus is used for the 2005, 2006, and 2007 tasks. The lexicon extracted from the corpus has 536678 surface words. The lexicon was clustered using various threshold settings, and the number of clusters versus threshold curve is shown in Figure 1. The step like regions around 0.8, 1.1, 1.5, 2.0 suggest that the number of clusters is stable around these threshold values. These values may thus be chosen as candidate thresholds for clustering.
After clustering the lexicon using these four threshold values, the lexicon size gets reduced to 225489, 169619, 130278, 76782 classes respectively. The stemmers thus prepared are used in four different runs.
The official topics for the Hungarian monolingual run at CLEF-2006 were topic numbers 301 to 325 and 351 to 375. We find that YASS performs best at the threshold 1.1. A mean average precision (MAP) versus threshold curve for all the runs are plotted and given in Table 1.
We tested these stemmers on CLEF queries 251 to 300. These queries were used in the CLEF 2005 monolingual Hungarian task. The highest MAP obtained here was again at θ = 1.1. We tried to compare our results with that of Tordai et al.[3], but could not compile the stemmer used by them. We have therefore reproduced the same experiments using YASS. Table 2 compares our results with those reported by Tordai et al. Tordai et. al report the results of 8 runs in their paper, out of which we listed the best three runs (4-Gram, Heavy minus hyphen and 5-Gram).
Run Name noStem(T+D+N) θ = 0.8(T+D+N) θ =1.1(T+D+N) θ =1.5(T+D+N) θ =2.0(T+D+N) noStem(T+D) θ =0.8(T+D) θ =1.1(T+D) θ =1.5(T+D) θ =2.0(T+D)
Heavy minus hyphen 4-Gram 5-Gram
MAP 0.2472 0.3211 0.3246 0.3246 0.3246 0.2170 0.3121 0.3241 0.3268 0.3048 TORDAI et. al
R-prec % Relevant Docs Retrieved 0.3048 83.1 0.338 83.6 0.3057 82.4 Unfortunately, we could not complete the training experiments described above, before the official submission. Thus for both the languages, we have submitted three runs, untrained.
In the first Hungarian run ISI.YASSTDHUN, we indexed only the <title> and <desc> fields of the queries. For the second run, ISI.YASSHUN we indexed the <title>, <desc>, and <narr> fields of the queries. In both cases the clustering threshold was set to 1.5. For the third run, ISI.ISIDWLDHSTEMGZ, we made use of the Hungarian stemmer available from the web 1.
The Czech runs are analogous: the first run uses only the <title> and <desc> fields; the second and third runs use the complete query. The second run makes use of an existing stemmer2 instead of YASS. The final run was a baseline run where no stemming was used.
After the relevance judgments for the data sets were distributed, we performed some additional experiments for both the languages. The results obtained for all the official and unofficial runs are given in Table 3 and 4. These results confirms our hypothesis that YASS will work for a variety of languages, provided the languages are primarily suffixing in nature.
Our ignorance of the languages prevents us from doing a detailed post-mortem on these results. For the benefit of those who understand Hungarian / Czech, we provide some examples of words and their roots (as obtained using YASS) in the following table. These words were selected from queries on which the stemmed run did significantly better than the unstemmed run. 1http://snowball.tartarus.org/algorithms/hungarian/stemmer.html 2http://members.unine.ch/jacques.savoy/clef/index.html [2] Gerard Salton, editor. The SMART Retrieval System—Experiments in Automatic Document
Retrieval. Prentice Hall Inc., Englewood Cliffs, NJ, 1971. [3] Anna Tordai and Maarten de Rijke. Four stemmers and a funeral: Stemming in hungarian at clef 2005. In CLEF, pages 179–186, 2005. % Rel Ret 72.22 72.88 66.84 % Rel Ret 71.59 81.11 84.19 84.96 83.42 65.53 76.83 79.91 81.22 75.08
CzeTDN.cze.d6-1.1.Lnu (T+D+N)
CzeTDN.cze.d6-1.5.Lnu (T+D+N) CzeTDN.cze.d6-2.0.Lnu (T+D+N)(Lnu) Hungarian politikusokro´l, politikai atomhullad´ekot megszu˝n´ese eln¨okjelo¨ltek, elno¨kjelo¨lt kira´lyno˝, kira´lysa´gbeli politi atomhullad´ek megsz eln¨okjelo¨l kir / kira´ly
Czech Kosteli˘covy´ch, Kosteli˘covi Kosteli˘c preziden˘st´ı, prezidenta, prezidentsk´eho preziden kandida´ti, kandida´ta kandida´t vesm´ırn´ı, vesm´ırny´ch, vesm´ıru vesm´ır turistech, turist´e turist