Click here to view the companion module for these notes

Table of Contents

• Leaky ReLU
• Forward Pass via Matrix Operations
• Backward Pass via Matrix Operations

In homework 5, you implemented gradient descent to perform logistic regression. This can be thought of as learning a neural network with a single neuron ("the perceptron"), but the best we can do in this case is to learn a separating hyperplane. As we discussed in class, though, when we put a bunch of neurons together, we can learn arbitrarily complicated functions. So now we're going to take gradient descent to the next level to learn how to solve arbitrary fully connected feed forward networks, also known as multilayer perceptrons (MLPs), by using an algorithm called backpropagation as a subroutine. Actually, as you will see, this is just a fancy name for the chain rule of calculus, specialized to neural networks.

At this point, we could just turn to one of the myriad libraries out there like pytorch to optimize neural network models for us, but I want you to see if we use the right definitions, then creating a vanilla neural network solver really isn't that much code in numpy. It's also important that know how everything works under the hood when you run pytorch (see this Medium article by Andrej Karpathy on why it's important to understand these details). You will implement the algorithms I describe below in homework 6.

Leaky ReLU

Before I dive into the backpropagation algorithm, I first want to define a new type of activation function that will come in handy.

One of the issues with the logistic function is that it suffers from the problem of "vanishing gradients"; if the input to the logistic function is far from zero, then it is nearly flat, as shown below:

This makes it slow to learn, as the step sizes for internal weights in the network in these regimes will be very small. To address this, there's another activation function that's very popular known as the Leaky Rectified Linear Unit (Leaky ReLU), which can be defined as the following piecewise function

The derivative of this function is then

These functions are plotted below

We've lost continuity of the derivative at the origin, but otherwise, it's great numerically and it never saturates, and you'll find that learning can happen much faster.

Forward Pass via Matrix Operations

A multilayer perceptron is a sequence of layers of perceptrons. The output of each perceptron in each layer is fed as an input to every perceptron the next layer of perceptrons. This means that we need to define a weight between every pair of perceptrons between two adjacent layers. The image below shows all such weights between two layers with 3 and 4 perceptrons, respectively

At the end of the day, though, an MLP is just a function, and we want to know what it should output given a particular input x fed into the first layer. The key trick to make this easier for multilayer perceptrons is to recast their operation as a sequence of matrix multiplications and element-wise applications of activation functions^[1]. Let's take the following piece of a network below, for instance, where the blue nodes show inputs to the orange neurons:

^[1] In what follows, I'll be mostly following notational conventions from Ch. 6.5 of Deep Learning by Goodfellow, Bengio, and Courville

Let's also assume that the i^th orange node has a bias b_i. Assuming that the activation function for the orange neurons is a function f(u), then we could write the output of the i^th neuron as

In other words, the vector a is a dot product of the weights and the input vector x. But there is a much more elegant way to write transformations for all inputs if we reformulate it as a matrix expression, and this will be much easier to implement in code. In particular, define the following matrices

Then the output of a layer in the network can be defined in two stages

In general, the parameters to map from the output of a layer with N neurons to the input of a layer with M neurons can be described by an M x N weight matrix W and an Mx1 bias column vector b. To propagate information through the whole network, we continually apply this sequence of linear and nonlinear operators in matrix form. We just have to store the matrix W, the vector b, and the nonlinear function f that we're using at each layer. And that's it!

In sum, below is pseudocode that describes how to do a forward pass to transform the input from each layer to the next through the entire network

Backward Pass via Matrix Operations

Click here to view a derivation in the companion module for these notes, which explains how I got the equations in the pseudocode below

We're now ready to express the equations to compute the gradient over all parameters in the network; in other words, we will now figure out the effect of our parameters on the network downstream, so that we know how to change the parameters to improve classification. This will again boil down to some matrix equations that should be fairly painless to implement in code. Though a full derivation of these equations is beyond the scope of this writeup, I will give some intuition by looking at the at a simple network with 3 neurons, each with one input and one output (so that we can avoid doing matrix derivatives for the moment). In particular, let's consider the following function:

In order to do updates, we need derivatives with respect to our weights w₁, w₂, w₃ and our biases b₁, b₂, b₃. Let's use the notation we established in the forward pass to define the following variables

Then we can compute the following derivatives from the outside of the expression inwards, using the chain rule (recall that a partial derivative holds all of the variables fixed as constants except for the one we're taking the derivative with respect to)

A pattern is starting to emerge here. In particular, notice how equation 2 is contained in part of equations 3 and 4 and how equation 4 is contained in part of equations 5 and 6. So this means we'll be able to define some recursive substitutions from layer to layer as we go along, just like we remembered outputs of layers from one to the next as we went along during the forward pass.

From the point of view of the network, the first derivatives we're able to compute are with respect to parameters at the end of the network. We can then use these expressions to substitute in for parameters in layers that precede them. We can avoid recomputing things by remembering some of the products we computed along the way. This leads to an efficient dynamic programming algorithm known as backpropagation. It earns its name since, by contrast to evaluating moving forward layer to layer when evaluating an input, we actually start with the output of the network and compute the gradients backwards layer by layer.

There's one more thing I omitted, which is that we also define a loss function over the output, and we're really looking for the gradient with respect to the loss function. But the above gives a flavor for the patterns that emerge.

Below is the pseudocode for the matrix form of backpropagation for general feedforward networks of any shape. It may look daunting at first, but each bullet point should be a single line of code since we set up things in such an organized way with matrices.

If you look closely, you can match these steps up with the simple 1D example I gave above and see where the substitutions happen from one layer to the next. In a nutshell, what I've done is rearrange some of the results from the derivations I did in the module to be more convenient in code.