CSE 30124 · Introduction to Artificial Intelligence William Theisen · University of Notre Dame
Backpropagation01
The XOR Problem
What if instead of asking win or loss, we wanted to decide whether a game was close or not (within 8 points)
Asking if a game was close or not results in data that is very similar to the XOR problem we saw with perceptrons, where our data is not linearly separable
Backpropagation02
Neural Networks: Diagram
Combining our three artificial neurons gives us a simple FFN The organization of neurons in a neural network is called itsarchitecture.
There are a number of different conventions for writing the linear transformation as used in a linear_layer. I use a slightly non-standard one that I believe maps better to PyTorch and the diagrams I show in class.
Convention
Equation
Where you'll see it
Bias folded in
Z = Xω (X gets a column of 1s)
Linear regression, perceptrons and SVMs
Inputs × outputs
Z = Xω + b
Keras/TensorFlow, many textbooks
Outputs × inputs
Z = XωT + b
PyTorchnn.Linear and this course
PyTorch stores one row per neuron so it reads like the math: XωT + b
Backpropagation · Review09
Improving the Weights
Linear Regressions and OLS
Due to the simplicity of linear regression, we could use a closed-form solution (OLS) to directly find the optimal set of weights.
This is due to the loss function (SSE) being perfectly convex
Backpropagation · Gradient Descent10
Gradient Descent
Gradient Descent is an optimization method that iteratively tries to find a set of values (weights) that minimize the loss (cost) function
A gradient is the slope of a curve at a given point in a specified direction
Backpropagation · Gradient Descent11
Multivariate Gradient Descent
In the case of a multivariate function, the gradient is a vector of partial derivatives (one per variable)
Backpropagation is a technique in deep learning to compute the gradient of the loss with respect to every weight for a network. Using the chain rule allows us to implement Gradient Descent for multi-layer models
Backpropagation · Backpropagation18
Python Backprop by Hand - Linear Layer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import torch
classLinearLayer:
def__init__(self, n_in, n_out):
self.W = torch.randn(n_out, n_in) * (2/n_in)**0.5
self.b = torch.zeros(n_out)
defforward(self, X):
self.X = X# keep for backward
returnX @ self.W.T + self.b
defbackward(self, dY):
self.dW = dY.T @ self.X# dL/dW
self.db = dY.sum(dim=0) # dL/db
return dY @ self.W # dL/dX, sent back
defupdate(self, lr):
self.W -= lr * self.dW
self.b -= lr * self.db
Backpropagation · Backpropagation19
Python Backprop by Hand - Sigmoid and ReLU
1
2
3
4
5
6
7
8
9
10
classSigmoid:
defforward(self, Z):
self.A = 1 / (1 + torch.exp(-Z)) # saved
return self.A
defbackward(self, dA):
return dA * self.A * (1 - self.A) # dL/dZ
defupdate(self, lr):
pass# no weights to learn
1
2
3
4
5
6
7
8
9
10
classReLU:
defforward(self, Z):
self.Z = Z # saved
return Z.clamp(min=0)
defbackward(self, dA):
return dA * (self.Z > 0).float() # dL/dZ
defupdate(self, lr):
pass# no weights to learn
Backpropagation · Backpropagation20
Python Backprop by Hand - Neural Network
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classNetwork:
def__init__(self, layers):
self.layers = layers
defforward(self, X):
for layer in self.layers:
X = layer.forward(X)
returnX# logits
defbackward(self, y_hat, y):
grad = y_hat - y# dL/dy_hat (hard-coded here)
for layer inreversed(self.layers): # chain rule
grad = layer.backward(grad) # back to front
defupdate(self, lr):
for layer in self.layers:
layer.update(lr)
Our network class is really just more of a wrapper than anything else, most of the work is done in the layer classes
print('y_hat at epoch 0:', y_hat.flatten(), 'loss:', bce(y_hat, y))
deftrain(model, X, lr=0.001, epochs=1000):
for epoch inrange(epochs):
y_hat = torch.sigmoid(model.forward(X))
model.backward(y_hat, y)
model.update(lr)
return torch.sigmoid(model.forward(X))
y_hat_trained = train(model, X)
print('y_hat at epoch 1000:', y_hat_trained.flatten(), 'loss:', bce(y_hat_trained, y))
Output
y_hat at epoch 0:tensor([0.5038, 0.5367, 0.4577, 0.5866]) loss:tensor(0.7008)
y_hat at epoch 1000:tensor([0.5537, 0.5523, 0.3362, 0.5538]) loss:tensor(0.6004)
Backpropagation · Backpropagation22
Some Issues with Backprop and Activation Functions
There are some issues that appear when you start using backprop, depending on the activation functions you use.
Saturated Sigmoids:
When a neuron's Z is far from 0, the sigmoidflattens out at 0 or 1, so its local derivative is effectively 0 and almost no gradient gets back through it. The neuron is saturated.
Dying ReLUs:
A ReLU's local derivative is 0 for z < 0, so a neuron that's negative on every input passes no gradient back and never updates again. The neuron is dead.
Backpropagation · Issues with Backprop23
Saturated Sigmoids
Not dissimilar to the issues with the step function, if we are too far outside of the curve of the sigmoid, we get effectively no useful gradient information from it.
Purple dots: this section's network's 8 values of Z1 (4 games × 2 neurons) on raw scores, most of them far out on the flat top.
Backpropagation · Issues with Backprop24
Saturated Neurons: Demo
1
2
3
4
5
6
7
8
9
10
torch.manual_seed(11) # ensure our random init is always the same
Same 2 → 2 → 1 shape as last class (seed 11, α = 0.5), and we keep it for the rest of the section. On raw scores the hidden layer is pinned at 1, so three of the games look identical to the output layer and almost no gradient reaches ω1.
Backpropagation · Issues with Backprop25
Dying ReLUs
Similarly to the edges of a sigmoid, a ReLU gives no useful gradient information if the Z value is less than 0.
Hollow dots: the same 8 values of Z1 at the start, nearly all on the ramp. One gradient step later, all 8 are in the dead zone.
Backpropagation · Issues with Backprop26
Dying ReLUs: Demo
1
2
3
4
5
6
7
8
9
10
11
12
13
torch.manual_seed(11) # ensure our random init is always the same
A1:tensor([[0., 0.],
[0., 0.],
[0., 0.],
[0., 0.]])
dead neurons:2 of 2y_hat:tensor([0.5000, 0.5000, 0.5000, 0.5000]) loss:tensor(0.6931)
Same network, same starting weights, only the activation changed. Both neurons start alive, but the first step, with gradients up to 38 from the raw scores, pushes every z below 0 and kills both. After that every gradient is exactly 0.
Backpropagation · Issues with Backprop27
Fixing Both: Standardize the Inputs
Standardized inputs sit on both sides of 0, so every z starts near 0: on the steep part of the sigmoid, and positive for some games, negative for others in each ReLU neuron.
Note: You can assume softmax and cross entropy loss are used after the final layer, the two yielding a combined derivative of: ŷ − y
Backpropagation · Issues with Backprop30
Backprop Exercise (old final exam question)
ℒ =
\frac{\partial ℒ}{\partial b_1} =
\frac{\partial ℒ}{\partial b_1} =
Backpropagation · Issues with Backprop31
The MNIST Dataset
MNIST (LeCun and others, 1998) is the classic first dataset for neural networks: 70,000 handwritten digits (60,000 to train, 10,000 to test), each a 28 × 28 grayscale image. Flattened, that's the 784 inputs of the exam network we just did.
EMNIST (Cohen and others, 2017) adds letters in the same format. Its balanced split has 47 classes: 10 digits, 26 capitals and the 11 lowercase letters that don't look like their capitals.
In Homework 06 and 07 we train on 9,400 of these from the police archive, then point the network at the cut-out letters in Professor Dingler's note.
Backpropagation · Issues with Backprop32
Modern Momentum: ADAM
Plain gradient descent gives every weight the same step sizeα. The exam network has 79,510 weights and biases for MNIST, so weights with big, noisy gradients overshoot while weights with tiny gradients barely move. Adam (Adaptive Moment Estimation, Kingma and Ba, 2014) is the optimizer I see most today, and it fixes the step with two running averages:
m \leftarrow \beta_1\, m + (1 - \beta_1)\, \frac{\partial ℒ}{\partial \omega}v \leftarrow \beta_2\, v + (1 - \beta_2) \bp{\frac{\partial ℒ}{\partial \omega}}^2\omega \leftarrow \omega - \alpha\, \frac{m}{\sqrt{v} + \epsilon}
In PyTorch it's one line, torch.optim.Adam(model.parameters(), lr=0.001), the optimizer Homework 07'sCNN trains with.
NOTE: The defaults are β1 = 0.9, β2 = 0.999, and Adam also corrects m and v for starting at 0.
Backpropagation · Issues with Backprop33
ADAM on MNIST
Kingma and Ba trained a 784 → 1000 → 1000 → 10ReLU network with dropout on MNIST, the same kind of network as the exam question, just wider. Adam falls fastest and ends lowest.