Sequence Generation: From Both Sides to the Middle

1 Introduction

The neural encoder-decoder framework has been widely adopted in sequence generation tasks, including neural machine translation (NMT) [Sutskever et al., 2014; Bahdanau et al., 2015; Vaswani et al., 2017], text summarization [Rush et al., 2015; Zhou et al., 2017; Li et al., 2018], and image captioning [Xu et al., 2015; Vinyals et al., 2015]. In this framework, the encoder models the semantics of the input sentence and transforms it into a context vector representation, which is then fed into the decoder to generate the output sequence token by token in a left-to-right manner.

Although the framework has obtained great success, the sequence-to-sequence model suffers from the decoding efficiency problem [Gu et al., 2017]. Most of the models use autoregressive decoders that operate one step at a time, and they become slow when generating long sequences because a computationally intensive neural network is used to predict each token. Several recently proposed models avoid recurrence at training time by leveraging convolutions [Gehring et al., 2017] or self-attention [Vaswani et al., 2017] as moreparallelizable alternatives to recurrent neural networks, but the decoding process cannot share the speed strength of parallelization due to the autoregressive generation schema in the decoder. More importantly, this left-to-right decoding cannot take advantage of future contexts which can be generated in a right-to-left decoding [Zhang et al., 2018b].

To avoid this autoregressive property, Gu et al. [2017] proposed a non-autoregressive model to speed up machine translation by directly generating target words without relying on any previous predictions. Oord et al. [2017] modified a convolutional network for non-autoregressive modeling of speech synthesis. Lee et al. [2018] introduced a conditional non-autoregressive neural sequence model based on iterative refinement. However, in spite of their improvement in decoding speed, non-autoregressive models typically suffer from the substantial drop in generation quality.

In this paper, we propose a synchronous bidirectional sequence generation (SBSG) model to achieve a better improvement on both generation quality and decoding speed. Instead of producing output sentences token by token or predicting its outputs in a totally parallel manner, the SBSG model generates two tokens at a time. As shown in Figure 1, the bidirectional decoder can generate output sentences from both sides to the middle with both left-to-right (L2R) and right-to-left (R2L) directions. Furthermore, we introduce an interactive bidirectional attention network to bridge L2R and R2L outputs. More specifically, at each moment, the generation of target-side tokens does not only rely on its previously generated outputs (history information), but also depends on previously predicted tokens of the other generation direction (future information).

Specifically, the contributions of this paper can be summarized as two folds:

• We propose a novel SBSG model that employs one decoder to predict outputs from both sides to the middle simultaneously and interactively. To the best of our knowledge, this is the first work to perform sequence generation from both ends to the middle.
• We extensively evaluate the proposed model on typical sequence generation tasks, namely neural machine translation and text summarization. In the case of machine translation, we not only obtain approximately 1.4× (1.5×) speedup for decoding than autoregressive Transformer with beam search (greedy search), but also get an improvement of 0.39 (0.99), 1.26 (2.87) and 0.73 (1.11) BLEU points of translation quality in WMT14 En⇒De, NIST Ch⇒En and WMT16 En⇒Ro respectively, which also significantly outperforms previous non-autoregressive models [Gu et al., 2017; Lee et al., 2018; Kaiser et al., 2018]. For text summarization, the proposed model is able to decode approximately 1.5× faster while achieving better generation quality relative to the autoregressive counterparts.

2 RelatedWork

Autoregressive Decoding. Recent approaches to sequence to sequence learning typically leverage recurrence [Sutskever et al., 2014], convolution [Gehring et al., 2017], or selfattention [Vaswani et al., 2017] as basic building blocks. Particularly, relying entirely on the attention mechanism, the Transformer introduced by Vaswani et al. [2017] can improve the training speed as well as model performance. To accelerate autoregressive architecture, Mi et al. [2016] introduced a sentence-level vocabulary which is able to reduce computing time and memory usage. Devlin [2017] focused on fast and accurate neural machine translation decoding in CPU. Zhang et al. [2018a] proposed an average attention network (AAN) as an alternative to the self-attention network in the decoder of Transformer. Despite their remarkable success, they are difficult to parallelize and this unidirectional decoding framework limits its potential [Liu et al., 2016a].

Non-Autoregressive Decoding. In terms of speeding up the decoding of the neural Transformer, Gu et al. [2017] modified the autoregressive architecture to speed up machine translation by directly generating target words in parallel. However, the main drawback of this work is the need for extensive policy gradient fine-turning techniques, as well as the issue that this method only works for machine translation and cannot be applied to other sequence generation tasks. In parallel to Gu et al. [2017], Oord et al. [2017] presented a successful, non-autoregressive sequence model for speech waveform. Besides, Kaiser et al. [2018] first auto-encoded the target sequence into a shorter sequence of discrete latent variables, and then decoded the output sentence from this shorter latent sequence in parallel. Lee et al. [2018] introduced a conditional non-autoregressive neural sequence model based on iterative refinement. Concurrently to our work, Wang et al. [2018] presented a semi-autoregressive Transformer for faster translation without changing the autoregressive property in global. However, these approaches improved the parallelizability but significantly reduced generation quality.

Towards Bidirectional Decoding. Liu et al. [2016a] proposed an agreement model to encourage the agreement between a pair of target-directional LSTMs, which generated more balanced targets. Similarly, some work attempted at target-bidirectional decoding for SMT or NMT [Watanabe and Sumita, 2002; Finch and Sumita, 2009; Liu et al., 2016b; Sennrich et al., 2016a; Liu et al., 2018]. Recently, Zhang et al. [2018b] and Zhou et al. [2019] proposed an asynchronous and synchronous bidirectional decoding for NMT, respectively. Serdyuk et al. [2018] presented the twin networks to encourage the hidden state of the forward network to be close to that of the backward network used to predict the same token. Nevertheless, the above studies are not to speed up the decoding procedure, and even sacrifice speed in exchange for quality improvement. Our work differs from those by introducing a novel sequence generation model which aims at taking full advantage of both left-to-right and right-to-left decoding to accelerate and improve sequence generation.

3 The Framework

Our goal in this work is to achieve a better improvement on both generation quality and decoding speed. We introduce a novel method for decoding with both left-to-right and rightto-left manners simultaneously and interactively in a unified model. As demonstrated in Figure 2, our proposed model consists of an encoder and a bidirectional decoder, in which two special labels (〈l2r〉 and 〈r2l〉) at the beginning of output sentence are utilized to guide the sequence generation from left to right or right to left. The bidirectional decoder reads the encoder representation and generates two output tokens at each time step, by using interactive bidirectional attention networks. Next, we will detail individual components and introduce an algorithm for training and inference.

3.1 The Neural Encoder

Given an input sentence x = (x1, x2, ..., xm), the new Transformer leverages its encoder to induce input-side semantic and dependencies so as to enable its decoder to recover the encoded information in an output sentence. The encoder is composed of a stack of N identical layers, each of which has two sub-layers:

where the superscript l indicates layer depth, LN is layer normalization, FFN means feed-forward networks, and MHAtt denotes the multi-head attention mechanism as follows.

Scaled Dot-Product Attention. An attention function can be described as mapping a query and a set of key-value pairs to an output. The output is computed as a weighted sum of the values, where the weight assigned to each value is computed by a compatibility function of the query and the corresponding key. Scaled dot-product attention operates on a query Q, key K, and a value V as:

where dk is the dimension of the key.

Multi-HeadAttention. We use themulti-head versionwith h heads. It obtains h different representations of (Q,K, V ), computes scaled dot-product attention for each representation, concatenates the results, and projects the concatenation with a feed-forward layer.

where W Q i , W K i , W V i andW O are parameter matrices.

3.2 The Bidirectional Decoder

The bidirectional decoder performs decoding in both left-toright and right-to-left manners under the guidance of previously generated forward and backward outputs. We apply our bidirectional attention network to replace the self-attention network in its decoder part, and illustrate the overall architecture in Figure 2. Next, we will present those two bidirectional attention models and integrate them into the decoder of Transformer.

Bidirectional Scaled Dot-Product Attention

Figure 3 (left) shows our particular attention. The input consists of queries ([-→Q;←- Q]), keys ([-→K;←- K]) and values ([-→V ;←- V ]) which are all concatenated by forward (L2R) states and backward (R2L) states. The new forward states -→Hj and backward states ←- Hj can be obtained by bidirectional dot-product scaled attention. For new forward states -→Hj , it can be calculated as:

where -→H fj is obtained by conventional scaled dot-product attention as introduced in Equation 2, and -→H bj contains the attentional future information from R2L decoding. Then we use a linear interpolation method to integrate the forward information -→H fj and backward information -→H bj :

where λ is a hyper-parameter decided by the performance on development set.

For R2L decoding, similar to the calculation of forward hidden states -→H j , the backward hidden states ←- Hj can be computed as follows.←-

where Integration(·) is the same as introduced in Equation 5. We refer to the whole procedure formulated in Equation 4-6 as BSDPA(·).

It is worth noting that -→Hj and ←- Hj can improve each other and be calculated in parallel.

Bidirectional Multi-Head Intra-Attention

Different from the mask multi-head attention (Equation 3), we can obtain the new forward and backward hidden states simultaneously, as shown in Figure 3 (right), where i-th attention head with j-th target token can be computed using BSDPA(·):

where W Q i , W K i and W V i are parameter matrices, which are the same as standard multi-head attention introduced in Equation 3. By contrast, bidirectional multi-head inter-attention is composed of two standard multi-head attention models, which do not interact with each other.

Integrating Bidirectional Attention into Decoder

We use our bidirectional attention network to replace the multi-head attention in the decoder part, as demonstrated in Figure 2. For each layer in bidirectional decoder, the first sub-layer is the bidirectional multi-head intra-attention

(BiAttIntra ) network 1 which is capable of combining history and future information:

where sl denotes l-layer hidden states or embedding vectors when l=0, and subscript d denotes the decoder-informed intra-attention representation.

The second sub-layer is the bidirectional multi-head inter-attention (BiAttInter ) which integrates the representation of the corresponding source sentence by performing leftto-right and right-to-left decoding attention respectively, as shown in Figure 2.

where e denotes the encoder-informed inter-attention representation, and hN is the source hidden state of top layer.

The third sub-layer is a position-wise fully connected feedforward neural network: [-→s l ; ←-s l ] = FFN([-→s le ; ←-s le ]).

Finally, we employ a linear transformation and softmax activation to compute the probability of the j-th tokens based on N-layer sNj = [-→s Nj ; ←-s Nj ], namely the final hidden states of forward and backward decoding.

where W denotes the weight matrix and θ is the shared parameters for L2R and R2L decoding.

3.3 Training and Inference

Training. Given a parallel sentence pair (x, y), we design a smart strategy to enable synchronous bidirectional generation within a decoder. We first divide the output sentence (y) into two halves and reverse the second half. Second, we separately add the special labels (〈l2r〉 and 〈r2l〉) at the beginning of each half sentence (-→y and ←-y ) to guide generating tokens from left to right or right to left. Finally, we propose a smoothing model to better connect both directional generational results. As shown in Figure 4, if the output length is odd, we add the additional tag (〈null〉) before 〈eos〉 in forward or backward sentence randomly. In other words, our model is capable of generating a null word when necessary. Following previous work [Gu et al., 2017; Wang et al., 2018], we also use knowledge distillation techniques [Kim and Rush, 2016] to train our model. Given a set of training examples {x(z) , y(z) }Zz=1 , the training algorithm aims to find the model parameters that maximize the likelihood of the training data:

1 Note that we follow Vaswani et al. [Vaswani et al., 2017] to use residual connection and layer normalization in each decoder sublayer, which are omitted in the presentation for simplicity.

Inference. Once the proposed model is trained, we employ a simple bidirectional beam search algorithm to predict the output sequence. As illustrated in Figure 5, with two special start tokens which are optimized during the training process, we let half of the beam to keep decoding from left to right, and allow the other half beam to decode from right to left. The blue blocks denote the ongoing expansion of the hypothesis and decoding terminates when the end-of-sentence flag is predicted. More importantly, by using the bidirectional multihead intra-attention, the two decoding manners can help and interact with each other in one beam-search process. Alternatively, we can also use greedy search to our model.

4 Application to Neural Machine Translation

We use BLEU [Papineni et al., 2002] to evaluate the proposed model on translation tasks.

4.1 Setup

We verify our model on three translation datasets of different sizes: WMT14 English-German 2 (En⇒De), NIST ChineseEnglish 3 (Ch⇒En), WMT16 English-Romanian 4 (En⇒Ro), whose training sets consist of 4.5M, 2.0M, 0.6M sentence pairs, respectively. We tokenize the corpora using a script fromMoses [Koehn et al., 2007] and segment each word into subword units using BPE [Sennrich et al., 2016b]. We use 37K and 40K shared BPE tokens for En⇒De and En⇒Ro respectively. For En⇒De, we use newstest2013 as the validation set and newstest2014 as the test set. For Ch⇒En, we utilize BPE to encode Chinese and English respectively, and limit the source and target vocabularies to the most frequent 30K tokens. We use NIST 2006 as the validation set, NIST

2 http://www.statmt.org/wmt14/translation-task.html

3 The corpora include LDC2000T50, LDC2002T01, LDC2002E18, LDC2003E07, LDC2003E14, LDC2003T17 and LDC2004T07.

4 http://www.statmt.org/wmt16/translation-task.html

2003-2005 as our test sets. For En⇒Ro, we use newsdev2016 and newstest-2016 as development and test sets.

We implement the proposed model based on the tensor2tensor 5 toolkit. For our bidirectional Transformer model, we employ the Adam optimizer with β1=0.9, β2=0.998, and ϵ=10-9 . We use the same warmup and decay strategy for learning rate as Vaswani et al. [2017] , with 16,000 warmup steps. During training, we employ label smoothing of value ϵls=0.1. We use three GPUs to train En⇒De and one GPU for the other two language pairs. For evaluation, we use beam search with a beam size of k=4 and length penalty α=0.6. Besides, we use 6 encoder and decoder layers, 512 hidden size, 8 attention-heads, 2048 feed-forward inner-layer dimensions.

4.2 Results and Analysis

Parameters. NAT [Gu et al., 2017] adopts encoder-decoder architecture with additional fertility predictor model. DNAT [Lee et al., 2018] has two decoders and needs more parameters than conventional Transformer. Our bidirectional NMT model uses one single encoder-decoder model, which can predict the target tokens in left-to-right and right-to-left manners simultaneously. Hence, our SBSG model does not increase any parameters except for a hyper-parameter λ compared to the standard Transformer.

Inference Speed. As shown in Table 1, the proposed SBSG model is capable of decoding approximately 1.4× faster than autoregressive Transformer with beam search in three translation tasks. Besides, our model obtains 1.61× (En⇒De), 1.51× (Ch⇒En), and 1.46× (En⇒Ro) speedup than Transformer in greedy search. As a compromise solution between autoregressive and non-autoregressive models, the speed of our model is relatively slower than NAT, D-NAT, and LT [Kaiser et al., 2018]. Besides, our proposed model is capable of obtaining comparable translation speed compared to SAT [Wang et al., 2018] with K=2.

5 https://github.com/tensorflow/tensor2tensor

Translation Quality. Table 1 shows translation performance of En⇒De, Ch⇒En, and En⇒Ro translation tasks. The proposed model behaves better than NAT, D-NAT, LT in all test datasets. In particular, our model with beam search significantly outperforms NAT, D-NAT, and LT by 8.28, 8.54 and 4.95 BLEU points in large-scale English-German translation, respectively. Although the SAT has a faster decoding speed than the SBSG model when K becomes bigger, it suffers from the translation quality degradation relative to the autoregressive NMT. Compared to autoregressive Transformer, our proposed model with beam search is able to behave better in terms of both decoding speed and translation quality. Furthermore, our model with greedy search does not only outperform autoregressive Transformer by 0.99, 2.87 and 1.11 BLEU points of translation quality in En⇒De, Ch⇒En and En⇒Ro respectively, but also significantly speedups the decoding of conventional Transformer.

Length Analysis. We follow Bahdanau et al. [2015] to group sentences of similar lengths together, and compute a BLEU score and the averaged length of translations per group. Figure 6 shows that the performance of Transformer and Transformer (R2L) drops rapidly when the length of the input sentence increases. Our SBSG model alleviates this problem by generating a sequence from both sides to the middle, which in general encourages the model to produce more accurate and long sentences.

Case Study. In Table 2, we present a translation example from NIST Chinese-English. Liu et al. [2016b] show that L2R model produces the translation with good prefix and sometimes omits the second half sentence, but L2R model usually generates the generation with better suffixes. Our results confirm these findings. The proposed SBSG model can alleviate the errors by generating sequences from both sides to the middle.

5 Application to Text Summarization

We further verify the effectiveness of our proposed SBSG model on text summarization, which is another real-world application that encoder-decoder framework succeeds [Rush et al., 2015].

5.1 Setup

Abstractive sentence summarization aims to provide a titlelike summary for a long sentence. We conduct text summarization experiments on English Gigaword dataset 6 . The parallel corpus is produced by pairing the first sentence and the headline in the news article with some heuristic rules. The extracted corpus contains about 3.8M sentence-summary pairs for the training set and 189K examples for the development set. We employ a shared vocabulary of about 90K word types and use DUC 2004 used by Rush et al. [2015] as our test set. The model structure is the same as that used in neural machine translation. We employ ROUGE as our evaluation metric, which is all widely adopted evaluation metric for text summarization.

6 https://github.com/harvardnlp/sent-summary

5.2 Results and Analysis

In Table 3, we report the ROUGE score and speed for DUC 2004 test set. Experiments show that the generation quality of our proposed model is on par with the state-of-the-art text summarization models. We observe approximately 1.5× faster decoding than the autoregressive Transformer while achieving better generation quality. Specially, our model with beam search (greedy search) is capable of decoding 1.64× (2.26×) faster than conventional Transformer on English Gigaword test set.

6 Conclusions

In this work, we propose a novel SBSG model that performs bidirectional decoding simultaneously and interactively. Instead of producing output sentence token by token, the proposed model makes decoding much more parallelizable and generates two tokens at each time step. We extensively evaluate the proposed SBSG model on neural machine translation (En⇒De, Ch⇒En, and En⇒Ro) and text summarization (English Gigaword) tasks. Different from previous nonautoregressive models [Gu et al., 2017; Lee et al., 2018; Kaiser et al., 2018] which suffer from serious quality degradation, our SBSG model achieves a significant improvement in both generation quality and decoding speed compared to the state-of-the-art autoregressive Transformer.

Acknowledgments

The research work described in this paper has been funded by the National Key Research and Development Program of China under Grant No. 2016QY02D0303 and the Natural Science Foundation of China under Grant No. U1836221 and 61673380. This work is also supported by grants from NVIDIA NVAIL program.