Exponential Gains from Depth

Depth as repeated folding

Fold a strip of paper in half, then in half again, then once more. The stack has more layers after each fold, and the number of layers doubles every time. A deep network is a chain of nonlinear steps, and the number of steps is its depth. Each step can fold its input in the same way. The book’s claim is that stacking nonlinear steps can save an exponential number of units.

Two results from the book set the scene. A network with one hidden layer is a universal approximator: given enough hidden units, it approximates any continuous function to any non-zero tolerance. The book adds that the required number of hidden units may then be very large. Some functions can be represented by a deep architecture of depth with far fewer units than a shallow one would need. The book compares this with shallow architectures of depth 2 or depth , which would need an exponential number of hidden units.

The book also argues that many AI tasks need this depth. Factors such as a face’s gender or whether a person wears glasses can be chosen almost independently of each other, yet they relate to the pixels in a highly nonlinear way. The book says this demands deep distributed representations, where higher level features are built from the composition of many nonlinearities.

Predict first. Fold a strip three times, lay the stack flat, and draw one straight line across it. How many layers does the line cross?

Choose one answer.

The fold is a worked example added here, not a figure from the book. It is the map on the interval from 0 to 1. It sends to on the left half and to on the right half. The fold repeated times is . The graph of is the strip seen from its side: every straight piece of the graph is one layer of paper.

Move the height and the count stays the same. Every straight piece climbs or falls across the whole height from 0 to 1, so each piece is crossed exactly once by a line at any height between 0 and 1. The number of crossings is then the number of pieces, and the number of pieces doubles with each fold:

This count is added here and is not printed in the book. It is a worked example of the book’s claim about exponential gains, and you can check it on the sliders above.

A fold and the shallow alternative

The ReLU construction, the piece counts and the exact-fit rule in this section are added here; the book does not print them. The fold can be built from two ReLU units. A ReLU unit computes . It outputs zero for negative input and the input itself for positive input. Two of them give the fold exactly on the interval from 0 to 1:

Each fold is one such layer of two units, so a network of depth uses units in total. The shallow alternative puts all its units in one hidden layer. On one input, each unit adds at most one bend, called a kink, so units give at most straight pieces:

A fold of depth 4 has 16 pieces. Predict the fewest units a shallow network needs to match it exactly.

Choose one answer.

The demo gives the shallow network evenly spaced kinks, which is a simple way to place them and not the best possible shallow fit. The fit is drawn in violet, and the target fold in ink. The largest gap occurs at a fold point, because the gap is zero at every knot and changes in a straight line between neighboring fold points and knots.

A shallow fit is exact when every fold lies on a knot. The folds sit at multiples of , so the knots must include them. This rule is added here. Evenly spaced kinks do that when is a multiple of . The smallest such number of units is . The demo checks this for every depth from 1 to 5 and every width up to 40.

Units as depth grows

Two counts now compete. The deep fold network uses units, two for each fold, so its count grows in a straight line as depth grows. The shallow exact fit uses units, and its count doubles with each extra fold. This gap is the exponential advantage the book describes, here made concrete for one family of functions.

Predict the shallow count at depth 10.

Choose one answer.

On a logarithmic axis, a count that multiplies by the same factor at each step is a straight line. The shallow count is straight in this sense, because grows by a factor of 2 with each fold. The deep count bends away from the shallow one because grows only in proportion to .

The book links the smaller model to better statistical efficiency. The count of units is the cost that the smaller deep model avoids paying.

Other models and the limits of the result

Section 15.5 contains two kinds of result for families of models, which this page calls by the names below. A universal approximation result says that the model can match any function, or any distribution, in its class if it has enough hidden units. A depth separation result says that a deep model can need far fewer units than a shallow one for the same function. Sort the models below by the kind of result the book attaches to each.

Each tap cycles through not sorted, universal approximation, and depth separation. The book cites a minimum depth for sum-product networks, which compute probabilities with polynomial circuits. Later work showed significant differences between every two finite depths, and the book notes that the constraints which make these networks tractable may limit their representational power. For deep circuits related to convolutional nets, the book notes an advantage that survives even when the shallow circuit is allowed to approximate.

Predict what a depth separation result tells you about training.

Choose one answer.

• A depth- fold has pieces, and it needs only units when built deep.
• A shallow network with units has at most pieces on one input, so exact matching needs at least units.
• The gap between linear and exponential unit counts is the exponential gain from depth that the book describes.
• Depth separation results concern representation. They do not show that training will find the deep network.

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 15.5 (pages 553–554), 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.