What is the back-propagation algorithm and how does it work?
3 Answers
The back propagation algorithm is a gradient descent algorithm for fitting a neural network model. (as mentionned by @Dikran) Let me explain how.
Formally: Using the calculation of the gradient at the end of this post within equation [1] below (that is a definition of the gradient descent) gives the back propagation algorithm as a particular case of the use of a gradient descent.
A neural network model Formally, we fix ideas with a simple single layer model:
$$ f(x)=g(A^1(s(A^2(x)))) $$ where $g:\mathbb{R} \rightarrow \mathbb{R}$ and $s:\mathbb{R}^M\rightarrow \mathbb{R}^M$ are known with for all $m=1\dots,M$, $s(x)[m]=\sigma(x[m])$, and $A^1:\mathbb{R}^M\rightarrow \mathbb{R}$, $A^2\mathbb{R}^p\rightarrow \mathbb{R}^M$ are unknown affine functions. The function $\sigma:\mathbb{R}\rightarrow \mathbb{R}$ is called activation function in the framework of classification.
A quadratic Loss function is taken to fix ideas. Hence the input $(x_1,\dots,x_n)$ vectors of $\mathbb{R}^p$ can be fitted to the real output $(y_1,\dots,y_n)$ of $\mathbb{R}$ (could be vectors) by minimizing the empirical loss: $$\mathcal{R}_n(A^1,A^2)=\sum_{i=1}^n (y_i-f(x_i))^2\;\;\;\;\;\;\; [1]$$ with respect to the choice of $A^1$ and $A^2$.
Gradient descent A grandient descent for minimizing $\mathcal{R}$ is an algorithm that iterate: $$\mathbf{a}_{l+1}=\mathbf{a}_l-\gamma_l \nabla \mathcal{R}(\mathbf{a}_l),\ l \ge 0.$$ for well chosen step sizes $(\gamma_l)_l$ (also called learning rate in the framework of back propagation). It requires the calculation of the gradient of $\mathcal{R}$. In the considered case $\mathbf{a}_l=(A^1_{l},A^2_{l})$.
Gradient of $\mathcal{R}$ (for the simple considered neural net model) Let us denote, by $\nabla_1 \mathcal{R}$ the gradient of $\mathcal{R}$ as a function of $A^1$, and $\nabla_2\mathcal{R}$ the gradient of $\mathcal{R}$ as a function of $A^2$. Standard calculation (using the rule for derivation of composition of functions) and the use of the notation $z_i=A^1(s(A^2(x_i)))$ give $$\nabla_1 \mathcal{R}[1:M] =-2\times \sum_{i=1}^n z_i g'(z_i) (y_i-f(x_i))$$ for all $m=1,\dots,M$ $$\nabla_2 \mathcal{R}[1:p,m] =-2\times \sum_{i=1}^n x_i g'(z_i) z_i[m]\sigma'(A^2(x_i)[m]) (y_i-f(x_i))$$
Here I used the R notation: $x[a:b]$ is the vector composed of the coordinates of $x$ from index $a$ to index $b$.
Back-propogation is a way of working out the derivative of the error function with respect to the weights, so that the model can be trained by gradient descent optimisation methods - it is basically just the application of the "chain rule". There isn't really much more to it than that, so if you are comfortable with calculus that is basically the best way to look at it.
If you are not comfortable with calculus, a better way would be to say that we know how badly the output units are doing because we have a desired output with which to compare the actual output. However we don't have a desired output for the hidden units, so what do we do? The back-propagation rule is basically a way of speading out the blame for the error of the output units onto the hidden units. The more influence a hidden unit has on a particular output unit, the more blame it gets for the error. The total blame associated with a hidden unit then give an indication of how much the input-to-hidden layer weights need changing. The two things that govern how much blame is passed back is the weight connecting the hidden and output layer weights (obviously) and the output of the hidden unit (if it is shouting rather than whispering it is likely to have a larger influence). The rest is just the mathematical niceties that turn that intuition into the derivative of the training criterion.
I'd also recommend Bishops book for a proper answer! ;o)
It's an algorithm for training feedforward multilayer neural networks (multilayer perceptrons). There are several nice java applets around the web that illustrate what's happening, like this one: http://neuron.eng.wayne.edu/bpFunctionApprox/bpFunctionApprox.html. Also, Bishop's book on NNs is the standard desk reference for anything to do with NNs.
-
1$\begingroup$ In trying to build a permanent repository of high-quality statistical information in the form of questions & answers, we try to avoid link-only answers. If you're able, could you expand this, perhaps by giving a summary of the information at the link? $\endgroup$– Glen_bOct 8, 2015 at 3:26