RNNs and LSTMs

They process the sequence one item at a time and carry the prior context in recurrent connections, without a fixed-size window, so decisions can depend on information from hundreds of words back.

Any network with a cycle in its connections, so some unit’s value depends (directly or indirectly) on its own earlier outputs. Elman networks (simple recurrent networks) are a constrained, effective class in which the hidden layer receives its own previous value as extra input.

The previous time step’s hidden layer is added to the hidden layer’s input, acting as memory or context of earlier processing, with no fixed length limit: it can carry information back to the sequence start.

\(U\), connecting the previous hidden layer \(h_{t-1}\) to the current hidden layer; like the other weights, it is trained by backpropagation.

\(h_t = g(Uh_{t-1} + Wx_t)\) and \(y_t = f(Vh_t)\), usually \(y_t = \text{softmax}(Vh_t)\), with \(W\) \([d_h \times d_{in}]\), \(U\) \([d_h \times d_h]\), \(V\) \([d_{out} \times d_h]\).

Computing the hidden layer at time \(t\) requires the hidden layer from time \(t-1\).

Copy the network’s layers for each time step to show their different values over time, while the weight matrices \(U\), \(V\), \(W\) are shared across all steps.

The loss at time \(t\) depends on the hidden layer at \(t-1\), and the hidden layer at \(t\) affects both the output at \(t\) and all later hidden layers and losses; its error must account for both.

A two-pass algorithm: a forward pass computing and saving hidden states and accumulating the loss, then a backward pass over the sequence in reverse computing gradients and error terms for each step.

Unroll the network for the given input into a feedforward computation graph and train with ordinary backpropagation. For very long inputs (speech, character streams), unroll fixed-length segments treated as separate training items.

No limited or fixed context window: the hidden state can in principle represent information about all preceding words back to the start of the sequence.

\(e_t = Ex_t\) (embedding of the one-hot input), \(h_t = g(Uh_{t-1} + We_t)\), \(\hat{y}_t = \text{softmax}(Vh_t)\); \(P(w_{t+1} = k \mid w_{1:t}) = \hat{y}_t[k]\).

The product of the probabilities of each true word: \(P(w_{1:n}) = \prod_i \hat{y}_i[w_i]\).

The text supplies its own labels: at each step the model is trained (with cross-entropy) to predict the true next word, with no added gold annotation.

At each step the model is given the correct previous word (with the hidden state) rather than its own prediction from the previous step.

Using the embedding matrix \(E\) both at the input and, transposed, in place of the output matrix \(V\): \(\hat{y}_t = \text{softmax}(E^\top h_t)\). Both encode word embeddings; tying improves perplexity and greatly reduces parameters.

Input word embeddings; at each step a softmax over the tagset gives tag probabilities; pick the most likely tag per step; train with cross-entropy.

Run the text through the RNN and pass the last hidden state \(h_n\), a compressed representation of the whole sequence, to a feedforward network with a softmax over classes. Only the final classification produces a loss.

Using the loss from the downstream task to adjust weights all the way through the network (classifier and RNN).

Pooling all hidden states, e.g. the element-wise mean \(\frac{1}{n}\sum_i h_i\) or element-wise max.

Feed <s>, sample a word from the softmax, feed that word’s embedding as the next input, sample again, until </s> or a length limit.

Prime the generator with a task-appropriate context instead of just <s>: the source sentence for translation, the long text for summarization.

Multiple RNNs where the output sequence of one is the input of the next. Layers induce representations at different levels of abstraction (like early vision detecting edges, later stages shapes), but training cost rises quickly with depth.

Two independent RNNs, one reading left to right and one right to left; at each step their hidden states are concatenated, \(h_t = [h^f_t; h^b_t]\), capturing both left and right context.

A forward RNN’s final state reflects the end of the sentence more than its beginning; combining the final states of the forward and backward passes represents the whole sequence more evenly.

Predicting were requires remembering the distant plural flights, while the closer singular airline intervenes; RNN hidden states tend to encode mostly local information.

The hidden layer must both provide information for the current decision and carry forward information for future ones; and backpropagation through time multiplies gradients repeatedly, driving them toward zero (vanishing gradients).

Long short-term memory networks (Hochreiter & Schmidhuber, 1997) add an explicit context (cell) layer and learn, via gates, to remove information no longer needed and add information likely to be needed later.

A feedforward layer, then a sigmoid, then element-wise multiplication with the layer being gated. The sigmoid pushes values toward 0 or 1, so the product acts like a binary mask: values passed nearly unchanged or erased.

It deletes information from the context that is no longer needed: \(f_t = \sigma(U_fh_{t-1} + W_fx_t)\), \(k_t = c_{t-1} \odot f_t\).

Element-wise multiplication of two vectors of the same dimension, written \(\odot\).

Compute candidate information \(g_t = \tanh(U_gh_{t-1} + W_gx_t)\), mask it with the add (input) gate \(i_t = \sigma(U_ih_{t-1} + W_ix_t)\), \(j_t = g_t \odot i_t\), and add it to the filtered context: \(c_t = j_t + k_t\).

Decides what information the current hidden state needs (as opposed to what to preserve for the future): \(o_t = \sigma(U_oh_{t-1} + W_ox_t)\), \(h_t = o_t \odot \tanh(c_t)\).

Inputs: current input \(x_t\), previous hidden state \(h_{t-1}\), previous context \(c_{t-1}\). Outputs: new hidden state \(h_t\) (the unit’s output) and updated context \(c_t\).

It is encapsulated within the unit: externally an LSTM differs from a simple recurrent unit only by the extra context vector, so LSTM (or GRU) units can be swapped into any RNN architecture (stacked, bidirectional) and trained by unrolling.

LSTMs (rather than simple RNNs) for any modern system using recurrent networks.

Sequence labeling (one output per input token, e.g. POS); sequence classification (one output from the end of the sequence, e.g. sentiment); language modeling (predict the next token at each step); encoder-decoder (map an input sequence via a context to an output sequence of different length).

When input and output sequences can differ in length and the mapping between their tokens is indirect, as in machine translation; it is also used for summarization, question answering and dialogue.

An encoder producing contextualized representations \(h_{1:n}\) of the input; a context vector \(c\), a function of \(h_{1:n}\) conveying the essence of the input; and a decoder generating an arbitrary-length sequence of hidden states and outputs from \(c\).

Concatenate the source sentence, a separator token <s>, and the target sentence, and model \(p(y \mid x) = \prod_t p(y_t \mid y_{1:t-1}, x)\): after reading the source, generate the target autoregressively.

The encoder’s final hidden state \(c = h^e_n\) initializes the decoder (\(h^d_0 = c\)) and is also given to every decoder step, so its influence doesn’t wane: \(h^d_t = g(\hat{y}_{t-1}, h^d_{t-1}, c)\).

At inference the decoder feeds its own outputs back and drifts from the gold target; in training, feeding the gold token as the next input instead speeds up learning.

The final encoder hidden state must represent everything about the source sentence, since it is all the decoder sees; information from the beginning of long sentences may be poorly represented.

It lets the decoder use all encoder hidden states: at each decoding step \(i\), a new context vector \(c_i\) is computed as a weighted average of the encoder states, with weights depending on the decoder’s previous state; then \(h^d_i = g(\hat{y}_{i-1}, h^d_{i-1}, c_i)\).

Score each encoder state by similarity to the previous decoder state, \(\text{score} = h^d_{i-1} \cdot h^e_j\); softmax the scores into weights \(\alpha_{ij}\); take \(c_i = \sum_j \alpha_{ij}h^e_j\).

A bilinear score with learned weights, \(\text{score} = h^d_{i-1}W_sh^e_j\), which learns which aspects of similarity matter and allows encoder and decoder states of different dimensionality.

In the Parallel Distributed Processing (PDP) group at UC San Diego, mostly for human cognitive modeling; Elman (1990) introduced recurrence at the hidden layer, Jordan (1986) from the output layer.

LSTMs (Hochreiter & Schmidhuber, 1997; Gers et al., 2000), which brought big gains in phoneme recognition, handwriting recognition and, most significantly, speech recognition.

Near state-of-the-art performance on POS tagging, chunking, NER and semantic role labeling using learned word embeddings, convolutional networks and end-to-end training, without hand-engineered features.

Cho et al. (2014) coined the name (with Sutskever et al. 2014 using RNNs for both parts). Attention, a soft weighting over inputs for a generative decoder, was first developed by Graves (2013) for handwriting; Bahdanau et al. (2015) named it attention and applied it to MT.