Backpropagation

Is an algorithm used to calculate the gradient of the loss function of an output from a Feedforward Neural Networks.

Backpropagation uses the chain rule of calculus so that the gradient of the loss function can be calculated through a Feedforward Neural Networks by recursively applying the chain rule. So a weight vector (initialized by the user or by a step of Stochastic Gradient Descent) is sent forward through the network, a process called forward propagation. When this is done the Feedforward Neural Networks will have calculated an output, which can be used in recursive use of the chain rule to calculate the gradient backwards through the network, which is what backpropagation is.

Example

In a neural network with one hidden layer, we find the gradient of the loss function $J(\mathbf{\theta })$ (with $\mathbf{X}$ and $\mathbf{y}$ as implicit inputs to keep notation uncluttered) by

$$\nabla J\left(\mathbf{\theta }\right)=\left(\begin{array}{c}\frac{\partial J\left(f^{\text{out}}\left(f^{(1)}\left(\mathbf{\theta }\right)\right)\right)}{\partial {\theta }_1}\\ \\ ⋮\\ \\ \frac{\partial J\left(f^{\text{out}}\left(f^{(1)}\left(\mathbf{\theta }\right)\right)\right)}{\partial {\theta }_m}\end{array}\right)$$

where each element is found by

$$\frac{\partial J\left(f^{\text{out}}\left(f^{(1)}\left(\mathbf{\theta }\right)\right)\right)}{\partial {\theta }_i}=\frac{\partial J\left(f^{\text{out}}\left(f^{(1)}\left(\mathbf{\theta }\right)\right)\right)}{\partial f^{\text{out}}\left(f^{(1)}\left(\mathbf{\theta }\right)\right)}\frac{\partial f^{\text{out}}\left(f^{(1)}\left(\mathbf{\theta }\right)\right)}{\partial f^{(1)}\left(\mathbf{\theta }\right)}\frac{\partial f^{(1)}\left(\mathbf{\theta }\right)}{\partial {\theta }_i}$$

A computational graph of calculating the above gradient can be seen below. 

Here $f^{\prime }$ indicates that the function of the node is derived with regard to its input and $\times$ indicates that the node is a product of the nodes pointing to it.