This paper reports on the participation of ITC-irst in the Italian monolingual retrieval track and in the bilingual English-Italian track of the Cross Language Evaluation Forum (CLEF) 2002. A crosslanguage information retrieval systems is proposed which integrates retrieval and translation scores over the set of N-best translations of the source query. Translations are computed by a statistical translation model, based on an hidden Markov model, and trained over a bilingual dictionary and the target document collection. Retrieval scores result as a combination of a statistical language model and a standard Okapi model.
This paper reports on the participation of ITCirst in two Information Retrieval (IR) tracks of the Cross Language Evaluation Forum (CLEF) 2002: the monolingual retrieval task, and the bilingual retrieval task. The language of the queries was Italian for the monolingual track and English for the bilingual track; Italian documents were searched in both tracks. With respect to the 2001 CLEF evaluation (Bertoldi and Federico, 2002), the Cross Language IR (CLIR) system was modified in order to work with multiple translations of queries, and with source and target languages in the reverse order. The basic IR engine, used for both evaluations, combines scores of a standard Okapi model and of a statistical language model. For CLIR, a light-weight statistical model for translating queries was developed, which also computes the list of N-best translations for each query. In this way, the basic IR engine is used to integrate retrieval and translation scores over multiple translations (Federico and Bertoldi, 2002). Remarkably, training of the system just requires a bilingual dictionary and the target document collection. This paper is organized as follows. Section 2 introduces the statistical approach to CLIR. Sections 3 to 5 describe, respectively, the query-document model, the query-translation model, and the CLIR algorithm. Section 6 presents and discusses experimental results.
From a statistical perspective, the CLIR problem can be formulated as follows. Given a query f in the source language, by convention French, one would like to find relevant documents d in the target language, English, within a collection D. More formally, documents should be ranked according to the posterior probability:
where the right term of formula (1) follows from the application of Bayes formula and from the constancy of Pr(f ) with respect to the ranking of documents.
To fill the language difference between query and documents, the hidden variable e is introduced, which represents an English (term-by-term) translation of f . Hence, the following decomposition is derived:
In deriving formula (2), one makes the assumption (or approximation) that the probability of document d given query f and translation e, does not depend on f . Moreover, the main summation in (2) is taken over the set of possible translations of f . As terms of f may typically admit more than one translation, the size of this set can grow exponentially with the length of f . Finally, the denominator in formula (2) requires summing over all document in D and should be computed for every possible translation e.
In the following, statistical models will be described which, through suitable approximations, permit to efficiently compute formula (2). In particular, we will show how:
The query-document model computes the joint probability of a query e and a document d, written in the same language. Two query-document models were considered in the experiments. The former is based on a statistical model, the latter on the standard Okapi scoring function.
The joint probability of a query e a document d can be factored out as follows:
where Pr(e | d) represents the likelihood of e being generated by d, and Pr(d) the a-priori probability of d. In the following, no a-priori knowledge about the documents will be assumed, hence a uniform apriori distribution is taken 1 . For what concerns the probability of e given d, an order-free multinomial (bag-of-word) model is assumed. Hence, assuming e = e 1 , . . . , e n , we have2 :
Pr(e = e1, . . . , en
The probability of term q being generated by document d is estimated by the statistical LM:
where p(e), the word probability over D, is estimated by interpolating the smoothed relative frequency with the uniform distribution over the vocabulary V of D:
Parameters λ and µ are estimated according to (Witten and Bell, 1991).
The query-document model can also be based on a generic scoring function s(e, d). In order to obtain a distribution over queries and documents scores have to be normalized as follows:
The denominator of the above formula is considered only for the sake of normalization, but can be disregarded in the computation of equation ( 2).
In the experiments the following scoring function was used, whose logarithm corresponds to the standard Okapi formula:
where:
scores the relevance of w in d, and:
is the inverted document frequency. As in previous work, the setting k 1 = 1.5 and b = 0.4 were used.
An explanation of the involved terms can be found in (Robertson et al., 1994) and other papers referred in it.
Previous work (Bertoldi and Federico, 2001) showed that Okapi and the statistical model rank documents almost independently. Hence, information about the relevant documents can be gained by integrating the scores of both methods. Combination of the two models is implemented by just taking the sum of scores. Actually, in order to adjust scale differences, scores of each model are normalized in the range [0, 1] before summation. The resulting querydocument model was also applied to the monolingual IR track.
The query-translation model computes the probability of any query-translation pair. This probability is modelled by an HMM (Rabiner, 1990) in which the observable variable is the Italian query f , and the hidden variable is its English translation e. According to the HMM, the joint probability of a pair (f , e) is decomposed as follows:
Formula ( 11) puts in evidence two different conditional probabilities: the term translation probabilities p(f | e) and the target LM probabilities p(e | e ).
Given a query-document model and a query f , the most probable translation e * can be computed through the well known Viterbi search algorithm, while N -best translations of f can be computed with the tree-trellis based algorithm (Federico and Bertoldi, 2002). Probabilities p(f | e) are estimated from a bilingual dictionary as follows:
where δ(f, e) = 1 if the term e is one of the translations of term f and δ(f, e) = 0 otherwise. In Section 6, it will be explained how out-of-dictionary words are processed. where C(e, e ) is the number of co-occurrences appearing in the corpus, p(e) is computed according to equation ( 6), and the absolute discounting term β is equal to the estimate proposed in (Ney et al., 1994). Absolute discounting was chosen for its good performance and suitability to the order-free case.
The CLIR algorithm is in charge of computing formula (2) and sorting documents according to the posterior probability (1). The algorithm relies on two approximations in order to limit the set of possible translations and documents to be taken into account:
• external summation is taken over T N (f ), the set of the N -best translations of f , and
• internal summation is over I(e), the set of documents in D containing at least a word of e.
This corresponds to approximating formula (2) by:
Pr(e, d) The CLIR algorithm is illustrated in Table 2. Briefly, given an input query f , the N -best translations T N (f ) and their probabilities P [f , e] are computed first. Then, for each translation e, the addenda in formula (2) are computed only for documents containing at least one term of e. This requires one additional loop over the documents in order to compute the normalization term.
Four runs were submitted to CLEF 2002: one for the Italian monolingual track (IRSTit1) and 3 for the bilingual English-to-Italian track, using 1best, 5-best, and 10-best translation (IRSTen2it1, IRSTen2it2, and IRSTen2it3), respectively. The tracks consisted of 49 topics, for a total of 1072 documents to be retrieved, inside a collection of 108,578 Italian newspaper article from La Stampa and Swiss News Agency, both of 1994. All runs used only title and description parts of the topics.
Text preprocessing was applied on the target documents before indexing, and on the queries before retrieval. More specifically, the following preprocessing steps were carried out:
• Tokenization was performed on documents and queries to isolate words from punctuation marks, to recognize abbreviations and acronyms, correct possible word splits across lines, and discriminate between accents and quotation marks.
• Base forms were computed for Italian words by means of morphological analysis and POS tagging.
• Stemming was performed on English words by using the Porter's algorithm (Frakes and Baeza-Yates, 1992).
• Stop-terms removal was applied on the documents by removing terms with a low inverted document frequency (Frakes and Baeza-Yates, 1992).
• Proper names and numbers in the query were recognized in order to improve coverage of the dictionary.
• Out-of-dictionary terms which have not been recognized as proper names or numbers were removed from the query.
After document ranking, Blind Relevance Feedback (BRF) can be applied. BRF is a well known technique that allows to improve retrieval performance. The basic idea is to perform retrieval in two steps. First, the documents matching the source query e are ranked, then the B best ranked documents are taken and the R most relevant terms in them are added to the query, and the retrieval phase is repeated. In the CLIR framework, R terms are added to each single translation of the N -best list and the retrieval algorithms is repeated once again. In this work, new search terms are selected from the top B documents according to:
where r w is the number of documents, among the B top documents, which contain term w. In all the performed experiments the values B = 5 and R = 15 were used (Bertoldi and Federico, 2001). possible weakness in the preprocessing phase, poor coverage of the dictionary with respect to the terms in the queries, and any other possible causes of poor translation.