THE CREDIT ASSIGNMENT PROBLEM, which is the obstacle every previous topic ran into: WE KNOW THE ERROR AT THE OUTPUT. WE DO NOT KNOW WHAT A HIDDEN UNIT SHOULD HAVE OUTPUT, SO WE HAVE NO TARGET FOR IT AND THEREFORE NO ERROR — SO HOW DO WE UPDATE ITS WEIGHTS? This is why the perceptron rule and the delta rule train only one layer, and why Madaline needed a fixed output gate and a minimum-disturbance heuristic. The obstacle is not conceptual difficulty; it is that the STEP FUNCTION HAS ZERO DERIVATIVE EVERYWHERE (and no derivative at the threshold), so there is no gradient to propagate. THE TWO INGREDIENTS OF THE SOLUTION: 1. REPLACE THE STEP WITH A DIFFERENTIABLE ACTIVATION — sigmoid, tanh, ReLU. Now every quantity in the network is a differentiable function of every weight. 2. APPLY THE CHAIN RULE. The error is a composition of functions, so ∂E/∂w for a deep weight is a product of derivatives along the path from that weight to the error. THE INSIGHT THAT MAKES IT EFFICIENT — and this is the part usually skipped: A naive approach would compute ∂E/∂w separately for each weight, re-traversing the network every time: O(W²) work for W weights. BACKPROPAGATION COMPUTES A QUANTITY δ AT EACH UNIT — the error signal — AND REUSES IT FOR EVERY WEIGHT FEEDING THAT UNIT. Because a unit's δ depends only on the δ values of the units it feeds, computing them from the output backwards gives EVERY GRADIENT IN THE NETWORK IN ONE BACKWARD SWEEP, at O(W) cost — the same order as the forward pass. THAT REUSE IS THE ALGORITHM. Everything else is the chain rule. IT IS AN INSTANCE OF REVERSE-MODE AUTOMATIC DIFFERENTIATION, a general technique for differentiating any computation graph. The neural network is just the most famous graph it is applied to. A NOTE OF HISTORY, because it is a favourite exam aside: Werbos derived it in a 1974 PhD thesis; Rumelhart, Hinton and Williams published the paper that made it famous in 1986. THE TWELVE-YEAR GAP is the second half of the AI winter — the answer to Minsky and Papert existed and the field did not know it.

SETUP — a network with input x, hidden layer h, output y. hidden: net_j = Σᵢ vⱼᵢxᵢ + bⱼ , hⱼ = f(net_j) output: net_k = Σⱼ wₖⱼhⱼ + cₖ , yₖ = f(net_k) error: E = ½ Σₖ (tₖ − yₖ)² THE SIGMOID AND ITS DERIVATIVE, which is why sigmoid is chosen: f(z) = 1/(1 + e⁻ᶻ) f′(z) = f(z)(1 − f(z)) = y(1 − y) THE DERIVATIVE IS EXPRESSIBLE IN TERMS OF THE OUTPUT ITSELF, so it costs one multiplication and no re-evaluation. That is a substantial saving repeated for every unit on every example. STEP 1 — THE OUTPUT LAYER. Apply the chain rule to wₖⱼ: ∂E/∂wₖⱼ = (∂E/∂yₖ)(∂yₖ/∂net_k)(∂net_k/∂wₖⱼ) the three factors being ∂E/∂yₖ = −(tₖ − yₖ) = (yₖ − tₖ) ∂yₖ/∂net_k = f′(net_k) = yₖ(1 − yₖ) ∂net_k/∂wₖⱼ = hⱼ DEFINE THE OUTPUT ERROR SIGNAL: δₖ = (yₖ − tₖ) · yₖ(1 − yₖ) so that ∂E/∂wₖⱼ = δₖ · hⱼ and Δwₖⱼ = −η δₖ hⱼ COMPARE THE DELTA RULE from two topics ago: Δw = η(t − y)x. THE ONLY DIFFERENCE IS THE EXTRA FACTOR f′(net) — the slope of the activation. Backpropagation's output layer IS the delta rule with the activation's derivative attached, which is why the delta rule was the necessary preparation. STEP 2 — THE HIDDEN LAYER, where the actual work is. There is no target for hⱼ, so we cannot write (t − h). Instead we ask how E changes as hⱼ changes, and hⱼ affects E THROUGH EVERY OUTPUT UNIT IT FEEDS — so the contributions SUM: ∂E/∂hⱼ = Σₖ (∂E/∂net_k)(∂net_k/∂hⱼ) = Σₖ δₖ wₖⱼ THAT SUM IS THE WHOLE IDEA: THE HIDDEN UNIT'S ERROR IS THE ERROR OF THE UNITS IT FEEDS, WEIGHTED BY HOW STRONGLY IT FEEDS THEM. A unit that contributed a lot to a wrong answer, through a large weight, receives a large share of the blame. That is credit assignment, solved. Then, exactly as before, δⱼ = (Σₖ δₖ wₖⱼ) · f′(net_j) = (Σₖ δₖ wₖⱼ) · hⱼ(1 − hⱼ) ∂E/∂vⱼᵢ = δⱼ · xᵢ and Δvⱼᵢ = −η δⱼ xᵢ NOTICE THE SYMMETRY, which is what makes the algorithm generalise to any depth: OUTPUT UNIT: δ = (y − t) × f′(net) HIDDEN UNIT: δ = (Σ δ_next w) × f′(net) THE FORM IS IDENTICAL. Only the first factor differs — a direct error at the output, a WEIGHTED SUM OF DOWNSTREAM δ's at a hidden unit. So the same rule applies at every layer, and a network of any depth is trained by repeating it. THE BIAS: treat it as a weight on a constant input of 1, so Δbⱼ = −η δⱼ with no xᵢ factor. This is the most common slip in exam answers.

A 2−2−1 NETWORK, ONE TRAINING EXAMPLE, WORKED TO SIX DECIMALS. Sigmoid units throughout, η = 0.5. inputs x₁ = 0.05, x₂ = 0.10 target t = 0.99 hidden v₁₁ = 0.15 v₁₂ = 0.20 b₁ = 0.35 v₂₁ = 0.25 v₂₂ = 0.30 b₂ = 0.35 output w₁ = 0.40 w₂ = 0.45 c = 0.60 ── FORWARD PASS ──────────────────────────────────────────── net₁ = 0.15(0.05) + 0.20(0.10) + 0.35 = 0.377500 h₁ = 1/(1 + e^−0.3775) = 0.593270 net₂ = 0.25(0.05) + 0.30(0.10) + 0.35 = 0.392500 h₂ = 1/(1 + e^−0.3925) = 0.596884 net_o = 0.40(0.593270) + 0.45(0.596884) + 0.60 = 1.105906 y = 1/(1 + e^−1.105906) = 0.751365 E = ½(0.99 − 0.751365)² = 0.028473 ── BACKWARD PASS ─────────────────────────────────────────── OUTPUT δ: δ_o = (y − t)·y(1 − y) = (0.751365 − 0.99)(0.751365)(0.248635) = −0.044581 OUTPUT GRADIENTS: ∂E/∂w₁ = δ_o·h₁ = −0.044581 × 0.593270 = −0.026448 ∂E/∂w₂ = δ_o·h₂ = −0.044581 × 0.596884 = −0.026610 ∂E/∂c = δ_o = −0.044581 HIDDEN δ — note the weighted sum, here with a single output so the sum has one term: δ₁ = δ_o·w₁·h₁(1 − h₁) = −0.044581 × 0.40 × 0.593270 × 0.406730 = −0.00430294 δ₂ = δ_o·w₂·h₂(1 − h₂) = −0.044581 × 0.45 × 0.596884 × 0.403116 = −0.00482702 HIDDEN GRADIENTS: ∂E/∂v₁₁ = δ₁·x₁ = −0.00430294 × 0.05 = −0.00021515 ∂E/∂v₁₂ = δ₁·x₂ = −0.00430294 × 0.10 = −0.00043029 OBSERVE THE MAGNITUDES: the hidden gradients are roughly a HUNDRED TIMES SMALLER than the output ones. This is the vanishing gradient in miniature, in a network only two layers deep — and it is why the near-input layers of a deep sigmoid network learn so slowly. ── WEIGHT UPDATE, w ← w − η ∂E/∂w ────────────────────────── w₁ ← 0.40 − 0.5(−0.026448) = 0.413224 w₂ ← 0.45 − 0.5(−0.026610) = 0.463305 c ← 0.60 − 0.5(−0.044581) = 0.622290 v₁₁ ← 0.15 − 0.5(−0.00021515) = 0.150108 v₁₂ ← 0.20 − 0.5(−0.00043029) = 0.200215 v₂₁ ← 0.25 − 0.5(−0.00024135) = 0.250121 v₂₂ ← 0.30 − 0.5(−0.00048270) = 0.300241 ── VERIFICATION: re-run the forward pass ─────────────────── y = 0.758500 (was 0.751365 — moved toward t = 0.99) E = 0.026796 (was 0.028473) ERROR REDUCED BY 5.89% IN A SINGLE STEP. Repeating this for thousands of steps is training. NOTHING ELSE HAPPENS.

WEIGHT UPDATE MODES: STOCHASTIC (online) — update after EVERY example. Noisy, which helps escape shallow local minima; fast early progress; cannot be parallelised across examples. BATCH — accumulate gradients over the whole training set, update once per epoch. A true gradient, smooth descent, but slow and memory-hungry. MINI-BATCH — update every 32 / 64 / 128 examples. THE UNIVERSAL CHOICE IN PRACTICE, because it combines a reasonable gradient estimate with GPU-friendly parallelism. MOMENTUM — the standard acceleration: Δw(t) = −η ∂E/∂w + α Δw(t−1) with α ≈ 0.9 Adds a fraction of the previous update, so consistent directions accumulate speed while oscillating ones cancel. IT HELPS MOST IN RAVINES — surfaces steep in one direction and shallow in another, where plain descent zigzags. Momentum damps the zigzag and accelerates along the valley floor. ADAM, the modern default, extends this with per-weight adaptive learning rates. THE PROBLEMS, and what is done about them: 1. LOCAL MINIMA. Gradient descent finds a minimum, not THE minimum. Mitigations: momentum, several random restarts, stochastic noise. THE MODERN VIEW IS MORE INTERESTING: in very high dimensions, true local minima are RARE, because a point is only a minimum if the surface curves upward in ALL of millions of directions. SADDLE POINTS — up in some, down in others — are the real obstacle, and they are escaped by any method with noise or momentum. 2. VANISHING GRADIENTS — THE MOST IMPORTANT PROBLEM. δ for a layer includes one factor of f′ per layer above it. THE SIGMOID'S DERIVATIVE PEAKS AT 0.25 and is smaller everywhere else, so the gradient is multiplied by ≤ 0.25 at every layer: 5 layers: 0.25⁵ ≈ 9.77 × 10⁻⁴ 10 layers: 0.25¹⁰ ≈ 9.54 × 10⁻⁷ 20 layers: 0.25²⁰ ≈ 9.10 × 10⁻¹³ THE EARLY LAYERS RECEIVE ESSENTIALLY NO SIGNAL AND NEVER LEARN. This is precisely why networks stayed shallow until roughly 2010, and why the fixes below launched deep learning: · ReLU, whose derivative is exactly 1 for positive input · careful initialisation (Xavier, He) · batch normalisation · residual/skip connections, which give the gradient a path that bypasses the multiplications entirely THE EXPLODING GRADIENT is the mirror image, with factors > 1; the standard fix is GRADIENT CLIPPING. 3. OVERFITTING. Mitigations: early stopping on a validation set, weight decay (L2), dropout, data augmentation. 4. THE LEARNING RATE. Too large diverges, too small crawls — the trade-off analysed in the learning-rate topic. Schedules and adaptive methods address it. 5. SLOW CONVERGENCE — thousands of epochs is normal. Momentum, adaptive rates, normalised inputs and good initialisation all help. 6. IT IS NOT BIOLOGICALLY PLAUSIBLE. Real neurons have no mechanism for sending an error signal backwards along the axon, and the algorithm requires a unit to know the weights of the connections leaving it — the WEIGHT TRANSPORT PROBLEM. BACKPROPAGATION IS ENGINEERING, NOT NEUROSCIENCE, and the honest position is that it works despite being unlike the brain rather than because it resembles it. THE COMPLETE ALGORITHM, as it should be written in an exam: 1. initialise all weights to small random values 2. repeat until the stopping criterion is met: for each training example (x, t): a. FORWARD PASS: compute hⱼ = f(Σvⱼᵢxᵢ + bⱼ), then yₖ = f(Σwₖⱼhⱼ + cₖ) b. OUTPUT δ: δₖ = (yₖ − tₖ)·f′(net_k) c. HIDDEN δ: δⱼ = (Σₖ δₖwₖⱼ)·f′(net_j) d. UPDATE: wₖⱼ ← wₖⱼ − η δₖ hⱼ vⱼᵢ ← vⱼᵢ − η δⱼ xᵢ biases likewise, with input 1 3. stop on: error below a threshold, validation error rising, or an epoch limit