=Paper=
{{Paper
|id=Vol-1168/CLEF2002wn-adhoc-BertoldiEt2002
|storemode=property
|title=ITC-irst at CLEF 2002: Using N-best Query Translations for CLIR
|pdfUrl=https://ceur-ws.org/Vol-1168/CLEF2002wn-adhoc-BertoldiEt2002.pdf
|volume=Vol-1168
|dblpUrl=https://dblp.org/rec/conf/clef/BertoldiF02b
}}
==ITC-irst at CLEF 2002: Using N-best Query Translations for CLIR==
https://ceur-ws.org/Vol-1168/CLEF2002wn-adhoc-BertoldiEt2002.pdf
ITC-irst at CLEF 2002: Using N -best query translations for CLIR
Nicola Bertoldi and Marcello Federico
ITC-irst - Centro per la Ricerca Scientifica e Tecnologica
I-38050 Povo, Trento, Italy.
Abstract
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 cross-
language 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 trans-
lation 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.
1. Introduction where the right term of formula (1) follows from the
This paper reports on the participation of ITC- application of Bayes formula and from the constancy
irst in two Information Retrieval (IR) tracks of the of Pr(f ) with respect to the ranking of documents.
Cross Language Evaluation Forum (CLEF) 2002: the To fill the language difference between query and
monolingual retrieval task, and the bilingual retrieval documents, the hidden variable e is introduced,
task. The language of the queries was Italian for which represents an English (term-by-term) transla-
the monolingual track and English for the bilingual tion of f . Hence, the following decomposition is de-
track; Italian documents were searched in both tracks. rived:
With respect to the 2001 CLEF evaluation (Bertoldi
and Federico, 2002), the Cross Language IR (CLIR) X
Pr(f , d) = Pr(f , e, d)
system was modified in order to work with multi-
e
ple translations of queries, and with source and target X
languages in the reverse order. ≈ Pr(f , e) Pr(d | e)
The basic IR engine, used for both evaluations, com- e
X Pr(e, d)
bines scores of a standard Okapi model and of a sta- = Pr(f , e) P (2)
0
tistical language model. For CLIR, a light-weight sta- e d0 Pr(e, d )
tistical model for translating queries was developed,
which also computes the list of N-best translations for In deriving formula (2), one makes the assumption
each query. In this way, the basic IR engine is used to (or approximation) that the probability of document
integrate retrieval and translation scores over multiple d given query f and translation e, does not depend
translations (Federico and Bertoldi, 2002). Remark- on f . Moreover, the main summation in (2) is taken
ably, training of the system just requires a bilingual over the set of possible translations of f . As terms
dictionary and the target document collection. of f may typically admit more than one translation,
This paper is organized as follows. Section 2 intro- the size of this set can grow exponentially with the
duces the statistical approach to CLIR. Sections 3 to length of f . Finally, the denominator in formula (2)
5 describe, respectively, the query-document model, requires summing over all document in D and should
the query-translation model, and the CLIR algorithm. be computed for every possible translation e.
Section 6 presents and discusses experimental results. In the following, statistical models will be described
which, through suitable approximations, permit to ef-
2. Statistical CLIR Approach ficiently compute formula (2). In particular, we will
show how:
From a statistical perspective, the CLIR problem can
be formulated as follows. Given a query f in the • probability Pr(e, d) is computed by the query-
source language, by convention French, one would document model,
like to find relevant documents d in the target lan-
guage, English, within a collection D. More for- • probability Pr(f , e) is computed by the query-
mally, documents should be ranked according to the translation model,
posterior probability:
• formula (2) is computed and documents are
Pr(d | f ) ∝ Pr(f , d) (1) ranked by the CLIR algorithm.
Q, T, D random variables of query, translation, and document
f , e, d instances of source query, query translation, and document
w, f, e generic term, term in the source language, term in the target language
D collection of documents
V,V(d) set of terms occurring in D, and in document d
N, N (d) number of term occurrences in D, and in a document d
N (w), N (d, w), N (e, w) frequency of term w in D, in document d, and in query e
Nw number of documents in D which contain term w
|·| size of a set
Table 1: List of often used symbols.
3. Query-Document Model 3.2. Okapi Query-Document Model
The query-document model computes the joint The query-document model can also be based on a
probability of a query e and a document d, written generic scoring function s(e, d). In order to obtain a
in the same language. Two query-document models distribution over queries and documents scores have
were considered in the experiments. The former is to be normalized as follows:
based on a statistical model, the latter on the standard s(e, d)
Okapi scoring function. Pr(e, d) = P (7)
s(e0 , d0 )
e0 ,d0
3.1. Witten-Bell Query-Document Model The denominator of the above formula is considered
The joint probability of a query e and a document d only for the sake of normalization, but can be disre-
can be factored out as follows: garded in the computation of equation (2).
In the experiments the following scoring function
Pr(e, d) = Pr(e | d) Pr(d) (3) was used, whose logarithm corresponds to the stan-
dard Okapi formula:
where Pr(e | d) represents the likelihood of e be-
n
Y
ing generated by d, and Pr(d) the a-priori probability
s(e = e1 , . . . , en , d) = idf (ek )Wd (ek ) (8)
of d. In the following, no a-priori knowledge about
k=1
the documents will be assumed, hence a uniform a-
priori distribution is taken1 . For what concerns the where:
probability of e given d, an order-free multinomial N (d, w)(k1 + 1)
(bag-of-word) model is assumed. Hence, assuming Wd (w) = (9)
k1 (1 − b) + k1 b N (d) + N (d, w)
e = e1 , . . . , en , we have2 : l̄
Y
n scores the relevance of w in d, and:
Pr(e = e1 , . . . , en | d) = p(ek | d) (4) N − Nw + 0.5
k=1 idf (w) = (10)
Nw + 0.5
The probability of term q being generated by docu- is the inverted document frequency. As in previous
ment d is estimated by the statistical LM: work, the setting k1 = 1.5 and b = 0.4 were used.
N (d, e) An explanation of the involved terms can be found in
p(e | d) = λ + (1 − λ) p(e) (5) (Robertson et al., 1994) and other papers referred in
N (d)
it.
where p(e), the word probability over D, is estimated
by interpolating the smoothed relative frequency with 3.3. Combined Query-Document Model
the uniform distribution over the vocabulary V of D: Previous work (Bertoldi and Federico, 2001) showed
that Okapi and the statistical model rank documents
N (e) 1
p(e) = µ + (1 − µ) (6) almost independently. Hence, information about the
N |V|
relevant documents can be gained by integrating the
Parameters λ and µ are estimated according to (Wit- scores of both methods. Combination of the two
ten and Bell, 1991). models is implemented by just taking the sum of
scores. Actually, in order to adjust scale differ-
1
However, this model permits to apply any available ences, scores of each model are normalized in the
prior distribution on documents. range [0, 1] before summation. The resulting query-
2 document model was also applied to the monolingual
Notice the use of p(·) to indicate a probability com-
puted by a statistical model. IR track.
4. Query-Translation Model 5. CLIR Algorithm
The query-translation model computes the probabil- The CLIR algorithm is in charge of computing for-
ity of any query-translation pair. This probability is mula (2) and sorting documents according to the pos-
modelled by an HMM (Rabiner, 1990) in which the terior probability (1). The algorithm relies on two
observable variable is the Italian query f , and the hid- approximations in order to limit the set of possible
den variable is its English translation e. According to translations and documents to be taken into account:
the HMM, the joint probability of a pair (f , e) is de- • external summation is taken over TN (f ), the set
composed as follows: of the N -best translations of f , and
P r(f = f1 , . . . , fn , e = e1 , . . . , en ) • internal summation is over I(e), the set of doc-
Y n Y n uments in D containing at least a word of e.
= p(e1 ) p(ek | ek−1 ) p(fk | ek ) This corresponds to approximating formula (2) by:
k=2 k=1
X Pr(e, d)
(11) Pr(f , d) ≈ Pr(f , e) P 0
e∈TN (f ) d ∈I(e) Pr(e, d )
0
Formula (11) puts in evidence two different condi-
(15)
tional probabilities: the term translation probabilities
p(f | e) and the target LM probabilities p(e | e0 ).
Given a query-document model and a query f , 1. Input f
the most probable translation e∗ can be computed 2. Compute TN (f ) and scores P [f , e]
through the well known Viterbi search algorithm, 3. For each e ∈ TN (f )
while N -best translations of f can be computed 4. N = 0
with the tree-trellis based algorithm (Federico and 5. For each d ∈ I(e)
Bertoldi, 2002). 6. Compute P [e, d]
7. Update N = N + P [e, d]
Probabilities p(f | e) are estimated from a bilingual
8. For each d ∈ I(e)
dictionary as follows:
9. Update P [d] = P [d]+ P [e, d] ∗ P [f , e]/N
δ(f, e) 10. Order documents according to P [d]
Pr(f | e) = P 0
(12)
f 0 δ(f , e) Table 2: CLIR algorithm.
where δ(f, e) = 1 if the term e is one of the trans-
lations of term f and δ(f, e) = 0 otherwise. In The CLIR algorithm is illustrated in Table 2. Briefly,
Section 6, it will be explained how out-of-dictionary given an input query f , the N -best translations TN (f )
words are processed. and their probabilities P [f , e] are computed first.
Probabilities p(e | e0 ) are estimated on the target doc- Then, for each translation e, the addenda in formula
ument collection, through an order-free bigram LM, (2) are computed only for documents containing at
which tries to compensate for different word posi- least one term of e. This requires one additional loop
tions induced by the source and target languages. Let over the documents in order to compute the normal-
ization term.
p(e, e0 )
p(e | e0 ) = P 00 0
(13) 6. Experimental Evaluation
e00 p(e , e )
Four runs were submitted to CLEF 2002: one
where p(e, e0 ) is the probability of e co-occurring for the Italian monolingual track (IRSTit1) and
with e0 , regardless of the order, within a text win- 3 for the bilingual English-to-Italian track, using 1-
dow of fixed size. Smoothing of this probability is best, 5-best, and 10-best translation (IRSTen2it1,
performed through absolute discounting and interpo- IRSTen2it2, and IRSTen2it3), respectively.
lation as follows: The tracks consisted of 49 topics, for a total of
½ ¾ 1072 documents to be retrieved, inside a collection
0
C(e, e ) − β of 108,578 Italian newspaper article from La Stampa
p(e, e0 ) = max ,0 + βp(e)p(e0 ) (14)
N and Swiss News Agency, both of 1994. All runs used
only title and description parts of the topics.
where C(e, e0 ) is the number of co-occurrences ap-
pearing in the corpus, p(e) is computed according to 6.1. Preprocessing
equation (6), and the absolute discounting term β is Text preprocessing was applied on the target docu-
equal to the estimate proposed in (Ney et al., 1994). ments before indexing, and on the queries before re-
Absolute discounting was chosen for its good perfor- trieval. More specifically, the following preprocess-
mance and suitability to the order-free case. ing steps were carried out:
• Tokenization was performed on documents Official Run N-best mAvPr
and queries to isolate words from punctu- IRSTit1 .4920
ation marks, to recognize abbreviations and IRSTen2it1 1 .3444
acronyms, correct possible word splits across IRSTen2it2 5 .3531
lines, and discriminate between accents and IRSTen2it3 10 .3552
quotation marks.
Table 3: Results of the official runs.
• Base forms were computed for Italian words by
means of morphological analysis and POS tag-
ging. Official Run < mdn > mdn wrs bst
IRSTit1 11 37 0 7
• Stemming was performed on English words by IRSTen2it1 21 24 3 5
using the Porter’s algorithm (Frakes and Baeza- IRSTen2it2 19 26 2 2
Yates, 1992). IRSTen2it3 16 26 2 6
• Stop-terms removal was applied on the docu- Table 4: Results of the official runs against the worst,
ments by removing terms with a low inverted median and best values.
document frequency (Frakes and Baeza-Yates,
1992). possible weakness in the preprocessing phase, poor
• Proper names and numbers in the query were coverage of the dictionary with respect to the terms
recognized in order to improve coverage of the in the queries, and any other possible causes of poor
dictionary. translation.
• Out-of-dictionary terms which have not been 7. References
recognized as proper names or numbers were re- Bertoldi, N. and M. Federico, 2001. ITC-irst at
moved from the query. CLEF 2000: Italian monolingual track. In Peters
(ed.), Cross-Language Information Retrieval and
6.2. Blind Relevance Feedback Evaluation, vol. 2069 of LNCS, pages 261–272.
After document ranking, Blind Relevance Feedback Springer Verlag.
(BRF) can be applied. BRF is a well known tech- Bertoldi, N. and M. Federico, 2002. ITC-irst at
nique that allows to improve retrieval performance. CLEF 2001: Monolingual and bilingual tracks.
The basic idea is to perform retrieval in two steps. In Peters, et al. (eds.), Cross-Language Informa-
First, the documents matching the source query e are tion Retrieval and Evaluation, vol. 2406 of LNCS,
ranked, then the B best ranked documents are taken pages 94–101. Springer Verlag.
and the R most relevant terms in them are added to Federico, M. and N. Bertoldi, 2002. Statistical cross-
the query, and the retrieval phase is repeated. In the language information retrieval using n-best query
CLIR framework, R terms are added to each single translations. In Proc. of 25th International ACM
translation of the N -best list and the retrieval algo- SIGIR. Tampere, Finland.
rithms is repeated once again. Frakes, W. B. and Ricardo Baeza-Yates (eds.), 1992.
In this work, new search terms are selected from the Information Retrieval: Data Structures and Algo-
top B documents according to: rithms. Prentice Hall.
(rw + 0.5)(N − Nw − B + rw + 0.5) Ney, H., U. Essen, and R. Kneser, 1994. On struc-
rw (16) turing probabilistic dependences in stochastic lan-
(Nw − rw + 0.5)(B − rw + 0.5)
guage modelling. Computer Speech and Lan-
where rw is the number of documents, among the B guage, 8:1–38.
top documents, which contain term w. In all the per- Rabiner, L. R., 1990. A tutorial on hidden Markov
formed experiments the values B = 5 and R = 15 models and selected applications in speech recog-
were used (Bertoldi and Federico, 2001). nition. In Weibel and Lee (eds.), Readings
in Speech Recognition, pages 267–296. Morgan
6.3. Official Results Kaufmann.
Table 6.3. reports official results of the submitted Robertson, S. E., S. Walker, S. Jones, M. M.
runs, and Table 6.3. compares them with the worst, Hancock-Beaulieu, and M. Gatford, 1994. Okapi
median, and best results of competitors. at TREC-3. In Proc. of 3rd TREC. Gaithersburg,
With respect to previous evaluations, this year we had MD.
to perform query translation in the reverse order, i.e. Witten, I. H. and T. C. Bell, 1991. The zero-
from English to Italian. Given the large gap between frequency problem: Estimating the probabilities of
monolingual and cross-lingual results, i.e. about 15% novel events in adaptive text compression. IEEE
absolute, future work will be devoted to investigate Trans. Inform. Theory, IT-37(4):1085–1094.