For CLEF 2008 JHU conducted monolingual and bilingual experiments in the ad hoc TEL and Persian tasks. The TEL task involved focused on searching electronic card catalog records in English, French, and German using data from the British Library, the Bibliotheque Nationale de France, and the O sterreichische Nationalbibliothek (Austrian National Library). The approach we adopted for TEL was to strip out non-content sections of records and to treat the task as ordinary full-text search using character n-grams and stemmed words. For the Persian task, which is based on the Hamshahri corpus, several di erent forms of textual normalization were compared. Using the provided training topics we compared character n-grams, n-gram stems, ordinary words, words automatically segmented into morphemes, and a novel form of n-gram indexing based on n-grams with character skips. On the training topics we found that character 5-grams and skipgrams performed the best and this was borne out in our o cial submissions. We also did some post hoc experiments using previous CLEF ad hoc tests sets in 13 languages. In all three tasks we explored alternative methods of tokenizing documents including plain words, stemmed words, automatically induced segments, a single selected ngrams for each words, and all n-grams from words (i.e., traditional character n-grams). Character n-grams demonstrated consistent gains over ordinary words in each of these three diverse sets of experiments. Using mean average precision, relative gains of of 50-200% on the TEL task, 5% on the Persian task, and 18% averaged over 13 languages from past CLEF evaluations, were observed.
are bene cial for normalizing morphological variation, particularly in languages where words have many related surface forms.
Using test sets in the 13 languages used in the ad hoc tracks at previous CLEF evaluations, we compared n-grams to several tokenization alternatives, including a rule-based stemmer (Snowball ), an unsupervised morphological segmenter (Morfessor ), and a synthetic form of stemming based on selecting a single character n-gram from each word. Character n-grams of length n = 5 were the most e ective technique, performing 18% better than unnormalized words, averaged across the set of languages.
Accordingly n-grams were used in o cial submissions to this year's ad hoc tasks. For this
year's participation at CLEF we used the JHU HAIRCUT retrieval system, employing a
statistical language model similarity metric with a smoothing constant of 0.5. The similarity calculation
combines document term frequencies and corpus frequencies (for smoothing) using linear
interpolation with a smoothing constant of 0.5 [
In Section 2 we describe our experiments for the TEL subtask. In Section 3 we analyze our training experiments and o cial results for the Persian subtask. In Section 4 some recent experiments on previous CLEF collections are described. 2
Our approach to TEL was to treat the collection as unstructured documents. Fields that did not appear to contain good indexable content were removed, including: publisher, rights, format, description, indenti er, contributor, type, language, coverage, issued, available, extent, spatial, and created. Text from the following elds was retained: ispartof, edition, alternative, tableofcontents, abstract, bibliographiccitation, subject, title, abstract, date, creator, source, and relation. All SGML tags were removed.
Some of these choices were probably harmful. For example, queries that speci ed a particular language or document type (i.e., maps) might have bene tted from some of the deleted metadata. The aim of removing these elds was to increase the coherence of each document's indexable terms. 2.1
The tokenization methods explored were:
words: space-delimited tokens.
snow: output of the Snowball stemmer.
morf : the set of morphemes for each word identi ed by the Morfessor algorithm.
Morfessor is available online at http://www.cis.hut. /projects/morpho/. A model was trained
using the document collection's lexicon with digit-containing tokens omitted. The default
parameters for the Morfessor algorithm were used [1].
lcn4/5: least common n-gram stem (i.e., rarest word-internal character n-gram) of length
n = 4 or n = 5 [
5-grams: length n = 5 n-grams created in the same fashion as the character 4-grams. Common to each tokenization method was conversion to lower case letters, removal of punctuation, and truncation of long numbers to 6 digits.
words snow morf lcn4 lcn5 4-grams 5-grams 4-grams + RF Our o cial submissions were based on 4-grams, both with and without automated relevance feedback, 5-grams (no RF), and stemmed words. Table 1 lists mean average precision for these runs, as well as for several unsubmitted runs. In the o cial run names xx indicates one of de (German), en (English), or fr (French).
While performance did not vary dramatically in English, except for the unnormalized word run which performed the worst, 4-grams were dominant with the French and German collections. Large gains were observed with 4-grams compared to plain words { more than a 50% relative gain in French and over 200% in German. 2.3
For each language pair the source side query was tokenized using only character 5-grams and
those n-grams were `translated' to the target language using a large aligned parallel corpus (content
from the O cial Journal of the European Journal). The methodology in query term translation
was like that in [
Source language did not make a large di erence in performance across the three collections. Bilingual performance was approximately 60% of the highest performing monolingual run, which is a bit lower than we have customarily observed in bilingual retrieval against news corpora at CLEF. 3
We made submissions for both the monolingual and bilingual subtasks. The bilingual submissions were based on online machine translation software1 applied to the queries, so only one set of indexes was required. In addition to the methods in Section X.Y we used skipgrams, 4- or 5grams with and without one internal skip (denoted by sk41 & sk51 ). Snowball does not support Farsi so no stemming runs were attempted. 3.1
Consider the present tense conjugation of the Spanish verb contar (to count ): cuento, cuentas, cuenta, contamos, contais, and cuentan. Such in ectional variation can cause lexical mismatches that would impair retrieval, and character n-grams are unlikely to be a total solution to this problem since the 1st and 2nd person plural forms do not share longer n-grams with the other forms. Similar problems can happen with nouns, for example, in Welsh plentyn (child ) and its plural, plant (children). These two examples contain patterns that could enable matching, such as regular expressions c?nt and pl?nt, which would match all the related forms.
Pirkola et al. [
But with longer n-grams there are multiple places where skips can occur, and character skipgram methods can be generalized even further by including the possibility of multiple non-adjacent skips within a single word (though no such experiments are reported here). In these experiments skipgrams are considered as an alternative method for tokenization that might support matches across morphologically related words. When a letter is skipped we replace that letter in the n-gram subsequence with a special symbol (i.e., a dot character ( ). This is done in an attempt to avoid unintended con ations with n-gram strings produced by unrelated words. Skipgram tokenization of length four for the word cream would include the regular n-grams crea and ream in addition to c eam, cr am, and cre m. 3.2
The various methods of tokenization were compared on the 50 training topics. In Table 3 runs without relevance feedback are presented along with runs that made use of automated feedback using various numbers of expansion terms.
1http://www.parstranslator.net/eng/translate.htm 2They use the term s-grams. 4-grams 5-grams words morfessor lcn4 lcn5 sk41 sk51 In Table 4 mean average precision is reported for eight tokenization methods. The n-grams methods are the highest performing approach and the skipgrams perform slightly worse than traditional character n-grams. The highest performing run was character 4-grams using 200 expansion terms which got a MAP score of 0.4564; however the results on the training topics suggested 5-grams would outperform and we selected them instead. N-grams appear to need more query expansion terms than words to maximize performance, and skipgrams, being even more con ationary require more than regular 4- or 5-grams.
The results for our o cial monolingual and bilingual runs are given in Table 5. Tokenization method did not appear to drastically a ect the outcome monolingually; however, words and the Morfessor-based runs did markedly worse on the bilingual task compared to the n-gram based methods. We compared plain words, stems, induced morphemes, n-gram stems, and character n-grams using test sets from the CLEF ad hoc tasks between 2002 and 2007.3 In each of the 13 languages we used two years worth of data except for Czech where only one year was available. The number of test queries per language varied from 50 (Czech) to 107 (Spanish). In Table 6 results are presented using mean average precision to compare performance. The score for the highest performing technique in each language is emboldened. 4.1
Not attempting to control for morphological processes can have harmful e ects. In Bulgarian, Czech, Finnish, and Hungarian, more than a 30% loss is observed compared to the use of 4-grams as indexing terms. 4.2
Snowball does not support Bulgarian, Czech, or Russian and due to character encoding issues with the software we were not able to use it for Portuguese and Hungarian. In Table 1 performance for each technique is given averaged over eight remaining languages. Stemming, when available, is quite e ective, and just slightly below the top-ranked approach of character n-grams. 4.3
As it may be di cult to nd a rule-based stemmer for every language, a language-independent
approach can be quite attractive. The Morfessor algorithm only requires a lexicon (i.e., wordlist)
for a language to learn to identify morpheme boundaries, even for previously unseen words. Such
automatically detected segments can be an e ective form of tokenization [
Compared to plain words the induced morphemes produced by Morfessor led to gains in 9 of 13 languages; 8 of these were signi cant improvements with p < 0.05 (Wilcoxon test). The languages where words outperformed segments were English (dramatically), French, Italian, and Spanish { 3These results are also reported in our Morpho Challenge 2008 paper in these working notes. each is relatively low in morphological complexity. The di erences in French and Spanish were less than 0.004 in absolute terms. Segments achieved more than a 20% relative improvement in Bulgarian, Finnish, and Russian, and over 40% in Czech and Hungarian. Another language-neutral approach to stemming is to select for each word, its least common ngram. This requires advance knowledge of n-gram frequencies, but this is easily obtainable by constructing a regular n-gram index, or even by scanning a corpus and counting. Lengths of n = 4 and n = 5 appear about equally e ective with a slight advantage for lcn4, but this is in uenced primarily by the languages with greater morphological complexity, which see larger changes. An 8% relative improvement in mean average precision over words is obtained. As can be seen from Table 1, in languages where rule-based stemming is available its use is preferable. N-gram stemming achieves comparable performance with Morfessor segments.. N-grams achieve morphological regularization indirectly due to the fact that subsequences that touch on word roots will match. For example, \juggling" and \juggler" will share the 5-grams jugg and juggl. While n-gram's redundancy enables useful matches, other matches are less valuable, for example, every word ending in `tion' will share 5-gram tion with all of the others. In practice these morphological false alarms are almost completely discounted because term weighting deemphasizes them. In fact, such a xes can be so common, that ignoring them entirely by treating them as \stop n-grams" is a reasonable thing to do.
Character n-grams are the most e ective technique studied here, giving a relative improvement
of 18%. Consistent with earlier work [
Snowball stems are roughly as e ective as n-grams, on average, but only available in certain languages (i.e., 8 of 13 in this study). The other \alternative" stemming approaches, segments and least common n-grams, appear to gain about half of the bene t that full n-gram indexing sees compared to unnormalized word forms. 5
We examined a variety of methods for lexical normalization, nding that the most e ective technique was character n-gram indexing. N-grams achieved consistent gains in mean average precision over unlemmatized words. Relative gains of of 50-200% on the TEL task, 5% on the Persian task, and 18% averaged over thirteen languages from past CLEF evaluations, were observed. In languages such as Czech, Bulgarian, Finnish, and Hungarian gains of over 40% were observed. While rule-based stemming can be quite e ective, such tools are not available in every language and even when present, require additional work to integrate with an IR system. When languageneutral methods are able to achieve the same, or better performance, their use should be seriously considered. [1] Mathias Creutz and Krista Lagus. Unsupervised morpheme segmentation and morphology induction from text corpora using Morfessor 1.0. Technical report, Helsinki University of Technology, 2005.