7

Neural MT 1: Neural Encoder-Decoder Models

From Section 3 to Section 6, we focused on the language modeling problem of calculating
the probability P (E) of a sequence E. In this section, we return to the statistical machinetranslation problem (mentioned in Section 2) of modeling the probability P (E|F ) of theoutput E given the input F .

7.1

Encoder-decoder Models

The first model that we will cover is called an encoder-decoder model [3, 7, 9, 19]. The basic
idea of the model is relatively simple: we have an RNN language model, but before starting
calculation of the probabilities of E, we first calculate the initial state of the language modelusing another RNN over the source sentence F . The name “encoder-decoder” comes fromthe idea that the first neural network running over F “encodes” its information as a vectorof real-valued numbers (the hidden state), then the second neural network used to predict E“decodes” this information into the target sentence.
Encoder0

Decoder…

RNN(f)

h|F|

p(e)1

p(e)1

p(e)|E|

softmax(e)softmax(e)softmax(e)RNN(e)

RNN(e)…

RNN(f)

RNN(f)

RNN(e)

lookup(f)lookup(f)lookup(f)lookup(e)lookup(e)lookup(e)

f1

f2

f|F|

e0

e1

e|E|-1Figure 21: A computation graph of the encoder-decoder model.
If the encoder is expressed as RNN(f ) (·), the decoder is expressed as RNN(e) (·), and wehave a softmax that takes RNN(e) ’s hidden state at time step t and turns it into a probability,
then our model is expressed as follows (also shown in Figure 21):
(f )

mt

(f )

= M·,ft((f )(f )RNN(f ) (mt , ht 1 )
(f )
ht =
0
(e)

mt

(e)

= M·,et 1((e)(e)
RNN(e) (mt , ht 1 )
(e)
ht =
(f )
h|F |
(e)

pt

t 1,
otherwise.

(e)= softmax(Whs ht + bs )
(f )

t

1,

otherwise.
(62)

In the first two lines, we look up the embedding mt and calculate the encoder hidden state
(f )
(f )
ht for the tth word in the source sequence F . We start with an empty vector h0 = 0, and
45

(f )

by h|F | , the encoder has seen all the words in the source sentence. Thus, this hidden stateshould theoretically be able to encode all of the information in the source sentence.
In the decoder phase, we predict the probability of word et at each time step. First, we(e)similarly look up mt , but this time use the previous word et 1 , as we must condition theprobability of et on the previous word, not on itself. Then, we run the decoder to calculate(e)(e)
ht . This is very similar to the encoder step, with the important di↵erence that h0 is set(f )to the final state of the encoder h|F | , allowing us to condition on F . Finally, we calculate the
(e)

(e)

probability pt by using a softmax on the hidden state ht .
While this model is quite simple (only 5 lines of equations), it gives us a straightforward
and powerful way to model P (E|F ). In fact, [19] have shown that a model that follows
this basic pattern is able to perform translation with similar accuracy to heavily engineered
systems specialized to the machine translation task (although it requires a few tricks overthe simple encoder-decoder that we’ll discuss in later sections: beam search (Section 7.2), adi↵erent encoder (Section 7.3), and ensembling (Section 18)).

7.2

Generating Output

However, at this point, we have only mentioned how to create a probability model P (E|F )and haven’t yet covered how to actually generate translations from it, which we will now coverin the next section. In general, when we generate output we can do so according to several
criteria:
Random Sampling: Randomly select an output E from the probability distribution P (E|F ).
This is usually denoted Ê ⇠ P (E|F ).
1-best Search: Find the E that maximizes P (E|F ), denoted Ê = argmaxP (E|F ).
En-best Search: Find the n outputs with the highest probabilities according to P (E|F ).
Which of these methods we will choose will depend on our application, so we will discuss someuse cases.
7.2.1

Random Sampling and Greedy SearchFirst, random sampling is useful in cases where we may want to get a variety of outputs fora particular input. One example of a situation where this is useful would be in a sequenceto-sequence model for a dialog system, where we would prefer the system to not always givethe same response to a particular user input to prevent monotony. Luckily, in models like theencoder-decoder above, it is simple to exactly generate samples from the distribution P (E|F )using a method called ancestral sampling. Ancestral sampling works by sampling variablevalues one at a time, gradually conditioning on more context, so at time step t, we will
sample a word from the distribution P (et |êt1 1 ). In the encoder-decoder model, this means we
simply have to calculate pt according to the previously sampled inputs, leading to the simple
generation algorithm in Algorithm 3.
One thing to note is that sometimes we also want to know the probability of the sentencethat we sampled. For example, given a sentence Ê generated by the model, we might want to46

know how certain the model is in its prediction. During the sampling process, we can calcuQ|Ê|
late P (Ê|F ) = t P (êt |F, Ê1t 1 ) incrementally by stepping along and multiplying together
the probabilities of each sampled word. However, as we remember from the discussion ofprobability vs. log probability in Section 3.3, using probabilities as-is can result in very small
numbers that cause numerical precision problems on computers. Thus, when calculating thefull-sentence probability it is more common to instead add together log probabilities for each
word, which avoids this problem.
Algorithm 3 Generating random samples from a neural encoder-decoder
1: procedure Sample
2:
for t from 1 to |F | do
(f )
(f )
3:
Calculate mt and ht
4:
end for5:
Set ê0 =“hsi” and t
06:while êt 6=“h/si” do
7:
t
t+1
(e)
(e)
(e)
8:
Calculate mt , ht , and pt from êt 1(e)
9:
Sample êt according to pt
10:
end while
11: end procedure
Next, let’s consider the problem of generating a 1-best result. This variety of generation
is useful in machine translation, and most other applications where we simply want to output
the translation that the model thought was best. The simplest way of doing so is greedy
search, in which we simply calculate pt at every time step, select the word that gives us
the highest probability, and use it as the next word in our sequence. In other words, thisalgorithm is exactly the same as Algorithm 3, with the exception that on Line 9, instead of(e)(e)
sampling êt randomly according to pt , we instead choose the max: êt = argmaxpt,i .
iInterestingly, while ancestral sampling exactly samples outputs from the distribution according to P (E|F ), greedy search is not guaranteed to find the translation with the highest
probability. An example of a case in which this is true can be found in the graph in Figure 22, which is an example of search graph with a vocabulary of {a, b, h/si}.25 As an
exercise, I encourage readers to find the true 1-best (or n-best) sentence according to theprobability P (E|F ) and the probability of the sentence found according to greedy search andconfirm that these are di↵erent.
7.2.2

Beam Search

One way to solve this problem is through the use of beam search. Beam search is similar
to greedy search, but instead of considering only the one best hypothesis, we consider b best
hypotheses at each time step, where b is the “width” of the beam. An example of beam searchwhere b = 2 is shown in Figure 23 (note that we are using log probabilities here because they
are more conducive to comparing hypotheses over the entire sentence, as mentioned before).
In reality, we will never have a probability of exactly P (et = h/si|F, et1 1 ) = 1.0, but for illustrative
purposes, we show this here.
2547

e0 P(e1|F)

e1

P(e2|F,e1)e2 P(e3|F,e1,e2) e3
“a”

0.15
0.8




0.05

“a”

0.35

0.4

0.4

“b”

“b”

0.1




1.0








“a”

0.5

0.25

1.0

“b”

1.0
1.0









Figure 22: A search graph where greedy search fails.

log P(e1|F)

log P(e2|F,e1) log P(e3|F,e1,e2)
-2.95
“a”
X

-1.90
-1.27
-0.22 “b”
-1.05
-1.05



-0.92
-1.39

“a”

-0.92
“b”

-1.39

X

-3.00

0

-1.27



-4.05

X
-0.92
“a”
-0.69 X




-1.84
-1.61
“b”




-2.30

0

-1.61



-3.22

X




Figure 23: An example of beam search with b = 2. Numbers next to arrows are log probabilities for a single word log P (et |F, et1 1 ), while numbers above nodes are log probabilities forthe entire hypothesis up until this point.

48

In the first time step, we expand hypotheses for e1 corresponding to all of the three words inthe vocabulary, then keep the top two (“b” and “a”) and delete the remaining one (“h/si”).
In the second time step, we expand hypotheses for e2 corresponding to the continuation of thefirst hypotheses for all words in the vocabulary, temporarily creating b ⇤ |V | active hypotheses.
These active hypotheses are also pruned down to the b active hypotheses (“a b” and “b b”).
This process of calculating scores for b ⇤ |V | continuations of active hypotheses, then pruningback down to the top b, is continued until the end of the sentence.
One thing to be careful about when generating sentences using models, such as neural
Q|E|machine translation, where P (E|F ) = t P (et |F, et1 1 ) is that they tend to prefer shorter
sentences. This is because every time we add another word, we multiply in another probability,
reducing the probability of the whole sentence. As we increase the beam size, the searchalgorithm gets better at finding these short sentences, and as a result, beam search with alarger beam size often has a significant length bias towards these shorter sentences.
There have been several attempts to fix this length bias problem. For example, it is possible
to put a prior probability on the length of the sentence given the length of the previous sentence
P (|E|||F |), and multiply this with the standard sentence probability P (E|F ) at decoding time[6]:Ê = argmax log P (|E|||F |) + log P (E|F ).
(63)
EThis prior probability can be estimated from data, and [6] simply estimate this using a
multinomial distribution learned on the training data:
P (|E|||F |) =c(|E|, |F |).
c(|F |)(64)

A more heuristic but still widely used approach normalizes the log probability by the lengthof the target sentence, e↵ectively searching for the sentence that has the highest average log
probability per word [2]:Ê = argmax log P (E|F )/|E|.
(65)
E

7.3

Other Ways of Encoding Sequences

In Section 7.1, we described a model that works by encoding sequences linearly, one word at
a time from left to right. However, this may not be the most natural or e↵ective way to turnthe sentence F into a vector h. In this section, we’ll discuss a number of di↵erent ways toperform encoding that have been reported to be e↵ective in the literature.
Reverse and Bidirectional Encoders: First, [19] have proposed a reverse encoder.
In this method, we simply run a standard linear encoder over F , but instead of doing so fromleft to right, we do so from right to left.
(
(f )
(f )
RNN(f ) (mt , h t+1 ) t  |F |,
(f )
ht =
(66)
0
otherwise.
The motivation behind this method is that for pairs of languages with similar ordering (suchas English-French, which the authors experimented on), the words at the beginning of F will
generally correspond to words at the beginning of E. Assuming the extreme case that words
with identical indices correspond to each-other (e.g. f1 corresponds to e1 , f2 to e2 , etc.), the49(a) Dependency Distances in Forward Encoder
|F|
|F|
|F|

0

enc

enc

f1

f2

…

e1

e2

enc

dec

dec

f|F|

e0

e1

e|E|

…

enc
e|E|-1(b) Dependency Distances in Reverse Encoder
3|F|+|E|-1
0

enc

enc

f|F|

f|F|-1

…

1

e1

e2

enc

dec

dec

f1

e0

e1

e|E|

…

enc
e|E|-1Figure 24: The distances between words with the same index in the forward and reverse
decoders.
distance between corresponding words in the linear encoding and decoding will be |F |, asshown in Figure 24(a). Remembering the vanishing gradient problem from Section 6.3, thismeans that the RNN has to propagate the information across |F | time steps before making a
prediction, a difficult feat. At the beginning of training, even RNN variants such as LSTMs
have trouble, as they have to essentially “guess” what part of the information encoded in theirhidden state is being used without any prior bias.
Reversing the encoder helps solve this problem by reducing the length of dependencies fora subset of the words in the sentence, specifically the ones at the beginning of the sentences.
As shown in Figure 24(b), the length of the dependency for f1 and e1 is 1, and subsequentpairs of ft and et have a distance of 2t 1. During learning, the model can “latch on” to theseshort-distance dependencies and use them as a way to bootstrap the model training, after
which it becomes possible to gradually learn the longer dependencies for the words at the endof the sentence. In [19], this proved critical to learn e↵ective models in the encoder-decoder
framework.
However, this approach of reversing the encoder relies on the strong assumption that theorder of words in the input and output sequences are very similar, or at least that the words
at the beginning of sentences are the same. This is true for languages like English and French,
which share the same “subject-verb-object (SVO)” word ordering, but may not be true formore typologically distinct languages. One type of encoder that is slightly more robust tothese di↵erences is the bi-directional encoder [1]. In this method, we use two di↵erent
encoders: one traveling forward and one traveling backward over the input sentence( !
(f ) !(f )!(f )RNN(f ) (mt , h t+ ) t 1,
ht =
(67)
0
otherwise.
(
(f )
(f )
RNN(f ) (mt , h t+1 ) t  |F |,
(f )
ht =
(68)
0
otherwise.
(e)which are then combined into the initial vector h0 for the decoder RNN. This combination50

(a) Convolutional Neural Net(b) Tree-structured Nethh1 h2 h3 … h|F|-2

filt filt filt

pool

h
comp
comp

filt

comp
comp

…
comp

m1 m2 m3 m4 m5 … m|F|
m1 m2 m3 m4 m5 … m|F|

Figure 25: Examples of convolutional and tree-structured networks.
!
can be done by simply concatenating the two final vectors h |F | and h 1 . However, this also
requires that the size of the vectors for the decoder RNN be exactly equal to the combined
size of the two encoder RNNs. As a more flexible alternative, we can add an additionalparameterized hidden layer between the encoder and decoder states, which allows us to convert
the bidirectional encoder states into an appropriately-sized state for the decoder:!
(e)h0 = tanh(W!
h + W f e h 1 + be ).
(69)
f e |F |Convolutional Neural Networks: In addition, there are also methods for decodingthat move beyond a simple linear view of the input sentence. For example, convolutional
neural networks (CNNs; [8, 13], Figure 25(a)) are a variety of neural net that combines
together information from spatially or temporally local segments. They are most widely
applied to image processing but have also been used for speech processing (as “time-delay
neural networks” [22]), as well as the processing of textual sequences. While there are manyvarieties of CNN-based models of text (e.g. [11, 14, 10]), here we will show an example from[12]. This model has n filters with a width w that are passed incrementally over w-wordsegments of the input. Specifically, given an embedding matrix M of width |F |, we generatea hidden layer matrix H of width |F | w + 1, where each column of the matrix is equal toht = W concat(mt , mt+1 , . . . , mt+w 1 )(70)

where W 2 Rn⇥w|m| is a matrix where the ith row represents the parameters of filter i thatwill be multiplied by the embeddings of w consecutive words. If w = 3, we can interpret thisas h1 extracting a vector of features for f13 , h2 as extracting a vector of features for f24 , etc.
until the end of the sentence.
Finally, we perform a pooling operation that converts this matrix H (which varies inwidth according to the sentence length) into a single vector h (which is fixed-size and canthus be used in down-stream processing). Examples of pooling operations include average,
max, and k-max [11].
Compared to RNNs and their variants, CNNs have several advantages and disadvantages:• On the positive side, CNNs provide a relatively simple way to detect features of shortword sequences in sentence text and accumulate them across the entire sentence.
51

S
VP
NP

NP
NP'

DET JJNN

the red cat

NP'
VBD

DET JJ

NN

chased the little bird

Figure 26: An example of a syntax tree for a sentence showing the sentence structure andphrase types (DET=“determiner”, JJ=“adjective”, NN=“noun”, VBD=“past tense verb”,
NP=“noun phrase”, NP’=“part of a noun phrase”, VP=“verb phrase”, S=“sentence”).
• Also on the positive side, CNNs do not su↵er as heavily from the vanishing gradientproblem, as they do not need to propagate gradients across multiple time steps.
• On the negative side, CNNs are not quite as expressive and are a less natural way of
expressing complicated patterns that move beyond their filter width.
In general, CNNs have been found to be quite e↵ective for text classification, where it is more
important to pick out the most indicative features of the text and there is less of an emphasison getting an overall view of the content [12]. There have also been some positive results
reported using specific varieties of CNNs for sequence-to-sequence modeling [10].
Tree-structured Networks: Finally, one other popular form of encoder that is widelyused in a number of tasks are tree-structured networks ([16, 18], Figure 25(b)). The basic
idea behind these networks is that the way to combine the information from each particularword is guided by some sort of structure, usually the syntactic structure of the sentence, an
example of which is shown in Figure 26. The reason why this is intuitively useful is because
each syntactic phrase usually also corresponds to a coherent semantic unit. Thus, performing
the calculation and manipulation of vectors over these coherent units will be more appropriatecompared to using random substrings of words, like those used by CNNs.
For example, let’s say we have the phrase “the red cat chased the little bird” as shownin the figure. In this case, following a syntactic tree would ensure that we calculate vectors
for coherent units that correspond to a grammatical phrase such as “chased” and “the littlebird”, and combine these phrases together one by one to obtain the meaning of larger coherent phrase such as “chased the little bird”. By doing so, we can take advantage of thefact that language is compositional, with the meaning of a more complex phrase resulting
from regular combinations and transformation of smaller constituent phrases [20]. By taking
this linguistically motivated and intuitive view of the sentence, we hope will help the neuralnetworks learn more generalizable functions from limited training data.
Perhaps the most simple type of tree-structured network is the recursive neural network proposed by [18]. This network has very strong parallels to standard RNNs, but insteadof calculating the hidden state ht at time t from the previous hidden state ht 1 as follows:
ht = tanh(Wxh xt + Whh ht 1 + bh ),

52

(71)

we instead calculate the hidden state of the parent node hp from the hidden states of the left
and right children, hl and hr respectively:
hp = tanh(Wxp xt + Wlp hl + Wrp hr + bp ).

(72)

Thus, the representation for each node in the tree can be calculated in a bottom-up fashion.
Like standard RNNs, these recursive networks su↵er from the vanishing gradient problem.
To fix this problem there is an adaptation of LSTMs to tree-structured networks, fittingly
called tree LSTMs [21], which fixes this vanishing gradient problem. There are also a wide
variety of other kinds of tree-structured composition functions that interested readers can
explore [17, 4, 5]. Also of interest is the study by [15], which examines the various tasks inwhich tree structures are necessary or unnecessary for NLP.

7.4

ExerciseIn the exercise for this chapter, we will create an encoder-decoder translation model and makeit possible to generate translations.
Writing the program will entail:• Extend your RNN language model code to first read in a source sentence to calculate
the initial hidden state.
• On the training set, write code to calculate the loss function and perform training.
• On the development set, generate translations using greedy search. Look at them to see
if they look good or not. We will discuss how to evaluate them automatically next time.
Potential improvements to the model include: Implementing beam search. Implementing
an alternative encoder.

References[1] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly
learning to align and translate. In Proceedings of the International Conference on Learning Representations (ICLR), 2015.
[2] Kyunghyun Cho, Bart van Merrienboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder–decoder approaches. In Proceedings of the Workshop
on Syntax and Structure in Statistical Translation, pages 103–111, 2014.
[3] Lonnie Chrisman. Learning recursive distributed representations for holistic computation. Connection Science, 3(4):345–366, 1991.
[4] Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, and Noah A. Smith. Transitionbased dependency parsing with stack long short-term memory. In Proceedings of the 53rd Annual
Meeting of the Association for Computational Linguistics (ACL), pages 334–343, 2015.
[5] Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith. Recurrent neural network grammars. In Proceedings of the 2016 Conference of the North American Chapter of the
Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), pages
199–209, 2016.

53

[6] Akiko Eriguchi, Kazuma Hashimoto, and Yoshimasa Tsuruoka. Tree-to-sequence attentional neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (ACL), pages 823–833, 2016.
[7] Mikel L Forcada and Ramón P Ñeco. Recursive hetero-associative memories for translation. In
International Work-Conference on Artificial Neural Networks, pages 453–462. Springer, 1997.
[8] Kunihiko Fukushima. Neocognitron: A hierarchical neural network capable of visual patternrecognition. Neural networks, 1(2):119–130, 1988.
[9] Nal Kalchbrenner and Phil Blunsom. Recurrent continuous translation models. In Proceedingsof the 2013 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages
1700–1709, 2013.
[10] Nal Kalchbrenner, Lasse Espeholt, Karen Simonyan, Aaron van den Oord, Alex Graves, andKoray Kavukcuoglu. Neural machine translation in linear time. arXiv preprint arXiv:1610.10099,
2016.
[11] Nal Kalchbrenner, Edward Grefenstette, and Phil Blunsom. A convolutional neural network formodelling sentences. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (ACL), pages 655–665, 2014.
[12] Yoon Kim. Convolutional neural networks for sentence classification. In Proceedings of the 2014
Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1746–1751,
2014.
[13] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Ha↵ner. Gradient-based learning applied
to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.
[14] Tao Lei, Regina Barzilay, and Tommi Jaakkola. Molding cnns for text: non-linear, non-consecutive
convolutions. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language
Processing (EMNLP), pages 1565–1575, 2015.
[15] Jiwei Li, Thang Luong, Dan Jurafsky, and Eduard Hovy. When are tree structures necessary fordeep learning of representations? pages 2304–2314, 2015.
[16] Jordan B Pollack. Recursive distributed representations. Artificial Intelligence, 46(1):77–105,
1990.
[17] Richard Socher, John Bauer, Christopher D. Manning, and Ng Andrew Y. Parsing with compositional vector grammars. In Proceedings of the 51st Annual Meeting of the Association for
Computational Linguistics (ACL), pages 455–465, 2013.
[18] Richard Socher, Cli↵ C Lin, Chris Manning, and Andrew Y Ng. Parsing natural scenes andnatural language with recursive neural networks. pages 129–136, 2011.
[19] Ilya Sutskever, Oriol Vinyals, and Quoc VV Le. Sequence to sequence learning with neuralnetworks. In Proceedings of the 28th Annual Conference on Neural Information Processing Systems(NIPS), pages 3104–3112, 2014.
[20] Zoltán Gendler Szabó. Compositionality. Stanford encyclopedia of philosophy, 2010.
[21] Kai Sheng Tai, Richard Socher, and Christopher D. Manning. Improved semantic representations
from tree-structured long short-term memory networks. In Proceedings of the 53rd Annual Meetingof the Association for Computational Linguistics (ACL), 2015.
[22] Alex Waibel, Toshiyuki Hanazawa, Geo↵rey Hinton, Kiyohiro Shikano, and Kevin J Lang.
Phoneme recognition using time-delay neural networks. 37(3):328–339, 1989.

54