Simple and Efficient
Learning with AutomaticOperation Batching
Graham Neubig
joint work w/ Yoav Goldberg and Chris Dyerin

http://dynet.io/autobatch/https://github.com/neubig/howtocode-2017

Neural Networks w/
Complicated Structures
Words

Sentences
SVP
VP
PP

NP

AlicePhrases

gave amessage

Dynamic Decisions
a=1

a=1

a=2

to Bob

Neural Net Programming
Paradigms

What is Necessary for
Neural Network Training•

define computation•

add data•

calculate result (forward)•

calculate gradients (backward)•update parameters

Paradigm 1: Static Graphs(Tensorflow, Theano)•define•for each data point:•add data•

forward•backward•

updateAdvantages/Disadvantagesof Static Graphs••

Advantages:•

Can be optimized at definition time•

Easy to feed data to GPUs, etc., via data iterators

Disadvantages:•

Difficult to implement nets with varying structure (trees,graphs, flow control)•

Need to learn big API that implements flow control in the“graph” language

Paradigm 2:
Dynamic+Eager Evaluation(PyTorch, Chainer)•

for each data point:•

define/add data/forward•

backward•

updateAdvantages/Disadvantagesof Dynamic+Eager Evaluation••

Advantages:•

Easy to implement nets with varying structure,
API is closer to standard Python/C++•

Easy to debug because errors occur immediately

Disadvantages:•

Cannot be optimized at definition time•

Hard to serialize graphs w/o program logic,
decide device placement, etc.

Paradigm 3:
Dynamic+Lazy Evaluation (DyNet)•for each data point:•

define/add data•

forward•backward•

updateAdvantages/Disadvantagesof Dynamic+Lazy Evaluation••

Advantages:•

Easy to implement nets with varying structure,
API is closer to standard Python/C++•

Can be optimized at definition time (thispresentation!)

Disadvantages:•

Harder to debug because errors occur immediately•

Still hard to serialize graphs w/o program logic,
decide device placement, etc.

Efficiency Tricks:
Operation BatchingEfficiency Tricks:
Mini-batching•

On modern hardware 10 operations of size 1 ismuch slower than 1 operation of size 10•

Minibatching combines together smaller operations
into one big one

Minibatching

Manual Mini-batching•

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

Example Task: Sentiment
I hate this movie

I love this movie

I do n’t hate this movie

very good
good
neutralbadvery badvery good
good
neutralbadvery badvery good
good
neutralbadvery badContinuous Bag of Words(CBOW)
Ihatethismovie

lookuplookuplookuplookup+++=W+=bias

scoresBatching CBOWI
I

lovethat movie
hatethis movie

lookuplookup+lookup+lookup+

Mini-batched Code Example

Mini-batching Sequences
thisthisLoss
Calculation

is anexample 

is another 


Padding
1
1

1
1

1
1

1
1

10

Mask

Take Sum

Bi-directional LSTM
I

LSTM

hate

LSTM

thismovie

LSTM

LSTM

LSTM

LSTM

LSTM

LSTM

concatW+=biasscoresTree-structured RNN/LSTM
I

hatethismovie

RNN

RNN

RNN

W+=biasscoresAnd What About These?
WordsSentences
SVP
VP
PPNP

AlicePhrases

gave amessageDynamic Decisions
a=1

a=1

a=2

to BobAutomatic Operation
Batching

Automatic Mini-batching!

•Innovatd by TensorFlow Fold (faster than unbatched, but
implementation relatively complicated)•

DyNet Autobatch (basically effortless implementation)

Programming Paradigm
Just write a for loop!
for minibatch in training_data:
loss_values = []for x, y in minibatch:
loss_values.append(calculate_loss(x,y))
loss_sum = sum(loss_values)
loss_sum.forward()
loss_sum.backward()
trainer.update()
Batching occurs here

Under the Hood•

Each node has “profile”, same profile → batchable•

Batch and execute items with their dependencies satisfied

Challenges•

This goes in your training loop:
must be blazing fast!

•

DyNet’s C++ implementation is highly optimized•

Profiles stored as hash functions•

Minimize memory allocation overhead

Synthetic Experiments•

Fixed-length RNN → ideal case for manual batching•

How close can we get?

Real NLP Tasks•

Variably Lengthed RNN, RNN w/ character
embeddings, tree LSTM, dependency parser

Let’s Try it Out!
http://dynet.io/autobatch/https://github.com/neubig/howtocode-2017