Unfolding Computational Graphs

The big picture

Much of the data that matters comes in order: the words of a sentence, the notes of a melody, the prices of a stock by the day. A recurrent network reads such a sequence one element at a time and carries a summary forward. At every step it updates that summary with the same rule.

Picture a sourdough starter. Each morning you feed yesterday’s starter with the same recipe. Today’s starter therefore depends on every feeding before it, but the recipe itself never changes. Only the starter changes. A recurrent network works the same way: the summary is the starter, and the rule is the recipe.

In symbols, the state of the system at step is . The fixed rule is , and its settings are . The state refers back to itself one step earlier:

The definition of refers to , the same definition one step earlier. That reference is what makes the rule recurrent.

Try the starter. For this demo the rule is a toy. It keeps half of yesterday’s starter and adds 2. Written as a formula, . The first prediction comes before you feed it.

Each feeding halves the distance between the starter and 4, so the starter settles towards 4 without overshooting. The gap shrinks because this toy rule halves it. Real rules do not always behave this way.

Unfolding the recurrence

Apply the definition once and the state refers to the step before. Apply it again and the reference moves one more step back. After a finite number of applications the recurrence is gone, replaced by an ordinary expression with no loop. The book calls this unfolding. For three time steps the book writes:

Each in the second line is one application of the same rule with the same . The expression is a chain of identical boxes, and a chain with no loop is a directed acyclic graph, as the book notes, which a traditional computational graph can represent. Figure 10.1 of the book draws this chain.

In the demo, the rule is a toy chosen for this page: . Every value is then a power of times the starting state , which makes the arithmetic easy to follow. Choose the number of time steps and watch the chain grow.

Read the readout after you move the slider. The number of nested copies is always one less than , because the first state is the starting point and is not produced by . Every arrow in the chain carries the same , so changing it changes every link at once.

For the toy rule the value is times , which is the number the readout reports. For a general no such power exists, and the nested form is the only description.

A signal from outside

Many systems respond to an outside signal as well as to their own past. The book adds an input at each step:

The state now depends on two things: the previous state and the signal arriving at this step. Many recurrent networks give the state a name of its own, , the hidden state, and write the same idea as:

The state is a summary of the past, and in general it is lossy. A sequence of any length is squeezed into the fixed-length vector , so the network keeps only what the task needs. A model that predicts the next word of a sentence may keep enough to finish the sentence. The most demanding case is an autoencoder, where the state must be rich enough to recover the whole input (Chapter 14 of the book).

Figure 10.2 of the book shows the same network two ways. The left picture is a circuit. The black square in it marks a delay of one time step: the state computed at step is held and used at step . The right picture is the unfolded graph, with one copy of the rule for each step. The demo shows both views.

For this demo the rule is the toy , with . The memory controls how much of the old state is kept. Drag the bars to set the inputs for five steps. The first bar is set to 1 and the others to 0, so you see the response to a single impulse.

The state at step 5 is a sum of the inputs at steps 1 to 5. Each input is scaled by the memory raised to the number of steps since it arrived. With the bar at step 5 set to zero, the state at step 5 comes entirely from the past.

Sharing one rule across time

Unfolding the recurrence gives the state as a function of the whole past. Apply the rule of equation 10.5 repeatedly and the result is a function of every input so far:

The two lines say the same thing in different words. The first says the state is some function of the entire sequence. The second says it is built by applying one rule repeatedly. The book stresses that the unfolded form has two advantages, and both come from using the same rule at every step.

1. The input size does not grow. The model is written as a transition from one state to the next, so it always accepts one step of input at a time, whatever the sequence length. The unfolded graph still grows with the sequence, but the model does not.
2. One rule covers every step. The same with the same is used at all time steps. One model can therefore handle sequence lengths that did not appear in its training set, and it can be estimated from far fewer training examples than a separate model for each step would need.

The book also notes that both pictures have their uses. The recurrent graph is succinct. The unfolded graph states exactly which computations run, and it shows the path along which information flows forward, to outputs and losses, and backward, to gradients.

Before the demo, predict. In the toy rule, suppose the memory is and a change of 1 hits the input at step 1. How large is the change left in the state at step 5?

With the change shrinks to about 0.41 by step 5. The memory has to be strong for a change to survive several steps. A long memory has a cost: the state reacts more slowly to new inputs.

• Unfolding replaces a recurrence with a chain of identical steps, one copy of the rule per step.
• A chain of steps applies the rule times to the starting state.
• An input at each step is added through the rule, so the state summarizes the whole past.
• Because one rule and one set of settings serve every step, the model does not grow with the sequence length.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 10.1 (pages 375–377), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.