Insertion-based Decoding with Automatically Inferred Generation Order

Insertion-based Decoding with Automatically Inferred Generation Order Jiatao Gu†, Qi Liu⋄∗, and Kyunghyun Cho‡† †Facebook AI Research ⋄University of Oxford ‡New York University, CIFAR Azrieli Global Scholar †{jgu, kyunghyuncho}@fb.com ‡qi.liu@st-hughs.ox.ac.uk Abstract Conventional neural autoregressive decoding commonly assumes a fixed left-to-right gener- ation order, which may be sub-optimal. In this work,wepropose a novel decoding algorithm— InDIGO—which supports flexible sequence generation in arbitrary orders throughinsertion operations. We extend Transformer, a state- of-the-art sequence generation model, to effi- ciently implement the proposed approach, enabling it to be trained with either a pre- defined generation order or adaptive orders obtained from beam-search. Experiments on four real-world tasks, including word order recovery, machine translation, image caption, and code generation, demonstrate that our algorithm can generate sequences following arbitrary orders, while achieving competitive or even better performance compared with the conventional left-to-right generation. The generated sequences show that InDIGO adopts adaptive generation orders based on input information. 1 Introduction Neural autoregressive models have become the de facto standard in a wide range of sequence generation tasks, such as machine translation (Bahdanau et al., 2015), summarization (Rush et al., 2015), and dialogue systems (Vinyals and Le, 2015). In these studies, a sequence is modeled autoregressively with the left-to-right generation order, which raises the question of whether gen- eration in an arbitrary order is worth considering ∗This work was completed while the author worked as an AI resident at Facebook AI Research. (Vinyals et al., 2016; Ford et al., 2018). Nev- ertheless, previous studies on generation orders mostly resort to a fixed set of generation orders, showing particular choices of ordering are help- ful (Wu et al., 2018; Ford et al., 2018; Mehri and Sigal, 2018), without providing an efficient algorithm for finding adaptive generation orders, or restrict the problem scope to n-gram segment generation (Vinyals et al., 2016). In this paper, we propose a novel decoding al- gorithm, Insertion-based Decoding with Inferred Generation Order(InDIGO), which models gener- ation orders as latent variables and automatically infers the generation orders by simultaneously pre- dicting a word and its position to be inserted ateach decoding step. Given that absolute positions are unknown before generating the whole sequence, we use a relative-position-based representation to capture generation orders. We show that de- coding consists of a series of insertion operations with a demonstration shown in Figure 1. We extend Transformer (Vaswani et al., 2017) for supporting insertion operations, where the generation order is directly captured as relative positions through self-attention inspired by Shaw et al. (2018). For learning, we maximize the evidence lower-bound (ELBO) of the maxi- mum likelihood objective, and study two ap- proximate posterior distributions of generation orders based on a pre-defined generation order and adaptive orders obtained from beam-search, respectively. Experimental results on word order recov- ery, machine translation, code generation, and image caption demonstrate that our algorithm can generate sequences with arbitrary orders, while achieving competitive or even better performance compared to the conventional left-to-right genera- tion. Case studies show that the proposed method adopts adaptive orders based …

Content truncated to 500 words