PaperlayerView exact revision on arXiv

Source-linked AI summary

Insertion-Deletion Transformer

Laura Ruis, Mitchell Stern, Julia Proskurnia, William Chan

arXiv:2001.05540v1cs.LGcs.CLstat.ML

TL;DR

Insertion-only generation cannot undo mistakes, limiting its direct fit for iterative text editing. The paper introduces a Transformer with iterative insertion and deletion, training deletion on on-policy insertion outputs. On two synthetic translation tasks, deletion significantly increases BLEU over insertion-only generation, while evaluation on non-synthetic tasks remains future work.

  • Problem

    Insertion-only generation cannot undo its mistakes, while tasks such as text simplification and style transfer may require editing from the source sequence.

    Source: §1 · p. 1

  • Method

    The Insertion-Deletion Transformer iteratively performs insertions and deletions, training the deletion model on on-policy outputs from the insertion model.

    Source: §1 · p. 1

  • Results

    On two synthetic datasets, deletion significantly increases BLEU on simple tasks over insertion-only generation.

    Source: §1 · p. 2, §4 · p. 4

  • Takeaways & Limitations

    The framework can handle variable-length input and output sequences by repeating insertion and deletion phases until a stopping condition is reached.

    Source: §4 · p. 4

    The authors identify testing on non-synthetic data, including machine translation, paraphrasing, and style transfer, as future work.

    Source: §4 · p. 4

Abstract

from arXiv · show

We propose the Insertion-Deletion Transformer, a novel transformer-based neural architecture and training method for sequence generation. The model consists of two phases that are executed iteratively, 1) an insertion phase and 2) a deletion phase. The insertion phase parameterizes a distribution of insertions on the current output hypothesis, while the deletion phase parameterizes a distribution of deletions over the current output hypothesis. The training method is a principled and simple algorithm, where the deletion model obtains its signal directly on-policy from the insertion model output. We demonstrate the effectiveness of our Insertion-Deletion Transformer on synthetic translation tasks, obtaining significant BLEU score improvement over an insertion-only model.

1 Introduction and Related Work

Unlike conventional left-to-right autoregressive generation, insertion-based models can generate in arbitrary orders and in parallel. The paper adds an on-policy-trained deletion phase to insertion generation, aiming to undo insertion mistakes and support text editing.

1 Introduction and Related Work

  • Insertion-based models can generate in arbitrary orders and in parallel; balanced binary-tree ordering can produce n tokens in O(log2 n) iterations.The paper notes potential relevance to tasks such as cloze question answering and text simplification, where generation order may not naturally be left-to-right.Source: §1 · p. 1
  • The Insertion-Deletion Transformer iteratively performs insertion and deletion, training deletion on on-policy outputs from the insertion model.The deletion model learns appropriate deletions from sequences containing insertion errors.Source: §1 · p. 1
  • The deletion phase can undo insertion-model mistakes and supports editing applications such as text simplification and style transfer by starting from the source sequence.The paper contrasts this with insertion-only generation, where a generation mistake cannot be undone.Source: §1 · p. 1
  • Unlike LevT’s expert-policy training and three-stage process, this framework uses on-policy training and one insertion phase plus one deletion phase, without a token-count classifier.The authors describe this as a simplification of architecture, training, and inference runtime; they say speedups over balanced-tree insertion models are unclear.Source: §1 · p. 2
  • The paper presents the framework as a proof of concept on two synthetic character-based translation tasks, reporting significantly higher BLEU than insertion-only generation.Source: §1 · p. 2

2 Method

The method extends insertion-only generation with a deletion distribution over the current hypothesis. It trains the insertion and deletion decoders together, with deletion learning from insertion-model outputs sampled on-policy.

2 Method

  • Insertion operations add predicted vocabulary tokens at locations in an incomplete target until the output sequence is complete.The model predicts insertions in parallel at locations in the current sequence and stops inserting at a location when it predicts the end-of-sequence symbol.Source: §2 · p. 2
  • The deletion phase assigns each location in the current hypothesis a probability of deleting its token.The deletion variable d ranges from 0 for not deleting to 1 for deleting.Source: §2 · p. 2

2.1 Learning

  • Training samples a generation step and partial insertion history, inserts predicted tokens, then passes the resulting sequence to the deletion model.The sampled insertion output supplies the deletion model’s training input.Source: §2 · p. 2
  • Two stacked Transformer decoders parameterize the insertion and deletion distributions; both maximize their respective log-probabilities, without backpropagation through insertion sampling.The deletion model’s training signal depends on the current insertion model state.Source: §2.1 · pp. 2–3
  • Adversarial sampling masks ground-truth target tokens with probability padv so insertion selects a confident incorrect token and supplies deletion training signal.The authors propose this to address cases where the insertion model makes no errors or inserts nothing; they report it did not improve BLEU on the synthetic tasks.Source: §2.1 · p. 3

3 Experiments

On both synthetic translation tasks, adding deletion improves BLEU over insertion-only generation. The experiments cover ordered alphabetic shifts and the more diverse Caesar’s-cipher task, and report no BLEU improvement from adversarial deletion training.

3 Experiments

  • Adversarial deletion training did not improve BLEU on these tasks, but may provide a deletion signal when the insertion model makes no errors.Source: §3 · p. 3

3.1 Learning shifted alphabetic sequences

  • For shifted alphabetic sequences, training used 1,000 examples and evaluation used 100 held-out examples, with 200k training steps and no model selection.The task samples sequence lengths from 3 to 9 and shifts letters to create the target sequence.Source: §3.1 · p. 3

3.2 Learning Caesar’s Cipher

  • For Caesar’s cipher, the task uses randomly sampled letters and evaluates on 1,000 held-out examples after training on 100k examples.Sequences have lengths from 3 to 24, and each target letter is shifted left by one character in the example described.Source: §3.2 · p. 3

3 Experiments

4 Conclusion

The Insertion-Deletion Transformer uses two stacked Transformer decoders, with the deletion layer receiving its signal from the insertion model. On two synthetic datasets, deletion significantly increased BLEU on simple tasks; the authors leave evaluation on non-synthetic data for future work.

4 Conclusion

  • The model uses a simple stack of two Transformer decoders, with the deletion layer receiving its signal from the insertion transformer.Source: §4 · pp. 3–4
  • Deletion significantly increases BLEU on simple tasks across two synthetic datasets by iteratively refining outputs with insertion-deletion sequences.Table 2 reports BLEU scores for the sequence-shifting task.Source: §4 · p. 4, Table 2 · p. 4
  • The approach applies to variable-length inputs and outputs, such as machine translation, without adjustments.Source: §4 · p. 4
  • The authors identify non-synthetic machine translation, paraphrasing, and style transfer as future evaluation targets.Source: §4 · p. 4
Loading 2001.05540v1…