An Empirical Study of Generation Order for Machine Translation (2020)

Abstract: In this work, we present an empirical study of generation order for machine translation. Building on recent advances in insertion-based modeling, we first introduce a soft order-reward framework that enables us to train models to follow arbitrary oracle generation policies. We then make use of this framework to explore a large variety of generation orders, including uninformed orders, location-based orders, frequency-based orders, content-based orders, and model-based orders. Curiously, we find that for the WMT’14 English \to German and WMT’18 English \to Chinese translation tasks, order does not have a substantial impact on output quality. Moreover, for English \to German, we even discover that unintuitive orderings such as alphabetical and shortest-first can match the performance of a standard Transformer, suggesting that traditional left-to-right generation may not be necessary to achieve high performance.

## introduction neural sequence models @xcite have been successfully applied to a broad range of tasks in recent years. while these models typically generate their outputs using a fixed left-to-right order, there has also been some investigation into non-left-to-right and order-independent generation in pursuit of quality or speed. for example, @xcite explored the problem of predicting sets using sequence models. while this is a domain where generation order should intuitively be unimportant, they nevertheless found it to make a substantial difference in practice. @xcite explored treating language modeling as a two-pass process, where words from certain classes are generated first, and the remaining words are filled * equal contribution. in during the second pass. they found that generating function words first followed by content words second yielded the best results. separately, @xcite and @xcite developed non-autoregressive approaches to machine translation where the entire output can be generated in parallel in constant time. these models do away with order selection altogether but typically lag behind their autoregressive counterparts in translation quality. more recently, a number of novel insertionbased architectures have been developed for sequence generation @xcite @xcite . these frameworks license a diverse set of generation orders, including uniform @xcite , random @xcite , or balanced binary trees @xcite . some of them also match the quality of state-ofthe-art left-to-right models @xcite . in this paper, we utilize one such framework to explore an extensive collection of generation orders, evaluating them on the wmt'14 english-german and wmt'18 english-chinese translation tasks. we find that a number of non-standard choices achieve bleu scores comparable to those obtained with the classical approach, suggesting that left-to-right generation might not be a necessary ingredient for high-quality translation. our contributions are as follows: on the competitive wmt 2014 @xmath0, we encoder 那个 男人 吃 了 小吃 embedding self-attention decoder start ate snack end {the, man} {a} {} embedding self-attention + cross-attention content and location softmaxes figure 1: a schematic of the insertion transformer model for a chinese-english translation pair. the model is encouraged to predict the correct set of remaining words within each slot. using our order-reward framework (section 3), we can derive the necessary weight distribution to apply to the set of correct actions in order to train the model to follow any oracle generation policy of interest. serial generation: hypothesis insertion [] (ate, 0) [ate] (snack, 1) [ate, snack] (man, 0) [man, ate, snack] (the, 0) [the, man, ate, snack] (a, 3) [the, man, ate, a, snack] ( eos , 5) parallel generation: hypothesis insertions [] (ate, 0) [ate] ## background neural sequence models have traditionally been designed with left-to-right prediction in mind. in the classical setting, output sequences are produced by repeatedly appending tokens to the rightmost end of the hypothesis until an endof-sequence token is generated. though highperforming across a wide range of application areas, this approach lacks the flexibility to accommodate other types of inference such as parallel generation, constrained decoding, infilling, etc. moreover, it also leaves open the possibility that a non-left-to-right factorization of the joint distribution over output sequences could outperform the usual monotonic ordering. to address these concerns, several recent approaches have been proposed for insertion-based sequence modeling, in which sequences are constructed by repeatedly inserting tokens at arbitrary locations in the output rather than only at the right-most position. we use one such insertion-based model, the insertion transformer @xcite , for our empirical study. we give a brief overview of the model in this section before moving on to the details of our investigation. ## soft order-reward framework having presented our model of interest, we now describe a general soft order-reward framework that can be used to train the model to follow any oracle ordering for sequence generation. let o(a) be an order function mapping insertion actions to real numbers, where lower values correspond to better actions, and let p(a) be the probability assigned by the model to action a. from these, we construct a reward function r(a), an oracle policy q oracle , and a per-slot loss l: here, a * is the set of all valid actions. the temperature τ ∈ (0, ∞) controls the sharpness of the distribution, where τ → 0 results in a one-hot distribution with all mass on the best-scoring action under the order function o(a), and τ → ∞ results in a uniform distribution over all valid actions. intermediate values of τ result in distributions which are biased towards better-scoring actions but allow for other valid actions to be taken some of the time. having defined the target distribution, we take the slot loss l for insertions within a particular slot to be the kl-divergence between the oracle distribution q oracle and the model distribution p. substituting l in for the slot loss within the training framework of @xcite then gives the full sequence generation loss, which we can use to train an insertion transformer under any oracle policy rather than just the specific one they propose. we describe a wide variety of generation orders which can be characterized by different order functions o(a) in the subsections that follow. a summary is given in ## experiments for our experiments, we train and evaluate models for each order on two standard machine translation datasets: wmt14 en-de and wmt18 en-zh. for wmt14 en-de, we follow the standard setup with newstest2013 as our development set and newstest2014 as our test set. for wmt18 en-zh, we use the official preprocessed data 1 with no additional data normalization or filtering, taking newstest2017 to be our development set and new-stest2018 our test set. en-zh evaluation is carried 1 http://data.statmt.org/wmt18/ translation-task/preprocessed/zh-en/ input: imagine eating enough peanuts to serve as your dinner . ## related work in recent work, several insertion-based frameworks have been proposed for the generation of sequences in a non-left-to-right fashion for machine translation @xcite @xcite . @xcite introduced the insertion transformer and explored uniform and balanced binary tree orders. we built upon and generalized this approach in order to explore a much broader set of orders. @xcite explored insertions using a binary-tree formulation. they also explored uniform and model-based orders, but found them to lag significantly behind their left-to-right baselines. additionally, despite using a binary-tree formulation for generation, they did not explore tree-based orders. @xcite introduced a model which did not explicitly represent the output canvas arising from insertions, but rather used an implicit representation through conditioning on the insertion sequence. they also performed an exploration of different generation orders, including random, odd-even, common-first, rare-first, and a search-adaptive order. their search-adaptive order can be seen as a global version of our local model adaptive order, where we use the local greedy posterior as the reward function, and they use the sequence level log-probability as the reward function. curiously, in their framework, the random order fell significantly behind the left-to-right baseline, while they showed small gains in their search adaptive order. one key difference between our work @xcite and @xcite is that we use a soft order-reward framework as opposed to teacher forcing. this might explain some of the performance differences, as our framework allows for a more flexible training objective. additionally, since we use a uniform roll-in policy, our models may have less of a label bias problem, as they are trained to be able to continue from any partial output rather than just those arising from the target policy. ## conclusion in this work, we investigated a broad array of generation orders for machine translation using an insertion-based sequence generation model, the insertion transformer. we found that regardless of the type of strategy selected, be it locationbased, frequency-based, length-based, alphabetical, model-based, or even random, the insertion transformer is able to learn it with high fidelity and produce high-quality output in the selected order. this opens a wide range of possibilities for generation tasks where monotonic orderings are not the most natural choice, and we would be excited to explore some of these areas in future work.