The Recurrent Network

A notebook carried from step to step

How can we escape the tyranny of the fixed window of words? By an elegant and deeply human idea: instead of trying to take in the whole sentence at a single rigid glance, we read the text word by word, from left to right, exactly as a person reads. As it advances, the network carries with it a small numerical summary — a kind of internal notebook — that condenses everything it has read up to that moment. This bundle of numbers is called the hidden state and represents the network’s entire memory of the past.

At every step of reading the same rhythmic operation is repeated: the network combines the word that has just arrived with the notes from the previous step, passes them through a layer of neurons and produces a new, updated version of the notebook. Such a construction is called a recurrent network (or RNN), because the output of each moment returns as the input for the next step. It is exactly the same self-regulating loop we met in the flip-flop circuit of the first lessons: a machine that remembers its own state from one instant to the next.

In the interactive simulation above we have trained a simple network with a single mission: to remember which was the first symbol of the string (A or B) all the way to the end of the road. Notice how certain values in the internal notebook stay clearly distinguished along the whole sequence. There the memory lives: a numerical echo that endures and is passed on from one cell to the next.

The same machinery reused without end

The great engineering beauty of a recurrent network is that it needs no separate parameters for the first, the second or the tenth word. It uses a single stable set of connections, reused identically at every step — just as the convolution filter slid over the whole surface of an image.

This trick brings two formidable advantages. First, the sentence may be of any imaginable length: a hundred, a thousand or ten thousand words, because the processing cell is the same. Second, what the network learns about a verb or a preposition stays valid wherever the word appears in the sentence. The enormous waste of the rigid window seemed to have been settled once and for all, on paper.

The bottleneck of memory: how much can the notebook hold?

But there is an unavoidable physical obstacle: the network’s notebook has a fixed size. However long and complex the text passed through, all the information from the earlier pages has to be condensed and crammed into the same few hundred real numbers. Every newly arrived word competes fiercely for room with the old memories. It is like a narrow archive room: for every new file you push onto the shelf, an older file is inevitably pushed out of the window.

This weakness of memory can be tested with laboratory precision: we give the network a string beginning with “A” or “B”, then insert a series of random filler symbols and ask it at the end which letter came first. The task calls for no sophisticated deduction, only the faithful retention of one piece of information over a long distance.

Look at the results in the table: the accuracy does not fall smoothly but collapses abruptly! Up to a distance of ten or fifteen steps the network answers impeccably; beyond this invisible barrier, performance falls to 50%, exactly as with the toss of a coin. And increasing the volume of training examples does not shift this threshold at all. The fault is rooted deep in the very mathematics of learning.

Chinese whispers: the slope that dies away

Where does this early amnesia come from? The answer lies hidden in the algorithm of backpropagation. For the network to realise that the first word influenced the mistake made at the end, the correction signal (the gradient) must travel back through time, step by step, through all the intermediate links. At every step back, the signal is multiplied by the cell’s matrix of weights.

We recall the rule of repeated multiplications from the lesson on optimisation: if you repeatedly multiply a number below one (0.9, say) by itself thirty times, the result rushes towards zero. If the number is only a little above one (1.1, say), the result explodes towards infinity! It is the classic syndrome of the game of Chinese whispers along a long line of children: the initial whisper either dies away entirely until nothing can be heard, or is grotesquely distorted.

The correction signal that manages to reach the first steps is tens of thousands of times weaker than the one at the end. The connections that ought to learn to preserve the old memories receive practically no adjustment. The network does not forget out of malice or want of raw memory; it forgets because the mathematical echo of learning dies away on the road and nobody manages to tell it that those initial details were worth remembering!

The saving bypass: the gates of the LSTM cell

The ingenious solution to this problem was formulated in 1997 by the researchers Sepp Hochreiter and Jürgen Schmidhuber under the name of long short-term memory network (LSTM). Their idea was to create a parallel conveyor belt (a “motorway of memory”) along which information could travel unhindered, without being crushed at every step by successive multiplications.

Access to this belt is controlled by intelligent taps called gates: a forget gate that decides which old details may be erased, a write gate that adds fresh facts, and a read gate that draws out what is useful for the present moment. Thanks to this structure with its direct motorway, the gradient signal no longer dies away, and LSTM networks were able to hold far longer contexts, dominating machine translation and speech recognition for nearly twenty years.

The impassable wall: the bottleneck and step-by-step processing

Although the LSTM architecture pushed the capacity for memory considerably, two fundamental shortcomings remained unsolved and in the end blocked progress.

The first is the informational bottleneck of the single summary. However refined the gates, the whole content of a book or of a complex document has to be squeezed and compressed through a single vector of fixed size. What is lost along the way is lost for ever; the later steps have no way of looking directly back to reread the original text.

The second obstacle proved fatal in the age of modern computers: the strictly sequential dependence. To process word number one thousand, a recurrent network must necessarily have finished word nine hundred and ninety-nine, because it vitally needs its hidden state! It is impossible to process the sentence at a single stroke, in parallel. And modern graphics processors (GPUs) draw their power precisely from the ability to carry out millions of operations simultaneously on large matrices.

Here the evolution of recurrence stopped: not for want of imagination, but because it could not take advantage of the massive power of the new parallel chips. A complete revolution was needed: a mechanism allowing every word to look directly at any other word of the sentence, in a single global glance and with no bottlenecked summaries. In the next lesson we shall discover the idea that changed the world: the mechanism of attention.