Sequence Models and Recurrent Neural Networks

Definition A recurrent neural network (RNN) reads a sequence of input vectors $\mathbf{x}_1, \dots, \mathbf{x}_T$ in $\mathbb{R}^d$ in order. Starting from an initial hidden state $\mathbf{h}_0$ in $\mathbb{R}^{d_h}$, usually the zero vector, the simple recurrent cell computes for $t = 1, \dots, T$

with $W_x$ of shape $d_h \times d$, $W_h$ of shape $d_h \times d_h$, $\mathbf{b}$ in $\mathbb{R}^{d_h}$, and tanh applied to each entry. The hidden state $\mathbf{h}_t$ depends only on $\mathbf{h}_0$, the parameters and the inputs $\mathbf{x}_1, \dots, \mathbf{x}_t$. An output layer reads it, for example $K$ next-symbol scores $\mathbf{z}_t = W_y \mathbf{h}_t + \mathbf{b}_y$ with $W_y$ of shape $K \times d_h$, followed by a softmax. The same parameters are used at every step, so their number, $d_h(d + d_h + 1)$ for the cell, does not depend on $T$, and one network handles sequences of any length. A whole sequence, such as one machine session, is one example, and its steps are dependent parts of that example, not separate independent examples.

Definition Backpropagation through time (BPTT) computes the gradient of a sequence loss by unrolling the recurrence into one computation graph, with one copy of the cell per step, and applying the chain rule backward from the last step to the first. A shared parameter is used at every step, so its gradient is the sum of the contributions of all its uses. For the cell above and a loss $L = \sum_t \ell_t$, let $\mathbf{g}_t = \partial \ell_t / \partial \mathbf{h}_t$ be the direct derivative of the step loss, the zero vector for a step without a loss, and set $\boldsymbol{\delta}_{T+1} = \mathbf{0}$. Going backward for $t = T, \dots, 1$, the gradient of $L$ with respect to $\mathbf{a}_t$ is

where $\odot$ is the entrywise product, and the parameter gradients are

Truncated BPTT stops the backward pass after a fixed number of steps. It saves memory and time, but no gradient then reaches back across the cut, although the state values still do.

Definition A long short-term memory (LSTM) cell carries two vectors of width $d_h$, a cell state $\mathbf{c}_t$ and a hidden state $\mathbf{h}_t$. Let $\mathbf{u}_t$ be the vector that stacks $\mathbf{x}_t$ on top of $\mathbf{h}_{t-1}$. In the common form with a forget gate, the cell computes three gates and a candidate,

and then updates

Here $\sigma$ is the logistic sigmoid applied to each entry, so every gate entry lies strictly between 0 and 1, and each of the four matrices has shape $d_h \times (d + d_h)$. The forget gate $\mathbf{f}_t$ scales the old cell state, the input gate $\mathbf{i}_t$ scales the candidate, and the output gate $\mathbf{o}_t$ controls how much of the cell state appears in the hidden state. All gates are learned functions of the current input and the previous hidden state. In this form an LSTM cell has $4 d_h (d + d_h + 1)$ parameters, four times as many as a simple recurrent cell of the same widths.

Definition A gated recurrent unit (GRU) keeps a single state $\mathbf{h}_t$ and uses two gates. With $\mathbf{u}_t$ stacking $\mathbf{x}_t$ and $\mathbf{h}_{t-1}$, one common form computes the update gate $\mathbf{z}_t = \sigma(W_z \mathbf{u}_t + \mathbf{b}_z)$ and the reset gate $\mathbf{r}_t = \sigma(W_r \mathbf{u}_t + \mathbf{b}_r)$, then a candidate from the input and the reset previous state,

where $\mathbf{v}_t$ stacks $\mathbf{x}_t$ and $\mathbf{r}_t \odot \mathbf{h}_{t-1}$, and finally the blend

Each coordinate of the new state lies between the old state and the candidate, and in this convention $\mathbf{z}_t$ is the share given to the candidate. The original GRU and several software libraries write $\mathbf{h}_t = \mathbf{z}_t \odot \mathbf{h}_{t-1} + (\mathbf{1} - \mathbf{z}_t) \odot \tilde{\mathbf{h}}_t$ instead, so that their $\mathbf{z}_t$ is the share kept from the old state. Because $1 - \sigma(s) = \sigma(-s)$, negating the weights and bias of the update gate turns one convention into the other, and both describe the same family of models. In the form written here a GRU cell has $3 d_h (d + d_h + 1)$ parameters.

Definition Sequence padding appends placeholder positions to sequences of unequal lengths $L_1, \dots, L_B$ so that a batch fits one array of shape $B \times T \times d$ with $T \ge \max_i L_i$. In this batch-first layout the hidden states form an array of shape $B \times T \times d_h$. Some libraries put the time axis first, so the layout has to be checked, not guessed. The sequence mask is the $B \times T$ array with $m_{it} = 1$ when step $t$ of sequence $i$ holds a real observation and $m_{it} = 0$ at padding. For per-step losses $\ell_{it}$ the masked mean is

defined when at least one position is valid. It weights every valid step equally, so long sequences count more than short ones, and averaging within each sequence first is a different choice that has to be declared. Padded positions never become targets. A recurrence whose final state is used either stops at each sequence’s length or keeps the state unchanged at masked steps, $\mathbf{h}_{it} = \mathbf{h}_{i,t-1}$ when $m_{it} = 0$.

Definition Teacher forcing trains a next-symbol model by feeding it the observed previous symbols. For an observed sequence $y_1, \dots, y_T$ preceded by a start symbol $y_0$, the input at step $t$ is $y_{t-1}$, the target is $y_t$, and the training loss is

where $y_{<t}$ stands for $y_0, \dots, y_{t-1}$. This is the negative log-likelihood of the sequence under the factorization of $P(y_1, \dots, y_T \mid y_0)$ into the product of the conditionals $P(y_t \mid y_{<t})$, so teacher forcing is maximum likelihood estimation for such a model. The model must be causal, meaning the prediction for step $t$ may depend only on $y_{<t}$. At generation time the observed symbols do not exist, and the input at each step is the model’s own previous output.