PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-Monotonic Sequential Text Generation

Sean Welleck, Kianté Brantley, Hal Daumé III, Kyunghyun Cho

arXiv:1902.02192v3cs.CLcs.LGstat.ML

TL;DR

Most standard sequence generators assume a fixed order, such as left-to-right, and the paper investigates learning non-monotonic orders without external supervision. It trains a tree-generating policy through imitation learning and annealed coaching; results are competitive with left-to-right generation, with a projective-generation constraint.

  • Problem

    Standard sequence-generation methods assume a pre-specified order, commonly left-to-right, while the paper investigates non-monotonic generation without external supervision.

    Source: §1 · p. 1

  • Method

    The framework learns a policy through imitation learning, using annealed coaching to move from imitating an oracle toward reinforcing the policy’s own preferences.

    Source: §1 · p. 1

  • Results

    The annealed policy significantly outperforms alternatives in language modeling, essentially ties left-to-right decoding on word reordering, and tends to preserve meaning but not n-grams in machine translation.

    Source: §7 · p. 8

  • Takeaways & Limitations

    The approach learns non-monotonic generation orders without pre-specifying an order and achieves competitive or superior performance to left-to-right generation across the evaluated tasks.

    Source: §1 · p. 1, §7 · p. 8

    Generation is projective: it cannot consider orders with crossing edges, and extending the approach to non-projective generation is left for future work.

    Source: §7 · p. 8

Abstract

from arXiv · show

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.

1. Introduction

The paper asks whether text generation can use learned non-monotonic orders without external supervision. It proposes imitation learning with annealed coaching and reports competitive or superior performance to conventional left-to-right generation across several tasks.

1. Introduction

  • Most sequence-generation models use monotonic orders, motivating investigation of non-monotonic orders learned without external supervision.The introduction cites “easy first” techniques in tagging, parsing, and coreference as examples of learned ordering.Source: §1 · p. 1
  • The framework learns a generation order without specifying one in advance, using imitation learning and annealed coaching that shifts from a maximum-entropy oracle toward the policy’s preferences.It generates a word at an arbitrary position, then recursively generates words to its left and right.Source: §1 · p. 1
  • The learned policies achieve performance competitive with or superior to conventional left-to-right generation in language modeling, word reordering, and machine translation.Source: §1 · p. 1

2. Non-Monotonic Sequence Generation

The model generates a sequence by choosing a word at an arbitrary position and recursively generating left and right subtrees. Its policy can select among binary trees that yield the same final sequence, rather than following a fixed order.

2. Non-Monotonic Sequence Generation

  • The model generates a word at an arbitrary position, then recursively generates words to its left and right, forming a binary tree.Source: §2 · p. 2
  • A state is a level-order sequence of actions that represents a top-down traversal of a partial binary tree; ⟨end⟩ terminates a subtree.The final sequence is read in in-order traversal, with ⟨end⟩ tokens removed.Source: §2 · p. 2
  • A policy can choose among multiple binary trees with the same in-order sequence, and left-to-right generation is recoverable as a special case.Source: §2 · p. 2

3. Learning for Non-Monotonic Generation

Learning the generation policy is challenging because training sequences specify the target words but not the tree that determines their generation order. The paper uses learning-to-search and imitation learning, with a KL-style cost, oracle roll-ins, and several oracle designs.

3. Learning for Non-Monotonic Generation

  • The target sequence does not specify the tree or action sequence, making the tree a latent variable and preventing conventional supervised policy training.Knowing the target words and their order constrains the search space and motivates imitation learning.Source: §3 · p. 2

3.1. Background: Learning to Search

  • Learning-to-search trains a policy to imitate an oracle by sampling states under a roll-in policy and estimating each action’s cost-to-go under a roll-out policy.Source: §3.1 · p. 3

3.2. Cost Measurement

  • The training cost is a KL-divergence-type loss between the learned policy’s action distribution and the distribution preferred by the roll-out policy.The loss is estimated at states reached by a roll-in policy, then minimized iteratively.Source: §3.2 · p. 3

3.3. Roll-In Policies

  • All experiments use oracle roll-ins because they performed best in preliminary experiments, although this choice can make the learned model inconsistent.Source: §3.3 · p. 3

3.4. Oracle Policies

  • The oracle assigns probability only to valid target tokens and emits ⟨end⟩ when no words remain, preserving the target sequence across its choices.Choosing a token splits the current consecutive target subsequence between the left and right child nodes.Source: §3.4 · pp. 3–4
  • Uniform, coaching, and annealed oracles respectively treat valid orders equally, favor the policy’s valid actions, and mix both behaviors while β decreases from 1 to 0.Source: §3.4 · p. 4
  • Using deterministic left-to-right policies for both roll-in and oracle recovers maximum-likelihood training of an autoregressive sequence model.Source: §3.4 · p. 4

4. Neural Net Policy Structure

The model implements its policy with sequence-based neural architectures over a level-order representation of the partial tree. The network can also condition generation on an input, with different encoder outputs used for reordering and translation.

4. Neural Net Policy Structure

  • The LSTM policy encodes the partial tree as a flat level-order sequence, while the Transformer summarizes that sequence with multi-head attention.Both compute a distribution over the action set from the resulting vector.Source: §4 · p. 4
  • The LSTM relies on linearizing the partial tree and minimally uses the tree structure or surface order.Preliminary experiments adding the current node’s parent as context showed no gains.Source: §4 · p. 4

4.1. Conditional Sentence Generation

  • A conditioning input can be encoded jointly with the policy; reordering uses one encoder vector to initialize the LSTM, while translation uses encoder vectors as decoder-attention inputs.Source: §4.1 · p. 5

5. Experimental Results

The experiments cover two unconditional tasks—language modeling and sentence completion—and two conditional tasks—word reordering and machine translation—using qualitative analyses and benchmark comparisons.

5.1. Language Modeling

  • For Persona-Chat policies, statistics over 10,000 sampled sentences show non-monotonically trained policies generated many more novel sentences and bushy trees (span ∼1.3), while annealed-oracle training was most similar to validation data by BLEU.Source: Table 1 · p. 5, §5.1 · p. 6
  • Annealed-oracle language models often put punctuation at the root and pronouns at depth 1, while nouns tend to occur deeper.Uniform-oracle policies tend to generate varied part-of-speech tags at each depth.Source: §5.1 · p. 6, Figure 3 · p. 6

5.3. Word Reordering

  • F1 scores were 0.96 and 0.95 for uniform and annealed policies versus 0.903 for left-right; annealed BLEU was 46.0 versus 46.3 and exact match was 0.212 versus 0.208.The uniform policy did not fare as well on BLEU or exact match.Source: Table 4 · p. 7, §5.3 · p. 7

5.2. Sentence Completion

  • BLEU was 44.7 for annealed-oracle completions, versus 38.9 for uniform and 14.3 for left-to-right completions.Completions were sampled from initial trees seeded with three words drawn from validation sentences.Source: §5.2 · pp. 6–7

5.3. Word Reordering

  • The annealed word-reordering policy makes its highest-confidence predictions early in the tree and defers harder decisions, unlike the left-right and uniform policies.The latter two begin with high entropy and become more confident as prior context accumulates.Source: §5.3 · p. 7, Figure 4 · p. 7

5.4. Machine Translation

  • For machine translation, annealing outperformed the uniform policy on all reported metrics, and tree encoding yielded further gains; end-threshold tuning lowered Ribes while improving the other metrics.The tuned variant also notably increased the BLEU brevity penalty.Source: §5.4 · p. 7, Table 5 · p. 8
  • Left-to-right has higher BLEU than the best non-monotonic machine-translation model, while the best annealed model is typically within one percentage point on the other three quality measures.The paper notes that BLEU is more sensitive to exact word order than the other measures.Source: Table 5 · p. 8, §5.4 · p. 8

6. Related Work

Prior sequence-generation approaches largely use autoregressive or left-to-right orders, while earlier tree-structured language models rely on parse information. This work instead learns a distinct generation order without extra annotation or tools.

6. Related Work

  • Neural autoregressive modeling is a de facto standard in machine translation; non-autoregressive methods generate discrete tokens in parallel, while semi-autoregressive generators mix both paradigms yet largely stick to left-to-right generation.Source: §6 · p. 8
  • Earlier tree- or graph-based language models factorize sentence probabilities by syntactic structure but require ground-truth parses or an external parser [Zhang et al., 2015; Dyer et al., 2016].Such approaches were also applied to neural machine translation [Eriguchi et al., 2017; Aharoni & Goldberg, 2017].Source: §6 · p. 8
  • Unlike those approaches, the proposed method learns an automatically determined non-monotonic order without extra annotation or tools.Source: §6 · p. 8

7. Conclusion, Limitations & Future Work

The learned non-monotonic approach performs competitively across the reported tasks, while its current formulation constrains generation to projective binary trees. The authors identify stopping, oracle generalization, and broader tree structures as future work.

  • The annealed coaching oracle performs best among explored oracles and learns a best-first language-modeling strategy that significantly outperforms alternatives.Source: §7 · p. 8
  • On word reordering, the approach essentially ties left-to-right decoding; translation tends to preserve meaning but not n-grams.Source: §7 · p. 8
  • Future work includes directly learning when to stop and improving oracle generalization after mistakes so training can follow gold paths.Source: §7 · p. 8
  • The current sequence-generation formulation uses binary trees; extending it to n-ary trees would require an oracle designed for that structure.N-ary decisions could capture generation orders including all projective dependency parses.Source: §7 · p. 8
  • The approach supports projective generation, not all possible orders, because its trees prohibit crossing edges; non-projective generation is left for future work.Source: §7 · p. 8

A.1. Word Reordering

The word-reordering experiments use a two-layer LSTM policy and greedy decoding, with annealed coaching settings selected through a small grid search. The appendix also describes validation examples and training details.

  • The word-reordering decoder is a two-layer LSTM with 1,024 hidden units, and all reported results use greedy decoding.Word embeddings start from GloVe vectors and are updated during training.Source: §A.1 · p. 12
  • Models train for up to 500 epochs with batch size 32 and Adam; checkpoint selection uses the highest validation BLEU.The learning rate starts at 0.001 and halves every 20 epochs.Source: §A.1 · p. 12
  • Annealed coaching linearly reduces β from 1.0 to 0.0 by 0.05 per epoch after a 20-epoch burn-in.Source: §A.1 · p. 12
  • The coaching hyperparameter search tests β rates 0.01 or 0.05, burn-ins of 0 or 20 epochs, and greedy or stochastic roll-in; roll-in sampling showed no significant performance variation.Source: §A.1 · p. 12
  • Figure 8 presents validation-set predictions with their generation orders and underlying trees.Source: §A.1 · p. 12

A.2. Unconditional Generation

For unconditional generation, the appendix reports that annealed-oracle policies generally achieve the highest BLEU metrics across sampler settings. It also describes roll-in, checkpoint selection, and sample groupings.

  • Unconditional-generation experiments use stochastic sampling from π∗ coaching during roll-in and select the model at the end of training.Source: §A.2 · p. 12
  • The reported unconditional samples are grouped as short, average-length, or multi-sentence, and figures show each sentence with its tree and generation order.Source: §A.2 · p. 12
  • Across the reported top-k samplers and BLEU metrics, the annealed-oracle policy generally achieves the highest scores.Table 6 covers k values 10, 100, and 1,000 and BLEU-2, BLEU-3, and BLEU-4.Source: Table 6 · p. 12, §A.2 · p. 12

A.3. Machine Translation

The machine-translation appendix describes data preprocessing, Transformer and LSTM policy configurations, an auxiliary end-token loss, and tree-position encodings. Its supplied result excerpts identify test-set policy variants and translation-output figures.

  • Training data uses Moses tokenization and BPE to create 40,000 source and target tokens, with sentence pairs over 50 words filtered out.Source: §A.3 · p. 12
  • The Transformer policy has four layers and four attention heads; its learning rate decays every 100 epochs, and checkpoint selection uses validation BLEU.For this experiment, an epoch is 1,000 updates.Source: §A.3 · p. 12
  • The auxiliary end predictor uses binary cross-entropy at every step, while the policy KL loss is masked on end-token steps and averaged over unmasked steps.Source: §A.3 · p. 12
  • Transformer tree-position encodings represent each node by its root-to-node left/right path, zero-pad the vector, then scale it element-wise by a learned geometric series.Source: §A.3 · pp. 12–13
  • Figures 9, 10, and 11 show translation outputs from policies trained with π∗.Source: Figure 9 · p. 19, Figure 10 · p. 20, Figure 11 · p. 21
  • Test-set results name annealed, uniform, and leftright policies; Table 7 reports LSTM policy results for machine translation.Source: Table 7 · p. 13, §A.3 · pp. 19–21
Loading 1902.02192v3…