Online and Linear-Time Attention by Enforcing Monotonic Alignments

Colin Raffel, Minh-Thang Luong, Peter J. Liu, Ron J. Weiss, Douglas Eck

TL;DR

This paper introduces a novel "hard monotonic attention" mechanism for sequence-to-sequence models that allows for online processing and linear time complexity during inference. This is achieved by enforcing a left-to-right alignment between input and output sequences, making it suitable for real-time applications like speech recognition without sacrificing performance compared to existing quadratic-time attention models.

What Problem Does This Paper Address?

Sequence-to-sequence models, particularly those using recurrent neural networks (RNNs) with attention, have revolutionized tasks like machine translation and speech recognition. However, a major limitation of standard "soft attention" is its quadratic time complexity ($O(TU)$, where T and U are input and output lengths) because it requires a full pass over the entire input sequence for each output element. This also prevents their use in "online" settings where outputs need to be generated as the input is being received. The paper addresses this by leveraging the observation that in many real-world problems, the alignment between input and output sequences is inherently monotonic (e.g., words in a sentence correspond to speech segments in order).

Methods

The core contribution is a "hard monotonic attention" mechanism. Instead of computing a weighted average over all input elements (soft attention), this method enforces a strict left-to-right progression. At each output step, the model scans the input sequence from where it left off in the previous step and decides whether to "ingest" a new input element or produce an output. This decision is made using a Bernoulli distribution, effectively creating a discrete choice.

To enable training with standard backpropagation, the authors propose training with the expected output of this monotonic process. This involves computing attention energies and probabilities similar to soft attention but using a recurrence relation to derive the monotonic attention distribution. For inference (test time), they use the "hard" decision-making process, which is linear in time. They also introduce modifications to the attention energy function to encourage the desired discrete probabilities and improve stability.

Datasets

The paper evaluates its approach on the following datasets:

  • TIMIT: For online speech recognition.
  • Wall Street Journal (WSJ): For speech recognition.
  • Gigaword corpus: For sentence summarization.
  • TED talks (IWSLT 2015): For English-Vietnamese machine translation.

Key Insights and Ideas

  • Monotonicity as a Constraint: The key insight is that many sequence-to-sequence tasks exhibit a natural left-to-right alignment, and enforcing this monotonicity can unlock significant computational benefits.
  • Hard vs. Soft Attention for Inference: While soft attention is useful for training and providing probabilistic alignments, a "hard" monotonic decision at inference time is crucial for achieving linear complexity and online processing.
  • Training in Expectation: The ability to train a hard, discrete decision process using differentiable methods by optimizing its expected output is a critical enabler for this approach.
  • Online Processing is Achievable: The proposed method directly addresses the "online" requirement, which is impossible with standard soft attention.

Key Results

  • Speech Recognition: Achieved competitive phone error rates (PER) on TIMIT and word error rates (WER) on WSJ, with the hard monotonic attention model outperforming other online approaches and being only slightly worse than offline softmax attention.
  • Sentence Summarization: The hard monotonic attention model achieved strong ROUGE F-measure scores, falling slightly behind a baseline but demonstrating effectiveness on a task with less strict monotonicity.
  • Machine Translation: The model achieved competitive BLEU scores for English-Vietnamese translation, with qualitative analysis showing that the monotonic model sometimes focuses attention later in the input sequence to compensate for non-monotonic alignments.
  • Speedup: A synthetic benchmark demonstrated that the hard monotonic attention mechanism can be 4-40x faster than softmax attention, especially for short inputs and long outputs, due to its linear time complexity.

Limitations and Future Work

  • Training Complexity: While inference is linear, training in expectation still retains quadratic complexity. The authors suggest exploring gradient estimators like REINFORCE or the straight-through method for potentially faster training.
  • Non-Monotonic Alignments: The current approach strictly enforces monotonicity. For problems with only localized non-monotonicities, they suggest modifications like subtracting a constant from the starting index or using multiple parallel monotonic attention mechanisms.
  • Attention Energy Scaling: The method can be sensitive to the scaling of attention energies, especially with strict monotonicity. Regularizing with a soft penalty instead of outright prevention is proposed as a mitigation.
  • Recurrent Attention Energy: The authors believe there's potential to leverage the efficiency of the decoding process by using a recurrent attention energy function.

Summary updated

Abstract

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.
BibTeX
@inproceedings{raffel2017online,
  author = {Colin Raffel and Minh-Thang Luong and Peter J. Liu and Ron J. Weiss and Douglas Eck},
  title = {{Online and Linear-Time Attention by Enforcing Monotonic Alignments}},
  booktitle = {International Conference on Machine Learning},
  year = {2017},
  url = {https://openreview.net/forum?id=Bk-WK2WO-B},
}
Figure