Latent Structure Models
for NLP
André Mar ns
Tsvetomila Mihaylova
Nikita Nangia
Vlad Niculae

Ins tuto de Telecomunicações & IST & Unbabel
Ins tuto de Telecomunicações
NYU
Ins tuto de Telecomunicações

deep-spin.github.io/tutorial

I. Introduc on

Structured predic on and NLP• Structured predic on: a machine learning framework for predic ng structured,constrained, and interdependent outputs• NLP deals with structured and ambiguous textual data:• machine transla on• speech recogni on• syntac c parsing• seman c parsing• informa on extrac on• ...

deep-spin.github.io/tutorial

2

Examples of structure in NLP
Dependency parsing
···
⋆

dog

on

wheels⋆dogonwheels⋆dogonwheels···deep-spin.github.io/tutorial

3

Examples of structure in NLP
Dependency parsing
···
⋆

dog

on

wheelsExponen ⋆ally
many parse trees!
dog on wheels
Cannot enumerate.
⋆

dog

on

wheels···deep-spin.github.io/tutorial

3

Examples of structure in NLP
POS tagging
VERB

PREP

NOUN

dog

on

wheelsDependency parsing
···
⋆

NOUN

PREP

NOUN

dog

on

wheels
⋆

NOUN

DET

NOUN

dog

on

wheels
⋆

dog

dog

dog

on

on

on
···

deep-spin.github.io/tutorial

wheelswheelswheelsWord alignments
dog
on

hond
op

wheelswielen

dog
on

hond
op

wheelswielen

dog
on

hond
op

wheelswielen3

NLP 5 years ago:
Structured predic on and pipelines

NLP 5 years ago:
Structured predic on and pipelines• Big pipeline systems, connec ng di erent structured predictors, trained
separately• Advantages: fast and simple to train, can rearrange pieces

deep-spin.github.io/tutorial

5

NLP 5 years ago:
Structured predic on and pipelines• Big pipeline systems, connec ng di erent structured predictors, trained
separately• Advantages: fast and simple to train, can rearrange pieces• Disadvantage: linguis c annota ons required for each component

deep-spin.github.io/tutorial

5

NLP 5 years ago:
Structured predic on and pipelines• Big pipeline systems, connec ng di erent structured predictors, trained
separately• Advantages: fast and simple to train, can rearrange pieces• Disadvantage: linguis c annota ons required for each component• Bigger disadvantage: error propagates through the pipeline

deep-spin.github.io/tutorial

5

NLP today:
End-to-end training

NLP today:
End-to-end training• Forget pipelines—train everything from scratch!
• No more error propaga on or linguis c annota ons!

deep-spin.github.io/tutorial

7

NLP today:
End-to-end training• Forget pipelines—train everything from scratch!
• No more error propaga on or linguis c annota ons!
• Treat everything as latent!

deep-spin.github.io/tutorial

7

Representa on learning• Uncover hidden representa ons
useful for the downstream task.
• Neural networks are well-suitedfor this: deep computa on graphs.

deep-spin.github.io/tutorial

input



posi ve
neutralnega ve8

Representa on learning• Uncover hidden representa ons
useful for the downstream task.
• Neural networks are well-suitedfor this: deep computa on graphs.
• Neural representa ons are
unstructured, inscrutable.
Language data has underlying
structure!

deep-spin.github.io/tutorial

input



posi ve
neutralnega ve8

Latent structure models• Seek structured hidden
representa ons instead!

deep-spin.github.io/tutorial

input



posi ve
neutralnega ve9Latent structure models• Seek structured hidden
representa ons instead!

···
input

posi ve

neutralnega ve···deep-spin.github.io/tutorial

9Latent structure models aren’t so new!
• They have a very long history in NLP:
• IBM Models for SMT (latent word alignments) [Brown et al., 1993]• HMMs [Rabiner, 1989]• CRFs with hidden variables [Qua oni et al., 2007]• Latent PCFGs [Petrov and Klein, 2008, Cohen et al., 2012]• Trained with EM, spectral learning, method of moments, ...
• O en, very strict assump ons (e.g. strong factoriza ons)
• Today, neural networks opened up some new possibili es!

deep-spin.github.io/tutorial

10Why do we love latent structure models?

• The inferred latent variables can bring us some interpretability• They o er a way of injec ng prior knowledge as a structured bias
• Hopefully: Higher predic ve power with fewer model parameters

deep-spin.github.io/tutorial

11

Why do we love latent structure models?

• The inferred latent variables can bring us some interpretability• They o er a way of injec ng prior knowledge as a structured bias
• Hopefully: Higher predic ve power with fewer model parameters• smaller carbon footprint!

deep-spin.github.io/tutorial

11

What this tutorial is about:• Discrete, combinatorial latent structures• O en the structure is inspired by some linguis c intui on• We’ll cover both:• RL methods (structure built incrementally, reward coming from downstream task)• ... vs end-to-end di eren able approaches (global op miza on, marginaliza on)• stochas c computa on graphs• ... vs determinis c graphs.

• All plugged in discrimina ve neural models.

deep-spin.github.io/tutorial

12

This tutorial is not about:• It’s not about con nuous latent variables• It’s not about deep genera ve learning• We won’t cover GANs, VAEs, etc.
• There are (very good) recent tutorials on deep varia onal models for NLP:
• “Varia onal Inference and Deep Genera ve Models” (Schulz and Aziz, ACL 2018)• “Deep Latent-Variable Models for Natural Language” (Kim, Wiseman, Rush, EMNLP 2018)

deep-spin.github.io/tutorial

13

BackgroundUnstructured vs structured• To be er explain the math, we’ll o en backtrack to unstructured models (where
the latent variable is a categorical) before jumping to the structured ones

deep-spin.github.io/tutorial

14

The unstructured case: Probability simplex△

deep-spin.github.io/tutorial

15

The unstructured case: Probability simplex[0, 0, 1]• Each vertex is an indicator vector,
represen ng one class:zc = [0, . . . , 0,1
, 0, . . . , 0].
|{z}cth posi on△

deep-spin.github.io/tutorial

15

The unstructured case: Probability simplex[0, 0, 1]• Each vertex is an indicator vector,
represen ng one class:zc = [0, . . . , 0,[.3, .2, .5]

1, 0, . . . , 0].
|{z}cth posi on△• Points inside are probability vectors, aconvex combina on of classes:∑p ≥ 0,
pc = 1.
c

deep-spin.github.io/tutorial

15

What’s the analogous of △ for a structure?
• A structured object z can be represented as a bit vector.

deep-spin.github.io/tutorial

16

What’s the analogous of △ for a structure?
• A structured object z can be represented as a bit vector.
• Example:• a dependency tree can be represented a O(L2 ) vector indexed by arcs
• each entry is 1 i the arc belongs to the tree
• structural constraints: not all bit vectors represent valid trees!

deep-spin.github.io/tutorial

16

What’s the analogous of △ for a structure?
• A structured object z can be represented as a bit vector.
• Example:• a dependency tree can be represented a O(L2 ) vector indexed by arcs
• each entry is 1 i the arc belongs to the tree
• structural constraints: not all bit vectors represent valid trees!

z1 = [1, 0, 0, 0, 1, 0, 0, 0, 1]
⋆

dog

on

wheelsdeep-spin.github.io/tutorialz2 = [0, 0, 1, 0, 0, 1, 1, 0, 0]

z3 = [1, 0, 0, 0, 1, 0, 0, 1, 0]

⋆

⋆

dog

on

wheelsdogonwheels16

[Wainwright and Jordan, 2008]

The structured case: Marginal polytope

Mdeep-spin.github.io/tutorial

17

[Wainwright and Jordan, 2008]

The structured case: Marginal polytope• Each vertex corresponds to one such bit vector zMdeep-spin.github.io/tutorial

17

[Wainwright and Jordan, 2008]

The structured case: Marginal polytope• Each vertex corresponds to one such bit vector z• Points inside correspond to marginal distribu ons:
convex combina ons of structured objects
μ = p1 z1 + . . . + pN zN , p ∈ ∆.
|
{z
}

M

exponen ally many terms

p1 = 0.2,
p2 = 0.7,
p3 = 0.1,

z1 = [1, 0, 0, 0, 1, 0, 0, 0, 1]
z2 = [0, 0, 1, 0, 0, 1, 1, 0, 0]
z3 = [1, 0, 0, 0, 1, 0, 0, 1, 0]

deep-spin.github.io/tutorial⇒

μ=[.3, 0, .7, 0, .3, .7, .7, .1, .2].
17

Unstructured vs Structured• Unstructured case: simplex ∆△deep-spin.github.io/tutorial• Structured case: marginal polytope M

M
18

Unstructured vs Structured• Unstructured case: simplex ∆△deep-spin.github.io/tutorial• Structured case: marginal polytope M

M
18

Unstructured vs Structured• Unstructured case: simplex ∆△deep-spin.github.io/tutorial• Structured case: marginal polytope M

M
18

Compu ng the most likely structure
is a very high-dimensional argmax
input
x

s

z

outputby···deep-spin.github.io/tutorial

19

Compu ng the most likely structure
is a very high-dimensional argmax
s

input
x

z

outputbyThere are exponen ally
many structures···(s cannot t in memory;

we cannot “loop” over s nor z)

deep-spin.github.io/tutorial

19

Dealing with the combinatorial explosion
→

→

→ ···

1. Incremental structures

max · · · ,

,

,

, ···

2. Factoriza on into parts• Build structure greedily, as sequence• Op mizes globally (e.g. Viterbi,
of discrete choices (e.g., shi -reduce).
Chu-Liu-Edmonds, Kuhn-Munkres).
• Scores (par al structure, ac on) tuples. • Scores smaller parts.
• Advantages: exible, rich histories.
• Advantages: op mal, elegant, canhandle hard & global constraints.
• Disadvantages: greedy, local decisions• Disadvantages: strong assump ons.
are subop mal, error propaga on.
deep-spin.github.io/tutorial

20

The challenge of discrete choices.
z=1
z=2
···
z=N

deep-spin.github.io/tutorial

21

The challenge of discrete choices.
s
z=1
z=2
···
z=N

deep-spin.github.io/tutorial

21

The challenge of discrete choices.
s

z
z=1
z=2
···
z=N

deep-spin.github.io/tutorial

21

The challenge of discrete choices.
s

input
x
s = fθ (x)

z
z=1
z=2
···

outputbyb
y = gφ (z, x)

z=N

deep-spin.github.io/tutorial

21

The challenge of discrete choices.
s

input
x
s = fθ (x)

z
z=1
z=2
···

outputbyb
y = gφ (z, x)

z=N
∂L(b
y,y)
=?
∂w
deep-spin.github.io/tutorial

21

The challenge of discrete choices.
s

input
x
s = fθ (x)output
b
y

z
z=1
z=2
···

b
y = gφ (z, x)

z=N
∂L(b
y,y)
=?
∂w
deep-spin.github.io/tutorial

or, essen ally,

∂z
=?
∂s
21

Discrete mappings are “ at”
s

z
z=1
z=2
···
z=N
∂z
=?
∂s

deep-spin.github.io/tutorial

22

Discrete mappings are “ at”
s

z
z=1
z=2
···
z=N
∂z
=?
∂s

deep-spin.github.io/tutorial

22

Discrete mappings are “ at”
s

z
z=1
z=2
···
z=N
∂z
=?
∂s

deep-spin.github.io/tutorial

22

Discrete mappings are “ at”
s

z
z=1
z=2
···
z=N
∂z
=?
∂s

deep-spin.github.io/tutorial

22

Discrete mappings are “ at”
s

z
z=1
z=2
···
z=N
∂z
=?
∂s

deep-spin.github.io/tutorial

22

Discrete mappings are “ at”
s

z
z=1
z=2
···
z=N
∂z
=?
∂s

deep-spin.github.io/tutorial

22

Discrete mappings are “ at”
s

z
z=1
z=2
···
z=N
∂z
=?
∂s

deep-spin.github.io/tutorial

22

Discrete mappings are “ at”
s

z
z=1
z=2
···
z=N
∂z
=?
∂s

deep-spin.github.io/tutorial

22

Argmax
s

z
z=1
z=2
···

z1
1

0

s2 − 1s2

s2 + 1

s1

z=N
∂z
=0
∂s
deep-spin.github.io/tutorial

23

Example: Regression with latent categoriza onsuinput x*
embeddings E
1
u = |x|

∑

j Exj

Ws
s = Ws u

deep-spin.github.io/tutorial

24

Example: Regression with latent categoriza onsuzinput x(c)*embeddings E
1
u = |x|

∑

j Exj

Ws
s = Ws u

predict topic c (z = ec )deep-spin.github.io/tutorial

24

Example: Regression with latent categoriza on
s

u

z

v

input xoutput ŷ



(c)

*
embeddings E
1
u = |x|

∑

j Exj

Ws
s = Ws uWv
v = tanh (Wv [u, z])Wyŷ = Wy v L = (ŷ − y)2

predict topic c (z = ec )deep-spin.github.io/tutorial

24

Example: Regression with latent categoriza on
s

u

z

v

input xoutput ŷ



(c)

*
embeddings E
1
u = |x|

∑

j Exj

Ws
s = Ws u

deep-spin.github.io/tutorial

Wvv = tanh (Wv [u, z])Wyŷ = Wy v L = (ŷ − y)224

Example: Regression with latent categoriza on
s

u

z

v

input xoutput ŷ



(c)

*
embeddings E
1
u = |x|

∑

j Exj

Ws
s = Ws uWv
v = tanh (Wv [u, z])Wyŷ = Wy v L = (ŷ − y)2≡0∂L∂L ∂ŷ ∂v
= ∂ŷ
∂Ws
∂v ∂z

deep-spin.github.io/tutorial

z}|{
∂z
∂s

∂s
∂Ws

24

Example: Regression with latent categoriza on
u

s

z

v

input xoutput ŷ



(c)

*

Workarounds:
circumven ng theWs
Wv issue,Wy
bypassing discrete variables

embeddings E
1
u = |x|∑j Exj

s = Ws u

deep-spin.github.io/tutorialv = tanh (Wv [u, z])ŷ = Wy v L = (ŷ − y)224

Example: Regression with latent categoriza on
s

u

z

v

input xoutput ŷ



(c)

*
embeddings E
1
u = |x|

∑

j Exj

Ws
s = Ws uWv
v = tanh (Wv [u, z])Wyŷ = Wy v L = (ŷ − y)2

Op on 1. Pretrain latent classi er Ws
deep-spin.github.io/tutorial

24

Example: Regression with latent categoriza on
s

u

z

v

input xoutput ŷ



(c)

*
embeddings E
1 ∑u = |x|
j Exj

Ws

Wv

Wy
exp(sc )Z

s = Ws uv = tanh (Wv [u, z])− logŷ = Wy v L = (ŷ − y)2

Op on 2. Mul -task learning
deep-spin.github.io/tutorial

24

Example: Regression with latent categoriza on
s

u

z

v

input xoutput ŷ



(c)

*
embeddings E
1
u = |x|

∑

j Exj

Ws

W

v
Tackling discreteness end-to-end

s = Ws u

deep-spin.github.io/tutorialv = tanh (Wv [u, z])Wyŷ = Wy v L = (ŷ − y)224

Example: Regression with latent categoriza on
s

u

z

v

input xoutput ŷ



(c)

*
embeddings E
1
u = |x|

∑

j Exj

Ws
s = Ws uWv
v = tanh (Wv [u, z])

Op on 3. Stochas city!
deep-spin.github.io/tutorialWyŷ = Wy v L = Ez (ŷ − y)2∂Ez (ŷ(z)−y)2
=
/ 0
∂Ws
24

Example: Regression with latent categoriza on
s

u

z

v

input xoutput ŷ



(c)

*
embeddings E
1
u = |x|

∑

j Exj

Ws
s = Ws uWv
v = tanh (Wv [u, z])Wyŷ = Wy v L = (ŷ − y)2

Op on 4. Gradient surrogates (e.g. straight-through, ∂z← I)∂s
deep-spin.github.io/tutorial

24

Example: Regression with latent categoriza on
p

s

u

v

input xoutput ŷ



(c)

*
embeddings E
1
u = |x|

∑

j Exj

Ws
s = Ws uWv
v = tanh (Wv [u, p])Wyŷ = Wy v L = (ŷ − y)2

Op on 5. Con nuous relaxa on (e.g. so max)
deep-spin.github.io/tutorial

24Dealing with discrete latent variables

1. Pre-train external classi er
2. Mul -task learning
3. Stochas c latent variables
4. Gradient surrogates
5. Con nuous relaxa on

deep-spin.github.io/tutorial

25

Dealing with discrete latent variables

1. Pre-train external classi er
2. Mul -task learning
3. Stochas c latent variables (Part 2)
4. Gradient surrogates (Part 3)
5. Con nuous relaxa on (Part 4)

deep-spin.github.io/tutorial

25

Roadmap of the tutorial• Part 1: Introduc on ✓• Part 2: Reinforcement learning• Part 3: Gradient surrogates
Co ee Break• Part 4: End-to-end di eren able models• Part 5: Conclusions

deep-spin.github.io/tutorial

26

II. Reinforcement
Learning Methods

Latent structure via marginaliza on• Given a sentence-label pair (x, y) and its known parse tree z,

deep-spin.github.io/tutorial

27

Latent structure via marginaliza on• Given a sentence-label pair (x, y) and its known parse tree z,
we can make a predic on ŷ(z; x)

deep-spin.github.io/tutorial

27

Latent structure via marginaliza on• Given a sentence-label pair (x, y) and its known parse tree z,
we can make a predic on ŷ(z; x)
and incur a loss,L(ŷ(z; x), y)

deep-spin.github.io/tutorial

27

Latent structure via marginaliza on• Given a sentence-label pair (x, y) and its known parse tree z,
we can make a predic on ŷ(z; x)
and incur a loss,L(ŷ(z; x), y) or simply L(z)deep-spin.github.io/tutorial

27

Latent structure via marginaliza on• Given a sentence-label pair (x, y) and its known parse tree z,
we can make a predic on ŷ(z; x)
and incur a loss,L(ŷ(z; x), y) or simply L(z)• But we don’t know z!

deep-spin.github.io/tutorial

27

Latent structure via marginaliza on• Given a sentence-label pair (x, y) and its known parse tree z,
we can make a predic on ŷ(z; x)
and incur a loss,L(ŷ(z; x), y) or simply L(z)• But we don’t know z!
• In this sec on:
we jointly learn a structured predic on model πθ (z | x)

deep-spin.github.io/tutorial

27

Latent structure via marginaliza on• Given a sentence-label pair (x, y) and its known parse tree z,
we can make a predic on ŷ(z; x)
and incur a loss,L(ŷ(z; x), y) or simply L(z)• But we don’t know z!
• In this sec on:
we jointly learn a structured predic on model πθ (z | x)
by op mizing the expected loss,Eπθ (z|x) L(z)deep-spin.github.io/tutorial

27

But rst, supervised
SPINN[Bowman et al., 2016]

Stack-augmented Parser-Interpreter
Neural-Network

deep-spin.github.io/tutorial28

[Bowman et al., 2016]

Stack-augmented Parser-Interpreter
Neural-Network• Joint learning: Combines a cons tuency parser and a sentence representa on
model.

deep-spin.github.io/tutorial

29

[Bowman et al., 2016]

Stack-augmented Parser-Interpreter
Neural-Network• Joint learning: Combines a cons tuency parser and a sentence representa on
model.
• The parser, fθ (x) is a transi on-based shi -reduce parser. It looks at top twoelements of stack and top element of the bu er.

deep-spin.github.io/tutorial

29

[Bowman et al., 2016]

Stack-augmented Parser-Interpreter
Neural-Network• Joint learning: Combines a cons tuency parser and a sentence representa on
model.
• The parser, fθ (x) is a transi on-based shi -reduce parser. It looks at top twoelements of stack and top element of the bu er.
• TreeLSTM combines top two elements of the stack when the parser choses the
reduce ac on.

deep-spin.github.io/tutorial

29

[Bowman et al., 2016]

Stack-augmented Parser-Interpreter
Neural-Network

deep-spin.github.io/tutorial

30

[Bowman et al., 2016]

Stack-augmented Parser-Interpreter
Neural-Network

deep-spin.github.io/tutorial

30

[Bowman et al., 2016]

Stack-augmented Parser-Interpreter
Neural-Network

deep-spin.github.io/tutorial

30

[Bowman et al., 2016]

Stack-augmented Parser-Interpreter
Neural-Network

deep-spin.github.io/tutorial

30

[Bowman et al., 2016]

Stack-augmented Parser-Interpreter
Neural-Network

deep-spin.github.io/tutorial

30

[Bowman et al., 2016]

Stack-augmented Parser-Interpreter
Neural-Network

deep-spin.github.io/tutorial

30

Shi -Reduce parsing

We can write a shi -reduce style parse as a sequence of Bernoulli randomvariables,z = {z1 , . . . , z2L−1 }where, zj ∈ {0, 1} ∀j ∈ [1, 2L − 1]deep-spin.github.io/tutorial

31

Shi -Reduce parsing

A sequence of Bernoulli trials but with condi onal dependence,p(z1 , z2 , . . . , z2L−1 ) =2L−1∏

p(zj | z<j )j=1

deep-spin.github.io/tutorial

32

Latent structure learning with SPINN

deep-spin.github.io/tutorial

33

Latent structure learning with SPINN• But now, remove syntac c supervision from SPINN.

deep-spin.github.io/tutorial

33

Latent structure learning with SPINN• But now, remove syntac c supervision from SPINN.

• We model the parse, z, as a latent variable with our parser as the score func on
es mator, fθ (x).

deep-spin.github.io/tutorial

33

Latent structure learning with SPINN• But now, remove syntac c supervision from SPINN.

• We model the parse, z, as a latent variable with our parser as the score func on
es mator, fθ (x).
• With shi -reduce parsing, we’re making discrete decisions ⇒ REINFORCE as a“natural” solu on.
deep-spin.github.io/tutorial

33

Unsupervised SPINN

Unsupervised SPINN

No syntac c supervision.
Only reward is from the downstream task.
We only get this reward a er parsing the full sentence.

deep-spin.github.io/tutorial

34

[Williams, 1992]

SPINN with REINFORCE
Some basic terminology,• The ac on space is zj ∈ {shift,reduce}, and z is a sequence of ac ons.

deep-spin.github.io/tutorial

35

[Williams, 1992]

SPINN with REINFORCE
Some basic terminology,• The ac on space is zj ∈ {shift,reduce}, and z is a sequence of ac ons.
• Training parser network parameters, θ with REINFORCE

deep-spin.github.io/tutorial

35

[Williams, 1992]

SPINN with REINFORCE
Some basic terminology,• The ac on space is zj ∈ {shift,reduce}, and z is a sequence of ac ons.
• Training parser network parameters, θ with REINFORCE• The state, h, is the top two elements of the stack and the top element of thebu er.

deep-spin.github.io/tutorial

35

[Williams, 1992]

SPINN with REINFORCE
Some basic terminology,• The ac on space is zj ∈ {shift,reduce}, and z is a sequence of ac ons.
• Training parser network parameters, θ with REINFORCE• The state, h, is the top two elements of the stack and the top element of thebu er.
• Learning a policy network π (z | h; θ)

deep-spin.github.io/tutorial

35

[Williams, 1992]

SPINN with REINFORCE
Some basic terminology,• The ac on space is zj ∈ {shift,reduce}, and z is a sequence of ac ons.
• Training parser network parameters, θ with REINFORCE• The state, h, is the top two elements of the stack and the top element of thebu er.
• Learning a policy network π (z | h; θ)• Maximize the reward, where R is performance on the downstream task likesentence classi ca on.

deep-spin.github.io/tutorial

35

[Williams, 1992]

SPINN with REINFORCE
Some basic terminology,• The ac on space is zj ∈ {shift,reduce}, and z is a sequence of ac ons.
• Training parser network parameters, θ with REINFORCE• The state, h, is the top two elements of the stack and the top element of thebu er.
• Learning
NOTE:
Only
a singleat the end of parsing.
a policy
network
π (z | h;rewardθ)• Maximize the reward, where R is performance on the downstream task likesentence classi ca on.

deep-spin.github.io/tutorial

35

Through the looking glass of REINFORCE∇θ Ez∼πθ (z|x) [L(z)]deep-spin.github.io/tutorial36Through the looking glass of REINFORCE∇θ Ez∼πθ (z|x) [L(z)] = ∇θ∑

L(z)πθ (z | x)z
(By de ni on of expecta on. How to evaluate?)

deep-spin.github.io/tutorial36Through the looking glass of REINFORCE∇θ Ez∼πθ (z|x) [L(z)] = ∇θ∑

L(z)πθ (z | x)z
(By de ni on of expecta on. How to evaluate?)=∑L(z)∇θ πθ (z | x)z

deep-spin.github.io/tutorial36Through the looking glass of REINFORCE∇θ Ez∼πθ (z|x) [L(z)] = ∇θ∑

L(z)πθ (z | x)z
(By de ni on of expecta on. How to evaluate?)

=
=

∑
z
∑

L(z)∇θ πθ (z | x)L(z)πθ (z | x)∇θ log πθ (z | x)z
(By Leibniz integral rule for log )deep-spin.github.io/tutorial36Through the looking glass of REINFORCE∇θ Ez∼πθ (z|x) [L(z)] = ∇θ∑

L(z)πθ (z | x)z
(By de ni on of expecta on. How to evaluate?)

=
=

∑
z
∑

L(z)∇θ πθ (z | x)L(z)πθ (z | x)∇θ log πθ (z | x)z
(By Leibniz integral rule for log )deep-spin.github.io/tutorial= Ez∼πθ (z|x) [L(z)∇θ log πθ (z | x)]36

SPINN with REINFORCE, aka RL-SPINN

Yogatama et al. [2017] uses REINFORCE to train SPINN!

deep-spin.github.io/tutorial

37

SPINN with REINFORCE, aka RL-SPINN

Yogatama et al. [2017] uses REINFORCE to train SPINN!
However, this vanilla implementa on isn’t very e ec ve at learning syntax.

deep-spin.github.io/tutorial

37

SPINN with REINFORCE, aka RL-SPINN

Yogatama et al. [2017] uses REINFORCE to train SPINN!
However, this vanilla implementa on isn’t very e ec ve at learning syntax.
This model fails to solve a simple toy problem.

deep-spin.github.io/tutorial

37

[Nangia and Bowman, 2018]

Toy problem: ListOps[max 2 9 [min 4 7 ] 0 ]deep-spin.github.io/tutorial

38

[Nangia and Bowman, 2018]

Toy problem: ListOps

Model
LSTM
RL-SPINN
Random Trees

Accuracy
μ(σ )
max

Self
F1

71.5 (1.5)
60.7 (2.6)

74.4
64.8

30.8

-

-

30.1

deep-spin.github.io/tutorial

Model

LB

F1 wrt.
RB
GT

Avg.
Depth

48D RL-SPINN
128D RL-SPINN

64.5
43.5

16.0
13.0

32.1
71.1

14.6
10.4

GT Trees
Random Trees

41.6
24.0

8.8
24.0

100.0
24.2

9.6
5.2
39

[Nangia and Bowman, 2018]

Toy problem: ListOps

Model
LSTM
RL-SPINN
Random Trees

Accuracy
μ(σ )
max

Self
F1

71.5 (1.5)
60.7 (2.6)

74.4
64.8

30.8

-

-

30.1
LB

F1 wrt.
RB
GT

Avg.
Depth

48D RL-SPINN
128D RL-SPINN

64.5
43.5

16.0
13.0

32.1
71.1

14.6
10.4

GT Trees
Random Trees

41.6
24.0

8.8
24.0

100.0
24.2

9.6
5.2

But
why?
Model

deep-spin.github.io/tutorial

39

RL-SPINN’s Troubles

This system faces at least two big problems,

deep-spin.github.io/tutorial

40

RL-SPINN’s Troubles

This system faces at least two big problems,
1. High variance of gradients
2. Coadapta on

deep-spin.github.io/tutorial

40

High variance• We have a single reward at the end of parsing.

deep-spin.github.io/tutorial

41

High variance• We have a single reward at the end of parsing.
• We are sampling parses from very large search space!
Catalan number of binary trees.

deep-spin.github.io/tutorial

41

High variance• We have a single reward at the end of parsing.
• We are sampling parses from very large search space!
Catalan number of binary trees.
3 tokens ⇒ 5 trees
5 tokens ⇒ 42 trees
10 tokens ⇒ 16796 trees

deep-spin.github.io/tutorial

41

High variance• We have a single reward at the end of parsing.
• We are sampling parses from very large search space!
Catalan number of binary trees.
• And the policy is stochas c.

deep-spin.github.io/tutorial

41

High variance
So, some mes the policy lands in a “rewarding state”:[sm [sm [sm [max 5 6 ] 2 ] 0 ] 5 0 8 6 ]Figure: Truth: 7; Pred: 7

deep-spin.github.io/tutorial

42

High varianceSome mes it doesn’t:[max [med [med 1 [sm 3 1 3 ] 9 ] 6 ] 5 ]deep-spin.github.io/tutorial

Figure: Truth: 6; Pred: 542High variance

Catalan number of parses means we need many many samples to lower variance!

deep-spin.github.io/tutorial

43

High variance

Catalan number of parses means we need many many samples to lower variance!
Possible solu ons,
1. Gradient normaliza on
2. Control variates, aka baselines

deep-spin.github.io/tutorial

43

Control variates• A simple control variate: moving average of recent rewards

deep-spin.github.io/tutorial

44

Control variates• A simple control variate: moving average of recent rewards• Parameters are updated using the advantage which is the di erence between the
reward, R, and the baseline predic on.

deep-spin.github.io/tutorial

44

Control variates• A simple control variate: moving average of recent rewards• Parameters are updated using the advantage which is the di erence between the
reward, R, and the baseline predic on.
So,∇Ez∼π(z) = Ez∼π(z) [(L(z) − b(x)) ∇π (z)]deep-spin.github.io/tutorial

44

Control variates• A simple control variate: moving average of recent rewards• Parameters are updated using the advantage which is the di erence between the
reward, R, and the baseline predic on.
So,∇Ez∼π(z) = Ez∼π(z) [(L(z) − b(x)) ∇π (z)]Which we can do because,∑∑b(x)∇π (z) = b(x)∇π (z) = b(x)∇1 = 0z

deep-spin.github.io/tutorialz

44Issues with SPINN with REINFORCE

This system faces two big problems,
1. High variance of gradients
2. Coadapta on

deep-spin.github.io/tutorial

45

Coadapta on problem
Learning composi on func on parameters φ with backpropaga on,
and parser parameters θ with REINFORCE.

deep-spin.github.io/tutorial46

Coadapta on problem
Learning composi on func on parameters φ with backpropaga on,
and parser parameters θ with REINFORCE.
Generally, φ will be learned more quickly than θ,
making it harder to explore the parsing search space and op mize for θ.

deep-spin.github.io/tutorial46

Coadapta on problem
Learning composi on func on parameters φ with backpropaga on,
and parser parameters θ with REINFORCE.
Generally, φ will be learned more quickly than θ,
making it harder to explore the parsing search space and op mize for θ.
Di erence in variance of two gradient es mates.

deep-spin.github.io/tutorial46

Coadapta on problem
Learning composi on func on parameters φ with backpropaga on,
and parser parameters θ with REINFORCE.
Generally, φ will be learned more quickly than θ,
making it harder to explore the parsing search space and op mize for θ.

Possible solu on:
Proximal Policy Op miza on (Schulman et al., 2017)

Di erence in variance of two gradient es mates.

deep-spin.github.io/tutorial46

Making REINFORCE+SPINN work
Havrylov et al. [2019] use,
1. Input dependent control variate
2. Gradient normaliza on
3. Proximal Policy Op miza on

deep-spin.github.io/tutorial

47

Making REINFORCE+SPINN work
Havrylov et al. [2019] use,
1. Input dependent control variate
2. Gradient normaliza on
3. Proximal Policy Op miza on

They solve ListOps!

deep-spin.github.io/tutorial

47

Making REINFORCE+SPINN work
Havrylov et al. [2019] use,
1. Input dependent control variate
2. Gradient normaliza on
3. Proximal Policy Op miza on

They solve ListOps!
However, does not learn English grammars.

deep-spin.github.io/tutorial

47

Should I? Shouldn’t I?

• Unbiased!

deep-spin.github.io/tutorial48

Should I? Shouldn’t I?

• Unbiased!

deep-spin.github.io/tutorial• High variance48

Should I? Shouldn’t I?

• Unbiased!

• High variance• In a simple se ng, with enoughtricks, it can work!

deep-spin.github.io/tutorial48

Should I? Shouldn’t I?

• Unbiased!

• High variance• In a simple se ng, with enoughtricks, it can work!

• Has not yet been very e ec ve atlearning English syntax.

deep-spin.github.io/tutorial48

III. Gradient
Surrogates

So far:• Tackled expected loss in a stochas c computa on graphEπθ (z|x) L(z)deep-spin.github.io/tutorial49

So far:• Tackled expected loss in a stochas c computa on graphEπθ (z|x) L(z)• Op mized with the REINFORCE es mator.

deep-spin.github.io/tutorial49

So far:• Tackled expected loss in a stochas c computa on graphEπθ (z|x) L(z)• Op mized with the REINFORCE es mator.
• Struggled with variance & sampling.

deep-spin.github.io/tutorial49

So far:• Tackled expected loss in a stochas c computa on graphEπθ (z|x) L(z)• Op mized with the REINFORCE es mator.
• Struggled with variance & sampling.

In this sec on:• Consider the determinis c alterna ve:

deep-spin.github.io/tutorial49

So far:• Tackled expected loss in a stochas c computa on graphEπθ (z|x) L(z)• Op mized with the REINFORCE es mator.
• Struggled with variance & sampling.

In this sec on:• Consider the determinis c alterna ve:ẑ(x) := arg maxz∈M πθ (z | x)
pick “best” structure

deep-spin.github.io/tutorial49

So far:• Tackled expected loss in a stochas c computa on graphEπθ (z|x) L(z)• Op mized with the REINFORCE es mator.
• Struggled with variance & sampling.

In this sec on:• Consider the determinis c alterna ve:ẑ(x) := arg maxz∈M πθ (z | x)
pick “best” structure
L ẑ(x)incur loss

deep-spin.github.io/tutorial49

So far:• Tackled expected loss in a stochas c computa on graphEπθ (z|x) L(z)• Op mized with the REINFORCE es mator.
• Struggled with variance & sampling.

In this sec on:• Consider the determinis c alterna ve:ẑ(x) := arg maxz∈M πθ (z | x)
pick “best” structure
L ẑ(x)incur loss
• 3A: try to op mize the determinis c loss directly
deep-spin.github.io/tutorial49

So far:• Tackled expected loss in a stochas c computa on graphEπθ (z|x) L(z)• Op mized with the REINFORCE es mator.
• Struggled with variance & sampling.

In this sec on:• Consider the determinis c alterna ve:ẑ(x) := arg maxz∈M πθ (z | x)
pick “best” structure
L ẑ(x)incur loss
• 3A: try to op mize the determinis c loss directly• 3B: use this strategy to reduce variance in the stochas c model.
deep-spin.github.io/tutorial

49

Recap: The argmax problemsz = arg max(s)

z
z=1
z=2
···

z1
1

0

s2 − 1s2

s2 + 1

s1

z=N
∂z
=0
∂s
deep-spin.github.io/tutorial

50

So maxps
pj = exp(sj )/ Z

z=1
z=2
···

p1
1

0

s2 − 1s2

s2 + 1s1

z=N∂p= diag(p) − pp⊤∂sdeep-spin.github.io/tutorial

51

[Hinton, 2012, Bengio et al., 2013]

Straight-Through Es matorsdeep-spin.github.io/tutorial

52

[Hinton, 2012, Bengio et al., 2013]

Straight-Through Es mator• Forward: z = arg max(s)sdeep-spin.github.io/tutorialz

52

[Hinton, 2012, Bengio et al., 2013]

Straight-Through Es mator• Forward: z = arg max(s)sdeep-spin.github.io/tutorialz

52

[Hinton, 2012, Bengio et al., 2013]

Straight-Through Es mator• Forward: z = arg max(s)• Backward: pretend z was some con nuous p̃; ∂∂sp̃ =
/ 0

s

z

p̃

deep-spin.github.io/tutorial

52

[Hinton, 2012, Bengio et al., 2013]

Straight-Through Es mator• Forward: z = arg max(s)• Backward: pretend z was some con nuous p̃; ∂∂sp̃ =
/ 0

s

z

p̃

deep-spin.github.io/tutorial

52

[Hinton, 2012, Bengio et al., 2013]

Straight-Through Es mator• Forward: z = arg max(s)• Backward: pretend z was some con nuous p̃; ∂∂sp̃ =
/ 0

s

z

• simplest: iden ty, p̃(s) = s, ∂p̃ = I∂sp̃

deep-spin.github.io/tutorial

52

[Hinton, 2012, Bengio et al., 2013]

Straight-Through Es mator• Forward: z = arg max(s)• Backward: pretend z was some con nuous p̃; ∂∂sp̃ =
/ 0

s

z

• simplest: iden ty, p̃(s) = s, ∂p̃ = I∂s• others, e.g. so max p̃(s) = softmax(s), ∂p̃ = diag(p̃) − p̃p̃⊤∂sp̃

deep-spin.github.io/tutorial

52

[Hinton, 2012, Bengio et al., 2013]

Straight-Through Es mator• Forward: z = arg max(s)• Backward: pretend z was some con nuous p̃; ∂∂sp̃ =
/ 0

s

z

• simplest: iden ty, p̃(s) = s, ∂p̃ = I∂s• others, e.g. so max p̃(s) = softmax(s), ∂p̃ = diag(p̃) − p̃p̃⊤∂s• More explana on in a whilep̃

deep-spin.github.io/tutorial

52

[Hinton, 2012, Bengio et al., 2013]

Straight-Through Es mator• Forward: z = arg max(s)• Backward: pretend z was some con nuous p̃; ∂∂sp̃ =
/ 0

s

z

• simplest: iden ty, p̃(s) = s, ∂p̃ = I∂s• others, e.g. so max p̃(s) = softmax(s), ∂p̃ = diag(p̃) − p̃p̃⊤∂s• More explana on in a while

What about the structured case?

deep-spin.github.io/tutorialp̃

52

Dealing with the combinatorial explosion
→

→

→ ···

1. Incremental structures
max · · · ,

,

,

, ···

2. Factoriza on into parts• Build structure greedily, as sequence• Op mizes globally (e.g. Viterbi,
of discrete choices (e.g., shi -reduce).
Chu-Liu-Edmonds, Kuhn-Munkres).
• Scores (par al structure, ac on) tuples. • Scores smaller parts.
• Advantages: exible, rich histories.
• Advantages: op mal, elegant, canhandle hard & global constraints.
• Disadvantages: greedy, local decisions• Disadvantages: strong assump ons.
are subop mal, error propaga on.
deep-spin.github.io/tutorial

53

STE for incremental structures

deep-spin.github.io/tutorial

54

STE for incremental structures• Build a structure as a sequence of discrete choices (e.g., shi -reduce)

deep-spin.github.io/tutorial

54

STE for incremental structures• Build a structure as a sequence of discrete choices (e.g., shi -reduce)• Assigns a score to any (par al structure, ac on) tuple.

deep-spin.github.io/tutorial

54

STE for incremental structures• Build a structure as a sequence of discrete choices (e.g., shi -reduce)• Assigns a score to any (par al structure, ac on) tuple.
• In this case, we just apply the straight-through es mator for each step.

deep-spin.github.io/tutorial

54

STE for incremental structures• Build a structure as a sequence of discrete choices (e.g., shi -reduce)• Assigns a score to any (par al structure, ac on) tuple.
• In this case, we just apply the straight-through es mator for each step.
• Forward: the highest scoring ac on for each step

deep-spin.github.io/tutorial

54

STE for incremental structures• Build a structure as a sequence of discrete choices (e.g., shi -reduce)• Assigns a score to any (par al structure, ac on) tuple.
• In this case, we just apply the straight-through es mator for each step.
• Forward: the highest scoring ac on for each step
• Backward: pretend that we had used a di eren able surrogate func on

deep-spin.github.io/tutorial

54

STE for incremental structures• Build a structure as a sequence of discrete choices (e.g., shi -reduce)• Assigns a score to any (par al structure, ac on) tuple.
• In this case, we just apply the straight-through es mator for each step.
• Forward: the highest scoring ac on for each step
• Backward: pretend that we had used a di eren able surrogate func on
Example: Latent Tree Learning with Di eren able Parsers: Shi -Reduce Parsing
and Chart Parsing [Maillard and Clark, 2018] (STE through beam search).

deep-spin.github.io/tutorial

54

STE for the factorized approach

Requires a bit more work:• Recap: marginal polytope• Predic ng structures globally: Maximum A Posteriori (MAP)• Deriving Straight-Through and SPIGOT

deep-spin.github.io/tutorial

55

[Wainwright and Jordan, 2008]

The structured case: Marginal polytope

Mdeep-spin.github.io/tutorial

56

[Wainwright and Jordan, 2008]

The structured case: Marginal polytope• Each vertex corresponds to one such bit vector zMdeep-spin.github.io/tutorial

56

[Wainwright and Jordan, 2008]

The structured case: Marginal polytope• Each vertex corresponds to one such bit vector z• Points inside correspond to marginal distribu ons:
convex combina ons of structured objects
μ = p1 z1 + . . . + pN zN , p ∈ ∆.
|
{z
}

M

exponen ally many terms

p1 = 0.2,
p2 = 0.7,
p3 = 0.1,

z1 = [1, 0, 0, 0, 1, 0, 0, 0, 1]
z2 = [0, 0, 1, 0, 0, 1, 1, 0, 0]
z3 = [1, 0, 0, 0, 1, 0, 0, 1, 0]

deep-spin.github.io/tutorial⇒

μ=[.3, 0, .7, 0, .3, .7, .7, .1, .2].
56

Predic ng structures from scores of parts• η(i → j): score of arc i → j• z(i → j): is arc i → j selected?

deep-spin.github.io/tutorialηz

outputey57

Predic ng structures from scores of parts• η(i → j): score of arc i → j• z(i → j): is arc i → j selected?

ηzoutputey• Task-speci c algorithm for thehighest-scoring structure.

deep-spin.github.io/tutorial

57

Algorithms for speci c structures
Best structure (MAP)
Sequence tagging

Viterbi[Rabiner, 1989]

CKY
Cons tuent trees

Temporal alignments
Dependency trees
Assignments
deep-spin.github.io/tutorial[Kasami, 1966, Younger, 1967][Cocke and Schwartz, 1970]

DTW[Sakoe and Chiba, 1978]

Max. Spanning Arborescence[Chu and Liu, 1965, Edmonds, 1967]

Kuhn-Munkres[Kuhn, 1955, Jonker and Volgenant, 1987]
58

Structured Straight-Through• Forward pass:Find highest-scoring structure:z = arg max η⊤ z

η

z

z∈Z

• Backward pass:pretend we used μ̃ = η.

μ̃

deep-spin.github.io/tutorial

59

[Mar ns and Niculae, 2019]

Straight-Through Es mator
Revisiteddeep-spin.github.io/tutorial

60

[Mar ns and Niculae, 2019]

Straight-Through Es mator
Revisited• In the forward pass, z = arg max(s).

deep-spin.github.io/tutorial

60

[Mar ns and Niculae, 2019]

Straight-Through Es mator
Revisited• In the forward pass, z = arg max(s).
• if we had labels (mul -task learning), LMTL = L ŷ(z), y +Lhid (s, ztrue )deep-spin.github.io/tutorial

60

[Mar ns and Niculae, 2019]

Straight-Through Es mator
Revisited• In the forward pass, z = arg max(s).
• if we had labels (mul -task learning), LMTL = L ŷ(z), y +Lhid (s, ztrue )• One choice: perceptron loss Lhid (s, ztrue ) = s⊤ z − s⊤ ztrue ; ∂L∂shid = z − ztrue .

deep-spin.github.io/tutorial

60

[Mar ns and Niculae, 2019]

Straight-Through Es mator
Revisited• In the forward pass, z = arg max(s).
• if we had labels (mul -task learning), LMTL = L ŷ(z), y +Lhid (s, ztrue )• One choice: perceptron loss Lhid (s, ztrue ) = s⊤ z − s⊤ ztrue ; ∂L∂shid = z − ztrue .
• We don’t have labels! Induce labels by “pulling back” the downstream target:
the “best” (unconstrained) latent value would be: arg minz̃∈RD L ŷ(z̃), y

deep-spin.github.io/tutorial

60

[Mar ns and Niculae, 2019]

Straight-Through Es mator
Revisited• In the forward pass, z = arg max(s).
• if we had labels (mul -task learning), LMTL = L ŷ(z), y +Lhid (s, ztrue )• One choice: perceptron loss Lhid (s, ztrue ) = s⊤ z − s⊤ ztrue ; ∂L∂shid = z − ztrue .
• We don’t have labels! Induce labels by “pulling back” the downstream target:
the “best” (unconstrained) latent value would be: arg minz̃∈RD L ŷ(z̃), y• One gradient descent step star ng from z: ztrue ← z − ∂L∂zdeep-spin.github.io/tutorial

60

[Mar ns and Niculae, 2019]

Straight-Through Es mator
Revisited• In the forward pass, z = arg max(s).
• if we had labels (mul -task learning), LMTL = L ŷ(z), y +Lhid (s, ztrue )• One choice: perceptron loss Lhid (s, ztrue ) = s⊤ z − s⊤ ztrue ; ∂L∂shid = z − ztrue .
• We don’t have labels! Induce labels by “pulling back” the downstream target:
the “best” (unconstrained) latent value would be: arg minz̃∈RD L ŷ(z̃), y• One gradient descent step star ng from z: ztrue ← z − ∂L
∂z
∂LMTL
∂s

=

∂L
∂s
|{z}

+

∂Lhid
∂s

=0
deep-spin.github.io/tutorial

60

[Mar ns and Niculae, 2019]

Straight-Through Es mator
Revisited• In the forward pass, z = arg max(s).
• if we had labels (mul -task learning), LMTL = L ŷ(z), y +Lhid (s, ztrue )• One choice: perceptron loss Lhid (s, ztrue ) = s⊤ z − s⊤ ztrue ; ∂L∂shid = z − ztrue .
• We don’t have labels! Induce labels by “pulling back” the downstream target:
the “best” (unconstrained) latent value would be: arg minz̃∈RD L ŷ(z̃), y• One gradient descent step star ng from z: ztrue ← z − ∂L
∂z


∂LMTL
∂L
∂Lhid
∂L
∂L
=
+
=z− z−
=
∂s
∂s
∂s
∂z
∂z
|{z}
=0
deep-spin.github.io/tutorial

60

[Peng et al., 2018, Mar ns and Niculae, 2019]

Straight-Through in the structured case

• Structured STE: perceptron update with induced annota on
arg min L(ŷ(μ), y)μ∈RD

ztrue = z - ∇zL(z)≈ z − ∇z L(z) → ztrue
z(one step of gradient descent)deep-spin.github.io/tutorial

61

[Peng et al., 2018, Mar ns and Niculae, 2019]

Straight-Through in the structured case

• Structured STE: perceptron update with induced annota on
arg min L(ŷ(μ), y)μ∈RD

ztrue = z - ∇zL(z)≈ z − ∇z L(z) → ztrue
z(one step of gradient descent)• SPIGOT takes into account the constraints; uses the induced
annota onarg min L(ŷ(μ), y) ≈ ProjM z − ∇z L(z) → ztrue

z - ∇zL(z)μ∈M(one step of projected gradient descent!)
deep-spin.github.io/tutorial

ztrue
z

61

[Peng et al., 2018, Mar ns and Niculae, 2019]

Straight-Through in the structured case

• Structured STE: perceptron update with induced annota on
arg min L(ŷ(μ), y)μ∈RD

ztrue = z - ∇zL(z)≈ z − ∇z L(z) → ztrue
z(one step of gradient descent)• SPIGOT takes into account the constraints; uses the induced
annota onarg min L(ŷ(μ), y) ≈ ProjM z − ∇z L(z) → ztrue

z - ∇zL(z)μ∈M(one step of projected gradient descent!)

ztrue
z

• We discuss a generic way to compute the projec on in part 4.
deep-spin.github.io/tutorial

61

Summary: Straight-Through Es mator

deep-spin.github.io/tutorial

62

Summary: Straight-Through Es mator

We saw how to use the Straight-Through Es mator to allow learning models withargmax in the middle of the computa on graph.

deep-spin.github.io/tutorial

62

Summary: Straight-Through Es mator

We saw how to use the Straight-Through Es mator to allow learning models withargmax in the middle of the computa on graph.

We were op mizing
L ẑ(x)deep-spin.github.io/tutorial

62

Summary: Straight-Through Es mator

We saw how to use the Straight-Through Es mator to allow learning models withargmax in the middle of the computa on graph.

We were op mizing
L ẑ(x)
Now we will see how to apply STE for stochas c graphs, as an alterna ve
approach of REINFORCE.

deep-spin.github.io/tutorial

62

Stochas c node in the computa on graphdeep-spin.github.io/tutorial

63

Stochas c node in the computa on graph

Recall the stochas c objec ve:Eπθ (z|x) L(z)deep-spin.github.io/tutorial

63

Stochas c node in the computa on graph

Recall the stochas c objec ve:Eπθ (z|x) L(z)• REINFORCE (previous sec on).

deep-spin.github.io/tutorial

63

Stochas c node in the computa on graph

Recall the stochas c objec ve:Eπθ (z|x) L(z)• REINFORCE (previous sec on). High variance.

deep-spin.github.io/tutorial

63

Stochas c node in the computa on graph

Recall the stochas c objec ve:Eπθ (z|x) L(z)• REINFORCE (previous sec on). High variance.
• An alterna ve is using the reparameteriza on trick [Kingma and Welling, 2014].

deep-spin.github.io/tutorial

63

Categorical reparameteriza on

deep-spin.github.io/tutorial

64

Categorical reparameteriza on• Sampling from a categorical value inthe middle of the computa on graph.
z ∼ πθ (z | x) ∝ exp sθ (z | x)

deep-spin.github.io/tutorial

s

z

64

[Jang et al., 2017, Maddison et al., 2016]

Categorical reparameteriza on• Sampling from a categorical value inthe middle of the computa on graph.
z ∼ πθ (z | x) ∝ exp sθ (z | x)∂z
• What is the gradient of a sample ∂θ?!

deep-spin.github.io/tutorial

s

z

64

[Jang et al., 2017, Maddison et al., 2016]

Categorical reparameteriza on• Sampling from a categorical value inthe middle of the computa on graph.
z ∼ πθ (z | x) ∝ exp sθ (z | x)∂z
• What is the gradient of a sample ∂θ?!

• Reparameteriza on: Move thestochas city out of the gradient path.

deep-spin.github.io/tutorialsz

𝝐 (stochastic)

64

[Jang et al., 2017, Maddison et al., 2016]

Categorical reparameteriza on• Sampling from a categorical value inthe middle of the computa on graph.
z ∼ πθ (z | x) ∝ exp sθ (z | x)∂z
• What is the gradient of a sample ∂θ?!

• Reparameteriza on: Move thestochas city out of the gradient path.
• Makes z determinis c w.r.t. s!

deep-spin.github.io/tutorial

s+𝝐

s

z

+

𝝐 (stochastic)

64

[Jang et al., 2017, Maddison et al., 2016]

Categorical reparameteriza on• Sampling from a categorical value inthe middle of the computa on graph.
z ∼ πθ (z | x) ∝ exp sθ (z | x)∂z
• What is the gradient of a sample ∂θ?!

• Reparameteriza on: Move thestochas city out of the gradient path.
• Makes z determinis c w.r.t. s!

deep-spin.github.io/tutorial

s+𝝐

s

z

+

𝝐 (stochastic)

64

[Jang et al., 2017, Maddison et al., 2016]

Categorical reparameteriza on• Sampling from a categorical value inthe middle of the computa on graph.
z ∼ πθ (z | x) ∝ exp sθ (z | x)∂z
• What is the gradient of a sample ∂θ
?!

s+𝝐

s

z

+

As a result:• Reparameteriza on: Move the
Stochas city is moved as an input.
stochas city out of the gradient path.
𝝐 (stochastic)
We can backpropagate through the determinis c input to z.
• Makes z determinis c w.r.t. s!

deep-spin.github.io/tutorial

64

[Jang et al., 2017, Maddison et al., 2016]

Categorical reparameteriza on
s+𝝐

s

z

+

𝝐 (stochastic)

deep-spin.github.io/tutorial

65

[Jang et al., 2017, Maddison et al., 2016]

Categorical reparameteriza on
s+𝝐

s

z

+

How do we
sample from a categorical variable?
𝝐 (stochastic)

deep-spin.github.io/tutorial

65Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:

deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:• p = softmax(s)deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:• p = softmax(s)∑• ci = j≤i pj

deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:• p = softmax(s)∑• ci = j≤i pj• u ∼ Uniform(0, 1)

deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:• p = softmax(s)∑• ci = j≤i pj• u ∼ Uniform(0, 1)• return z = et s.t. ct ≤ u < ct+1

deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:

2. The Gumbel-Max trick• p = softmax(s)∑• ci = j≤i pj• u ∼ Uniform(0, 1)• return z = et s.t. ct ≤ u < ct+1

deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:• p = softmax(s)∑• ci = j≤i pj• u ∼ Uniform(0, 1)

2. The Gumbel-Max trick• ui ∼ Uniform(0, 1)• return z = et s.t. ct ≤ u < ct+1

deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:• p = softmax(s)∑• ci = j≤i pj• u ∼ Uniform(0, 1)

2. The Gumbel-Max trick• ui ∼ Uniform(0, 1)• εi = − log(− log(ui ))• return z = et s.t. ct ≤ u < ct+1

deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:• p = softmax(s)∑• ci = j≤i pj• u ∼ Uniform(0, 1)

2. The Gumbel-Max trick• ui ∼ Uniform(0, 1)• εi = − log(− log(ui ))• z = arg max(s + ε)

• return z = et s.t. ct ≤ u < ct+1

deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:• p = softmax(s)∑• ci = j≤i pj• u ∼ Uniform(0, 1)

2. The Gumbel-Max trick• ui ∼ Uniform(0, 1)• εi = − log(− log(ui ))• z = arg max(s + ε)

• return z = et s.t. ct ≤ u < ct+1
The two methods are equivalent. (Not obvious, but we will not prove it now.)

deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:• p = softmax(s)∑• ci = j≤i pj• u ∼ Uniform(0, 1)

2. The Gumbel-Max trick• ui ∼ Uniform(0, 1)• εi = − log(− log(ui ))• z = arg max(s + ε)

• return z = et s.t. ct ≤ u < ct+1
The two methods are equivalent. (Not obvious, but we will not prove it now.)
Requires sampling from the Standard Gumbel Distribu on G(0,1).

deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:• p = softmax(s)∑• ci = j≤i pj• u ∼ Uniform(0, 1)

2. The Gumbel-Max trick• ui ∼ Uniform(0, 1)• εi = − log(− log(ui ))• z = arg max(s + ε)

• return z = et s.t. ct ≤ u < ct+1
The two methods are equivalent. (Not obvious, but we will not prove it now.)
Requires sampling from the Standard Gumbel Distribu on G(0,1).
Deriva on & more info: [Adams, 2013, Vieira, 2014]
deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:• p = softmax(s)∑• ci = j≤i pj• u ∼ Uniform(0, 1)

s+𝝐s

2. The Gumbel-Max trick• ui ∼z Uniform(0, 1)• εi = − log(− log(ui ))+• z = arg max(s + ε)

• return z = et s.t. ct ≤ u < ct+1
𝝐 (stochastic)

The two methods are equivalent. (Not obvious, but we will not prove it now.)
Requires sampling from the Standard Gumbel Distribu on G(0,1).
Deriva on & more info: [Adams, 2013, Vieira, 2014]
deep-spin.github.io/tutorial

66

Sampling from a categorical variable
We want to sample from a categorical variable with scores s (class i has a score si )1. Inverse transform sampling:• p = softmax(s)∑• ci = j≤i pj• u ∼ Uniform(0, 1)

s+𝝐s

2. The Gumbel-Max trick• ui ∼z Uniform(0, 1)• εi = − log(− log(ui ))+• z = arg max(s + ε)

• return z = et s.t. ct ≤ u < ct+1We have an argmax again

and cannot backpropagate!

𝝐 (stochastic)

The two methods are equivalent. (Not obvious, but we will not prove it now.)
Requires sampling from the Standard Gumbel Distribu on G(0,1).
Deriva on & more info: [Adams, 2013, Vieira, 2014]
deep-spin.github.io/tutorial

66

[Jang et al., 2017, Maddison et al., 2016]

Straight-Through Gumbel Es mator
Apply a variant of the Straight-Through Es mator to Gumbel-Max!

deep-spin.github.io/tutorial

67

[Jang et al., 2017, Maddison et al., 2016]

Straight-Through Gumbel Es mator
Apply a variant of the Straight-Through Es mator to Gumbel-Max!

• Forward: z = arg max(s + ε)

s+𝝐

s

z

+

p̃

𝝐
𝝐i =-log(-log(ui))
ui~U(0,1)

deep-spin.github.io/tutorial

67

[Jang et al., 2017, Maddison et al., 2016]

Straight-Through Gumbel Es mator
Apply a variant of the Straight-Through Es mator to Gumbel-Max!

• Forward: z = arg max(s + ε)s+𝝐s

• Backward: pretend we haddonep̃ = softmax(s + ε)

z

+

p̃

𝝐
𝝐i =-log(-log(ui))
ui~U(0,1)

deep-spin.github.io/tutorial

67

[Jang et al., 2017, Maddison et al., 2016]

Straight-Through Gumbel Es mator
Apply a variant of the Straight-Through Es mator to Gumbel-Max!

• Forward: z = arg max(s + ε)s+𝝐s

• Backward: pretend we haddonep̃ = softmax(s + ε)z+What about the structured case?

p̃𝝐
𝝐i =-log(-log(ui))
ui~U(0,1)

deep-spin.github.io/tutorial

67

Dealing with the combinatorial explosion
→

→

→ ···

1. Incremental structures
max · · · ,

,

,

, ···

2. Factoriza on into parts• Build structure greedily, as sequence• Op mizes globally (e.g. Viterbi,
of discrete choices (e.g., shi -reduce).
Chu-Liu-Edmonds, Kuhn-Munkres).
• Scores (par al structure, ac on) tuples. • Scores smaller parts.
• Advantages: exible, rich histories.
• Advantages: op mal, elegant, canhandle hard & global constraints.
• Disadvantages: greedy, local decisions• Disadvantages: strong assump ons.
are subop mal, error propaga on.
deep-spin.github.io/tutorial

68Sampling from incremental structures

deep-spin.github.io/tutorial

69

Sampling from incremental structures• Build a structure as a sequence of discrete choices (e.g., shi -reduce)

deep-spin.github.io/tutorial

69

Sampling from incremental structures• Build a structure as a sequence of discrete choices (e.g., shi -reduce)• Assigns a score to any (par al structure, ac on) tuple.

deep-spin.github.io/tutorial

69

Sampling from incremental structures• Build a structure as a sequence of discrete choices (e.g., shi -reduce)• Assigns a score to any (par al structure, ac on) tuple.

• Reparameterize the scores with Gumbel-Max - now we have a determinis c node.

deep-spin.github.io/tutorial

69

Sampling from incremental structures• Build a structure as a sequence of discrete choices (e.g., shi -reduce)• Assigns a score to any (par al structure, ac on) tuple.

• Reparameterize the scores with Gumbel-Max - now we have a determinis c node.
• Forward: the argmax from the reparameterized scores for each step

deep-spin.github.io/tutorial

69

Sampling from incremental structures• Build a structure as a sequence of discrete choices (e.g., shi -reduce)• Assigns a score to any (par al structure, ac on) tuple.

• Reparameterize the scores with Gumbel-Max - now we have a determinis c node.
• Forward: the argmax from the reparameterized scores for each step
• Backward: pretend we had used a di eren able surrogate func on

deep-spin.github.io/tutorial

69

Sampling from incremental structures• Build a structure as a sequence of discrete choices (e.g., shi -reduce)• Assigns a score to any (par al structure, ac on) tuple.

• Reparameterize the scores with Gumbel-Max - now we have a determinis c node.
• Forward: the argmax from the reparameterized scores for each step
• Backward: pretend we had used a di eren able surrogate func on
Example: Gumbel Tree-LSTM [Choi et al., 2018].

deep-spin.github.io/tutorial

69

[Choi et al., 2018]

Example: Gumbel Tree-LSTM• Building task-speci c tree structures.
• Straight-Through Gumbel-So max at each step to select one arc.

The catsat

v1 = 0.5The

deep-spin.github.io/tutorial

v2 = 0.4

v2 = 0.1
The catqon

cat satcat

sat on

sat

on

70

[Papandreou and Yuille, 2011, Corro and Titov, 2019a,b]

Sampling from factorized models
Perturb-and-MAP
Reparameterize by perturbing the arc scores. (inexact!)

deep-spin.github.io/tutorial71[Papandreou and Yuille, 2011, Corro and Titov, 2019a,b]

Sampling from factorized models
Perturb-and-MAP
Reparameterize by perturbing the arc scores. (inexact!)• Sample from the normal Gumbel distribu on.

deep-spin.github.io/tutorial• ε ∼ G(0, 1)

71

[Papandreou and Yuille, 2011, Corro and Titov, 2019a,b]

Sampling from factorized models
Perturb-and-MAP
Reparameterize by perturbing the arc scores. (inexact!)• Sample from the normal Gumbel distribu on.

• ε ∼ G(0, 1)• Perturb the arc scores with the Gumbel noise.

• η̃ = η + ε

deep-spin.github.io/tutorial71[Papandreou and Yuille, 2011, Corro and Titov, 2019a,b]

Sampling from factorized models
Perturb-and-MAP
Reparameterize by perturbing the arc scores. (inexact!)• Sample from the normal Gumbel distribu on.

• ε ∼ G(0, 1)• Perturb the arc scores with the Gumbel noise.

• η̃ = η + ε• Compute MAP (task-speci c algorithm).

• arg maxz∈Z η̃⊤ zdeep-spin.github.io/tutorial71[Papandreou and Yuille, 2011, Corro and Titov, 2019a,b]

Sampling from factorized models
Perturb-and-MAP
Reparameterize by perturbing the arc scores. (inexact!)• Sample from the normal Gumbel distribu on.

• ε ∼ G(0, 1)• Perturb the arc scores with the Gumbel noise.

• η̃ = η + ε• Compute MAP (task-speci c algorithm).

• arg maxz∈Z η̃⊤ z• Backward: we could use Straight-Through with
Iden ty.
deep-spin.github.io/tutorial

71Summary: Gradient surrogates• Based on the Straight-Through Es mator.
• Can be used for stochas c or determinis c computa on graphs.
• Forward pass: Get an argmax (might be structured).
• Backpropaga on: use a func on, which we hope is close to argmax.
• Examples:• Argmax for itera ve structures and factoriza on into parts• Sampling from itera ve structures and factoriza on into parts

deep-spin.github.io/tutorial72

Gradient surrogates: Pros and cons
Pros
• Do not su er from the high variance problem of REINFORCE.
• Allow for exibility to select or sample a latent structured in the middle of thecomputa on graph.
• E cient computa on.

Cons• The Gumbel sampling with Perturb-and-MAP is an approxima on.
• Bias, due to func on mismatch on the backpropaga on(next sec on will address this problem.)deep-spin.github.io/tutorial73

OverviewEπθ (z|x) L(z)L arg maxz πθ (z | x)

• REINFORCE• Straight-Through• Straight-Through Gumbel(Perturb & MAP)

• SPIGOT

deep-spin.github.io/tutorial

74

OverviewEπθ (z|x) L(z)L arg maxz πθ (z | x)
L Eπθ (z|x) [z]• REINFORCE• Straight-Through• Structured A n. Nets

• Straight-Through Gumbel(Perturb & MAP)

• SPIGOT• SparseMAPAnd more, a er the break!
deep-spin.github.io/tutorial74

IV. End-to-end
Di eren able
Relaxa ons

End-to-end di eren able relaxa ons

1. Digging into so max
2. Alterna ves to so max
3. Generalizing to structured predic on
4. Stochas city and global structures

Recall: Discrete choices & di eren ability
s

input
x
s = fθ (x)output
b
y

z
z=1
z=2
···
z=N

y = gφ (z, x)
p11∂z= 0 or n/a∂s
deep-spin.github.io/tutorial(argmax)0s2 − 1s2

s2 + 1s1
76

One solu on: smooth relaxa on

s = fθ (x)

z=1
z=2
···
z=N

p = softmax(
 s) = E[z], i.e. replace E f(z) with f E[z]deep-spin.github.io/tutorial

output
b
y

p

s

input
x

y = gφ (z, x)
p1
1

∂p
=
∂s

(so max)0s2 − 1s2

s2 + 1s1
76

One solu on: smooth relaxa on

s = fθ (x)

z=1
z=2
···
z=N

p = softmax(
 s) = E[z], i.e. replace E f(z) with f E[z]deep-spin.github.io/tutorial

output
b
y

p

s

input
x

y = gφ (z, x)
p1
1

∂p
=
∂s

(so max)0s2 − 1s2

s2 + 1s1
76

OverviewEπθ (z|x) L(z)L arg maxz πθ (z | x)

• REINFORCE• Straight-Through• Straight-Through Gumbel(Perturb & MAP)

• SPIGOT

deep-spin.github.io/tutorial
L Eπθ (z|x) [z]77What is so max?
exp siO en de ned via pi = ∑
,
exp
s
j
j

deep-spin.github.io/tutorial

but where does it come from?

78

What is so max?
exp siO en de ned via pi = ∑
,
exp
s
j
j

but where does it come from?

p ∈ △: probability distribu on over choices
1.5
1
0.5
0.5
0.5 1

deep-spin.github.io/tutorial

1

1.5

1.5

78

What is so max?
exp siO en de ned via pi = ∑
,
exp
s
j
j

but where does it come from?

p ∈ △: probability distribu on over choices
1.5
1
0.5

p = [0, 1, 0]
0.5
0.5 1

deep-spin.github.io/tutorial

1

1.5

1.5

78

What is so max?
exp siO en de ned via pi = ∑
,
exp
s
j
j

but where does it come from?

p ∈ △: probability distribu on over choices
p = [0, 0, 1]

1.5
1
0.5

0.5
0.5 1

deep-spin.github.io/tutorial

1

1.5

1.5

78

What is so max?
exp siO en de ned via pi = ∑
,
exp
s
j
j

but where does it come from?

p ∈ △: probability distribu on over choices
1.5
1p = [1/ 3, 1/ 3, 1/ 3]

0.5
0.5
0.5 1

deep-spin.github.io/tutorial

1

1.5

1.5

78

What is so max?
exp siO en de ned via pi = ∑
,
exp
s
j
j

but where does it come from?

p ∈ △: probability distribu on over choices
Expected score under p: Ei∼p si = p⊤ s

1.5s = [.7, .1, 1.5]

1
0.5
0.5
0.5 1

deep-spin.github.io/tutorial

1

1.5

1.5

78

What is so max?
exp siO en de ned via pi = ∑
,
exp
s
j
j

but where does it come from?

p ∈ △: probability distribu on over choices
Expected score under p: Ei∼p si = p⊤ sargmax1.5

s = [.7, .1, 1.5]

1
0.5
0.5
0.5 1

deep-spin.github.io/tutorial

1

1.5

1.5

78

What is so max?
exp siO en de ned via pi = ∑
,
exp
s
j
j

but where does it come from?

p ∈ △: probability distribu on over choices
Expected score under p: Ei∼p si = p⊤ sargmax maximizes expected score

1.5

s = [.7, .1, 1.5]p⋆ = [0, 0, 1]

1
0.5

0.5
0.5 1

1

1.5

1.5

arg max p⊤ s
deep-spin.github.io/tutorialp∈△
78

What is so max?
exp siO en de ned via pi = ∑
,
exp
s
j
j

but where does it come from?
(0, 0, 1)

p ∈ △: probability distribu on over choices
Expected score under p: Ei∼p si = p⊤ s

0.800
1.0
0

0

argmax maximizes expected score∑
Shannon entropy of p: H(p) = − i pi log pi

0

0
1.0
(1, 0, 0)

deep-spin.github.io/tutorial

00
0.8(0, 1, 0)78

What is so max?
exp siO en de ned via pi = ∑
,
exp
s
j
j

but where does it come from?
(0, 0, 1)

p ∈ △: probability distribu on over choices
Expected score under p: Ei∼p si = p⊤ s

1.000

argmax maximizes expected score∑
Shannon entropy of p: H(p) = − i pi log pi

00

1.4

1.6

00

(1, 0, 0)

1.600

so max maximizes expected score + entropy:(0, 1, 0)

arg max p⊤ s + H(p)p∈△deep-spin.github.io/tutorial

78

Varia onal form of so max
exp s

Proposi on. The unique solu on to arg max p⊤ s + H(p) is given by pj = ∑ expj s .
p∈△deep-spin.github.io/tutorial

i

i

79

Varia onal form of so max
exp s

Proposi on. The unique solu on to arg max p⊤ s + H(p) is given by pj = ∑ expj s .
p∈△

i

i

Explicit form of the op miza on problem:∑
maximizej pj sj − pj log pj
subject to p ≥ 0, p⊤ 1 = 1

deep-spin.github.io/tutorial

79

Varia onal form of so max
exp s

Proposi on. The unique solu on to arg max p⊤ s + H(p) is given by pj = ∑ expj s .
p∈△

i

i

Explicit form of the op miza on problem:∑
maximizej pj sj − pj log pj
subject to p ≥ 0, p⊤ 1 = 1
Lagrangian:L (p, ν, τ ) = −∑j pj sj − pj log pj − pdeep-spin.github.io/tutorial⊤ ν + τ (p⊤ 1 − 1)79Varia onal form of so max
exp s

Proposi on. The unique solu on to arg max p⊤ s + H(p) is given by pj = ∑ expj s .
p∈△

i

i

Explicit form of the op miza on problem:∑
maximizej pj sj − pj log pj
subject to p ≥ 0, p⊤ 1 = 1
Lagrangian:L (p, ν, τ ) = −∑j pj sj − pj log pj − p⊤ ν + τ (p⊤ 1 − 1)

Op mality condi ons (KKT):
0 = ∇pi L (p, ν, τ ) = −si + log pi + 1 − νi + τ
⊤

p ν=0
p∈△
ν≥0
deep-spin.github.io/tutorial

79

Varia onal form of so max
exp s

Proposi on. The unique solu on to arg max p⊤ s + H(p) is given by pj = ∑ expj s .
p∈△Explicit form of the op miza on problem:∑
maximizej pj sj − pj log pjiilog pi = si + νi − (τ + 1)

subject to p ≥ 0, p⊤ 1 = 1
Lagrangian:L (p, ν, τ ) = −∑j pj sj − pj log pj − p⊤ ν + τ (p⊤ 1 − 1)

Op mality condi ons (KKT):
0 = ∇pi L (p, ν, τ ) = −si + log pi + 1 − νi + τ
⊤

p ν=0
p∈△
ν≥0
deep-spin.github.io/tutorial

79

Varia onal form of so max
exp s

Proposi on. The unique solu on to arg max p⊤ s + H(p) is given by pj = ∑ expj s .
p∈△Explicit form of the op miza on problem:∑
maximizej pj sj − pj log pj
subject to p ≥ 0, p⊤ 1 = 1
Lagrangian:L (p, ν, τ ) = −∑j pj sj − pj log pj − piilog pi = si + νi − (τ + 1)
if pi = 0, r.h.s. must be −∞,thus pi > 0, so νi = 0.

⊤ ν + τ (p⊤ 1 − 1)

Op mality condi ons (KKT):
0 = ∇pi L (p, ν, τ ) = −si + log pi + 1 − νi + τ
⊤

p ν=0
p∈△
ν≥0
deep-spin.github.io/tutorial

79

Varia onal form of so max
exp s

Proposi on. The unique solu on to arg max p⊤ s + H(p) is given by pj = ∑ expj s .
p∈△Explicit form of the op miza on problem:∑
maximizej pj sj − pj log pj
subject to p ≥ 0, p⊤ 1 = 1
Lagrangian:L (p, ν, τ ) = −∑j pj sj − pj log pj − piilog pi = si + νi − (τ + 1)
if pi = 0, r.h.s. must be −∞,thus pi > 0, so νi = 0.

pi = exp(si )/ exp(τ+1) = exp(si )/ Z

⊤ ν + τ (p⊤ 1 − 1)

Op mality condi ons (KKT):
0 = ∇pi L (p, ν, τ ) = −si + log pi + 1 − νi + τ
⊤

p ν=0
p∈△
ν≥0
deep-spin.github.io/tutorial

79

Varia onal form of so max
exp s

Proposi on. The unique solu on to arg max p⊤ s + H(p) is given by pj = ∑ expj s .
p∈△Explicit form of the op miza on problem:∑
maximizej pj sj − pj log pj
subject to p ≥ 0, p⊤ 1 = 1
Lagrangian:L (p, ν, τ ) = −∑j pj sj − pj log pj − p⊤ ν + τ (p⊤ 1 − 1)iilog pi = si + νi − (τ + 1)
if pi = 0, r.h.s. must be −∞,thus pi > 0, so νi = 0.

pi = exp(si )/ exp(τ+1) = exp(si )/ Z∑
Must nd Z such that j pj = 1.

Op mality condi ons (KKT):
0 = ∇pi L (p, ν, τ ) = −si + log pi + 1 − νi + τ
⊤

p ν=0
p∈△
ν≥0
deep-spin.github.io/tutorial

79

Varia onal form of so max
exp s

Proposi on. The unique solu on to arg max p⊤ s + H(p) is given by pj = ∑ expj s .
p∈△Explicit form of the op miza on problem:∑
maximizej pj sj − pj log pj
subject to p ≥ 0, p⊤ 1 = 1
Lagrangian:L (p, ν, τ ) = −∑j pj sj − pj log pj − p⊤ ν + τ (p⊤ 1 − 1)iilog pi = si + νi − (τ + 1)
if pi = 0, r.h.s. must be −∞,thus pi > 0, so νi = 0.

pi = exp(si )/ exp(τ+1) = exp(si )/ Z∑
Must nd Z such that j pj = 1.
∑
Answer: Z = j exp(sj )Op mality condi ons (KKT):
0 = ∇pi L (p, ν, τ ) = −si + log pi + 1 − νi + τ
⊤

p ν=0
p∈△
ν≥0
deep-spin.github.io/tutorial

79

Varia onal form of so max
exp s

Proposi on. The unique solu on to arg max p⊤ s + H(p) is given by pj = ∑ expj s .
p∈△Explicit form of the op miza on problem:∑
maximizej pj sj − pj log pj
subject to p ≥ 0, p⊤ 1 = 1
Lagrangian:L (p, ν, τ ) = −∑j pj sj − pj log pj − p⊤ ν + τ (p⊤ 1 − 1)

Op mality condi ons (KKT):
0 = ∇pi L (p, ν, τ ) = −si + log pi + 1 − νi + τ⊤iilog pi = si + νi − (τ + 1)
if pi = 0, r.h.s. must be −∞,thus pi > 0, so νi = 0.

pi = exp(si )/ exp(τ+1) = exp(si )/ Z∑
Must nd Z such that j pj = 1.
∑
Answer: Z = j exp(sj )exp(si )So, pi = ∑.
j exp(sj )

p ν=0
p∈△
ν≥0
deep-spin.github.io/tutorial

Classic result, e.g., [Boyd and Vandenberghe, 2004,
Wainwright and Jordan, 2008]
79

[Niculae and Blondel, 2017]

Generalizing so max: Smoothed argmaxesp̂Ω (s) = arg max p⊤ s − Ω(p)
p∈△

p1
1

0

−1

0

1

s1

△
deep-spin.github.io/tutorial

80[Niculae and Blondel, 2017]

Generalizing so max: Smoothed argmaxesp̂Ω (s) = arg max p⊤ s − Ω(p)
p∈△

p1
1

0

−1

0

1

s1

△
deep-spin.github.io/tutorial

80[Niculae and Blondel, 2017]

Generalizing so max: Smoothed argmaxesp̂Ω (s) = arg max p⊤ s − Ω(p)
p∈△

p1
1

argmax: Ω(p) = 0
0

−1

0

1

s1

[0, 0, 1]△
deep-spin.github.io/tutorial

80[Niculae and Blondel, 2017]

Generalizing so max: Smoothed argmaxesp̂Ω (s) = arg max p⊤ s − Ω(p)p∈△argmax: Ω(p) = 0∑
so max: Ω(p) = j pj log pj

p1
1

0

−1

0

1

s1

[0, 0, 1][.3, .2, .5]△
deep-spin.github.io/tutorial

80[Niculae and Blondel, 2017, Mar ns and Astudillo, 2016]

Generalizing so max: Smoothed argmaxesp̂Ω (s) = arg max p⊤ s − Ω(p)p∈△argmax: Ω(p) = 0∑
so max: Ω(p) = j pj log pj
sparsemax: Ω(p) = 1/ 2∥p∥22

p1
1

0

−1

0

1

s1

[0, 0, 1][.3, 0, .7][.3, .2, .5]△
deep-spin.github.io/tutorial

80[Niculae and Blondel, 2017, Blondel et al., 2019]

Generalizing so max: Smoothed argmaxesp̂Ω (s) = arg max p⊤ s − Ω(p)p∈△argmax: Ω(p) = 0∑
so max: Ω(p) = j pj log pj
sparsemax: Ω(p) = 1/ 2∥p∥22
α-entmax: Ω(p) = 1/ α(α−1)

0

∑

α
j pi

Generalized entropy interpolates in between [Tsallis, 1988]
Used in Sparse Seq2Seq: [Peters et al., 2019](Mon 13:50, poster session 2D)
deep-spin.github.io/tutorial

p1
1

−1

0

1

s1

[0, 0, 1][.3, 0, .7][.3, .2, .5]△80[Niculae and Blondel, 2017, Mar ns and Kreutzer, 2017, Malaviya et al., 2018]

Generalizing so max: Smoothed argmaxesp̂Ω (s) = arg max p⊤ s − Ω(p)p∈△argmax: Ω(p) = 0∑
so max: Ω(p) = j pj log pj
sparsemax: Ω(p) = 1/ 2∥p∥22

∑

α
j pi
∑
fusedmax: Ω(p) = 1/ 2∥p∥22 + j |pj − pj−1 |α-entmax: Ω(p) = 1/ α(α−1)

csparsemax: Ω(p) = 1/ 2∥p∥22 + ι(a ≤ p ≤ b)∑
cso max: Ω(p) = j pj log pj + ι(a ≤ p ≤ b)
deep-spin.github.io/tutorial

p1
1

0

−1

0

1

s1

[0, 0, 1][.3, 0, .7][.3, .2, .5]△80

[Wainwright and Jordan, 2008]

The structured case: Marginal polytope• Each vertex corresponds to one such bit vector z• Points inside correspond to marginal distribu ons:
convex combina ons of structured objects
μ = p1 z1 + . . . + pN zN , p ∈ ∆.
|
{z
}

M

exponen ally many terms

p1 = 0.2,
p2 = 0.7,
p3 = 0.1,

z1 = [1, 0, 0, 0, 1, 0, 0, 0, 1]
z2 = [0, 0, 1, 0, 0, 1, 1, 0, 0]
z3 = [1, 0, 0, 0, 1, 0, 0, 1, 0]

deep-spin.github.io/tutorial⇒

μ=[.3, 0, .7, 0, .3, .7, .7, .1, .2].
81△
deep-spin.github.io/tutorial

M82argmax arg max p⊤ s
p∈△△deep-spin.github.io/tutorial

M82argmax arg max p⊤ s
p∈△

MAP arg max μ⊤ ημ∈M△
deep-spin.github.io/tutorial

M82argmax arg max p⊤ s
p∈△

MAP arg max μ⊤ ημ∈M

so max arg max p⊤ s + H(p)p∈△△deep-spin.github.io/tutorial

M82argmax arg max p⊤ s

MAP arg max μ⊤ η

p∈△

μ∈M

so max arg max p⊤ s + H(p)emarginals arg max μ⊤ η + H(μ)

p∈△

μ∈M

△
deep-spin.github.io/tutorial

M82argmax arg max p⊤ s

MAP arg max μ⊤ η

p∈△

μ∈M

so max arg max p⊤ s + H(p)emarginals arg max μ⊤ η + H(μ)

p∈△

μ∈M

Just like so max relaxes argmax,
marginals relax MAP di eren ably!

△
deep-spin.github.io/tutorial

M82argmax arg max p⊤ s

MAP arg max μ⊤ η

p∈△

μ∈M

so max arg max p⊤ s + H(p)emarginals arg max μ⊤ η + H(μ)

p∈△

μ∈M

Just like so max relaxes argmax,
marginals relax MAP di eren ably!
Unlike argmax/so max, computa on is not obvious!
△
deep-spin.github.io/tutorial

M
82

Algorithms for speci c structures

Sequence tagging

Best structure (MAP)

Marginals

Viterbi

Forward-Backward[Rabiner, 1989][Rabiner, 1989]

CKY
Cons tuent trees

Temporal alignments
Dependency trees
Assignments
deep-spin.github.io/tutorial[Kasami, 1966, Younger, 1967][Cocke and Schwartz, 1970]

Inside-Outside[Baker, 1979]

DTW

So -DTW[Sakoe and Chiba, 1978][Cuturi and Blondel, 2017]

Max. Spanning Arborescence

Matrix-Tree[Chu and Liu, 1965, Edmonds, 1967][Kirchho , 1847]

Kuhn-Munkres#P-complete[Kuhn, 1955, Jonker and Volgenant, 1987][Valiant, 1979, Taskar, 2004]
83

Algorithms for speci c structures

Sequence tagging

Best structure (MAP)

Marginals

Viterbi

Forward-Backward[Rabiner, 1989][Rabiner, 1989]

CKY
dyn.
prog.

Cons tuent trees

Temporal alignments
Dependency trees
Assignments
deep-spin.github.io/tutorial[Kasami, 1966, Younger, 1967][Cocke and Schwartz, 1970]

Inside-Outside[Baker, 1979]

DTW

So -DTW[Sakoe and Chiba, 1978][Cuturi and Blondel, 2017]

Max. Spanning Arborescence

Matrix-Tree[Chu and Liu, 1965, Edmonds, 1967][Kirchho , 1847]

Kuhn-Munkres#P-complete[Kuhn, 1955, Jonker and Volgenant, 1987][Valiant, 1979, Taskar, 2004]83

Deriva ves of marginals 1: DP
Dynamic programming: marginals by Forward-Backward, Inside-Outside, etc.

deep-spin.github.io/tutorial

84

Deriva ves of marginals 1: DP
Dynamic programming: marginals by Forward-Backward, Inside-Outside, etc.

Marginals in a sequence tagging model.
1 input: d tags, n tokens, ηU ∈ Rn×d , ηV ∈ Rd×d
2 ini alize α 1 = 0, βn = 0
3 for i ∈ 2, . . . , n do
# forward log-probabilies
∑4
αi,k = log k′ exp αi−1,k′ + (ηU )i,k + (ηV )k′ ,kfor all k(ηU )1,VB

5 for i ∈ n − 1, . . . , 1 do
# backward log-probabilies
∑6
βi,k = log k′ exp βi+1,k′ + (ηU )i+1,k′ + (ηV )k,k′ for all k(ηU )1,NN∑

7 Z = k exp αn,k
8 return μ = exp α + β − log Z
deep-spin.github.io/tutorial# par(ηU )1,PR

ηV(ηU )2,PR(ηU )n,PR(ηU )2,VB(ηU )n,VB(ηU )2,NN(ηU )n,NN

on func on# marginals
84Deriva ves of marginals 1: DP
Dynamic programming: marginals by Forward-Backward, Inside-Outside, etc.
• Alg. consists of di eren able ops: PyTorch autograd can handle it! (v. bad idea)

Marginals in a sequence tagging model.
1 input: d tags, n tokens, ηU ∈ Rn×d , ηV ∈ Rd×d
2 ini alize α 1 = 0, βn = 0
3 for i ∈ 2, . . . , n do
# forward log-probabilies
∑4
αi,k = log k′ exp αi−1,k′ + (ηU )i,k + (ηV )k′ ,kfor all k(ηU )1,VB

5 for i ∈ n − 1, . . . , 1 do
# backward log-probabilies
∑6
βi,k = log k′ exp βi+1,k′ + (ηU )i+1,k′ + (ηV )k,k′ for all k(ηU )1,NN∑

7 Z = k exp αn,k
8 return μ = exp α + β − log Z
deep-spin.github.io/tutorial# par(ηU )1,PR

ηV(ηU )2,PR(ηU )n,PR(ηU )2,VB(ηU )n,VB(ηU )2,NN(ηU )n,NN

on func on# marginals
84Deriva ves of marginals 1: DP
Dynamic programming: marginals by Forward-Backward, Inside-Outside, etc.
• Alg. consists of di eren able ops: PyTorch autograd can handle it! (v. bad idea)• Be er book-keeping: Li and Eisner [2009], Mensch and Blondel [2018]

Marginals in a sequence tagging model.
1 input: d tags, n tokens, ηU ∈ Rn×d , ηV ∈ Rd×d
2 ini alize α 1 = 0, βn = 0
3 for i ∈ 2, . . . , n do
# forward log-probabilies
∑4
αi,k = log k′ exp αi−1,k′ + (ηU )i,k + (ηV )k′ ,kfor all k(ηU )1,VB

5 for i ∈ n − 1, . . . , 1 do
# backward log-probabilies
∑6
βi,k = log k′ exp βi+1,k′ + (ηU )i+1,k′ + (ηV )k,k′ for all k(ηU )1,NN∑

7 Z = k exp αn,k
8 return μ = exp α + β − log Z
deep-spin.github.io/tutorial# par(ηU )1,PR

ηV(ηU )2,PR(ηU )n,PR(ηU )2,VB(ηU )n,VB(ηU )2,NN(ηU )n,NN

on func on# marginals
84Deriva ves of marginals 1: DP
Dynamic programming: marginals by Forward-Backward, Inside-Outside, etc.
• Alg. consists of di eren able ops: PyTorch autograd can handle it! (v. bad idea)• Be er book-keeping: Li and Eisner [2009], Mensch and Blondel [2018]• With circular dependencies, this breaks! Can get an approxima on Stoyanov et al. [2011]

Marginals in a sequence tagging model.
1 input: d tags, n tokens, ηU ∈ Rn×d , ηV ∈ Rd×d
2 ini alize α 1 = 0, βn = 0
3 for i ∈ 2, . . . , n do
# forward log-probabilies
∑4
αi,k = log k′ exp αi−1,k′ + (ηU )i,k + (ηV )k′ ,kfor all k(ηU )1,VB

5 for i ∈ n − 1, . . . , 1 do
# backward log-probabilies
∑6
βi,k = log k′ exp βi+1,k′ + (ηU )i+1,k′ + (ηV )k,k′ for all k(ηU )1,NN∑

7 Z = k exp αn,k
8 return μ = exp α + β − log Z
deep-spin.github.io/tutorial# par(ηU )1,PR

ηV(ηU )2,PR(ηU )n,PR(ηU )2,VB(ηU )n,VB(ηU )2,NN(ηU )n,NN

on func on# marginals
84Deriva ves of marginals 2: Matrix-Tree
L(s): Laplacian of the edge score graph
Z = det L(s)μ = L(s)−1∇μ = ∇L−1 = L−1

deep-spin.github.io/tutorial



∂L
∂η



L−1

85

[Kim et al., 2017]

Structured A en on Networks
input
x

η

μ
la

outputycoali on...
aide

deep-spin.github.io/tutorial

86

[Kim et al., 2017]

Structured A en on Networks
inputx

deep-spin.github.io/tutorialημoutputy86

[Kim et al., 2017]

Structured A en on Networks
input
x

η

μ

outputyη(i): score of word i
receiving a en onη(i, i + 1): score ofconsecu ve words
receiving a en on

deep-spin.github.io/tutorial

μ(i): probability ofword i ge ng a en on

86

[Kim et al., 2017]

Structured A en on Networks
input
x

η

μ

outputyη(i): score of word i
receiving a en onη(i, i + 1): score ofconsecu ve words
receiving a en on

μ(i): probability ofword i ge ng a en on

CRF marginals (from forward–backward) give a en on weights ∈ (0, 1)

deep-spin.github.io/tutorial

86

[Kim et al., 2017]

Structured A en on Networks
input
x

η

μ

dog

η(dog → on): arc score(tree constraints)on

outputywheelsμ(dog → on):probability of arc

CRF marginals (from forward–backward) give a en on weights ∈ (0, 1)
Similar idea for projec ve dependency trees with inside–outside
deep-spin.github.io/tutorial

86

[Kim et al., 2017]

Structured A en on Networks
input
x

η

μ

dog

η(dog → on): arc score(tree constraints)on

outputywheelsμ(dog → on):probability of arc

CRF marginals (from forward–backward) give a en on weights ∈ (0, 1)
Similar idea for projec ve dependency trees with inside–outside
and non-projec ve with the Matrix-Tree theorem [Liu and Lapata, 2018].
deep-spin.github.io/tutorial86

[Corro and Titov, 2019a,b]

Di eren able Perturb & Parse
Extending Gumbel-So max to structured stochas c models• Forward pass:
sample structure z (approximately)z = arg max(η + ε)⊤ z

η

z

z∈Z

• Backward pass:pretend we did marginal inferenceμ̃ = arg max(η + ε)⊤ z + H̃(μ)μ∈Mμ̃(or some similar relaxa on)

deep-spin.github.io/tutorial

87

Back-propaga ng through marginals
Pros:

deep-spin.github.io/tutorial

88

Back-propaga ng through marginals
Pros:• Familiar algorithms for NLPers,

deep-spin.github.io/tutorial

88

Back-propaga ng through marginals
Pros:• Familiar algorithms for NLPers,• (Structured A en on Networks:) All computa ons exact.

deep-spin.github.io/tutorial

88

Back-propaga ng through marginals
Pros:• Familiar algorithms for NLPers,• (Structured A en on Networks:) All computa ons exact.
Cons:• (Structured A en on Networks:) forward pass marginals are dense;( xed by Perturb & MAP, at cost of rough approxima on)

deep-spin.github.io/tutorial

88

Back-propaga ng through marginals
Pros:• Familiar algorithms for NLPers,• (Structured A en on Networks:) All computa ons exact.
Cons:• (Structured A en on Networks:) forward pass marginals are dense;( xed by Perturb & MAP, at cost of rough approxima on)• E cient & numerically stable back-propaga on through DPs is tricky;(somewhat alleviated by Mensch and Blondel [2018])

deep-spin.github.io/tutorial

88

Back-propaga ng through marginals
Pros:• Familiar algorithms for NLPers,• (Structured A en on Networks:) All computa ons exact.
Cons:• (Structured A en on Networks:) forward pass marginals are dense;( xed by Perturb & MAP, at cost of rough approxima on)• E cient & numerically stable back-propaga on through DPs is tricky;(somewhat alleviated by Mensch and Blondel [2018])• Not applicable when marginals are unavailable.

deep-spin.github.io/tutorial

88

Back-propaga ng through marginals
Pros:• Familiar algorithms for NLPers,• (Structured A en on Networks:) All computa ons exact.
Cons:• (Structured A en on Networks:) forward pass marginals are dense;( xed by Perturb & MAP, at cost of rough approxima on)• E cient & numerically stable back-propaga on through DPs is tricky;(somewhat alleviated by Mensch and Blondel [2018])• Not applicable when marginals are unavailable.
• Case-by-case algorithms required, can get tedious.
deep-spin.github.io/tutorial

88

Back-propaga ng through marginals
Pros:• Familiar algorithms for NLPers,• (Structured A en on Networks:) All computa ons exact.
Cons:• (Structured A en on Networks:) forward pass marginals are dense;( xed by Perturb & MAP, at cost of rough approxima on)• E cient & numerically stable back-propaga on through DPs is tricky;(somewhat alleviated by Mensch and Blondel [2018])• Not applicable when marginals are unavailable.
• Case-by-case algorithms required, can get tedious.
deep-spin.github.io/tutorial

88

Back-propaga ng through marginals
Pros:• Familiar algorithms for NLPers,• (Structured A en on Networks:) All computa ons exact.
Cons:• (Structured A en on Networks:) forward pass marginals are dense;( xed by Perturb & MAP, at cost of rough approxima on)• E cient & numerically stable back-propaga on through DPs is tricky;(somewhat alleviated by Mensch and Blondel [2018])• Not applicable when marginals are unavailable.
• Case-by-case algorithms required, can get tedious.
deep-spin.github.io/tutorial

88

[Niculae et al., 2018a]

argmax arg max p⊤ s

MAP arg max μ⊤ η

p∈△

μ∈M

so max arg max p⊤ s + H(p)emarginals arg max μ⊤ η + H(μ)

p∈△

μ∈M

sparsemax arg max p⊤ s − 1/ 2∥p∥2p∈△△deep-spin.github.io/tutorialM89

[Niculae et al., 2018a]

argmax arg max p⊤ s

MAP arg max μ⊤ η

p∈△

μ∈M

so max arg max p⊤ s + H(p)emarginals arg max μ⊤ η + H(μ)

p∈△

μ∈M

sparsemax arg max p⊤ s − 1/ 2∥p∥2p∈△△deep-spin.github.io/tutorial

SparseMAP arg max μ⊤ η − 1/ 2∥μ∥2
μ∈M

M
89

[Niculae et al., 2018a]

SparseMAP solu on

μ⋆ = arg max μ⊤ η − 1/ 2∥μ∥2
μ∈M

=

= .6

+ .4

(μ⋆ is unique, but may have mul ple decomposi ons p. Ac ve Set recovers a sparse one.)deep-spin.github.io/tutorial

90

Algorithms for SparseMAPμ⋆ = arg max μ⊤ η − 1/ 2∥μ∥2μ∈M

deep-spin.github.io/tutorial

91

Algorithms for SparseMAP
linear constraints(alas, exponen ally many!)μ⋆ = arg max μ⊤ η − 1/ 2∥μ∥2deep-spin.github.io/tutorialμ∈M

quadra c objec ve

91

Algorithms for SparseMAP
linear constraints(alas, exponen ally many!)μ⋆ = arg max μ⊤ η − 1/ 2∥μ∥2μ∈M

quadra c objec ve

Condi onal Gradient[Frank and Wolfe, 1956, Lacoste-Julien and Jaggi, 2015]

deep-spin.github.io/tutorial

91

Algorithms for SparseMAP
linear constraints(alas, exponen ally many!)μ⋆ = arg max μ⊤ η − 1/ 2∥μ∥2μ∈M

quadra c objec ve

Condi onal Gradient[Frank and Wolfe, 1956, Lacoste-Julien and Jaggi, 2015]• select a new corner of M

deep-spin.github.io/tutorial

91

Algorithms for SparseMAP
linear constraints(alas, exponen ally many!)μ⋆ = arg max μ⊤ η − 1/ 2∥μ∥2μ∈M

quadra c objec ve

Condi onal Gradient[Frank and Wolfe, 1956, Lacoste-Julien and Jaggi, 2015]• select a new corner of M

arg max μ⊤ (η − μ(t−1) )
|
{z
}
μ∈M
e
η

deep-spin.github.io/tutorial

91

Algorithms for SparseMAP
linear constraints(alas, exponen ally many!)μ⋆ = arg max μ⊤ η − 1/ 2∥μ∥2μ∈M

quadra c objec ve

Condi onal Gradient[Frank and Wolfe, 1956, Lacoste-Julien and Jaggi, 2015]• select a new corner of M
• update the (sparse) coe cients of p
• Update rules: vanilla, away-step, pairwise

deep-spin.github.io/tutorial

91

Algorithms for SparseMAP
linear constraints(alas, exponen ally many!)μ⋆ = arg max μ⊤ η − 1/ 2∥μ∥2μ∈M

quadra c objec ve

Condi onal Gradient[Frank and Wolfe, 1956, Lacoste-Julien and Jaggi, 2015]• select a new corner of M
• update the (sparse) coe cients of p
• Update rules: vanilla, away-step, pairwise• Quadra c objec ve: Ac ve Set
a.k.a. Min-Norm Point, [Wolfe, 1976][Mar ns et al., 2015, Nocedal and Wright, 1999,
Vinyes and Obozinski, 2017]
deep-spin.github.io/tutorial

91

Algorithms for SparseMAP
linear constraints(alas, exponen ally many!)μ⋆ = arg max μ⊤ η − 1/ 2∥μ∥2μ∈M

quadra c objec ve

Condi onal Gradient[Frank and Wolfe, 1956, Lacoste-Julien and Jaggi, 2015]• select a new corner of M
• update the (sparse) coe cients
Ac veof pSet achieves• Update rules: vanilla, away-step, pairwise

nite & linear convergence!

• Quadra c objec ve: Ac ve Set

a.k.a. Min-Norm Point, [Wolfe, 1976][Mar ns et al., 2015, Nocedal and Wright, 1999,
Vinyes and Obozinski, 2017]
deep-spin.github.io/tutorial

91

Algorithms for SparseMAP
linear constraints(alas, exponen ally many!)μ⋆ = arg max μ⊤ η − 1/ 2∥μ∥2μ∈MCondi onal Gradientquadra c objec ve

Backward pass[Frank and Wolfe, 1956, Lacoste-Julien and Jaggi, 2015]• select a new corner of M
• update the (sparse) coe cients of p∂μis sparse∂η• Update rules: vanilla, away-step, pairwise• Quadra c objec ve: Ac ve Set
a.k.a. Min-Norm Point, [Wolfe, 1976][Mar ns et al., 2015, Nocedal and Wright, 1999,
Vinyes and Obozinski, 2017]
deep-spin.github.io/tutorial

91

Algorithms for SparseMAP
linear constraints(alas, exponen ally many!)μ⋆ = arg max μ⊤ η − 1/ 2∥μ∥2μ∈MCondi onal Gradientquadra c objec ve

Backward pass[Frank and Wolfe, 1956, Lacoste-Julien and Jaggi, 2015]• select a new corner of M
• update the (sparse) coe cients of p
• Update rules: vanilla, away-step, pairwise• Quadra c objec ve: Ac ve Set∂μis sparse
∂η
 ⊤
∂μ
compu ng ∂η dytakes O (dim(μ) nnz(p⋆ ))a.k.a. Min-Norm Point, [Wolfe, 1976][Mar ns et al., 2015, Nocedal and Wright, 1999,
Vinyes and Obozinski, 2017]
deep-spin.github.io/tutorial

91

Algorithms for SparseMAP
linear constraints(alas, exponen ally many!)μ⋆ = arg max μ⊤ η − 1/ 2∥μ∥2μ∈MCondi onal Gradientquadra c objec ve

Backward passCompletely modular: just add MAP[Frank and Wolfe, 1956, Lacoste-Julien and Jaggi, 2015]• select a new corner of M
• update the (sparse) coe cients of p
• Update rules: vanilla, away-step, pairwise• Quadra c objec ve: Ac ve Set∂μis sparse
∂η
 ⊤
∂μ
compu ng ∂η dytakes O (dim(μ) nnz(p⋆ ))a.k.a. Min-Norm Point, [Wolfe, 1976][Mar ns et al., 2015, Nocedal and Wright, 1999,
Vinyes and Obozinski, 2017]
deep-spin.github.io/tutorial

91

.

po a
l
of icew fice
at r
ch
es
si
tu a
at
cl ion
os
el
y

.

po a
l
of icew fice
at r
ch
es
si
tu a
at
cl ionosely[Chen et al., 2017]agentlemanoverlookinganeighborhood

situation.

[Niculae et al., 2018a]

A

a

A

gentlemangentlemanoverlooking

overlooking

o cerwatchesaaneighborhoodaneighborhood

situation

situa onsitua on

.
.

.

po a
l
of icew fice
at r
ch
es
si
tu a
at
cl ionoselypoliceclosely.

OverviewEπθ (z|x) L(z)L arg maxz πθ (z | x)
L Eπθ (z|x) [z]• REINFORCE• Straight-Through• Structured A n. Nets

• Straight-Through Gumbel(Perturb & MAP)

• SPIGOT• SparseMAP

deep-spin.github.io/tutorial

94

Structured latent variables without sampling

Ez L(z) =∑L ŷ (z) π (z | x)z∈Z

deep-spin.github.io/tutorial

95

Structured latent variables without sampling

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z

deep-spin.github.io/tutorial

95

Structured latent variables without samplinge.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z

deep-spin.github.io/tutorial

95

Structured latent variables without samplinge.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
parsing model,using some scorer fθ (z; x)

deep-spin.github.io/tutorial

95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
parsing model,using some scorer fθ (z; x)

Exponen ally large sum!
deep-spin.github.io/tutorial

95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
How to de ne πθ ?

parsing model,using some scorer fθ (z; x)idea 1
idea 2
idea 3deep-spin.github.io/tutorial

95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
How to de ne πθ ?

parsing model,using some scorer fθ (z; x)∑h∈Hidea 1
idea 2
idea 3deep-spin.github.io/tutorial

95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
How to de ne πθ ?

parsing model,using some scorer fθ (z; x)∑∂E L(z)h∈H∂θidea 1
idea 2
idea 3deep-spin.github.io/tutorial

95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
How to de ne πθ ?

idea 1
idea 2
idea 3πθ (z) ∝ exp fθ (z)deep-spin.github.io/tutorial

parsing model,using some scorer fθ (z; x)∑∂E L(z)h∈H∂θso max95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
How to de ne πθ ?

idea 1
idea 2
idea 3πθ (z) ∝ exp fθ (z)deep-spin.github.io/tutorial

parsing model,using some scorer fθ (z; x)∑∂E L(z)h∈H∂θso max95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
How to de ne πθ ?

idea 1
idea 2
idea 3πθ (z) ∝ exp fθ (z)deep-spin.github.io/tutorial

parsing model,using some scorer fθ (z; x)∑∂E L(z)h∈H∂θso max95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
How to de ne πθ ?

parsing model,using some scorer fθ (z; x)∑∂E L(z)All methods we’ve seen require sampling; hardin general.
∂θh∈H
idea 1
idea 2
idea 3πθ (z) ∝ exp fθ (z)deep-spin.github.io/tutorial

so max95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
How to de ne πθ ?

idea 1
idea 2
idea 3πθ (z) ∝ exp fθ (z)πθ (z) = 1 if z = MAP(fθ (·)) else 0

deep-spin.github.io/tutorial

parsing model,using some scorer fθ (z; x)∑∂E L(z)h∈H∂θso maxargmax95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
How to de ne πθ ?

idea 1
idea 2
idea 3πθ (z) ∝ exp fθ (z)πθ (z) = 1 if z = MAP(fθ (·)) else 0

deep-spin.github.io/tutorial

parsing model,using some scorer fθ (z; x)∑∂E L(z)h∈H∂θso maxargmax95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
How to de ne πθ ?

idea 1
idea 2
idea 3πθ (z) ∝ exp fθ (z)πθ (z) = 1 if z = MAP(fθ (·)) else 0

deep-spin.github.io/tutorial

parsing model,using some scorer fθ (z; x)∑∂E L(z)h∈H∂θso maxargmax95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
How to de ne πθ ?

parsing model,using some scorer fθ (z; x)∑

STE / SPIGOT relax ŷ in backward.
h∈Hidea 1
idea 2
idea 3πθ (z) ∝ exp fθ (z)πθ (z) = 1 if z = MAP(fθ (·)) else 0

deep-spin.github.io/tutorial∂E L(z)∂θso maxargmax95

Structured latent variables without samplingsum overall possible treese.g., a TreeLSTM de ned by z

Ez L(z) =∑L ŷφ (z) π θ (z | x)z∈Z
How to de ne πθ ?

idea 1
idea 2
idea 3πθ (z) ∝ exp fθ (z)πθ (z) = 1 if z = MAP(fθ (·)) else 0

deep-spin.github.io/tutorial

parsing model,using some scorer fθ (z; x)∑∂E L(z)h∈H∂θso maxargmaxSparseMAP
95

Structured latent variables without sampling

• • •

= .7×

• • •

+ .3×

• • •

recall our shorthand L(z) = L(ŷφ (z), y)

deep-spin.github.io/tutorial

96Structured latent variables without sampling

• • •

= .7×

• • •

+ .3×

• • •

+0× • • • + ...

recall our shorthand L(z) = L(ŷφ (z), y)

deep-spin.github.io/tutorial

96Structured latent variables without sampling= .7× • • • + .3× • • • +0× • • • + ...
E[L(z)]= .7× L( • • •) + .3× L( • • • )• • •recall our shorthand L(z) = L(ŷφ (z), y)

deep-spin.github.io/tutorial

96

[Corro and Titov, 2019b]

Stanford Natural Language Inference (Accuracy)[Kim et al., 2017]

Stanford Sen ment (Accuracy)
Socher et al
Bigram Naive Bayes

83.2
84.7

[Corro and Titov, 2019b]

GCN w/ CoreNLP
GCN w/ Perturb-and-MAP

86.2
86.8

[Liu and Lapata, 2018]

83.1[Niculae et al., 2018b]

TreeLSTM w/ CoreNLP
TreeLSTM w/ SparseMAP

Simple A en on
Structured A en on

83.8
84.6

100D SAN Yogatama et al
100D RL-SPINN

86.8
80.5

[Choi et al., 2018]

100D ST Gumbel-Tree
300D 600D -

82.6
85.6
86.0

[Corro and Titov, 2019b]

Latent Tree + 1 GCN Latent Tree + 2 GCN -deep-spin.github.io/tutorial

85.2
86.2

97

V. Conclusions

Is it syntax?!
• Unlike e.g. unsupervised parsing, the structures we learn are guided by adownstream objec ve (typically discrimina ve).
• They don’t typically resemble gramma cal structure (yet) [Williams et al., 2018](future work: more induc ve biases and constraints?)

deep-spin.github.io/tutorial98

Is it syntax?!
• Unlike e.g. unsupervised parsing, the structures we learn are guided by adownstream objec ve (typically discrimina ve).
• They don’t typically resemble gramma cal structure (yet) [Williams et al., 2018](future work: more induc ve biases and constraints?)• Common to compare latent structures with parser outputs.
But is this always a meaningful comparison?

deep-spin.github.io/tutorial98

[Niculae et al., 2018b]

Syntax vs. Composi on Order

CoreNLP parse, p = 21.4%⋆
deep-spin.github.io/tutorial

lovelyandpoignant.
99

[Niculae et al., 2018b]

Syntax vs. Composi on Orderp = 22.6%⋆

lovelyandpoignant.

CoreNLP parse, p = 21.4%⋆
deep-spin.github.io/tutorial

lovelyand···poignant.
99

[Niculae et al., 2018b]

Syntax vs. Composi on Orderp = 15.33%
1.0

1.0

1.0

p = 22.6%

1.0

⋆
⋆

lovelyandpoignant

1.0

a

and

poignant

andmeaningful

lm

.

lm

.

p = 15.27%
1.0
1.0

⋆
lovelydeep.

CoreNLP parse, p = 21.4%

⋆

1.0

a

1.0
1.0

1.0

deep

1.0

and

meaningful···
CoreNLP parse, p = 0%

.

···

1.0
1.0

1.0

1.0
1.0

deep-spin.github.io/tutorial

⋆

a

deep

1.0

and

meaningful

lm

. 100

OverviewEπθ (z|x) L(z)L arg maxz πθ (z | x)
L Eπθ (z|x) [z]• REINFORCE• Straight-Through• Structured A n. Nets

• Straight-Through Gumbel(Perturb & MAP)

• SPIGOT• SparseMAP• SparseMAP

deep-spin.github.io/tutorial

101

OverviewEπθ (z|x) L(z)L arg maxz πθ (z | x)
L Eπθ (z|x) [z]• REINFORCESPL• Straight-ThroughMAP,MRG• Structured A n. NetsMRG• Straight-Through Gumbel(Perturb & MAP)SPL,MRG• SPIGOTMAP+• SparseMAPMAP+• SparseMAPMAP+

Computa on:

SPL: Sampling. (Simple in incremental/unstructured, hard for most global structures.)
MAP: Finding the highest-scoring structure.
MRG: Marginal inference.
deep-spin.github.io/tutorial

101Conclusions• Latent structure models are desirable for interpretability, structural bias, andhigher predic ve power with fewer parameters.
• Stochas c latent variables can be dealt with RL or straight-through gradients.
• Determinis c argmax requires surrogate gradients (e.g. SPIGOT).
• Con nuous relaxa ons of argmax include SANs and SparseMAP.
• Intui vely, some of these di erent methods are trying to do similar things orrequire the same building blocks (e.g. SPIGOT and SparseMAP).
• ... we didn’t even get into deep genera ve models! These tools apply,
but there are new challenges. [Corro and Titov, 2019a, Kim et al., 2019a,b, Kawakami et al., 2019]
deep-spin.github.io/tutorial

102

References I
Ryan Adams. The gumbel-max trick for discrete distribu ons, 2013. URL
https://lips.cs.princeton.edu/the-gumbel-max-trick-for-discrete-distributions/. Blog post.
James K Baker. Trainable grammars for speech recogni on. The Journal of the Acous cal Society of America, 65(S1):S132–S132,
1979.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Es ma ng or propaga ng gradients through stochas c neurons forcondi onal computa on. arXiv preprint arXiv:1308.3432, 2013.
Mathieu Blondel, André FT Mar ns, and Vlad Niculae. Learning classi ers with Fenchel-Young losses: Generalized entropies,
margins, and algorithms. In Proc. of AISTATS, 2019.
Samuel R. Bowman, Jon Gauthier, Abhinav Rastogi, Raghav Gupta, Christopher D. Manning, and Christopher Po s. A fast uni ed
model for parsing and sentence understanding. In Proc. of ACL, 2016. doi: 10.18653/v1/P16-1139.
Stephen Boyd and Lieven Vandenberghe. Convex op miza on. Cambridge University Press, 2004.
Peter F Brown, Vincent J Della Pietra, Stephen A Della Pietra, and Robert L Mercer. The mathema cs of sta s cal machinetransla on: Parameter es ma on. Computa onal Linguis cs, 19(2):263–311, 1993.
Qian Chen, Xiaodan Zhu, Zhen-Hua Ling, Si Wei, Hui Jiang, and Diana Inkpen. Enhanced LSTM for natural language inference. In
Proc. of ACL, 2017.
Jihun Choi, Kang Min Yoo, and Sang-goo Lee. Learning to compose task-speci c tree structures. In Proc. of AAAI, 2018.
deep-spin.github.io/tutorial

103

References II
Yoeng-Jin Chu and Tseng-Hong Liu. On the shortest arborescence of a directed graph. Science Sinica, 14:1396–1400, 1965.
William John Cocke and Jacob T Schwartz. Programming languages and their compilers. Courant Ins tute of Mathema cal
Sciences., 1970.
Shay B Cohen, Karl Stratos, Michael Collins, Dean P Foster, and Lyle Ungar. Spectral learning of latent-variable PCFGs. In Proc. of
ACL, 2012.
Caio Corro and Ivan Titov. Di eren able Perturb-and-Parse: Semi-Supervised Parsing with a Structured Varia onal Autoencoder.
In Proc. of ICLR, 2019a.
Caio Corro and Ivan Titov. Learning latent trees with stochas c perturba ons and di eren able dynamic programming. In Proc.
of ACL, 2019b.
Marco Cuturi and Mathieu Blondel. So -DTW: a di eren able loss func on for me-series. In Proc. of ICML, 2017.
Jack Edmonds. Op mum branchings. J. Res. Nat. Bur. Stand., 71B:233–240, 1967.
Marguerite Frank and Philip Wolfe. An algorithm for quadra c programming. Nav. Res. Log., 3(1-2):95–110, 1956.
Serhii Havrylov, Germán Kruszewski, and Armand Joulin. Coopera ve Learning of Disjoint Syntax and Seman cs. In Proc.
NAACL-HLT, 2019.
Geo rey Hinton. Neural networks for machine learning. In Coursera video lectures, 2012.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameteriza on with Gumbel-so max. In Proc. of ICLR, 2017.
deep-spin.github.io/tutorial

104

References III
Roy Jonker and Anton Volgenant. A shortest augmen ng path algorithm for dense and sparse linear assignment problems.
Compu ng, 38(4):325–340, 1987.
Tadao Kasami. An e cient recogni on and syntax-analysis algorithm for context-free languages. Coordinated Science Laboratory
Report no. R-257, 1966.
Kazuya Kawakami, Chris Dyer, and Phil Blunsom. Learning to discover, ground and use words with segmental neural language
models. In Proc. of ACL, 2019.
Yoon Kim, Carl Denton, Loung Hoang, and Alexander M Rush. Structured a en on networks. In Proc. of ICLR, 2017.
Yoon Kim, Chris Dyer, and Alexander Rush. Compound probabilis c context-free grammars for grammar induc on. In Proc. of
ACL, 2019a.
Yoon Kim, Alexander Rush, Lei Yu, Adhiguna Kuncoro, Chris Dyer, and Gábor Melis. Unsupervised recurrent neural network
grammars. In Proc. of NAACL-HLT, 2019b.
Diederik P Kingma and Max Welling. Auto-encoding Varia onal Bayes. 2014.
Gustav Kirchho . Ueber die au ösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung
galvanischer ströme geführt wird. Annalen der Physik, 148(12):497–508, 1847.
Harold W Kuhn. The Hungarian method for the assignment problem. Nav. Res. Log., 2(1-2):83–97, 1955.
Simon Lacoste-Julien and Mar n Jaggi. On the global linear convergence of Frank-Wolfe op miza on variants. In Proc. of
NeurIPS, 2015.
deep-spin.github.io/tutorial

105References IV
Zhifei Li and Jason Eisner. First-and second-order expecta on semirings with applica ons to minimum-risk training ontransla on forests. In Proc. of EMNLP, 2009.
Yang Liu and Mirella Lapata. Learning structured text representa ons. TACL, 6:63–75, 2018.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribu on: A con nuous relaxa on of discrete randomvariables. In Proc. of ICLR, 2016.
Jean Maillard and Stephen Clark. Latent tree learning with di eren able parsers: Shi -Reduce parsing and chart parsing. arXiv
preprint arXiv:1806.00840, 2018.
Chaitanya Malaviya, Pedro Ferreira, and André FT Mar ns. Sparse and constrained a en on for neural machine transla on. In
Proc. of ACL, 2018.
André FT Mar ns and Ramón Fernandez Astudillo. From so max to sparsemax: A sparse model of a en on and mul -label
classi ca on. In Proc. of ICML, 2016.
André FT Mar ns and Julia Kreutzer. Learning what’s easy: Fully di eren able neural easy- rst taggers. In Proc. of EMNLP, 2017.
André FT Mar ns and Vlad Niculae. Notes on latent structure models and SPIGOT. preprint arXiv:1907.10348, 2019.
André FT Mar ns, Mário AT Figueiredo, Pedro MQ Aguiar, Noah A Smith, and Eric P Xing. AD3: Alterna ng direc ons dual
decomposi on for MAP inference in graphical models. JMLR, 16(1):495–545, 2015.
Arthur Mensch and Mathieu Blondel. Di eren able dynamic programming for structured predic on and a en on. In Proc. of
ICML, 2018.
deep-spin.github.io/tutorial

106References V
Nikita Nangia and Samuel Bowman. ListOps: A diagnos c dataset for latent tree learning. In Proc. of NAACL SRW, 2018.
Vlad Niculae and Mathieu Blondel. A regularized framework for sparse and structured neural a en on. In Proc. of NeurIPS, 2017.
Vlad Niculae, André FT Mar ns, Mathieu Blondel, and Claire Cardie. SparseMAP: Di eren able sparse structured inference. In
Proc. of ICML, 2018a.
Vlad Niculae, André FT Mar ns, and Claire Cardie. Towards dynamic computa on graphs via sparse latent structure. In Proc. of
EMNLP, 2018b.
Jorge Nocedal and Stephen Wright. Numerical Op miza on. Springer New York, 1999.
George Papandreou and Alan L Yuille. Perturb-and-MAP random elds: Using discrete op miza on to learn and sample fromenergy models. In Proc. of ICCV, 2011.
Hao Peng, Sam Thomson, and Noah A Smith. Backpropaga ng through structured argmax using a SPIGOT. In Proc. of ACL, 2018.
Ben Peters, Vlad Niculae, and André FT Mar ns. Sparse sequence-to-sequence models. In Proc. of ACL, 2019.
Slav Petrov and Dan Klein. Discrimina ve log-linear grammars with latent variables. In Advances in neural informa on processing
systems, pages 1153–1160, 2008.
Ariadna Qua oni, Sybor Wang, Louis-Philippe Morency, Michael Collins, and Trevor Darrell. Hidden condi onal random elds.
IEEE Transac ons on Pa ern Analysis & Machine Intelligence, 29(10):1848–1852, 2007.

deep-spin.github.io/tutorial

107References VI
Lawrence R. Rabiner. A tutorial on Hidden Markov Models and selected applica ons in speech recogni on. P. IEEE, 77(2):257–286, 1989.
Hiroaki Sakoe and Seibi Chiba. Dynamic programming algorithm op miza on for spoken word recogni on. IEEE Trans. on
Acous cs, Speech, and Sig. Proc., 26:43–49, 1978.
Veselin Stoyanov, Alexander Ropson, and Jason Eisner. Empirical risk minimiza on of graphical model parameters given
approximate inference, decoding, and model structure. In Proc. of AISTATS, 2011.
Ben Taskar. Learning structured predic on models: A large margin approach. PhD thesis, Stanford University, 2004.
Constan no Tsallis. Possible generaliza on of Boltzmann-Gibbs sta s cs. Journal of Sta s cal Physics, 52:479–487, 1988.
Leslie G Valiant. The complexity of compu ng the permanent. Theor. Comput. Sci., 8(2):189–201, 1979.
Tim Vieira. Gumbel-max trick, 2014. URL
https://timvieira.github.io/blog/post/2014/07/31/gumbel-max-trick/. Blog post.
Marina Vinyes and Guillaume Obozinski. Fast column genera on for atomic norm regulariza on. In Proc. of AISTATS, 2017.
Mar n J Wainwright and Michael I Jordan. Graphical models, exponen al families, and varia onal inference., volume 1. Now
Publishers, Inc., 2008.
Adina Williams, Andrew Drozdov, and Samuel R Bowman. Do latent tree learning models iden fy meaningful structure in
sentences? TACL, 2018.
deep-spin.github.io/tutorial

108

References VII
Ronald J. Williams. Simple sta s cal gradient-following algorithms for connec onist reinforcement learning. Mach. Learn., 8,
1992.
Philip Wolfe. Finding the nearest point in a polytope. Mathema cal Programming, 11(1):128–149, 1976.
Dani Yogatama, Phil Blunsom, Chris Dyer, Edward Grefenste e, and Wang Ling. Learning to compose words into sentences withreinforcement learning. In Proc. of ICLR, 2017.
Daniel H Younger. Recogni on and parsing of context-free languages in me n3 . Informa on and Control, 10(2):189–208, 1967.

deep-spin.github.io/tutorial

109