Practical Neural
Networks for NLP(Part 2)Chris Dyer, Yoav Goldberg, Graham Neubig

Previous Part
•

DyNet

•

Feed Forward Networks

•

RNNs

•

All pretty standard, can do very similar in TF / Theano / Keras.

This Part•

Where DyNet shines -- dynamically structured networks.

•

Things that are cumbersome / hard / ugly in otherframeworks.

BiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_B

theBiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_B

theBiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_B

theBiLSTM Tagger
tag

tag

tag

tag

tag

MLP
MLP
• This isMLP
by now a very
common model

MLP

to be effective
in many concat
works
concat • Shownconcatconcatconcat

MLP• Let's see how to implement it in dynet

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_F
LSTM_F• ... and we'll complicate it a bit later
LSTM_Bbrown

LSTM_Bfox

LSTM_B

engulfed

LSTM_F
LSTM_B

theBiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_B

theBiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_BtheWORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))
fwdRNN = dy.LSTMBuilder(1, 128, 50, model)
layersin-dimout-dimdy.renew_cg()# initialize the RNNs
f_init = fwdRNN.initial_state()
wembs = [word_rep(w) for w in words]
fw_exps = []s = f_init
for we in wembs:s = s.add_input(we)fw_exps.append(s.output())

WORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))
fwdRNN = dy.LSTMBuilder(1, 128, 50, model)
layersin-dimout-dimdy.renew_cg()# initialize the RNNs
f_init = fwdRNN.initial_state()
wembs = [word_rep(w) for w in words]
fw_exps = []s = f_init
for we in wembs:s = s.add_input(we)fw_exps.append(s.output())

WORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))
fwdRNN = dy.LSTMBuilder(1, 128, 50, model)
layersin-dimout-dimdef word_rep(w):dy.renew_cg()
w_index = vw.w2i[w]# initialize the return
RNNs WORDS_LOOKUP[w_index]
f_init = fwdRNN.initial_state()
wembs = [word_rep(w) for w in words]
fw_exps = []s = f_init
for we in wembs:s = s.add_input(we)fw_exps.append(s.output())

WORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))
fwdRNN = dy.LSTMBuilder(1, 128, 50, model)
layersin-dimout-dimdy.renew_cg()# initialize the RNNs
f_init = fwdRNN.initial_state()
wembs = [word_rep(w) for w in words]
fw_exps = []s = f_init
for we in wembs:s = s.add_input(we)fw_exps.append(s.output())

WORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))
fwdRNN = dy.LSTMBuilder(1, 128, 50, model)
layersin-dimout-dimdy.renew_cg()# initialize the RNNs
f_init = fwdRNN.initial_state()
wembs = [word_rep(w) for w in words]
fw_exps = []f_init.transduce(wembs)
s = f_init
for we in wembs:s = s.add_input(we)fw_exps.append(s.output())

WORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))
fwdRNN = dy.LSTMBuilder(1, 128, 50, model)
layersin-dimout-dimdy.renew_cg()# initialize the RNNs
f_init = fwdRNN.initial_state()
wembs = [word_rep(w) for w in words]
fw_exps = []f_init.transduce(wembs)
s = f_init
for we in wembs:s = s.add_input(we)fw_exps.append(s.output())

BiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_B

theBiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_BtheWORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))
fwdRNN = dy.LSTMBuilder(1, 128, 50, model)
bwdRNN = dy.LSTMBuilder(1, 128, 50, model)

dy.renew_cg()# initialize the RNNs
f_init = fwdRNN.initial_state()b_init = bwdRNN.initial_state()
wembs = [word_rep(w) for w in words]
fw_exps = f_init.transduce(wembs)
bw_exps = b_init.transduce(reversed(wembs))

BiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_B

theBiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_BtheWORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))
fwdRNN = dy.LSTMBuilder(1, 128, 50, model)
bwdRNN = dy.LSTMBuilder(1, 128, 50, model)

dy.renew_cg()# initialize the RNNs
f_init = fwdRNN.initial_state()b_init = bwdRNN.initial_state()
wembs = [word_rep(w) for w in words]
fw_exps = f_init.transduce(wembs)
bw_exps = b_init.transduce(reversed(wembs))# biLSTM statesbi = [dy.concatenate([f,b]) for f,b in zip(fw_exps,
reversed(bw_exps))]BiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_B

theBiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_BtheWORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))
fwdRNN = dy.LSTMBuilder(1, 128, 50, model)
bwdRNN = dy.LSTMBuilder(1, 128, 50, model)

pH = model.add_parameters((32, 50*2))
pO = model.add_parameters((ntags, 32))
dy.renew_cg()# initialize the RNNs
f_init = fwdRNN.initial_state()b_init = bwdRNN.initial_state()
wembs = [word_rep(w) for w in words]
fw_exps = f_init.transduce(wembs)
bw_exps = b_init.transduce(reversed(wembs)# biLSTM statesbi = [dy.concatenate([f,b]) for f,b in zip(fw_exps,
reversed(bw_exps))]# MLPsH = dy.parameter(pH)O = dy.parameter(pO)outs = [O*(dy.tanh(H * x)) for x in bi]

WORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))
fwdRNN = dy.LSTMBuilder(1, 128, 50, model)
bwdRNN = dy.LSTMBuilder(1, 128, 50, model)

pH = model.add_parameters((32, 50*2))
pO = model.add_parameters((ntags, 32))
dy.renew_cg()# initialize the RNNs
f_init = fwdRNN.initial_state()b_init = bwdRNN.initial_state()
wembs = [word_rep(w) for w in words]
fw_exps = f_init.transduce(wembs)
bw_exps = b_init.transduce(reversed(wembs)# biLSTM statesbi = [dy.concatenate([f,b]) for f,b in zip(fw_exps,
reversed(bw_exps))]# MLPsH = dy.parameter(pH)O = dy.parameter(pO)outs = [O*(dy.tanh(H * x)) for x in bi]

WORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))
fwdRNN = dy.LSTMBuilder(1, 128, 50, model)
bwdRNNdef word_rep(w):= dy.LSTMBuilder(1, 128, 50, model)

w_index = vw.w2i[w]return WORDS_LOOKUP[w_index]
dy.renew_cg()# initialize the RNNs
f_init = fwdRNN.initial_state()b_init = bwdRNN.initial_state()
wembs = [word_rep(w) for w in words]
fw_exps = f_init.transduce(wembs)
bw_exps = b_init.transduce(reversed(wembs)# biLSTM statesbi = [dy.concatenate([f,b]) for f,b in zip(fw_exps,
reversed(bw_exps))]# MLPsH = dy.parameter(pH)O = dy.parameter(pO)outs = [O*(dy.tanh(H * x)) for x in bi]

BiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_B

theBiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_BtheBack off to char-LSTM
for rare words
concat

C_F

C_F

C_F

C_F

C_F

C_F

C_F

C_F

C_B

C_B

C_B

C_B

C_B

C_B

C_B

C_B

e

n

g

u

l

f

e

d

BiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

engulfed

LSTM_F
LSTM_B

theBiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

LSTM_F
LSTM_B

theBiLSTM Tagger
tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

LSTM_F
LSTM_BtheWORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))CHARS_LOOKUP= model.add_lookup_parameters((nchars,
20))
fwdRNN = dy.LSTMBuilder(1,128, 50, model)
cFwdRNN
dy.LSTMBuilder(1, 128,
20, 64,bwdRNN == dy.LSTMBuilder(1,50, model)
cBwdRNN = dy.LSTMBuilder(1, 20, 64, model)

WORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))CHARS_LOOKUP= model.add_lookup_parameters((nchars,
20))
fwdRNN = dy.LSTMBuilder(1,128, 50, model)
cFwdRNN
dy.LSTMBuilder(1, 128,
20, 64,bwdRNN == dy.LSTMBuilder(1,50, model)
cBwdRNN = dy.LSTMBuilder(1, 20, 64, model)

def word_rep(w):w_index = vw.w2i[w]return WORDS_LOOKUP[w_index]

WORDS_LOOKUP = model.add_lookup_parameters((nwords, 128))CHARS_LOOKUP= model.add_lookup_parameters((nchars,
20))
fwdRNN = dy.LSTMBuilder(1,128, 50, model)
cFwdRNN
dy.LSTMBuilder(1, 128,
20, 64,bwdRNN == dy.LSTMBuilder(1,50, model)
cBwdRNN = dy.LSTMBuilder(1, 20, 64, model)

def word_rep(w):w_index = vw.w2i[w]return WORDS_LOOKUP[w_index]

def word_rep(w, cf_init, cb_init):
if wc[w] > 5:
w_index = vw.w2i[w]return WORDS_LOOKUP[w_index]
else:
char_ids = [vc.w2i[c] for c in w]
char_embs = [CHARS_LOOKUP[cid] for cid in char_ids]
fw_exps = cf_init.transduce(char_embs)
bw_exps = cb_init.transduce(reversed(char_embs))
return dy.concatenate([ fw_exps[-1], bw_exps[-1] ])def build_tagging_graph(words):
dy.renew_cg()# initialize the RNNs
f_init = fwdRNN.initial_state()b_init = bwdRNN.initial_state()
cf_init = cFwdRNN.initial_state()
cb_init = cBwdRNN.initial_state()
wembs = [word_rep(w, cf_init, cb_init) for w in words]
fws = f_init.transduce(wembs)
bws = b_init.transduce(reversed(wembs))# biLSTM statesbi = [dy.concatenate([f,b]) for f,b in zip(fws, reversed(bws))]# MLPsH = dy.parameter(pH)O = dy.parameter(pO)outs = [O*(dy.tanh(H * x)) for x in bi]
return outs

def tag_sent(words):
vecs = build_tagging_graph(words)
vecs = [dy.softmax(v) for v in vecs]
probs = [v.npvalue() for v in vecs]
tags = []for prb in probs:
tag = np.argmax(prb)tags.append(vt.i2w[tag])
return zip(words, tags)

def sent_loss(words, tags):
vecs = build_tagging_graph(words)
losses = []for v,t in zip(vecs,tags):
tid = vt.w2i[t]loss = dy.pickneglogsoftmax(v, tid)
losses.append(loss)
return dy.esum(losses)

num_tagged = cum_loss = 0
for ITER in xrange(50):random.shuffle(train)
for i,s in enumerate(train,1):
if i > 0 and i % 500 == 0:# print status
trainer.status()print cum_loss / num_tagged
cum_loss = num_tagged = 0
if i % 10000 == 0:# eval on dev
good = bad = 0.0
for sent in dev:
words = [w for w,t in sent]
golds = [t for w,t in sent]tags = [t for w,t in tag_sent(words)]
for go,gu in zip(golds,tags):
if go == gu: good +=1
else: bad+=1
print good/(good+bad)# train on sentwords = [w for w,t in s]
golds = [t for w,t in s]
loss_exp = sent_loss(words, golds)
cum_loss += loss_exp.scalar_value()
num_tagged += len(golds)
loss_exp.backward()
trainer.update()num_tagged = cum_loss = 0
for ITER in xrange(50):random.shuffle(train)
for i,s in enumerate(train,1):
if i > 0 and i % 500 == 0:# print status
trainer.status()print cum_loss / num_taggedpro
cum_loss = num_tagged = 0
gre
if i % 10000 == 0:# eval on dev
ss
rep
good = bad = 0.0orts
for sent in dev:
words = [w for w,t in sent]
golds = [t for w,t in sent]tags = [t for w,t in tag_sent(words)]
for go,gu in zip(golds,tags):
if go == gu: good +=1
else: bad+=1
print good/(good+bad)# train on sentwords = [w for w,t in s]
golds = [t for w,t in s]
loss_exp = sent_loss(words, golds)
cum_loss += loss_exp.scalar_value()
num_tagged += len(golds)
loss_exp.backward()
trainer.update()

trai
nin
g

To summarize this part•We've seen an implementation of a BiLSTM tagger•... where some words are represented as char-level LSTMs•... and other words are represented as word-embedding
vectors•... and the representation choice is determined at run time•

This is a rather dynamic graph structure.

up next•

Even more dynamic graph structure (shift-reduce parsing)•

Extending the BiLSTM tagger to use global inference.

Transition-Based
ParsingStack Buffer

ActionI saw her duck

SHIFT

saw her duck

SHIFT

I saw

her duck

REDUCE-L

I saw

her duck

SHIFT

I

I saw her duck

SHIFT

I saw her duck

REDUCE-L

I saw her duck

REDUCE-R

I saw her duckTransition-based parsing•

Build trees by pushing words (“shift”) onto a stackand combing elements at the top of the stack into a
syntactic constituent (“reduce”)•

Given current stack and buffer of unprocessedwords, what action should the algorithm take?

Let’s use a neural network!

Transition-based parsing
tokens is the sentence to be parsed.
oracle_actions is a list of {SHIFT, REDUCE_L, REDUCE_R}.

Transition-based parsing
tokens is the sentence to be parsed.
oracle_actions is a list of {SHIFT, REDUCE_L, REDUCE_R}.

Transition-based parsing
tokens is the sentence to be parsed.
oracle_actions is a list of {SHIFT, REDUCE_L, REDUCE_R}.

Transition-based parsing
tokens is the sentence to be parsed.
oracle_actions is a list of {SHIFT, REDUCE_L, REDUCE_R}.

Transition-based parsing
tokens is the sentence to be parsed.
oracle_actions is a list of {SHIFT, REDUCE_L, REDUCE_R}.

Transition-based parsing
tokens is the sentence to be parsed.
oracle_actions is a list of {SHIFT, REDUCE_L, REDUCE_R}.

Transition-based parsing
tokens is the sentence to be parsed.
oracle_actions is a list of {SHIFT, REDUCE_L, REDUCE_R}.

Transition-based parsing
tokens is the sentence to be parsed.
oracle_actions is a list of {SHIFT, REDUCE_L, REDUCE_R}.

Transition-based parsing
tokens is the sentence to be parsed.
oracle_actions is a list of {SHIFT, REDUCE_L, REDUCE_R}.

Transition-based parsing•

This is a good problem for dynamic networks!
•

Different sentences trigger different parsing
states•

The state that needs to be embedded is complex(sequences, trees, sequences of trees)•

The parsing algorithm has fairly complicated flow
control and data structures

Transition-based parsing
Challenges
unbounded depth unbounded length
arbitrarily complex trees
reading andforgetting

(

I saw

her duck

I saw her duckI saw her duckTransition-based parsing
State embeddings•

We can embed words•

Assume we can embed tree fragments•

The contents of the buffer are just a sequence••which we periodically “shift” fromThe contents of the stack is just a sequence•which we periodically pop from and push to•

Sequences -> use RNNs to get an encoding!

•

But running an RNN for each state will be expensive. Can we do better?

Transition-based parsing
Stack RNNs•

Augment RNN with a stack pointer•Three constant-time operations•

push - read input, add to top of stack•

pop - move stack pointer back•embedding - return the RNN state at the locationof the stack pointer (which summarizes its
current contents)

Transition-based parsing
Stack RNNs
DyNet:y0;

s=[rnn.inital_state()]s.append[s[-1].add_input(x1)s.pop()
s.append[s[-1].add_input(x2)s.pop()
s.append[s[-1].add_input(x3)Transition-based parsing
Stack RNNs
DyNet:

y0

y1

;

x1

s=[rnn.inital_state()]s.append[s[-1].add_input(x1)s.pop()
s.append[s[-1].add_input(x2)s.pop()
s.append[s[-1].add_input(x3)Transition-based parsing
Stack RNNs
DyNet:

y0

y1

;

x1

s=[rnn.inital_state()]s.append[s[-1].add_input(x1)s.pop()
s.append[s[-1].add_input(x2)s.pop()
s.append[s[-1].add_input(x3)Transition-based parsing
Stack RNNs
DyNet:

y0

y1

y2

;

x1

x2

s=[rnn.inital_state()]s.append[s[-1].add_input(x1)s.pop()
s.append[s[-1].add_input(x2)s.pop()
s.append[s[-1].add_input(x3)Transition-based parsing
Stack RNNs
DyNet:

y0

y1

y2

;

x1

x2

s=[rnn.inital_state()]s.append[s[-1].add_input(x1)s.pop()
s.append[s[-1].add_input(x2)s.pop()
s.append[s[-1].add_input(x3)Transition-based parsing
Stack RNNs
DyNet:

y0

y1

y2

y3

;

x1

x2

x3

s=[rnn.inital_state()]s.append[s[-1].add_input(x1)s.pop()
s.append[s[-1].add_input(x2)s.pop()
s.append[s[-1].add_input(x3)Transition-based parsing
DyNet wrapper implementation:

Transition-based parsing
Representing the state
)

od

am

(
FT D-L
I
SH RE

SHIFT

pt

…
REDUCE_L

REDUCE_R

Transition-based parsing
Representing the state

|

{z
S

)

am

(
FT D-L
I
SH RE

SHIFT

TO

P

}

amod

;

od

an
decisionoverhasty

pt…
REDUCE_L

REDUCE_Ram(
FT D-L
I
SH RE

SHIFT

|

{z

TO

P

pt

…
REDUCE_L

REDUCE_R

}

S

)

od

P
O
T

{z

Transition-based parsing
Representing the state

B

}

amod

;

an
decisionoverhasty

was

made

root

Transition-based parsing
Syntactic compositions

headhTransition-based parsing
Syntactic compositions

modifier

head

m

h

Transition-based parsing
Syntactic compositions
c = tanh(W[h; m] + b)

modifier

head

m

h

Transition-based parsing
Syntactic compositions

It is very easy to experiment with different
composition functions.

Code Touram(
FT D-L
I
SH RE

SHIFT

|

{z

TO

P

pt

…
REDUCE_L

REDUCE_R

}

S

)

od

P
O
T

{z

Transition-based parsing
Representing the state

B

}

amod

;

an
decisionoverhasty

was

made

root

Transition-based parsing
Representing the state…
REDUCE_L

SHIFT

REDUCE_R

pt

|

{z

TO

}

am

(
FT D-L
I
SH RE

{z

S

)

od

B

P
O
T

P

}

amod

;

was

A

made

TO

| {z }

andecisionoverhasty

P

REDUCE-LEFT(amod)

SHIFT

root

Transition-based parsing
Pop quiz•

How should we add this functionality?

Structured Training

What do we Know So Far?

•

How to create relatively complicated models•

How to optimize them given an oracle action
sequenceLocal vs. Global Inference•

What if optimizing local decisions doesn’t lead to good global
decisions?

time flies like an arrowP( NN VBZ PRPDET NN ) = 0.4
P( NN NNP VB DET NN ) = 0.3
P( VB NNP PRPDET NN ) = 0.3
NN NNP PRPDET NN•

Simple solution: input last label (e.g. RNNLM)→ Modeling search is difficult, can lead down garden paths•

Better solutions:• Local consistency parameters (e.g. CRF: Lample et al. 2016)• Global training (e.g. globally normalized NNs: Andor et al. 2016)

BiLSTM Tagger w/ Tag
Bigram Parameters



tag

tag

tag

tag

tag

MLP

MLP

MLP

MLP

MLP

concatconcatconcatconcatconcat

LSTM_F
LSTM_Bthe

LSTM_F
LSTM_Bbrown

LSTM_F
LSTM_Bfox

LSTM_F
LSTM_B

LSTM_F
LSTM_Bthe
From Local to Global•

Standard BiLSTM loss function:log P (y|x) =Xi•log P (yi |x)With transition features:

log emission
probs as scores

1 X
log P (y, x) =(se (yi , x) + st (yi 1 , yi ))Z iglobal normalizationtransition scores

How do We Train?
•

Cannot simply enumerate all possibilities and do backprop•

In easily decomposable cases, can use DP to calculate
gradients (CRF)•

More generally applicable solutions: structured perceptron,
margin-based methods

Structured Perceptron
Overviewŷ = argmax score(y|x; ✓)ytime flies like an arrow
Hypothesis
Reference≠
NN VBZ PRPDET NN
NN NNP VB DET NN
Update!
Perceptron Loss`percep (x, y, ✓) = max(score(ŷ|x; ✓)score(y|x; ✓), 0)

Structured Perceptron in
DyNet
def viterbi_sent_loss(words, tags):
vecs = build_tagging_graph(words)
vit_tags, vit_score = viterbi_decoding(vecs, tags)
if vit_tags != tags:
ref_score = forced_decoding(vecs, tags)
return vit_score - ref_score
else:
return dy.scalarInput(0)Viterbi Algorithm
time



flies

like

an

arrow

Viterbi Algorithm
time
s1,NN



NN
s1,NNP
NNP

s1,VB
VB
s1,VBZ
VBZ

s1,DET
DET

s1,PRP
PRP

…

flies

like

an

arrow

Viterbi Algorithm
time

flies

s1,NN



NN
s1,NNP
NNP

s1,VB
VB
s1,VBZ
VBZ

s1,DET
DET

s1,PRP
PRP

…

NN

like

an

arrow

Viterbi Algorithm



time

flies

s1,NN

s2,NN

NN

NN

s1,NNP
NNP

s1,VB
VB
s1,VBZ
VBZ

s1,DET
DET

s1,PRP
PRP

…

like

an

arrow

Viterbi Algorithm



time

flies

s1,NN

s2,NN

NN

NN

s1,NNP

s2,NNP

NNP

NNP

s1,VB

s2,VB

VB

VB

s1,VBZ

s2,VBZ

VBZ

VBZ

s1,DETs2,DET

DET

DET

s1,PRP

s2,PRP

PRP

PRP

…

…

like

an

arrow

Viterbi Algorithm



time

flies

like

an

arrow

s1,NN

s2,NN

s3,NN

s4,NN

s5,NN

s6,


NN

NN

NN

NN

NN




s1,NNP

s2,NNP

s3,NNP

s4,NNP

s5,NNP

NNP

NNP

NNP

NNP

NNP

s1,VB

s2,VB

s3,VB

s4,VB

s5,VB

VB

VB

VB

VB

VB

s1,VBZ

s2,VBZ

s3,VBZ

s4,VBZ

s5,VBZ

VBZ

VBZ

VBZ

VBZ

VBZ

s1,DETs2,DETs3,DETs4,DETs5,DET

DET

DET

DET

DET

DET

s1,PRP

s2,PRP

s3,PRP

s4,PRP

s5,PRP

PRP

PRP

PRP

PRP

PRP

…

…

…

…

…

Viterbi Algorithm



time

flies

like

an

arrow

s1,NN

s2,NN

s3,NN

s4,NN

s5,NN

s6,


NN

NN

NN

NN

NN




s1,NNP

s2,NNP

s3,NNP

s4,NNP

s5,NNP

NNP

NNP

NNP

NNP

NNP

s1,VB

s2,VB

s3,VB

s4,VB

s5,VB

VB

VB

VB

VB

VB

s1,VBZ

s2,VBZ

s3,VBZ

s4,VBZ

s5,VBZ

VBZ

VBZ

VBZ

VBZ

VBZ

s1,DETs2,DETs3,DETs4,DETs5,DET

DET

DET

DET

DET

DET

s1,PRP

s2,PRP

s3,PRP

s4,PRP

s5,PRP

PRP

PRP

PRP

PRP

PRP

…

…

…

…

…

Code

Viterbi Initialization Code
time

flies

like

an

arrow

s0,
 = 0
s0,NN = -∞NN

s0 = [0, 1, 1, . . .]T

s0,NNP = -∞NNP

s0,VB = -∞VB
s0,VBZ = -∞VBZ

s0,DET = -∞DET…

init_score = [SMALL_NUMBER] * ntags
init_score[S_T] = 0
for_expr = dy.inputVector(init_score)Viterbi Forward Step
time

flies

1 X
log
P
(y,
x)
=
(s
(y
,
x)
+
s
(y
,
y
))
e
i
t
i
1
i
NN
NN
Z i

s1,NN



s1,NNP
NNP

s1,VB
VB
s1,VBZ

s2,NNP,NN

sf,i,j,k = sf,i 1,j + se,i,k + st,j,k

forwardtransition
emission

VBZ

s1,DET
DET

s1,PRPPRP…

i = 2 (time step)j = NNP (previous POS)
k = NN (next POS)

Viterbi Forward Step
time

flies

s1,NN



NN

s2,NN,NN

NN

s1,NNP s2,NNP,NN
NNP

s2,VB,NN

s1,VB s2,VBZ,NN

VB
s1,VBZ
VBZ

s1,DET
DET

s1,PRP
PRP…

s2,DET,NN
s2,PRP,NN

sf,i,j,k = sf,i 1,j + se,i,k + st,j,kViterbi Forward Step
time

flies

s1,NN



NN

s2,NN,NN

NN

s1,NNP s2,NNP,NN
NNP

s2,VB,NN

s1,VB s2,VBZ,NN

VB
s1,VBZ
VBZ

s1,DET
DET

s1,PRP
PRP…

s2,DET,NN
s2,PRP,NN

sf,i,j,k = sf,i 1,j + se,i,k + st,j,kvectorize
sf,i,k = sf,i 1 + se,i,k + st,k

Viterbi Forward Step



time

flies

s1,NN

s2,NN

sf,i,j,k = sf,i 1,j + se,i,k + st,j,k

NN

NN

vectorize
sf,i,k = sf,i 1 + se,i,k + st,ks1,NNP
NNP

s1,VB
VB
s1,VBZ
VBZ

s1,DET
DET

s1,PRPPRP…

max
sf,i,k = max(sf,i,k )Viterbi Forward Step



time

flies

s1,NN

s2,NN

sf,i,j,k = sf,i 1,j + se,i,k + st,j,k

NN

NN

s1,NNP

s2,NNP

NNP

NNP

vectorize
sf,i,k = sf,i 1 + se,i,k + st,k

s1,VB

s2,VB

VB

VB

s1,VBZ

s2,VBZ

VBZ

VBZ

s1,DETs2,DET

DET

DET

s1,PRP

s2,PRP

PRP

PRP

…

…

max
sf,i,k = max(sf,i,k )recurseconcatsf,i = concat(sf,i,1 , sf,i,2 , . . .)

Transition Matrix in DyNet
Add additional parameters
TRANS_LOOKUP = model.add_lookup_parameters((ntags, ntags))

Initialize at sentence starttrans_exprs = [TRANS_LOOKUP[tid] for tid in range(ntags)]

Viterbi Forward in DyNet# Perform the forward pass through the sentence
for i, vec in enumerate(vecs):
my_best_ids = []my_best_exprs = []for next_tag in range(ntags):# Calculate vector for single next tag
next_single_expr = for_expr + trans_exprs[next_tag]
next_single = next_single_expr.npvalue()# Find and save the best scoremy_best_id = np.argmax(next_single)
my_best_ids.append(my_best_id)
my_best_exprs.append(dy.pick(next_single_expr, my_best_id))# Concatenate vectors and add emission probs
for_expr = dy.concatenate(my_best_exprs) + vec# Save the best ids
best_ids.append(my_best_ids)

and do similar for final “
” tagViterbi Backward in DyNet# Perform the reverse pass
best_path = [vt.i2w[my_best_id]]
for my_best_ids in reversed(best_ids):
my_best_id = my_best_ids[my_best_id]
best_path.append(vt.i2w[my_best_id])
best_path.pop() # Remove final 
best_path.reverse()# Return the best path and best score as an expression
return best_path, best_exprForced Decoding in DyNet
def forced_decoding(vecs, tags):# Initialize
for_expr = dy.scalarInput(0)for_tag = S_T# Perform the forward pass through the sentence
for i, vec in enumerate(vecs):
my_tag = vt.w2i[tags[i]]my_trans = dy.pick(TRANS_LOOKUP[my_tag], for_tag)
for_expr = for_expr + my_trans + vec[my_tag]
for_tag = my_tag
for_expr = for_expr + dy.pick(TRANS_LOOKUP[S_T], for_tag)
return for_expr

Caveat: Downsides ofStructured Training•

Structured training allows for richer models•

But, it has disadvantages••

Speed: requires more complicated algorithms•

Stability: often can’t enumerate whole hypothesis space

One solution: initialize with ML, continue with structured
training

Bonus: Margin Methods•

Idea: we want the model to be really sure about the best path•

During search, give bonus to all but correct tag




s1,NN

s2,NN +1

NN

NN

s1,NNP +1

s2,NNP +1

NNP

NNP

s1,VB +1

s2,VB

VB

VB

s1,VBZ +1

s2,VBZ +1

VBZ

VBZ

s1,DET +1

s2,DET +1

DET

DET

s1,PRP +1

s2,PRP +1

PRP

PRP

…

…

Margins in DyNet
def viterbi_decoding(vecs, gold_tags = []):...
for i, vec in enumerate(vecs):...
for_expr = dy.concatenate(my_best_exprs) + vec
if MARGIN != 0 and len(gold_tags) != 0:
adjust = [MARGIN] * ntags
adjust[vt.w2i[gold_tags[i]]] = 0
for_expr = for_expr + dy.inputVector(adjust)Conclusion

Training NNs for NLP•

We want the flexibility to handle the structures we like•

We want to write code the way that we think about models•

DyNet gives you the tools to do so!

•

We welcome contributors to make it even better