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

https://github.com/clab/dynet_tutorial_examples

November 1, 2016

EMNLP

Neural Nets and Language•

Tension: Language and neural nets•

Language is discrete and structured••

Sequences, trees, graphs

Neural nets represent things with continuous vectors•

Poor “native support” for structure•

The big challenge is writing code that translates between the{discrete-structured, continuous} regimes•

This tutorial is about one framework that lets you use the power ofneural nets without abandoning familiar NLP algorithms

Outline•

Part 1•

Computation graphs and their construction•

Neural Nets in DyNet•

Recurrent neural networks•

Minibatching•

Adding new differentiable functions

Outline•

Part 2: Case Studies•

Tagging with bidirectional RNNs•

Transition-based dependency parsing•

Structured prediction meets deep learning

Computation Graphs
Deep Learning’s Lingua Francaexpression:>y = x Ax + b · x + cgraph:A node is a {tensor, matrix, vector, scalar} valuexAn edge represents a function argument
expression:(and alsoandatadependency).
They
are
just
>
y = x toAxnodes.
+b·x+cpointers
A node with an incoming edge is a function ofgraph:
thatedge’s tail node.
A node knows how to compute its value and thevalue of its derivative w.r.t each argument (edge)@Ftimes a derivative of an arbitrary input @f (u) .
f (u) = u>@f (u) @F=@u @f (u)x✓@F@f (u)◆>

expression:>y = x Ax + b · x + cgraph:
Functions can be nullary, unary,binary, … n-ary. Often they are unary or binary.
f (U, V) = UV
f (u) = u>Ax

expression:>y = x Ax + b · x + cgraph:f (M, v) = Mv
f (U, V) = UV
f (u) = u>AxComputation graphs are directed and acyclic (in DyNet)expression:>y = x Ax + b · x + cgraph:f (M, v) = Mv

f (x, A) = x> Axf (U, V) = UV
f (u) = u

x

>

A
x

A

@f (x, A)= (A> + A)x@x@f (x, A)= xx>@Aexpression:>y = x Ax + b · x + cgraph:f (x1 , x2 , x3 ) =

X

xi

i

f (M, v) = Mv
f (U, V) = UV
f (u, v) = u · v

f (u) = u>

A
x

b

c

expression:>y = x Ax + b · x + cgraph:f (x1 , x2 , x3 ) =

y

X

xi

i

f (M, v) = Mv
f (U, V) = UV
f (u, v) = u · v

f (u) = u>

A
x

b

c

variable names are just labelings of nodes.

Algorithms•

Graph construction•

Forward propagation•

Loop over nodes in topological order•••

Compute the value of the node given its inputs

Given my inputs, make a prediction (or compute an “error” with respect to a “target
output”)

Backward propagation•

Loop over the nodes in reverse topological order starting with a final goal node••Compute derivatives of final goal node value with respect to each edge’s tailnode

How does the output change if I make a small change to the inputs?

Forward Propagationgraph:f (x1 , x2 , x3 ) =

X

xi

i

f (M, v) = Mv
f (U, V) = UV
f (u, v) = u · v

f (u) = u>

A
x

b

c

Forward Propagationgraph:f (x1 , x2 , x3 ) =

X

xi

i

f (M, v) = Mv
f (U, V) = UV
f (u, v) = u · v

f (u) = u>

A
x

b

c

Forward Propagationgraph:f (x1 , x2 , x3 ) =

X

xi

i

f (M, v) = Mv
f (U, V) = UV
f (u, v) = u · v

f (u) = u>

A
x

b

c

Forward Propagationgraph:f (x1 , x2 , x3 ) =

X

xi

i

f (M, v) = Mv
f (U, V) = UV
f (u, v) = u · v

f (u) = u>

A

x>

x

b

c

Forward Propagationgraph:f (x1 , x2 , x3 ) =

X

xi

i

f (M, v) = Mv
f (U, V) = UV
x> Af (u, v) = u · v

f (u) = u>

A

x>

x

b

c

Forward Propagationgraph:f (x1 , x2 , x3 ) =

X

xi

i

f (M, v) = Mv
f (U, V) = UV
x> Af (u, v) = u · v

f (u) = u>

A

x>

x

b·x

b

c

Forward Propagationgraph:f (x1 , x2 , x3 ) =

X

xi

i

f (M, v) = Mv
x> Ax
f (U, V) = UV
x> Af (u, v) = u · v

f (u) = u>

A

x>

x

b·x

b

c

Forward Propagationgraph:f (x1 , x2 , x3 ) =

X

xi

i

>

x Ax + b · x + cf (M, v) = Mv
x> Ax
f (U, V) = UV
x> Af (u, v) = u · v

f (u) = u>

A

x>

x

b·x

b

c

The MLPh = tanh(Wx + b)
y = Vh + af (u, v) = u + v
f (M, v) = Mvaf (u) = tanh(u)f (u, v) = u + v

hf (M, v) = Mv

b
W

x

V

Constructing Graphs

Two Software Models••

Static declaration•

Phase 1: define an architecture(maybe with some primitive flow control like loops andconditionals)•

Phase 2: run a bunch of data through it to train themodel and/or make predictions

Dynamic declaration•

Graph is defined implicitly (e.g., using operator
overloading) as the forward computation is executedHierarchical Structure
Words

Sentences
S
VP
VP
PP

NP

Alice

Phrasesgave amessageto BobDocuments
This film was completely unbelievable.
The characters were wooden and the plot was absurd.
That being said, I liked it.

Static Declaration
•

•

•

Pros
•

Offline optimization/scheduling of graphs is powerful•

Limits on operations mean better hardware support

Cons•

Structured data (even simple stuff like sequences), even variablesized data, is ugly•

You effectively learn a new programming language (“the Graph
Language”) and you write programs in that language to process data.

examples: Torch, Theano, TensorFlow

Dynamic Declaration
•

•

•

Pros
•

library is less invasive•

the forward computation is written in your favorite programming
language with all its features, using your favorite algorithms•

interleave construction and evaluation of the graphCons•little time for graph optimization•

if the graph is static, effort can be wasted

examples: Chainer, most automatic differentiation libraries, DyNetDynamic Structure?
••

Hierarchical structures exist in language•

We might want to let the network reflect that hierarchy•

Hierarchical structure is easiest to process withtraditional flow-control mechanisms in your favorite
languages

Combinatorial algorithms (e.g., dynamic programming)•

Exploit independencies to compute over a large
space of operations tractably

Why DyNet?
•••

The state of the world before DyNet/cnn•

AD libraries are fast and good, but don’t have support for deep learning
must-haves (GPUs, optimization algorithms, primitives for implementing
RNNs, etc.)•

Deep learning toolkits don’t support dynamic graphs well

DyNet is a hybrid between a generic autodiff library and a Deep learning toolkit•

It has the flexibility of a good AD library•

It has most obligatory DL primitives(Although the emphasis is dynamic operation, it can run perfectly well in “staticmode”. It’s quite fast too! But if you’re happy with that, probably stick to
TensorFlow/Theano/Torch.)Why DyNet?
•••

The state of the world before DyNet/cnn•

AD libraries are fast and good, but don’t have support for deep learning
must-haves (GPUs, optimization algorithms, primitives for implementing
RNNs, etc.)•

Deep learning toolkits don’t support dynamic graphs well

DyNet is a hybrid between a generic autodiff library and a Deep learning toolkit•

It has the flexibility of a good AD library•

It has most obligatory DL primitives(Although the emphasis is dynamic operation, it can run perfectly well in “staticmode”. It’s quite fast too! But if you’re happy with that, probably stick to
TensorFlow/Theano/Torch.)

How does it work?
•

C++ backend based on Eigen••

Custom (“quirky”) memory management••

Eigen also powers TensorFlow

You probably don’t need to ever think about this,but a few well-hidden assumptions make thegraph construction and execution very fast.

Thin Python wrapper on C++ API

Neural Networks in
DyNet

The Major Players•

Computation Graph•

Expressions (~ nodes in the graph)•

Parameters

•

Model
•

•

a collection of parameters

TrainerComputation Graphand Expressions

import dynet as dy

dy.renew_cg() # create a new computation graph
v1 = dy.inputVector([1,2,3,4])v2 = dy.inputVector([5,6,7,8])# v1 and v2 are expressions
v3 = v1 + v2
v4 = v3 * 2
v5 = v1 + 1
v6 = dy.concatenate([v1,v2,v3,v5])
print v6
print v6.npvalue()Computation Graphand Expressions

import dynet as dy

dy.renew_cg() # create a new computation graph
v1 = dy.inputVector([1,2,3,4])v2 = dy.inputVector([5,6,7,8])# v1 and v2 are expressions
v3 = v1 + v2
v4 = v3 * 2
v5 = v1 + 1
v6 = dy.concatenate([v1,v2,v3,v5])
print v6 expression 5/1
print v6.npvalue()Computation Graphand Expressions

import dynet as dy

dy.renew_cg() # create a new computation graph
v1 = dy.inputVector([1,2,3,4])v2 = dy.inputVector([5,6,7,8])# v1 and v2 are expressions
v3 = v1 + v2
v4 = v3 * 2
v5 = v1 + 1
v6 = dy.concatenate([v1,v2,v3,v5])
print v6
print v6.npvalue()
array([

1.,

2.,

3.,

4.,

2.,

4.,

6.,

8.,

4.,

8.,

12.,

16.])

Computation Graphand Expressions•

Create basic expressions.

•

Combine them using operations.

•

Expressions represent symbolic computations.

•Use:.value().npvalue().scalar_value().vec_value().forward()
to perform actual computation.

Model and Parameters•

Parameters are the things that we optimize over(vectors, matrices).

•

Model is a collection of parameters.

•

Parameters out-live the computation graph.

Model and Parametersmodel = dy.Model()pW = model.add_parameters((20,4))
pb = model.add_parameters(20)dy.renew_cg()
x = dy.inputVector([1,2,3,4])
W = dy.parameter(pW) # convert params to expressionb = dy.parameter(pb) # and add to the graphy = W * x + b

Parameter Initialization
model = dy.Model()pW = model.add_parameters((4,4))
pW2 = model.add_parameters((4,4), init=dy.GlorotInitializer())
pW3 = model.add_parameters((4,4), init=dy.NormalInitializer(0,1))
pW4 = model.parameters_from_numpu(np.eye(4))

Trainers and Backdrop•

Initialize a Trainer with a given model.

•

Compute gradients by calling expr.backward()
from a scalar node.

•Call trainer.update() to update the model
parameters using the gradients.

Trainers and Backdrop
model = dy.Model()trainer = dy.SimpleSGDTrainer(model)
p_v = model.add_parameters(10)for i in xrange(10):dy.renew_cg()
v = dy.parameter(p_v)
v2 = dy.dot_product(v,v)
v2.forward()
v2.backward()# compute gradients

trainer.update()

Trainers and Backdrop
model = dy.Model()trainer = dy.SimpleSGDTrainer(model)
dy.SimpleSGDTrainer(model,...)
p_v = model.add_parameters(10)dy.MomentumSGDTrainer(model,...)
for i in xrange(10):dy.AdagradTrainer(model,...)
dy.renew_cg()
dy.AdadeltaTrainer(model,...)
v = dy.parameter(p_v)
v2 = dy.dot_product(v,v)
dy.AdamTrainer(model,...)
v2.forward()
v2.backward()# compute gradients

trainer.update()

Training with DyNet•

Create model, add parameters, create trainer.

•

For each training example:•

create computation graph for the loss•

run forward (compute the loss)•

run backward (compute the gradients)•

update parameters

Example: MLP for XOR

LINEAR MODELS: THE XOR PROBLEM

nd log-linear) models is severely restricted. For example,• Data:• Model form:
ction,
defined as:ŷ = (v · tanh(Ux + b))

xor(0, 0) = 0
xor(1, 0) = 1
xor(0, 1) = 1

•

Loss:

xor(1, 1) = 0xytion w 2 R2 , b 2 R such that:`=(log ŷ
log(1y=1ŷ) y = 0

import dynet as dy
import randomŷ = (v · tanh(Ux + b))

data =[ ([0,1],0),([1,0],0),([0,0],1),([1,1],1) ]model = dy.Model()pU = model.add_parameters((4,2))
pb = model.add_parameters(4)pv = model.add_parameters(4)trainer = dy.SimpleSGDTrainer(model)
closs = 0.0
for ITER in xrange(1000):
random.shuffle(data)for x,y in data:....

ŷ = (v · tanh(Ux + b))
for ITER in xrange(1000):
for x,y in data:# create graph for computing loss
dy.renew_cg()
U = dy.parameter(pU)b = dy.parameter(pb)v = dy.parameter(pv)x = dy.inputVector(x)# predictyhat = dy.logistic(dy.dot_product(v,dy.tanh(U*x+b)))# loss(
if y == 0:
log ŷ
y=1
loss = -dy.log(1 - yhat)`=elif y == 1:
log(1
ŷ)
y
=
0
loss = -dy.log(yhat)closs += loss.scalar_value() # forward
loss.backward()
trainer.update()ŷ = (v · tanh(Ux + b))
for ITER in xrange(1000):
for x,y in data:# create graph for computing loss
dy.renew_cg()
U = dy.parameter(pU)b = dy.parameter(pb)v = dy.parameter(pv)x = dy.inputVector(x)# predictyhat = dy.logistic(dy.dot_product(v,dy.tanh(U*x+b)))# loss
if y == 0:loss = -dy.log(1 - yhat)elif y == 1:
loss = -dy.log(yhat)closs += loss.scalar_value() # forward
loss.backward()
trainer.update()ŷ = (v · tanh(Ux + b))
for ITER in xrange(1000):
for x,y in data:# create graph for computing loss
dy.renew_cg()
U = dy.parameter(pU)b = dy.parameter(pb)v = dy.parameter(pv)x = dy.inputVector(x)# predictyhat = dy.logistic(dy.dot_product(v,dy.tanh(U*x+b)))# loss
if y == 0:loss = -dy.log(1 - yhat)elif y == 1:
loss = -dy.log(yhat)closs += loss.scalar_value() # forward
loss.backward()
trainer.update()ŷ = (v · tanh(Ux + b))
for ITER in xrange(1000):
for x,y in data:# create graph for computing loss
dy.renew_cg()
U = dy.parameter(pU)b = dy.parameter(pb)v = dy.parameter(pv)x = dy.inputVector(x)# predictyhat = dy.logistic(dy.dot_product(v,dy.tanh(U*x+b)))# loss(
if y == 0:
log ŷ
y=1
loss = -dy.log(1 - yhat)`=elif y == 1:
log(1
ŷ)
y
=
0
loss = -dy.log(yhat)closs += loss.scalar_value() # forward
loss.backward()
trainer.update()ŷ = (v · tanh(Ux + b))
for ITER in xrange(1000):
for x,y in data:# create graph for computing loss
dy.renew_cg()
U = dy.parameter(pU)b = dy.parameter(pb)v = dy.parameter(pv)x = dy.inputVector(x)# predictyhat = dy.logistic(dy.dot_product(v,dy.tanh(U*x+b)))# loss(
if y == 0:
log ŷ
y=1
loss = -dy.log(1 - yhat)`=elif y == 1:
log(1
ŷ)
y
=
0
loss = -dy.log(yhat)closs += loss.scalar_value() # forward
loss.backward()
trainer.update()ŷ = (v · tanh(Ux + b))
for ITER in xrange(1000):
for x,y in data:# create graph for computing loss
dy.renew_cg()
U = dy.parameter(pU)b = dy.parameter(pb)v = dy.parameter(pv)x = dy.inputVector(x)# predictyhat = dy.logistic(dy.dot_product(v,dy.tanh(U*x+b)))# loss(
if y == 0:
log ŷ
y=1
loss = -dy.log(1 - yhat)`=elif y == 1:
log(1
ŷ)
y
=
0
loss = -dy.log(yhat)closs += loss.scalar_value() # forward
loss.backward()
if
ITER > 0 and ITER % 100 == 0:
trainer.update()
print "Iter:",ITER,"loss:", closs/400
closs = 0

for ITER in xrange(1000):
for x,y in data:# create graph for computing loss
dy.renew_cg()
U = dy.parameter(pU)b = dy.parameter(pb)v = dy.parameter(pv)x = dy.inputVector(x)# predictyhat = dy.logistic(dy.dot_product(v,dy.tanh(U*x+b)))# loss
if y == 0:loss = -dy.log(1 - yhat)elif y == 1:
loss = -dy.log(yhat)closs += loss.scalar_value() # forward
loss.backward()
trainer.update()

lets organize the code a bit
for ITER in xrange(1000):
for x,y in data:# create graph for computing loss
dy.renew_cg()
U = dy.parameter(pU)b = dy.parameter(pb)v = dy.parameter(pv)x = dy.inputVector(x)# predictyhat = dy.logistic(dy.dot_product(v,dy.tanh(U*x+b)))# loss
if y == 0:loss = -dy.log(1 - yhat)elif y == 1:
loss = -dy.log(yhat)closs += loss.scalar_value() # forward
loss.backward()
trainer.update()

lets organize the code a bit
for ITER in xrange(1000):
for x,y in data:# create graph for computing loss
dy.renew_cg()
U = dy.parameter(pU)xb == dy.inputVector(x)dy.parameter(pb)#predictv = dy.parameter(pv)yhat= predict(x)x = dy.inputVector(x)#loss# predictloss
y)yhat == compute_loss(yhat,
dy.logistic(dy.dot_product(v,dy.tanh(U*x+b)))#
loss += loss.scalar_value() # forwardcloss
if
y == 0:loss.backward()
loss = -dy.log(1 - yhat)trainer.update()
elif y == 1:
loss = -dy.log(yhat)closs += loss.scalar_value() # forward
loss.backward()
trainer.update()for ITER in xrange(1000):
for x,y in data:# create graph for computing loss
dy.renew_cg()
U = dy.parameter(pU)xb == dy.inputVector(x)dy.parameter(pb)#predictv = dy.parameter(pv)yhat= predict(x)x = dy.inputVector(x)#loss# predictloss
y)yhat == compute_loss(yhat,
dy.logistic(dy.dot_product(v,dy.tanh(U*x+b)))#
loss += loss.scalar_value() # forwardcloss
if
y == 0:loss.backward()
loss = -dy.log(1 - yhat)trainer.update()
elif y == 1:
loss = -dy.log(yhat)
def predict(expr):ŷ = (v · tanh(Ux + b))
U = dy.parameter(pU)
closs+= loss.scalar_value() # forwardb = dy.parameter(pb)loss.backward()
v = dy.parameter(pv)trainer.update()y = dy.logistic(dy.dot_product(v,dy.tanh(U*expr+b)))
return yfor ITER in xrange(1000):
for x,y in data:# create graph for computing loss
dy.renew_cg()
U = dy.parameter(pU)xb == dy.inputVector(x)dy.parameter(pb)#predictv = dy.parameter(pv)yhat= predict(x)x = dy.inputVector(x)#loss# predictloss
y)yhat == compute_loss(yhat,
dy.logistic(dy.dot_product(v,dy.tanh(U*x+b)))#
loss += loss.scalar_value() # forwardcloss
if
y == 0:loss.backward()
loss = -dy.log(1 - yhat)trainer.update()
elif y == 1:
loss = -dy.log(yhat)(
def compute_loss(expr, y):log ŷ
y=1
`=
closs
+= 0:
loss.scalar_value() # forward
if y ==
log(1
ŷ)
y
=
0
loss.backward()
return -dy.log(1 - expr)
trainer.update()
elif y == 1:
return -dy.log(expr)

Key Points•

Create computation graph for each example.

•

Graph is built by composing expressions.

•

Functions that take expressions and return
expressions define graph components.

Word Embeddings and
LookupParameters•

In NLP, it is very common to use featureembeddings.

•

Each feature is represented as a d-dim vector.

•

These are then summed or concatenated to form
an input vector.

•

The embeddings can be pre-trained.

•

They are usually trained with the model.

"feature embeddings"•

Each feature is assigned a vector.

•

The input is a combination of feature vectors.

•

The feature vectors are parameters of the modeland are trained jointly with the rest of the network.

•

Representation Learning: similar features will
receive similar vectors.

"feature embeddings"

Word Embeddings and
LookupParameters•

In DyNet, embeddings are implemented using
LookupParameters.

vocab_size = 10000
emb_dim = 200
E = model.add_lookup_parameters((vocab_size, emb_dim))

Word Embeddings and
LookupParameters•

In DyNet, embeddings are implemented using
LookupParameters.

vocab_size = 10000
emb_dim = 200
E = model.add_lookup_parameters((vocab_size, emb_dim))dy.renew_cg()
x = dy.lookup(E, 5)# or
x = E[5]# x is an expression

Deep Unordered Composition Rivals Syntactic Methods
for Text Classification
Mohit Iyyer,1 Varun Manjunatha,1 Jordan Boyd-Graber,2 Hal Daumé III1
1
University of Maryland, Department of Computer Science and UMIACS
2
University of Colorado, Department of Computer Science{miyyer,varunm,hal}@umiacs.umd.edu, Jordan.Boyd.Graber@colorado.edu"Document Averaging
Networks"
Abstract
results haveshown that syntactic functions outperMany existing deep learning models fornatural language processing tasks focus onlearning the compositionality of their inputs, which requires many expensive com-form unordered functions on many tasks (Socher
et al., 2013b; Kalchbrenner and Blunsom, 2013).
However, there is a tradeoff: syntactic functions
require more training time than unordered composition functions and are prohibitively expensive intext classification

scores of labels

sof tmax(⇤)
scores of labels

g 2 (W2 ⇤ + b2 )sof tmax(⇤)

g 1 (W1 ⇤ + b1 )CBOW (⇤)

CBOW (⇤)

w1 , ..., wn

w1 , ..., wn

eural bag of words""deep averaging network"
CBOW (w1 , . . . , wn ) =

n
X
i=1

E[wi ]

lets define this networkscores of labels

sof tmax(⇤)
scores of labels

g 2 (W2 ⇤ + b2 )sof tmax(⇤)

g 1 (W1 ⇤ + b1 )CBOW (⇤)

CBOW (⇤)

w1 , ..., wn

w1 , ..., wn"neural bag of words""deep averaging network"g 1 = g 2 = tanh
CBOW (w1 , . . . , wn ) =

n
X
i=1

E[wi ]

pW1 = model.add_parameters((HID, EDIM))
pb1 = model.add_parameters(HID)scores of labels

sof tmax(⇤)

pW2 = model.add_parameters((NOUT, HID))
scores of labels
pb2 = model.add_parameters(NOUT)

g 2 (W2 ⇤ + b2 )sof tmax(⇤) EDIM))
E = model.add_lookup_parameters((V,g 1 (W1 ⇤ + b1 )CBOW (⇤)

CBOW (⇤)

w1 , ..., wn

w1 , ..., wn"neural bag of words""deep averaging network"g 1 = g 2 = tanh
CBOW (w1 , . . . , wn ) =

n
X
i=1

E[wi ]

pW1 = model.add_parameters((HID, EDIM))
pb1 = model.add_parameters(HID)scores of labels

sof tmax(⇤)

pW2 = model.add_parameters((NOUT, HID))
scores of labels
pb2 = model.add_parameters(NOUT)

g 2 (W2 ⇤ + b2 )sof tmax(⇤) EDIM))
E = model.add_lookup_parameters((V,g 1 (W1 ⇤ + b1 )CBOW (⇤)

CBOW (⇤)

w1 , ..., wn

w1 , ..., wn"neural bag of words""deep averaging network"for (doc, label) in data:
dy.renew_cg()
probs = predict_labels(doc)def predict_labels(doc):
x = encode_doc(doc)h = layer1(x)y = layer2(h)return dy.softmax(y)scores of labels

sof tmax(⇤)
scores of labels

g 2 (W2 ⇤ + b2 )sof tmax(⇤)

g 1 (W1 ⇤ + b1 )CBOW (⇤)

CBOW (⇤)

w1 , ..., wn

w1 , ..., wn

def layer1(x):"deep averaging network"
W = dy.parameter(pW1) "neural bag of words"
b = dy.parameter(pb1)
return dy.tanh(W*x+b)
for (doc, label) in data:
def layer2(x):W = dy.parameter(pW2)b = dy.parameter(pb2)
return dy.tanh(W*x+b)

dy.renew_cg()
probs = predict_labels(doc)def predict_labels(doc):
x = encode_doc(doc)h = layer1(x)y = layer2(h)return dy.softmax(y)scores of labels

sof tmax(⇤)
scores of labels

g 2 (W2 ⇤ + b2 )sof tmax(⇤)

g 1 (W1 ⇤ + b1 )CBOW (⇤)

CBOW (⇤)

w1 , ..., wn

w1 , ..., wn

def layer1(x):"deep averaging network"
W = dy.parameter(pW1) "neural bag of words"
b = dy.parameter(pb1)
return dy.tanh(W*x+b)
for (doc, label) in data:
def layer2(x):W = dy.parameter(pW2)b = dy.parameter(pb2)
return dy.tanh(W*x+b)

dy.renew_cg()
probs = predict_labels(doc)def predict_labels(doc):
x = encode_doc(doc)h = layer1(x)y = layer2(h)return dy.softmax(y)scores of labels

sof tmax(⇤)
scores of labels

g 2 (W2 ⇤ + b2 )sof tmax(⇤)

g 1 (W1 ⇤ + b1 )CBOW (⇤)

CBOW (⇤)

w1 , ..., wn

w1 , ..., wn

def layer1(x):"deep averaging network"
W = dy.parameter(pW1) "neural bag of words"
b = dy.parameter(pb1)
return dy.tanh(W*x+b)
for (doc, label) in data:
def layer2(x):W = dy.parameter(pW2)b = dy.parameter(pb2)
return dy.tanh(W*x+b)

dy.renew_cg()
probs = predict_labels(doc)def predict_labels(doc):
x = encode_doc(doc)h = layer1(x)y = layer2(h)return dy.softmax(y)scores of labels

sof tmax(⇤)
scores of labels

g 2 (W2 ⇤ + b2 )sof tmax(⇤)

g 1 (W1 ⇤ + b1 )CBOW (⇤)

CBOW (⇤)

w1 , ..., wn

w1 , ..., wn

def layer1(x):"deep averaging network"
W = dy.parameter(pW1) "neural bag of words"
b = dy.parameter(pb1)
return dy.tanh(W*x+b)
for (doc, label) in data:
def layer2(x):W = dy.parameter(pW2)b = dy.parameter(pb2)
return dy.tanh(W*x+b)

dy.renew_cg()
probs = predict_labels(doc)def predict_labels(doc):
x = encode_doc(doc)h = layer1(x)y = layer2(h)return dy.softmax(y)scores of labels

sof tmax(⇤)
scores of labels

def encode_doc(doc):
sof tmax(⇤)
doc = [w2i[w] for w in doc]
embs = [E[idx] for idx in CBOWdoc](⇤)
return dy.esum(embs)
w1 , ..., wn

g 2 (W2 ⇤ + b2 )g 1 (W1 ⇤ + b1 )CBOW (⇤)
w1 , ..., wn

def layer1(x):"deep averaging network"
W = dy.parameter(pW1) "neural bag of words"
b = dy.parameter(pb1)
return dy.tanh(W*x+b)
for (doc, label) in data:
def layer2(x):W = dy.parameter(pW2)b = dy.parameter(pb2)
return dy.tanh(W*x+b)

dy.renew_cg()
probs = predict_labels(doc)def predict_labels(doc):
x = encode_doc(doc)h = layer1(x)y = layer2(h)return dy.softmax(y)scores of labels

sof tmax(⇤)
scores of labels

def encode_doc(doc):
sof tmax(⇤)
doc = [w2i[w] for w in doc]
embs = [E[idx] for idx in CBOWdoc](⇤)
return dy.esum(embs)
w1 , ..., wn

g 2 (W2 ⇤ + b2 )g 1 (W1 ⇤ + b1 )CBOW (⇤)
w1 , ..., wn

def layer1(x):"deep averaging network"
W = dy.parameter(pW1) "neural bag of words"
b = dy.parameter(pb1)
return dy.tanh(W*x+b)
for (doc, label) in data:
def layer2(x):W = dy.parameter(pW2)b = dy.parameter(pb2)
return dy.tanh(W*x+b)

dy.renew_cg()
probs = predict_labels(doc)loss = do_loss(probs,label)loss.forward()
loss.backward()
trainer.update()def predict_labels(doc):
x = encode_doc(doc)h = layer1(x)y = layer2(h)return dy.softmax(y)scores of labels

sof tmax(⇤)
scores of labels

g 2 (W2 ⇤ + b2 )sof tmax(⇤)

g 1 (W1 ⇤ + b1 )def do_loss(probs, label):
CBOW (⇤)
label = l2i[label]
return -dy.log(dy.pick(probs,label))
w1 , ..., wn"neural bag of words"

CBOW (⇤)
w1 , ..., wn"deep averaging network"for (doc, label) in data:
dy.renew_cg()
probs = predict_labels(doc)loss = do_loss(probs,label)loss.forward()
loss.backward()
trainer.update()def predict_labels(doc):
x = encode_doc(doc)h = layer1(x)y = layer2(h)return dy.softmax(y)scores of labels

sof tmax(⇤)
scores of labels

g 2 (W2 ⇤ + b2 )sof tmax(⇤)

g 1 (W1 ⇤ + b1 )CBOW (⇤)

CBOW (⇤)

w1 , ..., wn

w1 , ..., wn"neural bag of words""deep averaging network"

def classify(doc):
dy.renew_cg()
probs = predict_labels(doc)vals = probs.npvalue()
return i2l[np.argmax(vals)]

TF/IDF?
def encode_doc(doc):
doc = [w2i[w] for w in doc]
embs = [E[idx] for idx in doc]
return dy.esum(embs)

def encode_doc(doc):
weights = [tfidf(w) for w in doc]
doc = [w2i[w] for w in doc]
embs = [E[idx]*w for w,idx in zip(weights,doc)]
return dy.esum(embs)

Encapsulation with Classes
class MLP(object):def __init__(self, model, in_dim, hid_dim, out_dim, non_lin=dy.tanh):
self._W1 = model.add_parameters((hid_dim, in_dim))self._b1 = model.add_parameters(hid_dim)
self._W2 = model.add_parameters((out_dim, hid_dim))self._b2 = model.add_parameters(out_dim)
self.non_lin = non_lin
def __call__(self, in_expr):
W1 = dy.parameter(self._W1)
W2 = dy.parameter(self._W2)
b1 = dy.parameter(self._b1)
b2 = dy.parameter(self._b2)
g = self.non_lin
return W2*g(W1*in_expr + b1)+b2

x = dy.inputVector(range(10))
mlp = MLP(model, 10, 100, 2, dy.tanh)y = mlp(v)Summary•

Computation Graph•

Expressions (~ nodes in the graph)•

Parameters, LookupParameters•

Model (a collection of parameters)•

Trainers•

Create a graph for each example, thencompute loss, backdrop, update.

Outline•

Part 1•

Computation graphs and their construction•

Neural Nets in DyNet•

Recurrent neural networks•

Minibatching•

Adding new differentiable functions

Recurrent Neural Networks••

NLP is full of sequential data•

Words in sentences•

Characters in words•

Sentences in discourse•…

How do we represent an arbitrarily long history?
•

we will train neural networks to build a representation of these
arbitrarily big sequences

Recurrent Neural Networks••

NLP is full of sequential data•

Words in sentences•

Characters in words•

Sentences in discourse•…

How do we represent an arbitrarily long history?
•

we will train neural networks to build a representation of these
arbitrarily big sequences

Recurrent Neural Networks
Feed-forward NN
h = g(Vx + c)ŷ = Wh + b

ŷ

h

x

Recurrent Neural Networks
Feed-forward NN

Recurrent NN

h = g(Vx + c)

ht = g(Vxt + Uht 1 + c)ŷ = Wh + b

ŷt = Wht + b

ŷ

ŷt

h

ht

x

xt

Recurrent Neural Networks
ht = g(Vxt + Uht 1 + c)ŷt = Wht + b

How do we train the RNN’s parameters?

h0

ŷ1

ŷ2

ŷ3

ŷ4

h1

h2

h3

h4

x1

x2

x3

x4

Recurrent Neural Networks
ht = g(Vxt + Uht 1 + c)ŷt = Wht + b

h0

F

y1

y2

y3

y4

cost1

cost2

cost3

cost4

ŷ1

ŷ2

ŷ3

ŷ4

h1

h2

h3

h4

x1

x2

x3

x4

Recurrent Neural Networks
F•

The unrolled graph is a well-formed (DAG)
computation graph—we can run backprop•

Parameters are tied across time, derivatives areaggregated across all time steps•

This is historically called “backpropagation
through time” (BPTT)

Parameter Tying
ht = g(Vxt + Uht 1 + c)ŷt = Wht + b

h0

U

F

y1

y2

y3

y4

cost1

cost2

cost3

cost4

ŷ1

ŷ2

ŷ3

ŷ4

h1

h2

h3

h4

x1

x2

x3

x4

Parameter Tying
h0

ŷ1

ŷ2

ŷ3

ŷ4

h1

h2

h3

h4

x1

x2

x3

x4

U
4
X
@ht @F

@F
=
@U
@U
@h
t
t=1

What else can we do?
ht = g(Vxt + Uht 1 + c)ŷt = Wht + b

h0

F

y1

y2

y3

y4

cost1

cost2

cost3

cost4

ŷ1

ŷ2

ŷ3

ŷ4

h1

h2

h3

h4

x1

x2

x3

x4

“Read and summarize”
ht = g(Vxt + Uht 1 + c)ŷ = Wh|x| + b

Summarize a sequence into a single vector.
(For prediction, translation, etc.)

y

F
ŷ

h0

h1

h2

h3

h4

x1

x2

x3

x4

Example: Language Model

h

the
a
and
cat
dog
horse
runs
says
walkedwalks
walkingpig
Lisbonsardines…

softmaxu = Wh + b
exp uipi = P
j exp ujh 2 Rd|V | = 100, 000

Example: Language Model

h

the
a
and
cat
dog
horse
runs
says
walkedwalks
walkingpig
Lisbonsardines…

softmaxu = Wh + b
exp uipi = P
j exp ujh 2 Rd|V | = 100, 000

p(e) =p(e1 )⇥p(e2 | e1 )⇥p(e3 | e1 , e2 )⇥p(e4 | e1 , e2 , e3 )⇥histories are sequences of words…

Example: Language Modelp(tom | hsi) ⇥p(likes | hsi, tom)⇥p(beer | hsi, tom, likes)⇥p(h/si | hsi, tom, likes, beer)
⇠




⇠

beer

⇠

likes

⇠

tom

p̂1
softmaxh0

softmax

softmax

softmax

h1

h2

h3

h4

x1

x2

x3

x4




Language Model Training

⇠




⇠

beer

⇠

likes

⇠

tom

p̂1
softmaxh0

softmax

softmax

softmax

h1

h2

h3

h4

x1

x2

x3

x4




Language Model Training

cr lo
os g
s los
en s
tro /
py

F

{

tom

likes

beer




cost1

cost2

cost3

cost4

p̂1

h0

softmax

softmax

softmax

softmax

h1

h2

h3

h4

x1

x2

x3

x4




Alternative RNNs•Long short-term memories (LSTMs; Hochreiter andSchmidthuber, 1997)•

Gated recurrent units (GRUs; Cho et al., 2014)•

All follow the basic paradigm of “take input, updatestate”

Recurrent Neural Networks
in DyNet•

Based on “*Builder” class (*=SimpleRNN/LSTM)•

Add parameters to model (once):# LSTM (layers=1, input=64, hidden=128, model)
RNN = dy.LSTMBuilder(1, 64, 128, model)•

Add parameters to CG and get initial state (per sentence):s = RNN.initial_state()•

Update state and access (per input word/character):s = s.add_input(x_t)
h_t = s.output()RNNLM Example:
Parameter Initialization# Lookup parameters for word embeddings
WORDS_LOOKUP = model.add_lookup_parameters((nwords, 64))
# Word-level LSTM (layers=1, input=64, hidden=128, model)
RNN = dy.LSTMBuilder(1, 64, 128, model)# Softmax weights/biases on top of LSTM outputs
W_sm = model.add_parameters((nwords, 128))b_sm = model.add_parameters(nwords)

RNNLM Example:
Sentence Initialization# Build the language model graphdef calc_lm_loss(wids):
dy.renew_cg()# parameters -> expressions
W_exp = dy.parameter(W_sm)
b_exp = dy.parameter(b_sm)# add parameters to CG and get statef_init = RNN.initial_state()# get the word vectors for each word ID
wembs = [WORDS_LOOKUP[wid] for wid in wids]# Start the rnn by inputting "
"s = f_init.add_input(wembs[-1])…

RNNLM Example:
Loss Calculation and State Update…
# process each word ID and embedding
losses = []for wid, we in zip(wids, wembs):# calculate and save the softmax loss
score = W_exp * s.output() + b_exp
loss = dy.pickneglogsoftmax(score, wid)
losses.append(loss)# update the RNN state with the inputs = s.add_input(we)# return the sum of all losses
return dy.esum(losses)

Mini-batchingImplementation Details:
Minibatching•

Minibatching: group together multiple similar operations•

Modern hardware••

pretty fast for elementwise operations•

very fast for matrix-matrix multiplication•

has overhead for every operation (esp. GPUs)

Neural networks consist of•lots of elementwise operations•

lots of matrix-vector products

Minibatching
Single-instance RNN

ht = g(Vxt + Uht 1 + c)ŷt = Wht + b

Ht = g(VXt + UHt 1 + c)

Minibatch RNN

Ŷt = WHt + b
z

x1

}|
x1

{

x1

X1

anything wrong here?
We batch across instances,
not across time.

Minibatching Sequences•

How do we handle sequences of different lengths?
this
this

is an
example 

is another 



pad

calculate
loss

1
1

1
1

1
1

1
1

1
0

mask

sum to sentence loss

Mini-batching in Dynet•

DyNet has special minibatch operations for lookup
and loss functions, everything else automatic•

You need to:•Group sentences into a mini batch (optionally, forefficiency group sentences by length)•

Select the “t”th word in each sentence, and send
them to the lookup and loss functions

Function Changes
wid = 5
wemb = WORDS_LOOKUP[wid]loss = dy.pickneglogsoftmax(score, wid)
wids = [5, 2, 1, 3]
wemb = dy.lookup_batch(WORDS_LOOKUP, wids)
loss = dy.pickneglogsoftmax_batch(score, wids)

Implementing Functions

Standard Functions
addmv, affine_transform, average, average_cols, binary_log_loss,
block_dropout, cdiv, colwise_add, concatenate, concatenate_cols,
const_lookup, const_parameter, contract3d_1d, contract3d_1d_1d,conv1d_narrow, conv1d_wide, cube, cwise_multiply, dot_product,
dropout, erf, exp, filter1d_narrow, fold_rows, hinge, huber_distance,
input, inverse, kmax_pooling, kmh_ngram, l1_distance, lgamma,
log, log_softmax, logdet, logistic, logsumexp, lookup, max, min,nobackprop, noise, operator*, operator+, operator-, operator/,
pairwise_rank_loss, parameter, pick, pickneglogsoftmax, pickrange,
poisson_loss, pow, rectify, reshape, select_cols, select_rows,
softmax, softsign, sparsemax, sparsemax_loss, sqrt, square,squared_distance, squared_norm, sum, sum_batches, sum_cols,tanh, trace_of_product, transpose, zeroes

What if I Can’t Find my
Function?
•e.g. Geometric meany = sqrt(x_0 * x_1)•

Option 1: Connect multiple functions together•

Option 2: Implement forward and backward
functions directly→ C++ implementation w/ Python bindings

Implementing Forward•

Backend based on Eigen operationspgeom(x0 , x1 ) := x0 ⇤ x1

nodes.cc

template<class MyDevice>
void GeometricMean::forward_dev_impl(const MyDevice & dev,
const vector<const Tensor*>& xs,
Tensor& fx) const {fx.tvec().device(*dev.edevice) =(xs[0]->tvec() * xs[1]->tvec()).sqrt();}dev: which device — CPU/GPU
xs: input values
fx: output valueImplementing Backward@geom(x0 , x1 )x1=
• Calculate gradient for all args
@x0
2 ⇤ geom(x0 , x1 )nodes.cc

template<class MyDevice>
void GeometricMean::backward_dev_impl(const MyDevice & dev,
const vector<const Tensor*>& xs,
const Tensor& fx,
const Tensor& dEdf,
unsigned i,
Tensor& dEdxi) const {dEdxi.tvec().device(*dev.edevice) +=xs[i==1?0:1] * fx.inv() / 2 * dEdf;}

dev: which device, CPU/GPU dEdf: derivative of loss w.r.t f
xs: input values
i: index of input to consider
fx: output value
dEdxi: derivative of loss w.r.t. x[i]Other Functions to
Implement•

nodes.h: class definition•

nodes-common.cc: dimension check and function name•expr.h/expr.cc: interface to expressions•

dynet.pxd/dynet.pyx: Python wrappers

Gradient Checking•

Things go wrong in implementation (forgot a “2” or
a “-“)•

Luckily, we can check forward/backward
consistency automatically•

Idea: small steps (h) approximate gradient@f (x)f (x + h) f (x⇡@x2hUses Backward•h)Only Forward

Easy in DyNet: use GradCheck(cg) function

Questions/Coffee Time!