This work is an extension of our proposal originally presented in CLEF 2006, which, unfortunately, could not be ready on time for the workshop. We describe here a knowledge-light approach for query translation in Cross-Language Information Retrieval systems. This proposal itself can be considered as an extension of the previous work of the Johns Hopkins University Applied Physics Lab, preserving its advantages but avoiding its main drawbacks. As in their original proposal, our work is based on the direct translation of character n-grams, avoiding in this way the need for word normalization during indexing or translation, and also dealing with out-of-vocabulary words. Moreover, since such a solution does not rely on language-speci c processing, it can be used with languages of very di erent natures even when linguistic information and resources are scarce or unavailable. Nevertheless, in contrast with the original approach, our proposal is much faster and transparent, making extensive use of freely available resources. The system has been tested in the robust ad-hoc English-to-French bilingual task, obtaining encouraging results.
Sunderland { SR6 0DD (UK)
This work is an extension of the proposal originally presented by our group in the previous CLEF
edition, a new knowledge-light approach for query translation in Cross-Language Information
Retrieval (CLIR) systems based on the direct translation of character n-grams. Such a proposal
itself can be considered as an extension of the previous work of the Johns Hopkins University
Applied Physics Lab (JHU/APL) on the employment of overlapping character n-grams for indexing
documents [
The interest in using overlapping character n-grams comes from the fact that it provides a surrogate means to normalize word forms and to allow to manage languages of very di erent natures without further processing. Such a knowledge-light approach does not rely on languagespeci c processing, and it can be used even when linguistic information and resources are scarce or unavailable.
In the case of monolingual retrieval, the employment of n-grams is quite straightforward, since both queries and documents are just tokenized into overlapping n-grams instead of words: the word tomato, for example, is split into -tom-, -oma-, -mat- and -ato-. The resulting n-grams are then processed by the retrieval engine either for indexing or querying. Nevertheless, when extending its use to the case of CLIR, an extra translation phase is needed during querying.
Aiming to avoid some of the limitations of classic dictionary-based translation methods, such
as the need for word normalization or the inability to handle out-of-vocabulary words, JHU/APL
researchers developed a direct n-gram translation algorithm which allows translation not at the
word level but at the n-gram level [
This paper describes a new direct n-gram alignment proposal we have developed both to speed up the process and to make the system more transparent. The article is structured as follows. Firstly, Sect. 2 describes our approach. Next, in Sect. 3, our proposal is evaluated. Finally, in Sect. 4, we present our conclusions and future work. 2
Taking as our model the system designed by JHU/APL, we developed our own n-gram based
retrieval system, trying to preserve the advantages of the original proposal but avoiding its main
drawbacks. Moreover, instead of the ad-hoc resources developed for the original system [
Nevertheless, the main di erence is the n-gram alignment algorithm itself, which now consists
of two phases. In the rst phase, the slowest one, the input parallel corpus is aligned at the
word-level using the well-known statistical tool GIZA++ [
Next, prior to the second phase, heuristics can be applied |if desired| for re ning or
modifying the word-to-word translation scores calculated by GIZA++. In our case, we have removed
those least-probable word alignments from the input (those with a word translation probability
less than a threshold W , with W =0.15) [
Finally, in the second phase, n-gram translation scores are computed employing statistical
association measures [
As we can see, this rst step acts as an initial lter, since only those n-gram pairs corresponding to aligned words will be considered, whereas in the original JHU/APL approach all n-gram pairs corresponding to aligned paragraphs were considered. This approach increases the speed of the process by concentrating most of the complexity in the word-level alignment phase, allowing ngram alignment techniques to be easily tested. 2.1
Word-level alignment using association measures
Our n-gram alignment algorithm is an extension of the way association measures can be used for
creating bilingual word dictionaries taking as input parallel collections aligned at the paragraph
level [
S = ws S 6= ws
T = wt
T 6= wt O11 O21 = C1
O12 O22 = C2 = R1 = R2 = N As shown, the rst row accounts for those instances where the source language paragraph contains ws, while the rst column accounts for those instances where the target language paragraph contains wt. The cell counts are called the observed frequencies: O11, for example, stands for the number of aligned paragraphs where the source language paragraph contains ws and the target language paragraph contains wt; O12 stands for the number of aligned paragraphs where the source language paragraph contains ws but the target language paragraph does not contain wt; and so on. The total number of word pairs considered |or sample size N | is the sum of the observed frequencies. The row totals, R1 and R2, and the column totals, C1 and C2, are also called marginal frequencies and O11 is called the joint frequency.
Once the contingency table has been built, di erent association measures can be easily calculated for each word pair. The most promising pairs, those with the highest association measures, are stored in the bilingual dictionary. 2.2
Adaptations for n-gram-level alignment We have described how to compute and use association measures for generating bilingual word dictionaries from parallel corpora. However, in our case we do not start with aligned paragraphs composed of words, but aligned words |previously aligned through GIZA++| composed of character n-grams. A rst choice for adapting the previous word-level alignment algorithm to the case of n-grams could be just to adapt the contingency table to the new context, by considering that we are managing n-gram pairs (gs; gt) cooccurring in aligned words instead of word pairs (ws; wt) cooccurring in aligned paragraphs. So, contingency tables should be adapted accordingly: O11, for example, should be re-formulated as the number of aligned word pairs where the source language word contains n-gram gs and the target language word contains n-gram gt.
However, we do not have real instances of n-gram cooccurrences at aligned words, but just
probable ones, since GIZA++ uses a statistical alignment model which computes a translation
probability for each cooccurring word pair [
prob. milk milky milk leche lechoso tomate Our proposal consists of weighting the likelihood of a cooccurrence according to the probability of its containing word alignments. So, the resulting contingency tables corresponding to the n-gram pairs (-milk-, -lech-) and (-milk-, -toma-) are as follows:
T = -lech
T 6= -lechS = -milk
O11 = 0:98 + 0:92 =1.90
O12 = 0:98 + 3 0:92 + 3 0:15 =4.19 S 6= -milk
S = -milkS 6= -milk
O11 =0.15
O12 = 2 0:98 + 4 0:92 + 2 0:15 =5.94 O21 =0.92 Notice that, for example, the O11 frequency corresponding to (-milk-, -lech-) is not 2 as might be expected, but 1.90. This is because the pair appears in two word alignments |milk{leche and milky{lechoso|, but each cooccurrence in an alignment has been weighted according to its translation probability:
O11 = 0.98 (for milk{leche) + 0.92 (for milky{lechoso) = 1.90 .
Once the contingency tables have been generated, the association measures corresponding to each
n-gram pair can be computed. In contrast with the original JHU/APL approach [
Dice(gs; gt) =
2O11 R1 + C1 : (1)
M I(gs; gt) = log N O11 : (2)
R1C1 logl(gs; gt) = 2 X Oij log N Oij : (3) i;j RiCj If using the Dice coe cient, for example, we nd that the association measure of the pair (-milk-, -lech-) |the correct one| is much higher than that of the pair (-milk-, -toma-) |the wrong one:
Dice(-milk-, -lech-) = 6:09+2:82 = 0.43 .
2 1:90 Dice(-milk-, -toma-) = 6:09+0:15 = 0.05 .
2 0:15 Notice that if we consider that a real existing cooccurrence instance corresponds to a 100% probability, we can think about the original word-based algorithm described in Sect. 2.1 as a particular case of the generalized n-gram-based algorithm we have proposed here with n=1. 0.2 0 0.8 0.2
0
Since the lack of time did not allow us to have our n-gram direct translation tool ready on time for
the past CLEF 2006 workshop [
The robust task is essentially an ad-hoc task which re-uses the topics and collections from past
CLEF editions [
With respect to the indexing process, documents were simply split into n-grams and indexed,
as were the queries. We have used 4-grams as a compromise n-gram size after studying the results
previously obtained by the JHU/APL group [
For querying, the source language topic is rstly split into n-grams. Next, these n-grams are
replaced by their N most probable alignments.3 The resulting translated topics are then submitted
to the retrieval system.4 Because of the lack of time, we could not tune the N value for this new
set of English-to-French experiments, so we decided to take those values used in our previous
English-to-Spanish experiments [
Dice coe cient Mutual Information Log-likelihood
N =1 N =10 N =1 Finally, Fig. 1 and Fig. 2 show the results obtained for each association measure: the Dice coefcient (EN2FR Dice), Mutual Information (EN2FR MI), and log-likelihood (EN2FR logl). We also show the results for two baselines: by querying the French index with the initial English topics split into 4-grams (EN) |allowing us to measure the impact of casual matches|, and by querying the index using the French topics split into 4-grams (FR) |i.e. a French monolingual run and our ideal performance goal. Notice that mean average precision (MAP) values are also given. 2Inverse Document Frequency model with Laplace after-e ect and normalization 2. 3With N 2 f1; 2; 3; 5; 10; 20; 30; 40; 50; 75; 100g.
4A second selection algorithm, consisting of taking those alignments with a probability greater or equal than
a threshold T , was also used in previous experiments [
Documents retrieved (D)
These results show that the log-likelihood measure obtains the best results for both topic sets, although no signi cant di erence is found with respect to Dice.5 On the other hand, both approaches perform signi cantly better than mutual information.
Although we still need to improve our results in order to reach our ideal performance goal, our current results are encouraging, since it must be taken into account that these are still our rst experiments, so the margin for improvement is still great. 4
This paper extends the proposal originally presented in CLEF 2006 for the development of a CLIR
system which uses character n-grams not only as indexing units, but also as translation units. This
system was inspired by the work of the Johns Hopkins University Applied Physics Lab [
Moreover, since such a solution does not rely on language-speci c processing, it can be used with languages of very di erent natures even when linguistic information and resources are scarce or unavailable. Nevertheless, in contrast with the original approach, our proposal is much faster and transparent, making extensive use of freely available resources.
So, the n-gram alignment algorithm described consists of two phases. In the rst phase, the slowest one, word-level alignment of the text is made through a statistical alignment tool. In the second phase, n-gram translation scores are computed employing statistical association measures, taking as input the translation probabilities calculated in the previous phase. This new approach speeds up the training process, concentrating most of the complexity in the word-level alignment phase, making the testing of new association measures for n-gram alignment easier.
With respect to our future work, new tests with other languages of di erent characteristics
are being prepared in order to complete the tuning of the system, including the possibility of
removing high or low-frequency n-grams, the employment of relevance feedback, or the use of pre
or post-translation expansion techniques in the case of translingual runs [
This research has been partially funded by the European Union (FP6-045389), Ministerio de Educacion y Ciencia and FEDER (TIN2004-07246-C03 and HUM2007-66607-C04), and Xunta de Galicia 5Two-tailed T-tests over MAPs with =0.05 have been used along this work. (PGIDIT05PXIC30501PN, PGIDIT05SIN044E, and Rede Galega de Procesamento da Linguaxe e Recuperacion de Informacion). The authors would also like to thank John I. Tait for his support.