PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Sequence-to-Sequence Models

Ben Peters, Vlad Niculae, André F. T. Martins

arXiv:1905.05702v2cs.CLcs.LG

TL;DR

Dense softmax-based seq2seq models produce nonzero attention and output probabilities everywhere, limiting sparsity and interpretability. The paper replaces softmax with α-entmax transformations and supplies efficient computation methods. Sparse models consistently improve over dense models on morphological inflection and machine translation while enabling interpretable distributions and, sometimes, exact beam search.

  • Problem

    Conventional seq2seq models use softmax for attention and output, yielding dense alignments and nonzero probability for every vocabulary type.

  • Method

    The paper replaces softmax in attention and output layers with α-entmax transformations, supported by efficient exact and approximate algorithms.

  • Results

    Sparse seq2seq models produce consistent improvements over dense models on morphological inflection and machine translation, with interpretable attention and output distributions.

  • Takeaways & Limitations

    Sparse outputs can restrict probability to plausible hypotheses and provide exact beam-search decoding when the beam covers all nonzero-probability hypotheses.

  • Takeaways & Limitations

    Exact algorithms may not be available for general α, although the paper investigates a GPU-friendly approximate algorithm for arbitrary α.

Abstract

from arXiv · show

Sequence-to-sequence models are a powerful workhorse of NLP. Most variants employ a softmax transformation in both their attention mechanism and output layer, leading to dense alignments and strictly positive output probabilities. This density is wasteful, making models less interpretable and assigning probability mass to many implausible outputs. In this paper, we propose sparse sequence-to-sequence models, rooted in a new family of $α$-entmax transformations, which includes softmax and sparsemax as particular cases, and is sparse for any $α> 1$. We provide fast algorithms to evaluate these transformations and their gradients, which scale well for large vocabulary sizes. Our models are able to produce sparse alignments and to assign nonzero probability to a short list of plausible outputs, sometimes rendering beam search exact. Experiments on morphological inflection and machine translation reveal consistent gains over dense models.

1 Introduction

Conventional seq2seq models use dense softmax attention and output probabilities, while this paper introduces sparse α-entmax alternatives for more focused alignments and plausible outputs. Experiments report accuracy and interpretability benefits, with sparse outputs sometimes making beam search exact.

  • Softmax assigns positive values to every attention position and vocabulary type, producing dense alignments and output distributions.
  • α-entmax replaces softmax in attention and output layers, includes softmax at α = 1 and sparsemax at α = 2, and is sparse for every α > 1.
  • Sparse attention focuses on relevant source words and makes alignments more interpretable, while sparse output probabilities restrict support to a finite subset of possible strings.
  • Sparse output probabilities can yield short lists of plausible sequences that are fully covered by the beam, rendering beam search exact in some cases.
  • Fast exact algorithms are provided for 1.5-entmax, alongside a GPU-friendly approximate algorithm for arbitrary α.
  • Experiments on morphological inflection and machine translation show clear benefits in both accuracy and interpretability.

2 Background

The paper studies an RNN-based attention seq2seq architecture in which softmax computes normalized attention weights and next-word probabilities. Its dense distributions never assign zero probability, motivating alternatives that can exclude irrelevant inputs and unlikely outputs.

  • The underlying model is an RNN-based seq2seq system with global attention and input-feeding.
  • The encoder embeds the input and processes it with bidirectional LSTMs to produce encoder states.
  • At each decoding step, the attention mechanism uses the decoder state to score encoder states and form a focused summary.
  • The decoder generates tokens autoregressively, feeding its contextual output and predicted-token embedding into the next LSTM step.
  • Softmax maps score vectors to probability distributions for both normalized attention weights and predictive next-word probabilities.
  • Because softmax outputs are always positive, it cannot fully exclude unimportant input tokens or unlikely vocabulary words.

3 Sparse Attention and Outputs

The section develops α-entmax as a family of sparse mappings and losses connecting softmax with sparsemax, then provides differentiable formulations and efficient computation methods for seq2seq use.

  • 3.1 The sparsemax mapping and loss: Sparsemax replaces softmax with a simplex projection that can assign exactly zero probability to low-scoring choices.
  • 3.2 A new entmax mapping and loss family: Tsallis α-entropies yield entmax mappings that continuously interpolate between softmax at α = 1 and sparsemax at α = 2.For all α > 1, entmax tends to produce sparse probability distributions.
  • 3.2 A new entmax mapping and loss family: Entmax losses are convex and differentiable, with zero loss when the correct score exceeds every competing score by 1/α−1.At that separation, the optimal distribution is the one-hot vector for the correct class.
  • 3.2 A new entmax mapping and loss family: Entmax mappings retain sparsemax’s sparsity while providing smoother, differentiable curvature for 1 < α < 2.Sparsemax is piecewise linear, whereas intermediate mappings have smooth corners.
  • 3.3 Computing the entmax mapping: The mapping is computed by finding a unique threshold τ; bisection provides a general method, while sorting-based methods support exact computation for special α values.The paper gives an exact algorithm for 1.5-entmax and investigates approximate GPU-friendly computation for arbitrary α.
  • 3.4 Gradient of the entmax mapping: The entmax backward pass recovers softmax and sparsemax Jacobians at α = 1 and α = 2, while other α values produce gradients that depend on probability magnitudes.For sparsemax, the Jacobian depends only on the support; this is not true when α ≠ 2.

4 Experiments

Experiments evaluate entmax-based sequence-to-sequence models on morphological inflection and machine translation, comparing softmax, sparsemax, and 1.5-entmax under shared architectures. The models improve accuracy while producing sparse outputs and interpretable alignments, with sparse supports sometimes certifying exact beam-search decoding.

  • Experimental setup: Experiments cover character-level morphological inflection, where exact sequence matches are required, and word-level machine translation, where larger vocabularies create greater output ambiguity.The study uses high- and medium-resource multilingual inflection data plus German–English and Romanian–English translation in both directions.
  • Morphological inflection: Nearly 1 percentage point ensemble gains over softmax were achieved in morphological inflection, with up to 2.5-point gains in the medium setting without ensembling.The choice of attention had a smaller impact than the sparse loss.
  • Morphological inflection: 81% of high-setting and 66% of medium-setting validation samples concentrated all probability mass into a single predicted sequence.When multiple sequences received mass, predictions reflected reasonable ambiguity.
  • Morphological inflection: 87% of high-setting and 79% of medium-setting validation sequences permitted globally optimal beam-search decoding because the beam covered all nonzero-probability hypotheses.This provides an optimality certificate for those sequences.
  • Machine translation: 1.5-entmax consistently achieved the best BLEU across all six translation language-pair directions, while a fine-grained search found an output-loss optimum around α = 1.33.Sparser attention had only a small positive accuracy effect, whereas the loss-function α had a more visible impact.
  • Machine translation: 1.5-entmax assigned positive probability to only 16.13 target types out of a 17,993-word vocabulary on DE→EN validation data.Its support concentrated for phrases such as “the tree of life” and expanded for synonym lists, while Algorithm 2 ran near softmax speed.

5 Related Work

The paper situates sparse attention and output probabilities within efforts to make seq2seq models more selective, interpretable, and efficient for large vocabularies.

  • Sparse attention: Sparse attention targets the expectation that only a few source words are relevant for each translated word.
  • Sparse attention: Unlike hard attention, entmax is differentiable and functions as an easy-to-use drop-in replacement for softmax.
  • Losses for seq2seq models: Prior work on seq2seq losses replaces cross-entropy with alternative losses or approximations, often motivated by large vocabulary sizes.
  • Losses for seq2seq models: The paper connects sparse losses with existing strategies such as hierarchical prediction for seq2seq models.

6 Conclusion and Future Work

The paper concludes that sparse seq2seq models improve performance and interpretability while enabling fast transformations and exact decoding in suitable cases. It identifies self-attention and other concentrated-probability tasks as future applications.

  • Conclusion: Sparse seq2seq models yield consistent improvements over dense models on morphological inflection and machine translation.
  • Conclusion: Fast algorithms compute the models’ attention and output transformations.
  • Conclusion: Sparse attention and output distributions induce interpretability in both components.
  • Conclusion: Sparse output layers provide exactness when the number of possible hypotheses does not exhaust beam search.
  • Future work: Applying entmax to self-attention and to tasks with concentrated probability, such as speech recognition, is proposed as future work.

A.1 Tsallis entropies

This appendix establishes the α ≥ 1 Tsallis entropy formulation used in the paper and verifies its limiting behavior as α approaches 1.

  • Tsallis entropies: The appendix recalls the Tsallis entropy family for α ≥ 1 as groundwork for constructing α-entmax.
  • Limit proof: To evaluate the α → 1 limit, the proof defines f(α) and g(α), whose values at α = 1 form an indeterminate 0/0 case.
  • Limit proof: Differentiating f and g gives f′(α) = −t^α log t and g′(α) = 2α − 1.

A.2 Fenchel-Young losses

The appendix formalizes regularized prediction functions and Fenchel–Young losses, then derives optimality and Jacobian properties needed to compute and differentiate sparse mappings such as α-entmax.

  • Definitions: A strictly convex regularization function defines a probabilistic prediction function mapping scores to a probability distribution.
  • Definitions: Fenchel–Young loss combines score vectors, ground-truth labels, and regularized probabilistic predictions into a loss function.
  • Definitions: The chosen Tsallis entmax mapping and loss correspond to α-entmax and its associated Lα loss.
  • Loss properties: Fenchel–Young losses are convex in scores and equal zero exactly when the prediction matches the ground-truth label.
  • Optimality and Jacobians: The optimality conditions characterize the prediction solution and support algorithms for computing it and deriving its Jacobian.
  • Optimality and Jacobians: The resulting Jacobian analysis applies to α-entmax even when derivatives at zero may not exist.
  • Optimality and Jacobians: The Jacobian of a sparse prediction mapping is zero outside the solution’s support, while its nonzero entries are characterized on that support.
  • Optimality and Jacobians: For separable regularizers, the Jacobian simplifies because the Hessian is diagonal.

C.2 An exact algorithm for entmax with α = 1.5: Derivation of Algorithm 2.

The derivation gives an exact sorting-based algorithm for 1.5-entmax by characterizing solutions through their support size and induced threshold. It proves which support sizes are valid, establishes threshold monotonicity, and uses these properties to justify Algorithm 2.

  • Correctness: These results imply the correctness of Algorithm 2 for exact computation of 1.5-entmax.The proposition is explicitly used to establish the algorithm’s correctness after the supporting lemma on the threshold sequence.
  • Algorithm setup: The algorithm sorts z, defines top-ρ statistics, and seeks a support size whose threshold lies between z[ρ+1] and z[ρ].The optimal p is non-increasing after sorting, so its positive support can be represented by an index ρ.
  • Threshold derivation: For 1.5-entmax, the threshold is obtained from a quadratic equation derived from stationarity and primal feasibility, with the valid root selected by the support constraints.The positive root is ruled out by a contradiction with the threshold bound, leaving the admissible solution.
  • Correctness: The induced threshold τ(ρ) is non-decreasing, so any support size satisfying the interval condition produces the same optimal threshold τ⋆.The proof establishes τz(ρ) ≤ τz(ρ + 1) and then uses transitivity to obtain monotonicity.
  • Valid support domain: Finite thresholds exist exactly for support sizes 1 through ρmax, where ρmax is the largest index satisfying S(ρ) ≤ 1; larger supports yield infinite thresholds.The sequence S(ρ) is nondecreasing, which gives the contiguous valid domain.
Loading 1905.05702v2…