A Bilingual Graph-Based Semantic Model for Statistical Machine Translation

1 Introduction

Continuous representations of words onto multi-dimensional vectors enhance traditional natural language processing [Zhao et al., 2010; Zhao and Kit, 2011; Zhao et al., 2013; Zhang and Zhao, 2013], especially Statistical Machine Translation (SMT), by measuring similarities of words using distances of corresponding vectors [Bengio et al., 2003; Mikolov et al., 2013b; Wang et al., 2016a]. Most of early works are derived from cognitive processing such as WordNet [Miller et al., 1990], in which the lexicon is organized conceptually as a set of terms associated with a partition into synsets 1 , though words organized in this way are not conveniently represented as vectors.

⇤Corresponding authors. R. Wang, H. Zhao and B. L. Lu were partially supported by Cai Yuanpei Program (CSC No. 201304490199 and No. 201304490171), National Natural Science Foundation of China (No. 61170114 and No. 61272248), National Basic Research Program of China (No. 2013CB329401), Major Basic Research Program of Shanghai Science and Technology Committee (No. 15JC1400103), Art and Science Interdisciplinary Funds of Shanghai Jiao Tong University (No. 14JCRZ04), and Key Project of National Society Science Foundation of China (No. 15-ZDA041).

Word embedding for vector representation is usually built in two-steps. The first is to determine the detailed context related to a given word. The second is to summary the relationship between word and its context into lower dimensions.

For context determination: 1) The first category is to extract the word or word relations from the entire text, which is usually regarded as document level processing, such as bag-of-word, LSA, and LDA. 2) The second category is to use sliding window, such as n-grams, skip-grams and other local co-occurrence relation [Mikolov et al., 2013a; Zou et al., 2013; Levy and Goldberg, 2014; Pennington et al., 2014; Vuli´c and Moens, 2015]. 3) The third category, which has been seldom considered, uses much more sophisticated graph style context. Ploux and Ji [2003] describe a graph based semantic matching model using bilingual lexicons and monolingual synonyms 2 . They later represent words using individual monolingual co-occurrences [Ji and Ploux, 2003]. Saluja et al. [2014] propose a graph method to generate translation candidates using monolingual co-occurrences.

For relationship summarising, neural networks are very popular for bilingual word embeddings and SMT [Mikolov et al., 2013a; Wang et al., 2013; Zou et al., 2013; Zhang et al., 2014; Gao et al., 2014; Wang et al., 2014; Lauly et al., 2014; Wang et al., 2015; 2016b]. There are also some works which use matrix factorization [Ploux and Ji, 2003; Pennington et al., 2014; Shi et al., 2015] and canonical correlation analysis [Faruqui and Dyer, 2014; Lu et al., 2015] for word embedding.

Sense gives more exact meaning formulization than the word form itself. However, most of existing methods embed words as vectors, instead of sense information. Motivated by these inconveniences, we propose Bilingual Contexonym Cliques (BCCs), which are extracted from bilingual Point-wise Mutual Information (PMI) based word cooccurrence graph. BCC plays a role of minimal unit for bilingual sense representation. Correspondence Analysis (CA) is then used for summarizing BCC-word matrix into lower dimension vectors for word representation. This work extends previous monolingual method [Ploux and Ji, 2003], which needs bilingual lexicons or synonyms for bilingual mapping and has been never used for SMT.

1 synset is a small group of synonyms labeled as a concept.

2 http://dico.isc.cnrs.fr

The remaining of this paper is organized as follows: the proposed Bilingual Graph-based Semantic Model (BGSM) is introduced in Section 2, and then it is applied to phrase translation probability estimation in Section 3 and phrase pair generation in Section 4 to enhance SMT. The experiments and analysis are given in Section 5. Section 6 summarizes this work.

2 Bilingual Graph-based Semantic Model

2.1 Graph Constructing

Formally, words are considered as nodes (vertices) and cooccurrence relationships of words are considered as edges of graph. An edge-weighted graph derived from a bilingual corpus is formalized as, G = ¶W↪ E♦, where W is node set and E is edge set which is weighted by co-occurrence relationship introduced as follows.

For a given bilingual parallel corpus, each source sentence SF = (wf1 ↪wf2 ↪ ▷▷▷↪wfk ) and its corresponding target sentence SE = (we1 ↪we2 ↪ ▷▷▷↪wel ) are combined together to construct a Bilingual Sentence (BS) = (wf1 ↪wf2 ↪ ▷▷▷↪wfk ↪we1 ↪we2 ↪ ▷▷▷↪wel ). For words (either source or target word) wi and wj , if they are in the same BS, they are called co-occurrences for each other and marked as ni and nj in the graph G. As node ni in graph is always referred to word wi, we will not distinguish them throughout this paper. The Edge Weight (EW) connecting nodes ni and nj is defined by a PMI score,

where Co(ni↪ nj) is the co-occurrence counting of ni and nj and fr(n) stands for how many times n occurs in corpus.

For nearly all languages, stop words such as of, a, the in English or de, une, la in French have a wide distribution, and this results in that most nodes in the graph are unnecessarily connected with these stop word nodes. A filter with an EW threshold γ is thus set to prune these poorly connected edges. γ will be tuned using development data, to let the resulted graph keep the more useful edges based on the empirical result of each individual task.

2.2 Context-Dependent Clique Extraction

A clique defined in graph theory means a maximum, complete sub-graph [Luce and Perry, 1949]. For a subset of nodes with edges in the whole graph, if every two nodes in the subset are connected to each other, this subset of nodes form a clique. Suppose that both N1 and N2 are subsets of N in G. If N1 ⇢ N2, then N1 cannot be a clique (maximality).

Graph problems, such as finding all cliques from a graph, are mostly associated with high computational complexity (Clique Problem). The Clique Problem related to our model has been shown NP-complete [Karp, 1972], and it is time consuming or even impossible to find the cliques from the whole graph built from a very large corpus (such as millions of sentences) without any pruning. In addition, not all of the nodes are useful for word representations, because some nodes do not have any connection with input contextual words (sparsity). These nodes actually have not a direct impact over clique extraction. For a word n and its contextual words ¶n1↪ n2↪ ▷▷▷↪ ni↪ ▷▷▷nt♦ as input 3 , only the co-occurrence nodes nij of each ni (including n itself) are indeed useful and then actually extracted. The set of nodes ¶nij♦ with their weighted edges form an extracted graph Gextracted for further cliques extraction. So the number of nodes in the extracted graph Gextracted, ♣Nextracted♣, is given by,

In practice, the ♣Nextracted♣ is much smaller than ♣V ♣ (vocabulary size of bilingual corpus). For a typical corpus (IWSLT in Section 5.1), ♣Nextracted♣ is around 371.2 on average and ♣V ♣ is 162.3K. Thus the clique extraction in practice is quite efficient as it works over a quite small sized graph.

Clique extraction may follow a standard routine in [Luce and Perry, 1949]. As the clique in this paper is to represent a fine grained bilingual sense of a word, it is called Bilingual Contexonym Clique (BCC). Similar but more fine grained than synset (a small group of synonyms labeled as concept) defined in WordNet [Miller et al., 1990], the BCC now is the minimal unit for bilingual meaning representation.

Taking the word work e and readers e as an example (without context), two groups of BCCs (in alphabetical order) are given in Table 1. It shows that different word senses can be distinguished by BCCs. The BCCs containing employees e, travail f (work) and unemployed e may indicate the meaning of job, while the BCCs containing readers e may indicate the meaning of literature.

3 For SMT task, the words in aligned phrases are used as context, please refer to Section 3 for details.

Note that edges pruning is static, and nodes selection is dynamic depending on input word sequence. The proposed node selection and clique extraction follow [Ploux and Ji, 2003], except that we use bilingual co-occurrence graph rather than monolingual synonym or hypo(hypero)nym graphs. BCCs can be regarded as loose synsets, as only strongly related words can be nodes in a clique that possess full connections, and different senses will naturally result in roughly different cliques from our empirical observations, though noise or improper connections also exist at the same time. To obtain concise semantic vector representations, a dimension reduction will be performed.

2.3 Semantic Spatial Representation

Correspondence Analysis (CA) [Benzcri, 1973] assesses the extent of matching between two variables. It determines the first n factors of a system of orthogonal axes that capture the greatest amount of variance in the matrix. The first axis (or factor) captures the largest variations, the second axis captures the second largest, and so on.

To project words onto lower dimensional semantic space, CA is conducted over the clique-word matrix constructed from the relation between BCCs and words. An initial correspondence matrix M = ¶mij♦ is built, where mij = 1 if the BCC in row i contains the word in column j, and 0 if not. Normalized correspondence matrix P = ¶pij♦ is directly derived fromM, where pij = mij◁NM, and NM is grand total of all the elements inM. Let the row and column marginal totals of P be r and c which are the vectors of row and column masses, respectively, and Dr and Dc be the diagonal matrices of row and column masses. Coordinates of the row and column profiles with respect to principal axes are computed by using the Singular Value Decomposition (SVD) as follows.

Principal coordinates of rows F and columns G:

where U, V and ⌃ (diagonal matrix of singular values in descending order) are from the matrix of standardized residuals S and the SVD,

where ⇤ denotes conjugate transpose and U ⇤U = V ⇤V = I. By above processes, CA projects BCCs (F) and words (G) onto semantic geometric coordinates as vectors. Inertia χ2 ◁NM is to measure semantic variations of principal axes for F and G:

Following standard setting of CA [Benzcri, 1973], top principal dimensions (axes) of vectors are chosen for word and clique representation. Bilingual Graph-based Semantic Model (BGSM) is consequently constructed from these principal dimensions. In short, a word with its context are used as input of BGSM, and vectors of the word 4 and its bilingual co-occurrences are output.

4 In fact both BCCs and words can be represented as vectors.

To visualize the results, top two dimensions are chosen and illustrated into spatial map. We illustrate the spatial relationship between BCCs and words in the same map, instead of the spatial map of words only. BCCs are represented by points and words by regions. Label of word is approximately (to avoid overlapping) placed at the barycentre of region (gray line) delineated by a set of BCCs that contain the word. BCCs are clustered [Ward Jr, 1963] into three groups (green line). We only present several typical words, and the words too far from most of other words are discarded.

Figures 1 and 2 illustrate the spatial representation of all the co-occurrence words when work e is input without context and with readers e as context using BGSM, respectively. The following observations can be obtained from them:

1) Several good translation pairs are shown, such as (work e, travailler f ), (readers e, lecteurs f ), (reading e, lire f ) and (book e, livre f ).

2) For work e as input, the word work e itself is placed at the center and the other words are mainly clustered into three semantic groups: employment (the right), evaluation of job (the upper left), and literary works 5 (the bottom). However, we cannot determine which sense of work e belongs to.

3) For work e+readers e as input, we can identify that the sense of work e by the words close to both of work e and readers e, such as book e, print e and paper f.

3 Phrase Translation Probability Estimation

BGSM represents words as vectors dynamically on various geometric coordinates according to contextual words. For each word in a source phrase of SMT, its contextual words are fixed, so all the translation candidate target words can be represented as vectors in the same geometric coordinates. This makes it possible to apply BGSM into phrase-based SMT for selecting translated phrase candidates.

3.1 Bilingual Phrase Semantic Representation

The phrase table of phrase-based SMT model can be simply formalized as 6 ,

where PF (wf1 ↪wf2 ↪ ▷▷▷↪wfk ) and PE(we1 ↪we2 ↪ ▷▷▷↪wel ) are source and its aligned target phrases, respectively, and scores indicate various feature scores including direct translation probability, lexical weighting and phrase penalty. The phrase length is limited to 7, which is the default setting for phrasebased SMT.

BGSM represents words in phrase table as six-dimension vectors. It should be noted that the clique extraction depends on contextual words, and CA then projects clique-word matrix onto corresponding semantic geometric coordinates accordingly. So the same contextual words should be used for all the words in PF and all its aligned PE, in order to represent them on the same geometric coordinates. For each word wfi or wej (where 1  i  k, 1  j  l), in phrase pair

5 Part of borderline of this cluster is overlapped by some words.

6 The alignment is from standard IBM alignment model [Berger et al., 1994].

(PF ↪ PE), we consider two strategies for selecting the context words:

Strategy-A: only the source words in PF are used as the contextual words, ¶wf1 ↪ wf2 ↪ ▷▷▷↪ wfk ♦.

Word wfi (or wei) is represented as vector Vwfi (or Vwej ) (The co-occurrence word wco can also be represented as vector Vwco ). Note that all the source and target words for the same source phrase PF are represented as vectors in the same geometric coordinates. Some words may not belong to any BCC (partially because the graph is pruned). These unknown words would be represented as a default vector.

Strategy-B: both the source words in PF and target words in all the aligned PE are used as its contextual words, ¶wf1 ↪ wf2 ↪ ▷▷▷↪ wfk ↪ we1 ↪ we2 ↪ ▷▷▷↪ wel ♦.

3.2 Semantic SimilarityMeasurement

Because the numbers of word alignments in phrase pairs are different, Normalized Euclidean Distance (NED) is adopted to measure the distance between source and target phrases incorporated with IBM word-alignment model:

As there are usually multiple PE that are aligned to PF , NPE is noted as the number of aligned PE. To let the similarity score Sim(PE♣PF ) be a probability distribution, Sim(PE♣PF ) =1 if NPE = 1; otherwise, Sim(PEi ♣PF ) is given by,

where ED(Vwfi ↪ Vwej ) stands for Euclidean Distance between word vectors Vwfi and Vwej , align(i↪ j) is from the word-alignment model in Eq. (2), and Pi↪j align(wfi ↪wej ) is total number of word alignments between PF and PE.

(4)

Using the same pipeline, Sim(PF ♣PE) can also be calculated. Both Sim(PE♣PF ) and Sim(PF ♣PE) can be added as features for SMT decoding.

4 Bilingual Phrase Generation (BPG)

A few phrases are outside corpus but share the similar meaning as those inside the corpus. Take the source French phrase la bonne r´eponse as example, the corresponding aligned target English phrase the right answer is in the corpus and phrase table. The other phrases, such as the correct answer or the right response, may not be in the corpus or phrase table, however, they are also good candidates for translation.

Since the BGSM can be used to represent words as vectors and measure their similarities by computing vector distance, it is possible to generate new (maybe better) phrases with similar meaning as the original one for phrase table.

4.1 Phrase Pair Generation

As mentioned in Section 3, for each word w (source or target), both of the source words in PF and target words are used as its contextual words (Strategy-B). Word w and its cooccurrence words ¶wco♦ are represented as vectors.

For an aligned word pair (wfi , wej ), we find a new translation replacement w0ej in ¶wco♦ to help generate new phrases. For either source phrase PF or target phrase PE, each word inside will be tentatively replaced by the nearest word in its corresponding co-occurrence according to word vector distance (here, Euclidean distance is actually adopted.). However, only one word replacement with the minimal distance for either phrase will be chosen and implemented to generate two new phrases P 0E and P 0F , respectively 7 .

Sim(P 0E ♣PF ) and Sim(P 0F ♣PE) can be calculated using Eqs. (3) and (4). They are also being the phrase transition probabilities for the generated (PF , P 0E ) and (P 0F , PE), respectively, as no such probabilities exist in the original phrase table. The updated lexical weighting lex(P 0E ♣PF ) and inverse lexical weighting lex(P 0F ♣PE) are computed by IBM model [Berger et al., 1994].

The generated phrases are filled-up [Bisazza et al., 2011] into original phrase table. That is, a penalty score is added as feature: for original phrase pairs, the penalty is set as one; for the generated ones the penalty is set as natural logarithm base e (= 2.71828...). All scores weights in phrase table will be further tuned using MERT [Och, 2003].

4.2 Prase-table Size Tuning

Using the phrase generation approach, a lot of new phrase pairs can be generated. We need to select the most reasonable ones inside them. The Distance Ratio (DR) of normalized distance in Eq. (4) between the generated phrase pair (PF ↪ P 0E ) and the original phrase pair (PF ↪ PE),

is used to measure the usefulness of generated phrase pairs.

A threshold " is set up to keep the most useful generated phrase pair only. Namely, for a source phrase PF , only the P 0E whose DR(P 0E ↪ PE) smaller than " are selected as the generated phrase pair (PF ↪ P 0E ). Using the same pipeline, the size of generated source candidate phrases is also tuned. For SMT task, the threshold is tuned according to SMT performance on development data.

5 Experiments

5.1 Setting up

To evaluate BGSM in various language and domain SMT systems, Corpora of IWSLT-2014 French to English (EN) [Cettolo et al., 2012], NTCIR-9 Chinese to English [Goto et al., 2011] and NISTOpenMT08 8 are chosen.

7 Two or more words can be replaced, but it may lead to serious sense bias, and the experiments also show that replacing more than two words does not perform well.

8 Zou et al. [2013] only released their word vectors rather than their code (http://ai.stanford.edu/⇠wzou/mt/), so we have to conduct experiments on NIST08 Chinese-English translation task as they did for comparison. The training data consists of part of NIST OpenMT06, United Nations Parallel Text (1993-2007) and corpora

5.2 Baseline Systems

The same basic settings for the IWSLT-2014, NTCIR-9 and NIST08 translation baseline systems are complied. The standard Moses phrase-based SMT system is applied [Koehn et al., 2007] together with GIZA++ [Och and Ney, 2004] for alignment, SRILM [Stolcke, 2002] for language modeling and MERT for tuning (we run MERT three times and record the average BLEU score on test data). The paired bootstrap re-sampling test 9 is performed. Significant tests are done for each round of test. Marks at the right of BLEU scores indicate whether our proposed methods are significantly better/worse than the corresponding baseline ('++/--': significantly better/worse at significance level ↵ = 0▷01; '+/-': ↵ = 0▷05). All the experiments in this paper are conducted on the same machine with 2.70GHz CPU.

As the proposed BGSM is a bilingual word embedding method and applied to SMT as new features, we only compare with most related bilingual word embedding or generation methods for SMT. For phrase pair translation probability estimation task, two typical neural network based bilingual embedding methods, Continuous Space Translation Model (CSTM 10 ) [Schwenk, 2012] and [Zou et al., 2013], are select as baselines. The embedding of each method is added as features to the phrase-based SMT baseline, with all the other setting the same. For bilingual phrase generation methods, CSTM is used as the same way as [Schwenk, 2012]'s generation method. We also compare with [Saluja et al., 2014], which uses graph method for translation candidate generation 11 .

5.3 Results and Analysis

Only the best performed results (for both the baselines and proposed methods) on development data are chosen to be evaluated on test data and shown. The parameters for BGSM are set as follows: 1) Vector dimensions are 6; 2) Threshold γ for edge weight pruning EW in Eq. (1) is 3 ⇥ 10-4 ; 3) Threshold " for phrase table tuning DR in Eq. (5) is 1.31.

of [Galley et al., 2008] that were used by [Zou et al., 2013]. NIST Eval 2006 is used as development data and NIST Eval 2008 as test data.

9 The implementation of our system follows http://www.ark.cs. cmu.edu/MT

10 The recommended settings of CSTM [Schwenk, 2012] are followed. That is, phrase length limit is set as 7, shared 320-dimension projection layer for each word (that is 2240 for 7 words), 768dimension projection layer, 512-dimension hidden layer. The dimensions of input/output layers are the same as the size of vocabularies of source/target words.

11 The implementation and settings in [Saluja et al., 2014] are followed except morphological generation.

Phrase Pair Translation Probability Estimation Results

Table 3 indicates that BGSM can improve SMT performance up to +0.85 BLEU, and outperforms CSTM or Zou's methods up to +0.67 BLEU. Besides, the Strategy-B performs better than Strategy-A, which attributes to more contextual (both target and source) information used for the former while only source for the latter.

Bilingual Phrase Pair Generation Results

'Baseline + BPG' indicates adding the generated phrase pairs to the original phrase table. 'BPG + BGSM' indicates adding the generated phrase pairs, as well as replacing the translation probabilities in original phrase table with the Sim(PE♣PF ) and Sim(PF ♣PE) calculated by BGSM (Section 4.1).

The results in Table 4 indicate that the proposed BPG and BGSM methods can work well together and enhance SMT performance significantly up to +1.33 BLEU. They also outperform state-of-the-art method up to +0.79 BLEU.

Efficiency Comparison

We compare the efficiencies for model training and computing the probability scores of phrases pairs using CSTM and BGSM. Two thousand phrase pairs are randomly selected from the whole IWSLT-2014 FR-EN corpus. The CPU time of training models (the whole corpus) and calculating their probability scores (2,000 sentences) is shown in Table 5.

The results in Table 5 demonstrate that BGSM is much more efficient than CSTM, especially for training, the former can be more than 50 times as fast as the later.

6 Conclusion

Existing word embedding methods usually only consider simple context such as document or sliding window for word relationship building and later word representation. Instead, this paper focuses on sense representation in terms of bilingual background. Using a graph constructed from a bilingual corpus, Bilingual Contexonym Clique (BCC) is proposed for better sense characterization. A BCC-word matrix is then built from dynamic sense-sensitive context in the graph and correspondence analysis is to summarize the matrix into lower dimensions as Bilingual Graph Semantic Model (BGSM).

BGSM word embedding is applied to phrase pair translation probability estimation and generation. The experimental results show that the proposed model can enhance phrasebased SMT decoding and achieve a significant improvement with high computational efficiency. It also outperforms the existing related word embedding methods for SMT.