Backpropagation

David Wallace Croft

2005-02-18

Introduction

This is a derivation of a popular neural network training algorithm known as backpropagation. It is commonly used with feed-forward multilayer perceptrons.

To see backpropagation in action, check out the applet BackpropXOR in the CroftSoft Collection.

Definitions and Identities

1. Sigmoid Function
   

   $\sigma \left(x\right)=\frac{1}{(1+{\mathrm{e}}^{\mathrm{-x}})}$

2. Derivative of the Sigmoid Function
   

   $\sigma \text{'}\left(x\right)=\sigma \left(x\right)*[1-\sigma (x\left)\right]$

Simplest Case

This is a derivation of the backpropagation neural network training algorithm for the simplest case: a two-layer network with one neuron in each layer. In this derivation, all of the variables are scalars. Deriving the learning rule for the simplest case makes backpropagation easier to understand when vectors and matrices are introduced later.

s → v → b → σ → h → w → a → σ → r

A signal (s) is the input to the first layer hidden neuron. It is multiplied by the first layer weight (v). The weighted input (b) is then squashed by the nonlinear neuron to fall between zero and one using the sigmoidal function (σ). The output of the hidden neuron (h) is then multiplied by the weight (w). The weighted input from the hidden neuron (a) is fed to the squashing function of the second layer output neuron. The difference between the desired response (d) and the actual response (r) of the output neuron is the error (e). The objective function (l) is the scaled square of the error (e).

3. Objective Function
   

   $l=\mathrm{½}*e^2$

4. Error Function
   

   $e=d-r$

5. Response from Output Neuron
   

   $r=\sigma \left(a\right)$

6. Weighted Input from Hidden Neuron to Output Neuron
   

   $a=w*h$

7. Hidden Neuron Output
   

   $h=\sigma \left(b\right)$

8. Weighted Input to Hidden Neuron
   

   $b=v*s$

Output Layer

We seek to minimize the objective function (l) by modifying the weight (w) to the output layer. This is done by taking the partial derivative of the objective function with respect to the weights. This derivative is then used to modify the weight using a gradient descent algorithm.

9. Gradient for Output Layer Weight, Chain Rule
   

   $\frac{\partial l\left(w\right)}{\partial w}=\frac{\partial l\left(e\right)}{\partial e}*\frac{\partial e\left(r\right)}{\partial r}*\frac{\partial r\left(a\right)}{\partial a}*\frac{\partial a\left(w\right)}{\partial w}$

10. Output Layer Weight Gradient, First Term
    

    $\frac{\partial l\left(e\right)}{\partial e}=\frac{\partial (\mathrm{½}*e^2)}{\partial e}=e=d-r$

11. Output Layer Weight Gradient, Second Term
    

    $\frac{\partial e\left(r\right)}{\partial r}=\frac{\partial (\mathrm{d}-\mathrm{r})}{\partial r}=-1$

12. Output Layer Weight Gradient, Third Term
    

    $\frac{\partial r\left(a\right)}{\partial a}=\frac{\partial \sigma \left(\mathrm{a}\right)}{\partial a}=\sigma \left(\mathrm{a}\right)*(1-\sigma \left(\mathrm{a}\right))=r*(1-r)$

13. Output Layer Weight Gradient, Fourth Term
    

    $\frac{\partial a\left(w\right)}{\partial w}=\frac{\partial (w*h)}{\partial w}=h$

14. Gradient for Output Layer Weight, Combined Terms
    

    $\frac{\partial l\left(w\right)}{\partial w}=[d-r]*\left[-1\right]*[r*(1-r)]*\left[h\right]$

Hidden Layer

We also seek to minimize the objective function (l) by modifying the weight (v) to the hidden layer. The derivation of the first three terms in the gradient for the hidden layer weight are skipped as they are the same as the first three terms in the gradient for the output layer derived previously.

15. Gradient for Hidden Layer Weight, Chain Rule
    

    $\frac{\partial l\left(v\right)}{\partial v}=\frac{\partial l\left(e\right)}{\partial e}*\frac{\partial e\left(r\right)}{\partial r}*\frac{\partial r\left(a\right)}{\partial a}*\frac{\partial a\left(h\right)}{\partial h}*\frac{\partial h\left(b\right)}{\partial b}*\frac{\partial b\left(v\right)}{\partial v}$

16. Hidden Layer Weight Gradient, Fourth Term
    

    $\frac{\partial a\left(h\right)}{\partial h}=\frac{\partial (w*h)}{\partial h}=w$

17. Hidden Layer Weight Gradient, Fifth Term
    

    $\frac{\partial h\left(b\right)}{\partial b}=\frac{\partial \sigma \left(\mathrm{b}\right)}{\partial b}=\sigma \left(\mathrm{b}\right)*(1-\sigma \left(\mathrm{b}\right))=h*(1-h)$

18. Hidden Layer Weight Gradient, Sixth Term
    

    $\frac{\partial b\left(v\right)}{\partial v}=\frac{\partial (v*s)}{\partial v}=s$

19. Gradient for Hidden Layer Weight, Combined Terms
    

    $\frac{\partial l\left(v\right)}{\partial v}=[d-r]*\left[-1\right]*[r*(1-r)]*\left[w\right]*[h*(1-h\left)\right]*\left[s\right]$

Local Gradient

We noted that the first three terms of the gradients for the output layer and the hidden layer are the same. The negative product of these three terms is the local gradient. The local gradient can be computed for the output layer and then reused for the hidden layer.

20. Local Gradient for Output Neuron
    

    ${\delta }_o=-\frac{\partial l\left(a\right)}{\partial a}=-\frac{\partial l\left(e\right)}{\partial e}*\frac{\partial e\left(r\right)}{\partial r}*\frac{\partial r\left(a\right)}{\partial a}=e*r*(1-r)$

21. Output Layer Gradient Abbreviated

    $\frac{\partial l\left(w\right)}{\partial w}={-\delta }_o*h$

22. Hidden Layer Gradient Abbreviated
    

    $\frac{\partial l\left(v\right)}{\partial v}={-\delta }_o*w*h*(1-h)*s$

Backpropagation

The local gradient shows how the objective function decreases as the weighted input to the neuron increases. The local gradient for an output neuron depends on the error (e). The local gradients for hidden layer neurons, however, depend on the local gradients of the following layer. Thus the computation of the local gradients must be propagated from the back layer of the network to the front. The weight gradients can then be expressed as functions of the local gradients and the unweighted inputs.

23. Local Gradient for Hidden Neuron
    

    ${\delta }_h=-\frac{\partial l\left(b\right)}{\partial b}=-\frac{\partial l\left(e\right)}{\partial e}*\frac{\partial e\left(r\right)}{\partial r}*\frac{\partial r\left(a\right)}{\partial a}*\frac{\partial a\left(h\right)}{\partial h}*\frac{\partial h\left(b\right)}{\partial b}$

24. Local Gradient Backpropagation
    

    ${\delta }_h={\delta }_o*\frac{\partial a\left(h\right)}{\partial h}*\frac{\partial h\left(b\right)}{\partial b}$

25. The Pattern for Hidden Layers

    ${\delta }_h={\delta }_o*w*h*(1-h)$

26. Hidden Layer Gradient Abbreviated Further
    

    $\frac{\partial l\left(v\right)}{\partial v}={-\delta }_h*s$

Gradient Descent

Now that we have the gradient of the objective function with respect to the weights in terms of the of local gradients, we can incrementally decrease the objective function, and therefore the overall error, by shifting the weights.

27. Weight Update Rule

    $w(t+1)=w\left(t\right)+\Delta w$

28. Descend the Gradient

    $\Delta w=-\eta *\frac{\partial l\left(w\right)}{\partial w}$

29. A Negative Becomes a Positive

    $\Delta w=\eta *{\delta }_o*h$

30. The Weight Update Rule Revised

    $w(t+1)=w\left(t\right)+\eta *{\delta }_o*h$

31. Similar Pattern for Hidden Weights

    $v(t+1)=v\left(t\right)+\eta *{\delta }_h*s$

Links

• Character Entity References in HTML 4
• Exponentional Function
• MathML Basics
• MathML Fundamentals