Non-Monotonic Sequential Text Generation

By Sean Welleck, Kianté Brantley, Hal Daumé Iii, Kyunghyun Cho. 2019

143 citations recorded by the source corpus.

Standard sequential generation methods assume a pre-specified generation order, such as text generation methods which generate words from left to right. In this work, we propose a framework for training models of text generation that operate in non-monotonic orders; the model directly learns good orders, without any additional annotation. Our framework operates by generating a word at an arbitrary position, and then recursively generating words to its left and then words to its right, yielding a binary tree. Learning is framed as imitation learning, including a coaching method which moves from imitating an oracle to reinforcing the policy’s own preferences. Experimental results demonstrate that using the proposed method, it is possible to learn policies which generate text without pre-specifying a generation order while achieving competitive performance with conventional left-to-right generation.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Natural Language Processing

Citations in the corpus

How Decoding Strategies Affect the Verifiability of Generated Text (2019, background): “Given that recent studies (Fan et al., 2018; Holtzman et al., 2019; Welleck et al., 2019) point to repetitiveness as one of the main problems affecting the generation of state-of-the-art models, we mainly consider this dimension in our analysis.”
Language Models as Knowledge Bases? (2019, background): “…a multi-layer perceptron (Bengio et al., 2003; Mikolov and Zweig, 2012), convolutional layers (Dauphin et al., 2017), recurrent neural networks (Zaremba et al., 2014; Merity et al., 2016; Melis et al., 2017) or self-attention mechanisms (Radford et al., 2018; Dai et al., 2019; Radford et al.,…”
Imputer: Sequence Modelling via Imputation and Dynamic Programming (2020, methodology): “The Insertion Transformer (Stern et al., 2019) and other insertion-based models (Gu et al., 2019a; Welleck et al., 2019; Chan et al., 2019b; Li & Chan, 2019; Ruis et al., 2019) generates sequences through a series of insertions.”
Insertion Transformer: Flexible Sequence Generation via Insertion Operations (2019, neutral): “Finally, we also note that Welleck et al. (2019) 1 concurrently explored generation using a tree formulation, similar to our Insertion Transformer implementation.”
Insertion-based Decoding with Automatically Inferred Generation Order (2019, neutral): “Welleck et al. (2019) propose a tree-like generation algorithm.”
Levenshtein Transformer (2019, background): “Welleck et al. (2019); Stern et al. (2019); Gu et al. (2019) generate translations non-monotonically by adding words to the left or right of previous ones or by inserting words in arbitrary order to form a sequence.”
Blank Language Models (2020, methodology): “Part of these efforts was focused on ﬁnding an optimal generation order, including syntax-based approaches and methods for learning adaptive generation order (Emami & Jelinek, 2005; Zhang et al., 2015; Dyer et al., 2016; Ford et al., 2018; Zhou et al., 2019; Welleck et al., 2019; Gu et al., 2019a).”
Big Bidirectional Insertion Representations for Documents (2019, background): “Recently, insertion-based models (Stern et al., 2019; Welleck et al., 2019; Gu et al., 2019; Chan et al., 2019) have been introduced for text generation.”
Neural Machine Translation: A Review (2019, background): “Other orderings besides L2R and R2L have also been proposed such as middle-out (Mehri & Sigal, 2018), top-down in a binary tree (Welleck et al., 2019), insertionbased (Gu et al.”
Insertion-Deletion Transformer (2020, background): “Recently, research in insertion-based non- or partially- autoregressive models has spiked (Stern et al., 2019; Welleck et al., 2019; Gu et al., 2019a; Chan et al., 2019).”
Learning to Generate Code Sketches (2021, methodology): “Recently, sequence generation approaches that go beyond the left-to-right paradigm have been proposed [37, 32, 11, 10, 17, 30], usually by considering generation as an iterative reﬁnement procedure that changes or extends a sequence in every iteration.”
Big Little Transformer Decoder (2023, methodology): “Such a multi-iteration decoding scheme has also been proposed in [16, 55, 68], which generates texts with fewer steps than the autoregressive scheme by inserting or deleting multiple tokens per iteration.”
Logical Natural Language Generation from Open-Domain Tables (2020, methodology): “In this context, we believe L OGIC NLG to be an important testbed to study such a planing/inference ability in generation models (Ford et al., 2018; Welleck et al., 2019).”
Non-Autoregressive Transformer Automatic Speech Recognition (2019, unknown): “Another direction explored in previous studies is to allow the output sequence to grow dynamically [7, 8, 9].”
Progressive Generation of Long Text with Pretrained Language Models (2021, background): “Another relevant line of research is non-monotonic generation (Welleck et al., 2019; Gu et al., 2019; Stern et al., 2019; Chan et al., 2019; Zhang et al., 2020), inﬁlling (Zhu et al., 2019; Shen et al., 2020; Qin et al., 2020), or reﬁnement (Lee et al., 2018; Novak et al., 2016; Mansimov et al.,…”
EDITOR: An Edit-Based Transformer with Repositioning for Neural Machine Translation with Soft Lexical Constraints (2020, methodology): “…models than the squared error (Leblond et al., 2018; Cheng et al., 2018), we deﬁne the cost function as the KL divergence be-tween the action distributions given by the model policy and by the oracle (Welleck et al., 2019): (5) where the oracle has additional access to the reference sequence y ∗ .”
NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics (2021, background): “Welleck et al. (2019a) develop a tree-based constrained text generation, which recursively generates text in a non-monotonic order given constraint tokens, ensuring constraints are satisﬁed.”
RankGen: Improving Text Generation with Large Ranking Models (2022, methodology): “Following prior work on text generation (Welleck et al., 2019; Holtzman et al., 2020; Su et al., 2022), we primarily focus on open-ended text generation, which has wide applications for tasks such as generating stories (Fan et al.”
An Empirical Study of Generation Order for Machine Translation (2019, background): “tion of sequences in a non-left-to-right fashion for machine translation (Stern et al., 2019; Welleck et al., 2019; Gu et al., 2019).”