Translingual Information Retrieval: A Comparative Evaluation

1 Introduction

Translingual information retrieval (TIR) is starting to receive considerable attention in recent years with the increased accessibility of ever-more-diverse on-line inter­ nat ional text collections, including centrally the World Wide Web. In spite of some pioneering work [Salton , 1970; Dumais et al. , 1996; Davis and Dunning, 1996; Hull and Grefenstette, 1996], evaluations of different TIR techniques in realistic retrieval tasks are rare. This paper reports our evaluation results of both newly developed TIR techniques and reimplementations of previously re­ ported techniques.

Translingual information retrieval (aka "multilingual" or "crosslingual" IR) consists of providing a query in one language and searching document collect ions in one or more different languages. One can envision many ways to bridge the language barrier between query and collec­ tion. In this paper , we focus on query translation and methods based on automatically establishing translin­ gual associations between queries and documents with­ out need of translating either.

2 MT-Based Methods for TIR

The machine translation methods for TIR require that either the query be translated into the target language, and the translation be used to search the target-language collection, or the collection be translated into the source language, and the original query be used to search. Let us consider the pros and cons of each approach :

• Translation Accuracy - Both human and machine translation [Carbonell , 1985; Nirenburg et al., 1991] require context to achieve accuracy. Translating isolated words in a query is unreliable , due to un­ resolved lexical ambiguity. Translating documents shou ld yield greater accuracy.
• Retrieval Accuracy - Since documents contain far more information than queries, random translation errors should cause less degradation for the IR task in documents than in queries. Hence for both this reason and the above, document translation is in principle preferable. In fact, preliminary findings by Dumais et a[ [Dumais et al. , 1996] support this line of reasoning.
• Practicality - Many document collections are very large. Most are searched remotely. Some are propri­ etary; individual documents may be read or down­ loaded, but the entire collection may not be copied or translated. Even if these problems were sur­ mountable, translating the collection may require inordinately long computation and massive storage, not to mention re-indexing the translated collection.

Because of the above practicality constraint, we report only on translating the query for TIR. If the query were formulated as phrases, as a full sentence, or as a para­ graph, we could apply MT systems far more reliably. However, experience shows that users typically prefer to give isolated words, or at best short phrases to an IR

system. 1 The question is how to best translate a set of isolated words. Full fledged MT is not applicable. In­ stead, we investigated three approaches:

1. Dictionary Term Translation - Look up each query term in a general-purpose bilingual dictionary, and use all its possible translations. This is a form of query expansion upon translation.
2. Corpus-based Term Translation - Use a sentence­ aligned bilingual training corpus to find the terms that co-occur in context across languages, thus cre­ ating a corpus-based term-equivalence matrix.
3. Corpus-based Term-to-Sentence - Use the same type of aligned bilingual training corpus to extract full sentences that in the target language co-occur with query terms in the source language. Term-to­ sentence expansion may enhance recall, but at a cost in precision.

All three MT-based methods used variations of the Pangloss Example-Based Machine Translation engine (PanEBMT) [Brown, 1996], however only corpus-based term translation (called EBT below, for "Example-Based Term" translation) is further described since it produced better results.

2.1 PanEBMT Translations

In general, EBMT systems [Brown, 1996; Nagao, 1984] use a large corpus of example pairs of previously trans­ lated sentences, in order to find close matches and trans­ lations of words and phrases in context. The PanEBMT parallel corpus was derived primarily from the Span­ ish and English portions of the UN Multi lingual Corpus [Graff and Finch, 1994], with an admixture of texts from the Pan-American Health Organization and ARPA MT evaluations. The total corpus contains some 685,000 sen­ tence pairs after removing duplicated Spanish sentences. PanEBMT translates by finding the set of matches to a new text string (word, phrase or sentence) in the indexed bilingual corpus. Then the translations corresponding to these matches are combined into candidate translations of the new text. Because queries contain more isolated terms than phrases or sentences, our query-translation experiment is unable to exploit the power of EBMT.

2.2 Corpus-based Term Translation

In order to create domain-specific or corpus-specific bilingual dictionaries automatically, we start from a large sentence-aligned bilingual corpus and generate a large term co-occurrence table combined with a thresholding scheme[Brown , 1997]. The result was used as the dictio­ nary for corpus-based (example-based) term substitution MT (EBT).

Co-occurrence dictionary generation is performed in two phases: First the co-occurrence matrix (indexed by source-language words on one axis and target-language words on the other) is generated. Each cell in the ma­ trix represents the number of times the source-language word occurred in the same sentence pair as the target­ language word. Given this matrix, we compute the con­ ditional probability that if the term occurs in one lan­ guage its counterpart (i.e. its candidate translation) also occurs in the other language. If this probability is above a threshold, then the term translation is added into ~he dictionary. Should a term in one language co-occur with several terms in the other language with sufficient fre­ quency to pass the conditional probability threshold, all are stored as candidate translations.

1 LYCOS reports that their typical user queries for general web search are only one to three words long, although they are occasionally reformulated into longer queries.

3 IR-based Methods for TIR

We extended three monolingual retrieval methods to translingual retrieval: pseudo-relevance feedback (PRF)[Buckley et al., 1995], the general vector space model (GVSM)[Wong et al., 1985], and the latent se­ mantic indexing (LSI) approach[Deerwester et al., 1990]. In each case, a translingual semantic correspondence be­ tween queries and documents is established based on a document-aligned bilingual training corpus, without re­ quiring sentence-level alignment , bilingual dictionaries or machine translation.

3.1 Pseudo-Relevance Feedback

Relevance feedback (RF) is an approach to query ex­ pansion in monolingual text retrieval[Salton, 1989]. It requires a user to judge interactively which retrieved doc­ uments are relevant, and uses the relevance judgments to expand the original query for additional search. By "pseudo-relevance feedback" (PRF) we mean using the top-ranking documents obtained in an initial retrieval without human judgements, assuming that a significant fraction of top-ranked documents will be relevant . Both RF and PRF are query expansion techniques similar to case-based IR [Rissland and Daniels, 1995], and both typically improve performance in monolingual retrieval compared to not using them. The adaptation of PRF to translingual retrieval is relatively simple if a bilingual corpus is available. That is, we find the top-ran~ing doc­ uments for a query in the source language, substitute the corresponding documents in the target language, and use these documents to form the corresponding query in the target language. Figure 1 illustrates the data flow for translingual RF and PRF.

All the IR techniques discussed here, including the PRF approach are variants of the vector space model (VSM)[Salton, 1989] where both queries and documents are represented using vectors of term weights. To allow clear theoretical comparison of these IR-based methods, let us define the notation for VSM (including PRF):

where ij is the query, dis a document in a corpus , m is the number of unique terms (words or phrases) in the corpus , and q; and d; are the term weights in the query and the document, respectively.

3.2 Generalized Vector Space Model

A criticism of conventional VSM is that it uses terms as an orthogonal basis of the vector space, but terms are often not semantically independent. Wong et al proposed an alternative, namely the "generalized vector space model" (GVSM) [Wong et al., 1985], also referred to as "the dual space" [Sheridan and Ballerini , 1996] . The idea is to use documents as the basis for represent­ ing terms instead of using terms.

Consider a term-document matrix, Amxn, as a train­ ing corpus where m is the size of the vocabulary, and n is the number of unique documents in this corpus. One can view this matrix as a way to represent documents (the columns) using terms, and to represent terms (the rows) using documents. The former view corresponds to the conventional vector space model, and the latter view corresponds to the dual space. Each row vector of A reflects the term usage in the corpus, i.e., the pattern of this term distributed over documents .

Matrix A can be used for query transformation by computing q-, = At ij where ij is the original query vector whose dimensions are unique terms , and q-, is the trans­ formed vector whose dimensions are unique documents. The transformation is equivalent to weighting the distri­ bution pattern of each term using its weight in the origi­ nal query, and summing up the weighted patterns to ob­ tain a new representation of the query. Similar to query transformation, a document can also be transformed into a vector in the dual space by computing d-, = AtJ where dis the document vector in the conventional VSM. The retrieval criterion in GVSM for monolingual retrieval is defined to be:

Here we propose a novel extension of the monolingual GVSM for translingual retrieval. Assuming a bilingual corpus for training, we form two matrices, A and B, where A is a term-document matrix for the training doc­ uments in the source language (also the language of the queries), B is a term-document matrix for the training documents in the target language , and the corresponding columns of A and B are the matching pairs of documents in the bilingual corpus. We use A for query transforma­ tion and B target-language document transformation. The retrieval criterion is defined to be:

Since matrix A and B share the same dual space, the transformations Atq and BtJ give the query and the doc­ ument a common basis (presenting distribution patterns of terms over documents) on which they can be com­ pared. This is how the translingual correspondence is established .

The computation in GVSM consists of the transfor­ mation (A 1 ij and B 1 d) and the cosine computation. The time complexity of the first part is similar to the com­ putation in VSM. It is proportional to the number of non-zero elements in a query or document vector , 0( kn) where k is the average number of unique terms per query or document, and n is the number of document pairs in the bilingual training corpus. The time complexity in the second part, is O(n) per document , or O(nl) for a test corpus of l documents . It is possible to significantly reduce this complexity in large problems by aggressively removing non-influential elements from the transformed document vectors [Yang, 1995].

3.3 Latent Semantic Indexing

Latent Semantic Indexing[Deerwester et al., 1990] (LSI) is a one-step extension of GVSM. The claim is that nei­ ther terms nor documents are the optimal choice for the orthogonal basis of a semantic space, and that a reduced vector space consisting of the most meaningful linear combinations of documents would be a better represen­ tative basis for the content of documents.

In monolingual retrieval, LSI uses the term-document matrix (A) for training, the same as in GVSM. It com­ putes the orthogonal dimensions ( "the latent semantic structures" ) in matrix A, and selects the principal di­ mensions as the new basis for a reduce vector space. The monolingual LSI retrieval criterion is defined to be:

where matrices U and V contain a set of p orthogonal sin­ gular vectors each (one for the representation of terms, and another for the representation of documents) . Ma­ trix :E is p-diagonal , containing the singular values in­ dicating the importance of the corresponding singular vectors in matrices U and V. Matrix L contains the weighted singular vectors in U, where the weights are the corresponding singular values in E. This matrix can be viewed as a reduced version of matrix A. That is, both A and L use their row vectors to represent terms, but the term vectors in L are much shorter than the term vectors in A. The dimensions in L are linear com­ binations of documents, while the dimensions in A are individual documents.

The translingual LSI model [Dumais et al., 1996] is similar to the model for monolingual LSI, except that a bilingual document corpus is needed for training instead of a monolingual corpus. Let if be a query in the source language, J be a document in the target language, and

[ ~ ] be the matrix of bilingual document pairs where A and B are the same as defined in GVSM. Then the translingual LSI retrieval criterion is defined to be:

where U2, V2, E2 and L2 are the matrices computed using the singular value decomposition of the bilingual input matrix .

LSI has a quadratic time complexity of O(n'p) where n 1 = max{ m, n} is the larger number between the size ( m) of the joint vocabulary of both languages and the number ( n) of document pairs in the bilingual training corpus; p is the number of orthogonal dimensions (sin­ gular vectors) computed in the singular value decompo­ sition. Thus the scalability of this method to a large corpus would be much more limited than the VSM or GVSM approach if a large number of singular vectors is . necessary for good retrieval performance.

3.4 The Scientific Challenge

The similarities and differences between the three models mentioned above can be seen in their retrieval criteria:

The fundamental difference, in theory, is the choice of the basis for the similarity comparison between queries and documents. VSM assumes semantic independence of terms in its basis. GVSM uses documents instead, assuming documents are semantically independent . LSI computes the orthogonal dimensions in a training cor­ pus, and chooses the principal dimensions as the basis of a reduced vector space. GVSM and LSI are close variants in the sense that both exploit the dual space. The only difference is whether to use the original dimen­ sions (document vectors) or the reduced dimensions (the orthogonal singular vectors) as the basis for the vector space. Which model best represents the semantic space of documents and queries is a scientifically challenging question.

Given the methods, empirical validation is impor­ tant. For monolingual retrieval, performance improve­ ment of GVSM over VSM was observed on small collec­ tions [Wong et al., 1985]; improvement of LSI over VSM was observed sometimes but not always [Deerwester et al., 1990]. Until our work reported below, there has not been a comparison between GVSM and LSI , in either monolingual or translingual retrieval.

4 Empirical Evaluation

We carried out a comparative evaluation of the six translingual IR methods described above (the three term-based MT methods, PRF, GVSM, and LSI) on a realistic retrieval task. The large UN Multilingual Corpus[ Graff and Finch, 1994] from the Linguistic Data Consortium was available to us, but, among other prob­ lems, there were no queries or human relevance judge­ ments available for training and evaluation. We con­ ducted our experiments on a subset of this corpus, con­ sisting of 2255 document pairs pertaining to UNICEF reports and deliberations. Each document pair consists of an English document and its corresponding Spanish translation. 1134 document pairs were randomly se­ lected and used for translingual training. The remaining 1121 pairs were set aside for testing. The average (mono­ lingual) document is 9 paragraphs long. Altogether , the training and test sets in both languages consist of almost 2 million words of text .

We conducted our experiments as follows: First , we created 30 queries in English, germane to the UNICEF subcollection. The average query length was 11 words. Second, we obtained human relevance judgements on the cross product of the 30 queries and 1121 test documents (33 ,630 samples in all), and used these as our gold stan­ dard for testing2. Third, we trained each method to find translingual equivalences using paired documents, with­ out queries; hence no relevance judgements were required for training. Fourth, we tested each method monolin­ gually on the test set to obtain ranked lists of retrieved documents. Fifth, we applied the translingual version of our methods. Finally, we evaluated the results by comparing the retrieval degradation when moving from monolingual to translingual IR for all the methods.

We optimized each method for monolingual retrieval, with respect to its performance on 11-point average pre­ cision using the full human relevance judgements on the 30 queries for the test corpus. Optimizations include the settings on TF and IDF weights for cosine-similarity scoring, setting thresholds on pseudo-relevance feedback , setting cutoff levels for number of non-influential ele­ ments for GVSM (200 was optimal), and determining the optimal number of singular vectors in LSI (also 200, coincidentally). When each retrieval method was per­ forming at optimum on monolingual retrieval, we tested that method with exactly the same parameter settings on translingual retrieval.

2 An initial set of experiments was conducted before these judgements were available, as described below.

We carried out two sets of experiments . The firs t comparison focuses on overlap between monolingually­ retrieved documents and translingual retrievals, based on the parallel corpus to establish correspondences. The central tenet of the first evaluation was that perfect translingual retrieval would retrieve exactly the cor­ responding set of documents as monolingual retrieval , but in the target language. Hence, monolingual versus translingual comparison was our primary effectiveness measure. The second comparison is a direct evaluation of monolingual and of translingual retrieval using human relevance judgements and computing precision and recall scores in the traditional IR manner [Salton and McGill , 1983).

4.1 Initial Evaluation

Before we had relevance judgements available, we car­ ried out an initial set of experiments, using two novel evaluation methods. Each of the retrieval methods was trained on the same bilingual training data. We then ran each of the translingual methods using English queries to retrieve Spanish documents, and compared the Spanish documents retrieved translingually to the English docu­ ments retrieved monolingually by each method.

The results were compared using both an 11-point average precision and an overlap measure. "Precision" in this case was measured by comparing the top £2 of the translingually-retrieved ranked list against the top Ll of the corresponding monolingually-retrieved ranked list , and taking the monolingually-retrieved documents as relevant to the query. The overlap measure was sim­ ply the percentage of identical documents present in the top Ll ranked documents retrieved monolingually and the top £2 translingually, for a given Ll and £2. We calculated both measures in order to minimize any arti­ fact of our evaluation method.

The translingual results are presented in Figures 2 and 3. Figure 2 presents the 11-point average precision for each method plotted against the number of reference documents used (Ll) . £2 is four times Ll in each case, in an attempt to make the second ranked list sufficiently long. Figure 3 presents the overlap measure for each method , again versus Ll. Here we use £2 = Ll , as per our definition of overlap. As mentioned above, we only report the results of the corpus-based EBT method in these graphs , for brevity, given that it performed best among the MT methods.

From these figures, we see that GVSM outperformed the other methods in terms of these document overlap measures. All the methods have a large overlap between their monolingual and translingual retrievals , which is a good sign. Moreover , the graphs of the two evaluation methods are remarkably consistent .

4.2 Evaluation with Human Judgements

For our second comparison, we evaluated each method, monolingually and translingually, using human relevance judgements. The corresponding 11-point average preci­ sion values in the table in figure 4 below. For compari­ son, we also include corresponding translingual results reported by other researchers. Because the methods have been run on different corpora with different queries, direct comparisons on absolute 11-point-precision re­ call figures are not meaningful. However , the ratio of translingual IR (TIR) over monolingual IR results may be more indicative of the relative power of the TIR meth­ ods. We encourage direct comparisons on the same cor­ pus. We also present our results in the standard recall­ precision graphs for monolingual and translingual IR in figures 5 and 6, respectively.

As the table in figure 4 shows, example-based term (EBT) translation ( a.k.a. corpus-based term transla­ tions), never before tried for TIR, exhibits top absolute performance, whereas general-purpose machine-readable dictionary (MRD) query-translation exhibits the worst performance. In spite of the similarity between these methods (both translate the query) , the former is trained to the corpus and exploits context, and is therefore much superior. This result indicates that the most popu­ lar TIR method reported in the literature (MRD-based query translation) may be the simplest, but its perfor­ mance leaves much to be desired.

Pseudo-relevance feedback also performed well in ab­ solute terms, indicating that if the user were willing to provide true relevance judgements, full relevance feed­ back could become the top-performing method for TIR.

GVSM, never before tried for TIR, performed rela­ tively well and showed the least degradation from MIR to TIR. LSI did not perform according to expectations from the literature. In earlier less realistic experiments (with queries formulated directly from documents) , LSI had performed better [Dumais et al. , 1996].

5 Conclusions

This paper reports a thorough evaluation of multiple methods for translingual retrieval in a query-based re­ trieval task. We believe that the evaluation methodology used here may be generally useful when costly human relevance judgements are unavailable. Our experimental results indicate that:

• Translingual retrieval is viable by a number of dif­ ferent techniques, ranging from term-based query translation and pseudo-relevance feedback to gener­ alized vector spaces and latent semantic indexing.
• In the translingual retrieval test, example-based MT establishing corpus-based term equivalences per­ formed best , followed by PRF, GVSM, LSI and MRD-based query translation. However , in terms of performance relative to monolingual retrieval , GVSM performed best.
• MRD-based query translation, though popular in the literature, should be re-examined as the TIR method of choice given the results in this paper.
• It appears that Translingual LSI is not as good in a realistic setting with actual queries and 11-point­ average precision evaluations as in the preliminary Dumais et al study, although LSI does perform bet­ ter that simple MRD-based query translation.

It is worth noting that GVSM is simple to compute and easy to scale up , somewhat better than LSI , and its performance is not crucially dependent on the exact value of a tuned parameter (such as the number of sin­ gular vectors of LSI). More work is clearly called for in further evaluating the GVSM method and corpus­ based term-translation in other realistic contexts, and investigating whether other forms of tunable MT-based translingual IR could be made to perform reasonably well, especially in situations where translating the col­ lection does not pose serious problems.