Recitation 3: Multiclass, MLP, Backpropagation

​

Aviv Slobodkin

​

Partially based on prof. Yoav Goldberg’s slides

And on the slides of Yossi Adi and Felix Kreuk, CS Machine Learning course and the resources [1], [2], [3]

​

​

Softmax

• A vector with a score per class
• The scores sum to 1 (a probability distribution)

Dog Cat Watermelon toy

​

0.6 0.2 0.05 0.15

Derivative of softmax

Goal:

A derivative of a quotient:

First, assume i = j

Now, assume i ≠ j

In summary:

Gradient descent for multiclass logistic regression

Logistic regression: gradient calculation

We have one example (x_i, y_i) and calculate gradient with respect to row k in W

Logistic regression: gradient calculation

Beyond linear classifiers

Reminder: Chain Rule

Visualization

Backpropagation

​

We will calculate parameter updates for the following MLP model:

Backpropagation

​

We start by calculating ∂l/∂W₂. This is easy! Just ignore the rest of the network.

We will use the chain rule to calculate the gradient ∂l/∂W₁. We will start by calculating ∂l/∂h₁

Now that we have ∂l/∂h₁, we will continue by calculating ∂h₁[p]/∂zi[j]. What is the dimensionality of the gradient ∂h₁/∂z?

Now that we have both ∂l/∂h₁[p] and ∂h₁[p]/∂zi[j] we can calculate ∂l/∂z₁[j] with the chain rule:

With ∂l/∂z₁[j] we can finally calculate ∂l/∂w₁[j] (!!!)

Completely analogous to the formula for ∂l/∂w₂[j] !

What if we had another layer before x_t?

Conclusions

• We know how to calculate the error signal for the last layer:
• δ_out = Ŷ - Y_t (the “base case” of the dynamic programming)
• For any other layer i, let W_i be the layer’s weight matrix, its activation function g_i, its activation vector h_i, and let the input to the activation be z_i:
• z_i = W_i * h_i-1
• h_i = g(z_i)

*

Backpropagation Algorithm for multiclass MLP

1. Perform a forward pass on the network with input x_t
1. Store: Ŷ; z_i, h_i for each layer i = 1...n
2. Initialize δ_n = δ_out ← Ŷ - Y_t
3. Update W_n according to logistic regression
4. For each layer i = n-1 … 1 (backwards) do:
• δ_i ← (W_i+1δ_i+1) ∘g_i’(z_i) > error signal = z_i
• W_i ← h_i-1^Tδ_i > gradient calculation
• W_i ← W_i -η W_i > update layer’s parameters

In practice: automatic differentiation

The computation graph

In practice: computation graphs

Forward pass

Backward pass