Learning and Analyzing Generation Order for Undirected Sequence Models (2021)

Abstract: Undirected neural sequence models have achieved performance competitive with the state-of-the-art directed sequence models that generate monotonically from left to right in machine translation tasks. In this work, we train a policy that learns the generation order for a pre-trained, undirected translation model via reinforcement learning. We show that the translations decoded by our learned orders achieve higher BLEU scores than the outputs decoded from left to right or decoded by the learned order from Mansimov et al. (2019) on the WMT’14 German-English translation task. On examples with a maximum source and target length of 30 from De-En and WMT’16 English-Romanian tasks, our learned order outperforms all heuristic generation orders on three out of four language pairs. We next carefully analyze the learned order patterns via qualitative and quantitative analysis. We show that our policy generally follows an outer-to-inner order, predicting the left-most and right-most positions first, and then moving toward the middle while skipping less important words at the beginning. Furthermore, the policy usually predicts positions for a single syntactic constituent structure in consecutive steps. We believe our findings could provide more insights on the mechanism of undirected generation models and encourage further research in this direction.

## introduction directed neural sequence models such as the transformer @xcite with causal selfattention masks have been widely used for language generation tasks like machine translation and summarization. in such models, each token only depends on the left context and thus they can be naturally applied in the monotonic left-to-right generation scheme. on the other hand, in the undirected sequence models such as the transformer without the causal mask, each token depends on the full left and right context. the application of an undirected sequence model in language generation is not straightforward, as it can simply peek into the future for the target token if trained in the same way as a directed model. to circumvent this problem, previous works @xcite trained undirected transformer models using the masked language modeling (mlm) @xcite objective with the masking ratio randomly varying in the range of (0%, 100%]. at test time, the model first predicts the length t of the sequence to be generated and begins with a sequence of t mask tokens. then, at each step, the model selects one or more positions to update, masks the original tokens at those positions, and predicts the target tokens to replace the original ones there. however, how to select this order of tokens to update throughout the process still remains an open and interesting question for the research community. in this work, we study this question in a focused setting where the model can only replace one mask token per step for t steps. 2 under this linear-time decoding setup, we can easily compare the generation model's behaviors when decoding in different orders. previously, @xcite designed and bench-marked various heuristic orders under this setting. they further built and trained a policy network with reinforcement learning (rl) to predict the target generation order for the pretrained masked language model dynamically for each example. we aim to learn better generation orders by improving upon the previous rl objective. first, instead of using the change in the edit distance between the partially generated sequence and the ground-truth sequence as the reward func-tion for the order policy, we directly use the bleu scores of the ultimate sequence generated in the order sampled from the policy network as the reward because edit distance is too rigid and evaluates a sequence as individual tokens instead of n-grams, and thus cannot reflect the actual quality of a generated sequence order. furthermore, on the de-→en task, the learned policy by @xcite either follows the left-to-right order or generates the final punctuation first and then proceeds from left to right in around 75% of the generations. therefore, this might indicate that the policy converges prematurely to the left-to-right order which is a strong local optimum. and hence, to encourage the policy to better explore the entire action space instead of putting all weights on one position at every step too early, we add a negative entropy penalty to the policy's output distribution. when sampling an order during the training, a larger entropy means that the policy can explore and evaluate more possible orders and hence lead to a better policy ultimately. on the wmt14' english↔german translation tasks, using the same pre-trained undirected transformer fixed during the learning of the policy, the sequences decoded in the orders predicted by our policy receive higher bleu scores than the outputs decoded in the order learned in the previous work @xcite . on the de-→en task, our learned order also beats the left2right baseline on the test set. on the wmt16' romanian-→english task, our learned order again outperforms the left2right order and is competitive with the best heuristic easy-first order. moreover, our learned policy performs strongly when trained and evaluated on examples with the source and target shorter than 31 tokens, outperforming all heuristic generation orders (uniform, left2right, easy-first, least2most) on the dev sets of wmt14' en↔de and wmt16' ro-→en tasks. therefore, while our learned policy achieves the best overall scores on more than 2/3 of all en↔de examples and 1/2 of all ro-→en examples, it is expectedly harder for the policy to learn an optimal order on the remaining very long sequences, which is an interesting direction for future works. next, we focus on a detailed and important qualitative analysis (and human study) to reveal that, interestingly, our policy in general follows an outerto-inner order, predicting the left-most and rightmost positions first and move toward the middle. in ## background directed sequence generation models. most generation models nowadays are directed as they are trained and decode exclusively from left to right. the widely-used transformer @xcite decoder employs a causal self-attention layer to mask out the attention to the future tokens during the training. at the test time, the decoder takes the previously generated tokens as the input and predicts the next token from left to right. ## methods in this section, we introduce our policy network (sec. 3.1) that predicts the generation order for a pre-trained conditional mlm and our reinforcement learning (rl) objective (sec. 3.2). we visualize our models and the rl procedure in fig. 1 . ## analysis studies generation using undirected sequence model has been an under-explored area compared to the conventional directed generation. there are few studies that analyze the mechanism of this process and its difference with directed sequence generation. hence, to shed some light on the order preferences developed by the model when trained with conditional masked language modeling, we present multiple qualitative and quantitative analyses on our learned generation orders and try to understand what causes the model to adapt such orders. ## conclusion in this work, we train a policy network with reinforcement learning to predict the generation order for an undirected sequence models. it outperforms the left2right orders and previous learned orders on the de-→en task. when trained and evaluated on examples with source and target sequences of length 30 or less, our learned order receives the highest bleu scores compared to all heuristic orders on three translation tasks. we show that our learned policy follows an outer-to-inner order and skips some less important words at first. moreover, it usually completes an entire constituent in consecutive steps. we hope our results and analyses could provide insights on undirected generation models and encourage future works on this topic.