The Johns Hopkins University Applied Physics Laboratory participated in three of the five tasks of the CLEF-2001 evaluation, monolingual retrieval, bilingual retrieval, and multilingual retrieval. In this paper we describe the fundamental methods we used and we present initial results from three experiments. The first investigation examines whether residual inverse document frequency can improve the term weighting methods used with a linguisticallymotivated probabilistic model. The second experiment attempts to assess the benefit of various translation resources for cross-language retrieval. Our last effort is to improve cross-collection score normalization, a task essential for the multilingual problem.
The Hopkins Automated Information Retriever for Combing Unstructured Text (HAIRCUT) is a research
retrieval system developed at the Johns Hopkins University Applied Physics Laboratory (APL). The design
of HAIRCUT was influenced by a desire to compare various methods for lexical analysis and tokenization;
thus the system has no commitment to any particular method. With western European languages we typically
use both unstemmed words and overlapping character n-grams as indexing terms, and previous
experimentation has led us to believe that a combination of both approaches enhances performance [
692,745 4,154,405 235,710 3,118,973 479,682 2,966,390 1,670,316 5,028,002 1,323,283 3,333,537 382,664 3,339,343
The use of overlapping character n-grams provides a surrogate form of morphological normalization. For
example, in Table 2 above, the n-gram “minist” could have been generated from several different forms like
administer, administrative, minister, ministers, ministerial, or ministry. It could also come from an unrelated
word like feminist. Another advantage of n-gram indexing comes from the fact that n-grams containing
spaces can convey phrasal information. In the table above, 6-grams such as “rime-m”, “ime-mi”, and
“memin” may act much like the phrase “prime minister” in a word-based index using multiple word phrases.
At last year’s workshop we explored language-neutral retrieval and avoided the use of stopword lists,
lexicons, decompounders, stemmers, lists of phrases, or manually-built thesauri [
We conducted our work on four Sun Microsystems workstations that are shared with about 30 other researchers. Each machine has at least 1GB of physical memory and we have access to dedicated disk space of about 200GB. The use of character n-grams increases the size of both dictionaries and inverted files, typically by a factor of five or six, over those of comparable word-based indices. Furthermore, when we use pseudo-relevance feedback we use a large number of expansion n-grams. As a consequence, runtime performance became an issue that we needed to address. Over the last year we made a number of improvements to HAIRCUT to reduce the impact of large data structures, and to allow the system to run in less memory-rich environments.
To minimize the memory consumption needed for a dictionary in a large term-space, we developed a
multitiered cache backed by a B-tree. If sufficient memory is available, term/term-id pairs are stored in a hash
table; if the hash table grows too large, entries are removed from the table, but still stored in memory as
compressed B-tree nodes; if the system then runs out of memory data are written to disk.
To reduce the size of our inverted files we applied gamma compression [
HAIRCUT performs rudimentary preprocessing on topic statements to remove stop structure, e.g., phrases such as “… would be relevant” or “relevant documents should….” . We have constructed a list of about 1000 such English phrases from previous topic sets (mainly TREC topics) and these have been translated into other languages using commercial machine translation. Other than this preprocessing, queries are parsed in the same fashion as documents in the collection.
In all of our experiments we used a linguistically motivated probabilistic model for retrieval. Our official runs all used blind relevance feedback, though it did not improve retrieval performance in every instance. To perform relevance feedback we first retrieved the top 1000 documents. We then used the top 20 documents for positive feedback and the bottom 75 documents for negative feedback; however, we removed any duplicate or near duplicate documents from these sets. We then select terms for the expanded query based on three factors, a term’s initial query term frequency (if any); the cube root of the (α=3, β=2, γ=2) Rocchio score; and a term similarity metric that incorporates IDF weighting. The 60 top ranked terms are then used as the revised query with words as indexing terms; 400 terms are used with 6-grams. In previous work we penalized documents containing only a fraction of the query terms; we are no longer convinced that this technique adds much benefit and have discontinued its use. As a general trend we observe a decrease in precision at very low recall levels when blind relevance feedback is used, but both overall recall and mean average precision are improved.
Once again our approach to monolingual retrieval focused on language-independent methods. We submitted
two official runs for each target language, one using the mandated <title> and <desc> fields (TD runs) and
one that added the <narr> field as well (TDN runs), for a total of 10 submissions. These official runs were
automated runs formed by combining results from two base runs, one using words and one using n-grams.
In all our experiments we used a linguistically motivated probabilistic model. This model has been described
in a report by Hiemstra and de Vries [
Sim(q, d ) = ∏ (a ⋅ f (t, d ) + (1 - a ) ⋅ mrdf (t)) f (t,q)
t = terms
Equation 1. Similarity calculation. where f(t,d) is the relative frequency of term t in document d (or query q) and mrdf(t) denotes the mean relative document frequency of t. The parameter α is a tunable parameter that can be used to ascribe a degree of importance to a term. For our baseline system we simply fix the value of α at 0.3 when words are used as indexing terms. Since individual n-grams tend to have a lower semantic value than words a lower α is indicated; we use a value of 0.15 for 6-grams. In training experiments using the TREC-8 test collection we found performance remained acceptable across a wide range of values. When blind relevance feedback is applied we do not adjust this importance value, and instead just expand the initial query.
TD Cmb
TD Six
TD Words
TDN Cmb
TDN Six
TDN Words
We were interested in performing an experiment to see if baseline performance could be improved by
adjusting the importance parameter α for each query term, Residual inverse document frequency (RIDF) [
⎛ 1 ⎞ RIDF(t) = IDF (t) - log⎜
⎝ 1- e-cf (t) ⎟⎠ Equation 2. Computing residual inverse document frequency for a term. The log term in the equation represents the expected IDF if the term had a Poisson distribution.
Our approach was as follows. For each query term, we adjust the importance value, α, for each term depending on RIDF. We linearly interpolate the RIDF value based on the minimum and maximum values in the collection and multiply by a constant k to determine the adjusted α . For these initial experiments we only considered k=0.2 .
a(t) = abaseline + k ⋅
RIDF (t) - RIDFmin
RIDFmax - RIDFmin
Equation 3. Computing a term-specific value for α .
We are still analyzing these results, however the preliminary indications are promising. Figure 2 shows the change in average precision when applying this rudimentary method. We observe a small positive effect, particularly with intermediate-length queries. One possible explanation for why the improvement does not occur with very short queries (e.g., title-only) is because these queries are unlikely to contain low-RIDF terms (being short and to the point), and the adjustment in importance value is unwarranted. As yet, we have no explanation for why long queries (TDN or those with expanded queries) do not seem to gain much with this method. As time permits an analysis of individual topics may reveal what is happening.
Our goal for the bilingual task was to assess retrieval performance when four approaches to query translation are used, commercial machine translation software; publicly available bilingual wordlists; parallel corpora mined from the Web; and untranslated queries. The last is only likely to succeed when languages share word roots. We wanted to attempt as many of the topic languages as possible, and managed to use all but Thai. In the past we observed good performance when commercial machine translation is used, and so all of our official runs used MT. Since only four official runs were permitted, we had a hard time choosing which topic languages to use. We attempted the Dutch bilingual task as well as the English task and ended up submitting runs using French, German, and Japanese topics against English documents, and using English topics for the Dutch documents. aplbifren aplbideen aplbijpen aplmoenb topic fields
TD TD TD TD average precision 0.3519 0.4195 0.3285 0.4471 % mono 78.7% 93.8% 73.5%
-aplbiennl TD 0.2707 77.4% aplmonlb TD 0.3497 -Table 3. Official results for the bilingual task
recall At the time of this writing we are still working on our dictionary and corpus-based methods, and will present results from these experiments in a revised version of this manuscript. We now discuss some experiments on the English bilingual collection using MT-translated and untranslated queries. Systran supports translation from Chinese, French, German, Italian, Japanese, Russian, and Spanish to (American) English; to translate Dutch, Finnish, and Swedish topics we used the on-line translator at http://www.tranexp.com/. High quality machine translation can result in excellent cross-language retrieval; our official bilingual runs achieve 81% of the performance (on average) of a comparable monolingual baseline.
Although we generally use relevance feedback and are accustomed to seeing a roughly 25% boost in performance from its use, we observed that it was not always beneficial. This was especially the case with longer queries (TDN vs. Title-only) and when the translation quality was very high for the language pair in question. In Figure 3 (below), we compare retrieval performance using words as indexing terms when relevance feedback is applied. When 6-grams were used the results were similar.
Relevance Feedback Not Always Helpful T T+RF TD TD+RF TDN TDN+RF EN*
DE
ES
FI
FR
IT
JP
NL
RU
SV
ZH
Source Language <FR-title> Of the pesticides in food for babies <FR-desc> To seek documents on the pesticides in food for babies. <IT-title> Pesticidi in the alimony for children <IT-desc> Trova documents that they speak about the pesticidi in the alimony for children. <JP-title>Damage by disease and pest pest control medicine in baby hood <JP-desc>The article regarding the damage by disease and pest pest control medicine in the baby hood was searched to be. <NL-title> Pesticide within babyvoeding <NL-desc> Missing unpleasant documents via pesticide within babyvoeding. <RU-title> pesticides in the children's nourishment of <RU-desc> to find articles about the pesticides in the children's nourishment of <SV-title> Bekdmpningsmedel a baby <SV-desc> Svk report a bekdmpningsmedel a baby. <ZH-title> In baby food includes report which in pesticide <ZH-desc> inquiry concerned baby food includes pesticide.
The Finnish translations are poor in quality, which explains the rather low relative performance when those
topics were used. However, looking over the translated topics we observe that many untranslated terms are
near cognates to the proper English word. For example, pestizide (German), pesticidas (Spanish), and
pesticidi (Italian) are easily recognizable. Similarly, ‘baby hood’ is phonetically similar to ‘baby food’, an
easy to understand mistake when Japanese phonetic characters are used to transliterate a term.
In TREC-6, Buckley et al. explored cross-language English to French retrieval using cognate matches [
While Buckley et al. manually developed rules to spell-correct English into French, this work may be entirely unnecessary when n-gram indexing is used, since n-grams provide a form of morphological normalization. Thus we consider a more radical hypothesis than ‘English is misspelled French’, namely, ‘other languages are English.’ We now examine more closely the relative performance observed when words and 6-grams are used without spelling correction.
Figure 4 is a plot that compares the efficacy of machine-translated queries to untranslated queries for the English bilingual task. Since we have argued that relevance feedback does not have a large effect, we will only compare runs that do not use it. The data in the leftmost column is a monolingual English baseline, the unstarred columns in the central region are runs using machine translation for various source languages, and the rightmost area contains runs that used untranslated source language queries against the English collection. For each combination of translation method and source language six runs are shown using titleonly, TD, or TDN topic statements and either words or 6-grams.
Several observations can be made from this plot. First, we observe that longer topic statements tend to do better than shorter ones; roughly speaking, TDN runs are about 0.05 higher than corresponding TD runs, and TD runs are about the same amount better than title-only runs. Secondly we note that 6-grams tend to outperform words; the mean relative difference among comparable MT runs is 5.95%. Looking at the various source languages we note that as a group, the Systran translated runs (DE, ES, FR, IT, JP, RU, and ZH) outperform the InterTran translated queries (FI, NL, and SV); this may reveal an underlying difference in product quality, however a better comparison would be to use languages they translate in common. Translation quality is rather poor for the Finnish and Swedish topics (InterTran) and also with the Chinese topics (Systran). Averaging across all source languages, the translated runs have performance between 4163% of the top monolingual English run when words are used, and 41-70% when 6-grams are used. The untranslated queries plotted on the right clearly do worse than their translated equivalents. Averaging across the seven languages encoded in ISO-8859-1, word runs achieve performance between 9-15% of the top monolingual English run, but 6-gram runs do much better and get performance between 22-34% depending on the topic fields used. The mean relative advantage when n-grams are used on these topics is 183%, almost a doubling in efficacy over words. The 6-grams achieve 54% of the performance of the machine-translated runs. Though not shown in the plot, relevance feedback actually does enhance these untranslated 6-gram runs even though we have shown that relevance feedback did not significantly affect translated topics. One final observation is that shorter queries are actually better when words are used; we suspect that this is because longer topics may contain more matching words, but not necessarily the key words for the topic.
One concern we have with this analysis is that we are comparing an aggregate measure, mean average precision. For untranslated topics, we imagine that the variance in performance is greater over many topics since some topics will have almost no cognate matches. We hope to examine individual topic behavior in the future.
We looked for this effect in other measures besides average precision. Recall at 1000 documents was effectively doubled when 6-grams were used instead of words; roughly 70% of the monolingual recall was observed. Averaged across language, Precision at 5 documents was 0.1921 when 6-grams were used with TDN topics with blind relevance feedback. Thus even this rudimentary approach can expected to find one relevant document on average in the top five documents.
EN* DE ES FI FR IT JP NL RU SV ZH DE* ES* FI* FR* IT* NL* SV*
When combining several runs, one must either use document rank as a measure of the importance of a document, or try to make some sense out of system-generated scores. Using rank is problematic when the two runs cover different documents. For example, if a different index is built for each language in a multilingual retrieval task, there is no way to distinguish a language that has many relevant documents from one that has few or no relevant documents using rank alone. On the other hand, raw scores are not typically comparable. For example, the scores produced by our statistical language model are products, with one factor per query term. Even if the individual factors were somehow comparable (which they are not), there is no 0.50 ion0.40 s i c e r eP0.30 g a r e v nA0.20 a e M 0.10 0.00 Words T Words TD Words TDN Six T Six TD Six TDN guarantee that a query will have the same number of terms when translated into two or more different languages. Other similarity metrics suffer from similar difficulties. Thus, score normalization is crucial if scores are to be used for run combination.
We tried a new score normalization technique this year. We viewed scores as masses, and normalized by
dividing each individual score by the sum of the masses of the top 1000 documents. (Because our
probabilistic calculations are typically performed in log space, and scores are therefore negative, we achieved
the desired effect by using the reciprocal of a document's score as its mass.) Our previous method of score
normalization was to interpolate scores for a topic within a run onto [
We are still investigating rank-based combination as well, though we submitted no official runs using this
technique. Our preliminary findings show little difference compared to score-based combination.
We were intrigued by a method that the U.C. Berkeley team used for multilingual merging in TREC-7 [
topic fields
TD TDN index type(s) words + 6-grams words aplmuena aplmuenb aplmuenc TD unified
words aplmuend TD words +
6-grams aplmuene TD unified
5-grams Table 4. Multilingual results Conclusions normalization method
mass contribution
mass contribution
NA linear interpolation
NA average precision 0.2979
Our second experiment is only partially completed; we compared bilingual retrieval performance when two query translation methods are used. The first method using extant commercial machine translation gives very good results that approach a monolingual baseline. We also showed that reasonable performance can be obtained when no attempt whatsoever is made at query translation, and we have demonstrated that overlapping character n-grams have a strong advantage over word-based retrieval in this scenario. The method is of course only practicable when related languages are involved. We think this result is significant for several reasons. First, it quantifies a lower bound for bilingual performance that other approaches may be measured against. Secondly, it implies that translation to a related language, when translation to the target language of interest is infeasible, may form the basis of a rudimentary retrieval system. We hope to augment this work by also comparing the use of parallel corpora and publicly available bilingual dictionaries in the near future.
Multilingual retrieval, where a single source language query is used to search for documents in multiple target languages, remains a critical challenge. Our attempt to improve cross-collection score normalization was not successful. We will continue to investigate this problem, which will only grow more difficult as a greater number of target languages is considered.