Recurrent Neural Networks
Sequence Data
Our convolutional network looked at one 32 × 32 photo at a time and said what was in it. Each photo was classified completely on its own, so if we shuffle the 10,000 unseen photos every one of them still gets the same answer.
Text is different. Pictured above, under the photos, is the first line of the Notre Dame Victory March, one word to a box. Shuffled, it becomes
Data like this, where the order matters and each piece has to be read in the context of the pieces before it, is called sequence data. Text is the obvious example, but speech, music, stock prices and video are all sequences too. As we saw at the end of the last chapter, a CNN can't take one in. It expects a grid of a fixed size, and a sentence can be any number of words long.
Tokenization
Unfortunately, a network only understands numbers. Our photos came as numbers already (0 to 255 for each color of each pixel), but a fight song comes as letters, commas and spaces. Turning language into numbers a computer can use is the central problem of Natural Language Processing (NLP).
The first step is to cut the text into pieces called tokens, which is called tokenization. We'll keep it simple: lowercase everything, turn anything that isn't a letter into a space, and split on the spaces. We'll use the first four lines of the Victory March all the way through this chapter.
26 tokens, 22 words [cheer, cheer, for, old, notre, dame, wake, up, the] [0, 0, 1, 2, 3, 4, 5, 6, 7]
Tokenization Levels
Our code does word-level tokenization, one token per word, and it isn't the only choice. Here is how our four lines come out at each level:
| level | one token is | tokens | vocabulary |
|---|---|---|---|
| character-level | a character | 136 | 25 |
| word-level | a word | 26 | 22 |
| subword-level | a word or a piece of one | 70 | 512 |
| byte-level | a byte of the stored text | 136 | 256 |
Our 22-word vocabulary only works because our text is four lines long. Real English needs hundreds of thousands of words, and a word the vocabulary has never seen (a typo, say) can't be tokenized at all. Character-level needs only a few dozen symbols, but our four lines become 136 tokens, each meaning very little on its own. The goal is to keep the vocabulary small while keeping the sequences short.
Subword Tokenizers
A subword tokenizer gives common words a token of their own and builds rarer ones out of pieces, which keeps both the vocabulary and the sequences reasonably small, and nearly every modern language model uses one. Below is how one splits our first two lines, the tokenizer of irishQwen (the small language model built in CSE 10124), whose 512 tokens were made from Shakespeare.
With only 512 tokens to go around, just the most common words (
Token IDs
Above are all 26 of our word-level tokens. There are only 22 different words, since
So now every token is a number. Are we actually gaining anything from this? Not much, yet. The IDs are just positions in a list, so if we handed them to a network as they are, it would decide that
One-Hot Encoding
The usual fix is a one-hot vector, a list of 22 zeros with a single 1 in the token's position.
Now no word is bigger than any other. Unfortunately, every pair of words is also exactly the same distance apart (
What we'd like is a short list of numbers for each word, where words that are used in similar ways get similar numbers.
Word Embeddings
Much like our CNN turned each photo into a list of 4,096 learned features, in NLP we turn each token into a short vector called a word embedding, built from the only evidence a computer has about a word, the words around it.
Learning good embeddings takes billions of words, far more than our four lines, so we can borrow some. GloVe (Pennington, Socher and Manning, Stanford, 2014) counted how often every pair of words turns up near each other in 6 billion words of Wikipedia and news, and learned 300 numbers for each of 400,000 words so that words used in similar ways get similar vectors. We only need the rows for our 22 words.
torch.Size([22, 300])
Cosine Similarity
To compare two words we scale both vectors to length 1 and take their dot product, the cosine similarity (1 means they point the same way, 0 means unrelated). One matrix product gives us every pair at once, and we can ask which of our 22 words sits closest to each.
cheer cheering 0.61 notre dame 0.91 up down 0.75 thunder sky 0.34
Embedding Space
Pictured above is every word in our vocabulary, squashed from 300 numbers to 2 with PCA so we can look at it (only 28% of the spread survives, so this is extremely approximate).
Notice that
Bias in Embeddings
Unfortunately, the patterns include the text's biases. If we take the direction from "man" to "woman" in GloVe (the vector for "woman" minus the vector for "man") and see how far along it other words sit, jobs and ideas line up the way the articles talked about them. "nurse", "homemaker" and "receptionist" land far toward "woman", "engineer", "programmer" and "power" toward "man".
None of this was put there on purpose, the embedding only counted which words were used together. Embeddings learned from Google News articles went as far as answering "man is to computer programmer as woman is to ___" with "homemaker" (Bolukbasi and colleagues, 2016, who named their paper after it). A model built on top of embeddings inherits whatever they learned.
Context
Now that words are numbers, let's give a network a job, predicting the next word. A feed-forward network takes one fixed-size input, so the natural thing to give it is the current word's embedding. Given
Unfortunately,
We could feed it the last two words instead, but some other text will need three, or ten, and sentences don't come in a fixed length. The words that came before a word are its context, and what we want is a network that reads one word at a time and carries a summary of that context along with it.
Recurrent Neural Networks
A recurrent neural network (RNN) does exactly that. At step
The RNN Cell
Pictured above is one step of our RNN, drawn as a computation graph in the same colors as our earlier networks. The top half is the equation on the last page, and the hidden state it makes goes on to the next step. The bottom half turns the hidden state into a prediction, which we'll come back to.
The idea goes back to at least 1986 (Michael Irwin Jordan, no relation), and Jeffrey Elman's 1990 network fed back its hidden layer, as ours does. One step like this is usually called a cell, since the same one is used again for every word.
The Tanh Function
The function wrapped around all of this is tanh (the hyperbolic tangent), which we saw next to the sigmoid and ReLU with feed-forward networks. Like the sigmoid it's S-shaped, but it runs from −1 to 1 instead of 0 to 1, and it gives 0 for an input of 0.
An RNN feeds its hidden state back into itself once per word, 26 times for our four lines. If each pass through
Being centered on zero matters too. A sigmoid's outputs are always positive, while a tanh hidden state can push the next one up or down equally easily.
Unrolling
Because the hidden state loops back into the same cell, an RNN is usually drawn unrolled, with one copy of the cell for each word, side by side. Pictured below are our first four words.
It's important to remember that this isn't four different layers. Every box uses the same weights, so an RNN that reads 26 words has exactly as many weights as one that reads 4. The numbers under each word are its embedding (from a random table, since our network hasn't been trained) and the numbers above each cell are the hidden state it hands to the next step.
Notice that
An RNN by Hand
Let's work out those first two steps ourselves. Our embeddings and hidden state have two numbers each, the embedding table is random (rounded to one decimal), and we picked the weights by hand to keep the arithmetic simple, with the bias at 0:
The first word is
The second
Same word, same weights, different hidden state. The second
The Forward Pass
Running every word through the cell in order is the RNN's forward pass, a loop in PyTorch. Below we print the hidden state at each
[wake, up, the] tensor([-0.9790, -0.3550]) [shake, down, the] tensor([-0.9700, -0.2270]) [thunder, from, the] tensor([-0.9770, 0.2170])
Three times the network reads
RNNs in PyTorch
PyTorch has both pieces built in. nn.Embedding is the embedding table, one row per token ID, and nn.RNN runs the whole loop. Below we give them our weights instead of their own random ones and read the four lines again:
(1, 26, 2) (1, 26, 2) (1, 1, 2) tensor([-0.9790, -0.3550])
Inside nn.RNN
On the last page, out held the hidden state after every word (what we need to predict every next word) and c only the last one. The weights that made them are stored under names of their own:
weight_ih_l0 (2, 2) weight_hh_l0 (2, 2) bias_ih_l0 (2,) bias_hh_l0 (2,)
weight_ih_l0 ("input to hidden", layer 0) is our
Outputs
To predict the next word, each hidden state goes through one more layer, with a softmax to turn its scores into one probability per word in the vocabulary (as our CNN did for its ten kinds of photo):
For us
It thinks the next word is most likely
An RNN From Scratch
In Backpropagation we wrote each layer of a network as a small class with a forward method, and in CNNs we added a convolutional layer and pooling the same way. An RNN needs two new layers. The first is the embedding layer:
It holds the embedding table, one row per token in the vocabulary, and its forward is a lookup: a batch of token IDs, shape (B, T), becomes a batch of vectors, shape (B, T, d). That is the same as multiplying each one-hot vector by the table (One-Hot Encoding), without building the one-hot vectors.
The Recurrent Layer
The second is the recurrent layer, our cell run over the words in order:
The step method is the equation from The RNN Cell, for a whole batch of sequences at once. The forward method is our loop from The Forward Pass: it starts from a hidden state of zeros and calls the same step, with the same Wx and Wc, for every word. It also keeps every hidden state in self.states, since training will need them in the next chapter.
The Rest of the Network
The output layer from the last page is a linear layer, and we already have one. LinearLayer and Network are the classes from Backpropagation, with only their forward methods for now:
The recurrent layer hands on a hidden state for every word, shape (B, T, n_h), and @ multiplies the last dimension, so the linear layer scores every word's next word at once. Network doesn't care what kind of layers it holds.
Running Our RNN From Scratch
Below we put the four lines through an embedding layer, a recurrent layer with two hidden numbers and a linear layer back out to our 22 words, all with random weights:
IDs (1, 26) -> logits (1, 26, 22) hidden states: 27 weights: 120
One song of 26 words comes out as 26 rows of 22 scores, one for each next word, and the recurrent layer kept 27 hidden states. The network has 120 weights: 44 in the embedding table, 10 in the cell and 66 in the output layer. None of them depend on how long the song is.
Our Weights, From Scratch
To check our classes, we can give them the weights from the earlier pages (the same seed for the embedding table and
c: tensor([[-0.9790, -0.3550]]) p(echoes): tensor(0.0900)
After wake up the we get the hidden state from The Forward Pass and the 0.090 for echoes from Outputs, so our classes compute the same network as the loop.
Checking Against PyTorch
We can check against PyTorch the same way we did for the loop, by copying our weights into nn.Embedding, nn.RNN and nn.Linear:
largest difference: tensor(0.)
The scores are identical. PyTorch keeps a second bias in the cell (Inside nn.RNN), which we set to zero, and otherwise nn.RNN is our loop, written in faster code. When we train an RNN in the next chapter, our classes will need a backward method, while PyTorch will work the gradients out for us.
Uses of RNNs
Our network gives an output after every word, a guess at the next one. That isn't the only way to wire an RNN up, and which outputs we keep (and what we feed in) decides what it can be used for.
Pictured above, many to one reads a whole sequence and only answers at the end, using the last hidden state, which is how an RNN labels a sentence (is this review positive?). Many to many answers after every word, like our next-word predictions. The bottom two are the uses that made RNNs famous, writing text and translating it.
Text Generation
A network that predicts the next word can also write. We give it a first word, take the word it thinks is likeliest, and feed that back in as the next input, one word at a time:
[cheer, send, on, shake, shake] [for, old, shake, shake, for]
Not exactly the fight song, but that's what made-up weights write.
Sampling
Always taking the likeliest word tends to get stuck in loops (
After
Trained on enough text, a generating RNN gets surprisingly good. Andrej Karpathy's 2015 RNNs, which read and wrote one character at a time, produced passable fake Shakespeare and Wikipedia articles.
Machine Translation
Translation is harder, since a sentence and its translation rarely have the same number of words, or put them in the same order. The answer, from two groups in 2014 (Sutskever, Vinyals and Le at Google, and Cho and colleagues in Montreal), was to use two RNNs. The first, the encoder, reads the whole sentence and produces no outputs at all. Its last hidden state is handed to the second, the decoder, as its starting hidden state, and the decoder generates the translation one word at a time, like the last page, until it predicts a special end-of-sentence token.
Everything the decoder knows about the original sentence is in that one hidden state, which is why it's often called the context vector. It's also called an encoder-decoder (or sequence-to-sequence) model, and with LSTMs in place of our plain cells, plus the attention of a few pages on, it was good enough that in 2016 Google Translate switched to one.
Pros and Cons of RNNs
An RNN reads a sequence of any length with one fixed set of weights. Ours has 120 numbers to learn (44 in the embedding table, 10 in the cell and 66 in the output layer), whether it reads four words or four thousand. Its hidden state carries along the context a feed-forward network never sees, and it can give an output after every word, or only after the last one (to label a whole sentence, say).
Unfortunately, it can only read one word at a time. Each step needs the hidden state from the step before, so 26 words means 26 steps, one after another. Our CNN can label a thousand photos at once, because none of them needs the others' answers, but an RNN can't start on word 10 until it has finished word 9. On long texts and big GPUs that makes RNNs slow to train.
Long-Term Dependencies
Worse, it forgets. Below we run the forward pass twice, on the song as written and with
The gap is 0.93 after the first word, 0.26 by
A word that depends on another word far back is called a long-term dependency, and RNNs are bad at them. A trained network holds on for longer than our made-up one, but every RNN has this problem to some degree.
Gates
Our network forgets because every step replaces the hidden state with a mix of the new word and the old state, squashed. What if each step could choose how much of the old hidden state to keep? Write
A vector like
By the ninth word the plain RNN has 0.1% of the first word left, the gated one 59%, and at the end of the song still 21%.
LSTMs and GRUs
Of course a gate stuck at 0.9 isn't much use, since it remembers everything just as hard, the words that matter and the ones that don't. In a real network the gate is a layer of its own, a sigmoid looking at the new word and the old hidden state,
That's (most of) a Gated Recurrent Unit (GRU, Cho and colleagues, 2014), which adds a second gate deciding how much of the old state goes into
RNN 12 GRU 36 LSTM 48
In PyTorch either one is a drop-in replacement for nn.RNN, three and four times its size. Why gates make these networks so much easier to train is a story about gradients, and the next chapter's.
The Bottleneck
Gates help an RNN hold on, but it still has to fit everything into one hidden state of a fixed size. For a translation that's the context vector, and every word of the original sentence has to survive in it until the decoder needs it, however long the sentence is. Ours has two numbers to carry the whole song.
This is called the bottleneck problem, and it showed. Cho and colleagues found in 2014 that their encoder-decoder's translations got steadily worse as the sentences got longer.
The encoder did make a hidden state after every word, though, and each one is a summary of the sentence up to that word. Rather than throwing all but the last one away, the decoder could keep them all and, at each word it writes, look back at whichever ones it needs.
Attention
That's what Bahdanau, Cho and Bengio did in 2014, and they called it attention. Before writing each word, the decoder scores every one of the encoder's hidden states against its own current hidden state
So every word the decoder writes gets its own context vector, built mostly from the hidden states it gave the most weight. Translating into French, the weights for each French word mostly picked out the English word it came from, and the translations stopped falling apart on long sentences.
Attention Weights
We have no decoder, but we can let our network look back the same way. At the last
The biggest weights go to
Unfortunately, with made-up weights that's as far as we can get. Every weight, gate and score in this chapter needs to be learned from data, and every weight in an RNN is used at every step, so training one means following the loss back through every step of the loop, which is where we pick up next. (Attention will be back too, without the RNN at all.)