GRU: Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation

One recurrent network reads an English phrase into a fixed-length vector and a second one writes French from it, both built from a new gated unit that is now called the GRU.

The paper trains the pair on phrase pairs from 348 million words of parallel text and adds its probability as one more score in a phrase-based translation system. By itself the RNN score adds 0.57 BLEU on the test set, and 1.34 together with a neural language model. Each hidden unit has an update gate, which sets how much of its previous value it keeps, and a reset gate, which sets how much of the previous state the new candidate value may use.

Posted in June 2014 by researchers in Montréal, Le Mans and Bremen. Within about three months the same encoder-decoder design was translating whole sentences, first with attention and then with deep LSTMs.

The paper makes two proposals and tests them on one narrow job. The first is an architecture: a recurrent network that compresses a variable-length sequence into a vector, and a second recurrent network that generates another variable-length sequence from that vector, trained together to maximize the probability of the right output. The second is the recurrent unit inside both networks, which has two learned gates and is much simpler than an LSTM. The job is English-to-French translation, but the network does not translate sentences. It scores short phrase pairs inside a standard statistical translation system, and the system uses that score as one more input when it assembles a translation.

The page follows the dependencies. It starts with how phrase-based translation worked, because the network is a component of it. Then it covers how a recurrent network assigns a probability to a sequence, the encoder-decoder built from two of them, and the training objective. The gated unit gets two sections: what the gates compute, and why they let information and gradients survive many steps. The last sections cover how the scores enter the translation system, the results, and what later work changed.

Phrase-based translation in 2014

In 2014 the strongest English-French systems were phrase-based statistical machine translation (SMT). The paper writes the source sentence as $\mathbf{e}$ (English) and a candidate translation as $\mathbf{f}$ (French). The system looks for the $\mathbf{f}$ that maximizes $p(\mathbf{f} \mid \mathbf{e})$, which Bayes' rule splits into two models:

$p(\mathbf{e} \mid \mathbf{f})$ is the translation model, which scores whether the two sentences mean the same thing, and $p(\mathbf{f})$ is the language model, which scores whether the French is fluent. In practice most systems replace the product with a weighted sum of many features, each a log-probability or a count, and treat the sum as a log-probability:

This is a log-linear model. $f_n$ is the $n$-th feature (the symbol is unrelated to the French sentence $\mathbf{f}$), and $w_n$ is its weight. $Z(\mathbf{e})$ sums the exponentiated score over every possible translation so the probabilities add to one; it depends on the weights but not on any particular candidate, so the search for the best $\mathbf{f}$ never computes it. (The paper prints $+\log Z$; see the Provenance panel.) The weights are not fitted by maximum likelihood. They are tuned with minimum error rate training (MERT), which adjusts them to maximize the BLEU score of the system's translations on a held-out development set.

BLEU compares a system's output with a human reference translation. It counts how many of the output's 1-, 2-, 3- and 4-word sequences also occur in the reference, takes the geometric mean of those four precisions, and multiplies by a penalty if the output is shorter than the reference. It is reported on a 0-100 scale. A sentence that matches the reference exactly scores 100; at the corpus level, the systems in this paper score between 30 and 35.

In a phrase-based system, the translation model is broken into phrase pairs. Before translation, a word aligner (a program that estimates which words in a sentence pair translate each other) runs over millions of sentence pairs, and every pair of aligned word sequences up to a few words long goes into a phrase table with probabilities estimated from counts. A row of that table might read "the past few days ." → "les derniers jours .", together with the conditional probabilities in both directions and a few related numbers. Each of those numbers is a feature in (9). The decoder, which in SMT means the search procedure, covers the source sentence with phrases, picks a translation for each from the table, reorders them, and keeps the highest-scoring combinations.

Count-based phrase probabilities are reliable for frequent phrases and poor for rare ones. A source phrase seen twice, once with its correct translation and once with a misaligned one, gives the wrong translation probability 0.5. The paper adds a feature that does not depend on counts: a neural network that reads the English phrase and assigns a probability to the French phrase from what the words mean. Rescoring of this kind had been done with feedforward networks; Schwenk (2012) scored phrase pairs with a network that took seven input words and produced seven output words, padding shorter phrases; a recurrent network accepts phrases of any length.

Sequence probabilities from an RNN

A recurrent neural network (RNN) reads a sequence $\mathbf{x} = (x_1, \dots, x_T)$ one symbol at a time and keeps a hidden state $\mathbf{h}$, a vector that is updated at every step from its previous value and the current symbol:

The paper writes the time index in angle brackets, $\mathbf{h}_{\langle t\rangle}$, to keep subscripts free for vector elements. $f$ is a nonlinear function with learned weights. The simplest choice is $\tanh(\mathbf{W}x_t + \mathbf{U}\mathbf{h}_{\langle t-1\rangle})$; an LSTM is a more elaborate one, and the paper's gated unit is a third. Because the same $f$ runs at every step, one set of weights processes sequences of any length.

To make the RNN a probability model over sequences, a softmax layer reads the state after each step and outputs a distribution over the next symbol. With a vocabulary of $K$ symbols and $\mathbf{w}_j$ the $j$-th row of an output matrix $\mathbf{W}$:

$x_{t,j} = 1$ means "symbol $t$ is word $j$", since each word is a one-hot vector of length $K$. Multiplying these conditionals gives the probability of the whole sequence:

Equation (3) is the chain rule of probability, exact for any distribution over sequences; the model computes every conditional from the same RNN state. For a four-word phrase plus an end-of-sequence symbol, (3) is a product of five softmax outputs, and its log is a sum of five log-probabilities. A trained model can also generate: sample a symbol from (2), feed it back as the next input, and repeat until the end-of-sequence symbol comes out.

How the RNN Encoder–Decoder works

The model computes $p(y_1, \dots, y_{T'} \mid x_1, \dots, x_T)$, the probability of a target sequence given a source sequence, where the two lengths $T$ and $T'$ may differ. It uses two RNNs.

The encoder reads the source symbols one at a time with (1). After the end-of-sequence symbol, its final state is turned into a summary vector $\mathbf{c}$ of the whole input. Appendix A gives the exact form, $\mathbf{c} = \tanh(\mathbf{V}\mathbf{h}_{\langle N\rangle})$ for a source of $N$ symbols. The encoder has no softmax; its only output is $\mathbf{c}$.

The decoder is a second RNN with its own weights. It starts from $\mathbf{h}'_{\langle 0\rangle} = \tanh(\mathbf{V}'\mathbf{c})$, and its state and its output at each step depend on the previous target word and on $\mathbf{c}$:

$g$ ends in a softmax over the target vocabulary. Feeding $\mathbf{c}$ into every step, and not only into the starting state, means the decoder does not have to carry the source information through its own recurrence: at step 5 the summary enters through the same weights as at step 1. In the experiments, $\mathbf{c}$ enters the decoder's two gates, its candidate state, and the layer before the softmax. Sutskever et al.'s Seq2Seq, posted about three months later, made the other choice: its decoder LSTM starts from the encoder's final state and never sees the source again.

The pair in Figure 1 comes from the paper's Table 2. With the experiment's sizes, each English word is a one-hot vector over 15,001 symbols (the 15,000 most frequent words plus end-of-sequence), which a $15{,}001 \times 100$ embedding matrix maps to 100 numbers. The encoder state has 1,000 numbers, and so do $\mathbf{c}$ and the decoder state. At each decoder step the output layer combines the decoder state, the previous word's embedding and $\mathbf{c}$ into 1,000 numbers, takes the maximum of each adjacent pair (a maxout layer, leaving 500), and maps those 500 to 15,001 logits for the softmax. That last map is factored through 100 dimensions, $\mathbf{G} = \mathbf{G}_l \mathbf{G}_r$ with $\mathbf{G}_l$ of size $15{,}001 \times 100$ and $\mathbf{G}_r$ of size $100 \times 500$.

Counting the weight matrices of that configuration, biases ignored: the two embedding tables and the factored output matrix hold about 1.5 million each; the encoder's recurrent matrices for the candidate and the two gates hold 3 million; the decoder has another 3 million recurrent and 3 million for the three projections of $\mathbf{c}$; and the remaining projections ($\mathbf{V}$, $\mathbf{V}'$, the input matrices and the output layer's inputs) add about 4.7 million. The total is about 18.25 million. Without the rank-100 factoring, the input matrices alone would be $15{,}001 \times 1{,}000$, 15 million on each side. For comparison, Seq2Seq's 4-layer LSTMs with 160,000- and 80,000-word vocabularies had 384 million parameters.

Training on phrase pairs

Both networks are trained together to maximize the average conditional log-likelihood of the training pairs:

$\boldsymbol{\theta}$ is every weight in the encoder and the decoder, and each $(\mathbf{x}_n, \mathbf{y}_n)$ is a source phrase with its target phrase. The log-probability of one pair is the sum over target positions of the decoder's log-softmax at the correct word, with the correct previous word fed in at each step. The whole computation, from the first source embedding to the last softmax, is differentiable, so a single backward pass sends the gradient of the target log-probability through the decoder, into $\mathbf{c}$, and back through every encoder step. No loss term constrains $\mathbf{c}$ directly; the encoder learns whatever representation makes the French predictable.

for step in range(n_steps):                 # about three days on one GPU
    batch = sample_pairs(phrase_table, 64)  # uniform over unique pairs:
                                            # corpus frequencies are ignored
    loss = -sum(log_p(x, y, P) for x, y in batch) / 64     # equation (4)
    grads = backprop(loss, P)               # every matrix in BOTH networks
    grads = clip_global_norm(grads, 1.0)    # GroundHog default, not in paper
    adadelta(P, grads, rho=0.95, eps=1e-6)

The 348 million words of parallel text produce a phrase table, and the network trains on its unique phrase pairs, each sampled with equal probability regardless of how often it occurred in the corpus. Section 3.1 gives two reasons: sampling in proportion to frequency from a table this large is expensive, and the table's own probabilities already carry the frequency information. A network trained on uniform pairs spends its capacity on which translations are plausible given the words. Its scores are therefore meant to disagree with the count-based ones where counts are unreliable.

The other settings: Adadelta with $\rho = 0.95$ and $\epsilon = 10^{-6}$, minibatches of 64 phrase pairs, weights drawn from a Gaussian with standard deviation 0.01, and recurrent matrices initialized to orthogonal matrices (the left singular vectors of a random Gaussian matrix). Training took about three days. The authors' code also clips the global gradient norm at 1.0, which the paper does not mention.

Once trained, the model can be used two ways. It can generate a target phrase for a source phrase by sampling the decoder, or it can score a given pair by computing $p_{\boldsymbol\theta}(\mathbf{y} \mid \mathbf{x})$. The translation experiments use scoring.

How the GRU works

The paper's second proposal is the function $f$ in (1). It calls it a hidden unit that adaptively remembers and forgets; Chung et al. named it the gated recurrent unit (GRU) six months later, and the name is now standard. The motivation comes from the tanh RNN: every step rewrites the whole state through a matrix product and a squashing nonlinearity, so information from many steps back is scrambled step after step. The authors report that with plain tanh units they "were not able to get meaningful result". The LSTM fixes this with a separate memory cell and three gates. The gated unit uses two gates and no separate cell.

For hidden unit $j$, with $\mathbf{x}$ the current input and $\mathbf{h}_{\langle t-1\rangle}$ the previous state, the reset gate and the update gate are

$\sigma$ is the logistic sigmoid, so each gate is a number between 0 and 1, computed fresh at every step from the input and the previous state. $[\cdot]_j$ takes the $j$-th element. The unit then computes a candidate value and mixes it with its old value:

$\phi$ is tanh in the experiments and $\odot$ is element-wise multiplication. Equation (8) is listed before (7) here because (7) uses its result. The two gates act at different points:

• The reset gate $\mathbf{r}$ acts inside the candidate. It scales the previous state element by element before the state is multiplied by the recurrent matrix $\mathbf{U}$. With $\mathbf{r}$ near 0, the candidate is computed from the current input alone, as if the sequence had just started. With $\mathbf{r}$ near 1, it is an ordinary tanh RNN step.
• The update gate $z_j$ acts on the output. It interpolates between the unit's old value and the candidate. With $z_j$ near 1 the unit copies its old value forward unchanged; with $z_j$ near 0 it takes the candidate.

A reset gate near 0 does not erase the state. The paper's phrase is that the hidden state is "forced to ignore the previous hidden state", but that applies to the candidate; whatever $z_j$ keeps of the old value passes through (7) regardless of $\mathbf{r}$.

Equation (7) with a fixed number in place of $z_j$ is a leaky-integration unit, an older device for slow-changing RNN units (Bengio et al. 2013 sampled the fixed coefficient between 0.02 and 0.2 per unit). The update gate makes the coefficient depend on the data: the unit can take in a new value on the step where something relevant arrives and hold it on the steps that follow. Because every unit has its own gates, the paper expects units to specialize: those tracking short-range structure would reset often, and those tracking long-range structure would keep their update gates near 1. The paper states this as an expectation and does not measure it.

A worked step, with the scalar weights of Figure 2 below ($W = 1.5$, $U = 1.0$). The state starts at 0, and at step 3 the input is 1.0. With $r = 1$, the candidate is $\tanh(1.5 \cdot 1.0 + 1.0 \cdot 0) = 0.905$. With $z = 0.7$, the new state is $0.7 \cdot 0 + 0.3 \cdot 0.905 = 0.272$. At step 4 the input is 0, the candidate is $\tanh(0.272) = 0.265$, and the state is $0.7 \cdot 0.272 + 0.3 \cdot 0.265 = 0.270$.

The presets show the regimes. The plain tanh RNN ($z = 0$, $r = 1$) jumps to 0.905 at the first pulse and then decays toward zero through repeated tanh, losing about a fifth of its value in the first step. "Frozen" ($z = 1$) never leaves 0: a unit that only keeps cannot take anything in. The short-term unit ($z = 0.2$, $r = 0.1$) responds to each pulse and forgets it within three steps, because with $r = 0.1$ the candidate gets only a tenth of the previous state. The long-term unit ($z = 0.9$) is stable but takes in only a tenth of each pulse. No fixed setting both writes the pulse and holds it. "z follows input" does, with $z_t = \sigma(4 - 8|x_t|)$ standing in for the learned (6): 0.018 on the pulse step, 0.982 on empty steps. The state reaches 0.889 at step 3, is still 0.870 at step 9, and is overwritten by the next pulse at step 10.

Why the gates help over long spans

Training needs gradients to cross the same distance as the information. The gradient of the loss at a late step with respect to an early state is a product of one Jacobian per step in between (the chain rule). For a tanh RNN, $\mathbf{h}_{\langle t\rangle} = \tanh(\mathbf{W}\mathbf{x}_t + \mathbf{U}\mathbf{h}_{\langle t-1\rangle})$, each factor is

and a product of 50 such factors shrinks toward zero or grows without bound unless $\mathbf{U}$ is tuned to keep it near norm 1. Differentiating (7) instead, with the candidate's derivative written as $\partial\tilde{\mathbf{h}}$, gives a sum of three terms:

The first term is a direct path that bypasses $\mathbf{U}$ and the tanh. For a unit whose update gate is near 1 and saturated (so that the sigmoid's slope, and with it the middle term, is near 0), the Jacobian in that coordinate is close to 1, and the gradient passes back through that step almost unchanged. The derivation is ours; the paper says only that the update gate "helps the RNN to remember long-term information", and the LSTM's cell has the same kind of additive path.

At the default $u = 1$, $z = 0.9$, the tanh RNN's derivative after 50 steps is about $2 \times 10^{-20}$, below the plot's floor; the gated unit's is 0.22. At $z = 0.5$ the gated unit's falls to about $5 \times 10^{-6}$. A trained GRU does not hold $z$ fixed, so in practice the long path exists only for units whose gates are near 1 over the stretch that matters. With $u = 3$ and $z = 0.9$ the gated derivative grows to about 2.8 by step 50, so gating does not rule out exploding gradients, which is one reason for the gradient clipping in the code.

Scoring the phrase table

After training, the RNN Encoder–Decoder computes $\log p(\mathbf{f} \mid \mathbf{e})$ for every pair in the phrase table and stores the values as an extra column. Translation then proceeds as before: the new column is one more feature $f_n$ in (9) with its own weight $w_n$, MERT tunes all the weights on the development set, and the decoder searches with the new scores. Computing the column takes one pass over the table, and the decoder's search procedure is unchanged.

Figure 4 shows the effect on one source phrase, "the past few days .", which Table 2 lists among the long, rare phrases. Table 2 gives the three target phrases the translation model ranks highest and the three the RNN ranks highest. The translation model's top choice, "le petit texte ." ("the small text ."), is wrong, an artifact of noisy alignments that counts cannot correct for a rare phrase. The RNN's top three, "ces derniers jours .", "les derniers jours ." and "cours des derniers jours .", are all correct. The paper prints no scores, so the figure uses invented log-probabilities that reproduce only those two rankings.

With these numbers the top candidate changes three times as $w$ rises: "le petit texte ." up to about 0.05, then "cours des tout derniers jours .", then "les tout derniers jours ." from about 0.13, and "ces derniers jours ." from about 0.24 onward. In the real system this choice is made jointly with the language model, reordering and the other features, over whole sentences, and MERT picks one weight for the RNN column across the entire development set, not per phrase.

The paper also observes that the RNN prefers shorter target phrases. The paper gives no reason. A probable cause is that the probability of a phrase is a product of one factor per word, each below 1, so a longer phrase pays for every extra word. The standard word-count feature of Moses, the phrase-based system used as the baseline, can offset a length bias at the sentence level.

Replacing the phrase table with the network, generating candidates instead of rescoring them, is possible but would mean sampling a list of target phrases for every source phrase, which the paper calls expensive. Table 3 shows what sampling produces: for "for the first time", 24 of 50 samples were "pour la première fois"; for "the past few days .", "quelques jours ." and "les derniers jours ." appeared 5 times each. Not every sample is right: for "parts of the world ." the most common sample, 11 of 50, was "arts du monde .".

What the experiments show

The task is WMT'14 English-to-French. The parallel corpora total about 1.36 billion French words (Europarl 61M, news commentary 5.5M, UN 421M, and two web crawls of 90M and 780M), and a data-selection method picked the parallel text used to train the network, 348M words from an 850M-word subset (the paper does not say which corpora make up the 850M), and cut the language-model data to 418M of over 2 billion. The development set (newstest2012 and 2013) was used for data selection and MERT; the test set is newstest2014. Each has over 70,000 words and one reference translation. The baseline is Moses with default settings.

The second neural network in the table is a continuous-space language model (CSLM), Schwenk's feedforward network that predicts the next French word from the previous six. Each word is embedded in 512 dimensions, the six are concatenated into 3,072 numbers, and two rectifier layers of 1,536 and 1,024 units feed a softmax; it reached a perplexity of 45.80. It is queried during the decoder's search on the word sequences of each partial translation, while the RNN's scores are computed once per phrase pair beforehand. The word penalty (WP) is a feature that counts the words unknown to the neural networks.

The RNN's phrase scores alone add 0.57 BLEU on the test set; with the CSLM the gain is 1.34. On a 33-point baseline that is a 4% relative improvement, from features that leave the decoder unchanged. The paper gives no significance test. It concludes that the CSLM and the RNN contribute in different ways, which is plausible since one scores fluency of the French and the other the match between phrases, but the v3 table has no CSLM-only row to measure the CSLM's share. The first arXiv version, on a smaller system, did: there the CSLM alone added 0.25 test BLEU, the RNN alone 0.63, and both together 1.31, more than the sum.

The word penalty addresses a bias of the 15,000-word shortlist. Every word outside it is mapped to a single [UNK] token before the networks score it, so the probability the model gives an unknown word is really the probability of the whole out-of-shortlist set:

Any single rare word is credited with the probability of all of them together, so translations full of rare words are overrated. Counting the unknown words as a feature lets MERT push against that. It helped on the development set (31.48 to 31.50) and not on the test set (34.64 to 34.54).

Section 4.3 compares the phrase scores pair by pair. Plotted against the translation model's log-probabilities (Figure 3 in the paper), many pairs get similar scores from both models and about as many get very different ones, which the authors attribute to training on unique pairs. In most of Table 2's examples, frequent and rare, the RNN's top choices are closer to literal translations than the translation model's, and shorter.

Section 4.4 visualizes the learned representations with Barnes-Hut-SNE, a method that places high-dimensional vectors on a 2D plot so that nearby vectors stay nearby. The word embeddings cluster by meaning, as in earlier neural language models. The summary vectors $\mathbf{c}$ of phrases with four or more words cluster both by meaning (phrases naming countries or regions) and by syntax (phrases with the same structure), which is the "phrase representations" of the title. The paper shows these plots and does not evaluate $\mathbf{c}$ on any other task.

Limits and what followed

The model was evaluated only as a feature for phrases of a few words, where a 1,000-number summary is ample. In September 2014, Cho et al. used the same encoder-decoder to translate whole sentences and found that quality falls quickly as sentences get longer and contain more unknown words: everything the decoder knows about a 40-word sentence has to pass through $\mathbf{c}$. Two days before that analysis appeared, Bahdanau, Cho and Bengio had posted the fix. Their encoder keeps every state, and at each output word the decoder computes a weighted average of all of them, with weights computed from the decoder's state. That is attention, and the recurrent unit in both of its networks is this paper's gated unit. Nine days after that, Sutskever, Vinyals and Le's Seq2Seq showed that a large enough model with deep LSTMs and a reversed source could translate whole sentences without attention, reaching 34.81 BLEU with an ensemble on the same test set.

The gated unit outlived the translation setup. Chung et al. compared it with the LSTM in December 2014, named it the GRU, and found the two comparable, both well ahead of the plain tanh unit. It became a standard layer in deep learning libraries. The Transformer (2017) later replaced recurrence in most translation systems and kept the encoder-decoder layout: an encoder over the source, and a decoder that generates the target one token at a time while reading the encoder's output.

Implementation notes

The listing below is the gated unit as the paper defines it, plus the decoder variant with the summary vector. Every matrix multiplies a vector of known size: $\mathbf{W}$, $\mathbf{W}_z$, $\mathbf{W}_r$ are $1000 \times 100$; $\mathbf{U}$, $\mathbf{U}_z$, $\mathbf{U}_r$ and the three $\mathbf{C}$ matrices are $1000 \times 1000$.

import numpy as np

def sigmoid(a):
    return 1.0 / (1.0 + np.exp(-a))

def gru_step(x, h_prev, P):
    """Encoder step, equations (5)-(8). x: (100,) word embedding.
    h_prev: (1000,). Biases omitted, as in the paper."""
    r = sigmoid(P["W_r"] @ x + P["U_r"] @ h_prev)          # (5) reset gate
    z = sigmoid(P["W_z"] @ x + P["U_z"] @ h_prev)          # (6) update gate
    h_cand = np.tanh(P["W"] @ x + P["U"] @ (r * h_prev))   # (8) candidate
    return z * h_prev + (1.0 - z) * h_cand                 # (7) mix

def gru_step_ctx(y, h_prev, c, P):
    """Decoder step: the summary c (1000,) enters both gates and the
    candidate at every step. Reset placement follows the GroundHog code."""
    r = sigmoid(P["W_r"] @ y + P["U_r"] @ h_prev + P["C_r"] @ c)
    z = sigmoid(P["W_z"] @ y + P["U_z"] @ h_prev + P["C_z"] @ c)
    h_cand = np.tanh(P["W"] @ y + P["U"] @ (r * h_prev) + P["C"] @ c)
    return z * h_prev + (1.0 - z) * h_cand

Two details differ between sources. In the reset gate's placement, the paper's equation (8) multiplies the old state by $\mathbf{r}$ before the matrix $\mathbf{U}$, as in the listing. The first arXiv version, Appendix A's decoder, PyTorch's nn.GRU and the default Keras layer apply it after: $\mathbf{r} \odot (\mathbf{U}\mathbf{h})$. The two are different functions, and weights trained with one do not transfer to the other, but both train well; the after-form lets all three recurrent products be computed as one matrix multiplication before the gates are known, which is why cuDNN uses it. The other is which term the update gate multiplies. The paper puts $z$ on the old state; the GroundHog code and Chung et al. put it on the candidate. These are the same model with $z$ relabeled as $1 - z$.

The scoring function runs the encoder over the source, builds $\mathbf{c}$, and adds up the decoder's log-softmax at each correct target word:

def log_p(src_ids, tgt_ids, P):
    """log p(y | x) for one phrase pair. Ids index a 15,001-symbol
    vocabulary (15,000 words + end-of-sequence); both lists end with eos."""
    h = np.zeros(1000)                                  # h<0> = 0
    for i in src_ids:
        h = gru_step(P["E_src"][i], h, P["enc"])        # E_src: (15001, 100)
    c = np.tanh(P["V"] @ h)                             # summary c, (1000,)
    s = np.tanh(P["V_dec"] @ c)                         # decoder start h'<0>
    y_prev = np.zeros(100)                              # e(y_0) = 0
    total = 0.0
    for j in tgt_ids:
        s = gru_step_ctx(y_prev, s, c, P["dec"])
        pre = P["O_h"] @ s + P["O_y"] @ y_prev + P["O_c"] @ c   # (1000,)
        m = pre.reshape(500, 2).max(axis=1)             # maxout: (500,)
        logits = P["G_l"] @ (P["G_r"] @ m)              # (15001,) via rank 100
        total += logits[j] - np.logaddexp.reduce(logits)  # log softmax
        y_prev = P["E_tgt"][j]                          # the TRUE word is fed back
    return total

The output layer follows Appendix A and the code: a maxout over pairs of 1,000 pre-activations, then the rank-100 factored softmax. In the code the previous word enters the output layer through its 100-number embedding; the appendix writes the one-hot vector. Because the true previous word is fed back during scoring and training, the same function computes the loss for (4); generating a phrase instead means sampling $j$ from the softmax at each step and feeding the sampled word back.