Natural Language Processing before LLMs

This first post is about classical Natural Language Processing (NLP), before the LLM era.

I know what you’re thinking. Studying old-school NLP might feel like a waste of time, as these techniques have largely been superseded by LLMs.

Still, I believe dedicating a few hours to it is worth your time. First of all, you’ll learn important concepts that are still relevant today. You’ll better understand the genealogy of ideas, which is important for developing your research taste. In particular, you’ll see more clearly how and why transformers were introduced and rapidly adopted. Finally, this post references a few dozen seminal papers that you must have seen once in your life if you want to be serious about the topic.

In this first chapter, we will follow two important questions that have shaped the development of the field of NLP:

• How can we build a machine learning model that takes as input a piece of text, given that it has no fixed length?
• How can we transfer what a model learned on one task to another, building on the fact that on every NLP task, language is essentially the same?

To explore these questions, we’ll play mostly with two tasks and two datasets:

• the IMDB movie reviews for sentiment classification
• WikiText-2 for language modeling.

1. The typical tasks of NLP

Now that we live in a world of LLMs, it’s easy to think that autoregressive language modeling is all there is to NLP. But before 2019 and the realization that GPT-2 could generate coherent text and hence do other tasks without being specifically trained for them, language modeling was only one among the many tasks of classical NLP.

For decades, text classification, tagging and translation were the most important challenges that were tackled using the tools of machine learning.

Each of these four tasks can be formally represented as learning certain probability distributions conditioned on an input piece of text seen as a sequence of words. This is illustrated below.

Let’s consider these different tasks.

1.1 Classification

This is the simplest task to state in NLP: you receive a piece of text and you have to classify it among a predefined list of categories. It can be spam detection, sentiment analysis (Is this movie review positive or not?), or classification among topics (Is this news article about sports, politics, technology…?).

For that, a classifier has to learn the conditional probability

that a certain sequence of words $x_1 \dots x_L$ belongs to a class $C$, where here $L$ is not fixed a priori, and depends on the sequence.

As shown in the introductory example at the top of this post (“Wow, what a masterpiece. […] A perfect film if you love naps.”), sentiment classification can be subtle and involve detecting things like sarcasm.

1.2 Language modeling

In principle, modeling a language means learning the probability distribution $p(x_1 \dots x_L)$ of its possible sequences of words. In practice, it is often more convenient to learn the next-word probability

From this next-word probability, we can simply recover the full probability by using the chain rule, for instance

From today’s perspective, the main use of such a probability distribution is to generate text using autoregression: draw a word from the next-word distribution, append it to the text, and repeat. This is the principle behind LLM chatbots and agents.

But knowing the language probability distribution can have other uses, for instance to score the probability of sentences among a list of candidates. Imagine an Automatic Speech Recognition (ASR) model producing two candidate transcriptions that both reasonably fit the audio sample: it can be followed by a post-processing stage using a language model, to score these candidates and help choose the right one. For instance on any reasonable language model, the probability of the sentence “General relativity was formulated by Alfred Einstein” would certainly rank lower than that of “General relativity was formulated by Albert Einstein”.

Although I present them separately, it is important to realize that next-word prediction is a form of classification task! Instead of assigning probabilities to a finite set of classes, you assign probabilities to a finite set of words among the pre-defined vocabulary. The main practical difference is the size: generally a few classes in NLP classification tasks, while the vocabulary size in language modeling is often tens of thousands.

1.3 Translation

Translation from one language to another has long been one of the most important tasks in NLP, but also a hard one. Formally, we want to learn the probability of a candidate translation $y_1 \dots y_K$ conditioned on the original sentence $x_1 \dots x_L$. Again, in practice, we seek to estimate the next-word probability of the translated sequence, conditioned on the original sentence and what has been written so far:

Note that learning this probability distribution is far from obvious since the two sentences a priori have different lengths, and the translation is generally not a word-for-word correspondence.

On top of that, the word order can be totally different, see a nice example below showing the same sentence in 4 languages…you should try the English vs Turkish comparison!

1.4 Tagging

Finally, another typical NLP task is tagging. Its goal is to assign a class per word (or group of words). It can be grammar mistake detection, or tagging the grammatical category of each word in a sentence (noun, verb, …), a task that is known as part-of-speech tagging.

It can also be Named Entity Recognition (NER), for instance tagging all the names of people (or all places) in a text.

Tagging can be seen as “a classifier applied to each word”, but each taking into account the surrounding context.

I will not cover much of tagging here.

2. Counting words: n-grams as the simplest language models

Since language models will be our main interest later in the series, it is worth starting with a historical example representing the simplest way of generating language in an autoregressive way: the Markov model.

2.1 Markov model

If you really want the simplest (and most inefficient) language model, you can simply draw words at random in the vocabulary, following their natural frequency in the language. This is called the unigram model, for which

where $C(x_i)$ is the count of word $x_i$ in the training corpus, and $N = \sum C(x_i)$ is the corpus size. This is a very crude model! And we can at least improve it by considering bigrams, i.e. the Markov chain model.

Simple Markov chain

In the simplest bigram Markov chain model, the probability of a word in a sequence only depends on the word that comes just before it.

This assumption is of course incorrect for actual human languages, but it allows for very simple modeling using only a transition matrix.

Using a training set, we simply count the occurrences of every word $C(v)$ and of every pair of consecutive words $C(v,w)$. We then use it to compute the probability $p(w \mid v) = C(v,w)/C(v)$ that the word $w$ follows the word $v$. These probabilities define a transition matrix that can then be used for autoregressive text generation using a Markov Chain model.

Let’s try that on the following exercise.

from datasets import load_dataset

wikitext = load_dataset("Salesforce/wikitext", "wikitext-2-v1")
print(wikitext["train"][4]["text"][:70])   # 70 chars from line 4

 The game began development in 2010 , carrying over a large portion of

text: 2051910 words
vocabulary: 33277 words
distinct pairs: 618405

The institute . " and long , Mortimer Wheeler secured by worry over the Song military officer notable example of willows along the Richmond Chamber of the opening sequence stars except those produced , In November 23 January 1908 Distinguished Service before dissipating as a more able to bring the

from datasets import load_dataset

wikitext = load_dataset("Salesforce/wikitext", "wikitext-2-v1")
print(wikitext["train"][4]["text"][:70])   # 70 chars from line 4

 The game began development in 2010 , carrying over a large portion of

# (1) Build the train sequence by splitting every line on spaces
train_sequence = []
for line in wikitext["train"]["text"]:
    train_sequence.extend(line.split())

print(f"text: {len(train_sequence)} words")
print(f"vocabulary: {len(set(train_sequence))} words")


# (2) Use a nested dict for counting bigrams
bigram_counts = {}
for a, b in zip(train_sequence, train_sequence[1:]):
    if a not in bigram_counts:
        bigram_counts[a] = {}
    if b not in bigram_counts[a]:
        bigram_counts[a][b] = 0
    bigram_counts[a][b] += 1

print(f"distinct pairs: {sum(len(f) for f in bigram_counts.values())}")


# (3) Generate a sequence using random.choices with the counts as weights
first_word = "The"
length = 50

import random
random.seed(0)

sample_words = [first_word]
while len(sample_words) < length:
    followers = bigram_counts[sample_words[-1]]
    options, weights = list(followers), list(followers.values())
    next_word = random.choices(options, weights)[0]
    sample_words.append(next_word)

print("\n" + " ".join(sample_words))

text: 2051910 words
vocabulary: 33277 words
distinct pairs: 618405

The institute . " and long , Mortimer Wheeler secured by worry over the Song military officer notable example of willows along the Richmond Chamber of the opening sequence stars except those produced , In November 23 January 1908 Distinguished Service before dissipating as a more able to bring the

n-gram models

We can also extend the model by using n-grams, that is, chunks of $n$ consecutive words. To predict the next word, we thus consider the sequence of the $n-1$ previous words as an input. The Markov chain model of 2.1 is $n = 2$, the unigram model is $n=1$ where no context at all is used.

Using n-grams, the transition matrix will be $V^{n-1} \times V$, which can quickly become overwhelming (for $n=3$ and $V=30{,}000$, we have about $3 \times 10^{13}$ entries). In practice, once again we store only the n-grams that occur, in a dictionary of counts, but not the full table.

Below you can see examples for WikiText-2 at various $n$.

2.2 Comparing probability distributions

In language modeling, our goal is to approximate the “true” probability distribution of next word occurrence. Let’s call it $p(x_{L+1} \mid x_1 \dots x_L)$. Any candidate language model will produce a candidate distribution $q(x_{L+1} \mid x_1 \dots x_L)$ (in the n-gram Markov model, it depends only on $x_{L-n+2} \dots x_L$).

How do we measure success? That is, how do we quantify how similar $q$ is to $p$?

KL Divergence and cross-entropy loss

To assess whether a certain probability distribution is a good approximation to another one, the tool of choice is the Kullback–Leibler divergence

I write it with generic distribution $p$ and $q$, but note that this definition also works using conditional probabilities for instance in our case $p(x_{L+1} \mid x_1 \dots x_L)$ and $q(x_{L+1} \mid x_1 \dots x_L)$.

Finding the distribution $q$ that best approximates a given $p$ means minimizing the KL divergence. Now, in our case, as $p$ a priori is unknown, exactly computing this quantity might seem impossible. But to minimize the KL divergence, we can first notice that its log part can be separated into

The first part is (minus) the entropy of $p$ (which doesn’t depend on $q$), while the second part is the so-called cross-entropy.

Since the cross-entropy

is the only part that actually depends on $q$, we are actually seeking $q$ that minimizes it.

Finding $q$ that minimizes the KL-divergence $D_{KL}(p \,\|\, q)$ is equivalent to minimizing the cross-entropy $H(p,q)$.

You can try it informally on a very simple example below, by dragging the bars of the orange distribution.

Likelihood

Now let’s return to our notations, and remember that we are working with conditional probabilities $p(x \mid c)$ and $q(x \mid c)$ of having $x$ as the next word, knowing the context $c=(x_1,\dots,x_L)$.

If $q$ depends on some parameters $\theta$, we seek to minimize the cross-entropy

which can be seen as an expectation over distribution probability $x \sim p( . | c)$

Once again, we cannot compute this quantity directly because we do not know $p$, but our text corpus is a sample from $p$.

At each position $i$ of a text, the context $x_{<i} = x_1 \dots x_{i-1}$ is followed by the word $x_i$ that was actually written. Most contexts appear only once, so we never see the distribution $p(\cdot \mid x_{<i})$, only one word drawn from it. But the average over the $N$ positions of the text estimates the cross-entropy, averaged over the contexts as they occur in the language:

This average has a simple meaning. A sum of logs is the log of a product, and by the chain rule of section 1.2, $\prod_i q_\theta(x_i \mid x_{<i})$ is the probability that the model gives to the whole text, its likelihood. So $\hat{H}$ is the negative log-likelihood of the text divided by its number of words, and minimizing the cross-entropy amounts to maximizing the likelihood of the corpus.

To train a model, we choose the parameters $\theta$ (for instance the weights of a neural network) that minimize $\hat{H}$ on a training text. Each term of the sum is itself a cross-entropy: the one between $q_\theta$ and the distribution that puts all its probability on the observed word (a one-hot distribution), which stands in for the unknown $p$:

This is the cross-entropy loss used to train language models, LLMs included. Such a single term is a noisy estimate, but on average over the words of the text, its gradient is $\nabla_\theta H(p, q_\theta)$. Since the entropy of $p$ does not depend on $\theta$, this is also $\nabla_\theta D_{KL}(p \,\|\, q_\theta)$.

Maximizing the likelihood = Minimizing the cross-entropy loss = Minimizing the KL divergence.

For the n-gram models, we don’t even need gradients: the ratio of counts $C(v,w)/C(v)$ of section 2.1 is exactly the $q$ that maximizes the likelihood of the training text.

Perplexity

Now a cross-entropy is not easy to read and interpret, so we usually report its exponential, the perplexity of the model on a text:

It is the inverse of the geometric average of the probabilities that the model gives to the words of the text. A model that is uniform over $V$ words has perplexity $V$, so perplexity can be interpreted the number of words the model hesitates between.

In the exercises, we measure the perplexity on the validation set, and the test perplexity only to compare the models in section 6.

from datasets import load_dataset

wikitext = load_dataset("Salesforce/wikitext", "wikitext-2-v1")


# (1) Build the train sequence by splitting every line on spaces
# [Copied from the solution of 2.1, step (1)]
train_sequence = []
for line in wikitext["train"]["text"]:
    train_sequence.extend(line.split())

print(f"text: {len(train_sequence)} words")
print(f"vocabulary: {len(set(train_sequence))} words")


# (2) Use a nested dict for counting bigrams
# [Copied from the solution of 2.1, step (2)]
bigram_counts = {}
for a, b in zip(train_sequence, train_sequence[1:]):
    if a not in bigram_counts:
        bigram_counts[a] = {}
    if b not in bigram_counts[a]:
        bigram_counts[a][b] = 0
    bigram_counts[a][b] += 1

print(f"distinct pairs: {sum(len(f) for f in bigram_counts.values())}")


# ----------------------
#  New in this exercise
# ----------------------
# The validation and test sequences, built in the same way
val_sequence = []
for line in wikitext["validation"]["text"]:
    val_sequence.extend(line.split())

test_sequence = []
for line in wikitext["test"]["text"]:
    test_sequence.extend(line.split())

print(f"validation: {len(val_sequence)} words")
print(f"test: {len(test_sequence)} words")

text: 2051910 words
vocabulary: 33277 words
distinct pairs: 618405
validation: 213886 words
test: 241211 words

unigram perplexity, validation set: 996.5

validation pairs never seen in training: 46338
out of 213885, or 21.7%
bigram perplexity, validation set: inf

unigram perplexity, test set: 941.7

from datasets import load_dataset

wikitext = load_dataset("Salesforce/wikitext", "wikitext-2-v1")


# (1) Build the train sequence by splitting every line on spaces
# [Copied from the solution of 2.1, step (1)]
train_sequence = []
for line in wikitext["train"]["text"]:
    train_sequence.extend(line.split())

print(f"text: {len(train_sequence)} words")
print(f"vocabulary: {len(set(train_sequence))} words")


# (2) Use a nested dict for counting bigrams
# [Copied from the solution of 2.1, step (2)]
bigram_counts = {}
for a, b in zip(train_sequence, train_sequence[1:]):
    if a not in bigram_counts:
        bigram_counts[a] = {}
    if b not in bigram_counts[a]:
        bigram_counts[a][b] = 0
    bigram_counts[a][b] += 1

print(f"distinct pairs: {sum(len(f) for f in bigram_counts.values())}")


# ----------------------
#  New in this exercise
# ----------------------
# The validation and test sequences, built in the same way
val_sequence = []
for line in wikitext["validation"]["text"]:
    val_sequence.extend(line.split())

test_sequence = []
for line in wikitext["test"]["text"]:
    test_sequence.extend(line.split())

print(f"validation: {len(val_sequence)} words")
print(f"test: {len(test_sequence)} words")

text: 2051910 words
vocabulary: 33277 words
distinct pairs: 618405
validation: 213886 words
test: 241211 words

# (1) Count the words of the train sequence
unigram_counts = {}
for word in train_sequence:
    if word not in unigram_counts:
        unigram_counts[word] = 0
    unigram_counts[word] += 1


# (2) Perplexity of the unigram model: the exponential of minus
# the average log-probability of the validation words
import math

def perplexity(log_probs):
    return math.exp(-sum(log_probs) / len(log_probs))

n_train = len(train_sequence)
log_probs = []
for word in val_sequence:
    log_probs.append(math.log(unigram_counts[word] / n_train))

print(f"unigram perplexity, validation set: "
      f"{perplexity(log_probs):.1f}")


# (3) Perplexity of the bigram model. A pair never seen in
# training has the probability 0, and log(0) is minus infinity.
follower_totals = {}
for a in bigram_counts:
    follower_totals[a] = sum(bigram_counts[a].values())

log_probs = []
unseen_pairs = 0
for a, b in zip(val_sequence, val_sequence[1:]):
    count = bigram_counts[a].get(b, 0)
    if count == 0:
        unseen_pairs += 1
        log_probs.append(-math.inf)
    else:
        log_probs.append(math.log(count / follower_totals[a]))

n_pairs = len(log_probs)
print(f"\nvalidation pairs never seen in training: {unseen_pairs}")
print(f"out of {n_pairs}, or {100 * unseen_pairs / n_pairs:.1f}%")
print(f"bigram perplexity, validation set: {perplexity(log_probs)}")


# (4) Perplexity of the unigram model on the test set
log_probs = []
for word in test_sequence:
    log_probs.append(math.log(unigram_counts[word] / n_train))

test_perplexity = perplexity(log_probs)
print(f"\nunigram perplexity, test set: {test_perplexity:.1f}")

unigram perplexity, validation set: 996.5

validation pairs never seen in training: 46338
out of 213885, or 21.7%
bigram perplexity, validation set: inf

unigram perplexity, test set: 941.7

2.3 Curse of dimensionality

Zero counts arrive fast with words taken from a training corpus. With a vocabulary of 33,000 words, there are about 1.1 billion possible word pairs, but 2 million training words show at most 2 million of them (in exercise 2.1 we had about 618,000 distinct pairs, so 0.06%). Unseen pairs already appear in held-out text at n = 2 or 3. This is a manifestation of the curse of dimensionality: the number of possible contexts grows exponentially as $V^{n-1}$ while the training text stays the same size.

from datasets import load_dataset

wikitext = load_dataset("Salesforce/wikitext", "wikitext-2-v1")


# (1) Build the train sequence by splitting every line on spaces
# [Copied from the solution of 2.1, step (1)]
train_sequence = []
for line in wikitext["train"]["text"]:
    train_sequence.extend(line.split())

print(f"text: {len(train_sequence)} words")
print(f"vocabulary: {len(set(train_sequence))} words")


# The validation and test sequences, built in the same way
# [Copied from the starter of 2.2]
val_sequence = []
for line in wikitext["validation"]["text"]:
    val_sequence.extend(line.split())

test_sequence = []
for line in wikitext["test"]["text"]:
    test_sequence.extend(line.split())

print(f"validation: {len(val_sequence)} words")
print(f"test: {len(test_sequence)} words")

text: 2051910 words
vocabulary: 33277 words
validation: 213886 words
test: 241211 words

n = 1: The island Several was a three with Coast and at 500 Stefani five game expressed 15 is oxidation Abd Beginning digital and continuing F closed down . that built weekly

n = 2: The institute . " and long , Mortimer Wheeler secured by worry over the Song military officer notable example of willows along the Richmond Chamber of the opening sequence stars

n = 3: The institute is part of the river also served as the negative critical reviews , but the studio floor were often built in 1858 on the south of Romani marked

n = 4: The institute is part of the first stone of the original route of Highway 36 was first assumed by the Department of Highways were accused of cowardice by fellow officers

n = 5: The institute is part of Florida Atlantic 's Department of Ocean Engineering which was founded in 1870 . By 20 April 1914 , when the residents passed Act to <unk>

n = 1: 0.0% never seen
n = 2: 21.7% never seen
n = 3: 60.8% never seen
n = 4: 85.8% never seen
n = 5: 95.2% never seen

from datasets import load_dataset

wikitext = load_dataset("Salesforce/wikitext", "wikitext-2-v1")


# (1) Build the train sequence by splitting every line on spaces
# [Copied from the solution of 2.1, step (1)]
train_sequence = []
for line in wikitext["train"]["text"]:
    train_sequence.extend(line.split())

print(f"text: {len(train_sequence)} words")
print(f"vocabulary: {len(set(train_sequence))} words")


# The validation and test sequences, built in the same way
# [Copied from the starter of 2.2]
val_sequence = []
for line in wikitext["validation"]["text"]:
    val_sequence.extend(line.split())

test_sequence = []
for line in wikitext["test"]["text"]:
    test_sequence.extend(line.split())

print(f"validation: {len(val_sequence)} words")
print(f"test: {len(test_sequence)} words")

text: 2051910 words
vocabulary: 33277 words
validation: 213886 words
test: 241211 words

# (1) For each n, count the n-grams in a nested dict:
# counts[n][context][word] is the number of times `word` follows
# `context`, the tuple of the n - 1 words before it.
# For n = 1, the context is the empty tuple ().
counts = {}
for n in range(1, 6):
    counts[n] = {}
    for i in range(n - 1, len(train_sequence)):
        context = tuple(train_sequence[i - n + 1:i])
        word = train_sequence[i]
        if context not in counts[n]:
            counts[n][context] = {}
        if word not in counts[n][context]:
            counts[n][context][word] = 0
        counts[n][context][word] += 1


# (2) Generate 30 words with each n, starting with "The"
import random

first_word = "The"
length = 30

for n in range(1, 6):
    random.seed(0)
    sample_words = [first_word]
    while len(sample_words) < length:
        # The last n - 1 words, or fewer for the first words
        if n == 1:
            context = ()
        else:
            context = tuple(sample_words[-(n - 1):])
        followers = counts[len(context) + 1][context]
        options, weights = list(followers), list(followers.values())
        next_word = random.choices(options, weights)[0]
        sample_words.append(next_word)
    print(f"n = {n}: " + " ".join(sample_words) + "\n")


# (3) For each n, the fraction of the n-grams of the validation
# sequence never seen in training
for n in range(1, 6):
    unseen = 0
    total = 0
    for i in range(n - 1, len(val_sequence)):
        context = tuple(val_sequence[i - n + 1:i])
        word = val_sequence[i]
        if context not in counts[n] or word not in counts[n][context]:
            unseen += 1
        total += 1
    print(f"n = {n}: {100 * unseen / total:.1f}% never seen")

n = 1: The island Several was a three with Coast and at 500 Stefani five game expressed 15 is oxidation Abd Beginning digital and continuing F closed down . that built weekly

n = 2: The institute . " and long , Mortimer Wheeler secured by worry over the Song military officer notable example of willows along the Richmond Chamber of the opening sequence stars

n = 3: The institute is part of the river also served as the negative critical reviews , but the studio floor were often built in 1858 on the south of Romani marked

n = 4: The institute is part of the first stone of the original route of Highway 36 was first assumed by the Department of Highways were accused of cowardice by fellow officers

n = 5: The institute is part of Florida Atlantic 's Department of Ocean Engineering which was founded in 1870 . By 20 April 1914 , when the residents passed Act to <unk>

n = 1: 0.0% never seen
n = 2: 21.7% never seen
n = 3: 60.8% never seen
n = 4: 85.8% never seen
n = 5: 95.2% never seen

There are several options to avoid the infinite perplexity due to zero probabilities associated with the curse of dimensionality:

• Smoothing: giving unseen sequences a small non-zero probability. The simplest is add-one smoothing (add 1 to every count), but it works badly with words: it gives too much probability to the billions of unseen pairs.
• Interpolation works better: it mixes the n-gram estimate with the (n−1)-gram estimate, using a weight tuned on validation data. The estimate is applied step-by-step (recursively) down to the unigram, and since the unigram is non-zero for every word in the vocabulary, the mix is never zero.
• More sophisticated techniques have been devised since, see for instance the Kneser-Ney below, that has long been state-of-the-art.

Smoothing deals with unseen sequences of known words. Unseen words are another problem, which WikiText-2 hides by replacing rare words with <unk>. This is our first encounter with the vocabulary problem: it comes back in section 3.2, but tokenizers (the topic of the next post) solve it.

from datasets import load_dataset

wikitext = load_dataset("Salesforce/wikitext", "wikitext-2-v1")


# (1) Build the train sequence by splitting every line on spaces
# [Copied from the solution of 2.1, step (1)]
train_sequence = []
for line in wikitext["train"]["text"]:
    train_sequence.extend(line.split())

print(f"text: {len(train_sequence)} words")
print(f"vocabulary: {len(set(train_sequence))} words")


# The validation and test sequences, built in the same way
# [Copied from the starter of 2.2]
val_sequence = []
for line in wikitext["validation"]["text"]:
    val_sequence.extend(line.split())

test_sequence = []
for line in wikitext["test"]["text"]:
    test_sequence.extend(line.split())

print(f"validation: {len(val_sequence)} words")
print(f"test: {len(test_sequence)} words")


# (1) For each n, count the n-grams in a nested dict:
# counts[n][context][word] is the number of times `word` follows
# `context`, the tuple of the n - 1 words before it.
# For n = 1, the context is the empty tuple ().
# [Copied from the solution of 2.3a, step (1)]
counts = {}
for n in range(1, 6):
    counts[n] = {}
    for i in range(n - 1, len(train_sequence)):
        context = tuple(train_sequence[i - n + 1:i])
        word = train_sequence[i]
        if context not in counts[n]:
            counts[n][context] = {}
        if word not in counts[n][context]:
            counts[n][context][word] = 0
        counts[n][context][word] += 1

text: 2051910 words
vocabulary: 33277 words
validation: 213886 words
test: 241211 words

n = 1: add-one perplexity 999.1
n = 2: add-one perplexity 2207.8
n = 3: add-one perplexity 13327.0
n = 4: add-one perplexity 26020.8
n = 5: add-one perplexity 31024.1

n = 2: weight 0.68, interpolated perplexity 345.5
n = 3: weight 0.23, interpolated perplexity 303.7
n = 4: weight 0.11, interpolated perplexity 297.3
n = 5: weight 0.09, interpolated perplexity 296.2

test perplexity, n = 5: 277.7

from datasets import load_dataset

wikitext = load_dataset("Salesforce/wikitext", "wikitext-2-v1")


# (1) Build the train sequence by splitting every line on spaces
# [Copied from the solution of 2.1, step (1)]
train_sequence = []
for line in wikitext["train"]["text"]:
    train_sequence.extend(line.split())

print(f"text: {len(train_sequence)} words")
print(f"vocabulary: {len(set(train_sequence))} words")


# The validation and test sequences, built in the same way
# [Copied from the starter of 2.2]
val_sequence = []
for line in wikitext["validation"]["text"]:
    val_sequence.extend(line.split())

test_sequence = []
for line in wikitext["test"]["text"]:
    test_sequence.extend(line.split())

print(f"validation: {len(val_sequence)} words")
print(f"test: {len(test_sequence)} words")


# (1) For each n, count the n-grams in a nested dict:
# counts[n][context][word] is the number of times `word` follows
# `context`, the tuple of the n - 1 words before it.
# For n = 1, the context is the empty tuple ().
# [Copied from the solution of 2.3a, step (1)]
counts = {}
for n in range(1, 6):
    counts[n] = {}
    for i in range(n - 1, len(train_sequence)):
        context = tuple(train_sequence[i - n + 1:i])
        word = train_sequence[i]
        if context not in counts[n]:
            counts[n][context] = {}
        if word not in counts[n][context]:
            counts[n][context][word] = 0
        counts[n][context][word] += 1

text: 2051910 words
vocabulary: 33277 words
validation: 213886 words
test: 241211 words

# (1) For each word of a sequence and each n, look up two counts
# in training: the n-gram that ends with this word, and its
# context. Start at the 5th word, so that every word has 4 words
# before it. The counts are stored in numpy arrays.
import numpy as np

context_totals = {}
for n in range(1, 6):
    context_totals[n] = {}
    for context in counts[n]:
        context_totals[n][context] = sum(counts[n][context].values())

def lookup_counts(sequence):
    ngram_count = {}
    context_count = {}
    for n in range(1, 6):
        ngram_list = []
        context_list = []
        for i in range(4, len(sequence)):
            context = tuple(sequence[i - n + 1:i])
            followers = counts[n].get(context, {})
            ngram_list.append(followers.get(sequence[i], 0))
            context_list.append(context_totals[n].get(context, 0))
        ngram_count[n] = np.array(ngram_list)
        context_count[n] = np.array(context_list)
    return ngram_count, context_count

val_ngram, val_context = lookup_counts(val_sequence)

def perplexity(probs):
    return np.exp(-np.mean(np.log(probs)))


# (2) Add-one smoothing: add 1 to the count of every possible
# n-gram, so the count of each context grows by V, the size of
# the vocabulary
V = len(set(train_sequence))
add_one = []
for n in range(1, 6):
    probs = (val_ngram[n] + 1) / (val_context[n] + V)
    add_one.append(perplexity(probs))
    print(f"n = {n}: add-one perplexity {add_one[-1]:.1f}")


# (3) Interpolation: q_n = w * p_n + (1 - w) * q_(n-1), where p_n
# is the probability from the n-gram counts. When the context was
# never seen in training, q_n = q_(n-1).
def interpolate(ngram_count, context_count, weights):
    q = ngram_count[1] / context_count[1]   # n = 1
    for n in range(2, len(weights) + 2):
        w = weights[n - 2]   # weights[0] is the weight of n = 2
        seen = context_count[n] > 0
        p = np.zeros(len(q))
        p[seen] = ngram_count[n][seen] / context_count[n][seen]
        q = np.where(seen, w * p + (1 - w) * q, q)
    return q

# Tune the weight of each n in turn, by a grid search
weights = []
interpolation = [perplexity(interpolate(val_ngram, val_context, []))]
print()
for n in range(2, 6):
    best_w, best_perplexity = 0, np.inf
    for k in range(1, 100):
        w = k / 100
        q = interpolate(val_ngram, val_context, weights + [w])
        if perplexity(q) < best_perplexity:
            best_w, best_perplexity = w, perplexity(q)
    weights.append(best_w)
    interpolation.append(best_perplexity)
    print(f"n = {n}: weight {best_w}, "
          f"interpolated perplexity {best_perplexity:.1f}")


# (4) Test perplexity of the interpolated 5-gram model
test_ngram, test_context = lookup_counts(test_sequence)
q = interpolate(test_ngram, test_context, weights)
test_perplexity = perplexity(q)
print(f"\ntest perplexity, n = 5: {test_perplexity:.1f}")

n = 1: add-one perplexity 999.1
n = 2: add-one perplexity 2207.8
n = 3: add-one perplexity 13327.0
n = 4: add-one perplexity 26020.8
n = 5: add-one perplexity 31024.1

n = 2: weight 0.68, interpolated perplexity 345.5
n = 3: weight 0.23, interpolated perplexity 303.7
n = 4: weight 0.11, interpolated perplexity 297.3
n = 5: weight 0.09, interpolated perplexity 296.2

test perplexity, n = 5: 277.7

import matplotlib.pyplot as plt

orders = [1, 2, 3, 4, 5]
plt.figure(figsize=(5, 3.5))
plt.plot(orders, add_one, "o-", label="add-one")
plt.plot(orders, interpolation, "o-", label="interpolation")
plt.yscale("log")
plt.xticks(orders)
plt.xlabel("n")
plt.ylabel("validation perplexity")
plt.legend()
plt.show()

If you want to dig deeper, below are a few bonus exercises.

3. Classification with bag of words

Let’s now leave language modeling for a while, and turn to the other task of this post: classifying movie reviews as positive or negative.

3.1 The pattern: encoder → fixed-size representation → head

In a classification task, such as the sentiment analysis of movie reviews, the input text has a variable length. And we can’t rely on the trick we used for the Markov language model, which is to keep only the last $n$ words. Indeed there is no reason to assume that the important information will be in the last $n$ words, especially if $n$ is less than 3 or 4!

Since all classical machine learning methods (logistic regression, feedforward networks, tree-based methods…) require an input of fixed size, we need a way to go from a variable-length piece of text to a fixed-size representation of the content of this text.

In general, a classification model in NLP can be split into two steps: the encoder, which produces a fixed-size representation of the text (sometimes called a latent representation), and the classification head, which takes this representation and produces the probabilities of the classes.

This is illustrated below.

Note that the n-gram models of section 2 already follow this pattern, for language modeling: the encoder keeps the last n − 1 words of the text, a representation of fixed size, and the head is the table of counts, which gives the probabilities of the next word.

So what are our options to build a fixed-size representation of a review? Let’s start with the simplest one.

3.2 Bag of words

Consider this review:

Great acting, great lighting, and a flabbergasting soundtrack, but not even Zendaya could save this boring, boring plot.

We can simply count the occurrences of each word.

We can’t use this table directly as a representation, because its size (and the words in it) changes from one review to the next. The solution is to choose a vocabulary of V words beforehand, for instance the V most frequent words of the training reviews. Each review then becomes a vector of size V, whose entry number $v$ is the count $C_v$ of the $v$-th word of the vocabulary in the review.

Almost all the entries of this vector are zeros: the median IMDB review has 178 words, while the vocabulary has thousands of them. It is a sparse vector. You can also see it as the sum of the one-hot vectors of the words of the review, which has the same size V whatever the length of the review. We have our fixed-size representation, and we can feed it to any classical classifier.

This representation is called a bag of words: it is as if we had cut the review into words and thrown them into a bag. We know how many times each word appears, but we have lost the order in which they appear (keep that in mind, it will come back).

Of course, some words will not be in the vocabulary, like “Zendaya” in our example. They are simply ignored. With V = 10,000, “flabbergasting” is most likely ignored too: it appears in only 2 of the 25,000 training reviews of IMDB.

For the head, the simplest choice is a logistic regression. It gives a weight $w_v$ to each word of the vocabulary, and computes the probability that the review is positive as

where $b$ is a bias, and the sigmoid function $\sigma$ turns the score into a probability between 0 and 1. In other words, each occurrence of a word pushes the score up or down by the weight of this word, and the model says “positive” when the total is above zero. The weights are learned on labeled reviews, by minimizing the cross-entropy loss of section 2.2 (with two classes, instead of a whole vocabulary of next words).

You can play with such a model below: it is the one you will train in exercise 3.2. Edit the review and watch its count vector change. To show the limits of this approach, try to write a very negative review that gets classified as positive, for instance using sarcasm.

Let’s train such a model on IMDB.

from datasets import load_dataset

imdb = load_dataset("stanfordnlp/imdb")

example = imdb["train"][0]
print(f"label {example['label']} (0 = negative, 1 = positive)")
print(example["text"][:70])

label 0 (0 = negative, 1 = positive)
I rented I AM CURIOUS-YELLOW from my video store because of all the co

train: 20000 reviews
validation: 5000 reviews
test: 25000 reviews

C = 0.01: validation accuracy 0.883
C = 0.03: validation accuracy 0.887
C = 0.1: validation accuracy 0.889
C = 0.3: validation accuracy 0.886
C = 1: validation accuracy 0.875
C = 3: validation accuracy 0.870
C = 10: validation accuracy 0.862

test accuracy, C = 0.1: 0.876

negative: worst waste disappointment awful poorly boring lacks fails avoid mess
positive: 7 8 perfect excellent refreshing wonderfully superb amazing favorite rare

from datasets import load_dataset

imdb = load_dataset("stanfordnlp/imdb")

example = imdb["train"][0]
print(f"label {example['label']} (0 = negative, 1 = positive)")
print(example["text"][:70])

label 0 (0 = negative, 1 = positive)
I rented I AM CURIOUS-YELLOW from my video store because of all the co

# (1) Hold out 5,000 training reviews as a validation set, and
# replace the HTML line breaks with spaces

def clean(texts):
    return [text.replace("<br />", " ") for text in texts]

split = imdb["train"].train_test_split(test_size=5000, seed=0)
train_texts = clean(split["train"]["text"])
val_texts = clean(split["test"]["text"])
test_texts = clean(imdb["test"]["text"])
train_labels = split["train"]["label"]
val_labels = split["test"]["label"]
test_labels = imdb["test"]["label"]

print(f"train: {len(train_texts)} reviews")
print(f"validation: {len(val_texts)} reviews")
print(f"test: {len(test_texts)} reviews")


# (2) Count the words of each review, over the 10,000 most
# frequent words of the training reviews. The pattern makes every
# run of letters or digits a word, even a single letter like "a".
from sklearn.feature_extraction.text import CountVectorizer

vectorizer = CountVectorizer(max_features=10000,
                             token_pattern=r"\b\w+\b")
X_train = vectorizer.fit_transform(train_texts)
X_val = vectorizer.transform(val_texts)
X_test = vectorizer.transform(test_texts)


# (3) Train a logistic regression for several values of C, the
# inverse of the strength of the regularization, and keep the best
# model on the validation set
from sklearn.linear_model import LogisticRegression

print()
best_accuracy = 0
for C in [0.01, 0.03, 0.1, 0.3, 1, 3, 10]:
    model = LogisticRegression(C=C, max_iter=1000)
    model.fit(X_train, train_labels)
    accuracy = model.score(X_val, val_labels)
    print(f"C = {C}: validation accuracy {accuracy:.3f}")
    if accuracy > best_accuracy:
        best_accuracy, best_C, best_model = accuracy, C, model


# (4) Measure the test accuracy of the best model
test_accuracy = best_model.score(X_test, test_labels)
print(f"\ntest accuracy, C = {best_C}: {test_accuracy:.3f}")


# (5) Print the words with the largest weights, toward negative
# and toward positive. np.argsort sorts the weights in increasing
# order and returns their positions.
import numpy as np

words = vectorizer.get_feature_names_out()
weights = best_model.coef_[0]   # one weight per word
order = np.argsort(weights)
most_negative = [words[i] for i in order[:10]]
most_positive = [words[i] for i in order[-10:]]
most_positive.reverse()
print("\nnegative:", " ".join(most_negative))
print("positive:", " ".join(most_positive))

train: 20000 reviews
validation: 5000 reviews
test: 25000 reviews

C = 0.01: validation accuracy 0.883
C = 0.03: validation accuracy 0.887
C = 0.1: validation accuracy 0.889
C = 0.3: validation accuracy 0.886
C = 1: validation accuracy 0.875
C = 3: validation accuracy 0.870
C = 10: validation accuracy 0.862

test accuracy, C = 0.1: 0.876

negative: worst waste disappointment awful poorly boring lacks fails avoid mess
positive: 7 8 perfect excellent refreshing wonderfully superb amazing favorite rare

Learning the words from the data works much better than choosing them by hand, and this was one of the first lessons of sentiment classification by machine learning.

3.3 TF-IDF weighting

In the previous example, words like “a” and “and” are certainly not very informative, because they are very common: “the” appears in 99% of the training reviews of IMDB, “a” and “and” in 97% of them. On the contrary, “boring” appears in only 6% of the reviews, and certainly carries useful information.

A solution to improve the bag-of-words representation is to down-weight the words that appear in most documents, and up-weight the rare ones. This is what the inverse document frequency does: multiply the count of each word by $-\log$ of the fraction of documents that contain it,

where $N$ is the number of documents and $N_v$ the number of documents that contain the word $v$. The entry $v$ of the vector of a document becomes $C_v \times \text{idf}(v)$, hence the name TF-IDF, for “term frequency times inverse document frequency”. With a base-2 logarithm, “the” gets a weight of 0.01, almost nothing, “boring” a weight of 4, and “flabbergasting”, in 2 reviews out of 25,000, would get 13.6.

Another simple variant keeps only the presence of each word: 1 if the word is in the review, 0 if not. This is what worked best for Pang et al. (see the margin note of section 3.2). Let’s compare these weightings on IMDB.

from datasets import load_dataset

imdb = load_dataset("stanfordnlp/imdb")


# (1) Hold out 5,000 training reviews as a validation set, and
# replace the HTML line breaks with spaces
# [Copied from the solution of 3.2, step (1)]

def clean(texts):
    return [text.replace("<br />", " ") for text in texts]

split = imdb["train"].train_test_split(test_size=5000, seed=0)
train_texts = clean(split["train"]["text"])
val_texts = clean(split["test"]["text"])
test_texts = clean(imdb["test"]["text"])
train_labels = split["train"]["label"]
val_labels = split["test"]["label"]
test_labels = imdb["test"]["label"]

print(f"train: {len(train_texts)} reviews")
print(f"validation: {len(val_texts)} reviews")
print(f"test: {len(test_texts)} reviews")

train: 20000 reviews
validation: 5000 reviews
test: 25000 reviews

counts: C = 0.1, test accuracy 0.876
presence: C = 0.03, test accuracy 0.882
TF-IDF: C = 3, test accuracy 0.884

from datasets import load_dataset

imdb = load_dataset("stanfordnlp/imdb")


# (1) Hold out 5,000 training reviews as a validation set, and
# replace the HTML line breaks with spaces
# [Copied from the solution of 3.2, step (1)]

def clean(texts):
    return [text.replace("<br />", " ") for text in texts]

split = imdb["train"].train_test_split(test_size=5000, seed=0)
train_texts = clean(split["train"]["text"])
val_texts = clean(split["test"]["text"])
test_texts = clean(imdb["test"]["text"])
train_labels = split["train"]["label"]
val_labels = split["test"]["label"]
test_labels = imdb["test"]["label"]

print(f"train: {len(train_texts)} reviews")
print(f"validation: {len(val_texts)} reviews")
print(f"test: {len(test_texts)} reviews")

train: 20000 reviews
validation: 5000 reviews
test: 25000 reviews

# (1) The three weightings, over the 10,000 most frequent words
# of the training reviews
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.feature_extraction.text import TfidfVectorizer

V = 10000
pattern = r"\b\w+\b"   # every word, even a single letter
vectorizers = {
    "counts": CountVectorizer(max_features=V, token_pattern=pattern),
    "presence": CountVectorizer(max_features=V, token_pattern=pattern,
                                binary=True),
    "TF-IDF": TfidfVectorizer(max_features=V, token_pattern=pattern),
}


# (2) For each weighting, choose C on the validation set as in
# exercise 3.2, then measure the test accuracy of the best model
from sklearn.linear_model import LogisticRegression

test_accuracies = {}
for name in vectorizers:
    vectorizer = vectorizers[name]
    X_train = vectorizer.fit_transform(train_texts)
    X_val = vectorizer.transform(val_texts)
    X_test = vectorizer.transform(test_texts)

    best_accuracy = 0
    for C in [0.01, 0.03, 0.1, 0.3, 1, 3, 10]:
        model = LogisticRegression(C=C, max_iter=1000)
        model.fit(X_train, train_labels)
        accuracy = model.score(X_val, val_labels)
        if accuracy > best_accuracy:
            best_accuracy, best_C, best_model = accuracy, C, model

    test_accuracies[name] = best_model.score(X_test, test_labels)
    print(f"{name}: C = {best_C}, "
          f"test accuracy {test_accuracies[name]:.3f}")

counts: C = 0.1, test accuracy 0.876
presence: C = 0.03, test accuracy 0.882
TF-IDF: C = 3, test accuracy 0.884

These numbers are typical of the bag of words on IMDB: the paper that introduced the dataset reports 87.8% with the presence of the words (Maas et al., 2011). A strong bag-of-words baseline by Wang and Manning reaches 91.2% (Wang & Manning, 2012). It adds the pairs of consecutive words to the vocabulary, so that “not good” becomes a word of its own, and mixes a Naive Bayes classifier with an SVM. Pairs of words bring back a little of the word order, and this order is precisely what the bag of words is missing.

3.4 The limit

Consider these two reviews:

A: Excellent movie, awesome soundtrack.

B: Superb film, wonderful score.

They say essentially the same thing, but with completely different words. So they get completely orthogonal representations in the bag of words: no entry is non-zero in both vectors.

For the bag of words, “superb” is as different from “excellent” as it is from “boring”. The representation does not help the head: the head must learn the weight of each word separately, from the labeled reviews that contain this word. For a frequent word like “excellent”, found in 1,780 training reviews, this works fine. But a rare word like “mesmerizing” (62 reviews) gets a weight learned from a handful of examples, and a word outside the vocabulary, like “flabbergasting”, gets no weight at all.

The second limit is in the name: a bag of words forgets the order of the words. These two reviews have exactly the same words, hence exactly the same vector, so the model must give them the same probability:

A: I expected it to be terrible, but it was great.

B: I expected it to be great, but it was terrible.

The same goes for negation. In “not bad at all”, the model sees “not”, “bad”, “at” and “all” separately, and “bad” has a strong negative weight. And sarcasm is even worse, since it uses positive words to say something negative.

To follow these limits through the post, I wrote a small set of hard reviews. They are short, and their sentiment is obvious to any human reader. They are grouped by kind of difficulty: negation, contrast, sarcasm, word order, synonyms and rare words. We will run every IMDB model of the post on them, starting with our bag of words.

from datasets import load_dataset

imdb = load_dataset("stanfordnlp/imdb")


# (1) Hold out 5,000 training reviews as a validation set, and
# replace the HTML line breaks with spaces
# [Copied from the solution of 3.2, step (1)]

def clean(texts):
    return [text.replace("<br />", " ") for text in texts]

split = imdb["train"].train_test_split(test_size=5000, seed=0)
train_texts = clean(split["train"]["text"])
val_texts = clean(split["test"]["text"])
test_texts = clean(imdb["test"]["text"])
train_labels = split["train"]["label"]
val_labels = split["test"]["label"]
test_labels = imdb["test"]["label"]

print(f"train: {len(train_texts)} reviews")
print(f"validation: {len(val_texts)} reviews")
print(f"test: {len(test_texts)} reviews")


# (2) Count the words of each review, over the 10,000 most
# frequent words of the training reviews. The pattern makes every
# run of letters or digits a word, even a single letter like "a".
# [Copied from the solution of 3.2, step (2)]
from sklearn.feature_extraction.text import CountVectorizer

vectorizer = CountVectorizer(max_features=10000,
                             token_pattern=r"\b\w+\b")
X_train = vectorizer.fit_transform(train_texts)
X_val = vectorizer.transform(val_texts)
X_test = vectorizer.transform(test_texts)


# ----------------------
#  New in this exercise
# ----------------------
# The logistic regression of exercise 3.2, with C = 0.1, the
# value chosen on the validation set
from sklearn.linear_model import LogisticRegression

model = LogisticRegression(C=0.1, max_iter=1000)
model.fit(X_train, train_labels)

# The hard reviews: (review, label), with 1 for positive
hard_reviews = [
    # Negation
    ("Not bad at all, actually.", 1),
    ("Nothing about this movie is good.", 0),
    ("I wouldn't call it a masterpiece, but I didn't regret "
     "a minute.", 1),
    # Contrast
    ("Great acting, great lighting and a flabbergasting soundtrack, "
     "but not even Zendaya could save this boring, boring plot.", 0),
    ("The first hour is slow and the dialogue is clumsy, but the "
     "ending makes it all worth it.", 1),
    ("Everyone told me it would be the film of the year: great "
     "cast, amazing trailer, brilliant director. What a "
     "disappointment.", 0),
    # Sarcasm
    ("Wow, what a masterpiece. Two hours of pure brilliance, and I "
     "only checked my watch twenty times. The acting was so "
     "convincing that I truly believed the actors wanted to be "
     "somewhere else. A perfect film if you love naps.", 0),
    ("Brilliant. Another sequel nobody asked for, with the same "
     "jokes as the first one.", 0),
    # The same words in a different order
    ("I expected it to be terrible, but it was great.", 1),
    ("I expected it to be great, but it was terrible.", 0),
    # Synonyms, no word in common
    ("Excellent movie, awesome soundtrack.", 1),
    ("Superb film, wonderful score.", 1),
    # Rare words
    ("A flabbergasting, mesmerizing tour de force.", 1),
]

print(f"{len(hard_reviews)} hard reviews")

train: 20000 reviews
validation: 5000 reviews
test: 25000 reviews
13 hard reviews

label     p(positive)  right  review
positive  0.335        NO     Not bad at all, actually.
negative  0.423        yes    Nothing about this movie is good.
positive  0.470        NO     I wouldn't call it a masterpiece, b…
negative  0.109        yes    Great acting, great lighting and a …
positive  0.513        yes    The first hour is slow and the dial…
negative  0.685        NO     Everyone told me it would be the fi…
negative  0.761        NO     Wow, what a masterpiece. Two hours …
negative  0.598        NO     Brilliant. Another sequel nobody as…
positive  0.495        NO     I expected it to be terrible, but i…
negative  0.495        yes    I expected it to be great, but it w…
positive  0.779        yes    Excellent movie, awesome soundtrack.
positive  0.810        yes    Superb film, wonderful score.
positive  0.521        yes    A flabbergasting, mesmerizing tour …

7 right out of 13

from datasets import load_dataset

imdb = load_dataset("stanfordnlp/imdb")


# (1) Hold out 5,000 training reviews as a validation set, and
# replace the HTML line breaks with spaces
# [Copied from the solution of 3.2, step (1)]

def clean(texts):
    return [text.replace("<br />", " ") for text in texts]

split = imdb["train"].train_test_split(test_size=5000, seed=0)
train_texts = clean(split["train"]["text"])
val_texts = clean(split["test"]["text"])
test_texts = clean(imdb["test"]["text"])
train_labels = split["train"]["label"]
val_labels = split["test"]["label"]
test_labels = imdb["test"]["label"]

print(f"train: {len(train_texts)} reviews")
print(f"validation: {len(val_texts)} reviews")
print(f"test: {len(test_texts)} reviews")


# (2) Count the words of each review, over the 10,000 most
# frequent words of the training reviews. The pattern makes every
# run of letters or digits a word, even a single letter like "a".
# [Copied from the solution of 3.2, step (2)]
from sklearn.feature_extraction.text import CountVectorizer

vectorizer = CountVectorizer(max_features=10000,
                             token_pattern=r"\b\w+\b")
X_train = vectorizer.fit_transform(train_texts)
X_val = vectorizer.transform(val_texts)
X_test = vectorizer.transform(test_texts)


# ----------------------
#  New in this exercise
# ----------------------
# The logistic regression of exercise 3.2, with C = 0.1, the
# value chosen on the validation set
from sklearn.linear_model import LogisticRegression

model = LogisticRegression(C=0.1, max_iter=1000)
model.fit(X_train, train_labels)

# The hard reviews: (review, label), with 1 for positive
hard_reviews = [
    # Negation
    ("Not bad at all, actually.", 1),
    ("Nothing about this movie is good.", 0),
    ("I wouldn't call it a masterpiece, but I didn't regret "
     "a minute.", 1),
    # Contrast
    ("Great acting, great lighting and a flabbergasting soundtrack, "
     "but not even Zendaya could save this boring, boring plot.", 0),
    ("The first hour is slow and the dialogue is clumsy, but the "
     "ending makes it all worth it.", 1),
    ("Everyone told me it would be the film of the year: great "
     "cast, amazing trailer, brilliant director. What a "
     "disappointment.", 0),
    # Sarcasm
    ("Wow, what a masterpiece. Two hours of pure brilliance, and I "
     "only checked my watch twenty times. The acting was so "
     "convincing that I truly believed the actors wanted to be "
     "somewhere else. A perfect film if you love naps.", 0),
    ("Brilliant. Another sequel nobody asked for, with the same "
     "jokes as the first one.", 0),
    # The same words in a different order
    ("I expected it to be terrible, but it was great.", 1),
    ("I expected it to be great, but it was terrible.", 0),
    # Synonyms, no word in common
    ("Excellent movie, awesome soundtrack.", 1),
    ("Superb film, wonderful score.", 1),
    # Rare words
    ("A flabbergasting, mesmerizing tour de force.", 1),
]

print(f"{len(hard_reviews)} hard reviews")

train: 20000 reviews
validation: 5000 reviews
test: 25000 reviews
13 hard reviews

# (1) Count the words of the hard reviews over the vocabulary of
# the model, and compute their probability of being positive
hard_texts = [review for review, label in hard_reviews]
X_hard = vectorizer.transform(hard_texts)
probabilities = model.predict_proba(X_hard)
p_positive = probabilities[:, 1]   # column 0: negative, 1: positive


# (2) Print a table: the model is right when it gives more than
# 0.5 to the label of the review
names = ["negative", "positive"]
print("label     p(positive)  right  review")
right_count = 0
for (review, label), p in zip(hard_reviews, p_positive):
    right = (p > 0.5) == (label == 1)
    if right:
        right_count += 1
    mark = "yes" if right else "NO"
    short = review if len(review) <= 36 else review[:35] + "…"
    print(f"{names[label]:9} {p:.3f}        {mark:5}  {short}")
print(f"\n{right_count} right out of {len(hard_reviews)}")

label     p(positive)  right  review
positive  0.335        NO     Not bad at all, actually.
negative  0.423        yes    Nothing about this movie is good.
positive  0.470        NO     I wouldn't call it a masterpiece, b…
negative  0.109        yes    Great acting, great lighting and a …
positive  0.513        yes    The first hour is slow and the dial…
negative  0.685        NO     Everyone told me it would be the fi…
negative  0.761        NO     Wow, what a masterpiece. Two hours …
negative  0.598        NO     Brilliant. Another sequel nobody as…
positive  0.495        NO     I expected it to be terrible, but i…
negative  0.495        yes    I expected it to be great, but it w…
positive  0.779        yes    Excellent movie, awesome soundtrack.
positive  0.810        yes    Superb film, wonderful score.
positive  0.521        yes    A flabbergasting, mesmerizing tour …

7 right out of 13

How can we do better? For the first limit, we need a representation where similar words get similar vectors, so that what the model learns about “excellent” also helps with “superb”, and even with words it has rarely seen. This is the topic of the next section. For the word order, we will have to wait until section 7.

If you want to dig deeper, below are a few bonus exercises.

4. Dense word embeddings

At the end of section 3, we saw the first limit of the bag of words: each word has its own dimension, so for the model, “superb” is as different from “excellent” as it is from “boring”. Let’s fix this.

4.1 The embedding matrix

The idea is to represent each word by a dense vector of real numbers, in a space whose dimension D is much smaller than the size V of the vocabulary: a few hundred dimensions (for instance $D = 300$) for tens of thousands of words. This vector is called the embedding of the word.

The embeddings of all the words are stored in an embedding matrix $W$, with one column per word of the vocabulary:

Looking up the embedding of a word is the same as multiplying $W$ by the one-hot vector of this word: the product selects the column of the word.

The benefit of dense embeddings over the sparse vectors of the bag of words is that we can compare them, and measure how similar two words are. The usual measure is the cosine similarity, the cosine of the angle between the two vectors, which does not depend on their lengths:

It is 1 when the two vectors point in the same direction, 0 when they are orthogonal, and −1 when they point in opposite directions. Note that the one-hot vectors of two different words are always orthogonal: in the bag of words, the similarity between two different words is always 0.

Let’s assume for now that we have a good embedding matrix (we will see how to get one, and as you might guess, we will learn it). We can hope that similar words get similar vectors: a high similarity between “excellent” and “superb”, but a low one between “ball” and “crocodile”. This is what makes a good embedding: the similarity between the vectors reflects the similarity between the meanings of the words. A model that has learned something about “excellent” then knows something about “superb” too.

Now, simply using word embeddings does not solve our problem of variable input size. We replace the L words of a text with L vectors of size D: this is still not a representation of fixed size! So we need a way to aggregate these L vectors into a single vector, whose size does not depend on L. Here are three simple options:

• the average of the L vectors, of size D;
• a weighted average, to give more importance to some words, also of size D;
• the concatenation of the vectors of the last n − 1 words only, of size (n − 1) × D, as the n-gram models of section 2 did with the words themselves.

The concatenation keeps the order of the last words, but forgets everything before them. This suits language modeling, where the next word depends mostly on the last ones, so this is where we start.

4.2 Concatenation → Bengio’s neural language model

Let’s go back to language modeling for a moment. With the n-gram models of section 2, we assumed that the probability of the next word depends only on the n − 1 previous words. We can keep this assumption, but replace the table of counts with a neural network, whose input is the concatenation of the embeddings of the n − 1 previous words: a vector of fixed size (n − 1) × D.

This is the idea of the influential paper of Bengio et al. from 2003, which can be considered as the first neural language model. Its architecture is simple: look up the embeddings $e_{L-n+2}, \dots, e_L$ of the last n − 1 words in the matrix $W$, concatenate them into a vector $c$, then feed $c$ into a feedforward network with one hidden layer:

where $A$ and $b$ are the weights and the biases of the hidden layer, and $U$ and $d$ those of the output layer. The output layer gives one score $z_v$ per word $v$ of the vocabulary, and the softmax, $\text{softmax}(z)_v = e^{z_v} / \sum_{w} e^{z_w}$, turns these V scores into probabilities, positive and summing to 1, as the sigmoid of section 3.2 did for two classes.

The embedding matrix $W$ is a parameter of the model, like $A$, $b$, $U$ and $d$: the embeddings and the weights of the network are learned jointly, by minimizing the cross-entropy loss of section 2.2 on the training text. At each step, the gradient of the loss flows back through the network to the columns of $W$ of the words of the context, and moves them.

I’ll assume here that you know how to train a neural network with PyTorch. If not, the course of Andrej Karpathy is a great place to start, and its third lecture builds a model of this kind, on characters.

optimizer = torch.optim.Adam(model.parameters(), lr=1e-3)
for epoch in range(n_epochs):
    order = torch.randperm(len(targets))  # shuffle the examples
    for start in range(0, len(order), batch_size):
        batch = order[start:start + batch_size]
        scores = model(inputs[batch])
        loss = F.cross_entropy(scores, targets[batch])
        optimizer.zero_grad()
        loss.backward()   # compute the gradients
        optimizer.step()  # update the parameters

Why would this work better than counts? Remember the curse of dimensionality of section 2.3: most contexts of 3 or 4 words never appear in the training text, and for the counts, an unseen context is a dead end. The neural model is not stuck: if it has seen “the cat is walking”, and if “dog” has an embedding close to the one of “cat”, then it already knows something about “the dog is walking”. And similar words do get similar embeddings, because they appear in similar contexts and must lead to similar predictions. The model generalizes from the contexts it has seen to the contexts it has never seen.

Let’s train it on WikiText-2, and compare it with the n-gram models of section 2. The model has many more parameters than the logistic regression of section 3, and it overfits after a few epochs, so we choose the number of epochs on the validation set.

from datasets import load_dataset

wikitext = load_dataset("Salesforce/wikitext", "wikitext-2-v1")


# (1) Build the train sequence by splitting every line on spaces
# [Copied from the solution of 2.1, step (1)]
train_sequence = []
for line in wikitext["train"]["text"]:
    train_sequence.extend(line.split())

print(f"text: {len(train_sequence)} words")
print(f"vocabulary: {len(set(train_sequence))} words")


# The validation and test sequences, built in the same way
# [Copied from the starter of 2.2]
val_sequence = []
for line in wikitext["validation"]["text"]:
    val_sequence.extend(line.split())

test_sequence = []
for line in wikitext["test"]["text"]:
    test_sequence.extend(line.split())

print(f"validation: {len(val_sequence)} words")
print(f"test: {len(test_sequence)} words")


# ----------------------
#  New in this exercise
# ----------------------
# Give each word of the vocabulary an index
vocabulary = sorted(set(train_sequence))
word_index = {word: i for i, word in enumerate(vocabulary)}

# Turn a sequence into (context, next word) pairs of indices:
# row i of contexts holds the 3 words before the word targets[i]
import torch

context_size = 3

def make_pairs(sequence):
    indices = [word_index[word] for word in sequence]
    contexts = [indices[i - context_size:i]
                for i in range(context_size, len(indices))]
    targets = indices[context_size:]
    return torch.tensor(contexts), torch.tensor(targets)

train_contexts, train_targets = make_pairs(train_sequence)
val_contexts, val_targets = make_pairs(val_sequence)
test_contexts, test_targets = make_pairs(test_sequence)

print(f"train: {len(train_targets)} pairs")
context = [vocabulary[i] for i in train_contexts[30].tolist()]
print(f"example: {context} -> {vocabulary[train_targets[30]]}")

text: 2051910 words
vocabulary: 33277 words
validation: 213886 words
test: 241211 words
train: 2051907 pairs
example: ['Valkyria', 'Chronicles', 'III'] -> outside

epoch 1: validation perplexity 260.1
epoch 2: validation perplexity 226.2
epoch 3: validation perplexity 223.9
epoch 4: validation perplexity 228.5

test perplexity, epoch 3: 208.5

three: two, four, five, eight, six
he: she, He, Torres, McCall, Colby
city: town, park, community, sightings, formations
film: book, novel, album, What, bird
excellent: actual, reduce, ultimate, ideological, immense
terrible: my, ought, interesting, wrong, physical

from datasets import load_dataset

wikitext = load_dataset("Salesforce/wikitext", "wikitext-2-v1")


# (1) Build the train sequence by splitting every line on spaces
# [Copied from the solution of 2.1, step (1)]
train_sequence = []
for line in wikitext["train"]["text"]:
    train_sequence.extend(line.split())

print(f"text: {len(train_sequence)} words")
print(f"vocabulary: {len(set(train_sequence))} words")


# The validation and test sequences, built in the same way
# [Copied from the starter of 2.2]
val_sequence = []
for line in wikitext["validation"]["text"]:
    val_sequence.extend(line.split())

test_sequence = []
for line in wikitext["test"]["text"]:
    test_sequence.extend(line.split())

print(f"validation: {len(val_sequence)} words")
print(f"test: {len(test_sequence)} words")


# ----------------------
#  New in this exercise
# ----------------------
# Give each word of the vocabulary an index
vocabulary = sorted(set(train_sequence))
word_index = {word: i for i, word in enumerate(vocabulary)}

# Turn a sequence into (context, next word) pairs of indices:
# row i of contexts holds the 3 words before the word targets[i]
import torch

context_size = 3

def make_pairs(sequence):
    indices = [word_index[word] for word in sequence]
    contexts = [indices[i - context_size:i]
                for i in range(context_size, len(indices))]
    targets = indices[context_size:]
    return torch.tensor(contexts), torch.tensor(targets)

train_contexts, train_targets = make_pairs(train_sequence)
val_contexts, val_targets = make_pairs(val_sequence)
test_contexts, test_targets = make_pairs(test_sequence)

print(f"train: {len(train_targets)} pairs")
context = [vocabulary[i] for i in train_contexts[30].tolist()]
print(f"example: {context} -> {vocabulary[train_targets[30]]}")

text: 2051910 words
vocabulary: 33277 words
validation: 213886 words
test: 241211 words
train: 2051907 pairs
example: ['Valkyria', 'Chronicles', 'III'] -> outside

# (1) Build the model: look up the embeddings of the 3 words of
# the context, concatenate them, then a hidden layer (tanh) and
# one score per word of the vocabulary. Start from small
# embeddings: with the default initialization, of size 1, the
# rare words would keep their random vectors.
from torch import nn

V = len(vocabulary)
D = 100   # size of the embeddings
H = 200   # size of the hidden layer
torch.manual_seed(0)
model = nn.Sequential(
    nn.Embedding(V, D),   # (batch, 3) -> (batch, 3, D)
    nn.Flatten(),         # concatenation: (batch, 3 * D)
    nn.Linear(context_size * D, H),
    nn.Tanh(),
    nn.Linear(H, V),      # one score per word
)
nn.init.normal_(model[0].weight, std=0.1)

# Run on the GPU if there is one
device = "cuda" if torch.cuda.is_available() else "cpu"
model = model.to(device)


# (2) The perplexity of a model on a set of pairs: the exponential
# of the average cross-entropy loss. F.cross_entropy applies the
# softmax to the scores, then computes the loss of section 2.2.
import math
import torch.nn.functional as F

def perplexity(model, contexts, targets):
    total_loss = 0
    with torch.no_grad():
        for start in range(0, len(targets), 10000):
            scores = model(contexts[start:start + 10000].to(device))
            batch_targets = targets[start:start + 10000].to(device)
            total_loss += F.cross_entropy(scores, batch_targets,
                                          reduction="sum").item()
    return math.exp(total_loss / len(targets))


# (3) Train with Adam on batches of 512 pairs. After each epoch,
# measure the validation perplexity, and keep a copy of the best
# model.
import copy

optimizer = torch.optim.Adam(model.parameters(), lr=1e-3)
batch_size = 512
best_perplexity = math.inf
for epoch in range(4):
    order = torch.randperm(len(train_targets))   # shuffled pairs
    for start in range(0, len(order), batch_size):
        batch = order[start:start + batch_size]
        scores = model(train_contexts[batch].to(device))
        batch_targets = train_targets[batch].to(device)
        loss = F.cross_entropy(scores, batch_targets)
        optimizer.zero_grad()
        loss.backward()
        optimizer.step()
    val_perplexity = perplexity(model, val_contexts, val_targets)
    print(f"epoch {epoch + 1}: validation perplexity "
          f"{val_perplexity:.1f}")
    if val_perplexity < best_perplexity:
        best_perplexity, best_epoch = val_perplexity, epoch + 1
        best_model = copy.deepcopy(model)


# (4) Test perplexity of the best model
test_perplexity = perplexity(best_model, test_contexts, test_targets)
print(f"\ntest perplexity, epoch {best_epoch}: {test_perplexity:.1f}")


# (5) The nearest neighbors of a few words. nn.Embedding stores W
# transposed: row i is the embedding of word i. Divide each row by
# its length, so that a dot product is a cosine similarity.
embeddings = best_model[0].weight.detach().cpu()
embeddings = embeddings / embeddings.norm(dim=1, keepdim=True)

print()
for word in ["three", "he", "city", "film", "excellent", "terrible"]:
    similarities = embeddings @ embeddings[word_index[word]]
    ranking = similarities.argsort(descending=True).tolist()
    nearest = [vocabulary[i] for i in ranking[1:6]]   # [0]: the word
    print(f"{word}: {', '.join(nearest)}")