The chapter opens with a definition from DeepAI: “A Recurrent Neural Network is a type of neural network that contains loops, allowing information to be stored within the network.”
The motivation is a limitation of everything built so far. Feed-Forward Neural Networks are really good at learning a pattern between a set of inputs and outputs assuming that all inputs and outputs are independent of each other. They accept a fixed-sized vector as input (an image) and produce a fixed-sized vector as output (probabilities of different classes). Consequently:
The slides use a stock price example. A FFNN can make a prediction pi based on the current time ti — but this is not sufficient to make an accurate prediction, because the current stock price depends on the stock trend and not only on the current time.
Recurrent Neural Networks (RNNs) are a class of neural networks which not just look at the current input but use sequential data or time series data. The output of any layer depends not only on the current input but also on the sequence of inputs that have come before. Another way to think about RNNs is that they have a “memory” which captures information about what has been previously calculated.
An obvious objection: why not run a separate FFNN on each element of the series? The slides answer it directly:
Because each input item from the series is related to the others and has an influence on its neighbours. Otherwise it is not a series but only many inputs. RNNs are able to capture this relationship across inputs meaningfully; n independent FFNN calls cannot, by construction.
The application list is long enough to be worth reading as a map of the field: machine translation, natural language processing, robot control, time series prediction, speech recognition, speech synthesis, time series anomaly detection, sentiment analysis, rhythm learning, music composition, grammar learning, handwriting recognition, human action recognition, image captioning, video tagging, text summarization.
The slides then show what “sequence data” means concretely, and the shape of the problem changes case by case:
| Task | Input | Output |
|---|---|---|
| Speech recognition | an audio waveform | “The brown fox jumped over the lazy dog.” |
| Sentiment analysis | “There is nothing to like in this movie.” | a sentiment |
| Music composition | a musical sequence | a musical sequence |
| DNA analysis | AGCCCCTGTGAGGAACTAG | AGCCCCTGTGAGGAACTAG annotated |
| Machine translation | “Do you want to dance with me?” | “Vuoi ballare con me?” |
The standard diagram shows an RNN being unrolled (or unfolded) into a full network. Unrolling means that the network is written out for the complete sequence.
| Symbol | Meaning |
|---|---|
xt | the input at time step t |
ht | the hidden state at time step t |
ot | the output at time step t |
For each time step, the hidden state and the output are computed as:
ht = fh( U xt + W ht−1 )
ot = fo( V ht )where U, W and V are temporally shared weights and fh, fo are activation functions.
Four properties follow, and they are the whole architecture in four lines:
ht is the memory of the network at time t: it stores information about what happened in all the previous time steps.ot is calculated solely based on the memory at time t.h₀ is typically initialized to all zeroes.U reads the input, W reads the previous memory, V writes the output. The new hidden state is fed back, which is the loop the folded diagram draws as a self-arrow.FFNNs map one input to one output, while RNN inputs and outputs can vary in length. RNNs are classified by the number of their inputs and outputs.
Tₓ = Tₖ = 1. This is the traditional FFNN: one fixed-size input, one fixed-size output.
Example from the slides: an image in, the label “Cat” out.
Tₓ > 1, Tₖ = 1. A whole sequence is consumed and a single value comes out.
Applications: sentiment analysis, movie rating, video activity recognition.
Example: “This café is great, the staff is really friendly and the coffee is delicious” → Positive.
Tₓ = 1, Tₖ > 1. One input produces a whole sequence.
Applications: music composition, image captioning.
Example: an image → “Dog is running through the water”.
Tₓ = Tₖ > 1. Every input element produces its own output element, in lockstep.
Applications: named-entity recognition, video classification of each frame.
Example: “Luke joined Google as a data scientists in Mountain view” → “LukePERSON joined GoogleORG as a data scientists in Mountain viewPLACE”.
Tₓ ≠ Tₖ, both greater than 1. The input and the output are both sequences, but of different lengths.
Applications: machine translation, speech recognition.
Example: “Do you want to dance with me?” (7 tokens) → “Vuoi ballare con me?” (4 tokens).
BackPropagation Through Time (BPTT) is the application of the backpropagation training algorithm to RNNs. The complication is the weight sharing: because the weights of an RNN are shared by all time steps, the gradient at each output depends not only on the calculations of the current time step, but also on the previous time steps.
Two questions follow: what is the total error, and how do we update U, W and V?
Each full sequence is typically treated as one training example, so the total error is the sum of the errors at each time step:
E(y, o) = ∑t=1n Et(yt, ot)Similarly, the gradient of E with respect to each weight matrix is the sum of the gradients at each time step:
∂E/∂U = ∑t=1n ∂Et/∂U
∂E/∂V = ∑t=1n ∂Et/∂V
∂E/∂W = ∑t=1n ∂Et/∂WBut the three are not equally easy:
V is quite easy, as it only depends on the values at the current time step;U and W is not so easy, because it recursively depends on previous time steps.The slides make this concrete by drawing the unrolled RNN as a computational graph for a three-step input, then running one backward pass per time step: at t = 1 only the first cell contributes; at t = 2 the gradient flows back through two cells; at t = 3 through three.
The slides close the section with the deflationary summary: this is exactly the same procedure as the standard backpropagation algorithm we use in FFNNs. The key difference is that we sum up the gradients at each time step, because in a traditional network we do not share parameters across layers and so have nothing to sum. In conclusion BPTT is just the standard backpropagation on an unrolled RNN.
| Advantages | Drawbacks |
|---|---|
|
|
Because unrolled RNNs are often very deep, they particularly suffer from problems related to vanishing and exploding gradients. The consequences the slides list:
Because of the vanishing and exploding gradient problems, RNNs suffer from short-term memory: they are not able to memorize data for a long time and begin to forget their previous inputs. The slides give the canonical example:
“I grew up in France … I speak fluent French”
Recent information suggests that the next word is probably the name of a language. But to narrow down which language, we need the context of “France”, from further back. Unfortunately, as the gap between the relevant information and the point where it is needed grows, RNNs become unable to learn to connect the information.
Two further difficulties the slides note: some tokens are irrelevant because they carry no pertinent observation, and there can be a logical break between parts of a sequence, such as a transition between chapters in a book.
Every remaining section of this chapter is one of these cures:
| Problem | Possible solutions |
|---|---|
| Exploding and vanishing gradient | gradient clipping (Chapter 4); truncated backpropagation through time |
| Difficulty of accessing information from a long time ago (short-term memory) | long short-term memory; gated recurrent unit |
| Cannot consider any future input for the current state | bidirectional recurrent neural networks |
Truncated BackPropagation Through Time (TBPTT) is a modified version of the BPTT algorithm where the sequence is processed one time step at a time and periodically the BPTT update is performed back for a fixed number of time steps.
Instead of unrolling the whole sequence and backpropagating through all of it, the backward pass is cut off after a window. The gradient never travels far enough to vanish or explode, at the cost of never learning dependencies longer than the window.
Long Short-Term Memory networks (LSTMs) are a special kind of RNN, capable of learning long-term dependencies. An LSTM contains internal mechanisms called gates to regulate the information flow. These gates can learn which data in a sequence is important to keep or throw away, passing relevant information down the long chain of sequences to make predictions and discarding non relevant data.
An LSTM has a similar control flow to an RNN: it processes data, passing on information as it propagates forward. The differences are the operations within the LSTM cells.
The core concept of an LSTM is the cell state ct, and its various gates.
Gates are a way to optionally let information through. They are composed by a sigmoid neural network layer, so a gate returns values between 0 and 1 describing how much of each component should be let through: a value of 0 means “forget information” while a value of 1 means “keep information as is”.
An LSTM has three of these gates, to protect and control the cell state:
| Gate | Decides | Equation |
|---|---|---|
Forget gate ft | what is relevant to keep from prior steps | ft = σ(Wf ht−1 + Uf xt) |
Input gate it | what information is relevant to add from the current step | it = σ(Wi ht−1 + Ui xt) |
Output gate ot | what the next hidden state should be | ot = σ(Wo ht−1 + Uo xt) |
ct−1 should be kept. The forget gate looks at the previous hidden state ht−1 and the current input xt and outputs a value between 0 and 1 for each element of ct−1.c̃t = tanh(Wc ht−1 + Uc xt) that could be added to the new cell state.ct = ft ⊙ ct−1 + it ⊙ c̃tht−1 and xt go into the output gate while ct is passed through a tanh, and the two are multiplied:
ht = ot ⊙ tanh(ct)The Gated Recurrent Unit (GRU) belongs to the newer generation of RNNs. It is similar to an LSTM but with fewer parameters, as it lacks an output gate. GRU has only two gates:
| Gate | Role | Equation |
|---|---|---|
Reset gate rt | decides how much past information to forget | rt = σ(Wr ht−1 + Ur xt) |
Update gate ut | acts like the forget and input gates of an LSTM combined: it decides what information to throw away and what new information to add | ut = σ(Wu ht−1 + Uu xt) |
The candidate and the new state:
h̃t = tanh( Wh (rt ⊙ ht−1) + Uh xt )
ot = ht = ut ⊙ ht−1 + (1 − ut) ⊙ h̃tNote that in a GRU the new hidden state and the new output are the same. There is no separate cell state and no output gate: the interpolation between the old state and the candidate is the memory mechanism.
How they compare, according to the slides:
The objective in a typical sequence learning scenario is to model the next output given a sequence of past information. But sometimes it is not enough to learn from the past to predict the future: it is also important to look into the future to fix the past. The slides prove it with a fill-in-the-blank:
| Sentence | Plausible fill |
|---|---|
| “I am ___” | happy |
| “I am ___ hungry” | not |
| “I am ___ hungry, and I can eat half a pig” | very |
Depending on the amount of information available, we might fill in the blank with very different words. A sequence model unable to take advantage of future information will perform very poorly here.
Bidirectional Recurrent Neural Networks (BRNNs) are modified RNNs with the ability to look both back and forth at every time step. A BRNN is composed of two RNNs running in opposite directions:
BRNNs are trained with similar algorithms to RNNs, since the two RNNs do not interact with each other.
Can an RNN be made deep? The question is subtler than it looks. Depth is defined, in the case of FFNNs, as having multiple nonlinear layers between input and output. Unfortunately this definition does not apply trivially to an RNN because of its temporal structure: any RNN when unfolded in time is already deep, since the path between the input at time k and the output at time t crosses several nonlinear layers.
The genuine extension is to stack multiple recurrent hidden layers on top of each other. Each hidden state hij is continuously passed to both:
j+1 of the current layer RNNi, andj of the next layer RNNi+1.h¹t = fh¹( U¹ xt + W¹ h¹t−1 )
hit = fhi( Ui hi−1t + Wi hit−1 )
ot = fol( Vl hlt )
with 1 ≤ t ≤ n and 2 ≤ i ≤ lA FFNN assumes all inputs and outputs are independent of each other, accepts a fixed-sized vector and is not designed to take a series of inputs with no predetermined limit on size, so it cannot use previous context. Calling it once per element does not help because each input item from the series is related to the others and has an influence on its neighbours — otherwise it is not a series but only many inputs.
ht = fh(U xt + W ht−1) and ot = fo(V ht). The matrices U, W and V are temporally shared: the same weights are used at every time step because the network performs the same task at each step, just with different inputs. This greatly reduces the total number of trainable weights and means the model size does not grow with the input length.
ht is the memory of the network at time t: it stores information about what happened in all the previous time steps. The output ot is calculated solely based on the memory at time t, and h₀ is typically initialized to all zeroes.
One-to-one (Tₓ = Tₖ = 1): the traditional FFNN. Many-to-one: sentiment analysis, movie rating, video activity recognition. One-to-many: music composition, image captioning. Many-to-many with Tₓ = Tₖ: named-entity recognition, video classification of each frame. Many-to-many with Tₓ ≠ Tₖ: machine translation, speech recognition.
Only in one respect: the gradients at each time step are summed up. Each full sequence is treated as one training example so E = ∑t Et, and likewise ∂E/∂U, ∂E/∂V and ∂E/∂W are sums over time steps. This summation is needed precisely because the weights are shared across time; in a traditional network parameters are not shared across layers, so there is nothing to sum. BPTT is just standard backpropagation on an unrolled RNN.
Because V only appears in ot = fo(V ht), so its derivative only depends on the values at the current time step. U and W enter the hidden state recursion, so their derivatives recursively depend on previous time steps and the chain has to be unrolled backwards through the whole sequence.
Advantages: possibility of processing input of any length; model size not increasing with the size of the input; computation takes historical information into account; weights are shared across time. Drawbacks: computation being slow; exploding and vanishing gradient; difficulty of accessing information from a long time ago (short-term memory); cannot consider any future input for the current state.
It illustrates short-term memory. Recent information tells us the next word is probably the name of a language, but to narrow down which language we need the context of “France” from much further back. As the gap between the relevant information and the point where it is needed grows, RNNs become unable to learn to connect the information, because of the vanishing and exploding gradient problems.
A modified version of BPTT where the sequence is processed one time step at a time and periodically the BPTT update is performed back for a fixed number of time steps, instead of through the entire unrolled sequence. It bounds how far the gradient travels, which mitigates vanishing and exploding gradients at the cost of not learning dependencies longer than the window.
The cell state ct is the core concept of an LSTM: a transport highway that transfers relevant information all the way down the sequence chain, the memory of the network. Information is added or removed only via gates, and the path itself is a multiplication by the forget gate plus an addition — not a chain of squashing non-linearities. This lets information from earlier time steps make its way to later time steps, reducing the effects of short-term memory.
The forget gate decides what is relevant to keep from prior steps; the input gate decides what information is relevant to add from the current step; the output gate determines what the next hidden state should be. All three are sigmoid layers returning values between 0 and 1, where 0 means forget the information and 1 means keep it as is.
ct = ft ⊙ ct−1 + it ⊙ c̃t, where c̃t = tanh(Wc ht−1 + Uc xt) is the candidate. Then ht = ot ⊙ tanh(ct): the new hidden state is a filtered version of the new cell state.
A GRU lacks an output gate, so it has fewer parameters and only two gates: the reset gate (how much past information to forget) and the update gate (which acts like the forget and input gates of an LSTM combined). There is no separate cell state, and the new hidden state and the new output are the same. GRUs use less memory and are faster; performance can be similar or even better on certain tasks, but in general LSTM outperforms GRU especially with longer sequences.
They solve the inability to consider future input for the current state — as in “I am ___ hungry, and I can eat half a pig”, where the fill depends on words that come after the blank. A BRNN is composed of two RNNs running in opposite directions: one fed in normal time order, one in reverse time order, with the outputs concatenated at each time step. They are trained with similar algorithms to RNNs since the two RNNs do not interact.
Because depth for a FFNN means multiple nonlinear layers between input and output, and any RNN unfolded in time is already deep: the path from the input at time k to the output at time t crosses several nonlinear layers. The genuine extension stacks multiple recurrent hidden layers, with each hidden state passed both to the next time step of the current layer and the current time step of the next layer: hit = fhi(Ui hi−1t + Wi hit−1).