Source-linked AI summary
Online and Linear-Time Attention by Enforcing Monotonic Alignments
Colin Raffel, Minh-Thang Luong, Peter J. Liu, Ron J. Weiss, Douglas Eck
TL;DR
Soft attention improves sequence-to-sequence modeling but requires quadratic, offline processing of the entire input for each output. The paper learns hard monotonic alignments differentiably, using expected outputs for training and online linear-time attention at test time, with competitive performance across studied tasks.
Problem
Soft attention requires a full input pass for each output, giving O(TU) complexity and preventing online decoding.
Method
The paper trains a differentiable hard monotonic alignment process through expected outputs, then applies its left-to-right attention process for online linear-time decoding.
Results
Across the studied tasks, the added online and linear-time benefits caused only a small performance decrease relative to softmax-based attention.
Takeaways & Limitations
The approach provides efficient online decoding without sacrificing substantial performance across sentence summarization, machine translation, and online speech recognition.
Takeaways & Limitations
The method assumes strictly monotonic alignments, and online speech-recognition results remained substantially behind offline bidirectional-LSTM results.
Abstract
from arXiv · showhide
Recurrent neural network models with an attention mechanism have proven to be extremely effective on a wide variety of sequence-to-sequence problems. However, the fact that soft attention mechanisms perform a pass over the entire input sequence when producing each element in the output sequence precludes their use in online settings and results in a quadratic time complexity. Based on the insight that the alignment between input and output sequence elements is monotonic in many problems of interest, we propose an end-to-end differentiable method for learning monotonic alignments which, at test time, enables computing attention online and in linear time. We validate our approach on sentence summarization, machine translation, and online speech recognition problems and achieve results competitive with existing sequence-to-sequence models.
1. Introduction
Sequence-to-sequence models initially compress inputs into one fixed-length vector, while attention improves access to input representations but soft attention remains quadratic and offline. The paper proposes differentiable hard monotonic alignments to retain attention benefits with online, linear-time decoding.
- Motivation: Fixed-length encoding forces the model to compress all important input information into one vector, hindering generalization to longer sequences.Attention instead provides the decoder with encoder hidden states corresponding to input entries.
- Limitations of soft attention: Soft attention scans the entire input for every output element, producing O(TU) decoding complexity.T and U denote the input and output sequence lengths, respectively.
- Limitations of soft attention: Soft attention is unsuitable for online settings because it must process the entire input before producing any output symbols.Online output requires operating when only part of the input has been observed.
- Motivation: Many sequence-to-sequence tasks have roughly monotonic input-output alignments and attention concentrated mostly on a single input entry.The paper notes that alignments may include local reorderings and that these properties do not hold for every task, such as image captioning.
- Contribution: The proposed hard monotonic attention uses a stochastic process that supports online, linear-time decoding while training remains differentiable through expected outputs.The method is trained with a quadratic-time algorithm and uses standard backpropagation, then decodes efficiently at test time.
2. Online and Linear-Time Attention
The paper replaces softmax attention’s full-memory, non-online computation with a differentiable training procedure for hard monotonic alignments, enabling online linear-time decoding.
- 2.1. Soft Attention: Softmax attention computes expected context vectors from independently normalized alignment probabilities over the entire memory.The decoder can be viewed as sampling a memory index independently for each output step and replacing that sample with its expected value.
- 2.1. Soft Attention: Softmax attention requires O(TU) computation and cannot emit outputs before the entire input sequence is observed.At every output timestep, it passes over all input entries to compute the attention terms.
- 2.2. A Hard Monotonic Attention Process: Hard monotonic attention scans memory left-to-right from the previous chosen index and stops when it samples a selection decision.The selected memory entry becomes the context vector, while subsequent output steps resume from that position.
- 2.2. A Hard Monotonic Attention Process: The monotonic process is online and computes at most max(T, U) probability terms, yielding linear runtime under a strictly monotonic alignment assumption.It only requires encoder states up to the currently inspected memory position, but assumes input-output alignments never move backward.
- 2.3. Training in Expectation: Because sampling is nondifferentiable, training uses the expected context vector computed with a quadratic-time recurrence, followed by linear-time hard attention at test time.The expected and hard procedures coincide when selection probabilities are binary, motivating probabilities near 0 or 1.
- 2.4. Modified Energy Function: The modified energy function adds an offset r and weight normalization through g to stabilize sigmoid-based monotonic decisions, with negligible parameter overhead.The offset addresses sigmoid shift sensitivity, while weight normalization addresses sensitivity to the energy scale.
- 2.5. Encouraging Discreteness: The paper combines these components into a differentiable monotonic alignment decoder whose test-time decoding is deterministic.The training algorithm uses the expected process, while test-time decoding omits pre-sigmoid noise.
3. Related Work
Prior work explores monotonic or locally restricted attention to reduce computation and support online decoding, using reinforcement learning, dynamic programming, fixed or learned windows, and chunking. The proposed approach differs from these methods in its adaptive ingest/emit formulation and ability to produce output sequences longer than the input.
- Reinforcement-learning approaches preserve discrete ingest-or-emit decisions during training but were not found reliable across the authors’ different tasks.These methods differ from the paper’s expectation-based training procedure.
- CTC, RNN Transducer, and related models support monotonic alignment by adding null, shift, or emit operations to represent output timing.These approaches assume particular output-symbol or segmentation structures.
- Subsampling-based attention also uses dynamic programming for expected outputs, whereas this approach uses an RNN decoder and permits output sequences longer than the input.The distinction concerns both decoder structure and allowable output length.
- Sliding-window attention reduces runtime by restricting computation to local memory regions, but it relies on strong assumptions about subsequent attention locations or learns a window policy.Both fixed monotonic windows and decoder-state-dependent window centers have been studied.
- Other work interprets soft attention or online chunking probabilistically, but does not formulate left-to-right addressing as the paper does or uses fixed chunk sizes.The paper’s ingest/emit probabilities can instead adaptively chunk the input sequence.
4. Experiments
The experiments evaluate monotonic attention on sentence summarization, machine translation, and online speech recognition, using task-specific datasets and metrics. Results are competitive with softmax attention and other online methods, while qualitative analyses examine alignment behavior.
- Experimental setup: The evaluation covers sentence summarization, machine translation, and online speech recognition using Gigaword, IWSLT 2015 English-Vietnamese, TIMIT, and WSJ.The experiments use ROUGE for summarization, BLEU for translation, and phone or word error rate for speech recognition.
- Online speech recognition: On TIMIT, the model outperformed recently proposed sequence-to-sequence online methods, although dataset size and result variability limit claims that any approach is best.CTC still outperformed all sequence-to-sequence models, and offline bidirectional systems achieved lower reported phone error rates.
- Online speech recognition: On WSJ, hard monotonic decoding achieved significantly lower WER than other online methods and only a 1.4% WER decrease versus an otherwise identical softmax-attention baseline.The baseline is quadratic-time and offline, whereas the monotonic model is substantially more efficient.
- Sentence summarization: On Gigaword summarization, the monotonic model substantially outperformed existing models but fell slightly behind the Liu and Pan (2016) soft-attention baseline.The authors partly attribute the strongest scores to encoders with roughly twice as many layers as most literature baselines.
- Sentence summarization: In qualitative summarization examples, hard monotonic attention produced reasonable early alignments but unexpected later alignments, while soft attention remained soft and non-monotonic.The authors suggest bidirectional encoder representations can reorder input information, helping monotonic decoding produce reordered phrases.
- Machine translation: In translation, monotonic attention generally focused later than soft attention to handle phrase reordering with a unidirectional encoder, coinciding with a small BLEU decrease.The authors hypothesize that focusing on phrase-final words compensates for limited encoder context during reordered translations.
5. Discussion
The paper concludes that differentiable hard monotonic attention supports efficient online decoding with little performance loss. Training uses expected outputs to retain standard backpropagation while test-time decoding follows a hard monotonic process.
- The approach enables efficient online decoding at test time without substantial performance loss across a wide variety of tasks.
- Hard monotonic decoding scans memory entries from the previous stopping position until selecting an entry or exhausting the memory.
- The soft monotonic decoder computes attention probabilities over memory entries and forms a weighted context vector for each target timestep.
B. Figures
The figures compare hard monotonic and softmax attention alignments across speech, translation, and summarization examples. They also visualize how attention matrices and alignment differences are presented.
- Attention matrices use black for value 1 and white for value 0.
- Figure 4 places hard monotonic alignments, softmax alignments, and utterance feature sequences in top-to-bottom order.Dashed red circles mark alignment differences, while gaps correspond to ignoring speech silences and pauses.
- Figure 5 compares English inputs, Vietnamese predictions, and input-output alignments for monotonic and softmax attention models.The left example illustrates differing translations of the ambiguous input word “model.”
- Figure 6 shows an additional sentence-summary pair with attention alignment matrices for hard monotonic and softmax-based models.The ground-truth summary is “china attacks us human rights”.
C. Monotonic Attention Distribution
The monotonic attention distribution is derived by tracking the probability that each memory item is selected at each output timestep. A recurrence and parallel cumulative operations provide computationally useful forms of this distribution.
- α_i,j is the probability that memory element j is selected at output timestep i.For the first timestep, this combines selecting j with not selecting earlier memory elements.
- For later timesteps, α_i,j sums over prior attended positions k ≤ j while requiring that intervening memory entries are not selected.
- The recurrence can be computed from α_i−1,j and α_i,j−1, with α_0,j = δ_j recovering the initial special case.
- Defining q_i,j = α_i,j/p_i,j gives an intuitive decomposition into advancing from j−1 or remaining at j before selecting j.
- Figure 7 visualizes α_3,4 as four terms corresponding to the possible memory items attended at the previous output timestep.
- Parallel cumulative-sum and cumulative-product operations compute α_i efficiently, but the denominator product can cause numerical instability.
D. Experiment Details
The experiments use TensorFlow models with recurrent and convolutional encoders, attention-based decoders, and specified optimization and decoding procedures. Speech inputs are normalized, downsampled, and regularized during training.
- All models were implemented with TensorFlow, and the section provides model and training details for the experiments.
- One speech configuration uses standardized mel filterbank features, a three-layer unidirectional LSTM encoder, and hidden-state downsampling between layers.
- Training uses Adam with gradient clipping, learning-rate schedules, minibatches, regularization, and beam-search decoding.The configurations specify label smoothing and distinct beam-search pruning settings.
- Another speech configuration organizes mel filterbank, delta, and delta-delta features into a T × 80 × 3 tensor before convolutional downsampling.
- The convolutional encoder feeds a convolutional LSTM and three unidirectional LSTM layers with linear projection, batch normalization, and ReLU activation.
- Decoder inputs concatenate previous-symbol embeddings with attention context vectors before processing by a unidirectional LSTM.
D.2. Sentence Summarization
The sentence summarization experiments used recurrent encoder–decoder models with specified dimensions, optimization settings, and beam-search decoding. Data preparation retained only the article’s first sentence and selected a 200,000-token vocabulary.
- Data preparation: The summarization input consisted only of each article’s first sentence, tokenized by spaces, with a 200,000-token vocabulary.Tokens were embedded in a 200-dimensional space with small random-normal initialization.
- Model: The model used a four-layer bidirectional LSTM encoder and a single-layer unidirectional LSTM decoder, with 256-dimensional hidden states.The decoder fed directly into the softmax output layer.
- Decoding: The monotonic alignment decoder initialized its scalar bias r to -4 and used beam search with width 4 at test time.
- Optimization: Training used batch size 64, sampled-softmax cross-entropy with 4,096 negative samples, Adam, learning-rate decay, gradient clipping, and validation-based early stopping.The initial learning rate was 10^-3 and gradients were clipped at global norm 2.
- Comparison configuration: A comparison configuration followed Luong and Manning closely, using 512-dimensional embeddings and two unidirectional LSTM layers in both encoder and decoder.The comparison model used minibatches of 128 and trained for 40 epochs with Adam.
E. Future Work
The paper identifies training complexity, scaling failures, and strict monotonicity as limitations, while proposing extensions for local or broader non-monotonic alignments and more efficient attention computation.
- Limitations: Training in expectation retains quadratic complexity because it computes the expected output with a cumulative-product algorithm.The paper suggests thresholded-remainder methods or gradient estimators for discrete decisions as alternatives.
- Limitations: The method can fail when attention energies are poorly scaled, primarily because monotonicity is enforced strictly.A soft penalty discouraging non-monotonic alignments is proposed as a possible mitigation.
- Non-monotonic alignments: Subtracting an integer from the previous alignment position or using parallel monotonic mechanisms could accommodate localized or disparate non-monotonic alignments.
- Efficiency extensions: A recurrent attention energy function could exploit the efficiency of the decoding process more fully than the primarily parallelizable function used for comparison.
F. How much faster is linear-time decoding?
The experiment isolated attention-computation cost by comparing efficiently implemented softmax and hard monotonic mechanisms across sequence lengths. Hard monotonic attention was substantially faster, especially when outputs were long relative to inputs.
- Experimental design: The experiment measured attention mechanisms alone to isolate their computational-cost difference.The comparison used efficiently implemented softmax-based and hard monotonic attention mechanisms.
- Experimental design: Both mechanisms were implemented with Eigen, random memory and decoder states, and varying input and output sequence lengths.Context vectors were computed using the respective attention procedures and execution times were averaged.
- Results: 4–40× speedup was observed for monotonic attention over softmax attention, depending on input and output sequence lengths.The largest difference occurred with short inputs and long outputs, where monotonic attention could stop computing context vectors after processing the input.
G. Practitioner’s Guide
The practitioner guidance covers numerical stability, initialization, convergence, assumptions, and monitoring. It reports competitive performance across studied tasks while noting that training and alignment behavior require care.
- Numerical stability: 26 was replaced with log-space computation because automatic-differentiation packages can produce unstable cumulative-product gradients.
- Numerical stability: 10^-10 was used to clip a potentially tiny denominator, though this can make α_i,j inaccurate when p_i,j is near 1.The authors report no discernible effect on their results.
- Numerical stability: Setting the denominator to 1 also produced good preliminary results when all p_i,j values were encouraged toward 0 or 1.
- Initialization: Initial scalar-bias values from {-5, -4, -3, -2, -1} produced small performance gains across different problems, although performance was generally insensitive to this parameter.
- Convergence: Attention-energy modifications were necessary for summarization convergence but made no performance difference in the speech-recognition experiments.The authors recommend starting with the standard energy function and applying modifications if attention is not utilized.
- Assumptions: Reversing the input sequence violates the left-to-right processing assumption and should therefore be avoided.
- Monitoring: Visualizing α_i,j during training can expose failure modes such as all-zero attention alignments.
- Observed outcome: Competitive performance was achieved after replacing softmax-based attention with the proposed mechanism on all studied problems.