Iterative Learning of Parallel Lexicons and Phrases from Non-Parallel Corpora

1 Introduction

Parallel corpora, which are collections of parallel texts, play a critical role in data-driven multilingual natural language processing (NLP) tasks such as statistical machine translation (MT) and cross-lingual information retrieval. For example, in statistical MT, parallel corpora serve as the central source for estimating translation model parameters [Brown et al., 1993; Koehn et al., 2003; Chiang, 2005]. It is widely accepted that the quantity, quality, and coverage of parallel corpora have an important effect on the performance of statistical MT systems.

Despite the apparent success of data-driven multilingual NLP techniques, the availability of large-scale, widecoverage, high-quality parallel corpora still remains a major challenge. For most language pairs, parallel corpora are nonexistent. Even for the top handful of resource-rich languages, the available parallel corpora are usually unbalanced because the major sources are government documents or news articles.

∗Yang Liu is the corresponding author.

As a result, learning translation models from non-parallel corpora has attracted intensive attention from the community [Koehn and Knight, 2002; Fung and Cheung, 2004; Munteanu and Marcu, 2006; Quirk et al., 2007; Ueffing et al., 2007; Haghighi et al., 2008; Bertoldi and Federico, 2009; Cettolo et al., 2010; Daum´e III and Jagarlamudi, 2011; Ravi and Knight, 2011; Nuhn et al., 2012; Dou and Knight, 2012; Klementiev et al., 2012; Zhang and Zong, 2013; Dou et al., 2014]. Most existing approaches focus on learning word-based models: either bilingual lexicons or IBMmodels. Based on canonical correlation analysis (CCA), Haghighi et al. [2008] leverage orthographic and context features to induce word translation pairs. Ravi and Knight [2011] cast training IBM models on monolingual data as a decipherment problem. However, word-based models are not expressive enough to capture non-local dependencies and therefore are insufficient to yield high quality translations.

Recently, several authors have moved a step further to learn phrase-based models from non-parallel corpora [Klementiev et al., 2012; Zhang and Zong, 2013]. Zhang and Zong [2013] propose to use a parallel lexicon to retrieve parallel phrases from non-parallel corpora. They show that their approach can learn new translations and improve translation performance. However, their approach is unidirectional: only using lexicons to identify parallel phrases. In fact, it is possible to learn better lexicons from extracted phrase pairs in a reverse direction, which potentially constitutes a "find-one-get-more" loop [Fung and Cheung, 2004].

In this paper, we propose an iterative approach to learning bilingual lexicons and phrases jointly from non-parallel corpora. Given two sets of monolingual phrases that might contain parallel phrases, we develop a generative model based on IBMmodel 1 [Brown et al., 1993], which treats the mapping between phrase pairs as a latent variable. The model is trained using a Viterbi EM algorithm. Experiments on Chinese-English datasets show that iterative training significantly improves the quality of learned bilingual lexicons and phrases and benefit end-to-end MT systems.

2 Preliminaries

We begin with a brief introduction to IBM model 1, which is the core component of our generative model.

Let f = f1, . . . , fJ be a foreign sentence with J words. We use fj to denote the j-th word in the foreign sentence. Similarly, e = e1, . . . , eI is an English sentence with I words and ei is the i-th word. f and e denote single foreign and English words, respectively. A word alignment a = a1, . . . , aJ indicates the correspondence between f and e. Brown et al. [1993] restrict that each foreign word is aligned to exactly one English word: aj ∈ {0, 1, . . . , I}, where e0 is defined to be an empty English word.

According to Brown et al. [1993], IBMmodel 1 is defined as follows:

where the set of model parameters θ consists of length probabilities p(J|I) and translation probabilities p(f|e):

Brown et al. [1993] indicate that the right-hand side of Eq. (2) is a sum of terms each of which is a monomial in the translation probabilities. Therefore, we have

Given a set of parallel sentences D = {〈f (s) , e(s) 〉}Ss=1 , the training objective is to maximize the log-likelihood of the training data: 1

Brown et al. [1993] use the EM algorithm to estimate translation probabilities. c(f|e;D), which is the expected number of times that e connects to f on the training data, is calculated as

where I (s) and J (t) are lengths of e(s) and f (t) , respectively.

Then, the new translation probabilities can be obtained by normalizing these counts:

1 As there is no need to train the length model on parallel corpora, Brown et al. [1993] set p(J|I) to some small, fixed number.

3 Model

In this work, we are interested in learning IBMModel 1 from non-parallel corpora: a set of foreign strings F = {f (t) }Tt=1 and a set of English strings E = {e(s) }Ss=1 . Our goal is twofold:

1. Extract a parallel corpus from non-parallel corpora F and E using IBM model 1,
2. Train IBMmodel 1 from the extracted parallel corpus.

Due to data sparsity, a long foreign sentence in F can hardly have an English translation in E. Alternatively, we assume that a short foreign string, say a phrase with up to 7 words, in F can potentially have an English translation in E [Munteanu and Marcu, 2006; Quirk et al., 2007; Cettolo et al., 2010]. Therefore, in this work, F and E are defined to be sets of phrases. We can easily obtain such monolingual phrase sets by collecting n-grams.

We introduce phrase matching to denote the correspondence between phrases in F and E. A foreign phrase f is said to match an English phrase e if they are translations of each other. More formally, we use M to denote a set of all possible matchings andma matching. Following Brown et al. [1993], we restrict that each foreign phrase matches exactly one English phrase: m = m1, . . . ,mT , where mt ∈ {0, 1, . . . , S}. Note that we allow a foreign phrase to connect to an empty English phrase e(0) .

The joint model is defined as

We refer to P(f (t) |e(mt) ; θ) as phrase translation model, which can be divided into two categories: empty and nonempty. The probability of a foreign phrase given an empty English phrase is defined to be a model parameter satisfying

where F is the set of all possible foreign phrases. Note that F in the training data is just a subset of F. As F cannot be fully enumerated, we set p(f |e(0) ) to a fixed number ϵ, which is a hyper-parameter to be optimized on the held-out data.

For non-empty English phrases, we use IBM Model 1 as

Note that the length model p(J (t) |I (mt) ) plays an important role in learning IBMmodel 1 from non-parallel corpora since the model needs to choose among source phrases with various lengths.

Therefore, the phrase translation model is defined as

As learning translation models from non-parallel corpora is a very challenging task, many authors assume that a small parallel lexicon is readily available [Zhang and Zong, 2013]. Hence, we define a penalization term similar to the KullbackLeibler divergence to incorporate prior knowledge into the model:

where d is a parallel lexicon and σ(f, e, d) checks whether 〈f, e〉 exists in the lexicon:

4 Training

4.1 The Viterbi EMAlgorithm

Given monolingual corpora F and E and a parallel lexicon d, the training objective is given by

It is natural to use the EM algorithm to estimate the model parameters. The expected count of the length model c(J|I; F, E) is given by

The expected count of the translation model c(f |e; F, E) is given by

Unfortunately, calculating the two expectations in Eq. (17) and (18) on the training data is intractable due to the exponential search space of phrase matching.

1: procedure VITERBIEM(F,E, d) 2: Initialize θ(0) 3: for all k = 1, . . . ,K do 4: ˆm(k) ← ALIGN(F, E, θ(k-1) ) 5: θ(k) ←UPDATE(F,E, d, ˆm(k) ) 6: end for 7: return ˆm(K) , θ(K) 8: end procedure

Instead, we use a Viterbi EM algorithm as shown in Figure 1. The algorithm takes a set of foreign phrases F , a set of English phrases E, and a parallel lexicon d as input (line 1). After initializing model parameters (line 2), the algorithm calls the procedure ALIGN(F, E, θ) to compute the Viterbi matching between F and E (line 4). Then, the algorithm updates the model by normalizing counts collected from the Viterbi matching (line 5). This process terminates after K iterations and returns the final matching and model.

4.2 Computing Viterbi Matching

Given a set of foreign phrases F and a set of English phrases E, the Viterbi matching is defined as

It is clear that computing the Viterbi matching for individual foreign phrases is independent. We only need to focus on finding the most probable English phrase for each foreign phrase:

For the empty English phrase (i.e., s = 0), the translation probability is simply ϵ. For non-empty English phrases, the decision rule is

Therefore, the Viterbi matching for a foreign phrase can be determined by

We can see that ϵ determines whether a foreign phrase is unaligned or not. This is important for preventing a foreign phrase that has no counterparts on the English side from connecting to a wrong English phrase.

Computing ˆmt in Eq. (22) is computationally expensive if S is very large. In practice, we use information retrieval (IR) techniques to speed up the computation, which has been suggested by Zhang and Zong [2013]. While standard crosslingual IR focuses on the relevance between queries and documents and ignores function words (e.g., punctuations), our goal is to find translations in the set of English phrases. Both content and function words are important for indexing and retrieval. Therefore, we use translation probabilities instead of termweights such as tf.idf in retrieval for indexing.

We build a term-document incidence matrix M ∈ R|Vf |×S for all foreign words, where Vf is the foreign vocabulary. Each element in the matrix M(f, s) stores the probability that f connects to the s-th English phrase. This can be done by exploiting the translation probabilities of f given the English words in e(s) . For example, suppose the 621-th English phrase is "the program has been implemented" and p("chengxu"|"program") = 0.58, we set M("chengxu", 621) = 0.58. If another English word is also a translation of "chengxu", the matrix retains the highest translation probability. Hence, English phrases can be efficiently retrieved in a monolingual way.

For efficiency, we use a coarse-to-fine approach to computing the Viterbi matching for non-empty English phrases. First, the term-document incidence matrix is used to filter most unlikely source phrases and return a coarse set of candidates. Then, phrase translation probabilities are exactly calculated using Eq. (12).

4.3 UpdatingModel Parameters

Given the Viterbi matching, the count of the length model c(J|I; F,E) is simply

The count of the translation model c(f|e; F, E) is given by

5 Experiments

5.1 Matching Evaluation

To measure how well our approach identifies parallel phrases from non-parallel corpora F and E, we define the matching accuracy as

where T is number of all foreign phrases, ˆm is the Viterbi matching predicted by a model, and m∗ is the gold-standard matching.

As annotating gold-standard matching manually is both time-consuming and labor-intensive, we resort to an automatic approach instead. Given a parallel corpus, we extract a set of parallel phrases {〈f (n) , e(n) 〉}Nn=1 , in which the matching between foreign and English phrases are readily available. Then, the parallel phrase set is corrupted by removing and adding foreign and English phrases randomly. Foreign phrases that have no counterparts on the English side, which we refer to as noises, are set to connect to the empty English phrase in the gold-standard matching.

Table 1 shows the statistics of the development set, test set, and parallel dictionary. We used Chinese-English parallel corpus consisting 1,200K pairs of sentences from LDC to extract parallel phrases. From the parallel phrases, we constructed two kinds of monolingual corpora: development set and test set. The development set is used to optimize hyperparameters such as the empty phrase translation probability ϵ. It consists of 2,000 Chinese phrases and 4,000 English phrases (2,000 correspond to Chinese phrases and another 2,000 are noises). The Chinese phrase set has 2,994 distinct words and the English phrase set has 4,366 distinct words. The test set contains 20K Chinese phrases and 40K English phrases. The maximum phrase length is set to 7. The translation probability table learned from the parallel corpus serves as a bilingual lexicon, which has 1,000 entries.

We first use the development set to optimize the hyperparameter ϵ. Table 2 shows the effect of empty translation probability ϵ on matching accuracy. The Vierbi EM algorithm runs for 10 iterations. We find that ϵ does not have a significant impact on accuracy. Therefore, we set ϵ to e-30 in the following experiments.

Table 3 shows the log-likelihood and matching accuracy on the development set. We set ϵ = e-30 and the Viterbi EM algorithm ran for 10 iterations. Clearly, the log-likelihood has a high correlation with matching accuracy.

Table 4 shows the effect of dictionary size on matching accuracy. Clearly, using larger seed dictionaries improves the accuracy dramatically. We find that the accuracy reaches 95.28% when the dictionary is enlarged to contain 3,000 entries. This can be seen as an oracle accuracy since the dictionary with 3,000 entries covers most words in the development set.

Table 5 shows the effect of noises on matching accuracy. We find that the accuracy decreases with the increase of noises. Without noises, our model is able to achieve an accuracy of 59.30%.

Our final result on the test set is 40.18% as shown in Figure 2. The Viterbi EM algorithm ran for 70 iterations, the dictionary size is 1,000, and the empty translation probability ϵ = e-30 .

We analyzed the errors made by our model and found that most wrongly identified phrases are actually very close to the gold-standard phrases. For example, given a Chinese phrase "ta biaoshi jingji", our model identifies an English phrase "he says economy" while the gold-standard phrase is "he said economy". Therefore, although the matching accuracy is relatively low, the identified phrase pairs are still valuable for machine translation, as shown in the following section.

5.2 Translation Evaluation

We follow Zhang and Zong [2013] to evaluate our approach on domain adaptation for machine translation. Given an outdomain parallel corpus L and an in-domain non-parallel corpus U, the task is to maximize the translation performance on unseen in-domain text.

Our experiment runs as follows:

1. Train IBMmodel 1 on the out-domain parallel corpus L and obtain initial model parameters θ;
2. Identify parallel phrase pairs P from the in-domain nonparallel corpus U using θ;
3. Evaluate the combined parallel corpora L∪P by training phrase-based models and calculating the BLEU score on unseen in-domain test set;
4. Update model parameters θ on L ∪ P ;
5. Goto step 2 or terminate if the number of iterations reaches the pre-defined limit (e.g., 5).

The out-domain parallel corpus L (financial articles from FTChina) we used consists of 7,360 pairs of Chinese-English phrases with 41,279 Chinese words and 41,123 English words. The average lengths of Chinese and English phrases are 5.61 and 5.59. The in-domain non-parallel corpus U (news reports from LDC) consists of 2,935,265 Chinese phrases and 3,961,087 English phrases. The average lengths of Chinese and English phrases are 5.67 and 5.91.

We used Moses [Koehn and Hoang, 2007] to learn phrasebased translation models on the combined parallel corpus L∪P and evaluate translation performance on NIST datasets. We used the SRILM toolkit [Stolcke, 2002] to train a 4-gram language model on the Xinhua portion of the GIGAWORD corpus, which contains 238M English words. The NIST 2002 MT Chinese-English dataset is our the development set and the NIST 2005 dataset is the test set. The evaluation metric is case-insensitive BLEU4 [Papineni et al., 2002].

Table 6 lists the statistics of constructed parallel corpus L∪P and resulting BLEU scores. At iteration 0, only the outdomain parallel corpus L is used. Then, our system iteratively extracts parallel phrases from the in-domain non-parallel corpus U. We find that the constructed parallel corpus keeps growing by including new phrase pairs that do not exist in L. The size of translation probability table of IBMModel 1 also increases significantly, suggesting that our approach is able to learn translations of unseen words. As a result, our approach achieves statistically significant improvements than using the starting out-domain parallel corpus.

Table 7 shows some example learned parallel phrases. Note that these phrases do not exist in the out-domain parallel corpus L. Words that are unseen in L are highlighted in bold. We find that 39.27% of learned phrases contain words only seen in L (e.g., No 1 in Table 7), 25.68% contain one word unseen in L (e.g., No 2 and No 3 in Table 7), 19.92% contain two unseen words, and 7.18% contain three unseen words. This finding suggests that our approach is capable of enlarging the vocabulary and learning new phrase pairs.

6 RelatedWork

Joint Parallel Sentence and Lexicon Extraction. Advocating the "find-one-get-more" principle, Fung and Cheung [2004] propose an iterative framework to extract parallel sentences and lexicons from non-parallel corpora via boostrapping and EM. They first use similarity measures to match documents in non-parallel corpora and then extract parallel sentences and new translations from these documents by exploiting bootstrapping on top of IBM model 4. While similar in spirit to their idea, our work assumes that parallel phrases exist in monolingual corpora and develops a new model to capture the correspondence between monolingual phrases in a principled way.

Parallel Sub-Sentential Fragment Extraction. Observing that comparable corpora often contain parallel words or phrases, a number of authors have proposed to extract such parallel fragments from noisy parallel sentences [Munteanu and Marcu, 2006; Quirk et al., 2007; Cettolo et al., 2010]. They first extract candidate parallel sentences from comparable corpora and then identify parallel fragments from the noisy candidate parallel sentences. This approach assumes that comparable corpora are readily available and focuses on finding parallel fragments within comparable sentence pairs, our approach directly builds a generative model on fragments, which can be n-grams extracted from monolingual corpora.

Extracting Parallel Phrases using Lexicons. Our work is also similar to [Zhang and Zong, 2013] that exploits a bilingual lexicon to retrieve parallel phrases from monolingual corpora. The major difference is that their approach is non-iterative. Our approach uses a Viterbi EM algorithm and can improve the learned model iteratively. Experiments show that our iterative approach significantly outperforms the noniterative approach (see Table 6: 13.40 vs. 11.21).

Translation as Decipherment. Another interesting line of research casts translation with monolingual corpora as a decipherment problem [Ravi and Knight, 2011; Nuhn et al., 2012; Dou and Knight, 2012]. They develop word-based generative models on monolingual corpora and use sampling methods for efficient training. While our approach is also based on word-based translation model, it constructs parallel corpus in the EM loop, which significantly reduces the training complexity.

Transductive Learning on Monolingual Corpora. A number of authors leverage transductive learning to make full use of monolingual data [Ueffing et al., 2007; Bertoldi and Federico, 2009]. They use an existing translation model to translate unseen source-language text. Then, the input and their translations constitute a pseudo parallel corpus. This process iterates until convergence. Zhang and Zong [2013] indicate that this approach can hardly learn new translations consisting of words unseen in the seed parallel corpora.

7 Conclusion

We have presented an iterative approach to learning parallel lexicons and phrases from non-parallel corpora. Experiments show that iterative learning can offer valuable parallel phrases to machine translation systems. In the future, we plan to extend our approach to include more sophisticated alignment models such as IBM models 2-5 and HMM [Vogel et al., 1996]. It is also interesting to scale up to web text and build a never-ending parallel lexicon and phrase mining system.

Acknowledgements

Yang Liu and Maosong Sun are supported by the National Natural Science Foundation of China (No. 61331013 and No. 61432013), the 863 Program (2015AA011808) and Toshiba Corporation Corporate Research & Development Center. Huanbo Luan is supported by the National Natural Science Foundation of China (No. 61303075). This research is also supported by the Singapore National Research Foundation under its International Research Centre@Singapore Funding Initiative and administered by the IDM Programme.