How can syntactic grammars be used to guide the process of neural text generation?
Syntax for Generation Guidance. Different
from the above work, we focus on guiding genera-
tion explicitly following syntactic grammar. Typ-
ically, Aharoni and Goldberg (2017) and Le et al.
(2017) learn the mapping from sequences to lin-
earized constituency trees to improve machine
translation. Eriguchi et al. (2017) proposes a
hybrid decoder with RNNG (Dyer et al., 2016)
to jointly learn parse actions and word predic-
tions. Wu et al. (2017) and Wang et al. (2018)
design a syntactic tree decoder based on LSTM
(Hochreiter and Schmidhuber, 1997), with an ex-
tra rule decoder. Yang et al. (2020b) introduce a
syntax-guided soft target template as extra prompts
in Transformer. Different from their work, our
method leverages Transformer strengths and breaks
down the sequence-to-sequence generation process
into a hierarchically top-down generation guided
by the syntax tree
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
Sequence to Sequence Neural Machine Translation has achieved significant performance in recent years. Yet, there are some existing issues that Neural Machine Translation still does not solve completely. Two of them are translation for long sentences and the “over-translation”. To address these two problems, we propose an approach that utilize more grammatical information such as syntactic dependencies, so that the output can be generated based on more abundant information. In our approach, syntactic dependencies is employed in decoding. In addition, the output of the model is presented not as a simple sequence of tokens but as a linearized tree construction. In order to assess the performance, we construct model based on an attention mechanism encoder-decoder model in which the source language is input to the encoder as a sequence and the decoder generates the target language as a linearized dependency tree structure. Experiments on the Europarl-v7 dataset of French-to-English translation demonstrate that our proposed method improves BLEU scores by 1.57 and 2.40 on datasets consisting of sentences with up to 50 and 80 tokens, respectively. Furthermore, the proposed method also solved the two existing problems, ineffective translation for long sentences and over-translation in Neural Machine Translation.
[{"first":"An","last":"Nguyen Le","middle":[]},{"first":"Ander","last":"Martinez","middle":[]},{"first":"Akifumi","last":"Yoshimoto","middle":[]},{"first":"Yuji","last":"Matsumoto","middle":[]}]
Towards String-To-Tree Neural Machine Translation
We present a simple method to incorporate syntactic information about the target language in a neural machine translation system by translating into linearized, lexicalized constituency trees. An experiment on the WMT16 German-English news translation task resulted in an improved BLEU score when compared to a syntax-agnostic NMT baseline trained on the same dataset. An analysis of the translations from the syntax-aware system shows that it performs more reordering during translation in comparison to the baseline. A small-scale human evaluation also showed an advantage to the syntax-aware system.
[{"first":"Roee","last":"Aharoni","middle":[]},{"first":"Yoav","last":"Goldberg","middle":[]}]
Recurrent Neural Network Grammars
We introduce recurrent neural network grammars, probabilistic models of sentences with explicit phrase structure. We explain efficient inference procedures that allow application to both parsing and language modeling. Experiments show that they provide better parsing in English than any single previously published supervised generative model and better language modeling than state-of-the-art sequential RNNs in English and Chinese.
[{"first":"Chris","last":"Dyer","middle":[]},{"first":"Adhiguna","last":"Kuncoro","middle":[]},{"first":"Miguel","last":"Ballesteros","middle":[]},{"first":"Noah","last":"Smith","middle":["A."]}]
Improving Neural Machine Translation with Soft Template Prediction
Although neural machine translation (NMT) has achieved significant progress in recent years, most previous NMT models only depend on the source text to generate translation. Inspired by the success of template-based and syntax-based approaches in other fields, we propose to use extracted templates from tree structures as soft target templates to guide the translation procedure. In order to learn the syntactic structure of the target sentences, we adopt constituency-based parse tree to generate candidate templates. We incorporate the template information into the encoder-decoder framework to jointly utilize the templates and source text. Experiments show that our model significantly outperforms the baseline models on four benchmarks and demonstrates the effectiveness of soft target templates.
[{"first":"Jian","last":"Yang","middle":[]},{"first":"Shuming","last":"Ma","middle":[]},{"first":"Dongdong","last":"Zhang","middle":[]},{"first":"Zhoujun","last":"Li","middle":[]},{"first":"Ming","last":"Zhou","middle":[]}]
Learning to Parse and Translate Improves Neural Machine Translation
There has been relatively little attention to incorporating linguistic prior to neural machine translation. Much of the previous work was further constrained to considering linguistic prior on the source side. In this paper, we propose a hybrid model, called NMT+RNNG, that learns to parse and translate by combining the recurrent neural network grammar into the attention-based neural machine translation. Our approach encourages the neural machine translation model to incorporate linguistic prior during training, and lets it translate on its own afterward. Extensive experiments with four language pairs show the effectiveness of the proposed NMT+RNNG.
[{"first":"Akiko","last":"Eriguchi","middle":[]},{"first":"Yoshimasa","last":"Tsuruoka","middle":[]},{"first":"Kyunghyun","last":"Cho","middle":[]}]
A Tree-based Decoder for Neural Machine Translation
Recent advances in Neural Machine Translation (NMT) show that adding syntactic information to NMT systems can improve the quality of their translations. Most existing work utilizes some specific types of linguistically-inspired tree structures, like constituency and dependency parse trees. This is often done via a standard RNN decoder that operates on a linearized target tree structure. However, it is an open question of what specific linguistic formalism, if any, is the best structural representation for NMT. In this paper, we (1) propose an NMT model that can naturally generate the topology of an arbitrary tree structure on the target side, and (2) experiment with various target tree structures. Our experiments show the surprising result that our model delivers the best improvements with balanced binary trees constructed without any linguistic knowledge; this model outperforms standard seq2seq models by up to 2.1 BLEU points, and other methods for incorporating target-side syntax by up to 0.7 BLEU.
[{"first":"Xinyi","last":"Wang","middle":[]},{"first":"Hieu","last":"Pham","middle":[]},{"first":"Pengcheng","last":"Yin","middle":[]},{"first":"Graham","last":"Neubig","middle":[]}]
Sequence-to-Dependency Neural Machine Translation
Nowadays a typical Neural Machine Translation (NMT) model generates translations from left to right as a linear sequence, during which latent syntactic structures of the target sentences are not explicitly concerned. Inspired by the success of using syntactic knowledge of target language for improving statistical machine translation, in this paper we propose a novel Sequence-to-Dependency Neural Machine Translation (SD-NMT) method, in which the target word sequence and its corresponding dependency structure are jointly constructed and modeled, and this structure is used as context to facilitate word generations. Experimental results show that the proposed method significantly outperforms state-of-the-art baselines on Chinese-English and Japanese-English translation tasks.
[{"first":"Shuangzhi","last":"Wu","middle":[]},{"first":"Dongdong","last":"Zhang","middle":[]},{"first":"Nan","last":"Yang","middle":[]},{"first":"Mu","last":"Li","middle":[]},{"first":"Ming","last":"Zhou","middle":[]}]
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
Our task is to construct a model which learns input in sequence form and decodes output as a linearized dependency tree. In this work, we propose an approach in which dependency labels are incorporated into the model to represent more grammatical information in the output sequence. As we know, the Sequence to Sequence (Seq2Seq) Learning model Aharoni et al., 2016) is extremely effective on a va- * This author's present affiliation is CyberAgent, Inc., Tokyo, Japan, yoshimoto akifumi xa@cyberagent.co.jp riety of tasks that require a mapping between a sequence to sequence. Therefore, it is used to solve many tasks in natural language processing. The Seq2Seq model consists of an encoder-decoder neural network which encodes a variable-length input sequence into a vector and decodes it into a variable-length output. Since the model uses the information of the source representation and the previously generated words to produce the next-word token, this distributed representation allows the Seq2Seq model to generate appropriate mapping between the input and the output . For specific tasks, Neural Machine Translation (NMT) model, which is based on the Seq2Seq learning, has achieved excellent translation performance in recent years Bahdanau et al., 2015;Luong et al., 2015;Firat et al., 2016). In particular, the NMT model which is built upon an encoder-decoder framework with attention mechanism (Bahdanau et al., 2015) can also pay attention and its decoder knows which part of the input is relevant for the word that is currently being translated. Therefore, it has shown competitive results and outperformed conventional statistical methods (Bentivogli et al., 2016). Despite of these advantages, NMT model still has a couple particular issues to be solved such as dealing with fixed vocabulary, not applicable to small-data, additional phrases, wrong lexical choice errors, long sentence translation, over and under translation, etc. In this paper, we touch upon the following two major problems:
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
• Translation of long sentences • Over-translation Since the decoder of the Seq2Seq model produces the target language word by word simply based on the previous target words and the sourceside representation vector until it reaches the spe-cial end token, it is incapable in capturing longdistance dependencies in history, so ineffective for long sentences translation Toral and Sánchez-Cartagena, 2017). Even with an attention mechanism, the Seq2Seq model just pays attention to the current alignment information between the inputs and the output at the current position but ignores past alignments information. Therefore, it cannot keep track of the attention history when it updates information at each current time step, leading to the over-production (Tu et al., 2016a,c;Mi et al., 2016;Tu et al., 2016b).
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In order to address the above two issues, it is worth considering that using syntactic dependency information and representing the output as a tree structure would be effective. This approach allows the next tokens to be output based on not only the previous tokens but also the syntactic dependencies so far, thereby conditioning them on more abundant information so it has the ability to make smarter predictions. Basically, in this paper, we train the model with an encoder-decoder neural network and using dependencies in which the input of the source language is in sequence form and the output of the target language will be generated in a linearized dependency-based tree structure. That is, instead of predicting only words at each time step, the model trains the network to predict both words and their grammatical dependencies as a dependency tree at each time step. Therefore, it is hoped that the accuracy of output will be improved.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
The major contributions of this work are as follows:
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
1. To utilize the information of both "head" words and syntactic dependencies between them to produce better output.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
2. To settle the problems in the NMT task.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In this paper, we desire to solve two tasks. First is the ineffective translation for long sentences. Second is the over-translation in NMT task.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
Empirically, to assess the performance of the proposed method, we used Conditional Gated Recurrent Unit with Attention mechanism model of Bahdanau (2015) on the French-English portions of the Europarl-v7 dataset. As a result, the BLEU score is improved by 1.57 and 2.40 points for sentences of length up to 50 and 80 tokens, respec-tively. Also, we compare and analyze the results of attention-based Seq2Seq model and the proposed approach.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In our proposed approach, the neural network model is trained to map the target-side output in a linearized dependency tree construction from the source-side input in a sequence. Thus, we call this model Sequence-to-Dependency (Seq2Dep) model. The problem is defined as follows: Given a source sequence X = (x 1 , x 2 , . . . , x N ) of length N, we want the model to encode the input sequence X and decode it to a tree structure with both words and dependency information conditioned on the encoded vector. Therefore, the output will be represented in the form (LY ) = (ly 1 , ly 2 , . . . , ly M ). The conditional probability p(ly|x) is decomposed as:
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
in which (ly 1 , ly 2 , ..., ly M ) are words or dependency labels. Therefore, the hidden state s j at time step j is computed as follows:
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
and the next token ly j , which may be a word or dependency label, will be generated as follows:
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In this paper, dependencies are defined as the dependency labels which are achieved from the Stanford Dependency Parser (Chen and Manning, 2014). The decoder will decode the next output based on relations between governors and dependents in a linearized tree structure. In regards to the order of generating the dependency labels and the words, the decoder will produce these symbols in a manner called Depth-first pre-order traversal.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In this section, we will describe the model stepby-step as follows:
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
Since there is no parallel corpus in which the source-side is represented in sequence and targetside is represented in linearized dependency tree, we have to prepare data for training by doing dependency parsing for the target-side language.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In this paper, we do experiments on a French-English language pair so we use the Stanford Dependency Parser to obtain dependency parsing results for English. The Stanford Dependency Parser produces results in the form of a tree structure in which each word of the sentence is the dependent of exactly one token, either another word in the sentence or the distinguished "ROOT-0" token. The parsing result is represented in the format "abbreviated relation name(governor, depen-dent)" in which a governor is a head word and dependency is a syntactic relation between a governor and a dependent. The governor and the dependent are words in the sentence. This dependency parsing result will be transformed in another step for traversing the tree, which will be described in the next section to create a dependency tree. The dependency tree represents the target language as an ordered tree structure which is necessary for training. The reason we chose the Stanford Dependency Parser for the parsing portion of this method is because it can represent the order of words in sentence. This information of the order is useful to traverse tree in the following step.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In this section, we describe the Tree Transform and Tree Traversal process in which output in a linearized dependency tree form is created from the Stanford Dependency Parsing tree. For example, given a sentence "She ate an apple today .", after obtaining dependency parsing tree from the above dependency parsing phase, we move the rooted "ate" and "apple" headwords to the same layers of their dependents which are directly connected to the headwords. We also concurrently make consideration to their positions in order while shifting headwords. The headwords are shifted in such a manner that the word order of sentence can be preserved, so we can evaluate the translated output afterwards. Next, the tree structure obtained in the fist step will be transformed into another tree structure for the next tree traversal step. Then we traverse this tree in a Depthfirst pre-order traversal, which is the search tree in which tree is traversed from its left subtree to right subtree recursively until current node is empty, to create output with a linearized tree structure to train the model. That is, for each rooted subtree, governors and dependency labels of the sentence are predicted first, and their information will be used to predict the next dependent words. In other words, the model can capture the dependency information between label-word and wordword pairs to predict the next tokens. This means that the model is capable of modeling grammatical dependencies in the output symbols. Also, in Seq2Dep model, we define the Nonterminal "{DEPENDENCY LABEL", and Node-closing "}" tokens. Nonterminal indicates subtree (Dong and Lapata, 2016), which means open subtree to visit its children nodes. Node-closing indicates end-of- if (label's children order is larger than label's parent order) then 10:
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
INSERT label's parent first 11: else 12:
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
INSERT label's children subtree, that means finishing subtree traversal and returning to the upper layer to continue the next subtree traversal. And these defined tokens do not appear in original source and target datasets. Algorithms 1 and 2 show the definition of transformation and tree traversal in more detail respectively. The purpose of using Depth-first pre-order traversal is as follows:
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
1. To keep the words of the target language sequence in order when they are generated. With this generating order, the word order of the sentence is preserved, thus, we do not have to do any post-processing subsequently.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
2. To utilize both information of the words and the dependency labels generated in the previous rooted subtree to predict the tokens of the next rooted subtree.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
Figures 1, 2 and 3 show the Stanford dependency parsing tree, tree structure after the positions of "head" words are shifted and Depth-first pre-order Tree Traversal.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
The proposed (Seq2Dep) model consists of an encoder which is a bidirectional GRU layer as in Bahdanau's model (2015) 1 . The input embeddings of the source sentences are shared by the forward and backward GRU, and the hidden states of the corresponding forward and backward GRU are added to obtain the hidden representation for that time step. The decoder of the model will decode the output as words and dependency labels in a linearized dependency tree structure in 1 https://github.com/nyu-dl/dl4mt-tutorial OUTPUT Node a Depth-first pre-order traversal. Figure 4 shows the decoder which generates both dependency labels and words in the Seq2Dep model. In Figure  4, the previous token and context vector feeding are omitted for simplicity.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In our experiment, the proposed model was trained on the French-English parallel corpus of the Europarl-v7 dataset. We used newstest2011 and newstest2012 of WMT16 as development and test data respectively. To confirm translation for long sentences, the whole test set was used without removing any sentences with a maximum length of 50 or 80. We performed experiment on the following two datasets:
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
• Europarl-v7 dataset consisting of sentences with a maximum length of 50.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
• Europarl-v7 dataset consisting of sentences with a maximum length of 80.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
For preprocessing data, we filtered out sentences which were longer than the above maximum lengths and cleaned the special symbols or characters which were not strings. We also omitted sentences which had multiple sentences in one line. The reason is that the parsing results obtained from the Stanford Dependency Parser in parsing Figure 1: Stanford Dependency Parsing Tree step would contain multi "{ROOT" tokens for sentences which have multiple sentences in one line, while it is necessary to generate the next child nodes starting from just one top {ROOT of a tree. Next, we tokenize and lowercase this dataset and perform dependency parsing. After that, we traverse the tree in a Depth-first pre-order to create the parallel corpus for the training model in which the source language, French is in sequence form, and the target language, English is in a linearized dependency tree structure form. The longer sentences are(particularly sentences with a maximum length of 80 tokens), the more CPU's memory and time cost for this processing data step. In addition, we built a dictionary of the target language (English) that consists of both words and dependency labels. In this dictionary, we define 74 dependency labels based on the current representation of grammatical relations of the Stanford Dependency Parser.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In order to evaluate the performance of the proposed method, we set the same hyperparameters as the attention-based cGRU model in DL4MT-Tutorial and compare the obtained results of both Seq2Seq and Seq2Dep models.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
The recurrent transformation weights for gates and hidden state proposal matrices were initialized as random orthogonal matrices. Weights were optimized using the Adadelta algorithm and were updated with a mini-batch size of 32 sentences. The vocabulary sizes of both source and target languages were set at 30k words, the beam size was set to 5, dropout was not applied and the gradients were clipped at 1.0. Morever, because the generated tokens are not only words but also dependency labels in Seq2Dep model, the maxlen parameter was set up so that dependency labels are not counted, therefore long sentences will not be removed in training.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In the experiments, we trained the following 2 models on 1.65M sentences with a maximum length of 50 and 1.89M sentences with a maximum length of 80 from the Europarl-v7 French-English bitext.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
This model is a Seq2Seq model with attention mechanism as in Firat (2016) that consists of an encoder that encodes the source language input in sequence form and a decoder that decodes target language output in sequence form.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
The proposed method. In this model, the model architecture is the same as the attention-based Seq2Seq model but the input is in sequence form and the output is in linearized dependency tree structure.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In the Seq2Dep model, because the output consists of both words and dependency labels, we evaluated the result with post-processing, which is the process that removes the dependency labels from the translated result. From this section onwards, we will refer to the Seq2Seq and Seq2Dep models with sentences of maximum length 50 and 80 tokens as Seq2Seq-50, Seq2Dep-50, Seq2Seq-80 and Seq2Dep-80. As a result, the BLEU score of Seq2Dep-50 with post-processing was 20.88, which is higher than the BLEU score of 19.31 obtained by the attention-based Seq2Seq-50 model with a gain of up to 1.57 points. Similarly, the BLEU score improved by 2.40 points for datasets with maximum sentence lengths of 80.  Table 1 shows BLEU and METEOR scores and TER error of the attention-based Seq2Seq and Seq2Dep models. Figure 5 shows the relation between BLEU score and the length of sentence. Moreover, when we made a trial to evaluate the translation results without post-processing, the BLEU scores without post-processing were 42.76 and 43.41 for both datasets. From these scores, it is thought that the model can predict not only word-based tokens but also dependency labels well.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In order to verify the ability of the proposed approach to solve the repetition problem of NMT, over-translation, we measured the repetition of words in the translation results of attention-based Seq2Seq and Seq2Dep learnings in this section. The repetition rate is measured by the following formula:
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
in which y i and Y i are the i th hypothesis sentence and i th reference sentence respectively, and r is the number of the repeated words and is computed by:
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
r(X) = len(X) − len(set(X))
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
in which len(X) is the length of the sentence X and len(set(X)) is the number of words that are not repeated in sentence X. For example, given the sentence X="The big fish ate the smaller fish", in this case, set(X)={The, big, fish, ate, smaller}, len(X)=7, len(set(X))=5. Figure 6 shows the comparison of repetition rate in both models in which the horizontal axis is the length of sentences, vertical axis is the repetition rate respectively. In Figure 6, the repetition rate in both Seq2Seq and Seq2Dep learnings decreases as the length of the sentences increases. From Figure 6, we can see that the more tokens the model learns, the more the repetition rate decreases. Also, the repetition rate is reduced in the Seq2Dep model compared to the attention-based Seq2Seq model.  ineni et al., 2002). With regards to the BLEU score without post-processing, we see that the score of the Seq2Dep-80 model is higher than that of the Seq2Dep-50 model. The reason could be: The longer the sentences are, the more syntactic de-pendencies the models require for generating better outputs.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
Also, in terms of the over-translation problem, Figure 6 shows that the repetition rates of the two models decrease gradually with respect to the length of the sentences and the Seq2Dep model has a lower repetition rate. When we checked the translation results, we saw that Node-closing token "}" was almost generated after each subtree. Moreover, we saw that there were some very long sentences which the over-generation of "UNK"s occurred in the translation result of Seq2Seq model while that did not occur in translation results of Seq2Deq model. Our assumption is that after generating subtree, the Seq2Dep model can learn that it should generate the Node-closing token "}" next, instead of a chain of words. In other words, as mentioned in Kuncoro et al.'s work (Kuncoro et al., 2016) in which modeling of composition can achieve better performance, the Seq2Dep model which learns about the syntactic dependencies and tree structure performance is probably able to learn the blocks of the form "Nonterminal word }" like a phrase-structure in sen- Figure 6: Comparison of the repetition rate of the baseline and Seq2Dep models tences, so it is unlikely to generate the same word repeatedly. Therefore, it is possible to prevent the long repeated words in long sentences. Usually, because the block of the form "Nonterminal word }" is seen as a phrase in sentence or a subtree in tree structure, and it is rare for a phrase to occur repeatedly in sentence or for a subtree to repeat in a tree structure, so it is assumed that repetition of the blocks of form "Nonterminal word }" are also rare.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
In this work, we proposed a method in which the Seq2Dep NMT model is trained by utilizing syntactic dependencies to provide the model more abundant information. In other words, Seq2Dep model learns the potential internal relative connections among tokens and their long term syntactic dependencies to predict the next-word tokens. Furthermore, the Seq2Dep model can also generate output as a linearized dependency tree structure in a Depth-first pre-order tree traversal over words and dependencies. The purpose of this work is to alleviate issues of translating long sentences and repetitive translation. We conduct experiments on the French-English parallel corpus of the Europarl-v7 dataset to compare the performance of the proposed method with the attention-based Seq2Seq model. The results demonstrated that the proposed model achieved a 1.57 and 2.40 points BLEU score improvement for sentences of length at most 50 and 80 tokens re-spectively. Moreover, experiments verify that the proposed model also reduces the over-translation, particularly long sentences with over-generation of "UNK"s.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
• Confirm how accurate the Seq2Dep model generates the dependency labels and the whole tree structure as well.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
• In this paper, to compare performance of the proposed method with the baseline model, we set the same hyperparameters as the attention-based cGRU model in dl4mttutorial and trained the Seq2Dep model on only Europarl-v7 dataset. Since experiments were done on small vocabulary size and dataset, we plan to train the model on larger vocabulary and datasets with subword units segmentation.
Improving Sequence to Sequence Neural Machine Translation by Utilizing Syntactic Dependency Information
• For future work, we plan to train models on datasets which consist of only long sentences with more than 50 or 80 tokens to compare the performance of long-sentences translation of the approach and baseline model.
Towards String-To-Tree Neural Machine Translation
Neural Machine Translation (NMT) (Kalchbrenner and Blunsom, 2013;Sutskever et al., 2014;Bahdanau et al., 2014) has recently became the state-of-the-art approach to machine translation (Bojar et al., 2016), while being much simpler than the previously dominant phrase-based statistical machine translation (SMT) approaches (Koehn, 2010). NMT models usually do not make explicit use of syntactic information about the languages at hand. However, a large body of work was dedicated to syntax-based SMT (Williams et al., 2016). One prominent approach to syntaxbased SMT is string-to-tree (S2T) translation Knight, 2001, 2002), in which a sourcelanguage string is translated into a target-language tree. S2T approaches to SMT help to ensure the resulting translations have valid syntactic structure, while also mediating flexible reordering between the source and target languages. The main formalism driving current S2T SMT systems is GHKM rules (Galley et al., 2004(Galley et al., , 2006, which are synchronous transduction grammar (STSG) fragments, extracted from word-aligned sentence pairs with syntactic trees on one side. The GHKM translation rules allow flexible reordering on all levels of the parse-tree.
Towards String-To-Tree Neural Machine Translation
We suggest that NMT can also benefit from the incorporation of syntactic knowledge, and propose a simple method of performing string-to-tree neural machine translation. Our method is inspired by recent works in syntactic parsing, which model trees as sequences Choe and Charniak, 2016). Namely, we translate a source sentence into a linearized, lexicalized constituency tree, as demonstrated in Figure 2. Figure  1 shows a translation from our neural S2T model compared to one from a vanilla NMT model for the same source sentence, as well as the attentioninduced word alignments of the two models. Figure 1: Top -a lexicalized tree translation predicted by the bpe2tree model. Bottom -a translation for the same sentence from the bpe2bpe model. The blue lines are drawn according to the attention weights predicted by each model.
Towards String-To-Tree Neural Machine Translation
Note that the linearized trees we predict are different in their structure from those in  as instead of having part of speech tags as terminals, they contain the words of the translated sentence. We intentionally omit the POS information as including it would result in significantly Jane hatte eine Katze . → ( ROOT ( S ( N P Jane ) N P ( V P had ( N P a cat ) N P ) V P . ) S ) ROOT Figure 2: An example of a translation from a string to a linearized, lexicalized constituency tree. longer sequences. The S2T model is trained on parallel corpora in which the target sentences are automatically parsed. Since this modeling keeps the form of a sequence-to-sequence learning task, we can employ the conventional attention-based sequence to sequence paradigm (Bahdanau et al., 2014) as-is, while enriching the output with syntactic information. Related Work Some recent works did propose to incorporate syntactic or other linguistic knowledge into NMT systems, although mainly on the source side: Eriguchi et al. (2016a,b) replace the encoder in an attention-based model with a Tree-LSTM (Tai et al., 2015) over a constituency parse tree; Bastings et al. (2017) encoded sentences using graph-convolutional networks over dependency trees; Sennrich and Haddow (2016) proposed a factored NMT approach, where each source word embedding is concatenated to embeddings of linguistic features of the word; Luong et al. (2015) incorporated syntactic knowledge via multi-task sequence to sequence learning: their system included a single encoder with multiple decoders, one of which attempts to predict the parse-tree of the source sentence; Stahlberg et al. (2016) proposed a hybrid approach in which translations are scored by combining scores from an NMT system with scores from a Hiero (Chiang, 2005(Chiang, , 2007 system. Shi et al. (2016) explored the syntactic knowledge encoded by an NMT encoder, showing the encoded vector can be used to predict syntactic information like constituency trees, voice and tense with high accuracy.
Towards String-To-Tree Neural Machine Translation
In parallel and highly related to our work, Eriguchi et al. (2017) proposed to model the target syntax in NMT in the form of dependency trees by using an RNNG-based decoder (Dyer et al., 2016), while Nadejde et al. (2017) incorporated target syntax by predicting CCG tags serialized into the target translation. Our work differs from those by modeling syntax using constituency trees, as was previously common in the "traditional" syntax-based machine translation literature.
Towards String-To-Tree Neural Machine Translation
Experimental Setup We first experiment in a resource-rich setting by using the German-English portion of the WMT16 news translation task (Bojar et al., 2016), with 4.5 million sentence pairs. We then experiment in a low-resource scenario using the German, Russian and Czech to English training data from the News Commentary v8 corpus, following Eriguchi et al. (2017). In all cases we parse the English sentences into constituency trees using the BLLIP parser (Charniak and Johnson, 2005). 1 To enable an open vocabulary translation we used sub-word units obtained via BPE (Sennrich et al., 2016b) on both source and target. 2 In each experiment we train two models. A baseline model (bpe2bpe), trained to translate from the source language sentences to English sentences without any syntactic annotation, and a string-to-linearized-tree model (bpe2tree), trained to translate into English linearized constituency trees as shown in Figure 2. Words are segmented into sub-word units using the BPE model we learn on the raw parallel data. We use the NEMATUS (Sennrich et al., 2017) 3 implementation of an attention-based NMT model. 4 We trained the models until there was no improvement on the development set in 10 consecutive checkpoints. Note that the only difference between the baseline and the bpe2tree model is the syntactic information, as they have a nearly-identical amount of model parameters (the only additional parameters to the syntax-aware system are the embeddings for the brackets of the trees).
Towards String-To-Tree Neural Machine Translation
For all models we report results of the best performing single model on the dev-set (new-stest2013+newstest2014 in the resource rich setting, newstest2015 in the rest, as measured by BLEU) when translating newstest2015 and new-stest2016, similarly to Sennrich et al. (2016a); Eriguchi et al. (2017). To evaluate the stringto-tree translations we derive the surface form by removing the symbols that stand for nonterminals in the tree, followed by merging the subwords. We also report the results of an ensemble of the last 5 checkpoints saved during each model training. We compute BLEU scores using the mteval-v13a.pl script from the Moses toolkit (Koehn et al., 2007 Results As shown in Table 1, for the resourcerich setting, the single models (bpe2bpe, bpe2tree) perform similarly in terms of BLEU on new-stest2015. On newstest2016 we witness an advantage to the bpe2tree model. A similar trend is found when evaluating the model ensembles: while they improve results for both models, we again see an advantage to the bpe2tree model on newstest2016. Table 2 shows the results in the low-resource setting, where the bpe2tree model is consistently better than the bpe2bpe baseline. We find this interesting as the syntax-aware system performs a much harder task (predicting trees on top of the translations, thus handling much longer output sequences) while having a nearly-identical amount of model parameters. In order to better understand where or how the syntactic information improves translation quality, we perform a closer analysis of the WMT16 experiment.
Towards String-To-Tree Neural Machine Translation
The Resulting Trees Our model produced valid trees for 5970 out of 6003 sentences in the development set. While we did not perform an in-depth error-analysis, the trees seem to follow the syntax of English, and most choices seem reasonable.
Towards String-To-Tree Neural Machine Translation
Quantifying Reordering English and German differ in word order, requiring a significant amount of reordering to generate a fluent translation. A major benefit of S2T models in SMT is facilitating reordering. Does this also hold for our neural S2T model? We compare the amount of reordering in the bpe2bpe and bpe2tree models using a distortion score based on the alignments derived from the attention weights of the corresponding systems. We first convert the attention weights to hard alignments by taking for each target word the source word with highest attention weight. For an n-word target sentence t and source sentence s let a(i) be the position of the source word aligned to the target word in position  i. We define:
Towards String-To-Tree Neural Machine Translation
For example, for the translations in Figure 1, the above score for the bpe2tree model is 2.73, while the score for the bpe2bpe model is 1.27 as the bpe2tree model did more reordering. Note that for the bpe2tree model we compute the score only on tokens which correspond to terminals (words or sub-words) in the tree. We compute this score for each source-target pair on newstest2015 for each model. Figure 3 shows a histogram of the binned score counts. The bpe2tree model has more translations with distortion scores in bins 1onward and significantly less translations in the least-reordering bin (0) when compared to the bpe2bpe model, indicating that the syntactic information encouraged the model to perform more reordering. 5 Figure 4 tracks the distortion scores throughout the learning process, plotting the average dev-set scores for the model checkpoints saved every 30k updates. Interestingly, both models obey to the following trend: open with a relatively high distortion score, followed by a steep decrease, and from there ascend gradually. The bpe2tree model usually has a higher distortion score during training, as we would expect after our previous findings from Figure 3.
Towards String-To-Tree Neural Machine Translation
Tying Reordering and Syntax The bpe2tree model generates translations with their constituency tree and their attention-derived alignments. We can use this information to extract GHKM rules (Galley et al., 2004). 6 We derive (90) x1 x2 x0 (65) x0 x1 x2 (31) x1 x2 x0 ",/." (13) x0 x1 x2 ",/." (7) x1 "der" x2 x0 VP(x0:TER x1:PP) (113) x1 x0 (82) x0 x1 (38) x1 x0 ",/." (18) x0 x1 ",/." (5) ",/." x0 x1 S(x0:NP VP(x1:TER x2:NP)) (69) x0 x1 x2 (51) x0 x2 x1 (35) x0 x1 x2 ",/." (20) x0 x2 x1 ",/." (6) "die" x0 x1 x2 VP(x0:TER x1:NP x2:PP) (52) x0 x1 x2 (38) x1 x2 x0 (20) x1 x2 x0 ",/." (11) x0 x1 x2 ",/." (9) x2 x1 x0 VP(x0:TER x1:NP PP(x2:TER x3:NP)) (40) x0 x1 x2 x3 (32) x1 x2 x3 x0 (18) x1 x2 x3 x0 ",/." (8) x0 x1 x2 x3 ",/." (5) x2 x3 x1 x0 VP(x0:TER NP(x1:NP x2:PP)) (61) x0 x1 x2 (38) x1 x2 x0 (19) x0 x1 x2 ",/." (8) x0 "eine" x1 x2 (8) x1 x2 x0 ",/." NP(x0:NP PP(x1:TER x2:NP)) (728) x0 x1 x2 (110) "die" x0 x1 x2 (107) x0 x1 x2 ",/." (56) x0 x1 "der" x2 (54) "der" x0 x1 x2 S(VP(x0:TER x1:NP)) (41) x1 x0 (26) x0 x1 (14) x1 x0 ",/." (7) "die" x1 x0 (5) x0 x1 ",/." VP(x0:TER x1:VP) (73) x0 x1 (38) x1 x0 (25) x0 x1 ",/." (15) x1 x0 ",/." (9) ",/." x0 x1  Table 4: Translation examples from newstest2015. The underlines correspond to the source word attended by the first opening bracket (these are consistently the main verbs or structural markers) and the target words this source word was most strongly aligned to. See the supplementary material for an attention weight matrix example when predicting a tree ( Figure 6) and additional output examples. hard alignments for that purpose by treating every source/target token-pair with attention score above 0.5 as an alignment. Extracting rules from the dev-set predictions resulted in 233,657 rules, where 22,914 of them (9.8%) included reordering, i.e. contained variables ordered differently in the source and the target. We grouped the rules by their LHS (corresponding to a target syntactic structure), and sorted them by the total number of RHS (corresponding to a source sequential structure) with reordering. Table 3 shows the top 10 extracted LHS, together with the top-5 RHS, for each rule. The most common rule, VP(x 0 :TER x 1 :NP) → x 1 x 0 , found in 184 sentences in the dev set (8.4%), is indicating that the sequence x 1 x 0 in German was reordered to form a verb phrase in English, in which x 0 is a terminal and x 1 is a noun phrase. The extracted GHKM rules reveal very sensible German-English reordering patterns.
Towards String-To-Tree Neural Machine Translation
Relative Constructions Browsing the produced trees hints at a tendency of the syntax-aware model to favor using relative-clause structures and subordination over other syntactic constructions (i.e., "several cameras that are all priced..." vs. "several cameras, all priced..."). To quantify this, we count the English relative pronouns (who, which, that 7 , whom, whose) found in the newstest2015 translations of each model and in the reference translations, as shown in Figure  5. The bpe2tree model produces more relative constructions compared to the bpe2bpe model, and both models produce more such constructions than found in the reference.
Towards String-To-Tree Neural Machine Translation
Main Verbs While not discussed until this point, the generated opening and closing brackets also have attention weights, providing another opportunity to to peak into the model's behavior. Figure 6 in the supplementary material presents an example of a complete attention matrix, including the syntactic brackets. While making full sense of the attention patterns of the syntactic elements remains a challenge, one clear trend is that opening the very first bracket of the sentence consistently attends to the main verb or to structural markers (i.e. question marks, hyphens) in the source sentence, suggesting a planning-ahead behavior of the decoder. The underlines in Table 4 correspond to the source word attended by the first opening bracket, and the target word this source word was most strongly aligned to. In general, we find the alignments from the syntax-based system more sensible (i.e. in Figure 1 -the bpe2bpe alignments are off-by-1).
Towards String-To-Tree Neural Machine Translation
The bpe2tree translations read better than their bpe2bpe counterparts, both syntactically and semantically, and we highlight some examples which demonstrate this. Table 4 lists some representative examples, highlighting improvements that correspond to syntactic phenomena involving reordering or global structure. We also performed a small-scale human-evaluation using mechanical turk on the first 500 sentences in the dev-set. Further details are available in the supplementary material. The results are summarized in the following 
Towards String-To-Tree Neural Machine Translation
We present a simple string-to-tree neural translation model, and show it produces results which are better than those of a neural string-to-string model. While this work shows syntactic information about the target side can be beneficial for NMT, this paper only scratches the surface with what can be done on the subject. First, better models can be proposed to alleviate the long sequence problem in the linearized approach or allow a more natural tree decoding scheme (Alvarez-Melis and Jaakkola, 2017). Comparing our approach to other syntax aware NMT models like Eriguchi et al. (2017) and Nadejde et al. (2017) may also be of interest. A Contrastive evaluation (Sennrich, 2016) of a syntax-aware system vs. a syntax-agnostic system may also shed light on the benefits of incorporating syntax into NMT.
Towards String-To-Tree Neural Machine Translation
Data The English side of the corpus was tokenized (into Penn treebank format) and truecased using the scripts provided in Moses (Koehn et al., 2007). We ran the BPE process on a concatenation of the source and target corpus, with 89500 BPE operations in the WMT experiment and with 45k operations in the other experiments. This resulted in an input vocabulary of 84924 tokens and an output vocabulary of 78499 tokens in the WMT16 experiment. The linearized constituency trees are obtained by simply replacing the POS tags in the parse trees with the corresponding word or subwords. The output vocabulary in the bpe2tree models includes the target subwords and the tree symbols which correspond to an opening or closing of a specific phrase type.
Towards String-To-Tree Neural Machine Translation
Hyperparameters The word embedding size was set to 500/256 and the encoder and decoder sizes were set to 1024/256 (WMT16/other experiments). For optimization we used Adadelta (Zeiler, 2012) with minibatch size of 40. For decoding we used beam search with a beam size of 12. We trained the bpe2tree WMT16 model on sequences with a maximum length of 150 tokens (the average length for a linearized tree in the training set was about 50 tokens). It was trained for two weeks on a single Nvidia TitanX GPU. The bpe2bpe WMT16 model was trained on sequences with a maximum length of 50 tokens, and with minibatch size of 80. It was trained for one week on a single Nvidia TitanX GPU. Only in the low-resource experiments we applied dropout as described in Sennrich et al. (2016a) for Romanian-English.
Towards String-To-Tree Neural Machine Translation
We performed humanevaluation on the Mechnical Turk platform. Each sentence was evaluated using two annotators. For each sentence, we presented the annotators with the English reference sentence, followed by the outputs of the two systems. The German source was not shown, and the two system's outputs were shown in random order. The annotators were instructed to answer "Which of the two sentences, in your view, is a better portrayal of the the reference sentence." They were then given 6 options: "sent 1 is better", "sent 2 is better", "sent 1 is a little better", "sent 2 is a little better", "both sentences are equally good", "both sentences are equally bad". We then ignore differences between "better" and "a little better". We count as "strongly better" the cases where both annotators indicated the same sentence as better, as "weakly better" the cases were one annotator chose a sentence and the other indicated they are both good/bad. Other cases are treated as either "both good" / "both bad" or as disagreements. Figure 6: The attention weights for the string-totree translation in Figure 1 Additional Output Examples from both models, in the format of Figure 1. Notice the improved translation and alignment quality in the tree-based translations, as well as the overall high structural quality of the resulting trees. The few syntactic mistakes in these examples are attachment errors of SBAR and PP phrases, which will also challenge dedicated parsers.
Recurrent Neural Network Grammars
Sequential recurrent neural networks (RNNs) are remarkably effective models of natural language. In the last few years, language model results that substantially improve over long-established state-ofthe-art baselines have been obtained using RNNs (Zaremba et al., 2015;Mikolov et al., 2010) as well as in various conditional language modeling tasks such as machine translation (Bahdanau et al., 2015), image caption generation (Xu et al., 2015), and dialogue generation (Wen et al., 2015). Despite these impressive results, sequential models are a priori inappropriate models of natural language, since relationships among words are largely organized in terms of latent nested structures rather than sequential surface order (Chomsky, 1957).
Recurrent Neural Network Grammars
In this paper, we introduce recurrent neural network grammars (RNNGs; §2), a new generative probabilistic model of sentences that explicitly models nested, hierarchical relationships among words and phrases. RNNGs operate via a recursive syntactic process reminiscent of probabilistic context-free grammar generation, but decisions are parameterized using RNNs that condition on the entire syntactic derivation history, greatly relaxing context-free independence assumptions.
Recurrent Neural Network Grammars
The foundation of this work is a top-down variant of transition-based parsing ( §3). We give two variants of the algorithm, one for parsing (given an observed sentence, transform it into a tree), and one for generation. While several transition-based neural models of syntactic generation exist (Henderson, 2003(Henderson, , 2004Emami and Jelinek, 2005;Titov and Henderson, 2007;Buys and Blunsom, 2015b), these have relied on structure building operations based on parsing actions in shift-reduce and leftcorner parsers which operate in a largely bottomup fashion. While this construction is appealing because inference is relatively straightforward, it limits the use of top-down grammar information, which is helpful for generation (Roark, 2001). 1 RNNGs maintain the algorithmic convenience of transitionbased parsing but incorporate top-down (i.e., rootto-terminal) syntactic information ( §4).
Recurrent Neural Network Grammars
The top-down transition set that RNNGs are based on lends itself to discriminative modeling as well, where sequences of transitions are modeled conditional on the full input sentence along with the incrementally constructed syntactic structures. Similar to previously published discriminative bottomup transition-based parsers (Henderson, 2004;Sagae and Lavie, 2005;Zhang and Clark, 2011, inter alia), greedy prediction with our model yields a lineartime deterministic parser (provided an upper bound on the number of actions taken between processing subsequent terminal symbols is imposed); however, our algorithm generates arbitrary tree structures directly, without the binarization required by shift-reduce parsers. The discriminative model also lets us use ancestor sampling to obtain samples of parse trees for sentences, and this is used to solve a second practical challenge with RNNGs: approximating the marginal likelihood and MAP tree of a sentence under the generative model. We present a simple importance sampling algorithm which uses samples from the discriminative parser to solve inference problems in the generative model ( §5).
Recurrent Neural Network Grammars
Experiments show that RNNGs are effective for both language modeling and parsing ( §6). Our generative model obtains (i) the best-known parsing results using a single supervised generative model and (ii) better perplexities in language modeling than state-of-the-art sequential LSTM language models. Surprisingly-although in line with previous parsing results showing the effectiveness of generative models (Henderson, 2004;Johnson, 2001)parsing with the generative model obtains significantly better results than parsing with the discriminative model.
Recurrent Neural Network Grammars
Formally, an RNNG is a triple (N, Σ, Θ) consisting of a finite set of nonterminal symbols (N ), a finite set of terminal symbols (Σ) such that N ∩ Σ = ∅, and a collection of neural network parameters Θ. It does not explicitly define rules since these are implicitly characterized by Θ. The algorithm that the grammar uses to generate trees and strings in the language is characterized in terms of a transition-based algorithm, which is outlined in the next section. In the section after that, the semantics of the parameters that are used to turn this into a stochastic algorithm that generates pairs of trees and strings are discussed.
Recurrent Neural Network Grammars
RNNGs are based on a top-down generation algorithm that relies on a stack data structure of partially completed syntactic constituents. To emphasize the similarity of our algorithm to more familiar bottom-up shift-reduce recognition algorithms, we first present the parsing (rather than generation) version of our algorithm ( §3.1) and then present modifications to turn it into a generator ( §3.2).
Recurrent Neural Network Grammars
The parsing algorithm transforms a sequence of words x into a parse tree y using two data structures (a stack and an input buffer). As with the bottomup algorithm of Sagae and Lavie (2005), our algorithm begins with the stack (S) empty and the complete sequence of words in the input buffer (B). The buffer contains unprocessed terminal symbols, and the stack contains terminal symbols, "open" nonterminal symbols, and completed constituents. At each timestep, one of the following three classes of operations ( Fig. 1) is selected by a classifier, based on the current contents on the stack and buffer:
Recurrent Neural Network Grammars
• NT(X) introduces an "open nonterminal" X onto the top of the stack. Open nonterminals are written as a nonterminal symbol preceded by an open parenthesis, e.g., "(VP", and they represent a nonterminal whose child nodes have not yet been fully constructed. Open nonterminals are "closed" to form complete constituents by subsequent REDUCE operations. • SHIFT removes the terminal symbol x from the front of the input buffer, and pushes it onto the top of the stack. • REDUCE repeatedly pops completed subtrees or terminal symbols from the stack until an open nonterminal is encountered, and then this open NT is popped and used as the label of a new constituent that has the popped subtrees as its children. This new completed constituent is pushed onto the stack as a single composite item. A single REDUCE operation can thus create constituents with an unbounded number of children.
Recurrent Neural Network Grammars
The parsing algorithm terminates when there is a single completed constituent on the stack and the buffer is empty. Fig. 2 shows an example parse using our transition set. Note that in this paper we do not model preterminal symbols (i.e., part-ofspeech tags) and our examples therefore do not include them. 2 Our transition set is closely related to the operations used in Earley's algorithm which likewise introduces nonterminals symbols with its PREDICT operation and later COMPLETEs them after consuming terminal symbols one at a time using SCAN (Earley, 1970). It is likewise closely related to the "linearized" parse trees proposed by  and to the top-down, left-to-right decompositions of trees used in previous generative parsing and language modeling work (Roark, 2001(Roark, , 2004Charniak, 2010).
Recurrent Neural Network Grammars
A further connection is to LL( * ) parsing which uses an unbounded lookahead (compactly represented by a DFA) to distinguish between parse alternatives in a top-down parser (Parr and Fisher, 2011); however, our parser uses an RNN encoding of the lookahead rather than a DFA.
Recurrent Neural Network Grammars
Constraints on parser transitions. To guarantee that only well-formed phrase-structure trees are produced by the parser, we impose the following constraints on the transitions that can be applied at each step which are a function of the parser state (B, S, n) where n is the number of open nonterminals on the stack:
Recurrent Neural Network Grammars
• The NT(X) operation can only be applied if B is not empty and n < 100. 3 • The SHIFT operation can only be applied if B is not empty and n ≥ 1. To designate the set of valid parser transitions, we write A D (B, S, n).
Recurrent Neural Network Grammars
The parsing algorithm that maps from sequences of words to parse trees can be adapted with minor changes to produce an algorithm that stochastically generates trees and terminal symbols. Two changes are required: (i) there is no input buffer of unprocessed words, rather there is an output buffer (T ), and (ii) instead of a SHIFT operation there are GEN(x) operations which generate terminal symbol x ∈ Σ and add it to the top of the stack and the output buffer. At each timestep an action is stochastically selected according to a conditional distribution that depends on the current contents of B and T . The algorithm terminates when a single completed constituent remains on the stack. Fig. 4 shows an example generation sequence.
Recurrent Neural Network Grammars
Constraints on generator transitions. The generation algorithm also requires slightly modified constraints. These are:
Recurrent Neural Network Grammars
• The GEN(x) operation can only be applied if n ≥ 1.
Recurrent Neural Network Grammars
• The REDUCE operation can only be applied if the top of the stack is not an open nonterminal symbol and n ≥ 1.
Recurrent Neural Network Grammars
To designate the set of valid generator transitions, we write A G (T, S, n). This transition set generates trees using nearly the same structure building actions and stack configurations as the "top-down PDA" construction proposed by Abney et al. (1999), albeit without the restriction that the trees be in Chomsky normal form.
Recurrent Neural Network Grammars
Any parse tree can be converted to a sequence of transitions via a depth-first, left-to-right traversal of a parse tree. Since there is a unique depth-first, leftro-right traversal of a tree, there is exactly one transition sequence of each tree. For a tree y and a sequence of symbols x, we write a(x, y) to indicate the corresponding sequence of generation transitions, and b(x, y) to indicate the parser transitions.
Recurrent Neural Network Grammars
A detailed analysis of the algorithmic properties of our top-down parser is beyond the scope of this paper; however, we briefly state several facts. Assuming the availability of constant time push and pop operations, the runtime is linear in the number of the nodes in the parse tree that is generated by the parser/generator (intuitively, this is true since although an individual REDUCE operation may require  is a terminal symbol, X is a nonterminal symbol, and each τ is a completed subtree. The top of the stack is to the right, and the buffer is consumed from left to right. Elements on the stack and buffer are delimited by a vertical bar ( | ).
Recurrent Neural Network Grammars
Input: The hungry cat meows .
Recurrent Neural Network Grammars
Buffer Action   Stack t Terms t Open NTs t Action Stack t+1 Terms t+1 Open NTs t+1 S T n   applying a number of pops that is linear in the number of input symbols, the total number of pop operations across an entire parse/generation run will also be linear). Since there is no way to bound the number of output nodes in a parse tree as a function of the number of input words, stating the runtime complexity of the parsing algorithm as a function of the input size requires further assumptions. Assuming our fixed constraint on maximum depth, it is linear.
Recurrent Neural Network Grammars
Our generation algorithm algorithm differs from previous stack-based parsing/generation algorithms in two ways. First, it constructs rooted tree structures top down (rather than bottom up), and second, the transition operators are capable of directly generating arbitrary tree structures rather than, e.g., assuming binarized trees, as is the case in much prior work that has used transition-based algorithms to produce phrase-structure trees (Sagae and Lavie, 2005;Zhang and Clark, 2011;Zhu et al., 2013).
Recurrent Neural Network Grammars
RNNGs use the generator transition set just presented to define a joint distribution on syntax trees (y) and words (x). This distribution is defined as a sequence model over generator transitions that is parameterized using a continuous space embedding of the algorithm state at each time step (u t ); i.e.,
Recurrent Neural Network Grammars
and where action-specific embeddings r a and bias vector b are parameters in Θ.
Recurrent Neural Network Grammars
The representation of the algorithm state at time t, u t , is computed by combining the representation of the generator's three data structures: the output buffer (T t ), represented by an embedding o t , the stack (S t ), represented by an embedding s t , and the history of actions (a <t ) taken by the generator, represented by an embedding h t ,
Recurrent Neural Network Grammars
where W and c are parameters. Refer to Figure 5 for an illustration of the architecture.
Recurrent Neural Network Grammars
The output buffer, stack, and history are sequences that grow unboundedly, and to obtain representations of them we use recurrent neural networks to "encode" their contents (Cho et al., 2014). Since the output buffer and history of actions are only appended to and only contain symbols from a finite alphabet, it is straightforward to apply a standard RNN encoding architecture. The stack (S) is more complicated for two reasons. First, the elements of the stack are more complicated objects than symbols from a discrete alphabet: open nonterminals, terminals, and full trees, are all present on the stack. Second, it is manipulated using both push and pop operations. To efficiently obtain representations of S under push and pop operations, we use stack LSTMs (Dyer et al., 2015).
Recurrent Neural Network Grammars
When a REDUCE operation is executed, the parser pops a sequence of completed subtrees and/or tokens (together with their vector embeddings) from the stack and makes them children of the most recent open nonterminal on the stack, "completing" the constituent. To compute an embedding of this new subtree, we use a composition function based on bidirectional LSTMs, which is illustrated in Fig. 6.
Recurrent Neural Network Grammars
The first vector read by the LSTM in both the forward and reverse directions is an embedding of the label on the constituent being constructed (in the figure, NP). This is followed by the embeddings of the child subtrees (or tokens) in forward or reverse order. Intuitively, this order serves to "notify" each LSTM what sort of head it should be looking for as it processes the child node embeddings. The final state of the forward and reverse LSTMs are concatenated, passed through an affine transformation and a tanh nonlinearity to become the subtree embedding. 4 Because each of the child node embeddings (u, v, w in internal node), this composition function is a kind of recursive neural network.
Recurrent Neural Network Grammars
To reduce the size of A G (S, T, n), word generation is broken into two parts. First, the decision to generate is made (by predicting GEN as an action), and then choosing the word, conditional on the current parser state. To further reduce the computational complexity of modeling the generation of a word, we use a class-factored softmax (Baltescu and Blunsom, 2015;Goodman, 2001). By using |Σ| classes for a vocabulary of size |Σ|, this prediction step runs in time O( |Σ|) rather than the O(|Σ|) of the full-vocabulary softmax. To obtain clusters, we use the greedy agglomerative clustering algorithm of Brown et al. (1992).
Recurrent Neural Network Grammars
The parameters in the model are learned to maximize the likelihood of a corpus of trees.
Recurrent Neural Network Grammars
A discriminative parsing model can be obtained by replacing the embedding of T t at each time step with an embedding of the input buffer B t . To train this model, the conditional likelihood of each sequence of actions given the input string is maximized. 5
Recurrent Neural Network Grammars
Our generative model p(x, y) defines a joint distribution on trees (y) and sequences of words (x). To evaluate this as a language model, it is necessary to compute the marginal probability p(x) = y ∈Y(x) p(x, y ). And, to evaluate the model as a parser, we need to be able to find the MAP parse tree, i.e., the tree y ∈ Y(x) that maximizes p(x, y). However, because of the unbounded dependencies across the sequence of parsing actions in our model, exactly solving either of these inference problems is intractable. To obtain estimates of these, we use a variant of importance sampling (Doucet and Johansen, 2011).
Recurrent Neural Network Grammars
Our importance sampling algorithm uses a conditional proposal distribution q(y | x) with the following properties: (i) p(x, y) > 0 =⇒ q(y | x) > 0; (ii) samples y ∼ q(y | x) can be obtained efficiently; and (iii) the conditional probabilities q(y | x) of these samples are known. While many such distributions are available, the discrim-inatively trained variant of our parser ( §4.4) fulfills these requirements: sequences of actions can be sampled using a simple ancestral sampling approach, and, since parse trees and action sequences exist in a one-to-one relationship, the product of the action probabilities is the conditional probability of the parse tree under q. We therefore use our discriminative parser as our proposal distribution.
Recurrent Neural Network Grammars
Importance sampling uses importance weights, which we define as w(x, y) = p(x, y)/q(y | x), to compute this estimate. Under this definition, we can derive the estimator as follows:
Recurrent Neural Network Grammars
We now replace this expectation with its Monte Carlo estimate as follows, using N samples from q:
Recurrent Neural Network Grammars
To obtain an estimate of the MAP treeŷ, we choose the sampled tree with the highest probability under the joint model p(x, y).
Recurrent Neural Network Grammars
We present results of our two models both on parsing (discriminative and generative) and as a language model (generative only) in English and Chinese.
Recurrent Neural Network Grammars
Data. For English, §2-21 of the Penn Treebank are used as training corpus for both, with §24 held out as validation, and §23 used for evaluation. Singleton words in the training corpus with unknown word classes using the the Berkeley parser's mapping rules. 6 Orthographic case distinctions are preserved, and numbers (beyond singletons) are not normalized. For Chinese, we use the Penn Chinese Treebank Version 5.1 (CTB) (Xue et al., 2005). 7 For 6 http://github.com/slavpetrov/ berkeleyparser 7 §001-270 and 440-1151 for training, §301-325 development data, and §271-300 for evaluation.
Recurrent Neural Network Grammars
the Chinese experiments, we use a single unknown word class. Corpus statistics are given in Table 1. 8 Model and training parameters. For the discriminative model, we used hidden dimensions of 128 and 2-layer LSTMs (larger numbers of dimensions reduced validation set performance). For the generative model, we used 256 dimensions and 2layer LSTMs. For both models, we tuned the dropout rate to maximize validation set likelihood, obtaining optimal rates of 0.2 (discriminative) and 0.3 (generative). For the sequential LSTM baseline for the language model, we also found an optimal dropout rate of 0.3. For training we used stochastic gradient descent with a learning rate of 0.1. All parameters were initialized according to recommendations given by Glorot and Bengio (2010).
Recurrent Neural Network Grammars
English parsing results. Table 2 (last two rows) gives the performance of our parser on Section 23, as well as the performance of several representative models. For the discriminative model, we used a greedy decoding rule as opposed to beam search in some shift-reduce baselines. For the generative model, we obtained 100 independent samples from a flattened distribution of the discriminative parser (by exponentiating each probability by α = 0.8 and renormalizing) and reranked them according to the generative model. 9
Recurrent Neural Network Grammars
Chinese parsing results. Chinese parsing results were obtained with the same methodology as in English and show the same pattern (Table 6).
Recurrent Neural Network Grammars
Language model results. We report held-out perword perplexities of three language models, both sequential and syntactic. Log probabilities are normalized by the number of words (excluding the stop  
Recurrent Neural Network Grammars
It is clear from our experiments that the proposed generative model is quite effective both as a parser and as a language model. This is the result of (i) relaxing conventional independence assumptions (e.g., context-freeness) and (ii) inferring continuous representations of symbols alongside non-linear models of their syntactic relationships. The most significant question that remains is why the discriminative model-which has more information available to it than the generative model-performs worse than the generative model. This pattern has been observed before in neural parsing by Henderson (2004), who hypothesized that larger, unstructured conditioning contexts are harder to learn from, and provide opportunities to overfit. Our discriminative model conditions on the entire history, stack, and buffer, while our generative model only accesses the history and stack. The fully discriminative model of  was able to obtain results similar to those of our generative model (albeit using much larger training sets obtained through semisupervision) but similar results to those of our discriminative parser using the same data. In light of their results, we believe Henderson's hypothesis is correct, and that generative models should be considered as a more statistically efficient method for learning neural networks from small data.
Recurrent Neural Network Grammars
RNNGs can be combined with a particle filter inference scheme (rather than the importance sampling method based on a discriminative parser, §5) to produce a left-to-right marginalization algorithm that runs in expected linear time. Thus, they could be used in applications that require language models.
Recurrent Neural Network Grammars
A second possibility is to replace the sequential generation architectures found in many neural network transduction problems that produce sentences conditioned on some input. Previous work in machine translation has showed that conditional syntactic models can function quite well without the computationally expensive marginalization process at decoding time (Galley et al., 2006;Gimpel and Smith, 2014).
Recurrent Neural Network Grammars
A third consideration regarding how RNNGs, human sentence processing takes place in a left-toright, incremental order. While an RNNG is not a processing model (it is a grammar), the fact that it is left-to-right opens up several possibilities for developing new sentence processing models based on an explicit grammars, similar to the processing model of Charniak (2010).
Recurrent Neural Network Grammars
Finally, although we considered only the supervised learning scenario, RNNGs are joint models that could be trained without trees, for example, using expectation maximization.
Recurrent Neural Network Grammars
We introduced recurrent neural network grammars, a probabilistic model of phrase-structure trees that can be trained generatively and used as a language model or a parser, and a corresponding discriminative model that can be used as a parser. Apart from out-of-vocabulary preprocessing, the approach requires no feature design or transformations to treebank data. The generative model outperforms every previously published parser built on a single supervised generative model in English, and a bit behind the best-reported generative model in Chinese. As language models, RNNGs outperform the best single-sentence language models.
Improving Neural Machine Translation with Soft Template Prediction
Recently, neural machine translation (NMT) (Wu et al., 2016;Gehring et al., 2017;Vaswani et al., 2017;Chen et al., 2018) has achieved significant progress. Some advanced models (Chatterjee et al., 2016;Niehues et al., 2016;Junczys-Dowmunt and Grundkiewicz, 2017;Geng et al., 2018;Zhou et al., 2019a) predict the ultimate translation by multi-pass generation conditioned on the previous text such as CMLMs (Ghazvininejad et al., 2019), ABD-NMT (Zhang et al., 2018), SynST (Akoury et al., 2019), and Deliberation Network (Xia et al., 2017).
Improving Neural Machine Translation with Soft Template Prediction
Inspired by these works and the successful application of templates for other intriguing tasks, including semantic parsing (Dong and Lapata, 2018), summarization (Cao et al., 2018;Wang et al., 2019a), question answering (Duan et al., 2017;† Corresponding author.  Pandey et al., 2018), and other text generation tasks (Wiseman et al., 2018;Guu et al., 2018), we assume the candidate templates of the target sentences can guide the sentence translation process. We denote these templates extracted from the constituencybased parse tree as soft templates, which consist of tags and target words. The templates are soft because no explicit paradigms are inaugurated to build new translation from them, and the target tokens could be modified. In order to effectively use the templates, we introduce soft template-based neural machine translation (ST-NMT), which can use source text and soft templates to predict the final translation. Our approach can be split into two phases. In the first phase, a standard Transformer model is trained to predict soft target templates by using source text and templates extracted from the constituencybased parse tree. Secondly, we use two encoders, including a soft target template encoder and a source language encoder to encode source text and templates and generate the final translation. As shown in Figure 1, given the source text "我喜欢 打篮球" and the target template "S like to VP", the final translation "I like to play basketball" is generated by two encoders. In this work, the templates play a part in guiding, and some target tokens in  Figure 2: Overview of our ST-NMT. Given the source text and the soft target template predicted by the P θ X→Y , the source language Transformer encoder and target template Transformer encoder maps two sequences X = (x 1 , x 2 , x 3 , x 4 , x 5 ) and T = (t 1 , y 2 , t 3 , t 4 , t 5 ) into hidden states Z X and Z T . x i denotes the source word, t i denotes the template tag and y i denotes the target word. y i also denotes the target word but it can be modified to the other target words. The ultimate translation Y is generated by a Transformer decoder which incorporates the context Z X and Z Y in the second phase.
Improving Neural Machine Translation with Soft Template Prediction
the template could also be modified. In order to prove the effectiveness of our approach, we conduct main experiments on the popular benchmarks, including IWSLT14 German-English translation task, WMT14 English-German translation task, LDC Chinese-English translation task, and ASPEC Japanese-Chinese translation task. Experiments show that our approach achieves significant improvement compared to the baselines, which demonstrates the soft target templates can provide a positive influence for guiding translation procedure effectively. Our approach can be used for diverse scale data sets, different styles, and multiple language pairs.
Improving Neural Machine Translation with Soft Template Prediction
Our model first reads the source language sequence X = (x 1 , x 2 , x 3 , . . . , x n ) in the conventional way by a source language Transformer encoder and generates the template sequence T = (t 1 , t 2 , t 3 , . . . , t m ) by a template Transformer decoder. As shown in Figure 2, our model uses a source language Transformer encoder and a template Transformer encoder, which encodes the source language sequence X and the template sequence T separately. We deploy the target language decoder to generate the final translation. In this section, we present the details of the proposed template-based approach. Our method mainly in-cludes two phases: (1) The training data is constructed by the constituency-based parse tree. Then, we adopt a standard Transformer to convert the source text to the soft target template for the next generation.
Improving Neural Machine Translation with Soft Template Prediction
(2) Based on the source text and the predicted soft target template, we utilize two encoders to encode two sequences into hidden states separately and a target language decoder to generate the ultimate translation.
Improving Neural Machine Translation with Soft Template Prediction
In this procedure, we model the P θ X→T (T |X) to predict soft target templates on top of the constructed training data D X,T . To construct D X,T , we use a constituency-based parser to parse the target sequence and get a tree structure. Then, we prune nodes which are deeper than the specific depth and recover the left leaf nodes to the ordered template sequence. Through these operations, we gain the parallel training data D X,T and train a standard Transformer model P θ X→T (T |X) to predict the soft target template.
Improving Neural Machine Translation with Soft Template Prediction
The constituency-based parse tree could reveal the structure information of the whole sentence which utilizes the constituency grammar to distinguish terminal and non-terminal nodes. More specifically, the interior nodes are labeled by nonterminal categories which belong to the set of nonterminal tokens S, while the leaf nodes are labeled Pruned Figure 3: The constituency-based parse tree of the example sentence. Given the target sentence and definite depth of the tree, we gain the sub-tree by pruning the nodes deeper than 4 in this case. Then, the sub-tree can be converted to the soft target template "There are NP VP" from left to right. by terminal categories V . S = {S, VP, NP, . . . , ASBR} and V is the vocabulary set of the target language. For example, the sentence "There are some people running" could be expressed as Figure 3. In this case, the non-terminal tokens consist of S 0 = {S, NP, VP, EX, VBP, NP, DT, NNS, VBG} and the terminal tokens are composed of V 0 = {There, are some, people, running}. Our template T = {t 1 , t 2 , t 3 , t 4 } is the ordered sequence which is composed of non-terminal tokens and terminal tokens. In this case, t 1 =There, t 2 =are, t 3 =VP and t 4 =NP. Our template extraction aims to extract the sub-tree of the specific depth and use these nonterminal and terminal tokens locating at the leaf node of sub-tree.
Improving Neural Machine Translation with Soft Template Prediction
In order to predict the soft target templates, we train a standard Transformer model given the training data of the source text and extracted templates. The Transformer model reads the source text and predicts the soft target templates using beam search. Then, we select the top-K results of the beam search as templates.
Improving Neural Machine Translation with Soft Template Prediction
The depth of the tree is a trade-off. In Figure 3, One special case is that when the depth equals 1, the template only has one symbol "S". The template "S" cannot provide any useful information. Another special case is that when depth is greater than 6, the template "There are some people running" only has terminal tokens. The template only contains target words, which cannot provide any additional information. When the depth equals 4, the template is "There are NP VP". The template contains sentence syntactic and structural information, which is suitable for our method.
Improving Neural Machine Translation with Soft Template Prediction
With the Transformer model P θ X→T (T |X), we need to construct the pseudo training data D X,T,Y instead of directly using extracted templates by soft template prediction. Given the source text X, we use P θ X→T (T |X) to predict the top-1 soft target template T with beam search. Therefore, we get the triple training data
Improving Neural Machine Translation with Soft Template Prediction
which is prepared for the next phase.
Improving Neural Machine Translation with Soft Template Prediction
The triple training data D X,T,Y is used to model the probability P (X,T )→Y from the two sequences to the ultimate translation. Our approach could generate the target sentence Y , given the source sequence X and template T .
Improving Neural Machine Translation with Soft Template Prediction
Formulation In formula, we could model the whole procedure on top of the P θ X→T (T |X) and
Improving Neural Machine Translation with Soft Template Prediction
where θ X→T and θ (X,T )→Y are the parameters for the first and the second phase. The source language Transformer encoder and the soft template Transformer encoder maps the input sequence X and the template T composed of target language words and tags to the hidden states. Then, a Transformer decoder interacting with two encoders generates the final translation Y , described by the Equation 1.
Improving Neural Machine Translation with Soft Template Prediction
Encoder In the second phase, our template Transformer encoder and the source language Transformer encoder are stacked by blocks which contain self-attention layers with residual connections, layer normalization and fully connected feedforward network (FFN). Therefore, the hidden states of the source language Transformer encoder and the template Transformer encoder are calculated by:
Improving Neural Machine Translation with Soft Template Prediction
where h l = h X l for the source language Transformer encoder and h l = h T l for the template Transformer encoder. N is the number of layers and l ∈ [1, N ].
Improving Neural Machine Translation with Soft Template Prediction
Decoder Based on the hidden states h X l and h T l , the target language Transformer decoder use the encoder-decoder multi-head attention to jointly use the source language and template information to generate the ultimate translation Y . Besides, the target sequence decoder uses multi-head attention to obtain the representations of target language decoder with the parameters
Improving Neural Machine Translation with Soft Template Prediction
. . , z T n ) using the source language Transformer encoder and the template Transformer encoder.
Improving Neural Machine Translation with Soft Template Prediction
On top of the Z X and Z T , the decoder separately calculate the multi-head attention with source sentence context X = (x 1 , . . . , x m ) and target template sentence T = (t 1 , . . . , t n ), then our model obtain two hidden states Z X,Y and Z T,Y by attention with source context and template context. Here, We incorporate the Z X,Y containing source language information and Z X,Y including template information in a reasonable way:
Improving Neural Machine Translation with Soft Template Prediction
where β is the parameter to control the degree of incorporation between source text and template. In order to effectively incorporate source and template information, we calculate the parameter β as below:
Improving Neural Machine Translation with Soft Template Prediction
where Z Y is the decoder hidden state and W Y and U T are parameter matrices. σ is the sigmoid activation function.
Improving Neural Machine Translation with Soft Template Prediction
Similar to the conventional NMT, in order to make the model predict the target sequence, we use maximum likelihood estimation (MLE) loss function to update the model parameter by maximizing the log likelihood of translation over training set D.
Improving Neural Machine Translation with Soft Template Prediction
When we train the P θ X→Y without the template Transformer encoder, we only need to optimize the following loss function:
Improving Neural Machine Translation with Soft Template Prediction
where θ X→Y are the parameters of the source language Transformer encoder and the target language Transformer decoder. When we train the P θ (X,T )→Y with the template Transformer encoder, the loss function could be calculated by:
Improving Neural Machine Translation with Soft Template Prediction
where θ (X,T )→Y are the parameters of the source language Transformer encoder, template language Transformer encoder and target language Transformer decoder.
Improving Neural Machine Translation with Soft Template Prediction
To balance the two objectives, our model is trained on L θ X→Y (D) objective for the α% iterations, and trained on L θ (X,T )→Y (D) objective for the (1 − α)% interations. Therefore, this procedure is equivalent to the following formula:
Improving Neural Machine Translation with Soft Template Prediction
where α is a scaling factor accounting for the difference in magnitude between L θ X→Y (D) and L θ (X,T )→Y (D).
Improving Neural Machine Translation with Soft Template Prediction
In practice, we find optimizing these two objectives can make training procedure easier and get a higher BLEU score since there exist a few low-quality templates to influence the translation quality. Through optimizing two objectives simultaneously, we can reduce the effect of some lowquality templates and improve the stability of our model.
Improving Neural Machine Translation with Soft Template Prediction
We conducted experiments on four benchmarks, including LDC Chinese-English, WMT14 English-German, IWSLT14 German-English, and ASPEC Japanese-Chinese translation tasks. By conducting experiments on these four benchmarks, these settings prove that our approach is suitable for diverse situations: (1) These four benchmarks provide a wide coverage of both scale and genres. They vary from small scale to large scale (2) We use the different domains, which include news, science, and talk domain. (3) We also conduct the experiments on different language pairs, including the German-English translation task, the English-German translation task, the Chinese-English translation task, and the Japanese-Chinese translation task.
Improving Neural Machine Translation with Soft Template Prediction
In order to verify the effectiveness of our method, we conduct experiments on four benchmarks. WMT14 and LDC datasets are from the news domain. IWSLT14 dataset is from TED talk. ASPEC dataset is from a scientific paper excerpt corpus.
Improving Neural Machine Translation with Soft Template Prediction
LDC Chinese-English We use a subset from LDC corpus 1 which has nearly 1.4M sentences originally. The training set is selected from the LDC corpus that consists of 1.2M sentence pairs after dropping the low-quality sentence pairs of which the length is more than 2. We used the NIST 2006 dataset as the validation set for evaluating performance in the training procedure, and NIST 2003NIST , 2005NIST , 2008 and 2012 as test sets, which all have 4 English references for each Chinese sentence.
Improving Neural Machine Translation with Soft Template Prediction
IWSLT14 German-English This dataset contains 16K training sequence pairs. We randomly sample 5% of the training data as valid test. Besides, we merge the multiple testsets dev2010, dev2012, tst2010, tst2011, tst2012 for testing.
Improving Neural Machine Translation with Soft Template Prediction
WMT14 English-German The training data consists of 4.5M sentence pairs. The validation set is devtest2014, and the test set is newstest2014.
Improving Neural Machine Translation with Soft Template Prediction
ASPEC Japanese-Chinese We use 0.67M sentence pairs from ASPEC Japanese-Chinese corpus (Nakazawa et al., 2016) 2 . We use the devtest as the development data, which contains 2090 sentences, and the test data contains 2107 sentences with a single reference per source sentence.
Improving Neural Machine Translation with Soft Template Prediction
LDC Chinese-English The base Transformer model is used for this task, which includes 6 layers, each layer of which has the hidden dimensions of 512, feedforward dimensions of 2048 , and 8 attention heads. We use Moses (Koehn et al., 2007) to tokenize English sentences and our in-house tool to tokenize Chinese sentences. We use Byte Pair Encoding (BPE) (Sennrich et al., 2016) to encode 1 LDC2002E17, LDC2002E18, LDC2003E07, LDC2003E14, LDC2005E83, LDC2005T06, LDC2005T10, LDC2006E17, LDC2006E26, LDC2006E34, LDC2006E85, LDC2006E92, LDC2006T06, LDC2004T08, LDC2005T10 2 http://orchid.kuee.kyoto-u.ac.jp/ASPEC/ sentences using a shared vocabulary of 40K symbols.
Improving Neural Machine Translation with Soft Template Prediction
We adopt the small setup of the Transformer model. The model has 6 layers with the embedding size of 512, a feedforward size of 1024, and 4 attention heads. In order to prevent overfitting, we use a dropout of 0.3, a l 2 weight decay of 10 −4 , and a label smoothing of 0.1. We use BPE to encode sentences with a shared vocabulary of 10K symbols.
Improving Neural Machine Translation with Soft Template Prediction
WMT14 English-German We use the big setting of Transformer (Vaswani et al., 2017), in which both the encoder and the decoder have 6 layers, with the embedding size of 1024, feedforward size of 4096, and 16 attention heads. The dropout rate is fixed as 0.3. We adopt Adam (Kingma and Ba, 2015) optimizer with a learning rate 0.1 of the similar learning rate schedule as Transformer (Vaswani et al., 2017). We set the batch size as 6000 and the update frequency as 16 on 8 GPUs for updating parameters (Ott et al., 2018) to imitate 128 GPUs. The datasets are encoded by BPE with a shared vocabulary (Sennrich et al., 2016) of 40K symbols.
Improving Neural Machine Translation with Soft Template Prediction
ASPEC Japanese-Chinese We use the base setting of Transformer the same to the Chinese-English translation task. Following the similar learning rate schedule (Vaswani et al., 2017), we set the learning rate as 0.1. Chinese and Japanese sentences are tokenized with our in-house tools and encoded by BPE with a shared vocabulary of 10K symbols.
Improving Neural Machine Translation with Soft Template Prediction
We evaluate the performance of the translation results. The evaluation metric is BLEU (Papineni et al., 2002). For the Chinese-English and German-English translation tasks, we use case-insensitive tokenized BLEU scores. For the English-German translation task, we use case-sensitive tokenized BLEU scores for evaluation. All the experiments last for 150 epochs and use Stanford parser to generate templates (Manning et al., 2014). For all translation tasks, we use the checkpoint, which has the best valid performance on the valid set. For different test sets, we adapt the beam size and the length penalty to get better performance. In order to avoid the difference of the tokenizer for Chinese translation result evaluation, we adopt the character-level BLEU for testing. Checkpoint averaging is not used, except notification. 
Improving Neural Machine Translation with Soft Template Prediction
We compare our approach with two types of baselines including one-pass baselines and multi-pass baselines.
Improving Neural Machine Translation with Soft Template Prediction
One-pass Baselines: ConvS2S (Gehring et al., 2017) is a strong CNN-based baseline. We report the results referring to the paper of convolutional sequence to sequence model (ConvS2S).
Improving Neural Machine Translation with Soft Template Prediction
RNN-based NMT model. GNMT (Wu et al., 2016) is the typical encoder-decoder framework. We use the similar setting 3 for all experiments. Transformer (Vaswani et al., 2017) is a strong baseline which has the state-of-the-art performance. We reimplement this baseline 4 . LightConv and Dy-namicConv (Wu et al., 2019) are simpler but effective baselines. We directly report the results in the paper.
Improving Neural Machine Translation with Soft Template Prediction
Multi-pass Baselines: Deliberation network (Xia et al., 2017) and SoftPrototype (Wang et al., 2019b) generates and polishes the raw text by a two-pass manner. SB-NMT (Zhou et al., 2019a) is a synchronous bidirectional neural machine translation which predicts its outputs using two direction simultaneously. ABD-NMT (Zhang et al., 2018) is an encoder-decoder NMT framework with the forward and backward decoder. By considering the agreement of both directions left-to-right (L2R) and right-to-left (R2L), Rerank-NMT    Chen et al., 2018) 34.51 ConvS2S (Gehring et al., 2017) 30.41 LightConv (Wu et al., 2019) 34.80 DynamicConv (Wu et al., 2019) 35.20 Rerank-NMT  34.82
Improving Neural Machine Translation with Soft Template Prediction
Transformer (our implementation) 34.43 ST-NMT (our proposed) 35.24 by inserting method.
Improving Neural Machine Translation with Soft Template Prediction
For the IWSLT14 German-English machine translation task, we present the results of the ST-NMT and other strong baselines in Table 2. We compare our method with other various methods, including GNMT, RNMT+, convS2S, LightConv, Dy-namicConv, and the Transformer model with the small setting. The Rerank-NMT model gets 34.82 BLEU by using the two-pass results, including leftto-right (L2R) and right-to-left (R2L), and selects the best candidates. As shown in  (Wu et al., 2016) 24.61 ConvS2S (Gehring et al., 2017) 25.16 Transformer (Vaswani et al., 2017) 28.40 RNMT+ (Chen et al., 2018) 28.49 Rerank-NMT  27.81 ABD-NMT  28.22 Deliberation Network (Xia et al., 2017) 29.11 SoftPrototype (Wang et al., 2019b) 29.46 SB-NMT (Zhou et al., 2019a) 29.21 SBSG (Zhou et al., 2019b) 27.45 Insertion Transformer (Stern et al., 2019) 27.41 Transformer (our implementation) 29.25 ST-NMT (our proposed) 29.68 Table 3: BLEU-4 scores (%) on WMT14 En→De task.
Improving Neural Machine Translation with Soft Template Prediction
The result of our model is statistically significant compared to the other baselines (p < 0.05).
Improving Neural Machine Translation with Soft Template Prediction
GNMT (Wu et al., 2016) 49.12 ConvS2S (Gehring et al., 2017) 50.32
Improving Neural Machine Translation with Soft Template Prediction
Transformer (our implementation) 52.02 ST-NMT (our proposed) 52.84 Table 4: Character-level BLEU-4 scores (%) on AS-PEC Ja→Zh task. The result of our model is statistically significant compared to the other baselines (p < 0.01).
Improving Neural Machine Translation with Soft Template Prediction
baselines and outperforms the Transformer baseline by 1.14 BLEU point on average, which shows that the template could effectively improve the performance. More specifically, our model outperforms the Transformer model by 0.76 BLEU on NIST2003, 1.52 BLEU on NIST 2005, 0.91 BLEU on NIST 2008, and 1.39 BLEU on NIST 2012. We further demonstrate the effectiveness of our model on WMT14 English-German translation tasks, and we also compare our model with other competitive models, including ABD-NMT (Zhang et al., 2018), Deliberation Network (Xia et al., 2017), SoftPrototype (Wang et al., 2019b), SB-NMT (Zhou et al., 2019a) and SBSG (Zhou et al., 2019b). As shown in Table 3, our model also significantly outperforms others and gets an improvement of 0.43 BLEU points than a strong Transformer model.
Improving Neural Machine Translation with Soft Template Prediction
To investigate the effect of our approach on the different language pairs, we also evaluate  Figure 4: The effect of the multiple templates. We feed the the top-K results of the beam search as multiple templates and source sentence to generate the target translation.
Improving Neural Machine Translation with Soft Template Prediction
our model on the Japanese-Chinese translation task. According to Table 4, ST-NMT outperforms GNMT by 3.72 BLEU points, ConvS2S by 2.52 BLEU points, and the Transformer model by 0.82 BLEU points, which demonstrates that the soft template extracted by constituency-based parse tree can also bring strong positive effects.
Improving Neural Machine Translation with Soft Template Prediction
Because of the diversity of the templates, we investigate the performance with the different numbers of the templates. On top of the original parallel training data D = {(x (i) , y (i) )} N i=1 , we construct the training data from the source text to the soft target template D X→T = {(x (i) , t (i) )} N i=1 , by the model P θ X→T . Through this construction procedure, we could use the top-K results of the beam search as multiple templates by model P θ X→T . We could expand the training data of the source text to the target template as Figure 4, our model gains the best performance only using the single template. When the number of templates is 8, our model gains the worst BLEU score of 29.22. We can summarize that our model can be more robust but maybe get worse performance with the number of templates rising. Besides, in order to further improve the stability of our model, we expand the dataset by selecting random templates for the source sentence. The different templates confuse our model, although it can make our model more robust. 
Improving Neural Machine Translation with Soft Template Prediction
To further control how much our model leverages templates for translation, we tune the hyperparameter α. With the value rising, the contribution of template information gradually decreases. We study the influence of the ratio α. To investigate the effect of this hyperparameter, we set the discrete value α = {10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, 90%, 100%}. According to Figure 5, when the α switches from 0.4 to 0.9, our model can get the better performance which is greater than or equal to 29.3 BLEU. The results show that we can set the hyper-parameter α in a reasonable interval (0.4 ≤ α ≤ 0.9) to keep the balance between source text and template.
Improving Neural Machine Translation with Soft Template Prediction
Considering that the template derived from the specific depth can lead to the divergent performance, our model is examined with the different depth. The effect of the template extraction which is described as Section 3 is decided by the sub-tree which is controlled by the depth of sub-tree. For the same constituency-based parse tree, the different sub-tree can be obtained based on the different chosen depth d. When we get the sub-tree, the template could be derived from it. The depth of the constituency-based parse tree is decided by a simple but effective strategy as formula:
Improving Neural Machine Translation with Soft Template Prediction
where L is the length of the input sentence, γ 1 is the lower bound, γ 2 is the upper bound depth   of the sub-tree and λ is the ratio of the length of source sentence. When the λ approximates 1.0, the template contains more target tokens and less tags.
Improving Neural Machine Translation with Soft Template Prediction
In addition, we tune the depth on the LDC training data and list the results. According to the Table  5, the soft templates of the specific depth provide helpful information to the translation procedure when the λ = 0.15 in the LDC dataset.
Improving Neural Machine Translation with Soft Template Prediction
To measure contribution of the predicted soft target template for final translation, we calculate the overlapping words between the template and the translation. Table 6 gives the specific overlapping words ratio on the different test sets including NIST2003, NIST2005, NIST2008 and NIST2012. The overlapping ratio is calculated by the following formula:
Improving Neural Machine Translation with Soft Template Prediction
where Count y (·) and Count t (·) denote the number of w in the target translation Y and the template T , and w is the words in the target language. The overlapping ratio represents the correlation between the predicted template T and the target translation Y . According to Table 6, the correlation between the template T and the translation Y is highly relevant which demonstrates the contribution of our template to the final translation.
Improving Neural Machine Translation with Soft Template Prediction
Reference on the other hand , if we overreact , we will be deceived by their trick .
Improving Neural Machine Translation with Soft Template Prediction
Template on the other hand , if NP VP , we will VP .
Improving Neural Machine Translation with Soft Template Prediction
Ours on the other hand , if we react too much , we will be hit by them . 
Improving Neural Machine Translation with Soft Template Prediction
To further illustrate which aspects of NMT are improved by the target soft template, we provide a Chinese-English translation example shown in 7.
Improving Neural Machine Translation with Soft Template Prediction
Templates provide the structural and grammatical information of the target sentence. For instance, Chinese source sentence "另一方面 , 如果 我们 反应 过度 , 将 会 被 他们 欺骗 ", our model first predicts the target template "on the other hand , if NP VP , we will VP ", and then generate the final translation "on the other hand , if we react too much, we will be hit by them". Our target template provides the sentence pattern "If sb. do sth, sb. will be done". Our method introduces the constituency-based parse tree and utilizes the constituency grammar to distinguish terminal and non-terminal nodes. Therefore, our model can automatically learn sentence patterns, including grammatical and structural information.
Improving Neural Machine Translation with Soft Template Prediction
In this work, we propose a novel approach that utilizes source text and additional soft templates. More specifically, our approach can extract the templates from the sub-tree, which derives from the specific depth of the constituency-based parse tree. Then, we use a Transformer model to predict the soft target templates conditioned on the source text. On top of soft templates and source text, we incorporate the template information to guide the translation procedure. We compare our soft-template neural machine translation (ST-NMT) with other baselines on four benchmarks and multiple language pairs. Experimental results show that our ST-NMT significantly improves performance on these datasets.
Learning to Parse and Translate Improves Neural Machine Translation
Neural Machine Translation (NMT) has enjoyed impressive success without relying on much, if any, prior linguistic knowledge. Some of the most recent studies have for instance demonstrated that NMT systems work comparably to other systems even when the source and target sentences are given simply as flat sequences of characters (Lee et al., 2016;Chung et al., 2016) or statistically, not linguistically, motivated subword units Wu et al., 2016). Shi et al. (2016) recently made an observation that the encoder of NMT captures syntactic properties of a source sentence automatically, indirectly suggesting that explicit linguistic prior may not be necessary.
Learning to Parse and Translate Improves Neural Machine Translation
On the other hand, there have only been a couple of recent studies showing the potential benefit of explicitly encoding the linguistic prior into NMT.  for instance proposed to augment each source word with its corresponding part-of-speech tag, lemmatized form and dependency label. Eriguchi et al. (2016) instead replaced the sequential encoder with a tree-based encoder which computes the representation of the source sentence following its parse tree. Stahlberg et al. (2016) let the lattice from a hierarchical phrase-based system guide the decoding process of neural machine translation, which results in two separate models rather than a single end-to-end one. Despite the promising improvements, these explicit approaches are limited in that the trained translation model strictly requires the availability of external tools during inference time.
Learning to Parse and Translate Improves Neural Machine Translation
We instead propose to implicitly incorporate linguistic prior based on the idea of multi-task learning (Caruana, 1998;Collobert et al., 2011). More specifically, we design a hybrid decoder for NMT, called NMT+RG, that combines a usual conditional language model and a recently proposed recurrent neural network grammars (RNNGs, Dyer et al., 2016). This is done by plugging in the conventional language model decoder in the place of the buffer in RNNG, while sharing a subset of parameters, such as word vectors, between the language model and RNNG. We train this hybrid model to maximize both the log-probability of a target sentence and the log-probability of a parse action sequence. We use an external parser (Andor et al., 2016) to generate target parse actions, but unlike the previous explicit approaches, we do not need it during test time.
Learning to Parse and Translate Improves Neural Machine Translation
We evaluate the proposed NMT+RG on four language pairs ({Cs, De, Ru, Jp}-En). We observe significant improvements in terms of BLEU scores on three out of four language pairs and RIBES scores on all the language pairs.
Learning to Parse and Translate Improves Neural Machine Translation
Neural machine translation is a recently proposed framework for building a machine translation sys-tem based purely on neural networks. It is often built as an attention-based encoder-decoder network (Cho et al., 2015) with two recurrent networks-encoder and decoder-and an attention model. The encoder, which is often implemented as a bidirectional recurrent network with long short-term memory units (LSTM, Hochreiter and Schmidhuber, 1997) or gated recurrent units (GRU, Cho et al., 2014), first reads a source sentence represented as a sequence of words x = (x 1 , x 2 , . . . , x N ). The encoder returns a sequence of hidden states h = (h 1 , h 2 , . . . , h N ). Each hidden state h i is a concatenation of those from the forward and backward recurrent network:
Learning to Parse and Translate Improves Neural Machine Translation
The decoder is implemented as a conditional recurrent language model which models the target sentence, or translation, as
Learning to Parse and Translate Improves Neural Machine Translation
where y = (y 1 , . . . , y M ). Each of the conditional probabilities in the r.h.s is computed by
Learning to Parse and Translate Improves Neural Machine Translation
where f dec is a recurrent activation function, such as LSTM or GRU, and W y is the output word vector of the word y. c j is a time-dependent context vector that is computed by the attention model using the sequence h of hidden states from the encoder. The attention model first compares the current hidden state s j against each of the hidden states and assigns a scalar score: ong et al., 2015). These scores are then normalized across the hidden states to sum to 1, that is
Learning to Parse and Translate Improves Neural Machine Translation
The time-dependent context vector is then a weighted-sum of the hidden states with these attention weights: c j = i α i,j h i .
Learning to Parse and Translate Improves Neural Machine Translation
A recurrent neural network grammar (RNNG, Dyer et al., 2016) is a probabilistic syntax-based language model. Unlike a usual recurrent language model (see, e.g., Mikolov et al., 2010), an RNNG simultaneously models both tokens and their tree-based composition. This is done by having a (output) buffer, stack and action history, each of which is implemented as a stack LSTM (sLSTM, Dyer et al., 2015). At each time step, the action sLSTM predicts the next action based on the (current) hidden states of the buffer, stack and action sLSTM. That is,
Learning to Parse and Translate Improves Neural Machine Translation
where W a is the vector of the action a. If the selected action is shift, the word at the beginning of the buffer is moved to the stack. When the reduce action is selected, the top-two words in the stack are reduced to build a partial tree. Additionally, the action may be one of many possible non-terminal symbols, in which case the predicted non-terminal symbol is pushed to the stack.
Learning to Parse and Translate Improves Neural Machine Translation
The hidden states of the buffer, stack and action sLSTM are correspondingly updated by
Learning to Parse and Translate Improves Neural Machine Translation
where V y and V a are functions returning the target word and action vectors. The input vector r t of the stack sLSTM is computed recursively by
Learning to Parse and Translate Improves Neural Machine Translation
where r d and r p are the corresponding vectors of the parent and dependent phrases, respectively (Dyer et al., 2015). This process is iteratively done until the complete parse tree is built. When the complete sentence is provided, the buffer simply summarizes the shifted words. When the RNNG is used as a generator, the buffer further generates the next word when the selected action is shift. The latter can be done by replacing the buffer with a recurrent language model, which is the idea on which our proposal is based.
Learning to Parse and Translate Improves Neural Machine Translation
Our main proposal in this paper is to hybridize the decoder of the neural machine translation and the RNNG. We continue from the earlier observation that we can replace the buffer of RNNG to a recurrent language model that simultaneously summarizes the shifted words as well as generates future words. We replace the RNNG's buffer with the neural translation model's decoder in two steps.
Learning to Parse and Translate Improves Neural Machine Translation
Construction First, we replace the hidden state of the buffer h buffer (in Eq. (5)) with the hidden state of the decoder of the attention-based neural machine translation from Eq. (3). As is clear from those two equations, both the buffer sLSTM and the translation decoder take as input the previous hidden state (h buffer top and s j−1 , respectively) and the previously decoded word (or the previously shifted word in the case of the RNNG's buffer), and returns its summary state. The only difference is that the translation decoder additionally considers the states j−1 . Second, we let the next word prediction of the translation decoder as a generator of RNNG. In other words, the generator of RNNG will output a word, when asked by the shift action, according to the conditional distribution defined by the translation decoder in Eq. (1). Once the buffer sLSTM is replaced with the neural translation decoder, the action sLSTM naturally takes as input the translation decoder's hidden state when computing the action conditional distribution in Eq. (4). We call this hybrid model NMT+RG.
Learning to Parse and Translate Improves Neural Machine Translation
Learning and Inference After this integration, our hybrid NMT+RG models the conditional distribution over all possible pairs of translation and its parse given a source sentence, i.e., p(y, a|x). Assuming the availability of parse annotation in the target-side of a parallel corpus, we train the whole model jointly to maximize E (x,y,a)∼data [log p(y, a|x)]. In doing so, we notice that there are two separate paths through which the neural translation decoder receives error signal. First, the decoder is updated in order to maximize the conditional probability of the correct next word, which has already existed in the original neural machine translation. Second, the decoder is updated also to maximize the conditional probability of the correct parsing action, which is a novel learning signal introduced by the proposed hybridization. Furthermore, the second learning signal affects the encoder as well, encouraging the whole neural translation model to be aware of the syntactic structure of the target language. Later in the experiments, we show that this additional learning signal is useful for translation,  even though we discard the RNNG (the stack and action sLSTMs) in the inference time.
Learning to Parse and Translate Improves Neural Machine Translation
A major challenge in training the proposed hybrid model is that there is not a parallel corpus augmented with gold-standard target-side parse, and vice versa. In other words, we must either parse the target-side sentences of an existing parallel corpus or translate sentences with existing goldstandard parses. As the target task of the proposed model is translation, we start with a parallel corpus and annotate the target-side sentences. It is however costly to manually annotate any corpus of reasonable size ( Table 6 in Alonso et al., 2016). We instead resort to noisy, but automated annotation using an existing parser. This approach of automated annotation can be considered along the line of recently proposed techniques of knowledge distillation (Hinton et al., 2015) and distant supervision (Mintz et al., 2009). In knowledge distillation, a teacher network is trained purely on a training set with ground-truth annotations, and the annotations predicted by this teacher are used to train a student network, which is similar to our approach where the external parser could be thought of as a teacher and the proposed hybrid network's RNNG as a student. On the other hand, what we propose here is a special case of distant supervision in that the external parser provides noisy annotations to otherwise an unlabeled training set.
Learning to Parse and Translate Improves Neural Machine Translation
Specifically, we use SyntaxNet, released by Andor et al. (2016), on a target sentence. We convert a parse tree into a sequence of one of three transition actions (SHIFT, REDUCE-L, REDUCE-R). We label each REDUCE action with a corresponding dependency label and treat it as a more finegrained action.
Learning to Parse and Translate Improves Neural Machine Translation
We compare the proposed NMT+RG against the baseline model on four different language pairs-Jp-En, Cs-En, De-En and Ru-En. The basic statistics of the training data are presented in Table 1.
Learning to Parse and Translate Improves Neural Machine Translation
Ja We use the ASPEC corpus ("train1.txt") from the WAT'16 Jp-En translation task. We tokenize each Japanese sentence with KyTea (Neubig et al., 2011) and preprocess according to the recommendations from WAT'16 (WAT, 2016). We use the first 100K sentence pairs of length shorter than 50 for training. The vocabulary is constructed with all the unique tokens that appear at least twice in the training corpus. We use "dev.txt" and "test.txt" provided by WAT'16 respectively as development and test sets.
Learning to Parse and Translate Improves Neural Machine Translation
Cs, De and Ru We use News Commentary v8 from WMT'16. We use the tokenizer from Moses (Koehn et al., 2007), and build a vocabulary of each language using unique tokens that appear at least 6, 6 and 5 times respectively for Cs, Ru and De. The target-side (English) vocabulary was constructed with all the unique tokens appearing more than three times in each corpus. We only use sentence pairs of length 50 or less for training. We use "newstest2015" and "newstest2016" as development and test sets respectively.
Learning to Parse and Translate Improves Neural Machine Translation
In all our experiments, each recurrent network has a single layer of LSTM units of 256 dimensions, and the word vectors and the action vectors are of 256 and 128 dimensions, respectively. To reduce computational overhead, we use Black-Out (Ji et al., 2015) with 2000 negative samples and α = 0.4. For the proposed NMT+RG, we share the target word vectors between the decoder (buffer) and the stack sLSTM. We use stochastic gradient descent with minibatches of 128 examples. The learning rate starts from 1.0, and is halved each time the perplexity on the development set increases. We clip the norm of the gradient (Pascanu et al., 2012) with the threshold set to 3.0 (2.0 for the baseline models on Ru-En and Cs-En to avoid NaN and Inf). We use beam search in the inference time, with the beam width selected based on the development set performance.
Learning to Parse and Translate Improves Neural Machine Translation
The more details are described in the supplementary material.
Learning to Parse and Translate Improves Neural Machine Translation
In Table 2, we report the translation qualities of the tested models on all the four language pairs. We report both BLEU (Papineni et al., 2002) and RIBES (Isozaki et al., 2010). Except for De-En, measured in BLEU, we observe the statis-  Table 2: BLEU and RIBES scores by the baseline and proposed models on the test set. We use the bootstrap resampling method from Koehn (2004) to compute the statistical significance. We use † to mark those significant cases with p < 0.005. tically significant improvement by the proposed NMT+RG over the baseline model. It is worthwhile to note that these significant improvements have been achieved without any additional parameters nor computational overhead in the inference time.   Table 3, we see that the best performance could only be achieved when all the three components were present. Removing the stack had the most adverse effect, which was found to be the case for parsing as well by Kuncoro et al. (2017). into this possibility for future research.
A Tree-based Decoder for Neural Machine Translation
Most NMT methods use sequence-to-sequence (seq2seq) models, taking in a sequence of source words and generating a sequence of target words (Kalchbrenner and Blunsom, 2013;Sutskever et al., 2014;Bahdanau et al., 2015). While seq2seq models can implicitly discover syntactic properties of the source language (Shi et al., 2016), they do not explicitly model and leverage such information. Motivated by the success of adding syntactic information to Statistical Machine Translation (SMT) (Galley et al., 2004;Menezes and Quirk, 2007;Galley et al., 2006), recent works have established that explicitly leveraging syntactic information can improve NMT quality, ei-1 Our code is available at https://github.com/ cindyxinyiwang/TrDec_pytorch. ther through syntactic encoders Eriguchi et al., 2016), multi-task learning objectives (Chen et al., 2017;Eriguchi et al., 2017), or direct addition of syntactic tokens to the target sequence (Nadejde et al., 2017;Aharoni and Goldberg, 2017). However, these syntax-aware models only employ the standard decoding process of seq2seq models, i.e. generating one target word at a time. One exception is Wu et al. (2017), which utilizes two RNNs for generating target dependency trees. Nevertheless, Wu et al. (2017) is specifically designed for dependency tree structures and is not trivially applicable to other varieties of trees such as phrase-structure trees, which have been used more widely in other works on syntax-based machine translation. One potential reason for the dearth of work on syntactic decoders is that such parse tree structures are not friendly to recurrent neural networks (RNNs).
A Tree-based Decoder for Neural Machine Translation
In this paper, we propose TrDec, a method for incorporating tree structures in NMT. TrDec simultaneously generates a target-side tree topology and a translation, using the partially-generated tree to guide the translation process ( § 2). TrDec employs two RNNs: a rule RNN, which tracks the topology of the tree based on rules defined by a Context Free Grammar (CFG), and a word RNN, which tracks words at the leaves of the tree ( § 3). This model is similar to neural models of tree-structured data from syntactic and semantic parsing (Dyer et al., 2016;Alvarez-Melis and Jaakkola, 2017;Yin and Neubig, 2017), but with the addition of the word RNN, which is especially important for MT where fluency of transitions over the words is critical.
A Tree-based Decoder for Neural Machine Translation
TrDec can generate any tree structure that can be represented by a CFG. These structures include linguistically-motivated syntactic tree representations, e.g. constituent parse trees, as well as syntaxfree tree representations, e.g. balanced binary trees ( § 4). This flexibility of TrDec allows us to com- pare and contrast different structural representations for NMT.
A Tree-based Decoder for Neural Machine Translation
In our experiments ( § 5), we evaluate TrDec using both syntax-driven and syntax-free tree representations. We benchmark TrDec on three tasks: Japanese-English and German-English translation with medium-sized datasets, and Oromo-English translation with an extremely small dataset. Our findings are surprising -TrDec performs well, but it performs the best with balanced binary trees constructed without any linguistic guidance.
A Tree-based Decoder for Neural Machine Translation
TrDec simultaneously generates the target sequence and its corresponding tree structure. We first discuss the high-level generation process using an example, before describing the prediction model ( § 3) and the types of trees used by TrDec ( § 4). Fig. 1 illustrates the generation process of the sentence "_The _cat _eat s _fi sh _.", where the sentence is split into subword units, delimited by the underscore "_" (Sennrich et al., 2016). The example uses a syntactic parse tree as the intermediate tree representation, but the process of generating with other tree representations, e.g. syntax-free trees, follows the same procedure.
A Tree-based Decoder for Neural Machine Translation
Trees used in TrDec have two types of nodes: terminal nodes, i.e. the leaf nodes that represent subword units; and nonterminal nodes, i.e. the nonleaf nodes that represent a span of subwords. Additionally, we define a preterminal node to be a nonterminal node whose children are all terminal nodes. In Fig. 1 Left, the green squares represent preterminal nodes.
A Tree-based Decoder for Neural Machine Translation
TrDec generates a tree in a top-down, left-toright order. The generation process is guided by a CFG over target trees, which is constructed by taking all production rules extracted from the trees of all sentences in the training corpus. Specifically, a rule RNN first generates the top of the tree structure, and continues until a preterminal is reached. Then, a word RNN fills out the words under the preterminal. The model switches back to the rule RNN after the word RNN finishes. This process is illustrated in Fig. 1 Right. Details are as follows:
A Tree-based Decoder for Neural Machine Translation
Step 1. The source sentence is encoded by a sequential RNN encoder, producing the hidden states.
A Tree-based Decoder for Neural Machine Translation
Step 2. The generation starts with a derivation tree with only a Root node. A rule RNN, initialized by the last encoder hidden state computes the probability distribution over all CFG rules whose left hand side (LHS) is Root, and selects a rule to apply to the derivation. In our example, the rule RNN selects ROOT 7 ! S.
A Tree-based Decoder for Neural Machine Translation
Step 3. The rule RNN applies production rules to the derivation in a top-down, left-to-right order, expanding the current opening nonterminal using a CFG rule whose LHS is the opening nonterminal. In the next two steps, TrDec applies the rules S 7 ! NP VP PUNC and NP 7 ! pre to the opening nonterminals S and NP, respectively. Note that after these two steps a preterminal node pre is created.
A Tree-based Decoder for Neural Machine Translation
Step 4a. Upon seeing a preterminal node as the current opening nonterminal, TrDec switches to using a word RNN, initialized by the last state of the encoder, to populate this empty preterminal with phrase tokens, similar to a seq2seq decoder. For example the subword units _The and _cat are generated by the word RNN, ending with a special end-of-phrase token, i.e. heopi.
A Tree-based Decoder for Neural Machine Translation
Step 4b. While the word RNN generates subword units, the rule RNN also updates its own hidden states, as illustrated by the blue cells in Fig. 1 Right.
A Tree-based Decoder for Neural Machine Translation
Step 5. After the word RNN generates heopi, TrDec switches back to the rule RNN to continue generating the derivation from where the tree left off. In our example, this next stage is the opening nonterminal node VP. From here, TrDec chooses the rule VP 7 ! pre NP.
A Tree-based Decoder for Neural Machine Translation
TrDec repeats the process above, intermingling the rule RNN and the word RNN as described, and halts when the rule RNN generates the end-ofsentence token heosi, completing the derivation.
A Tree-based Decoder for Neural Machine Translation
We now describe the computations during the generation process discussed in § 2. At first, a source sentence x, which is split into subwords, is encoded using a standard bi-directional Long Short-Term Memory (LSTM) network (Hochreiter and Schmidhuber, 1997). This bi-directional LSTM outputs a set of hidden states, which TrDec will reference using an attention function (Bahdanau et al., 2015).
A Tree-based Decoder for Neural Machine Translation
As discussed, TrDec uses two RNNs to generate a target parse tree. In our work, both of these RNNs use LSTMs, but with different parameters.
A Tree-based Decoder for Neural Machine Translation
Rule RNN. At any time step t in the rule RNN, there are two possible actions. If at the previous time step t 1, TrDec generated a CFG rule, then the state s tree t is computed by:
A Tree-based Decoder for Neural Machine Translation
t 1 is the embedding of the CFG rule at time step t 1; c t 1 is the context vector computed by attention at s tree t 1 , i.e. input feeding (Luong et al., 2015); s tree p is the hidden state at the time step that generates the parent of the current node in the partial tree; s word t is the hidden state of the most recent time step before t that generated a subword (note that s word t comes from the word RNN, discussed below); and [·] denotes a concatenation.
A Tree-based Decoder for Neural Machine Translation
Meanwhile, if at the previous time step t 1, TrDec did not generate a CFG rule, then the update at time step t must come from a subword being generated by the word RNN. In that case, we also update the rule RNN similarly by replacing the embedding of the CFG rule with the embedding of the subword.
A Tree-based Decoder for Neural Machine Translation
Word RNN. At any time step t, if the word RNN is invoked, its hidden state s word t is:
A Tree-based Decoder for Neural Machine Translation
, where s tree p is the hidden state of rule RNN that generated the CFG rule above the current terminal; w t 1 is the embedding of the word generated at time step t 1; and c t 1 is the attention context computed at the previous word RNN time step t 1.  Softmax. At any step t, our softmax logits are
A Tree-based Decoder for Neural Machine Translation
, where W varies depending on whether a rule or a subword unit is needed.
A Tree-based Decoder for Neural Machine Translation
Unlike prior work on syntactic decoders designed for utilizing a specific type of syntactic information (Wu et al., 2017), TrDec is a flexible NMT model that can utilize any tree structure. Here we consider two categories of tree structures:
A Tree-based Decoder for Neural Machine Translation
Syntactic Trees are generated using a thirdparty parser, such as Berkeley parser (Petrov et al., 2006;Petrov and Klein, 2007). Fig. 2 Top Left illustrates an example constituency parse tree. We also consider a variation of standard constituency parse trees where all of their nonterminal tags are replaced by a null tag, which is visualized in Fig. 2 Top Right. In addition to constituency parse trees, TrDec can also utilize dependency parse trees via a simple procedure that converts a dependency tree into a constituency tree. Specifically, this procedure creates a parent node with null tag for each word, and then attaches each word to the parent node of its head word while preserving the word order. An example of this procedure is provided in Fig. 3.
A Tree-based Decoder for Neural Machine Translation
Balanced Binary Trees are syntax-free trees constructed without any linguistic guidance. We use two slightly different versions of binary trees. Version 1 (Fig. 2 Bottom Left) is constructed by recursively splitting the target sentence in half and creating left and right subtrees from the left and right halves of the sentence respectively. Version 2 (Fig. 2 Bottom Right), is constructed by applying Version 1 on a list of nodes where consecutive words are combined together. All tree nodes in both versions have the null tag. We discuss these construction processes in more detail in Appendix A.1.
A Tree-based Decoder for Neural Machine Translation
In the experiments detailed later, we evaluated TrDec with four different settings of tree structures: 1) the fully syntactic constituency parse trees; 2) constituency parse trees with null tags; 3) dependency parse trees; 4) a concatenation of both version 1 and version 2 of the binary trees, (which effectively doubles the amount of the training data and leads to slight increases in accuracy).
A Tree-based Decoder for Neural Machine Translation
Datasets. We evaluate TrDec on three datasets: 1) the KFTT (ja-en) dataset (Neubig, 2011), which consists of Japanese-English Wikipedia articles; 2) the IWSLT2016 German-English (de-en) dataset (Cettolo et al., 2016), which consists of TED Talks transcriptions; and 3) the LORELEI Oromo-English (or-en) dataset 2 , which largely consists of texts from the Bible. Details are in Tab. 1. English sentences are parsed using Ckylark (Oda et al., 2015) for the constituency parse trees, and Stanford Parser (de Marneffe et al., 2006;Chen and Manning, 2014) for the dependency parse trees. We use byte-pair encoding (Sennrich et al., 2016) with 8K merge operations on ja-en, 4K merge operations on or-en, and 24K merge operations on de-en.  Baselines. We compare TrDec against three baselines: 1) seq2seq: the standard seq2seq model with attention; 2) CCG: a syntax-aware translation model that interleaves Combinatory Categorial Grammar (CCG) tags with words on the target side 2 LDC2017E29 of a seq2seq model (Nadejde et al., 2017); 3) CCGnull: the same model with CCG, but all syntactic tags are replaced by a null tag; and 4) LIN: a standard seq2seq model that generates linearized parse trees on the target side (Aharoni and Goldberg, 2017).
A Tree-based Decoder for Neural Machine Translation
Results. Tab. 2 presents the performance of our model and the three baselines. For our model, we report the performance of TrDec-con, TrDec-connull, TrDec-dep, and TrDec-binary (settings 1,2,3,4 in § 4). On the low-resource or-en dataset, we observe a large variance with different random seeds, so we run each model with 6 different seeds, and report the mean and standard deviation of these runs. TrDec-con-null and TrDec-con achieved comparable results, indicating that the syntactic labels have neither a large positive nor negative impact on TrDec. For ja-en and or-en, syntax-free TrDec outperforms all baselines. On de-en, TrDec loses to CCG-null, but the difference is not statistically significant (p > 0.1).  Length Analysis. We performed a variety of analyses to elucidate the differences between the translations of different models, and the most conclusive results were through analysis based on the length of the translations. First, we categorize the ja-en test set into buckets by length of the reference sentences, and compare the models for each length category. Fig. 4 shows the gains in BLEU score over seq2seq for the tree-based models. Since TrDec-con outperforms TrDec-dep for all datasets, we only focus on TrDec-con for analyzing TrDec's performance with syntactic trees. The relative performance of CCG decreases on long sentences. However, TrDec, with both parse trees and syntaxfree binary trees, delivers more improvement on longer sentences. This indicates that TrDec is bet-ter at capturing long-term dependencies during decoding. Surprisingly, TrDec-binary, which does not utilize any linguistic information, outperforms TrDec-con for all sentence length categories. Second, Fig. 5 shows a histogram of translations by the length difference between the generated output and the reference. This provides an explanation of the difficulty of using parse trees. Ideally, this distribution will be focused around zero, indicating that the MT system is generating translations about the same length as the reference. However, the distribution of TrDec-con is more spread out than TrDec-binary, which indicates that it is more difficult for TrDec-con to generate sentences with appropriate target length. This is probably because constituency parse trees of sentences with similar number of words can have very different depth, and thus larger variance in the number of generation steps, likely making it difficult for the MT model to plan the sentence structure a-prior before actually generating the child sentences. TrDec-binary TrDec-con CCG Figure 5: Distribution of length difference from reference.
A Tree-based Decoder for Neural Machine Translation
We propose TrDec, a novel tree-based decoder for NMT, that generates translations along with the target side tree topology. We evaluate TrDec on both linguistically-inspired parse trees and synthetic, syntax-free binary trees. Our model, when used with synthetic balanced binary trees, outperforms CCG, the existing state-of-the-art in incorporating syntax in NMT models. The interesting result that syntax-free trees outperform their syntax-driven counterparts elicits a natural question for future work: how do we better model syntactic structure in these models? It would also be interesting to study the effect of using source-side syntax together with the target-side syntax supported by TrDec.
Sequence-to-Dependency Neural Machine Translation
Recently, Neural Machine Translation (NMT) with the attention-based encoder-decoder framework (Bahdanau et al., 2015) has achieved significant improvements in translation quality of many language pairs (Bahdanau et al., 2015;Luong et al., 2015a;Tu et al., 2016;. In a conventional NMT model, an encoder reads in source sentences of various lengths, and transforms them into sequences of intermediate hidden vector representations. After weighted by attention operations, combined hidden vectors are used by the decoder to generate translations. In most of cases, both encoder and decoder are implemented as recurrent neural networks (RNNs). * Contribution during internship at Microsoft Research.
Sequence-to-Dependency Neural Machine Translation
Many methods have been proposed to further improve the sequence-to-sequence NMT model since it was first proposed by Sutskever et al. (2014) and Bahdanau et al. (2015). Previous work ranges from addressing the problem of out-ofvocabulary words (Jean et al., 2015), designing attention mechanism (Luong et al., 2015a), to more efficient parameter learning (Shen et al., 2016), using source-side syntactic trees for better encoding (Eriguchi et al., 2016) and so on. All these NMT models employ a sequential recurrent neural network for target generations. Although in theory RNN is able to remember sufficiently long history, we still observe substantial incorrect translations which violate long-distance syntactic constraints. This suggests that it is still very challenging for a linear RNN to learn models that effectively capture many subtle long-range word dependencies. For example, Figure 1 shows an incorrect translation related to the long-distance dependency. The translation fragment in italic is locally fluent around the word is, but from a global view the translation is ungrammatical. Actually, this part of translation should be mostly affected by the distant plural noun foreigners rather than words Venezuelan government nearby.
Sequence-to-Dependency Neural Machine Translation
Fortunately, such long-distance word correspondence can be well addressed and modeled by syntactic dependency trees. In Figure 1, the head word foreigners in the partial dependency tree (top dashed box) can provide correct structural context for the next target word, with this information it is more likely to generate the correct word will rather than is. This structure has been successfully applied to significantly improve the performance of statistical machine translation (Shen et al., 2008). On the NMT side, introducing target syntactic structures could help solve the problem of ungrammatical output because it can bring two advantages over state-of-the-art NMT models: a) syntactic trees can be used to model the grammatical validity of translation candidates; b) partial syntactic structures can be used as additional context to facilitate future target word prediction.  Figure 1: Dependency trees help the prediction of the next target word. "NMT" refers to the translation result from a conventional NMT model, which fails to capture the long distance word relation denoted by the dashed arrow.
Sequence-to-Dependency Neural Machine Translation
However, it is not trivial to build and leverage syntactic structures on the target side in current NMT framework. Several practical challenges arise:
Sequence-to-Dependency Neural Machine Translation
(1) How to model syntactic structures such as dependency parse trees with recurrent neural network;
Sequence-to-Dependency Neural Machine Translation
(2) How to efficiently perform both target word generation and syntactic structure construction tasks simultaneously in a single neural network;
Sequence-to-Dependency Neural Machine Translation
(3) How to effectively leverage target syntactic context to help target word generation.
Sequence-to-Dependency Neural Machine Translation
To address these issues, we propose and empirically evaluate a novel Sequence-to-Dependency Neural Machine Translation (SD-NMT) model in our paper. An SD-NMT model encodes source inputs with bi-directional RNNs and associates them with target word prediction via attention mechanism as in most NMT models, but it comes with a new decoder which is able to jointly generate target translations and construct their syntactic dependency trees. The key difference from conventional NMT decoders is that we use two RNNs, one for translation generation and the other for dependency parse tree construction, in which incremental parsing is performed with the arc-standard shift-reduce algorithm proposed by Nivre (2004).
Sequence-to-Dependency Neural Machine Translation
We will describe in detail how these two RNNs work interactively in Section 3.
Sequence-to-Dependency Neural Machine Translation
We evaluate our method on publicly available data sets with Chinese-English and Japanese-English translation tasks. Experimental results show that our model significantly improves translation accuracy over the conventional NMT and SMT baseline systems.
Sequence-to-Dependency Neural Machine Translation
As a new paradigm to machine translation, NMT is an end-to-end framework (Sutskever et al., 2014;Bahdanau et al., 2015) which directly models the conditional probability P (Y |X) of target translation Y = y 1 ,y 2 ,...,y n given source sentence X = x 1 ,x 2 ,...,x m . An NMT model consists of two parts: an encoder and a decoder. Both of them utilize recurrent neural networks which can be a Gated Recurrent Unit (GRU) (Cho et al., 2014) or a Long Short-Term Memory (LSTM) (Hochreiter and Schmidhuber, 1997) in practice. The encoder bidirectionally encodes a source sentence into a sequence of hidden vectors H = h 1 ,h 2 ,...,h m with a forward RNN and a backward RNN. Then the decoder predicts target words one by one with probability P (Y |X) = n j=1 P (y j |y <j , H)
Sequence-to-Dependency Neural Machine Translation
Typically, for the jth target word, the probability P (y j |y <j , H) is computed as P (y j |y <j , H) = g(s j , y j−1 , c j )
Sequence-to-Dependency Neural Machine Translation
where g is a nonlinear function that outputs the probability of y j , and s j is the RNN hidden state. The context c j is calculated at each timestamp j based on H by the attention network
Sequence-to-Dependency Neural Machine Translation
where v a , W a , U a are the weight matrices. The attention mechanism is effective to model the correspondences between source and target.
Sequence-to-Dependency Neural Machine Translation
We use a shift-reduce transition-based dependency parser to build the syntactic structure for the target language in our work. Specially, we adopt the arcstandard algorithm (Nivre, 2004) to perform incremental parsing during the translation process. In this algorithm, a stack and a buffer are maintained to store the parsing state over which three kinds of transition actions are applied. Let w 0 and w 1 be two topmost words in the stack, andw be the current new word in a sequence of input, three transition actions are described as below.
Sequence-to-Dependency Neural Machine Translation
• Shift(SH) : Pushw to the stack.
Sequence-to-Dependency Neural Machine Translation
• Left-Reduce(LR(d)) : Link w 0 and w 1 with dependency label d as w 0 d − →w 1 , and reduce them to the head w 0 .
Sequence-to-Dependency Neural Machine Translation
• Right-Reduce(RR(d)) : Link w 0 and w 1 with dependency label d as w 0 d ← −w 1 , and reduce them to the head w 1 .
Sequence-to-Dependency Neural Machine Translation
During parsing, an specific structure is used to record the dependency relationship between different words of input sentence. The parsing finishes when the stack is empty and all input words are consumed. As each word must be pushed to the stack once and popped off once, the number of actions needed to parse a sentence is always 2n, where n is the length of the sentence (Nivre, 2004). Because each valid transition action sequence corresponds to a unique dependency tree, a dependency tree can also be equivalently represented by a sequence of transition actions.
Sequence-to-Dependency Neural Machine Translation
An SD-NMT model is an extension to the conventional NMT model augmented with syntactic structural information of target translation. Given a source sentence X = x 1 ,x 2 ,..,x m , its target translation Y = y 1 ,y 2 ,..,y n and Y 's dependency parse tree T , the goal of the extension is to enable us to compute the joint probability P (Y, T |X). As in most structural learning tasks, the full prediction of Y and T is further decomposed into a chain of smaller predictions. For translation Y , it is generated in the left-to-right order as y 1 , y 2 , .., y n following the way in a normal sequence-to-sequence model. For Y 's parse tree T , instead of directly modeling the tree itself, we predict a parsing action sequence A which can map Y to T . Thus at top level our SD-NMT model can be formulated as
Sequence-to-Dependency Neural Machine Translation
= P (y 1 y 2 ..y n , a 1 , a 2 ..a l |X) (6) where A = a 1 ,a 2 ,..,a j ,..,a l 1 with length l (l = 2n), a j ∈ {SH, RR(d), LR(d)} 2 . Two recurrent neural networks, Word-RNN and Action-RNN, are used to model generation processes of translation sequence Y and parsing action sequence A respectively. Figure 2 shows an example how translation Y and its parsing actions are predicted step by step.  Figure 2: Decoding example of our SD-NMT model for target sentence "who are you" with transition action sequence "SH SH LR SH RR". The ending symbol EOS is omitted.
Sequence-to-Dependency Neural Machine Translation
Because the lengths of Word-RNN and Action-RNN are different, they are designed to work in a mutually dependent way: a target word is only allowed to be generated when the SH action is predicted in the action sequence. In this way, we can perform incremental dependency parsing for translation Y and at the same time track the partial parsing status through the translation generation process.
Sequence-to-Dependency Neural Machine Translation
For notational clarity, we introduce a virtual translation sequenceŶ =ŷ 1 ,ŷ 2 ,..,ŷ j ,..,ŷ l for Word-RNN which has the same length l with transition action sequence.ŷ j is defined aŝ
Sequence-to-Dependency Neural Machine Translation
Apparently the mapping fromŶ to Y is deterministic, and Y can be easily derived givenŶ and A.
Sequence-to-Dependency Neural Machine Translation
With the notation ofŶ , the sequence probability of Y and A can be written as
Sequence-to-Dependency Neural Machine Translation
whereŶ <j refers to the subsequencê y 1 ,ŷ 2 , ..,ŷ j−1 , and A ≤j to a 1 , a 2 , .., a j . Based on Equation 7 and 8, the overall joint model can be computed as
Sequence-to-Dependency Neural Machine Translation
As we have two RNNs in our model, the termination condition is also different from a conventional NMT model. In decoding, we maintain a stack to track the parsing configuration, and our model terminates once the Word-RNN predicts a special ending symbol EOS and all the words in the stack have been reduced. Figure 3 (a) gives an overview of our SD-NMT model. Due to space limitation, the detailed interconnections between two RNNs are only illustrated at timestamp j. The encoder of our model follows standard bidirectional RNN configuration. At timestamp j during decoding, our model first predicts an action a j by Action-RNN, then Word-RNN checks the condition gate δ according to a j . If a j = SH, the Word-RNN will generate a new state (solid arrow) and predict a new target word y v j , otherwise it just copies previous state (dashed arrow) to the current state. For example, at timestamp 3, a 3 = SH, the state of Word-RNN is copied from its previous one. Meanwhile,ŷ 3 = y 2 is used as the immediate proceeding word in translation history.
Sequence-to-Dependency Neural Machine Translation
When computing attention scores, we extend Equation 5 by replacing the decoder hidden state with the concatenation of Word-RNN hidden state s and Action-RNN hidden state s (gray boxes in Figure 3). The new attention score is then updated as
Sequence-to-Dependency Neural Machine Translation
Syntax has been proven useful for sentence generation task (Dyer et al., 2016). We propose to leverage target syntax to help translation generation. In our model, the syntactic context K j at timestamp j is defined as a vector which is computed by a feed-forward network based on current parsing configuration of Action-RNN. Denote that w 0 and w 1 are two topmost words in the stack, w 0l and w 1l are their leftmost modifiers in the partial tree, w 0r and w 1r their rightmost modifiers respectively. We define two unigram features and four bigram features. The unigram features are w 0 and w 1 which are represented by the word embedding vectors. The bigram features are w 0 w 0l , w 0 w 0r , w 1 w 1l and w 1 w 1r . Each of them is computed by
Sequence-to-Dependency Neural Machine Translation
These kinds of feature template have beeb proven effective in dependency parsing task (Zhang and Clark, 2008). Based on these features, the syntactic context vector K j is computed as
Sequence-to-Dependency Neural Machine Translation
where W k , U k , W b , U b are the weight matrices, E stands for the embedding matrix. Figure 2 (b) gives an overview of the construction of K j . Note that zero vector is used for padding the words which are not available in the partial tree, so that all the K vectors have the same input size in computation.
Sequence-to-Dependency Neural Machine Translation
Adding K j to Equation 2, the probabilities of transition action and word in Equation 7 and 8 are then updated as P (a j |a <j , X,Ŷ <j ) = g(s j , a j−1 , c j , K j ) (12) P (ŷ j |ŷ <j , X, A ≤j ) = g(s j ,ŷ j−1 , c j , K j ) (13)
Sequence-to-Dependency Neural Machine Translation
After each prediction step in Word-RNN and Action-RNN, the syntax context vector K will be updated accordingly. Note that K is not used to calculate the recurrent states s in this work.
Sequence-to-Dependency Neural Machine Translation
For SD-NMT model, we use the sum of loglikelihoods of word sequence and action sequence as objective function for training algorithm, so that the joint probability of target translations and their parsing trees can be maximized:
Sequence-to-Dependency Neural Machine Translation
We also use mini-batch for model training. As the target dependency trees are known in the bilingual corpus during training, we pre-compute the partial tree state and syntactic context at each time stamp for each training instance. Thus it is easy for the model to process multiple trees in one batch.
Sequence-to-Dependency Neural Machine Translation
In the decoding process of an SD-NMT model, the score of each search path is the sum of log probabilities of target word sequence and transition action sequence normalized by the sequence length:
Sequence-to-Dependency Neural Machine Translation
where n is word sequence length and l is action sequence length.
Sequence-to-Dependency Neural Machine Translation
The experiments are conducted on the Chinese-English task as well as the Japanese-English translation tasks where the same data set from WAT 2016 ASPEC corpus  3 is used for a fair comparison with other work. In addition to evaluate translation performance, we also investigate the quality of dependency parsing as a by-product and the effect of parsing quality against translation quality.
Sequence-to-Dependency Neural Machine Translation
In the Chinese-English task, the bilingual training data consists of a set of LDC datasets, 4 which has around 2M sentence pairs. We use NIST2003 as the development set, and the testsets contain NIST2005, NIST2006, NIST2008 and NIST2012. All English words are lowercased. In the Japanese-English task, we use top 1M sentence pairs from ASPEC Japanese-English corpus. The development data contains 1,790 sentences, and the test data contains 1,812 sentences with single reference per source sentence.
Sequence-to-Dependency Neural Machine Translation
To train SD-NMT model, the target dependency tree references are needed. As there is no golden annotation of parse trees over the target training data, we use pseudo parsing results as the target dependency references, which are got from an in-house developed arc-eager dependency parser based on work in (Zhang and Nivre, 2011 In the neural network training, the vocabulary size is limited to 30K high frequent words for both source and target languages. All low frequent words are normalized into a special token unk and post-processed by following the work in (Luong et al., 2015b). The size of word embedding and transition action embedding is set to 512. The dimensions of the hidden states for all RNNs are set to 1024. All model parameters are initialized randomly with Gaussian distribution (Glorot and Bengio, 2010) and trained on a NVIDIA Tesla K40 GPU. The stochastic gradient descent (SGD) algorithm is used to tune parameters with a learning rate of 1.0. The batch size is set to 96. In the update procedure, Adadelta (Zeiler, 2012) algorithm is used to automatically adapt the learning rate. The beam sizes for both word prediction and transition action prediction are set to 12 in decoding.
Sequence-to-Dependency Neural Machine Translation
The baselines in our experiments are a phrasal system and a neural translation system, denoted by HPSMT and RNNsearch respectively. HPSMT is an in-house implementation of the hierarchical phrase-based model (Chiang, 2005), where a 4gram language model is trained using the modified Kneser-Ney smoothing (Kneser and Ney, 1995) algorism over the English Gigaword corpus (LDC2009T13) plus the target data from the bilingual corpus. RNNsearch is an in-house implementation of the attention-based neural machine translation model (Bahdanau et al., 2015) using the same parameter settings as our SD-NMT model including word embedding size, hidden vector dimension, beam size, as well as the same mechanism for OOV word processing.
Sequence-to-Dependency Neural Machine Translation
The evaluation results are reported with the case-insensitive IBM BLEU-4 (Papineni et al., 2002). A statistical significance test is performed using the bootstrap resampling method proposed by Koehn (2004) with a 95% confidence level. For Japanese-English task, we use the official eval-uation procedure provided by WAT 2016. 5 , where both BLEU and RIBES (Isozaki et al., 2010) are used for evaluation.
Sequence-to-Dependency Neural Machine Translation
We evaluate our method on the Chinese-English translation task. The evaluation results over all NIST test sets against baselines are listed in Table  1. Generally, RNNsearch outperforms HPSMT by 3.78 BLEU points on average while SD-NMT surpasses RNNsearch 2.03 BLUE point gains on average, which shows that NMT models usually achieve better results than SMT models, and our proposed sequence-to-dependency NMT model performs much better than traditional sequence-tosequence NMT model. We also investigate the effect of syntactic knowledge context by excluding its computation in Equation 12 and 13. The alternative model is denoted by SD-NMT\K. According to Table  1, SD-NMT\K outperforms RNNsearch by 0.54 BLEU points but degrades SD-NMT by 1.49 BLEU points on average, which demonstrates that the long distance dependencies captured by the target syntactic knowledge context, such as leftmost/rightmost children together with their dependency relationships, really bring strong positive effects on the prediction of target words.
Sequence-to-Dependency Neural Machine Translation
In addition to translation quality, we compare the perplexity (PPL) changes on the development set in terms of numbers of training mini-batches for RNNsearch and SD-NMT in Figure 4. We can see that the PPL of SD-NMT is initially higher than that of RNNsearch, but decreased to be lower over time. This is mainly because the quality of parse tree is too poor at the beginning which degrades translation quality and leads to higher PPL. After some training iterations, the SD-NMT   In our experiments, the time cost of SD-NMT is two times of that for RNNsearch due to a more complicated model structure. But we think it is a worthy trade to pursue high quality translations.
Sequence-to-Dependency Neural Machine Translation
In this section, we report results on the Japanese-English translation task. To ensure fair comparisons, we use the same training data and follow the pre-processing steps recommended in WAT 2016 6 . Table 2 shows the comparison results from 8 systems with the evaluation metrics of BLEU and RIBES. The results in the first 3 rows are produced by SMT systems taken from the official WAT 2016. The remaining results are produced by NMT systems, among which the bottom two row results are taken from our in-house NMT systems and others refer to the work in (Cromieres, 2016; that are the competitive NMT results on WAT 2016. According to Table  2, NMT results still outperform SMT results similar to our Chinese-English evaluation results. The SD-NMT model significantly outperforms most other NMT models, which shows that our proposed approach to modeling target dependency tree benefit NMT systems since our RNNsearch baseline achieves comparable performance with the single layer attention-based NMT system in (Cromieres, 2016). Note that our SD-NMT gets comparable results with the 4 single-layer ensemble model in (Cromieres, 2016;. We believe SD-NMT can get more improvements with an ensemble of multiple models in future experiments.
Sequence-to-Dependency Neural Machine Translation
The interaction effect between dependency tree conduction and target word generation is investigated in this section. The experiments are conducted on the Chinese-English task over multiple test sets. We evaluate how the quality of dependency trees affect the performance of translation.
Sequence-to-Dependency Neural Machine Translation
In the decoding phase of SD-NMT, beam search is applied to the generations of both transition and actions as illustrated in Equation 15. Intuitively, the larger the beam size of action prediction is, the better the dependency tree quality is. We fix the beam size for generating target words to 12, and change the beam size for action prediction to see the difference. Figure 5 shows the evaluation results of all test sets. There is a tendency for BLEU scores to increase with the growth of action prediction beam size. The reason is that the translation quality increases as the quality of dependency tree improves, which shows the construction of dependency trees can boost the generation of target  Figure 5: Translation performance against the beam size of action prediction.
Sequence-to-Dependency Neural Machine Translation
words, and vice versa we believe.
Sequence-to-Dependency Neural Machine Translation
As a by-product, the quality of dependency trees not only affects the performance of target word generation, but also influences the possible downstream processors or tasks such as text analyses. The direct evaluation of tree quality is not feasible due to the unavailable golden references. So we resort to estimating the consistency between the by-products and the parsing results of our standalone dependency parser with state-of-the-art performance. The higher the consistency is, the closer the performance of by-product is to the standalone parser. To reduce the influence of ill-formed data as much as possible, we build the evaluation data set by heuristically selecting 360 SD-NMT translation results together with their dependency trees from NIST test sets where both source-and target-side do not contain unk and have a length of 20-30. We then take the parsing results of the stand-alone parser for these translations as references to indirectly estimate the quality of byproducts. We get a UAS (unlabeled attachment score) of 94.96% and a LAS (labeled attachment score) of 93.92%, which demonstrates that the dependency trees produced by SD-NMT are much similar with the parsing results from the standalone parser.
Sequence-to-Dependency Neural Machine Translation
In this section, we give a case study to explain how our method works. Figure 6 shows a translation example from the NIST testsets. SMT and RNNsearch refer to the translation results from the baselines HPSMT and NMT. For our SD-NMT model, we list both the generated translation and its corresponding dependency tree. We find that the translation of SMT is disfluent and ungrammatical, whereas RNNsearch is better than SMT. Although the translation of RNNsearch is locally fluent around word "have" in the rectangle, both its grammar is incorrect and its meaning is inaccurate from a global view. The word "have" should be in a singular form as its subject is "safety" rather than "workers". For our SD-NMT model, we can see that the translation is much better than baselines and the dependency tree is reasonable. The reason is that after generating the word "workers", the previous subtree in the gray region is transformed to the syntactic context which can guide the generation of the next word as illustrated by the dashed arrow. Thus our model is more likely to generate the correct verb "is" with singular form. In addition, the global structure helps the model correctly identify the inverted sentence pattern of the former translated part and make better choices for the future translation ("only when .. can .." in our translation, "only when .. will .." in the reference), which remains a challenge for conventional NMT model.
Sequence-to-Dependency Neural Machine Translation
In this paper, we propose a novel string-todependency translation model over NMT. Our model jointly performs target word generation and arc-standard dependency parsing. Experimental results show that our method can boost the two procedures and achieve significant improvements on the translation quality of NMT systems.
Sequence-to-Dependency Neural Machine Translation
In future work, along this research direction, we will try to integrate other prior knowledge, such as semantic information, into NMT systems. In addition, we will apply our method to other sequenceto-sequence tasks, such as text summarization, to verify the effectiveness.