chapter 2: how the backpropagation algorithm works

the algorithm was introduced in the 1970s, but its importance wasn't fully appreciated until the famous 1986 paper by David Rumelhart, Geoffrey Hinton, and Ronald Williams.
"workhorse of learning in neural networks"
at the heart of it is an expression that tells us how quickly the cost function changes when we change the weights and biases.

/projects/ml/dl/neural-nets/ch2/
activations.svg — activation diagram of a single neuron in matrix notation

notation

$𝑤 𝑙 𝑗 𝑘$ ⊕ means the weight of the j $𝑡 ℎ$ neuron in layer $𝑙$ to the k $𝑡 ℎ$ neuron in the previous layer
- similarly for $𝑏 𝑙 𝑗$ we say it is the j $𝑡 ℎ$ bias in the l $𝑡 ℎ$ layer
- and $𝑎 𝑙 𝑗$ we say is the j $𝑡 ℎ$ activation in the l $𝑡 ℎ$ layer

obviously the activations of $𝑎 𝑙 𝑗$ are computed with:

𝑎 𝑙 𝑗 = 𝜎 (\sum 𝑘 𝑤 𝑙 𝑗 𝑘 𝑎 𝑙 - 1 𝑘 + 𝑏 𝑙 𝑗)

and says that the activation of any given neuron in layer l = the sigmoid of the weights multiplied by activations for all inputs of the previous layer + bias.

we can then vectorise this:

𝑎 𝑙 = 𝜎 (𝑤 𝑙 𝑎 𝑙 - 1 + 𝑏 𝑙)

it appears that the 'juicy bit' of the sigma above is worth naming: $𝑤 𝑙 𝑎 𝑙 - 1 + 𝑏 𝑙 = 𝑧 𝑙$ .

cost function

as before, we have:

𝐶 = 1 2 𝑛 \sum 𝑥 ‖ 𝑦 (𝑥) - 𝑎 𝐿 (𝑥) ‖ 2

we make two assumptions about this cost function.

the cost function can be written as an average $𝐶 = 1 𝑛 \sum 𝑥 𝐶 𝑥$ over cost functions $𝐶 𝑥$ for individual training examples, $𝑥$ .
the cost function can be written as a function of the outputs from the neural network.

hadamard product

it's just the element-wise multiplication of vectors.

implementing back-prop with this operator tends to be quite fast. (faster than matrix multiplication at times).

four fundamental equations.

$Erroneous nesting of equation structures$

where:

$𝛿 𝑙 𝑗 = 𝜕 𝐶 𝜕 𝑧 𝑙 𝑗$ is the error of neuron j in layer l.
L is the last layer
and then $𝛿 𝐿 𝑗 = 𝜕 𝐶 𝜕 𝑎 𝐿 𝑗 𝜎' (𝑧 𝐿 𝑗) = \nabla 𝑎 𝐶 ⊙ 𝜎' (𝑧 𝐿) = (𝑎 𝐿 - 𝑦) ⊙ 𝜎' (𝑧 𝐿)$

note that saturation means that the neuron has low or high activations (close to 0 or 1) and thus its output is not changing despite varying inputs. i.e. it is not learning.

pseudocode

backprop

Input x: Set the corresponding activation $𝑎 1$ for the input layer
Feedforward: For each $𝑙 = 2, 3, \dots, 𝐿$ compute $𝑧 𝑙 = 𝑤 𝑙 𝑎 𝑙 - 1 + 𝑏 𝑙$ and $𝑎 𝑙 = 𝜎 (𝑧 𝑙)$ .
Output Error $𝛿 𝑙$ : Compute the vector $𝛿 𝐿 = \nabla 𝑎 𝐶 ⊙ 𝜎' (𝑧 𝐿)$
Backpropagate the error: For each $𝑙 = 𝐿 - 1, 𝐿 - 2, \dots, 2$ compute $𝛿 𝑙 = ((𝑤 𝑙 1) 𝑇 𝛿 𝑙 1) ⊙ 𝜎' (𝑧 𝑙)$
Output: The gradient of the cost function is given by $𝜕 𝐶 𝜕 𝑤 𝑙 𝑗 𝑘 = 𝑎 𝑙 - 1 𝑘 𝛿 𝑙 𝑗$ and $𝜕 𝐶 𝜕 𝑏 𝑙 𝑗 = 𝛿 𝑙 𝑗$ .

sgd

given a minibatch, we step in the direction of steepest descent with the stochastic gradient descent algorithm:

Input minibatch
For each training example x: Set the corresponding input activation \(a^x,1, and perform the following steps:
1. Feedforward: For each $𝑙 = 2, 3, . . ., 𝐿$ compute $𝑧 𝑥, 𝑙 = 𝑤 𝑙 𝑎 𝑥, 𝑙 - 1 + 𝑏 𝑙$ and $𝑎 𝑥, 𝑙 = 𝜎 (𝑧 𝑥, 𝑙)$
2. Output Error $𝛿 𝑥, 𝐿$ : Compute the vector $𝛿 𝑥, 𝐿 = \nabla 𝑎 𝐶 𝑥 ⊙ 𝜎' (𝑧 𝑥, 𝐿)$ .
3. Backpropagate the Error: For each $𝑙 = 𝐿 - 1, 𝐿 - 2, . . ., 2$ compute $𝛿 𝑥, 𝐿 = ((𝑤 𝑙 + 1) 𝑇 𝛿 𝑥, 𝑙 + 1) ⊙ 𝜎' (𝑧 𝑥, 𝐿)$ .
Gradient descent: For each $𝑙 = 𝐿, 𝐿 - 1, . . ., 2$ update the weights according to the rule $𝑤 𝑙 \to 𝑤 𝑙 - 𝜂 𝑚 \sum 𝑥 𝛿 𝑥, 𝑙 (𝑎 𝑥, 𝑙 - 1) 𝑇$ , and the biases according to the rule $𝑏 𝑙 \to 𝑏 𝑙 - 𝜂 𝑚 \sum 𝑥 𝛿 𝑥, 𝑙$ .

speed of backprop

the total cost of backpropagation is roughly the same as making just two forward passes through the network.
speedup was first appreciated in 1986, and greatly expanded the range of problems that neural networks could solve.
as such it is possible to use backprop to train deep neural nets.