For our first participation in CLEF multilingual task, We present a new approach to obtain a single list of relevant documents for CLIR systems based on query translation. This new approach, which we call two-step RSV, is based on the re-indexing of the retrieval documents according to the query vocabulary, and it performs noticeably better than traditional methods.
how frequent such a term is in the rest of the documents, that is, the inverse document frequency
(idf ) [
RSVi0 =
RSVi
max(RSV )
, 1 <= i <= N
• A variant of the previous method is to divide each RSV by the difference between the
maximum and minimum document score values reached in each collection [
RSVi − min(RSV ) max(RSV ) − min(RSV ) , 1 <= i <= N in which RSVi is the original retrieval status value, and max(RSV ) and min(RSV ) are the maximum and minimum document score values achieved by the first and last documents respectively. N is the number of documents in the collection.
However, the problem only is solved partially, since the normalization of the document score is accomplished independently of the rest of the collections, and therefore, the differences in the RSV are still great.
Another approach is to apply a round-robin algorithm. In this case, the RSV obtained for each retrieved document is not taken into account, but rather the relative position reached by each document in their collection. A single list of documents is obtained and the document score m is in the position m in the list. Thus for example, if we have five languages and we retrieve five lists of documents, the first five documents of the single result list will coincide with the first document of each list; the next five, with the second document of each list; and so on. This approach is not completely satisfactory because the position reached by each document is calculated exclusively considering the documents of the monolingual collection to the one which belongs.
Finally, another approach, perhaps the most original, it is to generate a single index with all
the documents without taking into account the multilingual nature of the collection [
In this section we present a notation that will be used to describe the proposed model. A large
number of retrieval methods are based on this structure [
< T, Φ, D; f f, df > • D es is the document collection to be indexed. • Φ is the vocabulary used in the indices generated from D. • T is the set of all tokens τ present in the collection D, commonly the words or terms. Thus, the function
ϕ : T → Φ, τ → ϕ(τ ) maps the set of all tokens, T ,to the indexing vocabulary Φ. The function ϕ can be a simple process such as removing accents or another more complex such as root extraction (stemming), lemmatization... • f f is the feature frequency and denotes the number of occurrences of ϕi in a document dj: f f (ϕi, dj) :=| {τ ∈ T | ϕ(τ ) = ϕi ∧ d(τ ) = dj} | where d is the function that makes each token τ correspond to its document:
d : T → D, τ → d(τ ) • df is the document frequency and denotes the number of documents containing the feature ϕi at least once:
df (ϕi) :=| {dj ∈ D | ∃τ ∈ T : ϕ(τ ) = ϕi ∧ d(τ ) = dj} | 4
The proposed method [
1. 1. The document pre-selection phase consists of translating and running the query on each monolingual collection, Di, as is usual in CLIR systems based on query translation. This phase produces two results: • we obtain a single multilingual collection of preselected documents (D0 collection) as a result of joining all retrieved documents for each language. • we obtain the translation to the other languages for each term from the original query as a result of the translation process. That is, we obtain a T 0 vocabulary, where each element τ is called “concept” and consists of each term together with its corresponding translation. Thus, a concept is a set of terms expressed independently of the language. 2. The re-indexing phase consists of re-indexing the multilingual collection D0, but considering solely the T 0 vocabulary. That is, only the concepts are re-indexed. Finally, a new query formed by the concepts in T 0 is generated and this query is executed against the new index. Thus for example, if we have two languages, Spanish and English, and the term “casa” is in the original query and it is translated by “house”, both terms represent exactly the same concept. If “casa” occurs a total of 100 times in the Spanish collection, and “house” occurs a total of 150 times in the English collection, then the term frequency would be 250. From a practical point of view, in this second phase each occurrence of “casa” is treated exactly just as each occurrence of “house”.
Formally, the method can be described as follows: For each monolingual collection we begin with the already-known structure:
< Ti, Φi, Di, f f, df >, 1 <= i <= N
Where N is the number of present languages in the multilingual collection to be indexed. Let Q = {Qi, 1 <= i <= N }, be the set formed by the original query together with its translation to the other languages, in such a way that Qi is the query expressed in the same language as the collection Di. After each translation Qi has been run against its corresponding structure < Ti, Φi, Di, f f, df >, it is possible to obtain a new and single structure:
< T 0, Φ0, D, D0, f f 0, df 0 > where: • D is the complete multilingual document collection: D = {Di, 1 <= i <= N }. • D0 is the set of retrieved multilingual documents as consequence of running the query Q. • T 0 is the set of concepts τj, and denotes the vocabulary of the D0 collection. Since each query Qi is a translation of another, it is possible to align the queries at term level.
τj := {τij ∈ Qi, 1 <= i <= N }, 1 <= j = M, M = |Q| where τij represents all the translations of the term j of the query Q to the language i. Thus, τj denotes the concept j of the query Q independently of the language. • Φ0 is a new vocabulary to be indexed, such that each ϕj ∈ Φ0 is generated as follows: ϕj := {ϕ(τij), 1 <= i <= N }, 1 <= j <= M • The f f 0 function and df 0 function are interpreted as usual: – f f 0 is the number of occurrences of the concept j in the k document. That is, the sum of the occurrences of the term j in the query, expressed in language i: f f 0(ϕj, dk) :=| {τ ∈ T | ϕ(τ ) = ϕj ∧ d(τ ) = dk} |
:= Σf f (ϕij, dk), ∀ϕij ∈ ϕj, dk ∈ D0, 1 <= i <= N – df 0 is the number of documents with the concept j in the D collection. That is, the sum of the documents with the term j in the query, expressed in language i: df 0(ϕj) :=| {dk ∈ Di | ∃τ ∈ T : ϕ(τ ) = ϕj ∧ d(τ ) = dk} |
:= Σdf (ϕij), ∀ϕij ∈ ϕj, dk ∈ D, 1 <= i <= N where df (ϕij) is all the documents that contain the concept j in the monolingual collection Di.
Given this structure, a new index is generated in run time, but only taking into account the documents that are found in D0. The df function operates on the whole collection D, not only on the retrieved documents in the first phase, D0. This is so because in practice, we have found that the obtained results have been slightly better when the whole collection has been considered to calculate the idf factor. Once the indices have been generated in this way, the query Q formed by concepts, not by terms, is re-run on the D0 collection.
In some ways, this method shares some ideas with the CLIR systems based on corpus translation, but instead of translating the complete corpus, it only translates the words that appear in the query and the retrieved documents. These two simplifications allow the development of the system in run-query time since the necessary re-indexing process in the second phase is computationally possible due to small size of the D0 collection and to the scarce vocabulary T 0 (approximately, the query terms multiplied by the number of present languages in D0).
Some relevant aspects of two-step RSV are: • It is easily scalable to several languages. • The system requires the term-level alignment of the original query and the translation of its terms. Depending on the approach followed for the translation, this process can prove more or less complex. • A term together with its translation are treated in exactly the same way in the proposed model. This is not too realistic since it is usual for the original term and its translations not to be equally weighted. For example, it is possible that for a given language i, we maintain more than one translation for a given concept of the original query. Consequently, the concept frequency will be increased artificially in the documents expressed in the i language. In this case, if we know the translation probability of each term, we can weight each term according to its translation probability with respect to the original term. This can be modelled as follows:
f f 0(ϕj , dk) := Σf f (ϕij , dk) ∗ w(τij ), ∀ϕij ∈ ϕj , ϕ(τij ) = ϕij , 1 <= i <= N where w(τij ) represents the translation probability of each translation of term j in the query to language i, default it will be 1. 5 5.1
Multilingual Experiments
The experiment has been carried out for the five languages of the multilingual task. Each collection
has been pre-processed as usual, using the stopword lists and stemming algorithms available for
the participants, except for Spanish, in which we have used a stemming algorithm provided by
the ZPrise system 1. We have added to the stopword lists terms such as “retrieval”, “documents”,
“relevant”... Due to the German morphological wealth, compound words have been reduced to
simple words with the MORPHIX package [
Experiment
UJAMLTDRR UJAMLTDNORM
UJAMLTDRSV2
UJAMLTDRSV2RR UJABITD{SP,DE,FR,IT}
For each query, we have used the Title and Description sections. The method of query
translation is very simple: we have used the Babylon2 electronic dictionary to translate query terms
[
1ZPrise, developed by Darrin Dimmick (NIST). Available on demand at http://www.itl.nist.gov/iaui/894.02/works/papers/zp2/zp2.html 2Babylon is available at http://www.babylon.com
The obtained results show that the calculation of the two-step RSV improves more than seven points (36% more) the precision reached with respect to other approaches (table 2). This improvement is approximately constant with short, medium and large queries (table 3). The differences in accuracy between the bilingual experiments may be due to the stemming algorithms used, the quality of which varies according to language. Thus, the simplest stemming algorithm is used for Italian: it removes only inflectional suffixes such as singular and plural word forms or feminine and masculine forms, and it is in this language where the lowest level of accuracy is achieved.
Note that the multilingual document list has been calculated starting from the document lists obtained in the bilingual experiments. The accuracy obtained in the UJAMLTDRSV2 experiment is similar to that obtained in the bilingual experiments(table 4), surpassing even the accuracy for German and Italian, and only two points short of that reached in Spanish. Finally, we have carried out an experiment merging several approaches through a simple linear function. specifically, we have calculated document relevance with the function:
P os0i = 0.6 ∗ P osirsv2 + 0.4 ∗ P osimerge−approach Where P os0i is the new document position i. P osirsv2 is the document position reached using twostep RSV, and P osimerge−approach is the document position using the Round-Robin or normalized score approach. As shown in table 5, not only is there no improvement, but the accuracy even decreases slightly. We have presented a new approach to solve the problem of merging relevant documents in CLIR systems. This approach has performed noticeably better than other traditional approaches. To achieve this performance, it is necessary to align the query with its respective translations at term level. Our next efforts are directed towards three aspects: • We suspect that with the inclusion of more languages, the proposed method will perform better than other approaches. Our objective is therefore to confirm this suspicion. • To test the method with other translation strategies. We have a special interest in the Multilingual Similarity Thesaurus, since this provides a measure of the semantic proximity of two terms. That semantic proximity can be used by our method as the translation probability of a term. • Finally, we could study the effect of the pseudo-relevance feedback in the first and second phase of the proposed method.