In the past we have conducted experiments that investigate the benefits and peculiarities attendant to alternative methods for tokenization, particularly overlapping character n-grams. This year we continued this line of work and report new findings reaffirming that the judicious use of n-grams can lead to performance surpassing that of word-based tokenization. In particular we examined: the relative performance of n-grams and a popular suffix stemmer; a novel form of n-gram indexing that approximates stemming and achieves fast run-time performance; various lengths of n-grams; and the use of n-grams for robust translation of queries using an aligned parallel text. For the CLEF 2003 evaluation we submitted monolingual and bilingual runs for all languages and language pairs, multilingual runs using English as a source language, and a first attempt and cross-language spoken document retrieval. Our key findings are that shorter n-grams (n=4 and n=5) outperform a popular stemmer in non-Romance languages, that direct translation of n-grams is feasible using an aligned corpus, that translated 5-grams yield superior performance to words, stems, or 4grams, and that a combination of indexing methods is best of all.
In the past we have examined a number of issues pertaining to how documents and queries are represented.
This has been a particular interest in our work with the HAIRCUT retrieval system due to the consistent
success we have observed with the use of overlapping character n-grams. Simple measures that can be
uniformly applied to text processing, regardless of language, reduce developer effort and appear to be at least
as effective as approaches that rely on language-specific processing, and perhaps more so. They are
increasingly used when linguistic resources are unavailable[
We have wondered whether diacritical marks have much effect upon retrieval performance - for a long time
we have been retaining diacritical marks as part of our ordinary lexical processing, in keeping with a
keep-itsimple approach. One principled argument for retaining inflectional marks is that they possess a
deconflationary effect when content words that differ only in diacritics have different meaning. For example,
the English words resume (to continue) and résumé (a summary of one’s professional life) can be
distinguished by differences in diacritics. On the other hand, such marks are not always uniformly applied,
and furthermore, if retained, might distinguish two semantically related words. Stephen Tomlinson
investigated preservation of diacritics using the CLEF 2002 collection and reported that it was helpful in
some cases (Finnish) and harmful in others (Italian and French) [
We use a statistical language model for retrieval akin to those presented by Miller et al. [
P(D | Q) = ∏[αP(q | D) + (1 −α )P(q | C)],
q ∈Q where Q is a query, D is a document, C is the collection as a whole, and α is a smoothing parameter. The probabilities on the right side of the equation are replaced by their maximum likelihood estimates when scoring a document. The language model has the advantage that term weights are mediated by the corpus. Our experience has been that this type of probabilistic model outperforms a vector-based cosine model or a binary independence model with Okapi BM25 weighting.
For the monolingual, bilingual, and multilingual tasks, all of our submitted runs were based on a combination of several base runs. Our method for combination was to normalize scores by probability mass and to then merge documents by score. All of our runs were automatic runs and used only the title and description topic fields.
For our monolingual work we created several indexes for each language using the permissible document fields appropriate to each collection. Our four basic methods for tokenization were unnormalized words, stemmed words obtained through the use of the Snowball stemmer, 4-grams, and 5-grams. Information about each index is shown in Table 2.
language #docs %docs From the table above it can be seen that the percentage of relevant documents for each subcollection is closely related to its contribution to the overall number of documents. This would suggest that collection size might be a useful factor for multilingual merging. We also note that n-gram indexing results in increased disk storage costs. This cost is driven by the increased number of postings in the inverted file when n-gram indexing is performed.
Our use of 4-grams and 5-grams as indexing terms represents a departure from previous work using 6-grams
[
DE
EN
ES
FI
FR
IT
NL
SV
We determined that use of n=4 or n=5 is best in all eight languages though it is hard to distinguish between
the two. 6-grams are clearly not as effective in these languages. There are differences in performance
depending on the value of smoothing constant, α, that is used, though we have yet to test whether these
differences are significant or merely represent overtraining on the 2002 test set. The effect of smoothing
parameter selection in language model-based retrieval was investigated by Zhai and Lafferty [
In additional to determining good values for n, we also wanted to see if n-grams remained an attractive
technique in comparison to stemmed words. Having no substantive experience with stemming, we were
pleased to discover that the Snowball stemmer [
This method has the advantage of providing some morphological normalization, but it does not increase the
number of postings in an inverted file. This can be viewed either as a way to approximate stems or a way of
lowering the computational cost of using n-grams. We found that n-grams did outperform stems, and that our
pseudo stems based on n-grams were better than raw words, but not as effective as a rule-based stemmer (see
Figure 2). Details about this work can be found in Mayfield and McNamee [
sv nl it fr fi es en de 0.00 0.10
0.20 0.30 Mean Average Precision 0.40
0.50
Words
1 The Snowball stemmer also fails to transform juggler to a canonical form.
To produce our official monolingual runs we decided to combine runs based on the Snowball stemmer with
runs using n-grams as indexing terms. Runs named aplmoxxa used 4-grams and stems while runs named
aplmoxxb used 5-grams and stems. However, due to a mistake while creating the scripts used to produce all
of our runs, we inadvertently failed to perform blind relevance feedback for our monolingual submissions.
Routinely we expand queries to 60 terms using additional terms ranked after examining the top 20 and
bottom 75 (of 1000) documents. Failing to use blind relevance feedback had a detrimental effect on our
official runs. Our official monolingual runs are described in Table 4 and corrected scores are presented on
the far right.
It appears that several of our runs would have increased substantially if we had correctly used blind relevance
feedback. Relative improvements of more than 5% were seen in German, Russian, and Spanish although
performance would have dropped slightly in Swedish. The German and Spanish document collections are the
two largest in the entire test suite. We wonder if relevance feedback may be more beneficial when larger
collections are available, a conjecture partially explored by Kwok and Chan [
This year the Bilingual task focused on retrieval involving four language pairs, which notably did not contain English as a source or target language. This is only significant because of the difficulty in locating direct translation resources for some language pairs and the fact that many translation resources are available when English is one of the languages involved. The four language pairs are German to Italian, Finnish to German, French to Dutch, and Italian to Spanish.
For the 2002 campaign we relied on a single translation resource: bilingual wordlists extracted from parallel
corpora. We built a large alignable collection from a single source, the Official Journal of the EU [
Our collection was obtained through a nightly crawl of the Europa web site where we targeted the Official
Journal of the European Union [
We performed pairwise alignments between languages pairs, for example, between German and Italian. Once aligned, we indexed each pairwise-aligned collection using the technique described for the CLEF-2003 document collections. Again, we created four indexes per sub-collection, per language – one each of words, stems, 4-grams and 5-grams. Our goal was to support query term translation, so for each source language term occurring in at least 4 documents, we attempted to determine a translation of the same token type in the target language. At this point we should mention that the ‘proper’ translation of an n-gram is decidedly slippery – clearly there can be no single correct answer. Nonetheless, we simply relied on the large volume of n-grams to smooth topic translation. For example, the central 5-grams of the English phrase ‘prime minister’ include ‘ime_m’, ‘me_mi’, and ‘e_min’. The derived ‘translations’ of these English 5-grams into French are ‘er_mi’, ‘_mini’, and ‘er_mi’, respectively. This seems to work as expected for the French phrase ‘premier ministre’, although the method is not foolproof. Consider n-gram translations from the phrase ‘communist party’ (parti communiste): ‘_commu’ (mmuna), ‘commu’ (munau), ‘ommun’ (munau), ‘mmuni’ (munau), ‘munis’ (munis), ‘unist’ (unist), ‘nist_’ (unist), ‘ist_p’ (ist_p), ‘st_pa’ (1_re_), ‘t_par’ (rtie_), ‘_part’ (_part), ‘party’ (rtie_), and ‘arty_’ (rtie_). The lexical coverage of translation resources is a critical factor for good CLIR performance, so the fact that almost any n-gram has a ‘translation’ should improve performance. The direct translation of n-grams may offer a solution to several key obstacles in dictionarybased translation. Word normalization is not essential since sub-word strings will be compared. Translation of multiword expressions can be approximated by translation of word-spanning n-grams. Out-of-vocabulary words, particularly proper nouns, can be be partially translated by common n-gram fragments or left untranslated in close languages.
We extracted candidate translations as follows. First, we would take a candidate term as input and identify documents containing this term in the source language subset of the aligned collection. Up to 5000 documents were considered; we bounded the number for reasons of efficiency and because we felt that performance was not enhanced appreciably when a greater number of documents was used. If no document contained this term, then it was left untranslated. Second, we would identify the corresponding documents in the target language. Third, using a statistic that is similar to mutual information, we would extract a single potential translation. Our statistic is a function of the frequency of occurrence in the whole collection and the frequency in the subset of aligned documents. In this way we extracted the single-best target language term for each source language term in our lexicon (not just the query terms in the CLEF topics). When 5-grams were used this process took several days.
Table 5 lists examples of translating within the designated language pairs using each type of tokenization. Mistakes are evident; however, especially when pre-translation expansion is used the overall effectiveness is quite high. We believe the redundancy afforded by translating multiple n-grams for each query word also reduces loss due to erroneous translations. Finally, incorrect translations may still prove helpful if they are a collocation rather than an actual translation. 5grams words stems 4grams We remain convinced that pre-translation query expansion is a tremendously effective method to improve bilingual performance. Therefore we used each CLEF 2003 document collection as an expansion collection for the source language queries. Queries were expanded to a list of 60 terms, and then we attempted to translate each using our corpus-derived resource. In the past we have been interested in using n-grams as terms, however, we have worked with bilingual wordlists for translation. This year we decided to create translingual mappings using the same tokenization in both the source and target languages. Thus for each of the four language pairs, we created four different lists (for a total of 16): one list per type of indexing term (i.e., word, stem, 4-gram, or 5-gram). Again using experiments on the CLEF 2002 collection, we determined that mappings between n-grams were more efficacious than use of word-to-word or stem-to-stem mappings. Thus different tokenization can be used for initial search, pre-translation expansion, query translation, and target language retrieval. In testing we found the best results using both n-grams and stems for an initial source-language search, then we extracted ordinary words as ‘expansion’ terms, and finally we translated each n-gram contained in the expanded source language word list into n-grams in the target language (or stems into stems, as appropriate). The process is depicted in Figure 3:
IT query
ES docs combattimenti ribelli guerriglieri diamanti sierra diamantifero militare rivoluzionario leone …
Translation combates militares ribeldes rivolucionario guerriglieri leona diamantes sierra diamantes …
_comb, comba, ebate, … _sier, sierra, erra_, erril, … milit, itari, … _diam, diama, … … Our runs named aplbixxyya are bilingual runs that were translated directly from the source language to the target language; each run was a combination of four base runs that either used words, stems, 4-grams, or 5grams, with (post-translation) relevance feedback. The runs named aplbixxyyb were combined in the same way, however the four constituent base runs did not make use of post-translation feedback. When words or stems were used a value of 0.3 was used for alpha; when n-grams were used the value was 0.5. The base runs are compared in Figure 4.
DEIT
FIDE
FRNL
ITES
From observing the data in Table 6 and Figure 4, it would appear that the use of post-translation feedback did not enhance performance when multiple runs were combined. The two types of runs seemed to perform similarly in two language pairs (Finnish to German and Italian to Spanish); however, the merged runs without relevance feedback did better for the German to Italian and French to Dutch runs. Combination of methods resulted in between a 3 and 10% gain depending on language pair. We have not yet had the opportunity to retrospectively analyze the contribution to our overall performance of pre-translation expansion.
0.50 0.45 n io0.40 s i c e r P eg0.35 a r e v A n ea0.30 M 0.25 0.20 words stems 4-grams 5-grams words noRF stems noRF 4-grams noRF 5-grams noRF Best APL Run
We initially thought to create runs for the multilingual task in the exact same way as for the bilingual task. However, we decided to use English as our source language and we had to create translation lists for seven languages using four tokenization types (a total of 28 mappings). Construction of the 5-gram lists took longer than expected and so we had to modify our plans for our official submission. We decided to submit a hybrid run based on words, stems, and 4-grams; merging was again accomplished using normalized scores. As with the bilingual task, runs ending in ‘a’ denote the use of post-translation relevance feedback, while runs ending in ‘b’ did not use feedback (see Table 7).
This was our first time using the TREC-8 and TREC-9 spoken document dataset. Our submissions were created in very short order – in one day. We pre-processed the data so it had similar SGML markup as the ad hoc TREC collections and then indexed the English text using only 5-grams. The index took 33 minutes to build. We did not make use of any collection expansion for these runs. Our processing was similar to the work we did for the bilingual track, except that we used only 5-grams as translation terms and did not use pre-translation expansion (which was not permitted for ‘primary’ submissions).
For the first time we were able to directly compare words, various lengths of character n-grams, a suffix stemmer, and an n-gram alternative to stemming, all using the same retrieval engine. We found that n-grams of shorter lengths (n=4 or n=5) were preferable across the CLEF 2003 languages and that n-grams generally outperformed use of the Snowball stemmer: 4-grams had a 8% mean relative advantage across the 9 languages compared to stems; however stemming was better in Italian and Spanish (by 17% and 5% respectively). We found best performance can be obtained using a combination of methods. If emphasis is placed on accuracy over storage requirements or response time, this approach is reasonable. For bilingual retrieval we identified a method for direct translation of n-grams instead of word-based translation. Without the use of relevance feedback, 5-grams outperformed stems by an average of 17% over the four bilingual pairs though 4-grams appeared to lose much of their monolingual superiority. When feedback was used, the gap narrowed substantially.
This work should not be taken as an argument against language resources, but rather as further evidence that knowledge-light methods can be quite effective, when optimized. We are particularly excited about the use of non-word translation (i.e., using direct n-gram translation) as this appears to have the potential to avoid several pitfalls that plague dictionary-based translation of words.
We are still analyzing our results from the multilingual and spoken-document tracks and hope to report on them more fully in our revised paper.