PaperlayerView exact revision on arXiv

Source-linked AI summary

A Regularized Framework for Sparse and Structured Neural Attention

Vlad Niculae, Mathieu Blondel

arXiv:1705.07704v3stat.MLcs.CLcs.LG

TL;DR

Softmax attention gives every input element a nonzero weight, while sparse attention leaves open how to encode structural priors. This paper develops a regularized-max framework for sparse and structured attention and algorithms for neural-network training. Its mechanisms improve interpretability while achieving comparable or better accuracy across three tasks.

  • Problem

    Softmax produces dense attention weights, while it remains open whether attention can exploit structural prior knowledge beyond sparse alternatives such as sparsemax [31].

    Source: §1 · pp. 1–2

  • Method

    A strongly convex regularized max operator yields a differentiable probability mapping, extended with fused-lasso and OSCAR penalties for structured attention.

    Source: §1 · p. 2

  • Results

    The proposed mechanisms enhance interpretability while achieving comparable or better accuracy on textual entailment, machine translation, and summarization.

    Source: §6 · p. 9

  • Takeaways & Limitations

    The paper demonstrates forward and backward computations for these mechanisms, supporting their use in neural networks trained by backpropagation.

    Source: §6 · p. 9

    The NeurIPS 2017 version misstated Proposition 2: composing P∆d and POSC gives only an approximation of oscarmax in general.

    Source: §1 · p. 2

Abstract

from arXiv · show

Modern neural networks are often augmented with an attention mechanism, which tells the network where to focus within the input. We propose in this paper a new framework for sparse and structured attention, building upon a smoothed max operator. We show that the gradient of this operator defines a mapping from real values to probabilities, suitable as an attention mechanism. Our framework includes softmax and a slight generalization of the recently-proposed sparsemax as special cases. However, we also show how our framework can incorporate modern structured penalties, resulting in more interpretable attention mechanisms, that focus on entire segments or groups of an input. We derive efficient algorithms to compute the forward and backward passes of our attention mechanisms, enabling their use in a neural network trained with backpropagation. To showcase their potential as a drop-in replacement for existing ones, we evaluate our attention mechanisms on three large-scale tasks: textual entailment, machine translation, and sentence summarization. Our attention mechanisms improve interpretability without sacrificing performance; notably, on textual entailment and summarization, we outperform the standard attention mechanisms based on softmax and sparsemax.

1 Introduction

Attention maps input elements to probabilities that guide neural networks’ predictions, but softmax assigns every element a nonzero weight and leaves open how to encode structural priors. The paper introduces a regularized-max framework for sparse and structured attention, with differentiable mechanisms and algorithms for neural-network training.

1 Introduction

  • The framework addresses the open question of whether attention can use structural prior knowledge, beyond the sparsity of sparsemax [31].Softmax produces dense weights, whereas sparsemax provides a sparse alternative.Source: §1 · pp. 1–2
  • The differentiable gradient of a strongly convex regularized max operator maps real values to probabilities, with softmax and a generalization of sparsemax as special cases.This provides a general framework for designing attention mechanisms.Source: §1 · p. 2
  • Fusedmax uses fused lasso to encourage attention to contiguous text segments, while oscarmax uses OSCAR to encourage equal attention to possibly non-contiguous word groups.OSCAR is offered for cases where the contiguity assumption is too strict.Source: §1 · p. 2
  • The paper derives Jacobian computations for the general framework, fused lasso, and OSCAR, addressing a requirement for using these optimization-defined mechanisms in autodiff toolkits.The attention itself and its Jacobian must both be computed.Source: §1 · p. 2
  • The framework’s mechanisms enhance interpretability while achieving comparable or better accuracy on textual entailment, machine translation, and sentence summarization.The introduction presents them as drop-in replacements for existing attention mechanisms.Source: §1 · p. 2
  • In the NeurIPS 2017 version, Proposition 2 incorrectly stated that composing P∆d and POSC equals oscarmax generally; it is only an approximation.The paper flags this as an erratum.Source: §1 · p. 2

2 Proposed regularized attention framework

The framework smooths the max operator so its gradient maps real-valued inputs to probabilities, avoiding the max operator’s discontinuous one-hot subgradient mapping. It recovers softmax and sparsemax as special cases and supports structured regularizers.

2.1 The max operator and its subgradient mapping

  • The max operator’s subgradients put all probability mass on one element, and this discontinuous mapping is unsuitable for gradient-descent optimization.The discontinuity appears as a Heaviside step function when x = [t, 0].Source: §2.1 · p. 3

2.2 A regularized max operator and its gradient mapping

  • Strongly convex regularization makes the smoothed max differentiable, with its gradient providing a Lipschitz-continuous mapping to the probability simplex.The mapping ΠΩ is the argument achieving the supremum; its Lipschitz constant is 1/(γβ) with respect to the dual norm.Source: §2.2 · pp. 3–4
  • Training requires both evaluating ΠΩ(x) and computing its Jacobian, equivalently the Hessian of the smoothed max.The paper presents algorithms for general differentiable regularizers and for fused lasso and OSCAR.Source: §2.2 · p. 4

2.3 Recovering softmax and sparsemax as special cases

  • Negative-entropy regularization recovers temperature-parameterized softmax as the gradient of the log-sum-exp smoothed max.The resulting operator is 1/γ-smooth with respect to the infinity norm.Source: §2.3 · p. 4
  • Squared Euclidean regularization recovers sparsemax, while its generalization uses γ to control sparsity, with smaller values producing sparser outputs.The experiments set γ = 1, following the literature.Source: §2.3 · p. 4

3 Deriving new sparse and structured attention mechanisms

The section develops differentiable regularizers and structured attention mappings, then gives forward and backward computation methods for them. Fusedmax groups adjacent weights, while oscarmax can group non-adjacent weights.

3.1 Differentiable regularizer Ω

  • For a differentiable regularizer, the mapping’s Jacobian is obtained by solving a linear system, and its Jacobian-vector product can be computed efficiently.The method differentiates a fixed-point iteration rather than applying matrix differential calculus to KKT conditions.Source: §3.1 · p. 5
  • The squared p-norm mapping recovers sparsemax at p = 2 and has a smoother transition between two extreme outputs when 1 < p < 2.The experiments use p = 1.5.Source: §3.1 · p. 5

3.2 Structured regularizers: fused lasso and OSCAR

  • For sequential inputs, fusedmax uses a fused-lasso penalty to encourage contiguous segments with equal attention weights.Its regularizer combines a squared L2 term with a 1-d total-variation penalty.Source: §3.2 · p. 5
  • When contiguity is too restrictive, oscarmax uses an OSCAR penalty to encourage equal-valued attention clusters regardless of sequence position.The penalty replaces fusedmax’s 1-d total-variation penalty with an infinity-norm penalty on pairs of weights.Source: §3.2 · p. 5
  • Fusedmax is computed exactly by composing the 1-d total-variation proximal operator with simplex projection, whereas the analogous oscarmax decomposition is not exact.The simplex indicator meets the stated condition for exact fusedmax composition but not for the oscarmax decomposition.Source: §3.2 · p. 6
  • The structured mappings’ backward passes use the chain rule and efficiently computed Jacobians, with differentiability except where groups change.At group-change points, the paper notes that Clarke’s Jacobian can be used, as with sparsemax.Source: §3.2 · p. 6

4 Experimental results

Across textual entailment, machine translation, and sentence summarization, the experiments test structured attention as a drop-in replacement for existing mechanisms. The reported results pair improved interpretability with comparable or better performance.

4 Experimental results

  • The experiments use established neural architectures to test structured sparse attention as a drop-in replacement for softmax across three natural-language tasks.The textual-entailment setup follows the implementation, hyperparameters, and grid search of [31]; the summarization setup reproduces comparable results to [39] with softmax.Source: §4 · p. 6, §4.1 · p. 7, §4.3 · p. 8

4.1 Textual entailment (a.k.a. natural language inference) experiments

  • On SNLI, fusedmax achieves the highest accuracy, oscarmax slightly outperforms softmax, and fusedmax highlights the meaningful segment “band is playing.”All four models correctly predict contradiction for the example, despite differing attention weights.Source: Table 1 · p. 7, §4.1 · p. 7

4.2 Machine translation experiments

  • Across 10 language pairs, all compared mechanisms stay within 1 BLEU point of the best, while fusedmax and oscarmax often yield more interpretable alignments and qualitatively different translations.In the illustrated French-to-English example, oscarmax finds a slightly more natural translation.Source: §4.2 · p. 7, Figure 4 · p. 8

4.3 Sentence summarization experiments

  • On sentence summarization, fusedmax is best under nearly all reported metrics and always outperforms softmax.Evaluation uses DUC 2004 and a randomly held-out Gigaword subset; Table 2 reports the results.Source: Table 2 · p. 8, §4.3 · p. 8

5 Related work

The related work positions the paper’s gradient-based attention framework against smoothed-max methods and existing approaches to interpretability and structure. Its distinction is producing sparse, structured attention weights with deterministic backpropagation-compatible mechanisms.

Smoothed max operators

  • Unlike prior smoothed-max work, the paper uses the gradient as a mapping to the simplex and studies its Jacobian for backpropagation through neural networks.The cited contrast is with works using regularized max operators for smoothed hinge losses or maximum-a-posteriori relaxations.Source: §5 · p. 8

Interpretability, structure and sparsity in neural networks

  • The paper aims to make attention-based interpretations more useful for accountability, error analysis, and exploration through structured sparse regularization.Prior work visualized hidden activations or noted attention’s interpretability potential.Source: §5 · p. 8
  • Compared with explanation generators and CRF marginal attention, the proposed mechanisms are deterministic replacements that produce sparse, clustered outputs.The explanation generator in [26] uses learned parameters and stochastic training; CRF marginals are generally dense and unequal.Source: §5 · pp. 8–9

6 Conclusion and future directions

The paper concludes that its regularized framework supports new attention mechanisms with forward and backward computations for neural networks trained by backpropagation. It presents fusedmax and oscarmax as interpretable mechanisms with comparable or better accuracy across three tasks, and identifies further applications for future study.

6 Conclusion and future directions

  • The unified regularized framework supports designing new attention mechanisms and computing their forward and backward passes for backpropagation.The paper demonstrates the computations for general differentiable regularizers.Source: §6 · p. 9
  • Fusedmax and oscarmax enhance interpretability while achieving comparable or better accuracy on textual entailment, machine translation, and summarization.Source: §6 · p. 9
  • The authors identify categorical sampling with the Gumbel trick, conditional computation, and differentiable neural computers as potential future uses of sparse or structured mappings.They state that these applications are planned for future exploration.Source: §6 · p. 9

A.1 Proof of Proposition 1

The proof excerpts use chain-rule differentiation to derive Jacobians and optimality conditions to express structured proximity operators in terms of their inputs. For the fused-lasso case, the derivation proceeds segment by segment.

A.1 Proof of Proposition 1

  • For Proposition 1, the proof applies the chain rule to the optimizer and its stationarity relation to derive the mapping’s Jacobian.The displayed shorthand identifies a projection Jacobian and a regularizer-Hessian term.Source: §A.1 · p. 12

A.2 Proof of Proposition 3

  • For the structured proximity operators, the proof differentiates explicit expressions where group structure is locally unchanged and allows a Clarke generalized gradient at nondifferentiable points.The proof outline identifies such points with changes in group structure.Source: §A.2 · pp. 12, 14
  • For the fused-lasso proximity operator, the proof eliminates auxiliary t_j variables and unrolls a recursion across each segment.The resulting calculation is applied to every segment of the solution.Source: §A.2 · p. 13

B Computational complexity and implementation details

The implementation builds the structured mechanisms from proximal operators and sparsemax, with different computational costs for forward and backward passes. A general solver handles other regularizers, and the visualizations show how the mappings produce fused weights.

B.1 Sparsemax

  • Sparsemax is a simplex projection computed in worst-case O(d log d) by sorting or expected O(d) by a pivot algorithm; its backward pass costs O(nnz(y⋆)).The implementation uses sorting.Source: §B.1 · p. 14

B.2 Fusedmax

  • Fusedmax composes the fused-lasso proximal operator with sparsemax; its forward pass is worst-case O(d^2), while its backward pass is O(d).The forward algorithm performs close to O(d) on realistic benchmarks.Source: §B.2 · p. 14

B.3 Oscarmax

  • Oscarmax composes the OSCAR proximal operator with sparsemax; its forward and backward passes each cost O(d log d).The forward pass uses sorting and isotonic regression; the backward pass uses a stable sort and a linear-time grouping pass.Source: §B.3 · p. 14

B.4 General case and sq-pnorm-max

  • For general mappings, FISTA is used; sq-pnorm-max has per-run forward complexity O(td log d) and backward complexity O(nnz(y∗)^3).Each FISTA iteration projects onto the simplex; the backward pass solves only the subset associated with nonzero forward weights.Source: §B.4 · pp. 14–15

C.1 Visualizing attention mappings in 3-d

  • The 3-d mappings show smoother transitions for sq-pnorm-max at p = 1.5 and plateaus and ridges where fusedmax and oscarmax weights fuse.The visualization uses γ = 1 and λ = 0.2.Source: Figure 5 · p. 15

C.2 Textual entailment results

The textual-entailment experiments use the SNLI dataset and build on a GRU-based attention model. Training follows the settings and methodology of [31].

Experimental setup

  • The model builds on [31]’s attention implementation, a variation of [38] using GRUs instead of LSTMs, with separate premise and hypothesis parameters.The hypothesis GRU is initialized with the premise GRU’s last state.Source: §C.2 · p. 15
  • Training uses fixed 300-dimensional GloVe vectors, ADAM at learning rate 3 · 10^-4 for 200 epochs, dropout 0.1, and an l2 coefficient selected from four stated values.The candidate coefficients are 0, 10^-4, 3 · 10^-4, and 10^-3.Source: §C.2 · p. 15

Dataset and preprocessing

  • The experiments use SNLI v1, with 549,367 training, 9,842 development, and 9,824 test sentence pairs after minimal preprocessing.Pairs with missing labels are skipped, and the provided tokenization is retained.Source: §C.2 · p. 15

C.3 Machine translation results

The machine-translation experiments use OpenNMT-py defaults and report BLEU results, timing, and attention visualizations. The supplied passages describe the attention mechanisms’ practical runtime and their selection of grammatical segments, but do not provide BLEU scores.

Experimental setup

  • The experiments use OpenNMT-py defaults, train for 13 epochs, and select the model snapshot with the highest validation accuracy for test scores and visualizations.The setup uses a unidirectional LSTM, 500-dimensional word vectors and hidden representations, and input-feeding.Source: §C.3 · pp. 15–16

Machine translation results

  • Sparsemax, fusedmax, and oscarmax are practical in OpenNMT-py translation, taking within 1.75x the training time of a softmax model on the GPU.The sparse mechanisms are implemented on the CPU, incurring memory copies in both directions, while the rest of the pipeline runs on the GPU.Source: Table 5 · p. 17
  • Fusedmax often selects meaningful grammatical segments in translation alignments, including “est consacré” and determiner-noun constructions.The examples are French-to-English attention alignments.Source: §C.3 · p. 18

C.4 Sentence summarization results

The summarization experiments report ROUGE results and visualize attention on validation examples. The supplied figure descriptions highlight fusedmax’s alignment behavior and differing summary lengths across examples.

Experimental setup and data

  • The experiments use the preprocessed Gigaword dataset and also report results without truncating outputs at 75 bytes.The study additionally reports on DUC-2003 and provides ROUGE-L precision and recall scores.Source: §C.4 · p. 20, Table 6 · p. 20, Table 7 · p. 20

Sentence summarization results

  • Fusedmax’s 1-d TV prior aligns long input spans with single expressive words, an intuition supported by ROUGE scores.The passage does not provide the ROUGE values.Source: Figure 8 · p. 21
  • In one example, fusedmax recovers a longer but arguably better summary by identifying a separate important part of the input sentence.This is a qualitative judgment from the figure description.Source: Figure 8 · p. 22
  • In another example, fusedmax and oscarmax produce considerably shorter summaries.The figure description does not report quantitative scores for this example.Source: Figure 8 · p. 23

Related papers

Loading 1705.07704v3…