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.
Introduction 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
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
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:
Pr(d j f ) / Pr(f ; d) 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:
Pr(f ; d) =
X Pr(f ; e; d) ¼ =
e X Pr(f ; e) Pr(d j e)
e Xe Pr(f ; e) Pd0 Pr(e; d0)
Pr(e; d) (2) 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: ² probability Pr(e; d) is computed by the query
document model, ² probability Pr(f ; e) is computed by the query
translation model, ² formula (2) is computed and documents are ranked by the CLIR algorithm.
Q; T; D f ; e; d w; f; e D V,V(d) N; N (d) N (w); N (d; w); N (e; w) Nw j ¢ j random variables of query, translation, and document instances of source query, query translation, and document generic term, term in the source language, term in the target language collection of documents set of terms occurring in D, and in document d number of term occurrences in D, and in a document d frequency of term w in D, in document d, and in query e number of documents in D which contain term w size of a set 3.
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. 3.1.
Witten-Bell Query-Document Model The joint probability of a query e and a document d can be factored out as follows:
Pr(e; d) = Pr(e j d) Pr(d) (3) where Pr(e j 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 taken1. For what concerns the probability of e given d, an order-free multinomial (bag-of-word) model is assumed. Hence, assuming e = e1; : : : ; en, we have2: n Pr(e = e1; : : : ; en j d) = Y p(ek j d) k=1 The probability of term q being generated by document d is estimated by the statistical LM:
N (d; e) p(e j d) = ¸ N (d) + (1 ¡ ¸) p(e) 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: p(e) = ¹ N (e)
N
+ (1 ¡ ¹)
1
jVj
Parameters ¸ and ¹ are estimated according to
1However, this model permits to apply any available prior distribution on documents.
2Notice the use of p(¢) to indicate a probability computed by a statistical model. (4) (5) (6) 3.2.
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:
Pr(e; d) = Pe0;d0 s(e0; d0) s(e; d) 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: n Y idf (ek)Wd(ek) k=1 s(e = e1; : : : ; en; d) = where: Wd(w) =
N (d; w)(k1 + 1) k1(1 ¡ b) + k1b N(d) + N (d; w) ¯ l scores the relevance of w in d, and: idf (w) = N ¡ Nw + 0:5
Nw + 0:5
is the inverted document frequency. As in previous
work, the setting k1 = 1:5 and b = 0:4 were used.
An explanation of the involved terms can be found in
The query-translation model computes the
probability of any query-translation pair. This probability is
modelled by an HMM
P r(f = f1; : : : ; fn; e = e1; : : : ; en)
n n = p(e1) Y p(ek j ek¡1) Y p(fk j ek)
k=2 k=1
Formula (11) puts in evidence two different
conditional probabilities: the term translation probabilities
p(f j e) and the target LM probabilities p(e j e0).
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
Probabilities p(f j e) are estimated from a bilingual dictionary as follows:
Pr(f j e) = Pf0 ±(f 0; e) ±(f; e) 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.
Probabilities p(e j e0) are estimated on the target document collection, through an order-free bigram LM, which tries to compensate for different word positions induced by the source and target languages. Let 5. 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 TN (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:
X e2TN (f )
Pr(f ; e) P
Pr(e; d) d02I(e) Pr(e; d0) (15) (11)
Pr(f ; d) ¼ (12) (13) p(e j e0) =
p(e; e0)
Pe00 p(e00; e0) where p(e; e0) is the probability of e co-occurring with e0, regardless of the order, within a text window of fixed size. Smoothing of this probability is performed through absolute discounting and interpolation as follows: p(e; e0) = max ½ C(e; e0) ¡ ¯
N
; 0
¾
+ ¯p(e)p(e0) (14)
where C(e; e0) 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
The CLIR algorithm is illustrated in Table 2. Briefly, given an input query f , the N -best translations TN (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.
6.
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
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:
rw
(rw + 0:5)(N ¡ Nw ¡ B + rw + 0:5)
(Nw ¡ rw + 0:5)(B ¡ rw + 0:5)
(16)
where rw 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
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.
7.