Sequence Models: Predicting the Next Word

What a language model does

A language model assigns probabilities to text. Its core job is to answer: given the words so far, how likely is each possible next token?

To generate text, a model repeats one simple loop:

1. Predict the probability of every possible next token.
2. Choose one, usually by sampling from those probabilities.
3. Add it to the text, and go back to step 1.

Generating one token at a time, each time feeding the output back in as input, is called autoregressive generation. Every chatbot works this way: an essay is hundreds of next-token predictions in a row.

N-gram models: counting what comes next

The simplest language model just counts. A bigram model estimates the chance of each word from the word before it:

In the sentence set "the cat sat on the mat . the dog sat on the log . the cat saw the dog . the dog saw the cat on the mat .", the word "the" appears 9 times before another word:

An n-gram model looks at the previous n − 1 words. Longer contexts predict better but become hopelessly sparse: most five-word sequences never appear in any training text at all, so the counts are zero. Smoothing tricks help, but n-gram models can never use more than a few words of context.

Perplexity: how surprised is the model?

Language models are compared by perplexity, which measures how surprised a model is by real text:

A perplexity of 20 means the model is, on average, as uncertain as if it were choosing uniformly among 20 equally likely words. Lower is better. On a standard benchmark of news text, the best n-gram models scored perplexities well over 100; neural language models brought that down to the teens and below.

Recurrent neural networks

A recurrent neural network (RNN) reads a sequence one token at a time and carries a hidden state, a vector that acts as its memory of everything so far.

The same weights W and U are used at every step, so an RNN can handle sequences of any length. Drawn "unrolled", it looks like a very deep network with one layer per word, and it is trained with backpropagation through that unrolled graph, called backpropagation through time.

Why plain RNNs forget

The gradient from a word 50 steps back passes through 50 multiplications by W and 50 tanh slopes. Just as in deep networks (Level 6), it usually vanishes, so a plain RNN struggles to connect "The keys to the cabinet, which I left in the kitchen last week, ___" back to "keys" when choosing between "is" and "are".

LSTMs: learning what to remember

The long short-term memory network (LSTM), invented by Sepp Hochreiter and Jürgen Schmidhuber in 1997, adds a separate cell state, a memory line running along the sequence that information can travel on almost unchanged, plus three gates that learn what to do with it:

Each gate is a sigmoid layer outputting values between 0 (block) and 1 (let through), multiplied with the information it controls. Because the cell state is updated by addition rather than repeated multiplication, gradients survive over hundreds of steps. The simpler GRU (2014) merges some of the gates and works about as well.

LSTMs powered the 2016 version of Google Translate, speech recognition in phones and much more, until transformers replaced them.

Sequence to sequence, and the bottleneck

For translation, a sequence-to-sequence model (2014) uses two RNNs:

• an encoder reads the whole source sentence and squeezes it into its final hidden state, one fixed-size vector;
• a decoder generates the translation word by word, starting from that vector.

The weakness is obvious from the picture: the meaning of the entire sentence, however long, must pass through one vector, the bottleneck. Translation quality fell sharply for long sentences.

In 2014 Dzmitry Bahdanau, Kyunghyun Cho and Yoshua Bengio let the decoder look back at every encoder state, weighting them by relevance at each step. They called it attention. Three years later, a team at Google asked what would happen if you kept the attention and threw the recurrence away. That is Level 10.

Hands-on: language models from scratch

A bigram model that writes

import random
from collections import Counter

text = ("the cat sat on the mat . the dog sat on the log . the cat saw the dog . "
        "the dog saw the cat on the mat .").split()
pairs = Counter(zip(text, text[1:]))
starts = Counter(text[:-1])

def next_word_probs(word):
    return {b: c / starts[word] for (a, b), c in pairs.items() if a == word}

print("after 'the':", {w: round(p, 2) for w, p in next_word_probs("the").items()})
print("after 'sat':", next_word_probs("sat"))

random.seed(3)
word, sentence = "the", ["the"]
for _ in range(14):
    probs = next_word_probs(word)
    word = random.choices(list(probs), weights=list(probs.values()))[0]
    sentence.append(word)
print("generated:", " ".join(sentence))

Every pair of neighbouring words is plausible, yet the whole makes little sense, because a bigram model only ever sees one word back.

Perplexity

import math
from collections import Counter

train = ("the cat sat on the mat . the dog sat on the log . the cat saw the dog . "
         "the dog saw the cat on the mat .").split()
vocab = set(train)
pairs = Counter(zip(train, train[1:]))
starts = Counter(train[:-1])

def prob(prev, word):
    # add-one smoothing, so unseen pairs are unlikely but not impossible
    return (pairs[(prev, word)] + 1) / (starts[prev] + len(vocab))

def perplexity(sentence):
    words = sentence.split()
    loss = -sum(math.log(prob(a, b)) for a, b in zip(words, words[1:])) / (len(words) - 1)
    return math.exp(loss)

for s in ["the cat sat on the mat", "the dog sat on the log", "mat the on sat cat the"]:
    print(f"{s:24} perplexity {perplexity(s):5.2f}")

A recurrent memory

This one-number RNN state remembers that it saw a "1", and that memory fades with every step, which is the forgetting problem in miniature.

import math

w_hidden, w_input = 0.7, 1.5
h = 0.0
sequence = [1, 0, 0, 0, 0, 0, 1, 0, 0]
for t, x in enumerate(sequence):
    h = math.tanh(w_hidden * h + w_input * x)
    print(f"step {t}: input {x}  hidden state {h:.3f} " + "#" * int(h * 30))

Try this

1. Train the bigram model on a paragraph of your own and generate from it.
2. Change w_hidden to 0.95 and then 0.3. How long does the memory last now?

Level check

• Explain what a language model predicts and how autoregressive generation works
• Calculate bigram probabilities from counts
• Explain what perplexity measures and whether lower or higher is better
• Describe how an RNN carries a hidden state, and why plain RNNs forget
• Describe the three gates of an LSTM and why its cell state helps
• Explain the bottleneck in sequence-to-sequence models and how attention began

Key terms you must be able to define

Language model

A model that assigns probabilities to text, usually by predicting the next token.

Autoregressive generation

Producing text one token at a time, feeding each output back in as input.

N-gram

A sequence of n words; an n-gram model predicts a word from the n − 1 before it.

Sparsity

Most possible word sequences never appear in training data, so their counts are zero.

Perplexity

e to the power of the average cross-entropy per token: how many choices the model is effectively unsure between.

Recurrent neural network (RNN)

A network that processes a sequence step by step, carrying a hidden state forward.

Hidden state

The vector an RNN passes from step to step as its memory of the sequence so far.

Backpropagation through time

Training an RNN by backpropagating through its unrolled steps.

LSTM

Long short-term memory: an RNN with a cell state and gates that learn what to forget, store and output.

Sequence to sequence

An encoder network that reads an input sequence and a decoder that generates an output sequence.

Bottleneck

Forcing all of a sequence's information through one fixed-size vector.

Flashcards

Go further: notes for future AI engineers

Teacher forcing and exposure bias

When training a sequence model, the input at each step is the real previous token from the training text, not the model's own guess. This is called teacher forcing, and it makes training fast and parallel. But at generation time the model must eat its own outputs, including its mistakes, which it never practised: a mismatch called exposure bias. A single odd word can push the model into territory unlike anything it trained on, which is one reason long generations can drift.

Why RNNs were slow to train

An RNN must compute step 2 after step 1, step 3 after step 2, and so on, so a 1,000-token sequence takes 1,000 sequential steps that cannot run in parallel, leaving most of a GPU idle. The transformer's attention compares all positions at once, turning a sequence into one big matrix multiplication. That parallelism, more than any other single factor, is why transformers could be trained on vastly more data and replaced RNNs almost everywhere after 2017.

Misconceptions to avoid