Improving Corpus Comparability for Bilingual Lexicon Extraction from Comparable Corpora

Previous work on bilingual lexicon extraction from comparable corpora aimed at finding a good representation for the usage patterns of source and target words and at comparing these patterns efficiently. In this paper, we try to work it out in another way: improving the quality of the comparable corpus from which the bilingual lexicon has to be extracted. To do so, we propose a measure of comparability and a strategy to improve the quality of a given corpus through an iterative construction process. Our approach, being general, can be used with any existing bilingual lexicon extraction method. We show here that it leads to a significant improvement over standard bilingual lexicon extraction methods.


Introduction
Bilingual dictionaries are an essential resource in many multilingual natural language processing (NLP) tasks such as machine translation (Och and Ney, 2003) and cross-language information retrieval (CLIR) (Ballesteros and Croft, 1997). Hand-coded dictionaries are of high quality, but expensive to build and researchers have tried, since the end of the 1980s, to automatically extract bilingual lexicons from parallel corpora (see (Chen, 1993;Kay and Röscheisen, 1993;Melamed, 1997a;Melamed, 1997b) for early work). Parallel corpora are however difficult to get at in several domains, and the majority of bilingual collections are comparable and not parallel. Due to their low cost of acquisition, sev-eral researchers have tried to exploit such comparable corpora for bilingual lexicon extraction (Fung and McKeown, 1997;Fung and Yee, 1998;Rapp, 1999;Déjean et al., 2002;Gaussier et al., 2004;Robitaille et al., 2006;Morin et al., 2007;Yu and Tsujii, 2009). The notion of comparability is however a loose one, and comparable corpora range from lowly comparable ones to highly comparable ones and parallel ones. For data-driven NLP techniques, using better corpora often leads to better results, a fact which should be true for the task of bilingual lexicon extraction. This point has largely been ignored in previous work on the subject. In this paper, we develop a well-founded strategy to improve the quality of a comparable corpus, so as to improve in turn the quality of the bilingual lexicon extracted. To do so, we first propose a measure of comparability which we then use in a method to improve the quality of the existing corpus.
The remainder of the paper is organized as follows: Section 2 introduces the experimental materials used for the different evaluations; comparability measures are then presented and evaluated in Section 3; in Section 4, we detail and evaluate a strategy to improve the quality of a given corpus while preserving its vocabulary; the method used for bilingual lexicon extraction is then described and evaluated in Section 5. Section 6 is then devoted to a discussion, prior to the conclusion given in Section 7.

Experimental Materials
For the experiments reported here, several corpora were used: the parallel English-French Europarl corpus (Koehn, 2005), the TREC (http://trec.nist.gov/) Associated Press corpus (AP, English) and the corpora used in the multilingual track of CLEF (http://www.clefcampaign.org) which includes the Los Angeles Times (LAT94, English), Glasgow Herald (GH95, English), Le Monde (MON94, French), SDA French 94 (SDA94, French) and SDA French 95 (SDA95, French). In addition to these existing corpora, two monolingual corpora from the Wikipedia dump 1 were built. For English, all the articles below the root category Society with a depth less than 4 2 were retained. For French, all the articles with a depth less than 7 below the category Société are extracted. As a result, the English corpus Wiki-En consists of 367,918 documents and the French one Wiki-Fr consists of 378,297 documents.
The bilingual dictionary used in our experiments is constructed from an online dictionary. It consists of 33,372 distinct English words and 27,733 distinct French words, which constitutes 75,845 translation pairs. Standard preprocessing steps: tokenization, POS-tagging and lemmatization are performed on all the linguistic resources. We will directly work on lemmatized forms of content words (nouns, verbs, adjectives, adverbs).

Measuring Comparability
As far as we can tell, there are no practical measures with which we can judge the degree of comparability of a bilingual corpus. In this paper, we propose a comparability measure based on the expectation of finding the translation for each word in the corpus. The measure is light-weighted and does not depend on complex resources like the machine translation system. For convenience, the following discussions will be made in the context of the English-French comparable corpus.

The Comparability Measure
For the comparable corpus C, if we consider the translation process from the English part C e to the 1 The Wikipedia dump files can be downloaded at http://download.wikimedia.org. In this paper, we use the English dump file on July 13, 2009 and the French dump file on July 7, 2009. 2 There are several cycles in the category tree of Wikipedia. It is thus necessary to define a threshold on the depth to make the iterative process feasible.
French part C f , a comparability measure M ef can be defined on the basis of the expectation of finding, for each English word w e in the vocabulary C v e of C e , its translation in the vocabulary C v f of C f . Let σ be a function indicating whether a translation from the translation set T w of w is found in the vocabulary C v of a corpus C, i.e.: M ef is then defined as: where D v e is the English part of a given, independent bilingual dictionary D, and where the last equality is based on the fact that, the comparable corpus and the bilingual dictionary being independent of one another, the probability of finding the translation in C v f of a word w is the same for w is in C v e ∩ D v e and in C v e \D v e 3 . Furthermore, the presence of common words suggests that one should rely on a presence/absence criterion rather than on the number of occurrences to avoid a bias towards common words. Given the natural language text, our evaluation will show that the simple presence/absence criterion can perform very well. This leads to P r(w ∈ C v e ) = 1/|C v e |, and finally to: This formula shows that M ef is actually the proportion of English words translated in the French part of the comparable corpus. Similarly, the counterpart of M ef , M f e , is defined as: and measures the proportion of French words in C v f translated in the English part of the comparable corpus. A symmetric version of these measures is obtained by considering the proportion of the words (both English and French) for which a translation can be found in the corpus: We now present an evaluation of these measures on artificial test corpora.

Validation
In order to test the comparability measures, we developed gold-standard comparability scores from the Europarl and AP corpora. We start from the parallel corpus, Europarl, of which we degrade the comparability by gradually importing some documents from either Europarl or AP. Three groups (G a , G b , G c ) of comparable corpora are built in this fashion. Each group consists of test corpora with a gold-standard comparability ranging, arbitrarily, from 0 to 1 and corresponding to the proportion of documents in "parallel" translation. The first group G a is built from Europarl only. First, the Europarl corpus is split into 10 equal parts, leading to 10 parallel corpora (P 1 , P 2 , . . . , P 10 ) with a gold-standard comparability arbitrarily set to 1. Then for each parallel corpus, e.g. P i , we replace a certain proportion p of the English part with documents of the same size from another parallel corpus P j (j = i), producing the new corpus P i with less comparability which is the gold-standard comparability 1 − p. For each P i , as p increases, we obtain several comparable corpora with a decreasing gold-standard comparability score. All the P i and their descendant corpora constitute the group G a . The only difference between G b and G a is that, in G b , the replacement in P i is done with documents from the AP corpus and not from Europarl. In G c , we start with 10 final, comparable corpora P i from G a . These corpora have a gold-standard comparability of 0 in G a , and of 1 in G c . Then each P i is further degraded by replacing certain portions with documents from the AP corpus. We then computed, for each comparable corpus in each group, its comparability according to one of the comparability measures. Figure 1 plots the measure M for ten comparable corpora and their descendants from G c , according to their gold-standard comparability scores. As one can note, the measure M is able to capture almost all the differences in comparability and is strongly correlated with the gold-standard. The correlation between the different measures and the goldstandard is finally computed with Pearson correlation coefficient. The results obtained are listed in Table 1. As one can note, M f e performs worst among the three measures, the reason being that the process to construct G b and G c yields unbalanced bilingual corpora, the English section being larger than the French one. Translations of French words are still likely to be found in the English corpus, even though the corpora are not comparable. On all the 3 groups, M performs best and correlates very well with the gold standard, meaning that M was able to capture all the differences in comparability artificially introduced in the degradation process we have considered. This is the measure we will retain in the following parts.  Having established a measure for the degree of comparability of bilingual corpora, we now turn to the problem of improving the quality of comparable corpora.

Improving Corpus Quality
We here try to improve the quality of a given corpus C, which we will refer to as the base corpus, by extracting the highly comparable subpart C H which is above a certain degree of comparability η (Step 1), and by enriching the lowly comparable part C L with texts from other sources (Step 2). As we are interested in extracting information related to the vocabulary of the base corpus, we want the newly built corpus to contain a substantial part of the base corpus. This can be achieved by preserving in Step 1 as many documents from the base corpus as possible (e.g. by considering low values of η), and by using in step 2 sources close to the base corpus.

Step 1: Extracting C H
The strategy consisting of building all the possible sub-corpora of a given size from a given comparable corpora is not realistic as soon as the number of documents making up the corpora is larger than a few thousands. In such cases, better ways for extracting subparts have to be designed. The strategy we have adopted here aims at efficiently extracting a subpart of C above a certain degree of comparability and is based on the following property. Property 1. Let d 1 e and d 2 e (resp. d 1 f and d 2 f ) be two English (resp. French) documents from a bilingual corpus C. We consider, as before, that the bilingual dictionary D is independent from C.
. One can show, by exploiting condition (ii), that: and similarly that: Then exploiting condition (i), and the independence between the corpus and the dictionary, one arrives at: Property 1 shows that one can incrementally extract from a bilingual corpus a subpart with a guaranteed minimum degree of comparability η by iteratively adding new elements, provided (a) that the new elements have a degree of comparability of at least η and (b) that they are less comparable than the currently extracted subpart (conditions (ii)). This strategy is described in Algorithm 1. Since the degree of comparability is always above a certain threshold and since the new documents selected (d 2 e , d 2 f ) are the most comparable among the remaining documents, condition (i) is likely to be satisfied, as this condition states that the increase in the vocabulary from the second documents to the union of the two is the same in both languages. Similarly, considering new elements by decreasing comparability scores is a necessary step for the satisfaction of condition (ii), which states that the current subpart should be uniformly more comparable than the element to be added. Hence, the conditions for property 1 to hold are met in Algorithm 1, which finally yields a corpus with a degree of comparability of at least η.

4.2
Step 2: Enriching C L This step tries to absorb knowledge from other resources, which will be called external corpus,

Algorithm 1 Input:
English document set C d e of C French document set C d f of C Threshold η Output: C H , consisting of the English document set S e and the French document set S f 1: Initialize S e = ∅, S f = ∅, temp = 0; 2: repeat 3: if temp ≥ η then 6: Add d e into S e and add d f into S f ; 7: to enrich the lowly comparable part C L which is the left part in C during the creation of C H . One choice for obtaining the external corpus C T is to fetch documents which are likely to be comparable from the Internet. In this case, we first extract representative words for each document in C L , translate them using the bilingual dictionary and retrieve associated documents via a search engine. An alternative approach is of course to use existing bilingual corpora. Once C T has been constructed, the lowly comparable part C L can be enriched in exactly the same way as in section 4.1: First, Algorithm 1 is used on the English part of C L and the French part of C T to get the highquality document pairs. Then the French part of C L is enriched with the English part of C T by the same algorithm. All the high-quality document pairs are then added to C H to constitute the final result.

Validation
We use here GH95 and SDA95 as the base corpus C 0 . In order to illustrate that the efficiency of the proposed algorithm is not confined to a specific external resource, we consider two external resources: (a) C 1 T made of LAT94, MON94 and SDA94, and (b) C 2 T consisting of Wiki-En and Wiki-Fr. The number of documents in all the corpora after elimination of short documents (< 30 words) is listed in Table 2.  For the extraction of the highly comparable part C H from the base corpus C 0 , we set η to 0.3 so as to extract a substantial subpart of C 0 . After this step, corresponding to Algorithm 1, we have 20,124 English-French document pairs in C H . The second step is to enrich the lowly comparable part C L of the base corpus documents from the external resources C 1 T and C 2 T . The final corpora we obtain consist of 46,996 document pairs for C 1 (with C 1 T ) and of 54,402 document pairs for C 2 (with C 2 T ), size similar to the one of C 0 . The proportion of documents (columns "D-e" and "Df"), sentences (columns "S-e" and "S-f") and vocabulary (columns "V-e" and "V-f") of C 0 found in C 1 and C 2 is given in Table 3. As one can note, the final corpora obtained through the method presented above preserve most of the information from the base corpus. Especially for the vocabulary, the final corpora cover nearly all the vocabulary of the base corpus. Considering the comparability scores, the comparability of C 1 is 0.912 and the one of C 2 is 0.916. Both of them are more comparable than the base corpus of which the comparability is 0.882.
From these results of the intrinsic evaluation, one can conclude that the strategy developed to improve the corpus quality while preserving most of its information is efficient: The corpora obtained here, C 1 and C 2 , are more comparable than the base corpus C 0 and preserve most of its information. We now turn to the problem of extracting bilingual lexicons from these corpora.

Bilingual Lexicon Extraction
Following standard practice in bilingual lexicon extraction from comparable corpora, we rely on the approach proposed by Fung and Yee (1998). In this approach, each word w is represented as a

Using Algorithm 1 pseudo-Alignments
The process we have defined in the previous section to improve the quality of a given corpus while preserving its vocabulary makes use of highly comparable document pairs, and thus provides some loose alignments between the two corpora. One can thus try to leverage the above approach to bilingual lexicon extraction by re-weighting s c (w e , w f ) by a quantity which is large if w e and w f appear in many document pairs with a high comparability score, and small otherwise. In this section, we can not use the alignments in algorithm 1 directly because the alignments in the comparable corpus should not be 1 to 1 and we did not try to find the precise 1 to 1 alignments in algorithm 1. Let η be the threshold used in algorithm 1 to construct the improved corpus and let φ(d e , d f ) be defined as: Let H e (resp. H f ) be the set of documents containing word w e (resp. w f ). We define the joint probability of w e and w f as being proportional to the number of comparable document pairs they belong to, where two documents are comparable if their comparability score is above η, that is: The marginal probability p(w e ) can then be written as: Assuming that all d f in C d f have roughly the same vocabulary size and all d e have the same number of comparable counterparts in C d f , then the marginal probability can be simplified as: p(w e ) ∝ |H e |. By resorting to the exponential of the point-wise mutual information, one finally obtains the following weight: which has the desired property: It is large if the two words appear in comparable document pairs more often than chance would predict, and small otherwise. We thus obtain the revised similarity score for w e and w f :

Validation
In order to measure the performance of the bilingual lexicon extraction method presented above, we divided the original dictionary into 2 parts: 10% of the English words (3,338 words) together with their translations are randomly chosen and used as the evaluation set, the remaining words (30,034 words) being used to compute context vectors and similarity between them. In this study, the weight a(w c ) used in the context vectors (see above) are taken to be the tf-idf score of w c : a(w c ) = tf-idf(w c ). English words not present in C v e or with no translation in C v f are excluded from the evaluation set. For each English word in the evaluation set, all the French words in C v f are then ranked according to their similarity with the English word (using either equation 1 or 2). To evaluate the quality of the lexicons extracted, we first retain for each English word its N first translations, and then measure the precision of the lists obtained, which amounts in this case to the proportion of lists containing the correct translation (in case of multiple translations, a list is deemed to contain the correct translation as soon as one of the possible translations is present). This evaluation procedure has been used in previous work (e.g. (Gaussier et al., 2004)) and is now standard for the evaluation of lexicons extracted from comparable corpora. In this study, N is set to 20. Furthermore, several studies have shown that it is easier to find the correct translations for frequent words than for infrequent ones (Pekar et al., 2006). To take this fact into account, we distinguished different frequency ranges to assess the validity of our approach for all frequency ranges. Words with frequency less than 100 are defined as low-frequency words (W L ), whereas words with frequency larger than 400 are highfrequency words (W H ), and words with frequency in between are medium-frequency words (W M ).
We then tested the standard method based on the cosine similarity (equation 1) on the corpora C 0 , C H , C H , C 1 and C 2 . The results obtained are displayed in Table 4, and correspond to columns 2-6. They show that the standard approach performs significantly better on the improved corpora C 1 /C 2 than on the base corpus C 0 . The overall precision is increased by 5.3% on C 1 (corresponding to a relative increase of 26%) and 9.5% on C 2 (corresponding to a relative increase of 51%), even though the low-frequency words, which dominate the overall precision, account for a higher proportion in C 1 (61.3%) and C 2 (61.3%) than in C 0 (56.2%). For the medium and high frequency words, the precision is increased by over 11% on C 1 and 16% on C 2 . As pointed out in other studies, the performance for the low-frequency words is usually bad due to the lack of context information. This explains the relatively small improvement obtained here (only 2.2% on C 1 and 6.7% on C 2 ). It should also be noticed that the performance of the standard approach is better on C 2 than on C 1 , which may be due to the fact that C 2 is slightly larger than C 1 and thus provides more information or to the actual content of these corpora. Lastly, if we consider the results on the corpus C H which is produced by only choosing the highly comparable part from C 0 , the overall precision is increased by only 1.9%, which might come from the fact that the size of C H is less than half the size of C 0 . We also notice the better results on C H than on C H of the same size which consists of randomly choosing documents from C 0 .
The results obtained with the refined approach making use of the comparable document pairs found in the improved corpus (equation 2) are also displayed in Table 4 (columns "C 1 new" and "C 2 new"). From these results, one can see that the overall precision is further improved by 2.0% on C 1 and 2.3% on C 2 , compared with the standard approach. For all the low, medium and high-frequency words, the precision has been improved, which demonstrates that the information obtained through the corpus enrichment process contributes to improve the quality of the extracted bilingual lexicons. Compared with the original base corpus C 0 , the overall improvement of the precision on both C 1 and C 2 with the refined approach is significant and important (respectively corresponding to a relative improvement of 35% and 62%), which also demonstrates that the efficiency of the refined approach is not confined to a specific external corpus.

Discussion
It is in a way useless to deploy bilingual lexicon extraction techniques if translation equivalents are not present in the corpus. This simple fact is at the basis of our approach which consists in constructing comparable corpora close to the original corpus and which are more likely to contain translation equivalents as they have a guaranteed degree of comparability. The pseudo-alignments identified in the construction process are then used to leverage state-of-the-art bilingual lexicon extraction methods. This approach to bilingual lexicon extraction from comparable corpora radically differs, to our knowledge, from previous approaches   (Fung and Yee, 1998) and (Rapp, 1999). For example, the method developed in (Déjean et al., 2002) and (Chiao and Zweigenbaum, 2002) involves a representation of dictionary entries with context vectors onto which new words are mapped. Pekar et al. (2006) smooth the context vectors used in the standard approach in order to better deal with low frequency words. A nice geometric interpretation of these processes is proposed in (Gaussier et al., 2004), which furthermore introduces variants based on Fisher kernels, Canonical Correlation Analysis and a combination of them, leading to an improvement of the F1-score of 2% (from 0.14 to 0.16) when considering the top 20 candidates. In contrast, the approach we have developed yields an improvement of 7% (from 0.13 to 0.20) of the F-1 score on C 2 , again considering the top 20 candidates. More important, however, is the fact that the approach we have developed can be used in conjunction with any existing bilingual extraction method, as the strategies for improving the corpus quality and the re-weighting formula (equation 2) are general. We will assess in the future whether substantial gains are also attained with other methods.
Some studies have tried to extract subparts of comparable corpora to complement existing parallel corpora. Munteanu (2004) thus developed a maximum entropy classifier aiming at extracting those sentence pairs which can be deemed parallel. The step for choosing similar document pairs in this work resembles some of our steps. However their work focuses on high quality and specific documents pairs, as opposed to the entire corpus of guaranteed quality we want to build. In this latter case, the cross-interaction between documents impacts the overall comparability score, and new methods, as the one we have introduced, need to be proposed. Similarly, Munteanu and Marcu (2006) propose a method to extract subsentential fragments from non-parallel corpora. Again, the targeted elements are very specific (parallel sentences or sub-sentences) and limited, and the focus is put on a few sentences which can be considered parallel. As already mentioned, we rather focus here on building a new corpus which preserves most of the information in the original corpus. The construction process we have presented is theoretically justified and allows one to preserve ca. 95% of the original vocabulary.

Conclusion
We have first introduced in this paper a comparability measure based on the expectation of finding translation word pairs in the corpus. We have then designed a strategy to construct an improved comparable corpus by (a) extracting a subpart of the original corpus with a guaranteed comparability level, and (b) by completing the remaining subpart with external resources, in our case other existing bilingual corpora. We have then shown how the information obtained during the construction process could be used to improve state-ofthe-art bilingual lexicon extraction methods. We have furthermore assessed the various steps of our approach and shown: (a) that the comparability measure we introduced captures variations in the degree of comparability between corpora, (b) that the construction process we introduced leads to an improved corpus preserving most of the original vocabulary, and (c) that the use of pseudo-alignments through simple re-weighting yields bilingual lexicons of higher quality.