Source-linked AI summary
Parallel Iterative Edit Models for Local Sequence Transduction
Abhijeet Awasthi, Sunita Sarawagi, Rasna Goyal, Sabyasachi Ghosh, Vihari Piratla
TL;DR
Local sequence transduction tasks such as GEC require changing only a few positions, but encoder-decoder models decode sequentially and are slow. The paper introduces PIE, which labels and iteratively refines in-place edits in parallel while factorizing edit logits to reuse pretrained language models. Across GEC, OCR correction, and spell correction, PIE is reported as accurate and substantially faster than sequential alternatives.
Problem
Local sequence transduction tasks such as GEC need localized input-output changes, while popular encoder-decoder approaches use slow sequential decoding.
Method
PIE performs non-autoregressive sequence labeling with in-place edit operations, iterative refinement, and factorized logits that harness pretrained language models such as BERT.
Results
PIE is reported as accurate and significantly faster across GEC, OCR correction, and spell correction, with GEC inference 5 to 15 times faster than a competitive encoder-decoder model.
Takeaways & Limitations
Parallel iterative editing can achieve performance close to sequential models for local sequence transduction without beam-search and slow sequential decoding overheads.
Takeaways & Limitations
The edit construction cannot guarantee recovering every training target because it limits inserted q-grams to the M most frequent ones, although three or more consecutive inserts are rare in the NUCLE dataset.
Abstract
from arXiv · showhide
We present a Parallel Iterative Edit (PIE) model for the problem of local sequence transduction arising in tasks like Grammatical error correction (GEC). Recent approaches are based on the popular encoder-decoder (ED) model for sequence to sequence learning. The ED model auto-regressively captures full dependency among output tokens but is slow due to sequential decoding. The PIE model does parallel decoding, giving up the advantage of modelling full dependency in the output, yet it achieves accuracy competitive with the ED model for four reasons: 1.~predicting edits instead of tokens, 2.~labeling sequences instead of generating sequences, 3.~iteratively refining predictions to capture dependencies, and 4.~factorizing logits over edits and their token argument to harness pre-trained language models like BERT. Experiments on tasks spanning GEC, OCR correction and spell correction demonstrate that the PIE model is an accurate and significantly faster alternative for local sequence transduction.
1 Introduction
The paper reframes grammatical error correction as local sequence transduction and introduces PIE, a fast parallel-iterative alternative to autoregressive encoder-decoder models. PIE predicts and iteratively refines edits through sequence labeling, while factorized logits help exploit pretrained language models.
- Problem: GEC is treated as local sequence transduction because input and output sequences differ at only a few positions and use the same vocabulary.This contrasts with translation and paraphrasing, which may involve different vocabularies and non-local alignments.
- PIE approach: PIE uses parallel iterative inference to refine edit predictions while avoiding the sequential decoding required by encoder-decoder models.This iterative refinement is intended to capture dependencies despite parallel prediction.
- PIE approach: PIE replaces autoregressive token generation with non-autoregressive sequence labeling over edit operations applied to source tokens.Its edit space includes operations such as capitalization, copying, appending, replacement, and custom transformations.
- PIE approach: Factorized logits over edits and their token arguments allow PIE to harness pretrained language models such as BERT with edit-specific attention masks.The architecture separates edit commands from token arguments rather than predicting output tokens directly.
- Results: 5 to 15 times faster inference is reported for PIE than for a competitive encoder-decoder GEC model, while accuracy remains close to state of the art on standard GEC datasets.The paper also evaluates PIE on OCR correction and spell correction, where it is described as fast and accurate relative to task-specific models.
2 Our Method
PIE reformulates local sequence transduction as parallel labeling of input tokens with in-place edits, then iteratively refines those edits. Its architecture uses bidirectional contextual representations and edit-factorized logits to exploit BERT-like pre-training.
- 2.1 Problem Formulation: PIE models local sequence transduction by assigning each input token an edit label, keeping the edit sequence length equal to the input length.The Seq2Edits function converts source-target pairs into copy, delete, append, replace, and transformation operations.
- 2.1 Training and Inference: Inference predicts edits for all input positions independently, applies them in parallel, and repeatedly refines the generated sequence until convergence or a maximum iteration count.This avoids sequential token generation while allowing later rounds to capture dependencies between edits.
- 2.2 The Seq2Edits Function: The edit space represents insertions as in-place append or transformation operations, with q-gram arguments drawn from a frequent-insert dictionary.The conversion procedure post-processes Levenshtein diffs, merges consecutive inserts, and scans them into position-aligned edits.
- 2.2 The Seq2Edits Function: Because the frequent-insert dictionary is limited, Seq2Edits cannot guarantee exact reconstruction for every training pair; however, three-or-more consecutive inserts occur in fewer than 3% of NUCLE sentences.The experiments use q = 2 because long chains of consecutive inserts are expected to be rare in local transduction.
- 2.3 The Parallel Edit Prediction Model: PIE uses a bidirectional transformer encoder, pre-trained like BERT, to produce contextual representations for predicting edits at each input position.The encoder processes the input in parallel and can be initialized using masked-token prediction on an unmatched correct corpus.
- 2.3.2 An Edit-factorized BERT Architecture: The edit-factorized architecture combines edit-specific parameters with scores for the copied input word and any incoming token argument, enabling pre-trained token embeddings to support append and replace edits.Additional replace and append units use alternative positional embeddings and attention patterns without adding new hidden-layer parameters to BERT.
3 Experiments
Experiments evaluate PIE on GEC, OCR correction, and spell correction, showing competitive accuracy with substantially faster parallel decoding. Iterative refinement improves GEC accuracy, while ablations identify several important design choices.
- 3.1.1 Overall Results: PIE achieves GEC performance close to state-of-the-art models without beam-search overhead or sequential decoding.On CoNLL-14, results are very close to the highest reported score; JFLEG GLEU+ is somewhat lower because predictions are parallel.
- 3.1.2 Running Time Comparison: 5 to 15 times faster decoding is reported for PIE than an equivalent transformer-based ED model on CoNLL-14.PIE-LARGE has F0.5 = 59.7, PIE-BASE has F0.5 = 56.6, and T2T has F0.5 = 56.8 in the timing comparison.
- 3.1.3 Impact of Iterative Refinement: F0.5 increases from 57.9 to 59.5 by the second refinement iteration, while examples require 2.7 average rounds instead of 23.2 sequential steps.Only 832 of 1312 sentences changed in the first round, and 156 changed in the second.
- 3.1.4 Ablation study on the PIE Architecture: Removing edit factorization lowers F0.5 by 1.2 points, independently predicting inserts lowers it by 2.7 points, and removing transformations lowers recall by 6.3 points.These ablations compare alternative design choices with the factorized PIE configuration.
- 3.1.4 Ablation study on the PIE Architecture: Removing language-model pre-training causes a 20-point F0.5 drop, demonstrating the importance of pre-trained language models for GEC performance.The ablation compares an uninitialized network with the BERT-initialized model.
- 3.2 More Sequence Transduction Tasks: On OCR and spell correction, PIE accuracy is comparable to encoder-decoder models, but speedups are modest because most words are short and vocabularies are small.The evaluation uses a four-layer self-attention transformer with one refinement iteration for these tasks.
4 Related Work
The paper situates PIE against sequential encoder-decoder approaches and prior parallel or edit-based methods for local sequence transduction. Its formulation differs by combining in-place edit prediction with non-autoregressive sequence labeling.
- Recent neural GEC systems predominantly use sequential encoder-decoder models that generate word or character sequences.
- Prior parallel translation methods model dependency through latent variables, staged generation, or decoder-state initialization, whereas PIE uses delete and append edits.
- Ribeiro et al. predict insertion slots before labeling tokens, while PIE directly predicts edit operations including word transformations.
5 Conclusion
The PIE model applies parallel iterative editing to local sequence transduction, focusing on grammatical error correction. Compared with sequential encoder-decoder models, it reduces decoding time by a factor of 5 to 15 while aiming to match their accuracy.
- 5 to 15× lower decoding time is achieved by PIE's parallel decoding compared with sequential encoder-decoder models.The passage describes this as a reduction in decoding time relative to popular encoder-decoder models.
- PIE predicts in-place edits using a carefully designed edit space.
- PIE iteratively refines its predictions to help match the accuracy of sequential models despite parallel decoding.
A.1 Modified Cost in Levenshtein Distance Algorithm
The modified Levenshtein distance assigns a small length-dependent penalty to substitutions, resolving ties between otherwise equivalent edit diffs. Table 9 illustrates two minimum diffs that tie without this offset.
- Substitutions cost 1 + ϵd, where d is the absolute character-count difference between the replaced and substituted words.The offset parameter is set to ϵ = 0.001, while deletion and insertion costs remain 1.
- ϵ is set to 0.001 while delete and insert costs remain 1.
- Table 9 presents two diffs with the same edit distance when no substitution offset is used.The examples differ in how punctuation and the word Then/then are substituted or inserted.
A.2 Suffix transformations
The appendix reports 29 suffix transformations and their corresponding inverses, for 58 suffix transformations in total.
- 29 suffix transformations are paired with their corresponding inverse transformations.
- The transformations and their inverses make 58 suffix transformations in total.
- Each listed suffix transformation contributes a corresponding inverse to the transformation set.
A.3 Artificial Error Generation
The artificial-error generation algorithm corrupts clean sentences by sampling how many errors to introduce and which error types to apply, using distributions derived from a parallel corpus.
- Error sampling: The algorithm processes a dataset of clean sentences and samples each sentence’s error count from a multinoulli distribution over zero to four errors.The sampling probabilities are (0.05, 0.07, 0.25, 0.35, 0.28).
- Error sampling: The number and type distributions were estimated from the available parallel corpus.
- Error placement: For append, replace, and delete errors, the algorithm randomly selects the position where the error occurs.
- Error operations: Append errors drop the word at the selected position, delete errors add a spurious commonly deleted word, and replace errors perform both actions.
A.4 Wall-clock Decoding Times
The paper reports wall-clock decoding time in milliseconds for various grammatical error correction models.
- Decoding-time comparison: Table 11 compares wall-clock decoding time in milliseconds across various GEC models.
A.5 Hyperparameters
The paper specifies hyperparameters separately for PIE and T2T Transformer models across GEC, OCR correction, and spell correction.
- PIE Model: PIE hyperparameters are reported for GEC, OCR correction, and spell correction settings.For GEC, the copy weight is 0.4, selected on the validation set to scale down copy-label loss for class imbalance.
- T2T Transformer Models: T2T Transformer hyperparameters are reported for GEC, OCR correction, and spell correction models.The models were implemented using the tensor2tensor library.