한국어

KNOWLEDGE · MACHINE LEARNING

How does backpropagation teach a middle layer that has no answer?

Pass back along the connections how wrong the output is, and even the neurons of the middle layer, which have no answer, get their own share of the error (δ). Each weight’s gradient is that share × the incoming value, and gradient descent corrects the weights a little the opposite way.

A multilayer perceptron (MLP) is a neural network of neurons stacked in several layers. The training data holds only the inputs and the answers at the output; it says nothing about what the neurons of the middle layer (the hidden layer) should output. Backpropagation, shown by Rumelhart, Hinton and Williams in 1986, passes back how wrong the output is and so teaches this middle layer too. The small MLP in the figure below learns XOR. The inputs are the four corners 00, 01, 10 and 11, and XOR is 1 only at 01 and 10, where the two inputs differ.

Sources: hidden units are given no desired state, backpropagation: Rumelhart, Hinton & Williams 1986, Nature 323 p. 533

Structure
Activation function

A multilayer perceptron (2 inputs → 2 hidden → 1 output) learns XOR. Seeing the four cases once each is one sweep. Drag “Learning” to follow the path the error takes back.

  1. ① Forward
  2. ② Error
  3. ③ Backward
  4. ④ Update

Circles: the value each neuron gives for the current case. Numbers on the lines: weights (blue lines +, yellow lines −). b: bias. Red numbers in ③: the shares δ and the gradients. Press a line or a b to switch the slope plot to that weight.

The error of case 00, drawn while changing only v₁ (the other weights stay as they are).

The dot is where it stands now (v₁ = 0.0700, error 0.1321). The red line (the gradient) comes in ③-3.

Case 00: compute from left to right (σ is the sigmoid).

h₁ = σ(0.08·0 − 0.30·0 + 0.02) = 0.505

h₂ = σ(0.29·0 + 0.28·0 − 0.13) = 0.468

y = σ(0.07·0.505 + 0.13·0.468 − 0.04) = 0.514

The left part shows the first sweep one step at a time. Drag into the right part to see what repeating the same step sweep after sweep achieves.

Error E 0.500Right 2/4Start 1

Answer 1Answer 0Wrong nowOutput neuron’s lineHidden neurons’ lines

The shaded area is where the output is 1 (with the sigmoid, the darker, the closer to 1).

Total error E of the four cases per sweep (dashed: 0.05)

Computation: this page does it in your browser. One sweep shows the four cases once each, in the order 00, 01, 10, 11. The weights and biases start from values drawn from −0.3 to 0.3 (starting points 1, 2, 3, …) and are corrected after every case with learning rate η = 0.5. The weights the right part of the “Learning” slider picks are computed in advance (until solved, or 30,000 sweeps if not; 3,000 sweeps for the single-layer perceptron; 100 sweeps with the step function). The slope plot computes the error again 241 times, changing only the chosen weight. Its horizontal axis is a little wider than everywhere that weight goes during this run. The gradient check adds 0.001 to the chosen weight and subtracts it, and computes that case’s error again. The same computation done separately in Python gives the same numbers.

01 MLP vs. single-layer perceptron

XOR needs a hidden layer

A neuron multiplies each input by its weight, adds them up, and adds a bias b. If this sum is above 0 the neuron is on (a value near 1); if below, it is off (a value near 0). On the input plane, the places where the sum is exactly 0 join up into a straight line. So one neuron splits the plane with one straight line.

sum s = w₁x₁ + w₂x₂ + b, output y = f(s)

Single-layer perceptron: one line

The figure’s “single-layer perceptron” is a network with only one output neuron and no hidden layer. One line cannot split XOR. 01 and 10 must go on one side and 00 and 11 on the other, but the diagonal joining 01 and 10 and the diagonal joining 00 and 11 cross in the middle. So when you choose “Single-layer perceptron”, the error falls no further than 0.50, and to the end it gets only two right.

As formulas, and the 1958 perceptron

For 00 to be 0, b < 0; for 01 and 10 to be 1, w₂ + b ≥ 0 and w₁ + b ≥ 0. Adding the last two gives w₁ + w₂ + b ≥ −b > 0, so 11 is 1 too. So no such line exists.

Rosenblatt’s 1958 perceptron had three layers: sensory, association and response. But its first connections were fixed at random and only the response layer learned, so counting the layers that learn, it has one.

MLP: one line per hidden neuron

Neurons stacked in layers make a multilayer perceptron (MLP). Each neuron of the middle layer (each hidden neuron) draws a line of its own, and the output neuron splits their results again. With two lines, XOR can be split too. By hand, you could make h₁ “at least one on” (OR) and h₂ “both on” (AND), and have the output turn on when h₁ is on and h₂ is off. The green dashed lines in the figure are the two lines that learning found.

The answer starting point 1 found by itself

The answer the MLP from starting point 1 found after 2,097 sweeps differs from the one set by hand. h₁ is on when both inputs are off, h₂ is on when the inputs are not both on, and the output is on when h₂ is on and h₁ is off. A different road, but it does the same job.

But hidden neurons have no answer

The training data has answers only for the output. Nobody tells h₁ and h₂ what they should output. So what to look at when correcting the weights into the hidden neurons was a problem for a long time. Networks without a hidden layer had simple rules with guarantees, such as the perceptron convergence procedure, but networks with a hidden layer had no such rule. Backpropagation filled that gap (03).

Sources: one neuron and the step function: Rosenblatt 1958, Bishop 2006 §4.1.7 eqs. 4.52–4.53 · the 1958 perceptron’s three layers and fixed first connections: Rosenblatt 1958 pp. 389–392, Rumelhart, Hinton & Williams 1986, Nature p. 533 · no XOR without hidden units, hidden layers can represent it, no rule as good for networks with hidden units: PDP ch. 8 pp. 318–321 · stops at 0.50, only two, the two lines found from starting point 1: this page’s computation

02 Sigmoid vs. step function

The step function cuts the way back

The activation function turns the sum s that came into a neuron into its output. The step function gives only 1 if s is 0 or more and 0 otherwise (the 1958 perceptron). The sigmoid joins 0 and 1 with a smooth S curve.

Step function: flat, so the signal is cut

Each time backpropagation passes the error back, it multiplies by how steep the activation function is at that point (③ in 03). Apart from the one point where it jumps, the step function is flat everywhere, so its steepness is 0. Multiplying by 0 makes every share sent back 0, and no weight changes at all. Choose “Step function” in the figure: after 100 sweeps the weights are exactly as they started.

The slope plot makes it plainer. The step function’s error stays flat and then jumps in steps of 0.5 at some point. For case 00 in the first sweep, making v₁ smaller than 0.04 would bring this case’s error to 0, yet the current place (0.07) is flat, so there is no gradient to say “go that way”.

Sigmoid: a little slope everywhere

The sigmoid slopes at least a little everywhere. It is steepest in the middle (s = 0) and flattens toward both ends. So the shares sent back are never cut, and every weight gets a direction to be corrected. It need not be the sigmoid: any function that slopes smoothly like this will do.

As formulas, and how the perceptron learned

Step function: f(s) = 1 (s ≥ 0), 0 (s < 0)

Sigmoid: σ(s) = 1 / (1 + e⁻ˢ), steepness σ(1 − σ)

The sigmoid’s steepness σ(1 − σ) is largest at s = 0, where it is 0.25. The original paper notes that it need not be exactly the sigmoid: any function with a bounded derivative will do.

The 1958 perceptron did learn with a step function. Its rule adds a wrong case’s input to the weights or subtracts it. Because the rule compares the neuron with its own answer, it works only on the one output layer that has answers. This page’s figure learns not by this rule but by the gradient (gradient descent), so with the step function it does not move. Learning XOR with the perceptron rule never ends: the weights keep coming back to the same values (from the 4th sweep in a separate computation).

Sources: the step function: Bishop 2006 eqs. 4.52–4.53 · the number of mistakes is flat like a staircase with a gradient of 0 almost everywhere, the perceptron criterion and its rule: Bishop 2006 p. 193, eqs. 4.54–4.55 · the sigmoid, a bounded derivative will do: Rumelhart, Hinton & Williams 1986, Nature eq. 2, p. 534 · no rule as good for hidden units: PDP ch. 8 p. 321 · unchanged after 100 sweeps, an error that jumps in steps of 0.5, the 0.04 for case 00: this page’s computation · the perceptron rule circling on XOR: a separate computation (start 0.25, −0.5, 0.25, learning rate 0.5)

03 Gradient descent

One step at a time, against the gradient

To get down a foggy mountain into the valley, look at which way the ground slopes under your feet and take one step downhill at a time. That is what gradient descent does. The height of the ground is the error, and where you stand is the values of the weights.

The slope plot shows how the error changes when only one weight moves. The red line is the gradient where it stands now. If the ground rises to the right (a positive gradient), the weight is decreased; if it falls (negative), it is increased. Gradient descent moves all the weights together, each a little against its own gradient.

new weight = current weight − 0.5 × gradient

The 0.5 is the number that sets the size of a step, called the learning rate. A step is small: for case 00 in the first sweep, v₁ moves only 0.032. Repeating such steps, the MLP from starting point 1 solved XOR in 2,097 sweeps. For the first 1,000 sweeps or so the error hardly falls. Early in the right part, switch the slope plot to a hidden weight (for example w₁₁) and its slope is almost flat, probably because the starting weights are small, so the output hardly changes even when a hidden neuron does (hypothesis).

The gradient of every weight: backpropagation

For a weight connected directly to the output, the gradient comes straight from how wrong the output is. A weight going into a hidden neuron is stuck, because that neuron has no answer. Backpropagation passes back how wrong the output is and makes each neuron’s share of the error, δ. ③ in the figure is its three steps.

  1. ③-1 The output’s share: multiply how wrong the output is (y − d) by the output neuron’s steepness y(1 − y). This is the output neuron’s share δy.
  2. ③-2 A hidden neuron’s share: multiply δy by the connection weight v to send it to the hidden neuron, then by the hidden neuron’s steepness h(1 − h). This is how a hidden neuron with no answer gets its own share δh.
  3. ③-3 A gradient for each connection: multiply the share δ of the neuron at the connection’s far end by the value that came in through that connection. If the incoming value is 0, the gradient is 0 too.

δy = (y − d) · y(1 − y)

δh = δy · v · h(1 − h)

gradient = δ × (incoming value)

In the slope plot, the slope of the red line is the value found this way. Measuring it directly, by adding 0.001 to the weight and subtracting it, almost always gives the same value to six decimal places (③-3 in the figure).

Jiggling the weights one at a time and measuring also gives the gradients. But 9 weights need 18 more computations, and the more weights, the more it takes. Backpropagation gets every gradient with one forward and one backward computation.

A little more on the share δ and the chain rule

δ is the rate at which the error changes when the sum coming into that neuron changes a little (it is also called the error signal). When a change passes through several stages, the rates of change of the stages multiply; this is the chain rule. When a hidden neuron h changes a little, the output’s sum changes v times as much, so the rate at which the error changes with h is δy · v. Multiplied by h’s steepness, it is δh. If a hidden neuron is connected to several neurons, it adds up (δ × connection weight) over the neurons after it before multiplying by its steepness, and with more layers the same formula repeats one layer at a time.

A share here is not a piece cut from a whole. The signal is only multiplied by weights on the way back, so the hidden neurons’ shares do not add up to δy.

As a formula, the gradient is ∂E/∂w: the rate at which the error E changes when the weight w is increased a little. Gradient descent is w ← w − η · ∂E/∂w, where η is the learning rate. A bias counts as the weight of an input that is always 1.

In this page’s computation, backpropagation and the directly measured gradients differed by at most 1.4 × 10⁻¹¹. This computation, which gathers derivatives backward from the output, appeared independently in several fields in the 1960s and 70s (reverse-mode automatic differentiation); the 1986 paper used it to show that hidden neurons learn useful features by themselves.

One step per case

This page corrects the weights right after seeing each case. So in the first sweep the slope plot draws the error of that one case, and each case pulls its own way. In the first sweep, 00 and 11 decrease v₁, and 01 and 10 increase it. In the right part, the slope plot draws the error of the four cases together, and the red line is the four gradients added.

What changes when correcting after each case

Correcting after each case departs a little from true gradient descent, but PDP chapter 8 notes that if the learning rate is small enough the difference is negligible. In this page’s computation, after 1,000 sweeps, while the error comes down, the way the weights moved during a sweep was almost the same as the opposite of the four gradients added. In the first 500 sweeps the cases’ gradients pointed opposite ways and were much larger than their sum, and the two had almost nothing to do with each other. After 3,000 sweeps the single-layer perceptron’s weights stay the same through one more sweep, yet the slope in the slope plot is not 0. It has stopped where the steps of the cases cancel out within a sweep.

The size of a step and where it stops

A larger learning rate makes bigger steps and goes down faster, but too large and it oscillates across the valley. So it is set as large as possible without oscillation.

When the gradients come close to 0, there is no way further down, and it almost stops. There is no guarantee that this is the lowest place. It can be a valley lower only than its surroundings (a local minimum). Press “Another start” once (starting point 2) and drag to the end. The error stops at 0.33, and whichever weight you choose in the slope plot, the dot sits at the bottom. With this page’s settings, 6 of 100 starting points were not solved within 30,000 sweeps.

If all the weights start from the same value, the hidden neurons learn the same thing and always draw the same line. So it starts from small random values.

A little more on the learning rate and momentum

True gradient descent assumes tiny steps. PDP chapter 8 says it chooses the largest learning rate that does not lead to oscillation. Learning XOR with eight hidden neurons, it was solved after about 450 presentations on average with η = 0.1 and about 68 with η = 0.75, and larger rates were unstable. Momentum, which adds part of the previous step to enlarge the step (Nature eq. 9), also exists, but this page does not use it.

Sources: the formula of gradient descent: Rumelhart, Hinton & Williams 1986, Nature eq. 8, Bishop 2006 eq. 5.41 · a bias is the weight of an input that is always 1: Nature eq. 1 · the error surface and its gradient, where the gradient is 0, global and local minima: Bishop 2006 §5.2.1 fig. 5.5, eq. 5.26 · the forward and backward passes and eqs. 4–7: Nature pp. 534–535 · the formulas for δ and gradient = δ × incoming value: Bishop 2006 eqs. 5.53–5.56 · the cost of finite differences: Bishop 2006 §5.3.3 · the history of reverse-mode differentiation: Griewank 2012 pp. 389–390 · correcting after each case: Bishop 2006 eq. 5.43, Nature p. 535, PDP ch. 8 p. 324 · the learning rate and momentum: PDP ch. 8 pp. 329–330, 333–334, Nature eq. 9 · local minima, breaking symmetry: Nature p. 535, PDP ch. 8 pp. 330–332 · 0.0648 and 0.032, 2,097 sweeps, 1.4 × 10⁻¹¹, which way each case pulls, how a sweep moves (median cosine: 0.96 or more after 1,000 sweeps, near 0 in the first 500), the slope where the single-layer perceptron stops, the flat first slope of a hidden weight, 6 of 100, starting point 2’s 0.33, the gradient check: this page’s computation

Summary

What backpropagation needs

  1. A hidden layer (01). Each hidden neuron draws a line, which splits XOR. But hidden neurons have no answer.
  2. A smooth activation function (02). A flat step function cuts the shares sent back to 0.
  3. Backpropagation finds each neuron’s share δ and from it every weight’s gradient (δ × incoming value), and gradient descent corrects the weights a little the opposite way (03). There is no guarantee of reaching the lowest place.

MythBackpropagation is the algorithm that trains a neural network.

In factBackpropagation is the part that gets the gradient. Correcting the weights with that gradient is done by an optimization method such as gradient descent, and the same gradient can be used by other methods too.

MythBackpropagation is how the brain learns.

In factThe 1986 paper itself says that, in its current form, it is not a plausible model of learning in brains. It ends by noting that, since gradient descent can build useful internal representations, more biologically plausible ways of doing it are worth looking for.

Confirmed · Hypothesis · Unknown

Sources: backpropagation and gradient descent told apart: Bishop 2006 §5.3 · not a model of learning in brains: Rumelhart, Hinton & Williams 1986, Nature p. 536 · local minima: Nature p. 535, PDP ch. 8 pp. 331–332 · the size of the first gradients: this page’s computation

Questions

Frequently asked questions

What is backpropagation?

A method that passes a neural network’s output error backward, from the output toward the input, with the chain rule, to get the gradient of the error for every weight at once. Hidden neurons, which have no answer, also get an error signal of their own by receiving the error signals of the neurons after them multiplied by the connection weights, and with it they get the gradients of their weights. It became widely known when Rumelhart, Hinton and Williams published it in Nature in 1986 as a way to train networks with hidden layers.

How is backpropagation different from gradient descent?

Backpropagation is the computation that gets the gradient; gradient descent moves the weights a little (by the learning rate η) in the opposite direction of that gradient. Bishop 2006 §5.3 separates the two and notes that the gradient from backpropagation can also be used by other optimization methods more powerful than gradient descent.

What does the chain rule do in backpropagation?

It lets the effect of a weight on the error be found as a product of rates: how the weight changes the total input, how the total input changes the output, and how the output changes the error. A hidden neuron’s error signal is the sum of the error signals of the neurons after it, each times its connection weight, multiplied by the slope of its own activation function (Rumelhart, Hinton and Williams 1986, eqs. 5–7).

Why does backpropagation compute backward from the output?

Because once the error signals at the output are known, those of the layer before follow from a few multiplications. One forward and one backward pass give the gradients of all the weights. Finite differences, changing the weights one at a time, need W forward computations for W weights, or 2W with central differences (Bishop 2006 §5.3.3).

Why must the activation function be differentiable for backpropagation?

A step function is flat almost everywhere (its steepness is 0), so it does not say which way to change a weight to reduce the error. A differentiable function like the sigmoid σ(s) = 1 / (1 + e⁻ˢ) has a steepness σ(1 − σ) that is not 0, so the error passes backward. The original paper says any function with a bounded derivative will do (Rumelhart, Hinton and Williams 1986, eqs. 2, 5).

Does backpropagation always find the answer?

No. The error surface has local minima, and gradient descent can stop in one (Rumelhart, Hinton and Williams 1986). For learning XOR with two hidden neurons, PDP chapter 8 reports getting stuck twice in hundreds of runs; in this page’s computation (learning rate 0.5, starting weights from −0.3 to 0.3), 6 of 100 starting points were not solved within 30,000 sweeps.

What is a multilayer perceptron (MLP)?

A neural network that stacks neurons in an input layer, one or more hidden layers and an output layer, connected only from earlier layers to later ones. Each neuron multiplies the outputs of the layer before by weights, adds them up with a bias, and puts the result into an activation function. The weights of the hidden layers learn from the gradients that backpropagation computes (Rumelhart, Hinton and Williams 1986, p. 533).

Why does XOR need a hidden layer?

One neuron splits the input plane with one straight line, and XOR must put 00 and 11 on one side and 01 and 10 on the other, so no such line exists. Hidden neurons give several lines, which can split them (PDP chapter 8 pp. 318–321). On this page, taking out the hidden layer makes the error stop at 0.50 even with the same learning rule.

Sources: Rumelhart, Hinton & Williams 1986 (Nature 323 eqs. 2, 5–7, pp. 533, 535) · Bishop 2006 §5.3, §5.3.3 · PDP ch. 8 pp. 318–321, 331–332

Further reading