PaperlayerView exact revision on arXiv

Source-linked AI summary

From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification

André F. T. Martins, Ramón Fernandez Astudillo

arXiv:1602.02068v2cs.CLcs.LGstat.ML

TL;DR

The paper addresses the limitation that softmax always produces full-support distributions when sparse probabilities are desirable. It introduces sparsemax and a corresponding convex loss, then evaluates them in multi-label classification and attention-based natural language inference, where attention achieves similar performance to softmax with a more selective focus.

  • Problem

    Softmax always assigns nonzero probability to every output, limiting applications that require sparse probability distributions.

  • Method

    The paper introduces sparsemax, derives an efficiently computable Jacobian, and proposes a smooth, convex sparsemax loss analogous to logistic loss.

  • Results

    Sparsemax obtains empirical results in multi-label classification and natural language inference, with attention achieving similar performance to softmax while using a more selective, compact focus.

  • Takeaways & Limitations

    Sparsemax provides sparse label posteriors and differentiable selective attention while retaining important softmax properties.

  • Takeaways & Limitations

    Sparsemax may be less GPU-friendly than softmax because its computation requires sorting or linear-selection algorithms.

Abstract

from arXiv · show

We propose sparsemax, a new activation function similar to the traditional softmax, but able to output sparse probabilities. After deriving its properties, we show how its Jacobian can be efficiently computed, enabling its use in a network trained with backpropagation. Then, we propose a new smooth and convex loss function which is the sparsemax analogue of the logistic loss. We reveal an unexpected connection between this new loss and the Huber classification loss. We obtain promising empirical results in multi-label classification problems and in attention-based neural networks for natural language inference. For the latter, we achieve a similar performance as the traditional softmax, but with a selective, more compact, attention focus.

1. Introduction

The paper introduces sparsemax as a softmax alternative that produces sparse probabilities while retaining key computational and optimization properties. It develops the transformation, its efficient Jacobian, a convex sparsemax loss, and applications to multi-label classification and selective attention.

  • Motivation: Sparsemax can assign exactly zero probability to some outputs, supporting filtering, multi-label prediction, and more interpretable relevance selection.This contrasts with softmax's full-support distributions, which may require thresholding small probabilities to zero.
  • Sparsemax transformation: The paper formalizes sparsemax, derives its properties, and shows efficient evaluation through a threshold that shifts selected coordinates while truncating others to zero.A naïve evaluation algorithm runs in O(K log K).
  • Optimization: The sparsemax Jacobian is derived and reported to enable faster gradient backpropagation than the softmax case.
  • Sparsemax loss: The sparsemax loss is a smooth, convex analogue of logistic loss and a multi-class generalization of the Huber classification loss.
  • Applications: Sparsemax loss is applied to train multi-label linear classifiers on benchmark datasets, while sparsemax attention is evaluated on natural language inference with encouraging results.

2. The Sparsemax Transformation

Sparsemax maps real-valued scores to probability distributions through Euclidean projection onto the simplex, producing exact zeros while retaining several softmax-like properties. Its support-based structure enables efficient evaluation and Jacobian-vector computation for gradient-based models.

  • Definition: Sparsemax projects an input score vector z onto the probability simplex, and the projection can land on the boundary to produce sparse distributions.This contrasts with softmax, whose output has full support.
  • Evaluation: Sparsemax evaluation uses a threshold: coordinates above it are shifted, while the remaining coordinates are truncated to zero.A naïve implementation sorts the K coordinates and runs in O(K log K); linear-time algorithms are also available.
  • Basic properties: Sparsemax shares softmax invariance to constant shifts and permutations, and it has the same zero-temperature limit behavior without requiring an arbitrarily small temperature.For sparsemax, the limiting distribution on maximal components holds for a finite temperature range determined by the score gap.
  • Basic properties: In the binary case, sparsemax becomes a hard sigmoid, with output 0 below t = −1, (t + 1)/2 for −1 ≤ t ≤ 1, and 1 above t = 1.The resulting transformation is piecewise linear and asymptotically similar to softmax in the illustrated two- and three-dimensional cases.
  • Jacobian: The sparsemax Jacobian is defined away from support-splitting points and depends on the active support S(z), whose elements form a fully connected graph.Once sparsemax has been evaluated, the nonzero Jacobian-vector product can be computed in O(|S(z)|) time, which may be sublinear when K is large.

3. A Loss Function for Sparsemax

The paper develops the sparsemax loss as a differentiable, convex analogue of logistic loss that supports sparse posterior distributions. It establishes key theoretical properties, connects the binary case to Huber classification loss, and generalizes the loss to sparse label proportions and multi-label classification.

  • 3. A Loss Function for Sparsemax: The sparsemax loss is introduced to resemble logistic loss while allowing sparse posterior distributions.It is applied to label proportion estimation and multi-label classification.
  • 3.2. Sparsemax Loss: The loss is constructed as a differentiable function whose gradient matches the sparsemax prediction minus the gold-label distribution.The gradient is directly relevant to model updates in gradient-based optimization.
  • 3.2. Sparsemax Loss: The sparsemax loss is everywhere differentiable, convex, nonnegative, and invariant to adding the same constant to every score.These properties are stated in Proposition 3, alongside its gradient expression.
  • 3.2. Sparsemax Loss: Zero loss occurs exactly when the sparsemax output is the gold-label delta distribution, equivalently when unit-margin separation holds.The condition is zk ≥ 1 + maxj≠k zj.
  • 3.3. Connection to Huber Classification Loss: In the binary case, the sparsemax loss reduces to the Huber classification loss, also known as the modified Huber loss.Its continuity is preserved at the boundary where the support size changes.
  • 3.4. Generalization to Multi-Label Classification: The loss is generalized from single labels to sparse target distributions and non-empty sets of labels for multi-label classification.This framework subsumes single-label classification when each target distribution is concentrated on one class.

4. Experiments

The experiments evaluate sparsemax for label proportion estimation, multi-label classification, and neural attention. Sparsemax improves estimation when documents are sufficiently long, performs slightly better overall on benchmark classification, and matches or slightly exceeds soft attention in natural language inference.

  • The experiments cover label proportion estimation, multi-label classification, and attention-based natural language inference.
  • Label Proportion Estimation: Sparsemax and logistic losses perform similarly for short documents, but sparsemax consistently outperforms logistic loss beyond 400 words.The improvement occurs for both uniform and random mixtures and reduces mean squared error and Jensen-Shannon divergence.
  • Label Proportion Estimation: Sparsemax correctly identifies label-proportion support under stronger signals, reducing both mean squared error and Jensen-Shannon divergence.
  • Multi-Label Classification: Sparsemax attained the highest results in 4 of 10 benchmark multi-label classification experiments, compared with 3 wins each for logistic and softmax.Overall, the three losses performed very similarly, with sparsemax appearing better suited to problems with larger numbers of labels.
  • Neural Networks with Attention: The natural language inference comparison uses NOATTENTION, LOGISTICATTENTION, SOFTATTENTION, and SPARSEATTENTION systems built from recurrent networks.SPARSEATTENTION replaces the softmax attention mechanism with sparsemax.
  • Neural Networks with Attention: Soft and sparse attention perform similarly, with sparse attention slightly more accurate on the test set, and both outperform no-attention and logistic-attention systems.

5. Conclusions

The paper introduces sparsemax as a sparse alternative to softmax, develops its differentiable optimization machinery and loss, and reports empirical support across classification and attention tasks. Its sparse outputs also motivate interpretable and selectively focused neural architectures, including potential applications to memory and hierarchical attention.

  • 5. Conclusions: Sparsemax outputs sparse probability distributions while retaining properties similar to softmax.The paper emphasizes exact zero probabilities as useful for filtering, multi-label prediction, and interpretability.
  • 5. Conclusions: The paper derives a closed-form Jacobian for sparsemax and proposes a smooth, convex sparsemax loss for backpropagation.The Jacobian is presented as necessary for backpropagation, while the loss is described as a sparse analogue of logistic loss.
  • 5. Conclusions: Empirical results support sparsemax in multi-label classification and attention networks for natural language inference.The conclusion reports empirical validation across both application settings.
  • 5. Conclusions: Sparsemax attention can select only a few variables, making it potentially relevant to neural architectures with random access memory.The paper frames this as a future research direction rather than an established result.
  • 5. Conclusions: Sparsemax offers a differentiable compromise between soft and hard attention, while hierarchical products of sparse distributions can automatically prune hierarchies.The paper also notes a possible GPU-friendliness disadvantage because sparsemax may require sorting or linear-selection algorithms.

A.1. Proof of Prop. 1

The proof derives sparsemax’s thresholded support structure from the optimization problem’s KKT conditions. Positive coordinates share a common threshold relation, while non-support coordinates lie at or below that threshold.

  • A.1. Proof of Prop. 1: The proof begins from the Lagrangian and KKT conditions of sparsemax’s optimization problem.These conditions characterize the optimal probability vector, multipliers, and threshold.
  • A.1. Proof of Prop. 1: For supported coordinates, the optimal probabilities satisfy p*_i = z_i − τ*.The support is defined as S(z) = {j | p*_j > 0}.
  • A.1. Proof of Prop. 1: Summing the supported coordinates yields the threshold expression used in sparsemax’s closed-form solution.The normalization condition over S(z) produces the right-hand side of Eq. 4.
  • A.1. Proof of Prop. 1: For coordinates outside the support, complementary slackness implies z_i ≤ τ*.This identifies the inactive coordinates as those whose inputs do not exceed the threshold.
  • A.1. Proof of Prop. 1: The number of active coordinates equals the support size k(z) = |S(z)|.The proof obtains this equality from the characterization of supported and nonsupported coordinates.

A.2. Proof of Prop. 2

The proof establishes sparsemax’s stated properties using symmetry, scaling, translation invariance, and coordinate comparisons. It contrasts these arguments with corresponding softmax properties and analyzes sparsemax through thresholding cases.

  • A.2. Proof of Prop. 2: Coordinate symmetry establishes one of the properties and supports the uniform-distribution case.The proof states that the same symmetry argument handles the first part of the first property.
  • A.2. Proof of Prop. 2: For peaked distributions on maximal components, the proof uses t = ϵ^-1 and the scaling relation γ(tz) = tγ(z).For sparsemax, the support size becomes |A(z)| when γ(tz) ≥ 1/|A(z)|.
  • A.2. Proof of Prop. 2: Sparsemax is translation-invariant because shifting z by c1 changes squared distances by only a constant over the simplex.The proof explicitly uses 1^⊤p = 1 to establish this distance relation.
  • A.2. Proof of Prop. 2: Coordinate monotonicity states that z_i ≤ z_j implies sparsemax_i(z) ≤ sparsemax_j(z).The sparsemax proof proceeds by contradiction using its minimum-distance characterization over the simplex.
  • A.2. Proof of Prop. 2: The pairwise output difference is analyzed through three thresholding cases for two coordinates.Depending on which coordinates are truncated, the difference is expressed using the input difference and the threshold τ(z).

A.3. Proof of Prop. 3

The proof characterizes sparsemax’s Jacobian and sparsemax loss through support-based expressions. It establishes the loss gradient, convexity, translation behavior, and the condition for a one-hot minimizer.

  • A.3. Proof of Prop. 3: The sparsemax gradient is ∇_z L_sparsemax(z; k) = −δ_k + sparsemax(z).The expression follows from the support-based derivative calculation.
  • A.3. Proof of Prop. 3: The loss Hessian is a support-restricted matrix with entries δ_ij − 1/|S(z)| on the active support.It is zero outside the support coordinates.
  • A.3. Proof of Prop. 3: The Hessian is positive semidefinite, establishing convexity of L_sparsemax.Its rank is |S(z)| − 1 after padding zeros for inactive coordinates.
  • A.3. Proof of Prop. 3: The loss is invariant to adding c1 to z.The proof begins this claim with the identity L_sparsemax(z + c1) = −z_k − c + 1.
  • A.3. Proof of Prop. 3: The loss has a one-hot minimum exactly when z_k ≥ 1 + max_{j≠k} z_j.This follows from the zero-gradient condition sparsemax(z) = δ_k and sparsemax’s bound on coordinate differences.
Loading 1602.02068v2…