Historical Notes

Function approximation and the long road

A feedforward network is a function approximator. It has knobs, the parameters, and it turns the knobs until its outputs match the examples. Gradient descent is the rule that turns each knob a little in the direction that lowers the error. The book describes the modern feedforward network as the culmination of centuries of progress on this one task.

This page follows the book's Section 6.6, Historical Notes, on pages 224 to 227. The higher-order derivatives in the last subsection of Section 6.5 were covered in the previous module. The notes then follow four strands: the chain rule and gradient descent, the early linear models and their limits, the rediscovery of back-propagation, and two algorithmic changes that improved training after 2006.

The timeline below holds six milestones from the book, shown in a scrambled order. Click them in date order. Each click adds one milestone to your list. Undo removes the last one, and Reset clears the list.

Linear models and the XOR problem

In the 1940s, the function approximation idea motivated machine learning models such as the perceptron. The earliest of these were linear models. Critics, including Marvin Minsky, pointed out flaws of the linear family, most clearly its inability to learn the XOR function. The criticism led to a backlash against the whole neural network approach.

The XOR function gives 1 when exactly one of its two inputs is 1. Its two outputs of 1 sit on opposite corners of a square, and its two outputs of 0 sit on the other diagonal. A single straight line cannot separate them. The book's answer is a multilayer perceptron, together with a way to compute the gradient through it. A hidden layer of rectified units solves XOR with the weights below. This is the network from Section 6.1.

The demo below asks the same question two ways. The first view is one straight line with three numbers. The second view is the two rectified units. Try the line first, then switch.

The line can be turned in any direction and moved anywhere, yet it always gets at least one of the four points wrong. The rectified network gets all four right, because each unit bends at its own knot, and the sum of the two bends separates the diagonals.

Gradient descent and the chain rule

The chain rule that underlies back-propagation was invented in the 17th century (Leibniz, 1676; L'Hôpital, 1696). Calculus and algebra had long solved optimization problems in closed form, but gradient descent was not introduced as an iterative technique until the 19th century (Cauchy, 1847). The demo uses the simplest case, a one-dimensional function, to show what the iteration does.

Take f(x) = x squared, whose slope is 2x. A gradient descent step moves x against the slope, scaled by the learning rate . The update in one dimension is written here for this page and is not printed in the book.

The step multiplies x by 1 minus 2 times each time. Whether x shrinks, flips or grows depends only on that multiplier. Move the learning rate in the demo and watch which case you reach.

The book then traces the history that followed. Efficient uses of the chain rule based on dynamic programming began to appear in the 1960s and 1970s, mostly for control applications (Kelley, 1960; Bryson and Denham, 1961; Dreyfus, 1962; Bryson and Ho, 1969; Dreyfus, 1973), and also for sensitivity analysis (Linnainmaa, 1976). Werbos (1981) proposed applying these techniques to training artificial neural networks.

The idea was finally developed in practice after being independently rediscovered in different ways (LeCun, 1985; Parker, 1985; Rumelhart et al., 1986a). The book Parallel Distributed Processing presented some of the first successful experiments with back-propagation (Rumelhart et al., 1986b). The book also places that work in a wider program called connectionism, with the notion of distributed representation (Hinton et al., 1986). Neural network research gained popularity and reached a peak in the early 1990s, and other machine learning techniques then became more popular until the deep learning renaissance that began in 2006.

Cross-entropy and saturation

One of the two algorithmic changes that improved feedforward networks was the replacement of mean squared error with the cross-entropy family of losses. Mean squared error was popular in the 1980s and 1990s. It was gradually replaced as ideas spread between the statistics and machine learning communities, along with the principle of maximum likelihood.

The change mattered most for sigmoid and softmax outputs. They had suffered from saturation, a state in which the sigmoid is almost flat, so its slope is close to zero and learning is slow. The book notes that cross-entropy greatly improved these models. The comparison below is added for this page. Here is the squared error, and is the cross-entropy loss, whose gradient with respect to z is a minus y. Let be a sigmoid output with as its input, and let be the target.

For squared error, the gradient carries the extra factor (1 minus ), which is the slope of the sigmoid. For cross-entropy, that factor is absent. When the output is wrong and saturated, the squared error gradient is tiny, and the cross-entropy gradient stays near minus one. The ratio between the two magnitudes is exactly (1 minus ) when the target is 1.

The two curves in the demo show the same story at every input. Cross-entropy keeps the learning signal alive in the saturated region, and squared error does not.

Saturation through depth

Saturation also compounds with depth. Suppose each layer is a sigmoid with weight 1 and no bias, so each input is the sigmoid of the one before. The gradient that passes back through such layers is a product of sigmoid slopes. The bound below and the chain used in the demo are added for this page. They are not in the book, but they make the book's point about sigmoids concrete.

Each slope is at most '(z) = 0.25, so the product is at most 0.25 raised to the power . With rectified units, the slope is exactly 1 in the active region, so a chain of active rectifiers does not shrink the product at all. The next section returns to that point.

Rectified units and the modern era

The second algorithmic change was the replacement of sigmoid hidden units with piecewise linear units, such as the rectified linear unit, which outputs max(0, z). Rectification dates back at least to the Cognitron and Neocognitron (Fukushima, 1975, 1980). Rectification was largely replaced by sigmoids in the 1980s, perhaps because sigmoids perform better when networks are very small.

In the early 2000s, rectified linear units were avoided because of a belief that activation functions with non-differentiable points must be avoided. That belief began to change around 2009. Jarrett et al. (2009) found, among several architecture choices, that a rectifying nonlinearity was the single most important factor in improving a recognition system. For small datasets they found that rectification mattered even more than learning the hidden weights. Random weights were enough to carry useful information through a rectified network. Glorot et al. (2011a) then showed that learning is far easier in deep rectified networks than in networks with curvature or two-sided saturation.

The book connects rectified units to biology. Glorot et al. (2011a) motivated them with three properties of real neurons: some inputs leave a neuron completely inactive, for other inputs its output is proportional to its input, and most of the time neurons operate in the inactive regime, so their activations are sparse.

The demo below shows the sparsity. A unit with a standard normal input and bias is active when its input plus the bias is positive. The probability that this happens is (), the standard normal cumulative distribution. This relation is added for this page.

Between 2006 and 2012, it was widely believed that feedforward networks would not perform well unless they were assisted by other models, such as probabilistic models. The book says that with the right resources and engineering practices, feedforward networks perform very well. Gradient-based learning in feedforward networks is now a tool for building probabilistic models, such as variational autoencoders and generative adversarial networks (Chapter 20). Since 2012, it has been viewed as a powerful technology for many other machine learning tasks.

The book also notes a reversal. In 2006 the community used unsupervised learning to support supervised learning, and now it is more common to use supervised learning to support unsupervised learning. Most of the improvement from 1986 to 2015 came from larger datasets and larger networks, together with a small number of algorithmic changes. The book ends by saying that feedforward networks still have unfulfilled potential, and that advances in optimization and model design should improve them further.

• Back-propagation applies the chain rule, which dates to the 17th century. Gradient descent as an iterative technique dates to Cauchy in 1847.
• The XOR criticism of linear models led to a backlash. Multilayer networks with hidden units answered it.
• Cross-entropy removes the slope factor that makes squared error learn slowly on a saturated sigmoid.
• Rectified units keep slopes at exactly 1 in their active region, and they give sparse activity.
• Most of the improvement after 1986 came from more data, larger networks and a few algorithmic changes.

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 6.6 (pages 224–227), 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.