Backpropagation Algorithm

Neural Networks (NN) are non-linear classifiers that can be formulated as a series of matrix multiplications. Just like linear classifiers, they can be trained using the same principles we followed before, namely the gradient descent algorithm. The difficulty arises in computing the gradients.

But first things first.

Let’s start with a straightforward example of a two-layered NN, with each layer containing just one neuron.

Notations

• The superscript defines the layer that we are in.
• $o^L$ denotes the activation of layer L.
• $w^L$ is a scalar weight of the layer L.
• $b^L$ is the bias term of layer L.
• $C$ is the cost function, $t$ is our target class, and $f$ is the activation function.

Forward pass

Our lovely model would look something like this in a simple sketch:

We can write the output of a neuron at layer $L$ as:

$$o^L =f( w^{L}o^{L-1} +b^L)$$

To simplify things, let’s define:

$$z^L = w^{L}o^{L-1} +b^L$$

so that our basic equation will become:

$$o^L=f(z^l)$$

We also know that our loss function is:

$$C = (o^L - t)^2$$

This is the so-called forward pass. We take some input and pass it through the network. From the output of the network, we can compute the loss $C$.

Backward pass

Backward pass is the process of adjusting the weights $w$ in all the layers to minimize the loss $C$.

To adjust the weights based on the training example, we can use our known update rule:

$$w^{L}_{t} = w^{L}_{t-1} - \lambda * \frac{\partial C}{\partial w^L}$$

where $\lambda$ is the learning rate that scales down the gradient.

It should be clear by now that the only thing left to compute is the gradient $\frac{\partial C}{\partial w^L}$ (the derivative of the loss with respect to the weight).

One way to think about computing $\frac{\partial C}{\partial w^L}$ is through the following diagram, which is called computational graph:

We summarize the performed operation in this way. To convert this into math, we need to revisit the chain rule.

The chain rule for the backward pass

To compute the gradient $\frac{\partial C}{\partial w^L}$, our most useful tool is calculus and the chain rule. Using both, we can write:

$$\frac{\partial C}{\partial w^L}= \frac{\partial z^L}{\partial w^L} * \frac{\partial o^L}{\partial z^L} * \frac{\partial C}{\partial o^L}$$

It is evident that the final gradient is affected by the gradients of the previous neuron, which in turn is affected by the gradients of the one before. You can see that in order to compute the gradient, we need to go back (through the chain rule) all the way to the beginning of the network.

In other terms, we need to propagate the error backwards. This is how the backpropagation algorithm got its name.

To find the gradients, let’s compute all the subgradients. By using basic calculus, we get:

$$C = (o^L - t)^2 -> \frac{\partial C}{\partial o^L} = 2( o^L -t)$$

$$o^L =f( w^{L}o^{L-1} +b^L) = f(z^L) -> \frac{\partial o^L}{\partial z^L} = f'( z^L)$$

$$z^L = w^{L}o^{L-1} +b^L -> \frac{\partial z^L}{\partial w^L} = o^{L-1}$$

Combining them all together, we acquire our final gradient:

$$\frac{\partial C}{\partial w^L}= o^{L-1} * f'( o^L) * 2( o^L -t)$$

Similar equations can be derived for the biases. Instead of $\frac{\partial z^L}{\partial w^L}$ , we would have:

$$z^L = w^{L}o^{L-1} +b^L -> \frac{\partial z^L}{\partial b^L} = 1$$

For completion, if we do the math, we get:

$$\frac{\partial C}{\partial b^L}= f'( o^L) * 2( o^L -t)$$

Now, we can adjust the weight and biases based on a single training example based on the update rule:

$$w^{L}_{t} = w^{L}_{t-1} - \lambda * \frac{\partial C}{\partial w^L}$$

Next, we’ll feed the next example and readjust, and repeat. This is the infamous backpropagation.

You might argue that this is oversimplified because we only have 1 neuron. To be honest, not much will change if we add more neurons per layer. We will essentially conclude to the same equation.

$$\frac{\partial C}{\partial w^L_{jk}}= \frac{\partial z^L_j}{\partial w^L_{jk}} * \frac{\partial o^L_j}{\partial z^L_j} * \frac{\partial C}{\partial o^L_j}$$

Here $j$ is a neuron in the layer $L$, while k a neuron in the layer $L-1$.

And if we want to present the derivative in its final form, we have:

$$\frac{\partial C}{\partial w^L_{jk}} = o^{L-1}_k* f'(o^L_j) * \frac{\partial C}{\partial o^L_j}$$

where:

$$\frac{\partial C}{\partial o^L_j} = \sum_{j=0}^{n_{L+1} -1 } w^{L+1}_{jk} * f'({o^{L+1}_j}) * \frac{\partial C}{\partial o^{L+1}_j} = 2(o^L_j -t_j)$$

Two final things to note here:

• The derivative with respect to the activation is a summation due to the fact that the activation of a neuron now depends on the activations of all the neurons on the previous layer.
• The same derivative also depends on the derivatives of the next layer’s activation (backpropagation of the error).

You now have a sense of how NNs learn, and that is no easy task.

Important note: We will not be computing gradients in every network that we define. The gradients are computed automatically in modern frameworks such as PyTorch.

No more partial derivatives!