Year: 2019

Abstract:
We present Neural Phrase-to-Phrase Machine Translation (NPMT), a phrasebased translation model that uses a novel phrase-attention mechanism to discover relevant input (source) segments to generate output (target) phrases. We propose an efficient dynamic programming algorithm to marginalize over all possible segments at training time and use a greedy algorithm or beam search for decoding. We also show how to incorporate a memory module derived from an external phrase dictionary to NPMT to improve decoding. Experiment results demonstrate that NPMT outperforms the best neural phrase-based translation model (Huang et al., 2018) both in terms of model performance and speed, and is comparable to a state-of-the-art Transformer-based machine translation system (Vaswani et al., 2017).

heading: 1 INTRODUCTION
text: Segmental structures (i.e., phrasal information) are abstractions that have been shown to be useful in machine translation. State-of-the-art machine translation systems prior to the deep learning revolution were dominated by phrase-based models (Koehn et al., 2003; 2007; Lopez, 2008; Koehn, 2009). In contrast to word-based approaches, these methods consider explicit phrase structures in both source and target sentences and model their alignments.
Recent advances in sequence-to-sequence learning (Sutskever et al., 2014) and attention-based mechanisms (Bahdanau et al., 2014) have driven impressive progress on a new generation of machine translation models. They typically consist of three main components: an encoder that summarizes the source sentence into vectors, a decoder that generates the translation word by word, and a wordbased attention module that is used by the decoder to capture relevant source information when decoding. Innovations in terms of model architectures (Vaswani et al., 2017; Gehring et al., 2017a) and optimization algorithms (Ba et al., 2016) push these models to become the de facto state-of-the-art machine translation systems. These models operate at the word-level, since discovering phrases for both the source and target sentences and incorporating this phrasal information into a neural sequence to sequence model is not straightforward (i.e., it requires marginalizing over all possible phrase alignments in a neural model).
Huang et al. (2018) show a first-step toward a neural phrase-based machine translation model by designing a model that is aware of phrase structures in the target sentence. They show that such an approach leads to better results compared to baseline sequence to sequence models on several language pairs.
In this paper, we present the first neural phrase-based machine translation model (NP2MT) that considers phrasal information in both the source and target sentences. Our model uses segmental recurrent neural networks (Kong et al., 2015) to discover phrases on the source sentence and a novel phrase-attention model to align them to generated target phrases (§2.1). We design a dynamic programming algorithm to efficiently marginalize over all possible segments (phrases) in the source and target sentences in our model for training (§2.3) and use a greedy algorithm or beam search for decoding (§2.4). We also show how to augment this model with a memory module consisting of phrase-to-phrase translation (i.e., a phrase dictionary) in a setup when there are many unseen
words (e.g., proper nouns, cross-domain translation) to improve performance (§2.5). Experiments on benchmark datasets show that our model outperforms existing phrase-based machine translation models both in terms of performance and speed and is competitive with state-of-the-art word-based models (§3).
2 NP2MT
Consider a source sentence x1:S = {x1, x2, . . . , xS} and a target sentence y1:T = {y1, y2, . . . , yT }. Our model is based on the sequence-to-sequence model (Sutskever et al., 2014) with two main components: a source sentence encoder and a target sentence decoder. Figure 1 shows an overview of NP2MT, we describe each component in details below.

heading: 2.1 ENCODER
text: We represent each word in x1:S as a vector and use a bidirectional LSTM to obtain token representations r1, . . . , rS by concatenating the forward and backward hidden states.
We then obtain phrase representations using another bidirectional LSTM that takes token representations above as inputs based on Segmental RNNs (Kong et al., 2015). Specifically, in order to compute the representation of a phrase spanning from the i-th token to the j-th token, denoted by si:j , we run a bidirectional LSTM with ri, . . . , rj as inputs. Denote the hidden states of the forward LSTM by −→ h and the hidden states of the backward LSTM by ←− h . We have si:j = concat( −→ h j , ←− h i).
Given the maximum segment length P (a hyperparameter of the model), we compute representations for all phrases:
si,j ,∀(i, j) ∈ {(i, j) : 1 ≤ i ≤ j ≤ i+ P − 1 ≤ S} Since we use a bidirectional LSTM as the phrase encoder and all phrases are contiguous segments, we can efficiently compute these representations in O(SP ).

heading: 2.2 DECODER
text: Let z ∈ Zy1:T be a valid of segmentation of y1:T = {y1, y2, . . . , yT }. Denote each segment in z by zk and the number of segments |zk|.
The generative process of the target sentence is:
• For each segment k = 1, . . . , |zk|: – Sample a word yki until we get the end of segment symbol (i.e., yki = $) or the end of
sentence symbol in the last segment (i.e., yki = $$).
Our decoder consists of two main components:
• A unidirectional (forward) LSTM to compute a contextual representation gz<zk of previously generated segments z<k. In training time, gz<k can be obtained simply by running the LSTM on all target words from previous segments token by token.
• A segment decoder that generates words in the current segment. The segment decoder is an attention-based model over all possible source phrases si,j , gz<zk , and previously generated words in the current segment yzk<t.
We compute the phrase-attention score azki,j once for every segment zk, using gz<zk to query all possible source phrase representations si,j :
azki,j = attn(si,j ,gz<zk ) (1)
The phrase-attention score azki,j gives a soft alignment 1 between the target phrase zk and the source phrases si,j . The attention value is then computed as the sum over si,j weighted by the attention score azki,j . We use it as the initial state of the segment decoder.
The probability of generating the target sentence is computed as: p(y1:T | x1:S) = ∑
z∈Zy1:T
∏ t∈zk p(yzkt | si,j ,gz<zk ,y zk <t)

heading: 2.3 TRAINING
text: For a given pair of source and target sentence, the objective function that we would like to maximize in Eq. 2 is intractable due to the summation over Zy1:T (i.e., all possible target segmentations). Here, we show a dynamic programming algorithm to compute it efficiently.
Denote the probability of generating all valid segmentations ending in the n-th target words by α(n). The probability of generating the entire sentence is therefore α(T ).
We have the following recursive function: α(n) = ∑ m<n α(m) ∏ t∈z(m,n) p(yz (m,n) t | si,j ,gz<z(m,n) ,y z(m,n) <t ),
where α(0) = 1, and z(m,n) denotes a segment from m to n. The computational complexity of this dynamic programming algorithm is O(TP ), where P is the maximum (target) segment length.

heading: 2.4 DECODING
text: For inference at test time (i.e. decoding), we cannot use dynamic programming in §2.3 since the target sentence is unknown. We either use a greedy algorithm or beam search for decoding.
Greedy algorithm For the greedy method, we follow the generative process in §2.2 and greedily pick the word yki , until we reach the end of sentence symbol (i.e. y k i = $$).
Beam search Our beam search algorithm is different from the standard left-to-right beam search algorithm used in vanilla sequence-to-sequence models since the probability for the next word is conditioned not only on the local context with in the segment, but also on all previously generated segments. The main idea of our algorithm is to keep track of both during the beam search process. We show our Algorithm in Appendix A.
We maintain a set Yo to store the incomplete (open) sentences during the search. An open sentence is represented as a tuple consisting of three elements: previously generated segments, previously
1Enforcing a hard attention similar as in (Raffel et al., 2017) may be beneficial in the context of phrase-level attention. We leave that for future work.
generated words in the current segment, and the probability of generating the open sentence so far. This tuple contains sufficient information to compute the probability distribution of the next output word. We update each element (each open sentence) in Yo after we generate a new word, so the open sentences in Yo will always have the same length.

heading: 2.5 DECODING WITH A MEMORY MODULE
text: In language modeling, augmenting a recurrent neural network with a memory module at evaluation time has been shown to improve performance (Grave et al., 2016; Krause et al., 2017; Grave et al., 2017), especially for rare word predictions and in an open vocabulary setup. We explore the possibility of augmenting a neural machine translation model with a persistent memory module derived from external sources (i.e., a phrase-to-phrase dictionary) to improve decoding.
In this setup, we first build a phrase-to-phrase dictionary using a phrase extractor from Moses (Koehn et al., 2007). During decoding, at each timestep, we compute attention scores forr all possible source segments azki,j . We then choose the source phrase with the highest score to be translated. Given the attended source phrase, we decide whether to use a dictionary to translate the phrase or not. We perform a memory lookup and check whether the phrase is in the dictionary. If it is, we directly translate using the dictionary; otherwise, we proceed as in the greedy decoding case described above. When there are multiple translations for a phrase in the dictionary, we use the model to score all candidates, and then choose the best one as follows:
yzk ← argmax dzk∈dzk ∏ t∈zk p(dzkt | sm:n,gz<zk ,d zk <t) (2)
We summarize our memory-augmented decoding method in Algorithm 1 and illustrate it in Figure 2.
We note that word-based models can also benefit from the augmented memory module. However, it is more straightforward to use the phrase-level information in NP2MT. The word-based models only lookup phrases with source with length 1 using attention weights. Experiments show that when compared to models not augmented with memory modules, NP2MT improves significantly when there is a larger amount of OOV (See Appendix Table 6).
In addition, it is also possible to augment beam search decoding with a memory module. In this case, we perform a lookup and we add the translated phrase to Yo after the beam reaches the length of the translated phrase. We present the greedy case for simplicity. It should be straight-forward for the readers to extend the algorithm into beam search cases by combining algorithms 1 and 2.
We leave exploration of beam search and memory to future work.

heading: 3 EXPERIMENTS

heading: 3.1 DATASETS
text: We use IWSLT 2014 German-English (Cettolo et al., 2014) and IWSLT 2015 English-Vietnamese (Cettolo et al., 2015) as our benchmark datasets. We use ‘word’ as a basic unit as words are better atoms for phrases, while many other papers use BPE (Sennrich et al., 2015). We think word level experiments fit more into the purpose of examining our model, so in our discussion and analysis, we
Data: a source sentence: x1:T , a dictionary: D, maximum segment length P Result: a target sentence: y Compute the representations si,j for all phrases given the maximum segment length P ; y = ; while y not ends with $$ do
Compute phrase-attention score: ; azki,j = attn(si,j ,gz<zk ) ; m,n = argmaxazki,j if UNK in xm:n then
// Retrieve all translations for xm:n from D; // The function src retrieves the original text for segment xm:n ; dzk = lookup(D,src(xm:n)) ; // Select the best candidate ranked by the segment decoder, fixing the attention on sm:n ; yzk ← argmax
dzk∈dzk
∏ t∈zk p(d zk t | sm:n,gz<zk ,d zk <t) ;
else Generate yzk following the greedy algorithm (§2.4) ; end Append yzk to output y;
end Algorithm 1: NP2MT greedy decoding with dictionary
use the word level models. We run the BPE level experiment for the German-English dataset as a reference.
The IWSLT14 German-English dataset contains approximately 153,000 training pairs, 7,000 development pairs, and 7,000 test pairs from translated TED talks. We apply the same preprocessing as Ott et al. (2018) and remove sentences longer than 175 words.
The IWSLT15 English-Vietnamese dataset contains approximately 133,000 sentence pairs. We follow Luong et al. (2017) and use 1,553 sentence pairs in tst2012 as the development set and 1,268 sentence pairs in tst2013 as the test set.

heading: 3.2 BASELINES
text: We compare NP2MT with two baseline models in our experiments:
• Seq2Seq-Att: a sequence to sequence model with an attention module (Bahdanau et al., 2014).
• Transformer: a state-of-the-art machine translation model based on Transformer (Vaswani et al., 2017). We use the model implemented in fairseq2 (Gehring et al., 2017b).
• NPMT: a baseline neural phrase-based machine translation model that only explicitly considers target segments (Huang et al., 2018). We use the original implementation.3
Appendix. C contains the implemenation details of the baselines and our model.

heading: 3.3 RESULTS
text: The IWSLT 2014 German-English and IWLST 2015 English-Vietnamese test results are shown in Tables 1. NP2MT achieves comparable results to Transformer (Vaswani et al., 2017), and outperforms other baselines in both datasets. NP2MT is not only better but also significantly faster than NPMT (Huang et al., 2018). The proposed dynamic programming (§ 2.3) reduces the complexity from O(STP ) in NPMT to O(TP ) in NP2MT, where S and T denote the length of source and target
2https://github.com/pytorch/fairseq 3https://github.com/posenhuang/NPMT
sentence respectively, and P is the maximum segment length. Hence it results in approximately 10 times speedup at training time (2 hours vs 24 hours on an Nvidia V100 GPU).

heading: 3.4 MEMORY-AUGMENTED TRANSLATION
text: In this subsection, we perform two experiments to understand the effectiveness of augmenting a translation model with a memory module such as a dictionary.
Rare Words We first consider a setup where for every word (for Transformer) or every phrase (for NP2MT) that appears in the training data below a certain threshold (e.g., 3 times, 5 times, etc.), we deterministically look up the translation in the dictionary instead of using the segment decoder to generate a target phrase.
We consider six lookup thresholds: 3, 5, 10, 20, 50, 100. For this experiment, we explore two ways to construct the dictionary: using in-domain dataset and out-of-domain dataset (denoted by DI and DO respectively). For the in-domain dictionaries, we have 97,399 and 84,817 entries for the IWSLT14
German-English and IWSLT15 English-Vietnamese respectively. For the German-English translation task, we construct DO from the training set of WMT14 German-English that has 1,243,722 entries.
We show the results in Table 6 and Table 4. Our experiments demonstrate that both NP2MT and Transformer benefit from the addition of a dictionary, and that the increase in performance is more significant the higher the threshold is. There is no significant difference between using the in-domain dictionary and the out-of-domain dictionary. However, we observe that when the lookup threshold is low, using a bigger dictionary (DO) is consistently better, whereas when the threshold is high DI is better.
Figure 3 shows the dictionary usage ratio as a percentage of the number of translated words (Transformer) or phrases (NP2MT). Table 3 shows the statistics on the length of the phrases on the IWSLT14 German-English data using threshold 10 model as an example. We can see that the model learns to capture phrases of various length automatically in both the source and the target side.
We show translation examples from NP2MT and lookup threshold 50 in Table 2. NP2MT discovers meaningful source phrases such as “this is”, “the machine” and “read by”.
Cross-Domain Translation In this experiment, we evaluate our best two models: Transformer and NP2MT on a cross domain machine translation task with and without memory modules. We train both models on the IWSLT14 German-English dataset (TED talks) and test them on the WMT14 German-English dataset (news articles). The goal of this experiment is to evaluate the effectiveness
of the memory module in cases when there are many out of vocabulary words in a more realistic setting. We construct a phrase dictionary using the training set of WMT14, although we do not train our models on this. Future work can explore better setups such as expert-curated dictionaries for cross-domain translation.
We show our results in Table 5. While the addition of a dictionary improves the performance of both models, a phrase-based model such as NP2MT can use this memory module more effectively, as demonstrated by a higher absolute gain (+1.25 vs. 0.91) in terms of BLEU score.

heading: 4 RELATED WORK
text: Huang et al. (2018) introduced a variant of neural phrase-based machine translation that only considers target segments. Their model builds upon Sleep-WAke Networks (SWAN), a segmentation-based sequence modeling technique described in Wang et al. (2017a), and uses a new layer to perform (soft) local reordering on input sequences.
Another related work is the segment-to-segment neural transduction model (SSNT) (Yu et al., 2016b;a). Their model assumes monotonic alignment, which is often inappropriate in many language pairs. In contrast, our model relies on a phrasal attention mechanism instead of marginalizing out monotonic alignments using dynamic programming.
There have been other works that propose different ways to incorporate phrases into attention based neural machine translation. Wang et al. (2017b), Tang et al. (2016) and Zhao et al. (2018) incorporate the phrase table as memory in neural machine translation architectures. Hasler et al. (2018) use a user-provided phrase table of terminologies into NMT system by organizing the beam search into multiple stacks corresponding to subsets of satisfied constraints as defined by FSA states. Dahlmann et al. (2017) divide the beams into the word beam and the phrase beam of fixed size. He et al. (2016) uses statistical machine translation (SMT) as features in the NMT model under the log-linear framework. Yang et al. (2018) enhance the self-attention networks to capture useful phrase patterns by imposing learned Gaussian biases. Nguyen & Joty (2018) also incorporates phrase-level attention with transformer by encoding a fixed number of n-grams (e.g. unigram, bigram). However, Nguyen & Joty (2018) only focuses on phrase-level attention on the source side, whereas our model focuses on phrase-to-phrase translation by attending on a phrase at the source side and generating a phrase at the target side. Our model further integrates an external dictionary during decoding which is important in open vocabulary and cross domain translation settings.

heading: 5 CONCLUSIONS
text: We proposed Neural Phrase-to-Phrase Machine Translation (NP2MT) that uses a phrase-level attention mechanism to enable phrase-to-phrase level translation in a neural machine translation system. We showed how to to marginalize over all possible segments at training time and presented a greedy algorithm or beam search for decoding. We also proposed to incorporate a memory module derived from an external phrase dictionary to NP2MT to improve decoding. Our experiments showed that NP2MT outperforms the best neural phrase-based translation model (Huang et al., 2018) both in
terms of model performance and speed, and is comparable to a state-of-the-art Transformer-based machine translation system (Vaswani et al., 2017).

heading: B GERMAN-ENGLISH TRANSLATION WITH IN-DOMAIN AND OUT-OF-DOMAIN DICTIONARIES
text: C IMPLEMENTATION DETAILS
Seq2Seq-Attention We use the model architectures and results reported in Huang et al. (2018) as the baselines for Seq2Seq with attention. The Seq2Seq with attention baselines they built consist of a 2-layer BiGRU encoder with 256 hidden units and a 2-layer GRU decoder with 512 hidden units for the IWSLT14 German-English dataset, and a 2-layer BiLSTM encoder with 512 hidden units and a 3-layer LSTM decoder with 512 hidden units 4 for the IWSLT15 English-Vietnamese dataset. Adam algorithm Kingma & Ba (2014) is used for optimization with an initial learning rate of 1e−3.
NPMT We also use the model architectures and results reported in Huang et al. (2018) for the NPMT baseline. The NPMT models consist of a reordering layer, a 2-layer BiGRU encoder with 256 hidden units and a 2-layer GRU decoder with 512 hidden units for the IWSLT14 German-English dataset, and a reordering layer, a 2-layer BiLSTM encoder with 512 hidden units and a 3-layer LSTM decoder with 512 hidden units for the IWSLT15 English-Vietnamese dataset. The models are optimized using the Adam algorithm with an initial learning rate of 1e−3.
Transformer We set the number of layers in both encoder and decoder to 6. Our preliminary experiments suggest that increasing the number of layers does not improve performance further.
We use Adam (Kingma & Ba, 2014) as our optimization method and search the best hyperparameters using a validation set. We use a three-stage learning rate scheduler by replacing the exponential decay with a linear one for fast convergence, similar to the RNMT+ learning rate scheduler (Chen et al., 2018; Ott et al., 2018). Specifically, our learning rate is quickly warmed up to the maximum, kept at the maximum value until 50% training iterations, and is then decayed to zero. The maximum learning rate of Transformer is set to 2e−4.
NP2MT We use 6-layer BiLSTMs to encode at both words and segment level in the source encoder, 6-layer LSTMs as the target encoder, and a 6-layer transformer as the segment decoder.5 We also use Adam (Kingma & Ba, 2014) as our optimization method. We set the word embedding dimension to 256 In our experiments, we set the maximum learning rate to 1e−3, weight decay to 1e−4, and the dropout rate to 0.4. We set the word embedding dimension to 256. For 6 layer encoder/decoder, NP2MT and Transformer use ∼42M and ∼75M parameters, respectively.
4In our preliminary experiments, we reran the NPMT open source code. We found the NPMT doesn’t improve with deeper layers.
5We also experiment on LSTM segment decoder variant, but the performance is inferior.

Review summaries:
This paper presents a phrase-based encoder-decoder model for machine translation. The encoder considers all possible phrases (i.e. word sequences) up to a certain length and compute phrase representations using bidirectional LSTMs from contextual word embeddings computed with another bidirectional LSTM layer. The decoder also considers possible segmentations and computes contextual representations for the previously generated segments. Each word in the current segment is generated by a Transformer model by attending to all phrases in the source sentence. The authors present a dynamic programming method for considering all possible segmentations in decoding. They also present a method for incorporating a phrase-to-phrase dictionary built by Moses into the decoding process.