Source-linked AI summary
Sequence-to-Sequence Learning as Beam-Search Optimization
Sam Wiseman, Alexander M. Rush
TL;DR
Seq2seq training optimizes local word predictions even though inference searches over complete sequences, producing exposure and loss-evaluation mismatches. The paper introduces a sequence-scoring model with beam-search optimization that trains against search errors while retaining standard seq2seq efficiency. It reports significant improvements over attention-based seq2seq across word ordering, parsing, and machine translation.
Problem
Standard seq2seq training uses local word-level losses, while test-time generation uses search over complete sequences, causing exposure bias and loss-evaluation mismatch.
Method
The paper introduces a non-probabilistic seq2seq model with global sequence scores and a LaSO-inspired beam-search loss that penalizes the gold sequence falling off the beam.
Results
Significant improvements over an attention-based seq2seq system are reported on word ordering, syntactic parsing, and machine translation, especially on tasks requiring difficult search.
Takeaways & Limitations
Beam-search optimization provides a unified sequence-level training and generation approach while largely preserving standard seq2seq architecture and training efficiency.
Takeaways & Limitations
Early-update training did not work well even after pre-training, and the authors leave this question for future work.
Abstract
from arXiv · showhide
Sequence-to-Sequence (seq2seq) modeling has rapidly become an important general-purpose NLP tool that has proven effective for many text-generation and sequence-labeling tasks. Seq2seq builds on deep neural language modeling and inherits its remarkable accuracy in estimating local, next-word distributions. In this work, we introduce a model and beam-search training scheme, based on the work of Daume III and Marcu (2005), that extends seq2seq to learn global sequence scores. This structured approach avoids classical biases associated with local training and unifies the training loss with the test-time usage, while preserving the proven model architecture of seq2seq and its efficient training approach. We show that our system outperforms a highly-optimized attention-based seq2seq system and other baselines on three different sequence to sequence tasks: word ordering, parsing, and machine translation.
1 Introduction
Standard seq2seq systems train on local next-word predictions but generate complete sequences at test time, creating exposure and loss-evaluation mismatches. This work introduces beam-search optimization to learn sequence scores and reports improvements across word ordering, parsing, and machine translation.
- Seq2seq training maximizes each target word’s likelihood conditioned on the input and gold target history, typically using cross-entropy.
- At test time, seq2seq systems generate complete output sequences through greedy or beam search rather than conditional language-model evaluation.
- Exposure bias arises because training never exposes the model to its own errors, making test-time histories differ from gold training histories.
- Loss-evaluation mismatch arises because training uses a word-level loss while testing targets sequence-level metrics such as BLEU.
- The proposed non-probabilistic seq2seq variant scores complete target sequences and trains with beam-search errors, using an efficient backpropagation algorithm.
- Significant improvements over an attention-based seq2seq baseline occur on word ordering, syntactic parsing, and machine translation, especially when search is difficult.
2 Related Work
Related work addresses exposure bias through policy-based training, beam-aware structured prediction, and reinforcement-learning techniques, while label bias arises from locally normalized scores.
- SEARN and DAgger train on outputs from the model’s own policy to reduce the mismatch between oracle training and non-oracular test-time inference.
- Scheduled sampling applies SEARN/DAgger-style training to RNNs by increasingly replacing true previous tokens with predicted tokens.
- Early update and LaSO explicitly incorporate beam search and update parameters when the gold structure becomes unreachable.
- Reinforcement-learning approaches, including Ranzato et al.’s method and minimum risk training, improve sequence-to-sequence performance while targeting exposure bias and loss-evaluation mismatch.
- Label bias differs from exposure bias because it stems from locally normalized model scores, a property typical of RNN-based seq2seq models.
3 Background and Notation
Seq2seq uses an encoder-decoder architecture whose recurrent decoder generates target words conditioned on the input and prior history. Standard training models local conditional probabilities, while decoding requires heuristic beam search and remains vulnerable to exposure and label bias.
- Seq2seq maps source-target pairs into an encoder-decoder task, such as generating English sentences from corresponding French sentences.
- The decoder generates target-vocabulary words sequentially from the encoded input representation and previously generated target history.
- Most seq2seq decoders use recurrent neural networks that recursively map input vectors to hidden states with parameters shared across time.
- Conditional-language-model training represents each target-word probability as a function of the input and preceding target history, commonly using an affine layer and softmax.
- Decoding approximately maximizes target-sequence probability with beam search because the recurrent model is non-Markovian; beam search keeps K prospective histories per time step.
- These decoding and training choices motivate the paper because they can produce exposure bias and label bias.
4 Beam Search Optimization
Beam search optimization replaces local next-word probabilities with sequence scores and trains the model on beam-search errors, while retaining efficient seq2seq training. The method uses LaSO-style search, margin-based losses, constrained successors, and shared backpropagation to handle incorrect histories efficiently.
- Sequence scoring: The model scores complete sequences by summing or ranking non-probabilistic token-level scores instead of applying a final softmax to next-word outputs.The scoring function uses the RNN hidden state and input representation, with the experimental function matching the standard model before softmax.
- Search-based loss: Beam search optimization penalizes the gold prefix when it falls behind the top beam candidate by a margin, aligning training with test-time generation.At the final step, the gold sequence must exceed the highest-ranked incorrect prediction by a margin.
- Backward propagation: Training uses a forward beam-search pass to collect margin violations and a backward pass that propagates errors through the seq2seq RNNs.Unlike standard training, the forward pass runs search; the backward pass adapts backpropagation through time and includes wrongly predicted histories.
- Forward search: Candidate beams are updated recursively: standard beam search continues without a violation, while a violation resets search using the gold history before selecting the K best continuations.The successor function maps a prefix to valid one-token extensions, and topK selects candidates by their scores.
- Forward search: The successor function can impose hard constraints, enabling training over only valid output structures such as constituency or dependency parses.The constrained model is called ConBSO in the experiments.
- Backward propagation: Shared backward operations avoid the naive O(T^2) cost caused by independently backpropagating through up to T incorrect sequences.The LaSO reset structure lets gradients from sequences sharing prefixes be accumulated in a single computation tree.
5 Data and Methods
The paper evaluates beam-search optimization for seq2seq across word ordering, dependency parsing, and machine translation, using a shared attention-based architecture and comparisons with standard seq2seq and other baselines. Experiments also examine constrained decoding, beam sizes, sequence-level costs, and training efficiency.
- Experimental setup: Experiments compare BSO with seq2seq and other baselines on word ordering, dependency parsing, and machine translation.The same general-purpose system is evaluated across three different sequence-to-sequence problems.
- Experimental setup: The experiments use Luong et al.'s global-attention LSTM encoder-decoder as both the seq2seq baseline and the sequence-scoring model.The model includes input feeding and global attention, preserving the core seq2seq architecture.
- Training procedure: BSO training is implemented with forward beam search, margin-violation storage, and backward propagation through the search procedure.The procedure follows LaSO-style delayed updates and recursively constructs candidate beams after violations.
- Task constraints: Constrained BSO enforces task-specific output restrictions, including source-word permutation constraints for word ordering and valid-parse constraints for structured outputs.For word ordering, successor sequences may contain only unused source words; parsing uses constraints such as stack validity and source-order emission.
- Results: Word ordering improved substantially with BSO at every beam size, and constrained BSO produced further gains.Beam-size experiments also found that larger training beams could hurt greedy inference while initially benefiting larger test beams.
- Efficiency: Training processed 1,985, 1,768, 1,709, 1,521, and 1,458 tokens/second for training beams Ktr = 2, 3, 4, 5, and 6, respectively.The implementation incurred an initial factor of approximately 3.3 relative to the tuned seq2seq baseline, with sub-linear practical scaling from GPU batching.
6 Conclusion
The paper introduces beam-search optimization for seq2seq, addressing exposure bias and label bias while supporting sequence-level costs and hard constraints.
- Beam-search optimization addresses exposure bias and label bias in seq2seq models.
- The approach supports training with sequence-level cost functions and hard constraints on sequence generation.
- The authors identify scaling to much larger datasets as future work.