Neural Machine Translation with Source-Side Latent Graph Parsing

Introduction

Neural Machine Translation (NMT) is an active area of research due to its outstanding empirical results (Bahdanau et al. 2015; Luong et al. 2015; Sutskever et al. 2014). Most of the existing NMT models treat each sentence as a sequence of tokens, but recent studies suggest that syntactic information can help improve translation accuracy (Eriguchi et al. 2016b; Eriguchi et al. 2017; Sennrich and Haddow 2016; Stahlberg et al. 2016). The existing syntax-based NMT models employ a syntactic parser trained by supervised learning in advance, and hence the parser is not adapted to the translation tasks. An alternative approach for leveraging syntactic structure in a language processing task is to jointly learn syntactic trees of the sentences along with the target task (Socher et al. 2011; Yogatama et al. 2017).

Motivated by the promising results of recent joint learning approaches, we present a novel NMT model that can learn a task-specific latent graph structure for each source-side sentence. The graph structure is similar to the dependency structure of the sentence, but it can have cycles and is learned specifically for the translation task. Unlike the aforementioned approach of learning single syntactic trees, our latent graphs are composed of “soft” connections, i.e., the edges have real-valued weights (Figure 1). Our model consists of two parts: one is a task-independent parsing component, which we call a latent graph parser, and the other is an attention-based NMT model. The latent parser can be independently pre-trained with human-annotated treebanks and is then adapted to the translation task.

In experiments, we demonstrate that our model can be effectively pre-trained by the treebank annotations, outperforming a state-of-the-art sequential counterpart and a pipelined syntax-based model. Our final ensemble model outperforms the previous best results by a large margin on the WAT English-to-Japanese dataset.

Latent Graph Parser

2 POS Tagging Layer

3 Dependency Parsing Layer

Then, (soft) edges of our latent graph representation are obtained by computing the probabilities

NMT with Latent Graph Parser

The latent graph representation described in Section 2 can be used for any sentence-level tasks, and here we apply it to an Attention-based NMT (ANMT) model (Luong et al. 2015). We modify the encoder and the decoder in the ANMT model to learn the latent graph representation.

In the sequential LSTMs, relationships between words in distant positions are not explicitly considered. In our model, we explicitly incorporate such relationships into the encoder by defining a dependency composition function:

where $\overline{h}(H_{w_{i}})=\sum_{j\neq i}p(H_{w_{i}}=w_{j}|w_{i})h^{(enc)}_{j}$ is the weighted average of the hidden states of the parent nodes.

In NMT models, sub-word units are widely used to address rare or unknown word problems (Sennrich et al. 2016). In our model, the character $n$-gram embeddings are fed through the latent graph parsing component. To the best of our knowledge, the character $n$-gram embeddings have never been used in NMT models. Wieting et al. 2016, Bojanowski et al. 2017, and Hashimoto et al. 2017 have reported that the character $n$-gram embeddings are useful in improving several NLP tasks by better handling unknown words.

2 Decoder with Attention Mechanism

where $s(i,t)$ is a scoring function which specifies how much each source-side hidden state contributes to the word prediction.

In addition, like the attention mechanism over constituency tree nodes (Eriguchi et al. 2016b), our model uses attention to the dependency composition vectors:

The overall model parameters, including those of the latent graph parser, are jointly learned by minimizing the negative log-likelihood of the prediction probabilities of the target words in the training data. To speed up the training, we use BlackOut sampling (Ji et al. 2016). By this joint learning using Equation (3) and (7), the latent graph representations are automatically learned according to the target task.

Inspired by Zoph et al. 2016, we further speed up BlackOut sampling by sharing noise samples across words in the same sentences. This technique has proven to be effective in RNN language modeling, and we have found that it is also effective in the NMT model. We have also found it effective to share the model parameters of the target word embeddings and the softmax weight matrix for word prediction (Inan et al. 2016; Press and Wolf 2017). Also, we have found that a parameter averaging technique Hashimoto et al. 2013 is helpful in improving translation accuracy.

Translation

At test time, we use a novel beam search algorithm which combines statistics of sentence lengths (Eriguchi et al. 2016b) and length normalization (Cho et al. 2014). During the beam search step, we use the following scoring function for a generated word sequence $y=(y_{1},y_{2},\ldots,y_{L_{y}})$ given a source word sequence $x=(x_{1},x_{2},\ldots,x_{L_{x}})$:

where $p(L_{y}|L_{x})$ is the probability that sentences of length $L_{y}$ are generated given source-side sentences of length $L_{x}$. The statistics are taken by using the training data in advance. In our experiments, we have empirically found that this beam search algorithm helps the NMT models to avoid generating translation sentences that are too short.

Experimental Settings

We used an English-to-Japanese translation task of the Asian Scientific Paper Excerpt Corpus (ASPEC) (Nakazawa et al. 2016b) used in the Workshop on Asian Translation (WAT), since it has been shown that syntactic information is useful in English-to-Japanese translation (Eriguchi et al. 2016b; Neubig et al. 2015). We followed the data preprocessing instruction for the English-to-Japanese task in Eriguchi et al. 2016b. The English sentences were tokenized by the tokenizer in the Enju parser (Miyao and Tsujii 2008), and the Japanese sentences were segmented by the KyTea tool http://www.phontron.com/kytea/.. Among the first 1,500,000 translation pairs in the training data, we selected 1,346,946 pairs where the maximum sentence length is 50. In what follows, we call this dataset the large training dataset. We further selected the first 20,000 and 100,000 pairs to construct the small and medium training datasets, respectively. The development data include 1,790 pairs, and the test data 1,812 pairs.

For the small and medium datasets, we built the vocabulary with words whose minimum frequency is two, and for the large dataset, we used words whose minimum frequency is three for English and five for Japanese. As a result, the vocabulary of the target language was 8,593 for the small dataset, 23,532 for the medium dataset, and 65,680 for the large dataset. A special token $\langle$UNK$\rangle$ was used to replace words which were not included in the vocabularies. The character $n$-grams ($n=2,3,4$) were also constructed from each training dataset with the same frequency settings.

2 Parameter Optimization and Translation

We turned hyper-parameters of the model using development data. We set $(d_{1},d_{2})=(100,50)$ for the latent graph parser. The word and character $n$-gram embeddings of the latent graph parser were initialized with the pre-trained embeddings in Hashimoto et al. 2017. The pre-trained embeddings can be found at https://github.com/hassyGo/charNgram2vec. The weight matrices in the latent graph parser were initialized with uniform random values in $[-\frac{\sqrt{6}}{\sqrt{row+col}},+\frac{\sqrt{6}}{\sqrt{row+col}}]$, where $row$ and $col$ are the number of rows and columns of the matrices, respectively. All the bias vectors and the weight matrices in the softmax layers were initialized with zeros, and the bias vectors of the forget gates in the LSTMs were initialized by ones (Jozefowicz et al. 2015).

We set $d_{3}=128$ for the small training dataset, $d_{3}=256$ for the medium training dataset, and $d_{3}=512$ for the large training dataset. The word embeddings and the weight matrices of the NMT model were initialized with uniform random values in $[-0.1,+0.1]$. The training was performed by mini-batch stochastic gradient descent with momentum. For the BlackOut objective (Ji et al. 2016), the number of the negative samples was set to 2,000 for the small and medium training datasets, and 2,500 for the large training dataset. The mini-batch size was set to 128, and the momentum rate was set to 0.75 for the small and medium training datasets and 0.70 for the large training dataset. A gradient clipping technique was used with a clipping value of 1.0. The initial learning rate was set to 1.0, and the learning rate was halved when translation accuracy decreased. We used the BLEU scores obtained by greedy translation as the translation accuracy and checked it at every half epoch of the model training. We saved the model parameters at every half epoch and used the saved model parameters for the parameter averaging technique. For regularization, we used L2-norm regularization with a coefficient of $10^{-6}$ and applied dropout (Hinton et al. 2012) to Equation (8) with a dropout rate of 0.2.

The beam size for the beam search algorithm was 12 for the small and medium training datasets, and 50 for the large training dataset. We used BLEU (Papineni et al. 2002), RIBES (Isozaki et al. 2010), and perplexity scores as our evaluation metrics. Note that lower perplexity scores indicate better accuracy.

3 Pre-Training of Latent Graph Parser

The latent graph parser in our model can be optionally pre-trained by using human annotations for dependency parsing. In this paper we used the widely-used Wall Street Journal (WSJ) training data to jointly train the POS tagging and dependency parsing components. We used the standard training split (Section 0-18) for POS tagging. We followed Chen and Manning 2014 to generate the training data (Section 2-21) for dependency parsing. From each training dataset, we selected the first $K$ sentences to pre-train our model. The training dataset for POS tagging includes 38,219 sentences, and that for dependency parsing includes 39,832 sentences.

The parser including the POS tagger was first trained for 10 epochs in advance according to the multi-task learning procedure of Hashimoto et al. 2017, and then the overall NMT model was trained. When pre-training the POS tagging and dependency parsing components, we did not apply dropout to the model and did not fine-tune the word and character $n$-gram embeddings to avoid strong overfitting.

4 Model Configurations

is our proposed model that learns the Latent Graph Parsing for NMT.

LGP-NMT+

is constructed by pre-training the latent parser in LGP-NMT as described in Section 4.3.

SEQ

is constructed by removing the dependency composition in Equation (3), forming a sequential NMT model with the multi-layer encoder.

DEP

is constructed by using pre-trained dependency relations rather than learning them. That is, $p(H_{w_{i}}=w_{j}|w_{i})$ is fixed to 1.0 such that $w_{j}$ is the head of $w_{i}$. The dependency labels are also given by the parser which was trained by using all the training samples for parsing and tagging.

UNI

is constructed by fixing $p(H_{w_{i}}=w_{j}|w_{i})$ to $\frac{1}{N}$ for all the words in the same sentence. That is, the uniform probability distributions are used for equally connecting all the words.

Results on Small and Medium Datasets

We first show our translation results using the small and medium training datasets. We report averaged scores with standard deviations across five different runs of the model training.

Table 2 shows the results of using the small training dataset. LGP-NMT performs worse than SEQ and UNI, which shows that the small training dataset is not enough to learn useful latent graph structures from scratch. However, LGP-NMT+ ($K$ = 10,000) outperforms SEQ and UNI, and the standard deviations are the smallest. Therefore, the results suggest that pre-training the parsing and tagging components can improve the translation accuracy of our proposed model. We can also see that DEP performs the worst. This is not surprising because previous studies, e.g., Li et al. 2015, have reported that using syntactic structures do not always outperform competitive sequential models in several NLP tasks.

Now that we have observed the effectiveness of pre-training our model, one question arises naturally:

how many training samples for parsing and tagging are necessary for improving the translation accuracy?

Table 2 shows the results of using different numbers of training samples for parsing and tagging. The results of $K$= 0 and $K$= 10,000 correspond to those of LGP-NMT and LGP-NMT+ in Table 2, respectively. We can see that using the small amount of the training samples performs better than using all the training samples. We did not observe such significant difference when using the larger datasets, and we used all the training samples in the remaining part of this paper. One possible reason is that the domains of the translation dataset and the parsing (tagging) dataset are considerably different. The parsing and tagging datasets come from WSJ, whereas the translation dataset comes from abstract text of scientific papers in a wide range of domains, such as biomedicine and computer science. These results suggest that our model can be improved by a small amount of parsing and tagging datasets in different domains. Considering the recent universal dependency project http://universaldependencies.org/. which covers more than 50 languages, our model has the potential of being applied to a variety of language pairs.

2 Medium Training Dataset

Table 3 shows the results of using the medium training dataset. In contrast with using the small training dataset, LGP-NMT is slightly better than SEQ. LGP-NMT significantly outperforms UNI, which shows that our adaptive learning is more effective than using the uniform graph weights. By pre-training our model, LGP-NMT+ significantly outperforms SEQ in terms of the BLEU score. Again, DEP performs the worst among all the models.

By using our beam search strategy, the Brevity Penalty (BP) values of our translation results are equal to or close to 1.0, which is important when evaluating the translation results using the BLEU scores. A BP value ranges from 0.0 to 1.0, and larger values mean that the translated sentences have relevant lengths compared with the reference translations. As a result, our BLEU evaluation results are affected only by the word $n$-gram precision scores. BLEU scores are sensitive to the BP values, and thus our beam search strategy leads to more solid evaluation for NMT models.

Results on Large Dataset

Table 5 shows the BLEU and RIBES scores on the development data achieved with the large training dataset. Here we focus on our models and SEQ because UNI and DEP consistently perform worse than the other models as shown in Table 2 and 3. The averaging technique and attention-based unknown word replacement Jean et al. 2015; Hashimoto et al. 2016 improve the scores. Again, we see that the translation scores of our model can be further improved by pre-training the model.

Table 5 shows our results on the test data, and the previous best results summarized in Nakazawa et al. 2016a and the WAT website http://lotus.kuee.kyoto-u.ac.jp/WAT/evaluation/list.php?t=1&o=1. are also shown. Our proposed models, LGP-NMT and LGP-NMT+, outperform not only SEQ but also all of the previous best results. Notice also that our implementation of the sequential model (SEQ) provides a very strong baseline, the performance of which is already comparable to the previous state of the art, even without using ensemble techniques. The confidence interval $(p\leq 0.05)$ of the RIBES score of LGP-NMT+ estimated by bootstrap resampling (Noreen 1989) is $(82.27,83.37)$, and thus the RIBES score of LGP-NMT+ is significantly better than that of SEQ, which shows that our latent parser can be effectively pre-trained with the human-annotated treebank.

The sequential NMT model in Cromieres et al. 2016 and the tree-to-sequence NMT model in Eriguchi et al. 2016b rely on ensemble techniques while our results mentioned above are obtained using single models. Moreover, our model is more compact Our training time is within five days on a c4.8xlarge machine of Amazon Web Service by our CPU-based C++ code, while it is reported that the training time is more than two weeks in Cromieres et al. 2016 by their GPU code. than the previous best NMT model in Cromieres et al. 2016. By applying the ensemble technique to LGP-NMT, LGP-NMT+, and SEQ, the BLEU and RIBES scores are further improved, and both of the scores are significantly better than the previous best scores.

Figure 2 shows two translation examples These English sentences were created by manual simplification of sentences in the development data. to see how the proposed model works and what is missing in the state-of-the-art sequential NMT model, SEQ. Besides the reference translation, the outputs of our models with and without pre-training, SEQ, and Google Translation The translations were obtained at https://translate.google.com in Feb. and Mar. 2017. are shown.

In the translation example (1) in Figure 2, we see that the adverb “obliquely” is interpreted differently across the systems. As in the reference translation, “obliquely” is a modifier of the verb “crosses”. Our models correctly capture the relationship between the two words, whereas Google Translation and SEQ treat “obliquely” as a modifier of the verb “existed”. This error is not a surprise since the verb “existed” is located closer to “obliquely” than the verb “crosses”. A possible reason for the correct interpretation by our models is that they can better capture long-distance dependencies and are less susceptible to surface word distances. This is an indication of our models’ ability of capturing domain-specific selectional preference that cannot be captured by purely sequential models. It should be noted that simply using standard treebank-based parsers does not necessarily address this error, because our pre-trained dependency parser interprets that “obliquely” is a modifier of the verb “existed”.

Adverb or Adjective

The translation example (2) in Figure 2 shows another example where the adverb “negatively” is interpreted as an adverb or an adjective. As in the reference translation, “negatively” is a modifier of the verb “controls”. Only LGP-NMT+ correctly captures the adverb-verb relationship, whereas “negatively” is interpreted as the adjective “negative” to modify the noun “ImRNA” in the translation results from Google Translation and LGP-NMT. SEQ interprets “negatively” as both an adverb and an adjective, which leads to the repeated translations. This error suggests that the state-of-the-art NMT models are strongly affected by the word order. By contrast, the pre-training strategy effectively embeds the information about the POS tags and the dependency relations into our model.

2 Analysis on Learned Latent Graphs

We inspected the latent graphs learned by LGP-NMT. Figure 1 shows an example of the learned latent graph obtained for a sentence taken from the development data of the translation task. It has long-range dependencies and cycles as well as ordinary left-to-right dependencies. We have observed that the punctuation mark “.” is often pointed to by other words with large weights. This is primarily because the hidden state corresponding to the mark in each sentence has rich information about the sentence.

To measure the correlation between the latent graphs and human-defined dependencies, we parsed the sentences on the development data of the WSJ corpus and converted the graphs into dependency trees by Eisner’s algorithm (Eisner 1996). For evaluation, we followed Chen and Manning 2014 and measured Unlabeled Attachment Score (UAS). The UAS is 24.52%, which shows that the implicitly-learned latent graphs are partially consistent with the human-defined syntactic structures. Similar trends have been reported by Yogatama et al. 2017 in the case of binary constituency parsing. We checked the most dominant gold dependency labels which were assigned for the dependencies detected by LGP-NMT. The labels whose ratio is more than 3% are nn, amod, prep, pobj, dobj, nsubj, num, det, advmod, and poss. We see that dependencies between words in distant positions, such as subject-verb-object relations, can be captured.

With Pre-Training

We also inspected the pre-trained latent graphs. Figure 3-(a) shows the dependency structure output by the pre-trained latent parser for the same sentence in Figure 1. This is an ordinary dependency tree, and the head selection is almost deterministic; that is, for each word, the largest weight of the head selection is close to 1.0. By contrast, the weight values are more evenly distributed in the case of LGP-NMT as shown in Figure 1. After the overall NMT model training, the latent parser is adapted to the translation task, and Figure 3-(b) shows the adapted latent graph. Again, we can see that the adapted weight values are also distributed and different from the original pre-trained weight values, which suggests that human-defined syntax is not always optimal for the target task.

The UAS of the pre-trained dependency trees is 92.52% The UAS is significantly lower than the reported score in Hashimoto et al. 2017. The reason is described in Section 4.3., and that of the adapted latent graphs is 18.94%. Surprisingly, the resulting UAS (18.94%) is lower than the UAS of our model without pre-training (24.52%). However, in terms of the translation accuracy, our model with pre-training is better than that without pre-training. These results suggest that human-annotated treebanks can provide useful prior knowledge to guide the overall model training by pre-training, but the resulting sentence structures adapted to the target task do not need to highly correlate with the treebanks.

Related Work

While initial studies on NMT treat each sentence as a sequence of words (Bahdanau et al. 2015; Luong et al. 2015; Sutskever et al. 2014), researchers have recently started investigating into the use of syntactic structures in NMT models (Bastings et al. 2017; Chen et al. 2017; Eriguchi et al. 2016a; Eriguchi et al. 2016b; Eriguchi et al. 2017; Li et al. 2017; Sennrich and Haddow 2016; Stahlberg et al. 2016; Yang et al. 2017). In particular, Eriguchi et al. 2016b introduced a tree-to-sequence NMT model by building a tree-structured encoder on top of a standard sequential encoder, which motivated the use of the dependency composition vectors in our proposed model. Prior to the advent of NMT, the syntactic structures had been successfully used in statistical machine translation systems (Neubig and Duh 2014; Yamada and Knight 2001). These syntax-based approaches are pipelined; a syntactic parser is first trained by supervised learning using a treebank such as the WSJ dataset, and then the parser is used to automatically extract syntactic information for machine translation. They rely on the output from the parser, and therefore parsing errors are propagated through the whole systems. By contrast, our model allows the parser to be adapted to the translation task, thereby providing a first step towards addressing ambiguous syntactic and semantic problems, such as domain-specific selectional preference and PP attachments, in a task-oriented fashion.

Our model learns latent graph structures in a source-side language. Eriguchi et al. 2017 have proposed a model which learns to parse and translate by using automatically-parsed data. Thus, it is also an interesting direction to learn latent structures in a target-side language.

As for the learning of latent syntactic structure, there are several studies on learning task-oriented syntactic structures. Yogatama et al. 2017 used a reinforcement learning method on shift-reduce action sequences to learn task-oriented binary constituency trees. They have shown that the learned trees do not necessarily highly correlate with the human-annotated treebanks, which is consistent with our experimental results. Socher et al. 2011 used a recursive autoencoder model to greedily construct a binary constituency tree for each sentence. The autoencoder objective works as a regularization term for sentiment classification tasks. Prior to these deep learning approaches, Wu 1997 presented a method for bilingual parsing. One of the characteristics of our model is directly using the soft connections of the graph edges with the real-valued weights, whereas all of the above-mentioned methods use one best structure for each sentence. Our model is based on dependency structures, and it is a promising future direction to jointly learn dependency and constituency structures in a task-oriented fashion.

Finally, more related to our model, Kim et al. 2017 applied their structured attention networks to a Natural Language Inference (NLI) task for learning dependency-like structures. They showed that pre-training their model by a parsing dataset did not improve accuracy on the NLI task. By contrast, our experiments show that such a parsing dataset can be effectively used to improve translation accuracy by varying the size of the dataset and by avoiding strong overfitting. Moreover, our translation examples show the concrete benefit of learning task-oriented latent graph structures.

Conclusion and Future Work

We have presented an end-to-end NMT model by jointly learning translation and source-side latent graph representations. By pre-training our model using treebank annotations, our model significantly outperforms both a pipelined syntax-based model and a state-of-the-art sequential model. On English-to-Japanese translation, our model outperforms the previous best models by a large margin. In future work, we investigate the effectiveness of our approach in different types of target tasks.

Acknowledgments

We thank the anonymous reviewers and Akiko Eriguchi for their helpful comments and suggestions. We also thank Yuchen Qiao and Kenjiro Taura for their help in speeding up our training code. This work was supported by CREST, JST, and JSPS KAKENHI Grant Number 17J09620.

References