our experience with the TREC-8 CLIR track suggested that morphological analysis of terms contained in lists found on the web often contain an eclectic mix of root forms and their morphological variants, and introduction of spurious translations: thus developed a four-stage backo strategy that w as designed to maximize coverage while limiting the documents and bilingual term lists could discover plausible translations when no exact match is found. We a term that is not known to the translation resource (in this case, the bilingual term list). Bilingual term The coverage problem in CLIR arises when the object being translated (in this case, a document), contains multi-word translations (in no particular order), and nally b y any single word entries that did not appear unigram frequency in the Brown corpus (which contains many genres of written English), followed by all that most commonly occurred in written English. All single word translations were ordered by decreasing had the eect of minimi zing the eect of infrequen t words in non-standard usages or misspellings that might appear in the bilingual term list. at all in the Brown corpus. Translations beyond the second for any English term were then deleted; this and four-character suxes in decreasing order of frequency . We observed that the count vs. rank plot for an We implemented rule induction as follows. We rst coun ted the frequency of every one, two, three and possibly the terms that would prove most useful in a search. We therefore augmented Linguistica with a And second, the morphological analysis systems would need to produce accurate results on words presented words to discover common suxes [1 ]. We decided to try to push that idea further, automating the process that was ultimately to be searched.
Goldsmith known as Linguistica [2]. Linguistica examines each token in a collection, observing the frequency simplication of this idea in whic h morphological analysis was replaced by stemming. Stemmers are freely so that it could be applied to new languages without additional eort. W e call this approach \statistical on a 128 MB Windows NT machine. This is certainly large enough to ensure that breakpoints will be computational linguistics. Of this work, the closest in spirit to our objectives that we know of is a program by morphology in information retrieval applications where (as is the case in our application) matching is the of the next longer length from each sux. 5 The adjusted frequencies were then used to sort all two, three stemming," since the stemmer is learned from the statistics of a text collection, in our case the collection collection. This \minimum description length" criterion captures the intuition that breakpoints should be chosen in such a way that each token is partitioned into a relatively common stem and a relatively common of stems and suxes that w ould result from every possible breakpoint. An optimal breakpoint for each token simple rule induction technique to handle words that were outside Linguistica’s training set. would overstate the frequency of partial suxes|for example, \-ng" is a common ending in English, but in discovered for most common words, but breakpoints might not be discovered for less common terms|quite ecien t morphological analysis system be available for every document language that must be processed. and then choosing breakpoints for each unique token that minimize the number of bits needed to encode the almost every case it is part of \-ing". We thus subtracted the frequency of the most common subsuming sux easily constructed for Spanish without knowledge of the language by examining lexicographically similar sux. Linguistica is freely a but the present implementation can process only about 200,000 words vailable,4 out of context, as they are in the bilingual term list. This is a tall order, so we elected to explore a available stemmer for Italian. In TREC-4, Buckley, et al. demonstrated that a simple stemmer could be principal objective [3]. This represents only a partial solution, however, since we are not aware of a freely The four-stage backo strategy described abo ve poses two key challenges. First, it would require that an four-character sux that w ould result in a stem of three or more characters for the rst 500,000 w ords of the collection. Each instance of every word was used to compute the sux frequencies. These statistics alone available for French and and stemming has proven to be about as eectiv e as more sophisticated German,3 is then selected by applying as a constraint that every instance of a token must have the same breakpoint Statistical stemming is a special case of unsupervised acquisition of morphology, a specialized topic in English training case was convex, so we selected the rank at which the second derivative of the count vs. rank stemming (i.e., step one alone). In our Linguistica run (\backo4Ling"), w e implemented the complete in this language. This somewhat counterintuitive set suggests that further optimization of threshold setting frequency (regardless of location) is highly skewed. We thus sorted single characters by the ratio between English, this approach did not work well for single-character suxes because the distribution of c haracter The heuristics we chose were motivated by our intuition of what constituted a likely sux, but the longer subsuming strings selects the less general suxes. A large n umber of single character suxes are derivative as a stopping For each word, the rst matc hing sux (if an y, from the top of the list) was point.6 then removed to produce the stemmed form. details were settled only after a good deal of tweaking with a training collection. Of note, the training Three ocial runs w ere submitted. In our baseline run (\unstemmed"), we used no pre-translation that were automatically produced with no further tuning. Many of the postulated suxes in that table accord sux ent. However, some others suggest insucien t generalization. Consider the suggested German suxes: four-stage backo strategy using Linguistica for terms with kno wn breakpoints, and added a fth stage that replicated stage four using the rule induction stemmer in place of Linguistica that would be invoked if none of the rst four stages found a translation. The rule induction process is considerably faster than Linguistica (less than 5 minutes, compared with 30-40 minutes for Linguistica) so we also submitted a third run in which their word-nal lik elihood and their unconditioned likelihood, and again used the maximum of the second collection contained only English documents and the tweaking was done by the rst author, who has no useful knowledge of French, German or Italian. Table 2.2 shows the sux remo val rules for those languages well with our intuition, as in the case the French adverbial sux ment or third-person plural inectional is necessary. suggested for Italian, including letters such as k and w which do not typically appear in word-nal position ngen,nden,sen,nen,gen,den, and ten. The more appropriate sux w ould be en; however, the preference for plot was maximized as the limit for how many suxes to generate for eac h length. In tuning experiments with with other language-independent techniques such as blind relevance feedback for query expansion and for can be used together to improve retrieval eectiv eness in a document translation architecture. When coupled We have introduced two new techniques, four-stage backo and statistical stemming, and sho wn how they
None None 6 which we implemented four-stage backo with rule induction alone. T able 2.2 summarizes these conditions. Table 4: Multilingual evaluation results, uninterpolated mean average precision over 40 topics. Table 3: Summary of ocial runs Stage Document Document 4 Conclusion
Although we can conclude that four-stage backo resulted in impro ved retrieval eectiv eness and that statistical stemming appears to be a viable substitute for more sophisticated morphological analysis in this benecial eects, or whether rev ersing the second and third stages might improve retrieval eectiv eness. We between the Linguistica and rule induction results on a query-by-query basis as we seek to understand these results as indicating that we have achieved a credible degree of retrieval eectiv eness using only freely design can easily mask single-language eects, so w e plan to perform unocial monolingual runs using the available linguistic resources. median average precision on 24 of 40 queries, and the backo4 run ac hieved at-or-above-median average plan to explore those questions using unocial con trastive runs. Finally, we plan to explore the dierences ure 4). Since the eect of our limited man ual stop-structure removal was likely quite small, we interpret whether some other way of combining the two might result in improved retrieval eectiv eness. nican t by a paired two-tailed t-test (p < 0:002 in both cases) (Figure 2). Surprisingly, our ad hoc rule more sophisticated Linguistica software (p 0:38).(Figure 3) The backo4Ling run ac hieved at-or-aboveimprovement in retrieval eectiv eness over the unstemmed approach that was found to be statistically sigsame language pairs. We do not yet know which stages in our four-stage backo strategy produce the greatest application, further analysis is needed if we are to optimize the design of our techniques. The multilingual task Our backo4 run w as judged, and all three runs were scored ocially . Table 3 summarizes the results. precision on 27 or 40 queries, although in both cases the median was computed for automatic queries (Figinduction technique produced results that were statistically indistinguishable from those obtained using the [4] Gina-Anne Levow and Douglas W. Oard. Translingual topic tracking with PRISE. In Working Notes of the Third Topic Detection and Tracking Workshop, February 2000. humanities.uchicago.edu/faculty/goldsmith/, 2000. [2] John Goldsmith. Unsupervised learning of the morphology of a natural language.
[3] David A. Hull. Stemming algorithms - A case study for detailed evaluation. Journal of the American 8 References http:// Acknowledgments (specically , a comparable collection from which to obtain term statistics). The CLEF evaluation has proven to be a suitable venue for exploring these questions, and we look forward to continued participation in future years. dictionary-based CLIR systems using only a bilingual term list and some modest query-language resources post-translation document expansion [4], developers now have a robust toolkit with which to design eectiv e term lists. This work was work was supported in part by DARPA contract N6600197C8540 and DARPA The authors wish to thank Patrick Schone, Philip Resnik and David Yarowsky for helpful discussions of the unsupervised morphology acquisition and Jianqiang Wang for his help with Inquery and the bilingual cooperative agreement N660010028910. [5] Douglas W. Oard. A comparative study of query and document translation for cross-lan guage information Americas, October 1998. retrieval. In Proceedings of the Third Conference of the Association for Machine Translation in the [1] Chris Buckley, Gerard Salton, James Allan, and Amit Singhal. Automatic query expansion using SMART: TREC 3. In D. K. Harman, editor, Overview of the Third Text REtrieval Conference (TREC-3), pages 69{80. NIST, November 1994. http://trec.nist.gov/.