From Sparse Modelingto Sparse Communication in NLP
André Martins

TALN Récital 2021
André Martins (IST)

Sparse Communication

TALN 2021

1 / 64

Our Amazing Team (December 2019, pre-COVID)

André Martins (IST)

Sparse Communication

TALN 2021

2 / 64

DeepSPIN

ERC starting grant (2018–23)
Topics: deep learning, structured prediction, NLP
More details: https://deep-spin.github.io

André Martins (IST)

Sparse Communication

TALN 2021

3 / 64

Natural Language Processing over TimeOld times: rule-based systems
Mid-90s (“empirical revolution”): statistical methods (HMMs, PCFGs, IBMmodels)André Martins (IST)

Sparse Communication

TALN 2021

4 / 64

Natural Language Processing over TimeOld times: rule-based systems
Mid-90s (“empirical revolution”): statistical methods (HMMs, PCFGs, IBMmodels)2000+: structured prediction, linear models with rich features (CRFs,
structured SVMs), feature engineering/selection

André Martins (IST)

Sparse Communication

TALN 2021

4 / 64

Natural Language Processing over TimeOld times: rule-based systems
Mid-90s (“empirical revolution”): statistical methods (HMMs, PCFGs, IBMmodels)2000+: structured prediction, linear models with rich features (CRFs,
structured SVMs), feature engineering/selection
Today: neural models, attention, transformers, ...

André Martins (IST)

Sparse Communication

TALN 2021

4 / 64

Natural Language Processing over TimeOld times: rule-based systems
Mid-90s (“empirical revolution”): statistical methods (HMMs, PCFGs, IBMmodels)2000+: structured prediction, linear models with rich features (CRFs,
structured SVMs), feature engineering/selection
Today: neural models, attention, transformers, ...

Structure, feature selection, and neural networks can go together!

André Martins (IST)

Sparse Communication

TALN 2021

4 / 64

Natural Language Processing over Time

(Slide from 2017)
André Martins (IST)

Sparse Communication

TALN 2021

5 / 64

Natural Language Processing over Time

(Slide from 2017)
André Martins (IST)

Sparse Communication

TALN 2021

5 / 64

Transformers Are Big Bulldozers

Very powerful, but highly overparametrized.

André Martins (IST)

Sparse Communication

TALN 2021

6 / 64

This Talk: Bet on Sparsity
What’s inside a bulldozer? Can we redesign its components?

Sparsity can be useful:for interpretability
for discovering linguistic
structurefor eﬃciency
for generating.

André Martins (IST)

Sparse Communication

TALN 2021

7 / 64

From Sparse Modeling ...
Mostly used with linear models, lots of work in the 2000s
Main idea: embed a sparse regularizer (e.g. `1 -norm) in the learning
objective
Irrelevant features get zero weight and can be discarded
Extensions to structured sparsity (group-lasso, fused-lasso, etc.)... to Sparse Communication:
Mostly used with neural networks, most work after 2015
Main idea: sparse neuron activations (biological plausibility)
Predictions are triggered by a few neurons only (input-dependent)
Example: ReLUs, dropout, sparse attention mechanisms

André Martins (IST)

Sparse Communication

TALN 2021

8 / 64

This Talk
An inventory of transformations that capture sparsity and structure:
All diﬀerentiable (eﬃcient forward and backward propagation)
Adaptively sparseCan be used at hidden or output layers
Eﬀective in many NLP tasks.
Building block:zp

Sparse transformations from the Euclidean space to the simplex 4.
André Martins (IST)

Sparse Communication

TALN 2021

9 / 64

Outline
1

Sparse Attention Mechanisms
Sparsemax and Entmax
Adaptively Sparse Transformers
Other Transformations

2Sparse Losses
Sparse Sequence-to-Sequence Models
Entmax Sampling3

Conclusions

André Martins (IST)

Sparse Communication

TALN 2021

10 / 64

Recap: Softmax and Argmax
Softmax exponentiates and normalizes:

exp(z)
softmax(z) = PK
k=1 exp(zk )Fully dense: softmax(z) > 0, ∀z
Used both as a loss function (cross-entropy) and for attention.

André Martins (IST)

Sparse Communication

TALN 2021

11 / 64

Recap: Softmax and Argmax
Softmax exponentiates and normalizes:

exp(z)
softmax(z) = PK
k=1 exp(zk )Fully dense: softmax(z) > 0, ∀z
Used both as a loss function (cross-entropy) and for attention.
Argmax can be written as:argmax(z) := arg max z > pp∈4=

lim softmax(z/τ )τ →0+(temperature trick)

Retrieves a one-hot vector for the highest scored index.

André Martins (IST)

Sparse Communication

TALN 2021

11 / 64

argmax(z)softmax(z)
1

1

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0

0

(Same z = [1.0716, −1.1221, −0.3288, 0.3368, 0.0425])

Argmax is an extreme case of sparsity, but it is discontinuous.
Is there a sparse and diﬀerentiable alternative?

André Martins (IST)

Sparse Communication

TALN 2021

12 / 64softmax(z)argmax(z)sparsemax(z)

1

1

1

0.8

0.8

0.8

0.6

0.6

0.6

0.4

0.4

0.4

0.2

0.2

0.2

0

0

0

(Same z = [1.0716, −1.1221, −0.3288, 0.3368, 0.0425])

Argmax is an extreme case of sparsity, but it is discontinuous.
Is there a sparse and diﬀerentiable alternative?

André Martins (IST)

Sparse Communication

TALN 2021

12 / 64

Sparsemax (Martins & Astudillo, 2016, ICML)
Euclidean projection of z onto the probability simplex 4:sparsemax(z) := arg min kp − zk2
p∈4

=

1
arg max z > p − kpk2 .
p∈4
2

Likely to hit the boundary of the simplex, in which case sparsemax(z)becomes sparse (hence the name)End-to-end diﬀerentiable
Forward pass: O(K logK ) or O(K ), (almost) as fast as softmax
Backprop: sublinear, better than softmax!

André Martins (IST)

Sparse Communication

TALN 2021

13 / 64

Sparsemax in 2D and 3D(Martins & Astudillo, 2016, ICML)

1.0

soft max1 ([t,0])
sparsemax1 ([t,0])

0.8

0.6

0.4

0.2

0.0
−3

−2

−1

0

1

2

3

t

Sparsemax is piecewise linear, but asymptotically similar to softmax.

André Martins (IST)

Sparse Communication

TALN 2021

14 / 64Ω-Regularized Argmax (Niculae & Blondel, 2017, NeurIPS)
For convex Ω, deﬁne the Ω-regularized argmax transformation:argmax Ω (z) := arg max z > p − Ω(p)p∈4

Argmax corresponds to no regularization, Ω ≡ 0

PK

i=1 pi logpi
1
2
Sparsemax amounts to `2 -regularization, Ω(p) = 2 kpk

Softmax amounts to entropic regularization, Ω(p) =Is there something in-between?

André Martins (IST)

Sparse Communication

TALN 2021

15 / 64

Entmax (Peters, Niculae & Martins, 2019, ACL)
Parametrized by α ≥ 0:(Ωα (p) :=



PK α
1
i=1 piα(α−1) 1 −PK
i=1 pi logpi



if α 6= 1
if α = 1.

Related to Tsallis generalized entropies (Tsallis, 1988).
Argmax corresponds to α → ∞Softmax amounts to α → 1
Sparsemax amounts to α = 2.
Key result: always sparse for α > 1, sparsity increases with α
Forward pass for general α can be done with a bissection algorithm
Backward pass runs in sublinear time.
André Martins (IST)

Sparse Communication

TALN 2021

16 / 64

Entmax in 2D (Peters, Niculae & Martins, 2019, ACL)

α = 1.5 is a sweet spot!
Eﬃcient exact algorithm (nearly as fast as softmax), smooth, and good
empirical performance.
Pytorch code: https://github.com/deep-spin/entmax
André Martins (IST)

Sparse Communication

TALN 2021

17 / 64

Sparse Transformations (Peters, Niculae & Martins, 2019, ACL)
α=1

α = 1.5α=2α=∞softmax(z)1.5-entmax(z)sparsemax(z)argmax(z)

1

1

1

1
0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0

0

0

0

(Same z = [1.0716, −1.1221, −0.3288, 0.3368, 0.0425])

André Martins (IST)

Sparse Communication

TALN 2021

18 / 64

Example: Sparse Attention for Machine Translation(Peters, Niculae & Martins, 2019, ACL)

Selects source words
when generating a target
word (sparse alignments)
Better interpretability
Can also model fertility:
constrained sparsemax(Malaviya, Ferreira & Martins,
2018, ACL)

André Martins (IST)

Sparse Communication

TALN 2021

19 / 64

Example: Sparse Attention for Explainability(Treviso & Martins, 2020, BlackboxNLP)ŷClassiﬁermExplainerỹ
Layperson

A classiﬁer makes a prediction
An “explainer” (embedded or not in the classiﬁer) generates a sparse
message that explains the classiﬁer’s decision
The layperson receives the message and tries to guess the classiﬁer’s
prediction (also called simulatability, forward simulation/prediction)
Communication success rate: how often the two predictions match?
André Martins (IST)

Sparse Communication

TALN 2021

20 / 64

From Sparse Modeling to Sparse Communication(Treviso & Martins, 2020, BlackboxNLP)

Wrappers

Model interpretability

Prediction explainability• Forward selection• Backward elimination (Kohavi &• Input reduction (Feng et al., 2018)• Erasure (leave-one-out) (Li et al.,John, 1997)

2016; Serrano & Smith, 2019)• LIME (Ribeiro et al., 2016)
Filters• PMI (Church & Hanks, 1990)• recursive feature elimination(Guyon et al., 2002)• Input gradient (Li et al., 2016)• LRP (Bach et al., 2015)• top-k softmax attention• Stochastic attention (Xu et al.,Embedded• `1 -regularization (Tibshirani, 1996)• elastic net (Zou & Hastie, 2005)

2015; Lei et al., 2016; Bastings et al.,2019)

• Sparse attention

André Martins (IST)

Sparse Communication

TALN 2021

21 / 64

Comparing Explainers(Treviso & Martins, 2020, BlackboxNLP)

SST

IMDB

AgNews

Yelp

SNLI

Clf.

Explainer

CSR

ACCL

CSR

ACCL

CSR

ACCL

CSR

ACCL

CSR

ACCL

C
C
C
C
Cent
Csp

RandomErasureTop-k gradientTop-k softmax
Top-k 1.5-entmax
Top-k sparsemax

69.41
80.12
79.35
84.18
85.23
85.23

70.07
81.22
79.24
82.43
83.31
81.93

67.30
92.17
86.30
93.06
93.32
93.34

66.67
88.72
83.93
89.46
89.60
89.57

92.38
97.31
96.49
97.59
97.29
95.92

91.14
95.41
94.86
95.61
95.67
94.48

58.27
78.72
70.54
81.00
82.20
82.50

53.06
68.90
62.86
70.18
70.78
70.99

75.83
77.88
76.74
78.66
80.23
82.89

68.74
70.04
69.40
71.00
73.39
74.76

Cent Selec. 1.5-entmax
Csp Selec. sparsemax
Cbern Bernoulli
Chk HardKuma

83.96
85.23
82.37
85.17

82.15
81.93
78.42
80.40

92.55
93.24
91.66
94.72

89.96
89.66
86.13
90.16

97.30
95.92
96.91
97.11

95.66
94.48
94.43
95.45

81.38
83.55
84.93
87.39

70.41
71.60
66.89
71.64

77.25
82.04
76.81
74.98

71.44
73.46
69.65
71.48

See paper for human experiments.
In general, attention > erasure  gradient methods (in terms of CSR).

André Martins (IST)

Sparse Communication

TALN 2021

22 / 64

Questions

Which α to choose?
The bigger the α, the higher propensity to sparsity.
What if we have many attention heads, and we don’t know how sparse
we want each one to be?
Can we learn α from data?

André Martins (IST)

Sparse Communication

TALN 2021

23 / 64

Transformer (Vaswani et al., 2017)
Attention in three places:
Self-attention in the encoder
Self-attention in the decoder
Contextual attention.
Multi-head attention: 6 layers, 8
attention heads (48 total).
Each head involves a query, a key, and avalue matrix:V̄ = softmax

André Martins (IST)

QK>
√
dk


V.

Sparse Communication

TALN 2021

24 / 64Adaptively Sparse Transformers(Correia, Niculae & Martins, 2019, EMNLP)

Key idea: replace softmax in attention heads by α-entmax!
Recall: α controls propensity to sparsity
Learn each α ∈ [1, 2] adaptively!
One α for each attention head and each layer.

André Martins (IST)

Sparse Communication

TALN 2021

25 / 64

Related Work: Other Sparse Transformers(Child et al., 2019; Sukhbaatar et al., 2019)

Our model allows non-contiguous attention for each head, learned
adaptively.

André Martins (IST)

Sparse Communication

TALN 2021

26 / 64

Accuracies and Learned α(Correia, Niculae & Martins, 2019, EMNLP)

Bimodal for the encoder, mostly unimodal for the decoder.

André Martins (IST)

Sparse Communication

TALN 2021

27 / 64

Trajectories of α During Training(Correia, Niculae & Martins, 2019, EMNLP)

Most heads become denser in the beginning, before converging.
Dense attention more beneﬁcial while the network is still uncertain,
becomes sparser as the network learns.
André Martins (IST)

Sparse Communication

TALN 2021

28 / 64

Previous Position Head(Correia, Niculae & Martins, 2019, EMNLP)(Learned α = 1.91)

André Martins (IST)

Sparse Communication

TALN 2021

29 / 64

Interrogation-Detecting Head(Correia, Niculae & Martins, 2019, EMNLP)(Learned α = 1.05)
André Martins (IST)

Sparse Communication

TALN 2021

30 / 64

Subword-Merging Head(Correia, Niculae & Martins, 2019, EMNLP)(Learned α = 1.91)
André Martins (IST)

Sparse Communication

TALN 2021

31 / 64Other Related Transformations
Constrained softmax (Martins & Kreutzer, 2017, EMNLP),
Constrained sparsemax (Malaviya, Ferreira & Martins, 2018, ACL):
Allows placing a budget on how much attention a word can receive
Useful to model fertility in NMT
Fusedmax (Niculae & Blondel, 2017, NeurIPS):
Can promote structured sparsity (e.g. contiguous words more likely to
be selected together)SparseMAP (Niculae, Martins, Blondel & Cardie, 2018, ICML):
Extends sparsemax to sparse structured prediction

André Martins (IST)

Sparse Communication

TALN 2021

32 / 64

SparseMAP(Niculae et al., 2018, ICML)

Generalizes sparsemax to sparse structured prediction
Works both as output layer and hidden layer
As hidden layer, similar to structured attention networks (Kim et al., 2017),
but sparse!
Eﬃcient forward/backprop requiring only an argmax (MAP) oracle!

André Martins (IST)

Sparse Communication

TALN 2021

33 / 64

Example: Latent Structured Alignments in SNLI

André Martins (IST)

Sparse Communication

TALN 2021

34 / 64

Example: Dependency Parsing

Suitable for capturing ambiguity in natural language!

André Martins (IST)

Sparse Communication

TALN 2021

35 / 64

LP-SparseMAP (Niculae & Martins, 2020, ICML)

Extension of SparseMAP
for latent factor graphs!
Can handle latent logic
variables and constraints.
Example: latent syntax
with valency constraints.

André Martins (IST)

Sparse Communication

TALN 2021

36 / 64

Dynamic Computation Graphs and Exact Expectations(Niculae, Martins & Cardie, 2018, EMNLP)(Correia, Niculae, Aziz & Martins, 2020, NeurIPS)

When combinatorial structures are used as latent variables in a neuralnetwork, it may become intractable to compute expectations:Have to sum through exponentially many terms (one per structure)
SparseMAP oﬀers a solution to this! Only a sparse subset of structure will
have non-zero terms in the summation!
We do this for:Discriminative models with dynamic computation graphs(Niculae, Martins & Cardie, 2018, EMNLP)

Generative models (combinatorial discrete VAEs)(Correia, Niculae, Aziz & Martins, 2020, NeurIPS)

André Martins (IST)

Sparse Communication

TALN 2021

37 / 64

Sparse and Continuous Attention(Martins, Farinhas, Treviso, Niculae, Aguiar & Figueiredo, 2020, NeurIPS)

So far: attention over a ﬁnite set (words, pixel regions, etc.)
We generalize attention to arbitrary sets, possibly continuous.

=⇒André Martins (IST)

Sparse Communication

TALN 2021

38 / 64

Example: Visual Question Answering
What is the woman looking at?

tv

computercomputer
1E-1

9

1E-0

8

1E-01
9

1E+01

0

7 5

Is the man wearing a hat?

yes

no

no
3E+00

65

0

4

1E-01
1E-06

(original image)

André Martins (IST)(discrete attention)(continuous softmax)

Sparse Communication(continuous sparsemax)

TALN 2021

39 / 64

Outline
1

Sparse Attention Mechanisms
Sparsemax and Entmax
Adaptively Sparse Transformers
Other Transformations

2Sparse Losses
Sparse Sequence-to-Sequence Models
Entmax Sampling3

Conclusions

André Martins (IST)

Sparse Communication

TALN 2021

40 / 64

Entmax Losses

Entmax can also be used as a loss in the output layer (to replacelogistic/cross-entropy loss)
However, not expressed as a log-likelihood (which could lead to log(0)problems due to sparsity)
Instead, we build a entmax loss inspired by Fenchel-Young losses.

André Martins (IST)

Sparse Communication

TALN 2021

41 / 64

Entmax Transformations and Losses(Blondel, Martins & Niculae, 2020, JMLR)

For α > 1, losses have margins
Interesting case: 1.5-entmax (specialized forward pass algorithm).
Pytorch code: https://github.com/deep-spin/entmax

André Martins (IST)

Sparse Communication

TALN 2021

42 / 64

Sparse Sequence-to-Sequence (Peters, Niculae & Martins, 2019, ACL)

Key idea:
Replace all instances of softmax by sparsemax or α-entmax.
We consider both sparsity in the attention mechanism and sparsity inthe output layer
Two tasks:
Machine translation (word-based)
Morphological inﬂection (character-based).

André Martins (IST)

Sparse Communication

TALN 2021

43 / 64

Training and InferenceTraining

Inference

Minimize token-level loss:

Approximate MAP decoding:L(θ) =X|y |X

ŷ = argmax pθ (y | x)

L(yt , z t )y ∈V ∗(x,y )∈D t=1

=

X

|y |
X

= argmaxy ∈V ∗−log[softmax(z t )]yt

(x,y )∈D t=1= argmaxy ∈V ∗

André Martins (IST)

Sparse Communication|y |Ypθ (yt | x, y<t )

t=1
|y |
Y

softmax(z t )yt

t=1

TALN 2021

44 / 64

What’s the Problem Here?

pθ (y | x) =|y |Ypθ (yt | x, y<t ).

t=1

The chain rule favors short sequences!

André Martins (IST)

Sparse Communication

TALN 2021

45 / 64

What’s the Problem Here?

pθ (y | x) =|y |Ypθ (yt | x, y<t ).

t=1

The chain rule favors short sequences!
Softmax → all strings have positive probability

André Martins (IST)

Sparse Communication

TALN 2021

45 / 64

What’s the Problem Here?

pθ (y | x) =|y |Ypθ (yt | x, y<t ).

t=1

The chain rule favors short sequences!
Softmax → all strings have positive probability
Often the empty string is the most likely sequence (Stahlberg & Byrne, 2019)

André Martins (IST)

Sparse Communication

TALN 2021

45 / 64

What’s the Problem Here?

pθ (y | x) =|y |Ypθ (yt | x, y<t ).

t=1

The chain rule favors short sequences!
Softmax → all strings have positive probability
Often the empty string is the most likely sequence (Stahlberg & Byrne, 2019)
Beam search prunes it.

André Martins (IST)

Sparse Communication

TALN 2021

45 / 64

Cat Got Your Tongue?




this

is

a

look




that

was

one

view

in

and

so

of

gaze

to

for

to

on

···




André Martins (IST)it

Sparse Communication

TALN 2021

46 / 64

Cat Got Your Tongue?




this

is

a

look




that

was

one

view

in

and

so

of

gaze

to

p(·) = 10−4
···




André Martins (IST)

it

for

to

on

Sparse Communication

TALN 2021

46 / 64

Cat Got Your Tongue?




this

is

a

look




that

was

one

view

in

and

so

of

gaze

to

p(·) = 10−1p(·) = 10−4
···




André Martins (IST)

it

for

to

on

Sparse Communication

TALN 2021

46 / 64

Cat Got Your Tongue?




this

is

a

look




that

was

one

view

in

and

so

of

gaze

to

p(·) = 10−5p(·) = 10−4
···




André Martins (IST)

it

for

to

on

Sparse Communication

TALN 2021

46 / 64

Can Entmax Save Us? (Peters, Niculae & Martins, 2019, ACL)
α=1

α = 1.5α=2α=∞softmax(z)1.5-entmax(z)sparsemax(z)argmax(z)

1

1

1

1
0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0

0

0

0

(Same z = [1.0716, −1.1221, −0.3288, 0.3368, 0.0425])

André Martins (IST)

Sparse Communication

TALN 2021

47 / 64

Cat Got Your Tongue? Maybe Not.




this

is

a

look




that

was

one

view

in

and

so

of

gaze

to

p(·) = 10−5p(·) = 10−4
···




André Martins (IST)

it

for

to

on

Sparse Communication

TALN 2021

48 / 64

Cat Got Your Tongue? Maybe Not.




this

is

a

look




that

was

one

view

in

and

so

of

gaze

to

p(·) = 10−3p(·) = 0···
André Martins (IST)

it

for

to

on

Sparse Communication

TALN 2021

48 / 64

Example: Machine Translation(Peters et al., 2019, ACL)

(Source: “Dies ist ein weiterer Blick auf den Baum des Lebens.”)

Only a few words get non-zero probability at each time stepAuto-completion when several words in a row have probability 1
Useful for predictive translation.
André Martins (IST)

Sparse Communication

TALN 2021

49 / 64

Sparsity in Attention and in Output Layer(Peters et al., 2019, ACL)

Sparsity in the output leads to higher accuracy
Sparse attention leads to more interpretable alignments.

1.5-entmax attains better
performance faster.

André Martins (IST)

Sparse Communication

TALN 2021

50 / 64

Example: Morphological Inﬂection

Only a few inﬂected words get nonzero probability.
Variants with double/gated attention: Peters & Martins (2019, SIGMORPHON).

André Martins (IST)

Sparse Communication

TALN 2021

51 / 64

Entmax and Label Smoothing (Peters & Martins, 2021, NAACL)
Sparse functions do mitigate the cat-got-your-tongue problem for MT
Fenchel-Young Label Smoothing: FY loss with smoothed target
instead of a one-hot label

LΩ, (z, e yt ) := LΩ (z, (1 − )e yt + u).
Cross-entropy = 0.0
Cross-entropy = 0.2
Cross-entropy = 0.5

2.0
1.5
1.0

1.5
1.0
0.5

0.5
0.0

Sparsemax loss = 0.0
Sparsemax loss = 0.2
Sparsemax loss = 0.5

2.0

4

3

2

André Martins (IST)

1
s

0

1

2

0.0

4

Sparse Communication

3

2

1
s

0

1

TALN 2021

2

52 / 64

Entmax Loss and Label Smoothing (Peters & Martins, 2021, NAACL)
Grapheme-to-Phoneme (SIGMORPHON 2020 Task 1):αSingleWER ↓PER ↓Ensemble
WER ↓
PER ↓

1

0
0.15

18.14
15.55

3.95
3.09

14.74
13.87

2.96
2.77

1.5

0
0.04

15.25
14.18

3.05
2.86

13.79
13.47

2.77
2.69

Machine Translation (BLEU scores; WMT14 is En-De):
α



De-En

En-De

Ja-En

En-Ja

Ro-En

En-Ro

WMT14

1

0
>0
0
>0

27.05
27.72
28.12
28.11

23.36
24.24
24.03
24.36

20.52
20.99
21.23
21.34

26.94
27.28
27.58
27.58

29.41
30.03
30.27
30.37

22.84
23.15
23.74
23.47

25.10
25.21
25.46
25.45

1.5

André Martins (IST)

Sparse Communication

TALN 2021

53 / 64

Entmax Sampling (Martins, Marinho & Martins, 2020, EMNLP)
Use the entmax loss for training language models.
At test time, sample from this sparse distribution.

Distinct-n

Better quality with less repetitions than other methods:

1.00
0.95
0.90
0.85
0.80
0.75
0.70
0.65
0.60
0.55
1.0

André Martins (IST)humanentmaxnucleussoftmax-t
top-k
unlikelihood

1.5

2.0

2.5
n

Sparse Communication

3.0

3.5

4.0
TALN 2021

54 / 64

Story Completion on WritingPrompts

Fine-tuned GPT-2; repetitions and oﬀ-topic text are highlighted.
Context:“Are they ready to go live?" Zuko asked. “Yup, in just a minute" Tomi
replied as he leaned back in his reclining chair. This was a moment thatthe entire galaxy would see. After 10 years...

André Martins (IST)

Sparse Communication

TALN 2021

55 / 64

Story Completion on WritingPrompts

Fine-tuned GPT-2; repetitions and oﬀ-topic text are highlighted.
Context:“Are they ready to go live?" Zuko asked. “Yup, in just a minute" Tomi
replied as he leaned back in his reclining chair. This was a moment thatthe entire galaxy would see. After 10 years...

Greedy:... of study, the scientists had ﬁnally come to the conclusion that theuniverse was not a place for living. The scientists had been studying
the universe for over a century. They had been studying the universe
for over a century.

André Martins (IST)

Sparse Communication

TALN 2021

55 / 64

Story Completion on WritingPrompts

Fine-tuned GPT-2; repetitions and oﬀ-topic text are highlighted.
Context:“Are they ready to go live?" Zuko asked. “Yup, in just a minute" Tomi
replied as he leaned back in his reclining chair. This was a moment thatthe entire galaxy would see. After 10 years...

Top-k :... of studying this phenomenon, the team had ﬁnally come up with aplan to study what the aliens were doing. The team would be looking
for a way to create a space station. “And what would you call it?"
“What would you call the space station?"

André Martins (IST)

Sparse Communication

TALN 2021

55 / 64

Story Completion on WritingPrompts

Fine-tuned GPT-2; repetitions and oﬀ-topic text are highlighted.
Context:“Are they ready to go live?" Zuko asked. “Yup, in just a minute" Tomi
replied as he leaned back in his reclining chair. This was a moment thatthe entire galaxy would see. After 10 years...

Nucleus:... of diligent testing, and some test run after that, the results were
well received. “they’re waiting for you, because there’s no way theywould.” Stowedly at a local wedding place, the two archaeologists spoke
together.

André Martins (IST)

Sparse Communication

TALN 2021

55 / 64

Story Completion on WritingPrompts

Fine-tuned GPT-2; repetitions and oﬀ-topic text are highlighted.
Context:“Are they ready to go live?" Zuko asked. “Yup, in just a minute" Tomi
replied as he leaned back in his reclining chair. This was a moment thatthe entire galaxy would see. After 10 years...

Entmax:... of hibernation, Tomi was back. These last days had been a significant step forward in his mission. This time, Tomi was not alone. All
the empires had aligned together and the world’s leadership began
to openly support his mission.

André Martins (IST)

Sparse Communication

TALN 2021

55 / 64

Human Evaluation of Story Completion

Greedytop-k
Nucleus
Unlikelihood
EntmaxAndré Martins (IST)

Fluency

Coherence

Engagement

2.5
3.3
3.5
3.3
3.5

2.3
2.9
3.1
3.0
3.2

2.3
2.9
3.2
3.2
3.6

Sparse Communication

TALN 2021

56 / 64

Human Evaluation of Dialogue Generation

We followed the ConvAI2 challenge: 12 volunteers had 30 conversations
each with models using the diﬀerent sampling methods.
The model’s personas were randomly selected from the PersonaChat
validation set.

Greedytop-k
Nucleus
EntmaxAndré Martins (IST)

Fluency

Consistency

Engagement

4.1
4.0
4.1
4.1

3.0
3.2
3.4
3.6

2.5
3.3
3.3
3.9

Sparse Communication

TALN 2021

57 / 64

Outline
1

Sparse Attention Mechanisms
Sparsemax and Entmax
Adaptively Sparse Transformers
Other Transformations

2Sparse Losses
Sparse Sequence-to-Sequence Models
Entmax Sampling3

Conclusions

André Martins (IST)

Sparse Communication

TALN 2021

58 / 64

Conclusions

Transformations from real numbers to distributions are ubiquitous
We introduced new transformations that handle sparsity, constraints,
and structure
All are diﬀerentiable and their gradients are eﬃcient to computeCan be used as hidden layers or as output layers
The sparsity can be adaptive
Encouraging results in NMT and other tasks
Sparse communication potentially useful as a path for explainability.

André Martins (IST)

Sparse Communication

TALN 2021

59 / 64

Thank You!

DeepSPIN (“Deep Structured Prediction in NLP”)
ERC starting grant, started in 2018
Topics: deep learning, structured prediction, NLP
More details: https://deep-spin.github.io

André Martins (IST)

Sparse Communication

TALN 2021

60 / 64References I
Bach, S., Binder, A., Montavon, G., Klauschen, F., Müller, K.-R., & Samek, W. (2015). On pixel-wise
explanations for non-linear classiﬁer decisions by layer-wise relevance propagation. PloS one, 10(7),130–140.
Bastings, J., Aziz, W., & Titov, I. (2019). Interpretable neural predictions with diﬀerentiable binary
variables. In Proc. ACL.
Blondel, M., Martins, A. F. T., & Niculae, V. (2020). Learning with fenchel-young losses. Journal of
Machine Learning Research, 21(35), 1–69.
Child, R., Gray, S., Radford, A., & Sutskever, I. (2019). Generating long sequences with sparsetransformers. arXiv preprint arXiv:1904.10509.
Church, K. W. & Hanks, P. (1990). Word association norms, mutual information, and lexicography.
Computational linguistics, 16(1), 22–29.
Correia, G., Niculae, V., Aziz, W., & Martins, A. (2020). Eﬃcient marginalization of discrete andstructured latent variables via sparsity. Advances in Neural Information Processing Systems, 33.
Correia, G., Niculae, V., & Martins, A. F. T. (2019). Adaptively sparse transformers. In Proceedings of the
Empirical Methods for Natural Language Processing.
Feng, S., Wallace, E., Grissom II, A., Iyyer, M., Rodriguez, P., & Boyd-Graber, J. (2018). Pathologies ofneural models make interpretations diﬃcult. In Proc. EMNLP, (pp. 3719–3728).
Guyon, I., Weston, J., Barnhill, S., & Vapnik, V. (2002). Gene selection for cancer classiﬁcation using
support vector machines. Machine learning, 46(1-3), 389–422.

André Martins (IST)

Sparse Communication

TALN 2021

61 / 64References II
Kim, Y., Denton, C., Hoang, L., & Rush, A. M. (2017). Structured attention networks. arXiv preprint
arXiv:1702.00887.
Kohavi, R. & John, G. H. (1997). Wrappers for feature subset selection. Artiﬁcial intelligence, 97(1-2),
273–324.
Lei, T., Barzilay, R., & Jaakkola, T. (2016). Rationalizing neural predictions. In Proc. EMNLP, (pp.
107–117).
Li, J., Chen, X., Hovy, E., & Jurafsky, D. (2016). Visualizing and understanding neural models in nlp. In
Proc. NAACL-HLT, (pp. 681–691).
Li, J., Monroe, W., & Jurafsky, D. (2016). Understanding neural networks through representation
erasure. arXiv preprint arXiv:1612.08220.
Malaviya, C., Ferreira, P., & Martins, A. F. T. (2018). Sparse and Constrained Attention for Neural
Machine Translation. In Proc. of the Annual Meeting of the Association for Computation Linguistics.
Martins, A., Farinhas, A., Treviso, M., Niculae, V., Aguiar, P., & Figueiredo, M. (2020). Sparse andcontinuous attention mechanisms. Advances in Neural Information Processing Systems, 33.
Martins, A. F. T. & Astudillo, R. (2016). From Softmax to Sparsemax: A Sparse Model of Attention andMulti-Label Classiﬁcation. In Proc. of the International Conference on Machine Learning.
Martins, A. F. T. & Kreutzer, J. (2017). Fully diﬀerentiable neural easy-ﬁrst taggers. In Proc. of Empirical
Methods for Natural Language Processing.
Martins, P. H., Marinho, Z., & Martins, A. F. T. (2020). Sparse text generation. In Proc. of EMNLP.
Niculae, V. & Blondel, M. (2017). A regularized framework for sparse and structured neural attention.
arXiv preprint arXiv:1705.07704.
André Martins (IST)

Sparse Communication

TALN 2021

62 / 64References III
Niculae, V., Martins, A. F., & Cardie, C. (2018). Towards dynamic computation graphs via sparse latent
structure. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,(pp. 905–911).
Niculae, V. & Martins, A. F. T. (2020). Lp-sparsemap: Diﬀerentiable relaxed optimization for sparse
structured prediction. In Proc. of ICML.
Niculae, V., Martins, A. F. T., Blondel, M., & Cardie, C. (2018). SparseMAP: Diﬀerentiable Sparse
Structured Inference. In Proc. of the International Conference on Machine Learning.
Peters, B. & Martins, A. F. (2019). It–ist at the sigmorphon 2019 shared task: Sparse two-headedmodels for inﬂection. In Proceedings of the 16th Workshop on Computational Research in Phonetics,
Phonology, and Morphology, (pp. 50–56).
Peters, B. & Martins, A. F. (2021). Smoothing and shrinking the sparse seq2seq search space. In
Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational
Linguistics: Human Language Technologies, (pp. 2642–2654).
Peters, B., Niculae, V., & Martins, A. F. T. (2019). Sparse sequence-to-sequence models. In Proceedingsof the Annual Meeting of the Association for Computational Linguistics.
Ribeiro, M. T., Singh, S., & Guestrin, C. (2016). Why should i trust you?: Explaining the predictions of
any classiﬁer. In Proc. ACM SIGKDD, (pp. 1135–1144). ACM.
Serrano, S. & Smith, N. A. (2019). Is attention interpretable? In Proc. ACL.
Stahlberg, F. & Byrne, B. (2019). On nmt search errors and model errors: Cat got your tongue? In
Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9thInternational Joint Conference on Natural Language Processing (EMNLP-IJCNLP), (pp. 3347–3353).
André Martins (IST)

Sparse Communication

TALN 2021

63 / 64References IV
Sukhbaatar, S., Grave, E., Bojanowski, P., & Joulin, A. (2019). Adaptive attention span in transformers.
arXiv preprint arXiv:1905.07799.
Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal StatisticalSociety, 58(1), 267–288.
Treviso, M. V. & Martins, A. F. T. (2020). The explanation gamae: Towards prediction explainability
through sparse communication. In Proc. of EMNLP Workshop on Analyzing and Interpreting Neural
Networks for NLP (BlackboxNLP).
Tsallis, C. (1988). Possible generalization of boltzmann-gibbs statistics. Journal of Statistical Physics.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L. u., & Polosukhin, I.
(2017). Attention is all you need. In Advances in Neural Information Processing Systems (pp.
5998–6008).
Xu, K., Ba, J., Kiros, R., Cho, K., Courville, A., Salakhudinov, R., Zemel, R., & Bengio, Y. (2015). Show,
attend and tell: Neural image caption generation with visual attention. In Proc. ICLR, (pp.
2048–2057).
Zou, H. & Hastie, T. (2005). Regularization and variable selection via the elastic net. Journal of the royalstatistical society, 67(2), 301–320.

André Martins (IST)

Sparse Communication

TALN 2021

64 / 64