In Information Retrieval (IR), stemming is used to reduce variant word forms to common root. The assumption is that if two words have the same root, then they represent the same concept. Hence stemming permits a IR system to match query and document terms which are related to a same meaning but which can appear in different morphological variants. In this paper we will report our participation in CLEF 2002 Italian monolingual task, whose aim was to evaluate a statistical stemming algorithm based on link analysis. Considering that a word is formed by a prefix (stem) and a suffix, the key idea is that the interlinked prefixes and suffixes form a community of substrings. Hence discovering these communities means searching for the best word splits which give the best word stems. The results show that stemming improves the IR effectiveness. They also show that effectiveness level of our algorithm, which does not incorporate any heuristics nor linguistic knowledge, is comparable to that of an algorithm based on a-priori linguistic knowledge. This is an encouraging result, particularly in a multi-lingual context.
Stemming is used to reduce variant word forms to common root. The assumption is that if two words have the same root, then they represent the same concept. Hence stemming permits a IR system to match query and document terms which are related to a same meaning but which can appear in different morphological variants.
The effectiveness of stemming is a debated issue, and there are different results and conclusions. If
effectiveness is measured by the traditional precision and recall measures, it seems that for a language with
a relatively simple morphology, like English, stemming influences the overall performance little [
To design a stemming algorithm, it is possible to follow a linguistic approach, using prior knowledge of the morphology of the specific language, or a statistical approach using some methods based on statistical principles to infer from the corpus of documents the word formation rules in the language studied. The former implies manual labor which has to be done by experts in linguistics – as matter of the fact, it is necessary to formalize the word formation rules, the latter being hard work, especially for those languages whose morphology is complex. Stemming algorithms based on statistical methods ensure no costs for inserting new languages on the system, and this is an advantage that becomes crucial especially for multilingual IR systems. 3
We will consider a special case of stemming, which belongs to the category known as affix removal
stemming [
x arg max P r(w ∈ W | x ∈ S)P r(x ∈ S) x P r(w ∈ W ) (1) (2) where (2) is obtained applying the Bayes’ theorem which lets us swap the order of dependence between events. We can ignore the denominator, which is the same for all splits of w. P r(w ∈ W | x ∈ S) is the probability of observing w given that the stem x has been observed. A reasonable estimation of that probability would be the reciprocal of the number of words beginning by that stem if the stems were known. However note that the stems are unknown – indeed stem detection is the target of this method – and the number of words beginning by a stem cannot be computed. Therefore we estimated that probability by the reciprocal of the number of words beginning by that prefix. As regards P r(x ∈ S) we estimated this probability using an algorithm that discloses the mutual relationship between stems and derivations in forming the words of the collection.
The rationale of using mutual reinforcement is based on the idea that stems extracted from W are those substrings that: – are very frequent, and – form words together with very frequent suffixes.
This means that very frequent prefixes are candidate to be stems, but they are discarded if they are not followed by very frequent suffixes; for example, all initials are very frequent prefixes but they are unlikely stems because the corresponding suffixes are rather rare, if not unique – the same holds for suffixes corresponding to ending vowels or consonants. Thus, there are prefixes being less frequent than initials, but followed by frequent suffixes, yet less frequent than ending characters: these suffixes and prefixes correspond to candidate correct word splits and we label them as “good”. The key idea is that interlinked good prefixes and suffixes form a community of substrings whose links correspond to words, i.e. to splits. Discovering these communities is like searching for the best splits.
To compute the best split, we used the quite well-known algorithm called HITS reported in [
Using a graphical notation, the set of prefixes and suffixes can be written as a graph g such that nodes are substrings and an edge occurs between nodes x, y if w = xy is a word in W . By definition of g, no vertex is isolated. As an example, let us consider the following toy set of words: W ={aba, abb, baa}; splitting these into all the possible prefixes and suffixes produces a graph, reported in Figure 3a. (a) substring a aa ab b ba bb
Let us define P (y) = {x : ∃w, w = xy} and S(x) = {y : ∃w, w = xy} that are, respectively, the set of all prefixes of a given suffix y and the set of all suffixes of a given prefix x. If px and sx indicate, respectively, the prefix score and the suffix score, the criteria can be expressed as: px =
X y∈S(x) sy sy =
X x∈P (y) px (3) under the assumption that scores are expressed as sums of scores and splits are equally weighed.
The method of mutual reinforcement has been formalized through the HITS iterative algorithm. Here we map HITS in our study context, as follows: Compute suffix scores and prefix scores from W V : the set of substrings extracted from all the words in W P (y): the set of all prefixes of a given suffix y S(x): the set of all suffixes of a given prefix x N : the number of all substrings in V n: the number of iterations 1: the vector (1, ..., 1) ∈ R|V | 0: the vector (0, ..., 0) ∈ R|V | s(k): suffix score vector at step k p(k): prefix score vector at step k s(0) = 1 p(0) = 1 for each iteration k = 1, ..., n s(k) = 0 p(k) = 0 for each y ∈ V for each x ∈ V end.
s(yk) = Px∈P (y) p(xk−1); p(xk) = Py∈S(x) s(yk); normalize p(k) and s(k) so that 1 = Px p(xk) = Py s(yk) Using the matrix notation, the graph g can be described with a |V | × |V | matrix M such that mij = (1 if prefix i and suffix j form a word
0 otherwise
As explained in [
As explained previously, we argue that the probability that x is a stem, can be estimated with the
prefix score px just calculated. The underlying assumption is that the scores can be seen as probabilities,
and, in effect, it has been proved in a recent work that HITS scores can be considered as a stationary
distribution of a random walk [
The aim of CLEF 2002 experiments is to compare the retrieval effectiveness of the link analysis-based algorithm illustrated in the previous Section with that of an algorithm based on a-priori linguistic knowledge, because the hypothesis is that a language-independent algorithm, such as the one we propose, might effectively replace one developed on the basis of manually coded derivational rules. Before comparing the algorithms, we assessed the impact of both stemming algorithms by comparing their effectiveness with that reached without any stemmer. In fact, we did want to test if the system performance is not word prefix
suffix
baa
baa
aba
aba
abb
abb
b
ba
a
ab
a
ab
aa
a
ba
a
bb
b
words beginning
by prefix
1
1
2
2
2
2
significantly hurt by the application of stemming, as hypothesized in [
As regards the realization of the statistical stemming algorithm, we built a suite of tools, called Stemming Program for Language Independent Tasks (SPLIT), which implements the link-based algorithm and chooses the best stem, according to the probabilistic criterion described in Section 3. From the vocabulary of the Italian CLEF sub-collection, SPLIT spawns a 2,277,297-node and 1,215,326-edge graph, which is processed to compute prefix and suffix scores – SPLIT took 2.5 hours for 100 iterations on a personal computer equipped with Linux, an 800 MHz Intel CPU and 256MB RAM. 4.2
We tested four different stemming algorithms:
1. NoStem: No stemming algorithm was applied.
2. Porter-like: We used the stemming algorithm for the Italian language, which is freely available
in the Snowball Web Site [
We carried out a macro evaluation by averaging the results over all the queries of the test collection. Table 2 shows a summary of the figures related to the macro analysis of the stemming algorithm for 2002 topics, while table 3 reports 2001 data.
Run ID PDDN PDDP PDDS2PL PDDS2PL3
Algorithm NoStem Porter-like SPLIT SPLIT-L3
Note that both for 2001 and 2002 topics, all the considered stemming algorithms improve recall, since the number of retrieved relevant documents is larger than the number of retrieved relevant documents observed in the case of retrieval without any stemmer; the increase has been observed for all the stemming algorithms. As regards the precision, while for 2002 topics, stemming does not hurt the overall performances of the system, for 2001 data, stemming even increases the precision, and then the overall performance is higher thanks to the application of stemming.
Figure 2 shows the Averaged Recall-Precision curve at different levels of recall and Figure 3 illustrates the Recall-Precision curve at given document cutoff values, both for 2002 and 2001 topic sets. As regards Topic 2002 − Interpolated recal vs average precision
Topic 2001 − Interpolated recal vs average precision 80% 70% 60% iin50% o s c e reP40% g a r e v A30% 20% 10% 80% 70% 60% iin50% o s c e reP40% g a r e v A30% 20% 10% NoStem Porter−like SPLIT SPLIT−L3
NoStem Porter−like SPLIT SPLIT−L3 the use of link-based stemming algorithms, it is worth noting that SPLIT can attain levels of effectiveness being comparable to one based on linguistic knowledge. This is surprising if you know that SPLIT was 40% 30% n o iir s c e P 20% 10% 05%docs 10 docs 15 docs 20 docs 30 docs 100 docs 200 docs 500 docs 1000 docs
Retrieved documents (a) 2002 Topics 05%docs 10 docs 15 docs 20 docs 30 docs 100 docs 200 docs 500 docs 1000 docs
Retrieved documents (b) 2001 Topics built without any sophisticated extension to HITS and that neither heuristics nor linguistic knowledge was used to improve effectiveness. It should also be considered as a good result, if you consider that it has also been obtained for the Italian language, which is morphologically more complex than English. 5
The objective of this research was to investigate a stemming algorithm based on link analysis procedures. The idea has been that prefixes and suffixes, that are stems and derivations, form communities once extracted from words. We tested this hypothesis by comparing the retrieval effectiveness of SPLIT, a link analysis based algorithm derived from HITS, with a linguistic knowledge based algorithm, on a quite morphologically complex language as it is the Italian language.
The results are encouraging because effectiveness level of SPLIT is comparable to that developed by Porter. The results should be considered even better since SPLIT does not incorporate any heuristics nor linguistic knowledge. Moreover, stemming, and then SPLIT, showed to improve effectiveness with respects to not using any stemmer.
We are carrying out further analysis at a micro level to understand the conditions under which SPLIT performs better or worse compared to other algorithms. Further work is in progress to improve the probabilistic decision criterion and to insert linguistic knowledge directly in the link-based model by thus weighting links among prefixes and suffixes with a probabilistic function which could capture available information on the language, such as, for example, the minimum length of a stem. Finally, further experimental work is in progress with other languages.