Backpropagation Algorithm

Consider a deep neural network $\mathbf{f}[{\mathbf{x}}_i,\varphi ]$ that takes inputs ${\mathbf{x}}_i$, has $K$ hidden layers with ReLU activations, and individual loss term $\text{l}[\mathbf{f}[{\mathbf{x}}_i,\varphi ],{\mathbf{y}}_i]$.

The goal of backpropagation is to compute the derivatives $\partial {\ell }_i/\partial {\beta }_k$ and $\partial {\ell }_i/\partial {\mathbf{\Omega }}_{\mathbf{k}}$ with respect to the biases ${\beta }_k$ and weights ${\mathbf{\Omega }}_k$.

Forward pass

We compute and store the following quantities:

$$\begin{array}{rl}{\mathbf{f}}_0& ={\beta }_0+{\mathbf{\Omega }}_0{\mathbf{x}}_i\\ {\mathbf{h}}_k& =\mathbf{a}[{\mathbf{f}}_{k-1}]\\ {\mathbf{f}}_k& ={\beta }_k+{\mathbf{\Omega }}_k{\mathbf{h}}_k\end{array}$$

where $k\in \{1,2,...K\}$.

Backward pass

We start with the derivative $\partial {\ell }_i/\partial {\mathbf{f}}_K$ of the loss function ${\ell }_i$ with respect to the network output ${\mathbf{f}}_k$ and work backward through the network. For $k\in \{K,K-1,\dots ,1\}$, we do:

$$\begin{array}{rl}\frac{\partial {\ell }_i}{\partial {\beta }_k}& =\frac{\partial {\ell }_i}{\partial {\mathbf{f}}_{\mathbf{k}}}\\ \frac{\partial {\ell }_i}{\partial {\mathbf{\Omega }}_k}& =\frac{\partial {\ell }_i}{\partial {\mathbf{f}}_k}{\mathbf{h}}_k^T\end{array}$$

We then pass backward to the previous layer:

$$\begin{array}{rl}\frac{\partial {\ell }_i}{\partial {\mathbf{f}}_{k-1}}& =\mathbb{I}[{\mathbf{f}}_{k-1}>0]\odot \frac{\partial {\ell }_i}{\partial {\mathbf{h}}_k}\\ & =\mathbb{I}[{\mathbf{f}}_{k-1}>0]\odot \left({\mathbf{\Omega }}_k^T\frac{\partial {\ell }_i}{\partial {\mathbf{f}}_k}\right)\end{array}$$

where:

• $\odot$ is a pointwise multiplication
• $\mathbb{I}[{\mathbf{f}}_{k-1}>0]$ is a vector containing ones where ${\mathbf{f}}_{k-1}$ is greater than zero and zeros elsewhere.
• Thus, the $\mathbb{I}[{\mathbf{f}}_{k-1}>0]\odot$ operation is a mask applying the activation function

Finally, we compute the derivatives with respect to the first set of weights and biases:

$$\begin{array}{rl}\frac{\partial {\ell }_i}{\partial {\mathbf{\Omega }}_0}& =\frac{\partial {\ell }_i}{\partial {\mathbf{f}}_0}{\mathbf{x}}_i^T\\ \frac{\partial {\ell }_i}{\partial {\beta }_0}& =\frac{\partial {\ell }_i}{\partial {\mathbf{f}}_0}\end{array}$$

We calculate these derivatives for every training example in the batch and sum them together to retrieve the gradient for the SGD update.

Backpropagation is extremely efficient; the most demanding computational step in the forward and backward pass is matrix multiplication (by $\Omega$ and ${\Omega }^T$, respectively) which only requires additions and multiplications. However, it is not memory efficient; the intermediate values in the forward pass must all be stored, which can limit the size of the model we can train.