Learn AI · Chapter 10 · Sequence Modeling: Recurrent and Recursive Nets

Recursive Neural Networks

Read a sequence as a tree instead of a chain, count how the depth of a balanced tree grows, and follow one forward pass with weights shared across the tree.

Book §10.6, pages 400–401About 25 minutes

Section 1

A tree instead of a chain

Picture a knockout tournament with eight players. Two players meet, the winner moves on, and the rounds continue until one champion is left. The bracket is a tree. The players are the leaves, each match is a node, and the champion sits at the root.

A recurrent network combines its inputs in a different order. It keeps one running total and folds in one input at a time, so eight inputs make a chain of eight folds. A recursive network replaces the chain with a tree. The book’s Figure 10.14 draws the tree with three weight matrices: at the leaves, and and at the internal nodes.

Why does the shape matter? The book says that for a sequence of the same length, the depth, counted as the number of compositions of nonlinear operations, can drop from to . A chain forces a signal through every step in turn. A tree lets it pass through only a few levels.

x, o, y, U, V, W inputs, outputs, targets and weights h hidden value at a leaf or node a pre-activation of a node L loss

How to use this page

Click the colored symbols. Each click explains the symbol and lights up its other uses on the page.

Move the sliders before you read on. Each readout describes what you have changed.

Predict before you look. How many rounds does the champion play in a bracket of eight?

Predict, then reveal

Choose a number of rounds. The answer appears after you choose.

The bracket answer is the depth of the tree. A tree with eight leaves has depth three, because eight players become four winners, four become two, and two become one. The chain answer is much larger, and the next two sections measure both.

Where the book is brief

The book gives the logarithmic depth in one sentence and does not draw a bracket. The tournament is an analogy written for this page.

Section 2

Merging neighbors and depth

Play the merge game. Each box is a subtree, and its number is its depth: the largest number of merges on a route from a leaf up to that box. A single input is a box of depth 0. Click a dashed gap between two neighboring boxes. The two boxes join into one, and its depth is one more than the deeper of the two.

Merge neighbors until one box is left

Challenge +8 XP

Merge the eight boxes until one box is left, with a depth of exactly 3. Each merge joins two neighboring boxes.

Challenge +8 XP

Merge the eight boxes until one box is left, with a depth of exactly 5.

The number in the last box is the depth of the whole tree. Many patterns of merges are possible. A balanced pattern keeps the number small, and a chain makes it large.

Why a balanced tree is shallowest

A tree of depth d has at most 2^d leaves, because each level can at most double the number of leaves below it. Eight inputs therefore need depth at least 3, since 2³ = 8. A balanced tree reaches that bound. This counting is added here and is not printed in the book.

Section 3

One set of weights at every node

A recursive network needs only three weight matrices, whatever the size of the tree. Every leaf applies to its input . Every internal node applies to its left child and to its right child. The same matrices are reused at every leaf and every node, so the number of parameters does not grow with the sequence. This is the fixed set of parameters that the book describes, which maps a variable-size sequence to a fixed-size representation.

Click any coloured symbol to see what it means.

Each leaf turns its input into a hidden value. Each node combines its two children and squashes the sum with tanh. The root gives the output , and the loss compares that output with a target . The example uses a target of 0.2.

Added here

These equations are added here and are not printed in the book. Figure 10.14 names the weights U, V and W, but it gives no nonlinearity and no formula for the loss. The tanh and the one-half squared loss are choices made for this page. The labels also differ from the time-step labels of Section 10.2.

Forward pass with shared weights

Weight U, left child

Weight V, leaves

Weight W, right child

leaf valuesnode valuesoutput

The example input is , shown under the leaves. With all three weights at 1, the output is about 0.746 and the loss is about 0.149. The readout tracks both numbers as you move the sliders.

Challenge +8 XP

Move the three weights until the loss is below 0.005.

Why the same weights can serve every node

The leaves and nodes do the same kind of job: each one takes its children, weights them, and applies tanh. A tree with eight leaves and a tree with four leaves use the same three matrices, so a model trained on one size can be applied to another. This sharing is the reason a recursive network needs no new parameters for a longer input.

Section 4

Depth against sequence length

Use the merge game to count. A balanced tree with leaves has a depth equal to the smallest whole number that is at least the base-two logarithm of :

Click any coloured symbol to see what it means.

A chain with the same number of leaves needs one merge fewer than it has leaves, so its depth is:

Click any coloured symbol to see what it means.

Move the slider to see the two depths side by side. The chain line rises with the number of leaves, while the balanced dots climb one step at a time, each step arriving one leaf after a power of two.

Depth of the two trees against the number of leaves

Number of leaves

balanced treechaincurrent setting

Challenge +8 XP

Set the number of leaves to the smallest value whose balanced tree has depth 5.

Counting convention

This page counts merges, so a leaf has depth 0. A recurrent network over inputs is a chain of leaves, so in this count it has merges, as the chain formula says. The book counts compositions of nonlinear operations, where each time step of a recurrent network adds one, which gives for the chain. Counting the transformation at each leaf as one more nonlinear step moves every depth on this page up by one. This convention is added here and is not printed in the book. Under either count the chain grows with and the balanced tree grows with the logarithm.

Where the idea comes from

The book credits Pollack (1990) with the first recursive networks, and Bottou (2011) with the idea that the learner might infer its own tree. Socher et al. (2011a, 2013a) applied them to natural language, where the tree can be fixed to the parse tree of a sentence. The book also gives the balanced binary tree as an option that does not depend on the data. It notes that a node need not compute an affine map followed by a nonlinearity, and Socher et al. (2013a) use tensor operations instead. Socher et al. (2011b) apply the idea to computer vision.

Summary

A recursive network reads a sequence as a tree. The book notes that depth can fall from to , which may help with long-term dependencies.
Each leaf applies to its input, and each node applies to its left child and to its right child. The same weights serve every node.
The depth of a balanced tree with leaves is the smallest whole number that is at least the base-two logarithm of . A chain has depth .
The book treats the tree structure as open: a fixed balanced tree, a parse tree from a language parser, or a tree the learner infers from the data.

Final quiz

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.6 (pages 400–401), 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.