Learning Representations by Back-propagating Errors

David E. Rumelhart  ·  Geoffrey E. Hinton  ·  Ronald J. Williams

This paper marks the beginning of modern deep learning and the popularization of backpropagation, the algorithm used to train deep neural networks. In a way this is the most important paper in deep learning and hence it's the perfect paper to start with.

Prerequisites

  1. A bit of multivariable calculus (chain rule)
  2. A bit of linear algebra (vector dot products and notation)
  3. A little bit of mathematical thinking

Neural Networks

Neural networks are the foundation of deep learning. Here we are going to provide an intuitive introduction and translate that to a more mathematical view of the subject.

Let us begin by considering a problem. Suppose you wish to define a function on the domain of images say \(\mathcal{I}\) which consists of images of both cats and dogs and you wish for your function to correctly classify a given image as a cat or a dog. This is a pretty difficult function to come up with yourself and so is a function that classifies the picture of a mole on one's skin as malignant or non-malignant.

Since these functions are hard to define we are going to approximate them and Neural Networks are the way to do this.

So essentially how it works is, you have an input vector with a dimension (say \(i\)) and then you map that \(i\)-dimensional vector to a different dimension to understand the complex relations between those individual units in that dimension. What this means is that we connect the input layer to a hidden layer of dimension say \(m\) and usually \(m > i\). Now this may also be reversed in some cases, the point is we take a different-dimension view of our input vector. This allows our network to understand the intricate details of the relationships of the features or units of our input dimension.

Now what we can do with this is we can then further propagate that hidden layer to more hidden layers until we reach our output dimension say \(o\).

So what happens during that transformation to each vector upon transformation across these layers?

Well, if we strictly go by the paper, they first proceed with a linear transformation of the vector given by:

$$x^{(n+1)} = W^{(n)} x^{(n)} + b^{(n)}$$

Here \(n\) denotes the layer index. The vector \(x^{(n)}\) represents the activations of the \(n\)-th layer and \(x^{(n+1)}\) represents the activations of the next layer. The weight matrix \(W^{(n)} \in \mathbb{R}^{b \times a}\) maps an input of dimension \(a\) to an output of dimension \(b\). The bias vector \(b^{(n)} \in \mathbb{R}^{b}\) allows the transformation to be shifted.

But we don't stop there, we also apply a non-linear function to these values which are called activation functions. By using these non-linear functions we achieve non-linearity in our connections which means that we can now understand non-linear relationships between our data. The original paper uses the sigmoid function given by:

$$\sigma(x) = \frac{1}{1 + e^{-x}}$$

But what are these weights? Well we do not know because if we did then we would know the answer. So what we do is we randomly initialize these weights and we usually use our friendly neighbourhood Gaussian distribution.

But if these weights are randomly initialized then how do we get to the answer?

The answer to this question is the backbone of modern deep learning and the answer is...

BACKPROPAGATION

The way the paper describes this felt a bit confusing but I will try to make it as simple as possible.

Now we will explain how it all works. Suppose you have to solve a problem of predicting a numerical value from some data. Imagine a neural network that has the following structure:

  1. An input layer of dimension \(a\): \(x \in \mathbb{R}^a\)
  2. A hidden layer of dimension \(b\): \(h \in \mathbb{R}^b\)
  3. An output layer of dimension \(o\): \(\hat{y} \in \mathbb{R}^o\)

The hidden layer representation is given by:

$$h = \sigma\left(W^{(1)} x + b^{(1)}\right)$$

where \(W^{(1)} \in \mathbb{R}^{b \times a}\), \(b^{(1)} \in \mathbb{R}^b\)

The final output is given by:

$$\hat{y} = \sigma\left(W^{(2)} h + b^{(2)}\right)$$

where \(W^{(2)} \in \mathbb{R}^{o \times b}\), \(b^{(2)} \in \mathbb{R}^o\)

What we just did is called a forward pass in the network — meaning we went from the input to the output. But this output is utter rubbish because our weights were random so we will get a random answer.

Now comes the most important step: we call it training the network, meaning we adjust the weights which were randomly initialized to get a better answer from our neural network.

But to find out how much we must correct ourselves, we first need to understand how wrong we were in the first place — and for that we use something known as a loss function. Loss functions are of many types but since here we are predicting a numerical value (called regression) and not classifying (called classification) we can use the Mean Squared Error (MSE) given by:

$$L = \frac{1}{2}(\hat{y} - y)^2$$

This is the case for a single value where \(\hat{y} \in \mathbb{R}\), \(y \in \mathbb{R}\). For our output layer it's given by:

$$L = \frac{1}{2}\|\hat{y} - y\|^2, \quad \hat{y} \in \mathbb{R}^{o},\ y \in \mathbb{R}^{o}$$

Now we have the information as to how wrong we are — let's now adjust our weights to make our network better. We adjust each of our weights as:

$$w \leftarrow w - \alpha \cdot \nabla_{w} L$$

So we have to calculate the gradient of our loss function with respect to each weight, and we can easily do so by using the chain rule.

Let us denote the pre-activation values of the output layer as:

$$z^{(2)} = W^{(2)}h + b^{(2)}$$

so that \(\hat{y} = \sigma(z^{(2)})\).

The gradient of the loss function with respect to the network output is:

$$\frac{\partial L}{\partial \hat{y}} = \hat{y} - y$$

Using the derivative of the sigmoid function:

$$\sigma'(z) = \sigma(z)(1 - \sigma(z))$$

we obtain the error term for the output layer:

$$\delta^{(2)} = (\hat{y} - y) \odot \hat{y}(1 - \hat{y})$$

The gradient of the loss with respect to the output layer weights and bias is:

$$\frac{\partial L}{\partial W^{(2)}} = \delta^{(2)} h^\top$$
$$\frac{\partial L}{\partial b^{(2)}} = \delta^{(2)}$$

We now propagate this error backward to the hidden layer:

$$\frac{\partial L}{\partial h} = (W^{(2)})^\top \delta^{(2)}$$

Let the hidden layer pre-activation be:

$$z^{(1)} = W^{(1)}x + b^{(1)}$$

and recall that \(h = \sigma(z^{(1)})\).

The error term for the hidden layer is then:

$$\delta^{(1)} = \left( (W^{(2)})^\top \delta^{(2)} \right) \odot h(1 - h)$$

The gradients with respect to the hidden layer parameters are:

$$\frac{\partial L}{\partial W^{(1)}} = \delta^{(1)} x^\top$$
$$\frac{\partial L}{\partial b^{(1)}} = \delta^{(1)}$$

Finally, the weights are updated using gradient descent with learning rate \(\alpha\):

$$W^{(2)} \leftarrow W^{(2)} - \alpha \frac{\partial L}{\partial W^{(2)}}$$ $$b^{(2)} \leftarrow b^{(2)} - \alpha \frac{\partial L}{\partial b^{(2)}}$$ $$W^{(1)} \leftarrow W^{(1)} - \alpha \frac{\partial L}{\partial W^{(1)}}$$ $$b^{(1)} \leftarrow b^{(1)} - \alpha \frac{\partial L}{\partial b^{(1)}}$$
Note: We usually omit the sigmoid function in the output layer in regression networks but we showed it here just to give the reader a better understanding of how the chain rule is used in Backpropagation.

The paper also describes an enhanced weight update using momentum. In modern notation:

$$v_t = \alpha v_{t-1} - \eta \nabla_w L$$
$$w_t = w_{t-1} + v_t$$

where \(v_t \equiv \Delta w(t)\).

More Resources

  1. 3Blue1Brown — Neural Network Playlist
  2. Andrej Karpathy — Zero to Hero Playlist