Sequences, recurrence and its limits

The support team wants to know which conversations will end in a cancellation. Each conversation is a list of events: messages, page views, a failed payment, a refund request. Some have four events, some have four hundred. There is no fixed number of columns to hand a model, because there is no fixed number of anything.

The convolution from the last article does not apply, since it needs a window of known size and it deliberately ignores where in the sequence something happened. Order is exactly what matters here. A refund request after a failed payment is a different story from a refund request before one.

The recurrence

A recurrent network reads the sequence one step at a time and keeps a single vector of state between steps. At each step it combines the state it is carrying with the new event, and produces the state it will carry into the next step.

• Start with a state of zeros.
• For each event: new state = activation of (W times state, plus U times event, plus bias).
• After the last event, use the final state to make the prediction.

That is the whole architecture. It handles four events and four hundred with the same weights, because the same W and U are applied at every step. The state is a fixed-size summary of everything read so far, and its size is a design choice rather than a property of the data.

The weight sharing is the same trick convolutions used across space, applied across time instead. It brings the same benefit, which is a parameter count that does not grow with the length of the input, and a different cost, which is the subject of the rest of this article.

What fifty steps does to a gradient

Training uses backpropagation, run backwards through the unrolled sequence. Every gradient reaching an early step is a product with one term per step it travelled through, which is the mechanism worked through in Backpropagation worked by hand. The difference here is that the same matrix W appears at every step, so the product is not a mixture of different factors. It is a power.

Suppose that at each step the gradient is multiplied by 0.9.

• Over 20 steps: 0.9 to the twentieth, which is 0.122.
• Over 50 steps: 0.0052.
• Over 100 steps: 0.000027.

Now suppose the factor is 1.1 instead.

• Over 20 steps: 6.7.
• Over 50 steps: 117.
• Over 100 steps: 13,781.

Neither number is a bug. A factor slightly below one means the network cannot learn from anything that happened more than a few dozen steps ago, because the gradient telling it to has already been rounded into nothing. A factor slightly above one means the gradient arriving at the first step is enormous, the update is enormous, and the weights leave the region where the loss made sense. There is no factor in between that is safe, because a factor of exactly one is a knife edge and a real matrix has many singular values, not one.

Pascanu, Mikolov and Bengio set this out from analytical, geometric and dynamical systems perspectives, and their two remedies are the ones still in use. For the exploding case they propose a gradient norm clipping strategy: measure the total size of the gradient, and if it exceeds a threshold, scale the whole thing down to that threshold before stepping. For the vanishing case they propose a soft constraint. Clipping is a single line in most training scripts and it is there because of the arithmetic above, not because of anything peculiar to language.

Clipping fixes the explosion and does nothing at all for the vanishing case. Scaling a gradient of 0.000027 back up would amplify whatever noise is in it by the same factor.

Gates, and what they are actually doing

The long short-term memory cell is the standard response, and it is easier to understand as an arithmetic manoeuvre than as a biological metaphor.

The cell keeps a second vector alongside the state, the cell state, and updates it by a rule of the form

new cell = forget gate times old cell, plus input gate times candidate.

The important part is that the old cell state is multiplied by a number the network chooses, rather than passed through a matrix and an activation. If the forget gate sits near one, the path from an early cell state to a late one is close to multiplication by one, repeated, which does not vanish.

Put numbers on it. A forget gate of 0.99, held for 50 steps, gives 0.99 to the fiftieth, which is 0.605. At 0.95 it is 0.077. At 0.90 it is 0.0052, the same collapse as before.

So gates do not remove the problem. They give the network a dial it can set per unit and per step, and the network can learn to hold that dial near one for the specific things worth remembering while letting everything else decay. The mechanism is not magic and it is not unlimited: a cell that must remember something across a thousand steps still needs a forget gate averaging above 0.999 to do it.

Greff, Srivastava, Koutnik, Steunebrink and Schmidhuber ran the experiment nobody else had. They present the first large-scale analysis of eight LSTM variants on three representative tasks, and report that the forget gate and the output activation function are the most critical components, with none of the variants significantly outperforming the standard architecture. Two useful conclusions follow. The forget gate is doing the work, as the arithmetic above suggests. And the time spent choosing between cell variants is time wasted, because the study that compared them found no winner.

The bottleneck that ended the design

Recurrence had a second problem, separate from gradients, and it appeared as soon as anyone tried to map one sequence onto another.

Sutskever, Vinyals and Le built the standard version: one network reads the input sequence into a vector of a fixed dimensionality, and a second network generates the output sequence from that vector. On English to French translation their model reached a BLEU score of 34.8 against 33.3 for the phrase-based system they compared with, and 36.5 when used to rerank that system's hypotheses. They also report a result that reads as a warning in hindsight: reversing the order of the words in all source sentences, but not target sentences, improved performance markedly, because it created shorter-term dependencies between source and target.

A change that improves a model by shortening the distance information has to travel is evidence about the distance, not about the change.

Bahdanau, Cho and Bengio named it. They conjecture that the use of a fixed-length vector is a bottleneck in improving the performance of the basic encoder-decoder architecture, and propose allowing the model to automatically search for the parts of the source sentence relevant to predicting each target word, without forming those parts as an explicit segment. Their qualitative analysis reports that the soft alignments the model finds agree well with intuition.

Everything a fifty-word sentence contains had to fit through one vector of a few hundred numbers, and the last word read had a much better chance of being in it than the first. That is a capacity argument, and no amount of gating addresses it.

The cost nobody mentions until the training run

Two practical limits matter as much as the gradient arithmetic.

Recurrence cannot be parallelised over time. Step 200 needs the state from step 199, so a sequence of 1,000 steps requires 1,000 sequential operations no matter how many processors are available. A convolution over the same sequence, or the architecture in the next article, runs every position at once. The design that made recurrent networks feasible on the hardware of one decade made them uncompetitive on the hardware of the next.

Training memory grows with sequence length. Every activation at every step is held until the backward pass consumes it, so a batch of 32 sequences of 500 steps holds 16,000 sets of activations at once. Truncating the backpropagation to the last 50 steps is the usual fix, and it makes the memory constant while formally guaranteeing that nothing before those 50 steps is learned.

When a recurrent model is still the right answer

The architecture is not obsolete, and treating it as such is how teams end up running a transformer over sequences of eleven events.

• Short sequences with genuine order, in the tens rather than the thousands, where the gradient product never gets long enough to collapse.
• Streaming settings where events arrive one at a time and a fixed-size state that updates in constant time per event is exactly what the system needs.
• Small data. A gated recurrent model has few parameters and the arguments in Bias and variance in plain terms apply directly: a large attention-based model on a few thousand sequences will fit the noise.
• As the baseline. The discipline from Linear regression is still the baseline survives the change of domain. A one-layer gated recurrent model trains in minutes and gives the ambitious architecture something to beat.

The next article takes Bahdanau's proposal seriously and works it out with numbers on a four-word sentence. It replaces the single carried state with a lookup over everything read so far, and the lookup is learned rather than written.

References

1. On the difficulty of training Recurrent Neural Networks. Razvan Pascanu, Tomas Mikolov and Yoshua Bengio, arXiv, 2012.
2. LSTM, A Search Space Odyssey. Klaus Greff, Rupesh Kumar Srivastava, Jan Koutnik, Bas R. Steunebrink and Jurgen Schmidhuber, arXiv, 2015.
3. Sequence to Sequence Learning with Neural Networks. Ilya Sutskever, Oriol Vinyals and Quoc V. Le, arXiv, 2014.
4. Neural Machine Translation by Jointly Learning to Align and Translate. Dzmitry Bahdanau, Kyunghyun Cho and Yoshua Bengio, arXiv, 2014.