Vilhelm Bergsøe - Introduction to Neural Networks and Backpropagation

Introduction to Neural Networks and Backpropagation

Tue 30 Apr 2024 - 12 min read

I originally wrote these notes as a way to make the concepts more concrete for myself.

Neural networks are a family of function approximators built by composing layers of relatively simple mathematical operations. Their name comes from a loose analogy with biological neurons, but modern neural networks should not be mistaken for realistic models of the brain.

Despite the simplicity of their individual parts, neural networks can approximate complicated relationships in data. They are used for tasks such as image classification, recommendation systems, sequence modelling and many other kinds of function approximation.

In this post, I’ll build up a small fully connected neural network from individual neurons, describe how information moves through it and then derive the backpropagation algorithm used to calculate its gradients. Finally, we’ll use those gradients to train the network with gradient descent.

An introduction to Neural Networks

Perceptron (single-neuron function)

One influential early model was Frank Rosenblatt’s perceptron, introduced in the late 1950s in the paper “The Perceptron: A probabilistic model for information storage and organization in the brain”¹. A perceptron combines several inputs into a weighted sum and applies a threshold to produce its output. Modern artificial neurons use the same broad pattern, although they commonly use differentiable activation functions instead of a hard threshold.

A perceptron receives $𝑛$ inputs $𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}$ . Each input $𝑥_{𝑖}$ has a corresponding adjustable weight $𝑤_{𝑖}$ . Together with a bias $𝑏$ , these values form a weighted sum of the inputs.

Figure 1: The weighted sum and activation of a single neuron.

This means multiplying every input $𝑥_{𝑖}$ by its corresponding weight $𝑤_{𝑖}$ , summing the results and adding the bias. The resulting scalar is the pre-activation $𝑧$ :

𝑧 = \sum_{𝑖 = 1}^{𝑛} 𝑤_{𝑖} 𝑥_{𝑖} + 𝑏

where $𝑥_{𝑖}$ is the $𝑖$ -th input, $𝑤_{𝑖}$ is its weight, $𝑏$ is the bias and $𝑛$ is the number of inputs.

In Rosenblatt’s formulation, this value is passed through a step function. The perceptron outputs $1$ if $𝑧$ is greater than $0$ and $0$ otherwise:

𝑎 = {\begin{cases} 1 & if 𝑧 > 0 \\ 0 & else \end{cases}

Modern artificial neurons keep the same weighted sum but replace the hard threshold with a more general activation function $𝜎$ :

𝑎 = 𝜎 (𝑧)

Here, $𝑎$ is the neuron’s scalar output, or activation. Common choices for $𝜎$ include ReLU, sigmoid and hyperbolic tangent. They all introduce nonlinearity, but they have different ranges and behave differently during training.

This becomes cumbersome notation for when we need to describe larger networks with multiple layers or multiple neurons per layer. For this reason we can make use of vector and matrix notation to better organise our data.

Now we can instead represent both $𝑥$ and $𝑤$ as column-vectors.

𝑥 = [\begin{matrix} 𝑥_{1} \\ 𝑥_{2} \\ ⋮ \\ 𝑥_{𝑛} \end{matrix}] 𝑤 = [\begin{matrix} 𝑤_{1} \\ 𝑤_{2} \\ ⋮ \\ 𝑤_{𝑛} \end{matrix}]

Because both are column vectors, the weighted sum can be written as $𝑤^{𝑇} 𝑥$ . We then add the bias and apply the activation function:

𝑧 = 𝑤^{𝑇} 𝑥 + 𝑏

𝑎 = 𝜎 (𝑧)

So, to summarise, a neuron takes an input vector $𝑥$ and produces a scalar. It calculates a weighted sum of the inputs, adds a bias and applies a nonlinear activation function.

The nonlinearity is important because it allows a network to model nonlinear relationships. Without nonlinear activation functions, a stack of layers would still be equivalent to a single linear transformation. For example, composing these two linear functions only produces another linear function:

\begin{aligned} 𝑓 (𝑥) & = 2 𝑥 + 1 \\ 𝑔 (𝑥) & = 3 𝑥 - 2 \\ 𝑔 (𝑓 (𝑥)) & = 𝑔 (2 𝑥 + 1) \\ = 3 (2 𝑥 + 1) - 2 \\ = 6 𝑥 + 3 - 2 \\ = 6 𝑥 + 1 \end{aligned}

Multiple neurons and the MLP

A multi-layer perceptron (also called an MLP) is built by arranging our neurons into layers. In what’s called a fully connected layer, every neuron receives every activation from the previous layer as input. Each neuron has its own weights and bias so each can produces a distinct scalar output from the same input vector.

We can collect these individual scalar outputs into a column vector $𝑎^{𝑙}$ , where $𝑙$ identifies the layer. For example, the two outputs $𝑠_{1}$ and $𝑠_{2}$ in the diagram below form the activation vector $𝑎^{𝑙} = [\begin{matrix} 𝑠_{1} \\ 𝑠_{2} \end{matrix}]$ .

Figure 2: Two neuron outputs collected into the activation vector

𝑎^{𝑙}

Suppose layer $𝑙 - 1$ contains $𝑛$ activations and layer $𝑙$ contains $𝑚$ neurons. The weights for the whole layer can be represented by a matrix $𝑊^{𝑙}$ with $𝑚$ rows and $𝑛$ columns:

𝑊^{𝑙} = [\begin{matrix} 𝑤_{11}^{𝑙} & 𝑤_{12}^{𝑙} & \dots & 𝑤_{1 𝑛}^{𝑙} \\ 𝑤_{21}^{𝑙} & 𝑤_{22}^{𝑙} & \dots & 𝑤_{2 𝑛}^{𝑙} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 𝑤_{𝑚 1}^{𝑙} & 𝑤_{𝑚 2}^{𝑙} & \dots & 𝑤_{𝑚 𝑛}^{𝑙} \end{matrix}]

The entry $𝑤_{𝑗 𝑘}^{𝑙}$ is the weight connecting activation $𝑘$ in the previous layer to neuron $𝑗$ in layer $𝑙$ . The first index therefore selects a destination neuron, while the second selects an input to that neuron. Each neuron also has its own bias, collected in the vector

𝑏^{𝑙} = [\begin{matrix} 𝑏_{1}^{𝑙} \\ 𝑏_{2}^{𝑙} \\ ⋮ \\ 𝑏_{𝑚}^{𝑙} \end{matrix}] .

This gives us the dimensions

𝑎^{𝑙 - 1} \in ℝ^{𝑛}, 𝑊^{𝑙} \in ℝ^{𝑚 \times 𝑛}, 𝑏^{𝑙} \in ℝ^{𝑚} .

Figure 3: A two-layer fully connected network.

The layer first computes a vector of pre-activations $𝑧^{𝑙}$ and then applies the activation function elementwise:

𝑧^{𝑙} = 𝑊^{𝑙} 𝑎^{𝑙 - 1} + 𝑏^{𝑙}

𝑎^{𝑙} = 𝜎^{𝑙} (𝑧^{𝑙})

Both $𝑧^{𝑙}$ and $𝑎^{𝑙}$ are vectors in $ℝ^{𝑚}$ . In our network pictured above, the input vector is $𝑎^{0} = 𝑥$ , the hidden layer produces $𝑎^{1}$ , and the output layer produces $𝑎^{2}$ .

More generally, an MLP repeats this calculation for layers $𝑙 = 1, \dots, 𝐿$ , using the activation from one layer as the input to the next. Evaluating those layers from $𝑎^{0}$ through to $𝑎^{𝐿}$ is called the forward pass. Training the network requires working in the opposite direction to determine how each parameter influenced the final error. That is the purpose of backpropagation.

Backpropagation and optimization (training)

Neural networks are trained by adjusting these weights and biases so that their predictions produce a smaller loss. We do this by first determining how each parameter contributes to said loss.

Backpropagation utilises the chain rule from differential calculus to compute the gradient of the loss function, also known as an objective function, with respect to every weight and bias in the network. It starts from the output and propagates this information back through each layer.

An optimization algorithm such as gradient descent then uses the resulting gradients to update the parameters.

Loss calculation

A loss function measures how far the network’s prediction $𝑎^{𝐿}$ is from the desired target $𝑦$ , producing a single scalar $𝐶 (𝑎^{𝐿}, 𝑦)$ . Mean squared error (MLE) is a common choice for regression while classification problems often use a form of cross entropy.

The choice of loss function determines the gradient at the output layer. From there, backpropagation then uses the chain rule to propagate that gradient through the rest of the network.

For each layer $𝑙$ , define the pre-activation gradient

𝛿^{𝑙} ≔ \frac{𝜕 𝐶}{𝜕 𝑧^{𝑙}}

The vector $𝛿^{𝑙}$ has the same dimensions as $𝑧^{𝑙}$ . At the output layer, the chain rule gives

𝛿^{𝐿} = \frac{𝜕 𝐶}{𝜕 𝑧^{𝐿}} = \frac{𝜕 𝐶}{𝜕 𝑎^{𝐿}} ⊙ {(𝜎^{𝐿})}^{'} (𝑧^{𝐿})

where $⊙$ denotes elementwise multiplication.

In order to calculate $𝛿^{𝑙}$ for an earlier layer, we follow the computational path from the loss $𝐶$ back to the pre-activations $𝑧^{𝑙}$ , applying the chain rule at each step.

Starting with $𝛿^{𝐿}$ at the output layer, we can work backwards through the network to obtain the pre-activation gradient for each preceding layer.

\begin{aligned} 𝛿^{𝑙} & = \frac{𝜕 𝐶}{𝜕 𝑧^{𝑙}} \\ = \frac{𝜕 𝐶}{𝜕 𝑎^{𝐿}} \frac{𝜕 𝑎^{𝐿}}{𝜕 𝑧^{𝐿}} \frac{𝜕 𝑧^{𝐿}}{𝜕 𝑎^{𝐿 - 1}} \dots \frac{𝜕 𝑧^{𝑙 + 1}}{𝜕 𝑎^{𝑙}} \frac{𝜕 𝑎^{𝑙}}{𝜕 𝑧^{𝑙}} \end{aligned}

Figure 4: Backpropagation follows the computational path in reverse.

Rather than expanding the entire chain for every layer, we can simplify the calculation by only looking at layer $𝑙$ and the following layer $𝑙 + 1$ . Suppose the two layers contain $𝑛$ and $𝑚$ neurons, respectively. Starting with the definition of the next layer’s pre-activation and working backwards through the linear transformation and activation function gives

\begin{aligned} 𝑧^{𝑙 + 1} & = 𝑊^{𝑙 + 1} 𝑎^{𝑙} + 𝑏^{𝑙 + 1} & \in ℝ^{𝑚} \\ \frac{𝜕 𝐶}{𝜕 𝑎^{𝑙}} & = {(𝑊^{𝑙 + 1})}^{𝑇} 𝛿^{𝑙 + 1} & \in ℝ^{𝑛} \\ 𝛿^{𝑙} & = \frac{𝜕 𝐶}{𝜕 𝑎^{𝑙}} ⊙ {(𝜎^{𝑙})}^{'} (𝑧^{𝑙}) & \in ℝ^{𝑛} \\ = ({(𝑊^{𝑙 + 1})}^{𝑇} 𝛿^{𝑙 + 1}) ⊙ {(𝜎^{𝑙})}^{'} (𝑧^{𝑙}) & \in ℝ^{𝑛} . \end{aligned}

This gives us the backward step: once we know $𝛿^{𝑙 + 1}$ , we can calculate $𝛿^{𝑙}$ and continue backwards through the network. The transposed weight matrix reverses the mapping from $ℝ^{𝑛} \to ℝ^{𝑚}$ to $ℝ^{𝑚} \to ℝ^{𝑛}$ .

Finally, the parameter gradients are computed, which are the changes in the loss function $𝐶$ with respect to the parameters $𝑊^{𝑙}$ and $𝑏^{𝑙}$ . Looking at an individual weight and bias first, and then collecting the results, we get:

\begin{aligned} \frac{𝜕 𝐶}{𝜕 𝑤_{𝑗 𝑘}^{𝑙}} & = \frac{𝜕 𝑧_{𝑗}^{𝑙}}{𝜕 𝑤_{𝑗 𝑘}^{𝑙}} \frac{𝜕 𝐶}{𝜕 𝑧_{𝑗}^{𝑙}} \\ = 𝑎_{𝑘}^{𝑙 - 1} 𝛿_{𝑗}^{𝑙} \\ \frac{𝜕 𝐶}{𝜕 𝑊^{𝑙}} & = 𝛿^{𝑙} {(𝑎^{𝑙 - 1})}^{𝑇} \\ \frac{𝜕 𝐶}{𝜕 𝑏_{𝑗}^{𝑙}} & = \frac{𝜕 𝑧_{𝑗}^{𝑙}}{𝜕 𝑏_{𝑗}^{𝑙}} \frac{𝜕 𝐶}{𝜕 𝑧_{𝑗}^{𝑙}} \\ = 1 \cdot 𝛿_{𝑗}^{𝑙} = 𝛿_{𝑗}^{𝑙} \\ \frac{𝜕 𝐶}{𝜕 𝑏^{𝑙}} & = 𝛿^{𝑙} . \end{aligned}

Now that we know how each parameter in our neural net influences the loss, we just need to figure out how to optimize our network to minimise the loss. Luckily, there is a simple and effective way of doing that as we’ve already done the hard part.

Gradient descent and optimization

The gradient points in the direction in which the loss increases most quickly. Gradient descent therefore updates each parameter in the opposite direction. Using the parameter gradients derived above, the updates for layer $𝑙$ are

\begin{aligned} 𝑊^{𝑙} & \leftarrow 𝑊^{𝑙} - 𝜂 \frac{𝜕 𝐶}{𝜕 𝑊^{𝑙}} \\ 𝑏^{𝑙} & \leftarrow 𝑏^{𝑙} - 𝜂 \frac{𝜕 𝐶}{𝜕 𝑏^{𝑙}}, \end{aligned}

where $𝜂$ is the learning rate, which controls the size of each update.

Ordinary gradient descent calculates these gradients over the entire training set before performing an update. Stochastic gradient descent (SGD) instead uses a randomly selected training example or, more commonly, a small batch of examples. Each update is then cheaper to compute, although the resulting gradient is a noisier estimate of the full-dataset gradient.

Training basically just consists of repeating these steps: perform a forward pass, calculate the loss, use backpropagation to calculate the parameter gradients and finally update the parameters. Repeating this process allows the network to gradually find parameters that produce a smaller loss on the training data.

¹Rosenblatt, F. 1958. “The perceptron: A probabilistic model for information storage and organization in the brain”. Psychological Review 65 (6): 386–408. https://doi.org/10.1037/h0042519.

tags: [machine learning, mathematics]