Stemming, an approximation to morphological analysis, is a commonly used technique to improve performance in information retrieval systems. In the MorphoChallenge 2007 evaluation we applied a simple zero-knowledge technique that is based on frequency counts rather than machine learning. Our method is based on substituting a single xed-length substring for each word that appears in documents or queries. We hope to discover whether this method, which has been used in previous IR evaluations with good e ect, will be as e ective for the information retrieval task as the unsupervised methods used by other participants. It should be emphasized that out submission was not a credible attempt to learn morphology and thus is not expected to perform well in the morphology induction task.
2.1
Commonly IR systems adopt a bag-of-words model where words in a document are treated as the basic indexing units. Often the tokenization process additionally transforms words into stems or root forms so that words that di er only by in ectional or perhaps even derivational morphology are treated as the same. With character n-gram indexing, words are not considered the basic indexing unit; instead, character substrings are used, typically of a xed length. For example, for the text `Johns Hopkins' the character 4-grams generated are: #joh, john, ohns, hns#, ns#h, s#ho, #hop, hopk, opki, pkin, kins, and ins# 1. While short n-grams can have higher individual ambiguity (e.g., ins# could come from the words ns, skins, and dolphins, among others), this collection of twelve n-grams is not very likely to occur unless the phrase `Johns Hopkins' was present in the original text. Storing 12 entries in an inverted le instead of just two (one for each word) is why n-gram indexing su ers from performance issues. However, this expense also enables exible matching. Web log analysis shows that roughly 30% of users mistakenly2 type \john hopkins" and yet 8 out of the 12 n-grams still match this string.
N-grams have been used in many Asian languages because of inherent di culties with word segmentation; however they have not been very popular in Western languages. Damashek [1] promoted their use at early TREC evaluations, but his claims generated controversy and were received with skepticism. McNamee and May eld [3] overwhelmingly demonstrated that n-grams are e ective in European languages and presented compelling evidence using eight languages from the CLEF 2002 evaluation. They found that lengths of n=4 or n=5 worked about equally well and signi cantly outperformed unnormalized words. 2.2
In their article on n-gram indexing, McNamee and May eld left unaddressed the question of whether n-grams achieved higher performance over stemmed words. But in other work they did a direct comparison of n-grams and stems and found that 4-grams performed on par with Porter's SNOWBALL stemmer and in three of eight CLEF 2002 languages performed signi cantly better. The tendency was that n-grams held an advantage in the more morphologically complex languages (i.e., Finnish, Swedish, German). Still, the question remained as to whether the advantage in accuracy was worth the degradation in run-time performance.
The key factor in increased disk space and run-times is the fact that each word generates multiple n-grams. If there were only some way to prune away most of the n-grams and yet preserve enough of the bene ts of n-grams to still confer an advantage. The selection method for each word must be e cient as this is an operation that will be performed on every word in the corpus { billions of operations will be required. May eld and McNamee [2] introduced n-gram stemming where a single n-gram would be used to represent each word. The selected n-gram was chosen based on the relative document frequencies of the n-grams spanning the word under consideration. The least frequent n-gram was used; this makes sense if the hypothesis that frequent n-grams are more likely to be part of the morphologically variable part of a word, not the root form. As an example, consider the words jugglers and juggling. Using statistics from 110282 newspaper articles the constituent n-grams of each word are shown in Table 1. It can be clearly seen that the rarest n-gram `jugg' occurs much less often than the su xes `ers ' and `ing '. And both words would get replaced with `jugg' which intuitively seems like a good choice.
Other methods for selecting a single n-gram or a small number of n-grams are possible. For example, the examples we have given use n=4, but since three runs were permitted in this year's evaluation we also created lists using n=3 and n=5. One could consider variants such as using two disjoint 3-grams or never ending an n-gram on a vowel, or any number of other permutations that might have linguistic merit.
1The # symbol is used to denote whitespace. 2See http://en.wikipedia.org/wiki/Johns Hopkins for an explanation of this unusual given name.
For Task 1 we simply reported, for each word, the 3, 4, or 5-gram with lowest collection frequency based on the training data provided for each language. We did not predict any attributes such as +PL or +3 PER. Since we did not set out to truly learn morphological rules, we are not really surprised by our results. Our runs had lower F-score than all other runs in each of the four languages. We note that our runs with 5-grams did have the highest precision in each of the four languages with with very low recall. 3.2
We have experimented with n-gram morphemes in previous CLEF datasets. In Table 2 we present results in ve languages using data from CLEF 2002 (for English, German, and Finnish) and CLEF 2005 (Bulgarian and Hungarian) that illustrate the relative e ectiveness of n-gram indexing and n-gram analysis compared to processing unnormalized words. We report performance using mean average precision. Comparisons should not be made across languages in Table 2, but the results are meaningful for the di erent conditions in each language.
N-gram stemming usually helps, though performance was slightly worse for English. The largest gains are in the more complex languages and n-gram stemming does not perform as well as the use of ordinary n-gram indexing where the set of all n-grams is used instead of a select one. 3.3
In this competition the organizers took lists of normalized word forms and replaced words in the CLEF source documents with a canonical form. The test sets used were: CLEF-2005 (English), CLEF-2004 (Finnish), and CLEF-2003 (German). The Lemur retrieval engine was used with TF/IDF or Okapi BM25 term weighting. No automated relevance feedback was performed on queries.
In Table 3 we compare our performance using 4-stems and 5-stems to several reference conditions. These gures are all based on the withnew condition, the scenario where all words in the IR collection were transformed, and with TF/IDF weighting.
The 4-Stems do not score as high as the 5-Stems. The 5-Stems outperform the dummy condition and the gold standard analysis in two out of three languages. The Morfessor baseline roundly beats 5-Stems in Finnish and German, though the two methods are comparable in English. The results in Table 2, using CLEF-2002 data (which was not used in MorphoChallenge 2007), also show little di erence between the dummy condition (labeled 'words' in Table 2) and n-gram morphemes. However, in Table 2, the use of all n-grams that span a word yields sizable improvements. This is also the case on the test sets used in this year's competition.
In Table 4 we list results obtained using the JHU/APL HAIRCUT retrieval engine in the CLEF evaluations in 2003-2005. These runs also made use of relevance feedback, and are not directly comparable to the results in Table 3. Nonetheless these gures suggest the use of all n-grams yields better performance compared to a single selected one. 4
We set out to participate in the information retrieval evaluation, not the morphology induction task. Our method for producing morphemes is unorthodox, but we believe that it is suitable for use in information retrieval. We provided results based on our own information retrieval experiments that support this claim, and that o er a means to obtain improvement with n-grams without a run-time penalty. The technique is also well motivated when working in a language with no available morphological toolkit. The results from the Task 2 evaluation suggest that n-gram morphemes perform better than unnormalized words and similarly to the gold standard analysis, but not as well as the Morfessor algorithm. [1] Marc Damashek. Gauging simularity with n-grams: Language-independent categororization of text. Science, 267:843{848, 10 February 1995. [2] James May eld and Paul McNamee. Single n-gram stemming. In SIGIR, pages 415{416, 2003. [3] Paul McNamee and James May eld. Character N-gram tokenization for european language text retrieval. Inf. Retr, 7(1-2):73{97, 2004. #! / usr / b i n / p e r l # Take corpus o f t r a i n i n g data and an i n p u t w o r d l i s t , compute n gram f r e q u e n c i e s , # and o u t p u t transformed w o r d l i s t t h a t reduce wordforms t o t h e l e a s t f r e q u e n t n gram . # Usage : CreateStems corpus . t x t w o r d l i s t . t x t package main ; my %cnt = ( ) ; my $nlen = 5 ; my $ c o r p f i l e = $ARGV [ 0 ] ; my $ w o r d f i l e = $ARGV [ 1 ] ; open FH, "<$ c o r p f i l e " ; while (<FH>) f $ l i n e = $ ; chomp( $ l i n e ) ; next i f ( $ l i n e =~ /^0n t / ) ; $ l i n e =~ s /nd+nt / / ; # remove l e a d i n g junk $ l i n e =~ s /n s+/ /g ; # r e p l a c e space w i t h u n d e r s c o r e s $ l i n e = " " . $ l i n e . " " ; # padding # s p l i t l i n e i n t o n grams my $ l e n l i m = length ( $ l i n e ) $nlen + 1 ; for (my $ i =0; $i <$ l e n l i m ; $ i++) f my $tok = substr ( $ l i n e , $i , $nlen ) ; # a d j u s t counts f o r each o b s e r v e d n gram $cnt f $tokg++; g close FH; open FH, "<$ w o r d f i l e " ; while (<FH>) f $ l i n e = $ ; chomp( $ l i n e ) ; $ l i n e =~ s /nd+ns +//; # remove l e a d i n g junk ( i . e . , t h e f r e q u e n c y ) , keep t h e word my $origword = $ l i n e ; $ l i n e =~ s /n s+/ /g ; # r e p l a c e space w i t h u n d e r s c o r e s $ l i n e = " " . $ l i n e . " " ; # s p l i t l i n e ( r e a l l y word ) i n t o n grams my $ l e n l i m = length ( $ l i n e ) $nlen + 1 ; my $ b e s t t o k = "" ; my $ l o w e s t f r e q = 100000000; for (my $ i =0; $i <$ l e n l i m ; $ i++) f my $tok = substr ( $ l i n e , $i , $nlen ) ; i f ( exists ( $cnt f $tok g) && $cnt f $tok g < $ l o w e s t f r e q ) f $ b e s t t o k = $tok ; $ l o w e s t f r e q = $cnt f $tok g ; g i f ( $ b e s t t o k eq "" ) f # Word wasn ' t in corpus , or was < 2 c h a r s in l e n g t h . Use t h e o r i g i n a l word . $ b e s t t o k = $origword ; g # Now o u t p u t word and stem print " $origword n t $ b e s t t o k nn" ;