Preface: Following the previous #AI series and #MarvinMinsky series. This post is co-written with Claude.

1951: Prediction and Entropy of Printed English

Around 1950, Claude Shannon of Bell Labs and his wife, Mary, played a game at home. He pulled a book off the shelf, covered the title, and opened it to a random passage. Her job was to guess the passage one letter at a time. If she got a letter right, she moved on to the next. If she got it wrong, he told her the answer and the game continued. She got the first letter on her first try: T. Then h, e, a space. After the first word, many letters hardly needed guessing. What came before had already decided them.

In January 1951, Shannon turned the game into a paper, "Prediction and Entropy of Printed English," published in the Bell System Technical Journal. He wanted to measure how much of English is predictable. The answer was: a lot. In ordinary literary English, if you take the previous hundred letters into account, roughly three quarters of the text is redundant. "Redundant" here doesn't mean useless. It means it can be inferred from what came before. Shannon measured this in bits.

A bit is the amount of information you get from the answer to one yes-or-no question. Flip a coin and there are two possibilities; one question, "Is it heads?", settles it. That's 1 bit. With four possibilities, ask "Is it one of the first two?" and then "Is it the first?": two questions, 2 bits. With eight, each question rules out half, so three questions, 3 bits. Every time the number of possibilities doubles, you need one more question.

Now try it on a letter. English has 26 letters, plus a space, for 27 possibilities. Guess the way you would in a game of twenty questions, cutting the field in half each time. "Is it between A and M?" leaves about 14. Ask again and about 7 remain, then 4, then 2, then 1. Sometimes that takes four questions, sometimes five. Four questions can sort out at most 16 options (2 × 2 × 2 × 2), and five can sort out 32. Twenty-seven falls in between, and worked out exactly, the average comes to 4.75 questions. That's 4.75 bits per letter. That's the case where every letter is completely random, with no pattern to go on.

But real English has patterns. Shannon's experiments found that once the preceding text is taken into account, each letter carries only about 1 bit of new information on average, as if a single yes-or-no question were enough to pin down the next letter. The drop from 4.75 questions to 1 is what's redundant.

Strip the vowels out of a sentence: Th_ k_tt_n sl__ps _n th_ s_f_. Most people can still read it. Q is almost always followed by u; th is likely followed by e; after "The kitten sleeps on the," the next word is probably sofa, bed, or floor. Every letter you can delete and still guess is redundant.

The redundancy isn't waste. Speech happens amid noise, accents, and missed syllables, and the redundant part lets people understand even when some of it gets lost. It also means that what can be predicted can be compressed, and that a machine can learn to guess.

An N-Gram Model

The simplest version came from Shannon himself, and the method was counting. Go through a large body of text and tally which word most often follows which. "Drink" is usually followed by "water," "tea," or "wine," rarely by "table." Chain words together by these frequencies, one after another, and you get strings that look like English but mean nothing.

An n-gram model is a model that looks only at the last few words and guesses the next one from frequency counts. Look at two words to guess the third, and it's a trigram model. This approach was used for decades. Speech recognition and early machine translation both relied on it. But it had two fundamental problems.

A tiny example shows how it works. Suppose all the text the machine has ever read is four sentences: I drank water. I drank tea. I drank tea. He drank wine. A bigram model, which looks only at the previous word, records every pair of neighboring words and counts how often each appears. After "drank," the counts look like this:

Divide each count by the total and you have a probability. This table is everything the model knows. To guess the next word, it picks the most likely one: after "drank," it guesses "tea." To generate a sentence, it draws by probability, adds the word, then looks up the new word in the table, one word after another. Shannon did this by hand in 1948: open a book at random, find the current word, write down the word that follows it; then open to another page, find the word just written down, and see what follows that. English assembled this way is natural from one word to the next, and senseless as a whole.

A trigram model does the same thing but looks at the previous two words. After "I drank," "water" appears once and "tea" twice; after "he drank," "wine" appears once. Reading "he drank," the trigram model guesses "wine." The bigram model sees only "drank" and still guesses "tea." One more word of context, a slightly better guess. But give it "she drank," and there's no "she drank" in the table at all. The count is zero, and the model has no idea what comes next.

This approach was used for decades. Speech recognition and early machine translation both relied on it. But it had two fundamental problems.

First, it can't see far. Looking only two or three words back, it has no idea what the passage was about at the start. Try to look further and the number of combinations to count explodes: with ten thousand common words, there are a hundred million possible two-word combinations and a hundred quintillion five-word ones. Everything humans have ever published adds up to a few hundred trillion words, not even a rounding error against that. Even a perfectly ordinary phrase like "the pickled beans grandma made yesterday" may never have been written in exactly that order. If a sequence never appears, its count is zero, and the model has no idea what comes next. So it can only look two or three words back, because only sequences that short are common enough to count. Second, it doesn't understand similarity. To it, "cat" and "dog" are two unrelated symbols, as unrelated as "cat" and "piano." Having seen "the cat is sleeping on the sofa," it cannot infer that "the dog is sleeping on the sofa" also makes sense.

Neural Networks

A neural network is a web of very simple calculating units, each of which takes in a few numbers and passes one number on. Each unit, loosely called a neuron, does three things: it multiplies each incoming number by a weight, adds the results together, and squeezes the sum into a fixed range.

Say the question is whether to see a movie tonight. The inputs are the review score (8), whether a friend is going (yes, 1), and whether the theater is far (yes, 1). Give the score a weight of 0.5, the friend 2, the distance -1.5: 8 × 0.5 + 1 × 2 + 1 × (-1.5) = 4.5, which squeezes to nearly 1. Go. If the friend isn't going, the total drops to 2.5. Still go, but less sure. The unit understands nothing; every bit of its judgment lives in those weights.

Put many units side by side and you have a layer. Each one sees the same inputs but weighs them differently, so each picks up on something different. Feed one layer's outputs into the next, and the next, and the final layer gives the answer. A single layer can only make crude judgments; stacked layers can combine simple features into more and more complex ones.

At the start, all the weights are random and the network's answers are nonsense. In training, it sees a large number of examples. Each time, its answer is checked against the right one, and the error is passed backward from the last layer to the first, telling each weight whether to go up or down a little. After millions of these small corrections, the weights settle into something that gets the answers right. No one writes the rules. They are tuned out of the data.

In February 2003, Yoshua Bengio and three colleagues at the Université de Montréal published "A Neural Probabilistic Language Model" in the Journal of Machine Learning Research. Their proposal had three parts. Give every word in the vocabulary its own string of numbers; in their experiments, 30, 60, or 100 of them. Compute the probability of the next word from the numbers of the words before it, instead of looking it up in a table. And learn both the numbers and the way of computing with them at the same time, without anyone setting them in advance.

To guess what follows "he drank," the model looks up the numbers for "he" and "drank," lines them up side by side, and feeds them into a neural network, which puts out a probability for every word in the vocabulary: so much for wine, so much for tea, so much for table.

In training, it guesses the next word over and over across a large body of text. Each time it's wrong, two things get adjusted: the network's weights, and the numbers for the words it just used, both nudged so the right answer becomes more likely.

Over time, words that turn up in similar places end up with similar numbers. "He" and "she" are often followed by the same words, said, went, drank, so their numbers drift close together. Even if "she drank" has never appeared, its numbers look a lot like those of "he drank," and the network gives a similar answer. The paper's own example: having seen a sentence about a cat walking in the bedroom should make one about a dog running in a room seem nearly as likely, because cat and dog, bedroom and room, walking and running all sit near each other.

On both of the text collections they tested, the model clearly beat the best n-gram models of the day. The cost was speed. The paper itself noted that training a model with millions of parameters in a reasonable amount of time was a serious challenge in its own right. That is why the idea sat for a decade.

2013: word2vec

The idea took a decade to catch on. In 2013, researchers at Google released word2vec, a tool that could be trained quickly on enormous amounts of text. What it does is simple: each word learns to predict which words appear around it. Once training is done, every word has become a point in a space with a few hundred dimensions. A word vector is a string of numbers representing a word, where words with similar meanings sit close together.

The surprise was that directions in this space carry meaning too. Take the coordinates of "king," subtract "man," add "woman," and the nearest point is "queen." No one taught it what gender is. It simply found, across billions of words, that the difference between "king" and "queen" looks a lot like the difference between "man" and "woman."

But there is a limit: each word gets exactly one set of coordinates. "Bank" means both a financial institution and the edge of a river, and in word2vec it can only sit somewhere awkward in between. A word's meaning depends on context, and a word vector has no context.

To understand context, you have to read the whole sentence. The main tool for that at the time was the recurrent neural network. A recurrent neural network (RNN) is a network that reads from left to right, one word at a time, updating its "memory" after each word.

This "memory" isn't a piece of text. It's a string of numbers, usually a few hundred of them. Think of it as a small whiteboard that says, "Here's what I understand of this sentence so far." At the start, the whiteboard is blank: all zeros.

Take the sentence "The kitten sleeps on the sofa." When the network reads "kitten," it combines two things: what's currently on the whiteboard (still blank) and the word vector for "kitten." Each is multiplied by a set of weights, the results are added together, and the sum is passed through a function that squeezes the values into a fixed range. That gives a new whiteboard. The old one is wiped and replaced. Weights are the coefficients a neural network uses to mix its inputs; training is the process of adjusting them.

An activation function is a simple function a neural network applies after every mixing step. The one most commonly used in recurrent networks is the hyperbolic tangent (tanh), which squeezes any number into the range between -1 and 1: feed it 0.5 and you get 0.46; feed it 3 and you get 0.995; feed it 100 and you still get less than 1.

Why squeeze? Plug in some numbers and see. Suppose the network is reading this film review: "The cinematography is beautiful, the acting superb, the score moving, the opening thrilling, the dialogue memorable, but the middle is dull, the pacing sluggish, the ending rushed, and overall it's a letdown".

To keep things simple, we look only at the evaluative word in each clause. The first five are positive, and each adds +1 to the whiteboard. The last four are negative, and each adds -1. A real whiteboard holds a few hundred numbers; here we reduce it to one. As described above, each time a word is read, the new whiteboard equals the old whiteboard multiplied by a weight, plus whatever the new word contributes. The weight on the old whiteboard determines how much the past counts in the new whiteboard: below 1, the past fades step by step; above 1, the past is amplified step by step.

In a real network, the weights are learned, and among a few hundred of them some will always be greater than 1. Setting the weight to 2 here lets us see what happens when that's the case. So the rule is: multiply the number on the old whiteboard by 2, then add the word's +1 or -1. The whiteboard starts at 0. At "beautiful," 0 × 2 + 1 = 1. At "superb," 1 × 2 + 1 = 3. At "moving," 3 × 2 + 1 = 7. The squeezed column applies tanh after each step: at "beautiful," 0 × 2 + 1 = 1, which squeezes to 0.76; at "superb," 0.76 × 2 + 1 = 2.52, which squeezes to 0.99.

Start with the unsqueezed column. The five positive words push the number up to 31. From "dull" onward, the review turns negative, but each negative word subtracts only 1, while the whiteboard doubles at every step, so the number keeps climbing. By "letdown," the whiteboard reads 481. The network still thinks this is a rave. Keep reading, and the number would grow too large for the computer to store.

Now the squeezed column. The first five words push the whiteboard close to 1, and there it stops. It can't climb any higher. So when the negative words arrive, they pull it down quickly: 0.76 at "dull," 0.47 at "sluggish," negative by "rushed," and -0.80 after "letdown." The whiteboard changes its mind. It works like a limiter in a recording studio: no matter how loud the sound, it never goes past a ceiling, so one loud bang can't drown out everything that follows.

Then the network reads "sleeps." Same procedure: old whiteboard plus "sleeps," mix, squeeze, new whiteboard. Then "on," "the," "sofa," step by step. After the last word, what's on the whiteboard is the network's understanding of the whole sentence. To guess the next word, it computes the probability of every word from the current whiteboard.

The crucial point is that every step uses the same set of weights. Reading the first word and reading the hundredth word follow the same rules; only the incoming whiteboard and the word change. The same small network is used over and over in a loop, which is why it's called a recurrent neural network. It's also why it can read a sentence of any length.

To train it, you have it guess the next word across a large amount of text. When it guesses wrong, you measure how wrong, then pass that error backward through time: how the last step should be adjusted, how the step before that should be adjusted, all the way back to the first word. Because every step uses the same weights, all these adjustments end up added to the same set of weights.

The trouble is on the way back. Each step the error travels backward, it gets multiplied by the weights once more. Multiply a few dozen times and a number either shrinks toward zero or grows out of control. Multiply 0.9 by itself fifty times and you're left with 0.005; multiply 1.1 by itself fifty times and you get 117. In practice it's usually the first.

The Vanishing Gradient Problem

The vanishing gradient problem is when the error signal grows weaker as it travels backward, so that steps far in the past receive almost no adjustment. The result is that the network has a hard time learning that something thirty words back matters now. And because the whiteboard is rewritten in full at every step, what was written early on gets gradually washed out. Take "Joe is a baseball player, and after a good breakfast he went to the park and got two hits." By the time the network reaches "hits," "baseball" has faded almost to nothing on the whiteboard. The problem was identified in the early 1990s.

The LSTM (long short-term memory network), proposed in 1997, was the answer. Alongside the whiteboard, it adds a "conveyor belt" dedicated to keeping information over the long term. What's on the belt isn't rewritten in full at every step. It's controlled by three "gates." The forget gate was added around 2000; the original version had only two.

The forget gate decides which old contents on the belt should be erased. Reading a new subject, for instance, it erases the old one. The input gate decides which information from the current word is worth writing down. Reading "baseball player," it writes down "this passage is about baseball"; reading "good," it may write nothing. The output gate decides what to take off the belt for use at this step. Reading "hits," it takes out "baseball."

Each gate is itself a string of numbers between 0 and 1, where 0 is fully closed and 1 is fully open. When a gate opens, and how wide, is also something the network learns from data. No one tells it what a "subject" or "baseball" is.

More importantly, updates to the belt are additions and subtractions to what's already there, not a multiply-and-overwrite at every step. As long as the forget gate stays open, a piece of information can sit on the belt untouched for many steps. When the error signal travels backward, it can also ride the belt a long way without fading. That's why an LSTM remembers longer. By the mid-2010s, it was the most widely used architecture in speech recognition and machine translation.

But whether it's a plain recurrent network or an LSTM, one limit can't be removed: it has to finish reading "kitten" before it can read "sleeps." Every new whiteboard has to wait for the previous one to be computed.

In 2014, researchers used two of these networks for translation. The first reads the source sentence and compresses the whole thing into a fixed-length string of numbers; the second writes out the translation from that string, one word at a time. This is called an "encoder-decoder." The length of the string is fixed. Whether the source sentence has five words or fifty, it has to fit into a box of the same size. The longer the sentence, the more the translation starts to lose. That same year, Dzmitry Bahdanau and his collaborators came up with a patch, built around the attention mechanism, which lets the model decide at each step which parts of the input matter most. When translating "bank," for example, it looks for "river" or "money" in the source sentence.

The Attention Mechanism

Here's how it's computed. Each time the decoder is about to write a word, it takes its current state and compares it against every word in the source sentence, giving each one a score. The scores are converted into proportions that add up to 1: say "river" gets 0.7, "sat" gets 0.2, and the remaining words split the last 0.1. The information from each source word is then blended according to these proportions and handed to the decoder to write the next word. Before the next word, the scores are calculated all over again. The box is still the same size, but it's repacked at every step with only what that step needs.

The paper Bahdanau and his collaborators released in September 2014, "Neural Machine Translation by Jointly Learning to Align and Translate," includes a figure that draws these proportions as a grid of squares in varying shades.

On one side is an English sentence about an agreement on the European Economic Area signed in August 1992; on the other is the model's French translation. Most of the dark squares line up along a diagonal, because the two languages mostly share word order: the nth word of the translation lines up with the nth word of the source.

In one place, the diagonal bends. English says "European Economic Area," with two adjectives before the noun; French says "zone économique européenne," with the noun first and the adjectives after. When the model writes "zone," it skips the first two words and looks straight at "Area"; for "économique," it looks back one word; for "européenne," one more. No one told it that French adjectives come after the noun. It learned, from a large body of parallel translations, where to look and when.

Alignment is which word in the translation corresponds to which word in the source. Earlier statistical translation systems had to train a separate model just to work out alignment. Attention turned it into a by-product of translation itself. In 2016, Google Translate put this approach into its product.

Before that, it had used phrase-based statistical translation. The method starts with a large supply of the same sentences in two languages. The most common sources were the proceedings of bodies like the United Nations and the European Parliament, where every sentence is already translated into several languages by professional translators. From millions of such sentence pairs, the system works out which words correspond, then cuts frequently co-occurring words into phrases and records every way each phrase has been translated, along with how often. The Chinese 开会, "to meet," for instance, might be "have a meeting" or "hold a meeting." These phrase tables could run to hundreds of millions of entries.

To translate a new sentence, the system cuts it into pieces, picks a translation for each piece from the table, shuffles the order within a narrow range, and assembles thousands of candidate translations. It picks one based on two scores: the translation probabilities from the phrase table, and how much the result sounds like English. The second score comes from the same n-gram model described above: it looks only at whether two or three neighboring words commonly appear together.

Each piece holds up on its own, but no step ever actually understands the whole sentence. As sentences get longer, the seams start to show: subjects and verbs don't agree, pronouns point to the wrong person, the word order still carries traces of the original. That familiar quality of early machine translation, every word right and the whole thing unlike anything a person would say, comes from here.

In September 2016, Google announced that Chinese-to-English translation on its web and mobile versions had been switched entirely to the new neural network system, a direction handling about 18 million translations a day. The new system's encoder and decoder each had eight layers of LSTM, connected by attention. By Google's own human evaluations, across English–French, English–Spanish, and English–Chinese, translation errors fell by about 60 percent on average compared with the old system. The paper also acknowledged its flaws: it still dropped words, mistranslated names and rare terms, and translated one sentence at a time without regard to what the sentence meant in the surrounding paragraph.

Attention was still just an add-on. Underneath, the recurrent network still read one word at a time, and the tenth word had to wait for the ninth. On the hardware, that was a waste. More on this in the next post. 🧪