JHU/APL has long espoused the use of language-neutral methods for cross-language information retrieval. This year we participated in the ad hoc cross-language track and submitted both monolingual and bilingual runs. We undertook our first investigations in the Bulgarian and Hungarian languages. In our bilingual experiments we used several nontraditional CLEF query languages such as Greek, Hungarian, and Indonesian, in addition to several western European languages. We found that character n-grams remain an attractive option for representing documents and queries in these new languages. In our monolingual tests n-grams were more effective than unnormalized words for retrieval in Bulgarian (+30%) and Hungarian (+63%). Our bilingual runs made use of subword translation, statistical translation of character n-grams using aligned corpora, when parallel data were available, and web-based machine translation, when no suitable data could be found.
lemmatization, matching of multiple word expressions, and inability to handle out-of-vocabulary words such
as common surnames [
We submitted official runs for the monolingual and bilingual tracks. For all of our runs we used the HAIRCUT system and a statistical language model similarity calculation. Some of our official runs were based solely on n-gram processing; however, we thought that by using a combination of n-grams and words or stemmed words better performance could sometimes be obtained.
HAIRCUT supports several ways of representing documents using an order independent, bag-of-terms model. Note we are frequently using character n-grams, not words as indexing terms. Our general approach is to process the text of each document, reducing all terms to lower-case. Words were deemed to be whitespace delimited tokens in the text; however, we preserve only the first 4 digits of a number and we truncate any particularly long tokens (those greater than 35 characters in length). We make no attempt at compound splitting. Once words are identified we optionally perform transformations on the words to create indexing terms (e.g., stemming using the Snowball stemmer). Starting in 2003 we began removing diacritical marks, believing that they are of little importance. So-called stopwords are retained in our index and the dictionary is created from all words present in the corpus. At query time we ignore high frequency terms for reasons of efficiency, and because such terms typically add little to query performance. (By default, query terms occurring in greater than 20% of documents are ignored).
We continue to use a statistical language model for retrieval akin to those presented by Ponte and Croft [13]
and Hiemstra [
P (D | Q ) = ? [a P (q | D ) + (1 - a )P (q | C ) ] ,
q ?Q where Q is a query, D is a document, C is the collection as a whole, and a 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. It has been 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.
Character n-grams, sequences of n consecutive characters, have been used for a number of tasks in human
language technology (e.g., spelling correction [14], diacritics restoration [
For our monolingual work we created 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 (when available), 4-grams, and 5-grams. Information about each index is shown in Table 1 (below).
Selection of 4-grams and 5-grams as indexing terms was based on a comprehensive study across the CLEF
languages that investigated n-gram length [
Our submitted runs were based on a combination of several base runs using various options for tokenization. Our method for combination is to normalize scores by probability mass and to then merge documents by score. All of our submitted runs were automatic runs and used only the title and description topic fields. We produced three to five runs in each language that were created from combinations of the base runs. Runs were labeled aplmoxx[a-e], where xx indicates the language of interest. Runs whose names end with a terminal ‘a’ were produced by combining a 5-gram base run with a stemmed word base run; a terminal ‘b’ indicates fusion of a 4-grams and stemmed words; terminal ‘c’is used for runs that used both 4-grams and 5grams; the suffix ‘d’indicates solitary use of 4-grams; and, a terminal ‘e’indicates the use of 5-grams alone. Monolingual performance based on mean average precision is reported in Table 2.
0.50 0.45 n0.40 o i s i c re0.35 P e g a r ve0.30 A n a e M0.25 0.20 0.15 words snow 4-grams 5-grams
Our preferred approach to bilingual retrieval is based on the following procedure: (1) apply pre-translation
query expansion using the source language CLEF corpus; (2) translate terms statistically using aligned
parallel corpora, where terms can be words, stems, or n-grams; (3) and, perform retrieval using the query
terms that were projected into the target language, possibly with additional relevance feedback. We have had
good success using aligned parallel corpora to extract statistical translations. Others have also relied on
corpus-based translation; however, we recently demonstrated significant improvements in bilingual
performance by translating character n-grams directly. We call this ‘subword translation’. Additionally we
also translate stemmed words and words. This year we were only able to use this technique for the English,
French, and Portuguese target collections as we lacked parallel resources in Bulgarian and Hungarian.
For the 2002 and 2003 campaigns we relied on a single source for parallel texts, the Official Journal of the
E.U. [15], which is published in the official languages (20 languages as of May 2004). The Journal is
available in each of the E.U. languages and consists mainly of governmental topics, for example, trade and
foreign relations. For the CLEF 2003 evaluation we had obtained 33 GB of PDF files that we distilled into
approximately 300 MB of alignable text, per language. In December 2003 we began the process of mining
archival issues of the Journal, beginning with 1998. This process took nearly five months. We obtained data
from January 1998 through April 2004 – over six years of data. This is nearly 80 GB of PDF files, or roughly
750 MB of plain text per language. We extracted text using the pdftotext program; however this software
cannot extract the Greek data set; we were left with data in ten languages, from which 45 possible alignments
are possible. Though focused on European topics, the time span is three to ten years after most of the
CLEF2004 document collection. Though aware of smaller, but aligned parallel data (e.g., Philip Koehn’s Europarl
corpus [
To align data between two languages, we would:
o convert the data from PDF format to plain text (this introduced some errors, especially when
processing diacritical marks in the earlier years);
o apply rules for splitting the text into sections (the data was page-aligned, we desired
paragraphsized chunks);
o and, align files using Church’s char_align [
To induce a translation for a given source language term, we proceed by: o identifying documents (i.e., approximately paragraphs) containing the source language term; o examining the set of corresponding documents from the target language portion of the aligned collection; o producing a score for each term that occurs in at least one of the target language paragraphs (more on this below); o and finally, selecting the single term with the largest translation score for the source language term. Our method for scoring candidate translations does not require translation model software such as GIZA++. Rather, we rely on information theoretic scores (e.g., symmetric conditional probability or mutual information) to rank terms. We adopt the same technique we rely on for pseudo relevance feedback – a method we have developed called affinity sets. Terms are weighted based on their inverse document frequency (IDF) and the difference between their relative frequency in the set of documents under consideration and the global set of documents. This measure is related to mutual information; however, we believe our technique is more general as it permits the set of documents to be identified through any means, including potentially, query-specific attempts at retrieval and translation.
We performed pairwise alignments between languages pairs, for example, between English and Portuguese.
Once aligned, we indexed each pairwise-aligned collection using the technique described earlier on the
CLEF-2005 document collections. That is, we created four indexes per sub-collection, per language – one
each of words, stems, 4-grams and 5-grams. This year, rather than create a translation dictionary for every
term in a source language index, we translated terms on demand using the algorithm presented above. So far
we have been using 1-best translation, but we can generate multiple weighted translations for each term. We
have not found this necessary as techniques such as pre-translation query expansion are capable of
generating many terms related to a query; thus the harm introduced by a dubious translation is lessened. Our
experience on the CLEF 2003 and 2004 bilingual test sets led us to believe that direct translation of 5-grams
would likely be the most effective single technique, but that combination using runs generated by translating
multiple term types might yield an improvement [
Unfortunately, our data from the Official Journal of the EU did not cover two of the target language collections (i.e., Bulgarian and Hungarian). To support translation to or from these languages we relied on query translation using web-based machine translation. We also used MT to use the Greek and Indonesia query sets against English documents. The online services we used are located at: • http://babelfish.altavista.com (GR to EN) • http://www.toggletext.com/kataku_trial.php (IN to EN) • http://www.bultra.com/test_e.htm (BG to/from EN) • http://www.tranexp.com/ (HU to/from EN) As can be seen in Table 3 (below), our results using corpus-based subword translation achieved bilingual performance between 78% and 87% of our best monolingual runs for the given target language. Table 4 details our results using available machine translation software. The resultant bilingual performance depends heavily on the individual translation engine used (from 26% to 85% of our best monolingual baselines). In some cases the result of fusing multiple runs using different target-side tokenization of the machine translation output resulted in an improvement, for example, run aplbiidend had a 4% absolute improvement in mean average precision of aplbiidena, which used 5-grams alone. In a couple of cases we directly compared the use of 4-grams and 5-grams on the MT output and found the results to be very similar (e.g., compare aplbienbg[a/e] and aplbienhu[a/e]). In Bulgarian and Hungarian it seems that 4-grams may have a slight advantage over 5-grams, though additional testing should be performed to verify that the differences are statistically significant. However, the use of n-grams over raw words seems clearly indicated.
JHU/APL participated in the ad hoc tasks in the CLEF 2005 evaluation, using our language-neutral approach that prominently features character n-gram tokenization and statistical translation using aligned parallel corpora. This year we had to rely on web-based machine translation for mappings between several language pairs, for which we had been unable to obtain suitable parallel data. We compared words, a popular suffix stemmer, and n-grams of lengths four and five on the monolingual collections, all using the same retrieval engine and language model similarity metric. We found that n-grams continued to work well for monolingual retrieval, though their superiority was only apparent in Bulgarian and Hungarian. We continued to combine runs produced through disparate retrievals, which, in the past, we have seen a modest (e.g., 10% relative) improvement. This year, however, we noted that our single-best tokenization method outperformed merging of disparate runs (compare Figure 1 and the results in Table 2). For bilingual retrieval we employed subword translation in several official runs, with good effect. However we still lack parallel corpora for Bulgarian and Hungarian. We would like to expand on these experiments if we can locate appropriate data. Our results from this year agree with previous findings that character n-grams remain effective and an attractive alternative, especially in languages with complex morphology or ones in which resources (e.g., morphological analyzers or stemmers) are difficult to obtain or use. Our recipe for bilingual retrieval appears effective, but is best accomplished when parallel data are available. [13] J. M. Ponte and W. B. Croft, ‘A Language Modeling Approach to Information Retrieval.’ In: Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Melbourne, Australia, pp. 275-281, 1998. [14] E. M. Zamora, J. J. Pollock, and A. Zamora, ‘The Use of Trigram Analysis for Spelling Error Detection.’ Information Processing and Management 17:305-316, 1981. [15] http://europa.eu.int/