10_Perceptrons_and_Neural_Networks

Module 9 — Perceptrons, Multilayer Networks and Backpropagation

Sources: Lec 21 — Perceptron Learning Algorithm; Lec 22 — Multilayer Perceptron Learning Algorithm; Lec 23 — Artificial Neural Network and Backpropagation Algorithm. · Prev: Module 8 · Index: 00_INDEX_and_Coverage

Notation

Perceptron: $({\vec{X}}_i,y_i)$, $y_i\in \{-1,+1\}$; augmented vector ${\vec{X}}_i^{\prime }=[1,x_{i1},\dots ,x_{im}{]}^T$; weights $\vec{W}=[w_0,w_1,\dots ,w_m{]}^T$ ($w_0$ = bias). Network: layer index $l=\mathrm{1..}L$; $n_l$ nodes in layer $l$; $y_i^l$ output of node $i$ in layer $l$; $S_j^l$ net input; $w_{ij}^l$ weight from node $i$ of layer $l$ to node $j$ of layer $l+1$.

Python helpers — run once, the checks below reuse them

import numpy as np
np.set_printoptions(precision=4, suppress=True)
X = np.array([[0,0], [0,1], [1,0], [1,1]], float); Xa = np.c_[np.ones(4), X]      # augmented inputs
y_and = np.array([-1, -1, -1, 1]); y_xor = np.array([-1, 1, 1, -1])
 
def perceptron(y, eta=1.0, max_epochs=200):
    """Online perceptron, cyclic order, update when y·f <= 0. Returns (W, #updates, trajectory)."""
    W = np.zeros(3); traj = [W.copy()]
    for _ in range(max_epochs):
        changed = False
        for i in range(4):
            if y[i] * (W @ Xa[i]) <= 0:
                W = W + eta * y[i] * Xa[i]; traj.append(W.copy()); changed = True
        if not changed: break
    return W, len(traj) - 1, traj
 
sigmoid = lambda z: 1 / (1 + np.exp(-z))

---

C49. The Perceptron Model and Learning Rule

Intuition

A single artificial neuron: weigh the inputs, add them, fire "$+1$" if the total is positive, "$-1$" otherwise. Learning = whenever the neuron makes a mistake, nudge the weights so that this very example would be a bit more correct — like a bouncer who adjusts the guest-list rule each time they let in the wrong person.

flowchart LR
    x0["1 (bias)"] -- w0 --> S(("Σ"))
    x1[x₁] -- w1 --> S
    x2[x₂] -- w2 --> S
    S --> A{"sign"}
    A --> O["±1"]

Formal definition

Linear discriminant (21.1): $f({\vec{X}}_i,\vec{W})=w_0+{\sum }_{j=1}^m{w}_j{x}_{ij}={\vec{W}}^T{\vec{X}}_i^{\prime }$. Prediction: $\mathrm{sign}(f)$. A point is correctly classified iff $y_{i}f({\vec{X}}_i,\vec{W})>0$.

Online (incremental) rule: at iteration $k$ pick a training point $(\vec{X}(k),y(k))$ that is misclassified, $y(k){\vec{W}}^T(k){\vec{X}}^{\prime }(k)\le 0$ (we include $=0$, otherwise the all-zero start never moves), and set $\vec{W}(k+1)=\vec{W}(k)+\eta y(k){\vec{X}}^{\prime }(k),\eta >0(\eta =1\text{ in the lecture}).$ Stop when all training points are classified correctly.

Why the update helps (local error correction)

$y\vec{W}(k+1{)}^T{\vec{X}}^{\prime }=y\vec{W}(k{)}^T{\vec{X}}^{\prime }+\eta y^2{\vec{X}}^{\prime T}{\vec{X}}^{\prime }=y\vec{W}(k{)}^T{\vec{X}}^{\prime }+\eta \Vert {\vec{X}}^{\prime }{\Vert }^2$ — the quantity $y{\vec{W}}^T{\vec{X}}^{\prime }$ for this point rises by $\eta \Vert {\vec{X}}^{\prime }{\Vert }^2>0$. (It may spoil other points — Figure 21.2 in the lecture.)

Key insights

• A single-layer perceptron = a linear classifier (hyperplane ${\vec{W}}^T{\vec{X}}^{\prime }=0$).
• Converges only for linearly separable data (C50).
• Starting from $\vec{W}(0)=\vec{0}$, $\eta$ merely scales $\vec{W}$ (Example 4).

Worked examples

Example 1 — Very Easy · Classify with given weights

• Problem: $\vec{W}=(-1,2,1)$ ($w_0=-1$). Classify $\vec{X}=(1,0)$ and $\vec{X}=(0,0.5)$.
• Asked: Labels.
• Concept: $\mathrm{sign}({\vec{W}}^T{\vec{X}}^{\prime })$.
• Approach: Augment, dot.
• Solution: $(1,0)$: $-1+2=1>0\Rightarrow +1$. $(0,0.5)$: $-1+0.5=-0.5<0\Rightarrow -1$.
• Final answer: $+1$ and $-1$.

Key lesson

The bias is the weight on the constant $1$.

Example 2 — Easy · One update fixes the point

• Problem: $\vec{W}=(0,1,1)$, misclassified point $\vec{X}=(0,1)$ with $y=-1$. Apply one update ($\eta =1$) and check the point.
• Asked: New $\vec{W}$ and new margin.
• Concept: Update rule.
• Approach: $\vec{W}+y{\vec{X}}^{\prime }$.
• Solution: ${\vec{X}}^{\prime }=(1,0,1)$. Before: $f=1$, $yf=-1<0$ ✗. New $\vec{W}=(0,1,1)-(1,0,1)=(-1,1,0)$. Now $f=-1$, $yf=+1>0$ ✓ (increase $=\Vert {\vec{X}}^{\prime }{\Vert }^2=2$).
• Final answer: $\vec{W}=(-1,1,0)$.

Key lesson

One update raises that point’s $yf$ by exactly $\eta \Vert {\vec{X}}^{\prime }{\Vert }^2$.

Example 3 — Moderate · Learn AND

• Problem: Learn AND with labels $-1,-1,-1,+1$ for $(0,0),(0,1),(1,0),(1,1)$ in that cyclic order, $\vec{W}(0)=\vec{0}$, $\eta =1$. Run to convergence.
• Asked: Final $\vec{W}$ and number of updates.
• Concept: Online perceptron.
• Approach: Cycle through the data; update on every mistake ($yf\le 0$).
• Solution: Updates in order (epoch, point → new $\vec{W}$):

#	epoch	point	$\vec{W}$ after
1	1	(0,0)	(−1, 0, 0)
2	1	(1,1)	(0, 1, 1)
3	2	(0,0)	(−1, 1, 1)
4	2	(0,1)	(−2, 1, 0)
5	2	(1,1)	(−1, 2, 1)
6	3	(0,1)	(−2, 2, 0)
7	3	(1,0)	(−3, 1, 0)
8	3	(1,1)	(−2, 2, 1)
9	4	(1,0)	(−3, 1, 1)
10	4	(1,1)	(−2, 2, 2)
11	5	(0,1)	(−3, 2, 1)
12	5	(1,1)	(−2, 3, 2)
13	6	(0,1)	(−3, 3, 1)
14	6	(1,0)	(−4, 2, 1)
15	6	(1,1)	(−3, 3, 2)
16	7	(1,0)	(−4, 2, 2)
17	7	(1,1)	(−3, 3, 3)
18	8	(0,1)	(−4, 3, 2)

Epoch 9 is clean: $f=-4,-2,-1,+1$ ⇒ all correct.

• Final answer: $\vec{W}=(-4,3,2)$ after $18$ updates; boundary $3x_1+2x_2=4$.

Python check

W, n, traj = perceptron(y_and); print(W, n)               # [-4. 3. 2.]  18

Key lesson

The perceptron finds a separator, not the best one (the max-margin one is $(-3,2,2)$).

Example 4 — Hard · Step size does not matter

• Problem: Re-run Example 3 with $\eta =0.5$ and $\eta =3$. What happens?
• Asked: Final weights.
• Concept: Scale invariance.
• Approach: Track the trajectories.
• Solution: Claim: with $\vec{W}(0)=\vec{0}$, the trajectory for step size $\eta$ is $\eta$ times the trajectory for $\eta =1$. Induction: if ${\vec{W}}_{\eta }(k)=\eta {\vec{W}}_1(k)$, then the sign of $y{\vec{W}}_{\eta }^T{\vec{X}}^{\prime }=\eta y{\vec{W}}_1^T{\vec{X}}^{\prime }$ equals that of $y{\vec{W}}_1^T{\vec{X}}^{\prime }$ ⇒ the same points are mistakes in the same order, and ${\vec{W}}_{\eta }(k+1)=\eta {\vec{W}}_1(k)+\eta y{\vec{X}}^{\prime }=\eta {\vec{W}}_1(k+1)$ ✓. Hence $\eta =0.5$ ⇒ $(-2,1.5,1)$; $\eta =3$ ⇒ $(-12,9,6)$, each after $18$ updates.
• Final answer: $\eta \times (-4,3,2)$; identical classification.

Python check

print(perceptron(y_and, .5)[:2], perceptron(y_and, 3)[:2])   # ([-2. 1.5 1.], 18)  ([-12. 9. 6.], 18)

Key lesson

Only the direction of $\vec{W}$ matters, so with a zero start $\eta$ is irrelevant.

Example 5 — Very Hard · The XOR cycle

• Problem: Run the same procedure on XOR ($y=-1,+1,+1,-1$ for $(0,0),(0,1),(1,0),(1,1)$). Describe the behaviour.
• Asked: Trajectory.
• Concept: Non-separable data.
• Approach: Simulate.
• Solution: $(0,0)$: $f=0$ ⇒ $(-1,0,0)$. $(0,1)$: $f=-1$, $y=+1$ ⇒ $(0,0,1)$. $(1,0)$: $f=0$, $y=+1$ ⇒ $(1,1,1)$. $(1,1)$: $f=3$, $y=-1$ ⇒ $(0,0,0)$. Back at $\vec{W}=\vec{0}$ after 4 updates — the sequence repeats forever with period $4$. The four updates sum to $(-1)(1,0,0)+(1,0,1)+(1,1,0)-(1,1,1)=\vec{0}$.
• Final answer: The weights cycle $\vec{0}\to (-1,0,0)\to (0,0,1)\to (1,1,1)\to \vec{0}$; no convergence.

Python check

W = np.zeros(3)
for k in range(8):
    i = k % 4
    if y_xor[i] * (W @ Xa[i]) <= 0: W = W + y_xor[i] * Xa[i]
    print(k, W)                                           # returns to [0 0 0] every 4 steps

Key lesson

On non-separable data the perceptron never stops; a cycle of weights is the typical symptom.

Common mistakes

• Treating $yf=0$ as correct (the all-zero start would never learn).
• Forgetting to augment with the constant $1$.

Exam traps

• Labels are $\pm 1$ here (not $0/1$).
• The update uses the misclassified point only (online version).

Connections: Logistic regression (C27), SVM (C30), convergence (C50), batch version (C51), MLP (C52).

Mastery checklist

• Apply the update rule.
• Show the rule helps the point it updates on.
• Recognise non-convergence.

---

C50. Convergence Theorem for the Perceptron

Intuition

If a separator exists, the perceptron makes only a finite number of mistakes. Two competing facts: the weight vector keeps aligning with a true separator (alignment grows linearly in the number of mistakes $k$), but its length grows only like $\sqrt{k}$. A vector can’t align faster than it can grow ⇒ $k$ is bounded.

Theorem (Rosenblatt) and proof

Assume separability: $\exists {\vec{W}}^{\ast }$ and $\gamma >0$ with $y_i{\vec{W}}^{\ast T}{\vec{X}}_i^{\prime }\ge \gamma$ for all $i$ (take $\gamma ={\min }_i{y}_i{\vec{W}}^{\ast T}{\vec{X}}_i^{\prime }$). Let $R^2={\max }_i\Vert {\vec{X}}_i^{\prime }{\Vert }^2$ (the lecture’s $M$) and $\vec{W}(0)=\vec{0}$. If $k$ updates have occurred then $\boxed{k\le \frac{R^2\Vert {\vec{W}}^{\ast }{\Vert }^2}{{\gamma }^2}.}$ Proof. (a) Length bound. At a mistake $y{\vec{W}}^T{\vec{X}}^{\prime }\le 0$, so $\Vert \vec{W}(k+1){\Vert }^2=\Vert \vec{W}(k){\Vert }^2+2y\vec{W}(k{)}^T{\vec{X}}^{\prime }+\Vert {\vec{X}}^{\prime }{\Vert }^2\le \Vert \vec{W}(k){\Vert }^2+R^2.$ By induction $\Vert \vec{W}(k){\Vert }^2\le k{R}^2$ (lecture 21.5–21.8). (b) Alignment. $\vec{W}(k)={\sum }_{j<k}y(j){\vec{X}}^{\prime }(j)$ (lecture 21.10), so $\vec{W}(k{)}^T{\vec{W}}^{\ast }={\sum }_{j<k}y(j){\vec{W}}^{\ast T}{\vec{X}}^{\prime }(j)\ge k\gamma$. (c) Cauchy–Schwarz. $(k\gamma {)}^2\le (\vec{W}(k{)}^T{\vec{W}}^{\ast }{)}^2\le \Vert \vec{W}(k){\Vert }^2\Vert {\vec{W}}^{\ast }{\Vert }^2\le k{R}^2\Vert {\vec{W}}^{\ast }{\Vert }^2$ ⇒ $k\le R^2\Vert {\vec{W}}^{\ast }{\Vert }^2/{\gamma }^2$. ∎

Salient points (lecture) and clarifications

• If the data are not separable the algorithm does not converge.
• The lecture says “no bound on the number of iterations can be found”: the bound above exists, but it depends on the unknown margin of the data, so it cannot be computed in advance without knowing a separator.
• Any positive step size works (C49 Example 4).
• Online perceptron = one sample at a time; classification: $\mathrm{sign}({\vec{W}}^T{\vec{X}}_0^{\prime })$.

Worked examples

Example 1 — Very Easy · The radius R

• Problem: AND data (augmented ${\vec{X}}^{\prime }$). Compute $R^2$.
• Asked: $R^2$.
• Concept: Radius.
• Approach: $\Vert {\vec{X}}^{\prime }{\Vert }^2=1+x_1^2+x_2^2$.
• Solution: $(0,0)\to 1$; $(0,1)\to 2$; $(1,0)\to 2$; $(1,1)\to 3$.
• Final answer: $R^2=3$.

Key lesson

Include the constant $1$ in the norm.

Example 2 — Easy · The bound for AND

• Problem: Use ${\vec{W}}^{\ast }=(-3,2,2)$ for AND. Find $\gamma$, $\Vert {\vec{W}}^{\ast }{\Vert }^2$, and the bound on $k$.
• Asked: Bound.
• Concept: Theorem.
• Approach: Compute $y{\vec{W}}^{\ast T}{\vec{X}}^{\prime }$ for the four points.
• Solution: $y{\vec{W}}^{\ast T}{\vec{X}}^{\prime }=(3,1,1,1)$ ⇒ $\gamma =1$. $\Vert {\vec{W}}^{\ast }{\Vert }^2=9+4+4=17$. Bound $=\frac{3\cdot 17}{1}=51$.
• Final answer: $k\le 51$ (the run of C49 Ex. 3 used $18$).

Python check

Ws = np.array([-3, 2, 2.]); gam = (y_and * (Xa @ Ws)).min(); R2 = (Xa**2).sum(1).max()
print(gam, R2, R2 * (Ws @ Ws) / gam**2)                   # 1.0  3.0  51.0

Key lesson

The bound is conservative (51 vs 18 actual).

Example 3 — Moderate · Check the proof ingredients

• Problem: Verify inequalities (a) and (b) numerically along the first three updates of the AND run: $\vec{W}(1)=(-1,0,0)$, $\vec{W}(2)=(0,1,1)$, $\vec{W}(3)=(-1,1,1)$.
• Asked: Check.
• Concept: Proof ingredients.
• Approach: Compute norms and dot products with ${\vec{W}}^{\ast }=(-3,2,2)$.
• Solution: $\Vert \vec{W}(k){\Vert }^2=1,2,3\le k{R}^2=3,6,9$ ✓. Alignment: $\vec{W}(k{)}^T{\vec{W}}^{\ast }=3,4,7\ge k\gamma =1,2,3$ ✓.
• Final answer: All inequalities hold.

Python check

for k, Wk in enumerate(perceptron(y_and)[2][1:4], 1):
    print(k, Wk @ Wk, k * R2, Wk @ Ws, k * gam)           # 1 1 3 3 1 | 2 2 6 4 2 | 3 3 9 7 3

Key lesson

$\vec{W}(k{)}^T{\vec{W}}^{\ast }$ grows at least linearly; $\Vert \vec{W}(k){\Vert }^2$ at most linearly.

Example 4 — Hard · A scale-free bound

• Problem: Express the bound with the geometric margin ${\gamma }_g=\gamma /\Vert {\vec{W}}^{\ast }\Vert$ and show invariance to rescaling both ${\vec{W}}^{\ast }$ and the data.
• Asked: $(R/{\gamma }_g{)}^2$ and invariance.
• Concept: Scale invariance of the bound.
• Approach: Substitute.
• Solution: $k\le \frac{R^2\Vert {\vec{W}}^{\ast }{\Vert }^2}{{\gamma }^2}=(\frac{R}{{\gamma }_g}{)}^2$. Replace ${\vec{W}}^{\ast }\to c{\vec{W}}^{\ast }$: $\gamma \to c\gamma$, $\Vert {\vec{W}}^{\ast }\Vert \to c\Vert {\vec{W}}^{\ast }\Vert$ ⇒ ratio unchanged. Scale the data ${\vec{X}}^{\prime }\to s{\vec{X}}^{\prime }$: $R\to sR$, ${\gamma }_g\to s{\gamma }_g$ ⇒ unchanged. AND: ${\gamma }_g=\frac{1}{\sqrt{17}}=0.2425$; $(R/{\gamma }_g{)}^2=3\cdot 17=51$ ✓.
• Final answer: $k\le (R/{\gamma }_g{)}^2$, $=51$ for AND.

Key lesson

The mistake bound depends only on the relative margin ${\gamma }_g/R$ — the same quantity SVM maximises (C30).

Example 5 — Very Hard · XOR has no separator

• Problem: Show that for XOR no ${\vec{W}}^{\ast }$ exists, so the proof cannot apply, and explain how the cycle of C49 Ex. 5 is consistent with the proof’s failure.
• Asked: Non-existence and relation to the cycle.
• Concept: Separability is essential.
• Approach: Contradictory inequalities.
• Solution: Needs $y{\vec{W}}^T{\vec{X}}^{\prime }>0$ for all four: $(0,0)$, $y=-1$: $w_0<0$. $(0,1)$, $y=+1$: $w_0+w_2>0$. $(1,0)$, $y=+1$: $w_0+w_1>0$. $(1,1)$, $y=-1$: $w_0+w_1+w_2<0$. Adding the middle two: $2w_0+w_1+w_2>0$; with $w_0<0$ this gives $w_0+w_1+w_2>-w_0>0$, contradicting the fourth. So no separator ⇒ $\gamma >0$ cannot exist. In the proof, step (b) fails: $\vec{W}(k{)}^T{\vec{W}}^{\ast }\ge k\gamma$ needs a ${\vec{W}}^{\ast }$; without it nothing forces $\Vert \vec{W}(k)\Vert$ to grow, and indeed the weights return to $\vec{0}$ (the four updates sum to $\vec{0}$).
• Final answer: XOR is not separable; the weight vector cycles.

Key lesson

The linear-growth-vs-square-root-growth squeeze needs a true separator.

Common mistakes

• Using $R^2$ without the bias coordinate.
• Believing the bound is the actual number of updates.

Exam traps

• Convergence ⇒ separable (the theorem is “if separable then finite updates”).
• The bound involves $R$ and the margin only — not the dimension or the number of points.

Connections: C30 (margin), C49, C51.

Mastery checklist

• State and prove the theorem.
• Compute $R,\gamma ,\Vert {\vec{W}}^{\ast }\Vert$ and the bound.
• Explain why XOR fails.

---

C51. Batch Perceptron and the Gradient-Descent View

Intuition

Instead of reacting to one mistake at a time, sum the corrections from all currently misclassified points and apply them together — this is gradient descent on a cost that adds up how badly points are misclassified.

Formal definition

Misclassified index set at iteration $k$: $S_k=\{j:y_j\vec{W}(k{)}^T{\vec{X}}_j^{\prime }\le 0\}$. Cost (“figure of merit”): $J(\vec{W})=-{\sum }_{j\in S_k}{y}_j{\vec{W}}^T{\vec{X}}_j^{\prime }(\ge 0).$ Gradient (for the current $S_k$): ${\nabla }_{\vec{W}}J=-{\sum }_{j\in S_k}{y}_j{\vec{X}}_j^{\prime }$. Gradient descent $\vec{W}(k+1)=\vec{W}(k)-\eta \nabla J$ gives $\vec{W}(k+1)=\vec{W}(k)+\eta {\sum }_{j\in S_k}{y}_j{\vec{X}}_j^{\prime },\eta >0$ (the lecture’s 21.15 writes "$+\eta \partial J/\partial \vec{W}$", but with the stated result the sign is as above). If ${\vec{W}}_0$ separates the data then $S=\varnothing$ and $J=0$. Memory cost of the batch version is higher (all misclassified points are used per step).

Key insights

• Online = stochastic gradient descent; batch = full gradient.
• $J$ counts violation amount, not just the number of errors.
• With the "$\le 0$" convention $J$ can be $0$ while $S_k\ne \varnothing$ (points exactly on the boundary).

Worked examples (AND data: $(0,0)-$, $(0,1)-$, $(1,0)-$, $(1,1)+$)

Example 1 — Very Easy · S and J

• Problem: For $\vec{W}=(0,1,1)$ find $S$ and $J$.
• Asked: $S,J$.
• Concept: Definition of $J$.
• Approach: Compute $yf$.
• Solution: $f=(0,1,1,2)$; $yf=(0,-1,-1,2)$. $S=\{(0,0),(0,1),(1,0)\}$ ($yf\le 0$). $J=-(0-1-1)=2$.
• Final answer: $|S|=3$, $J=2$.

Key lesson

$J$ sums the (negative) margins of the mistakes.

Example 2 — Easy · One batch step

• Problem: One batch step from $\vec{W}=(0,1,1)$, $\eta =1$.
• Asked: New $\vec{W}$.
• Concept: Batch update.
• Approach: ${\sum }_{j\in S}{y}_j{\vec{X}}_j^{\prime }$.
• Solution: $(-1)(1,0,0)+(-1)(1,0,1)+(-1)(1,1,0)=(-3,-1,-1)$. $\vec{W}=(0,1,1)+(-3,-1,-1)=(-3,0,0)$.
• Final answer: $(-3,0,0)$.

Key lesson

A big jump — all three mistakes pushed at once.

Example 3 — Moderate · Run the batch algorithm

• Problem: Continue the batch algorithm to convergence from $(0,1,1)$ ($\eta =1$).
• Asked: Trajectory.
• Concept: Batch perceptron.
• Approach: Repeat.
• Solution:

step	$\vec{W}$	mistakes $S$	$J$	next $\vec{W}$
1	(0, 1, 1)	(0,0),(0,1),(1,0)	2	(−3, 0, 0)
2	(−3, 0, 0)	(1,1)	3	(−2, 1, 1)
3	(−2, 1, 1)	(1,1) (tie)	0	(−1, 2, 2)
4	(−1, 2, 2)	(0,1),(1,0)	2	(−3, 1, 1)
5	(−3, 1, 1)	(1,1)	1	(−2, 2, 2)
6	(−2, 2, 2)	(0,1),(1,0) (ties)	0	(−4, 1, 1)
7	(−4, 1, 1)	(1,1)	2	(−3, 2, 2)
—	(−3, 2, 2)	none ($yf=3,1,1,1$)	—	stop

• Final answer: $\vec{W}=(-3,2,2)$ after 7 batch updates (this happens to be the maximum-margin separator).

Python check

W = np.array([0, 1, 1.]); steps = 0
while True:
    S = [j for j in range(4) if y_and[j] * (W @ Xa[j]) <= 0]
    if not S: break
    W = W + sum(y_and[j] * Xa[j] for j in S); steps += 1; print(steps, W)
# ends at [-3. 2. 2.] after 7 steps

Key lesson

Batch converged in fewer steps (7) than online updates (18), though each step uses more points.

Example 4 — Hard · A batch step lowers the restricted cost

• Problem: Show that one batch step reduces the restricted cost: for fixed $S$, $J_S(\vec{W})=-{\sum }_{j\in S}{y}_j{\vec{W}}^T{\vec{X}}_j^{\prime }$ decreases by $\eta \Vert \vec{g}{\Vert }^2$ where $\vec{g}={\sum }_{j\in S}{y}_j{\vec{X}}_j^{\prime }$. Verify on Example 2.
• Asked: Proof and numeric check.
• Concept: Gradient descent decreases the cost.
• Approach: Substitute the update.
• Solution: $J_S(\vec{W}+\eta \vec{g})=J_S(\vec{W})-\eta {\vec{g}}^T{\sum }_{j\in S}{y}_j{\vec{X}}_j^{\prime }=J_S(\vec{W})-\eta \Vert \vec{g}{\Vert }^2$. Example 2: $J_S=2$, $\vec{g}=(-3,-1,-1)$, $\Vert \vec{g}{\Vert }^2=11$ ⇒ new restricted cost $2-11=-9$; direct: $\vec{W}=(-3,0,0)$ gives $yf=(3,3,3)$ on those three points ⇒ $-9$ ✓.
• Final answer: Decrease of $\eta \Vert \vec{g}{\Vert }^2=11$.

Key lesson

The restricted cost can become negative: points become correctly classified; the next $S$ is recomputed (here $(1,1)$ became wrong), which is why $\eta$ matters.

Example 5 — Very Hard · Online = SGD

• Problem: Derive that the per-point online rule is stochastic gradient descent on $J$, and compare the cost $J$ after the online and batch runs ended (both $0$) and the number of weight changes.
• Asked: Equivalence and comparison.
• Concept: SGD vs full gradient.
• Approach: Per-point cost.
• Solution: Per-point cost $J_j(\vec{W})=\max (0,-y_j{\vec{W}}^T{\vec{X}}_j^{\prime })$ (perceptron loss); its sub-gradient at a mistake is $-y_j{\vec{X}}_j^{\prime }$; descent step $\vec{W}\leftarrow \vec{W}+\eta y_j{\vec{X}}_j^{\prime }$ = the online rule. $J={\sum }_j{J}_j$ ⇒ batch = sum of per-point sub-gradients. Final: online reached $\vec{W}=(-4,3,2)$ in $18$ weight changes; batch reached $(-3,2,2)$ in $7$; both have $J=0$.
• Final answer: Online = SGD, batch = full gradient; $18$ vs $7$ updates.

Key lesson

Different update schedules reach different separators; none is guaranteed to be max-margin.

Common mistakes

• Wrong sign in the update.
• Re-using the old $S_k$ after the weights have changed.

Exam traps

• $J\ge 0$; $J=0$ for a separating hyperplane.
• Batch needs all misclassified samples simultaneously (memory-hungry).

Connections: C49–C50, gradient descent in logistic regression (C27) and backpropagation (C54).

Mastery checklist

• Compute $S_k$, $J$ and the batch update.
• Show online = SGD.
• Compare online vs batch.

---

C52. The XOR Problem and the Multilayer Perceptron

Intuition

One neuron draws one line. XOR needs two lines. Let a first layer of neurons compute features (here OR and AND), and a second neuron combine them linearly. The hidden layer transforms a non-separable problem into a separable one.

flowchart LR
    x1((x₁)) --> OR["h₁ = OR<br/>x₁+x₂−½ > 0"]
    x2((x₂)) --> OR
    x1 --> AND["h₂ = AND<br/>x₁+x₂−3/2 > 0"]
    x2 --> AND
    OR -- "+1" --> Y["y = h₁ − h₂ − ½ > 0"]
    AND -- "−1" --> Y

Formal content (lecture)

Step activation $f(g)=1$ if $g>0$, else $0$. With inputs $x_1,x_2\in \{0,1\}$:

• OR: $g_1(\vec{X})=x_1+x_2-\frac{1}{2}$ (output $0$ only for $(0,0)$).
• AND: $g_2(\vec{X})=x_1+x_2-\frac{3}{2}$ (output $1$ only for $(1,1)$).
• XOR = OR and not AND. Hidden layer $Y_1=f(g_1)$, $Y_2=f(g_2)$; output layer $Y=f(Y_1-Y_2-\frac{1}{2})$.

$x_1{x}_2$	$Y_1$ (OR)	$Y_2$ (AND)	$Y_1-Y_2-\frac{1}{2}$	$Y$
00	0	0	$-0.5$	0
01	1	0	$0.5$	1
10	1	0	$0.5$	1
11	1	1	$-0.5$	0

• The hidden layer maps the four inputs to $(0,0),(1,0),(1,0),(1,1)$ in $(Y_1,Y_2)$ space, where “class B” $=\{(1,0)\}$ lies on one side of the line $Y_1-Y_2=\frac{1}{2}$ and class A $=\{(0,0),(1,1)\}$ on the other — linearly separable.
• A multilayer feedforward network = input layer + one or more hidden layers + output layer; it generalises to any input dimension and any numbers of layers and nodes.

Key insights

• Non-linearity is essential: if all activations were linear (identity), a stack of layers collapses to a single linear map (Example 5).
• Hidden layers learn a representation in which a linear classifier works.

Python helper for this section

step = lambda g: (np.asarray(g) > 0).astype(int)
def xor_net(x1, x2):
    h1 = step(x1 + x2 - .5); h2 = step(x1 + x2 - 1.5)          # OR, AND
    return step(h1 - h2 - .5)

Worked examples

Example 1 — Very Easy · A neuron that computes OR

• Problem: Verify that $g_1=x_1+x_2-\frac{1}{2}$ with the step activation computes OR on all four inputs.
• Asked: Truth table.
• Concept: Perceptron as OR.
• Approach: Evaluate.
• Solution: $00$: $-0.5\to 0$; $01$: $0.5\to 1$; $10$: $0.5\to 1$; $11$: $1.5\to 1$.
• Final answer: OR ✓.

Key lesson

The threshold $-\frac{1}{2}$ lets any single active input fire the neuron.

Example 2 — Easy · A neuron that computes AND

• Problem: Same for AND with $g_2=x_1+x_2-\frac{3}{2}$.
• Asked: Truth table.
• Concept: Perceptron as AND.
• Approach: Evaluate.
• Solution: $00$: $-1.5\to 0$; $01$: $-0.5\to 0$; $10$: $-0.5\to 0$; $11$: $0.5\to 1$.
• Final answer: AND ✓.

Key lesson

Raising the threshold to $-\frac{3}{2}$ demands both inputs.

Example 3 — Moderate · A single neuron cannot do XOR

• Problem: Prove no single perceptron computes XOR (class $0$ for $(0,0),(1,1)$; class $1$ for $(0,1),(1,0)$).
• Asked: Impossibility.
• Concept: Linear inseparability.
• Approach: Contradict the inequalities.
• Solution: Need $b<0$; $w_2+b>0$; $w_1+b>0$; $w_1+w_2+b<0$. Add the 2nd and 3rd: $w_1+w_2+2b>0$ ⇒ $w_1+w_2+b>-b>0$, contradicting the 4th. (Geometrically, the hulls of $\{(0,1),(1,0)\}$ and $\{(0,0),(1,1)\}$ both contain $(0.5,0.5)$.)
• Final answer: Impossible.

Key lesson

One linear threshold unit cannot realise XOR.

Example 4 — Hard · XNOR from the same hidden units

• Problem: Design a two-layer network for XNOR (output $1$ iff $x_1=x_2$) re-using the OR / AND hidden units.
• Asked: Output weights.
• Concept: Reuse hidden features.
• Approach: XNOR $=1-$XOR; negate the output discriminant.
• Solution: Use $f_{out}=f(-Y_1+Y_2+\frac{1}{2})$. $00$: $(0,0)\to 0.5>0\to 1$ ✓. $01$ and $10$: $(1,0)\to -0.5\to 0$ ✓. $11$: $(1,1)\to 0.5\to 1$ ✓.
• Final answer: Hidden OR & AND; output $f(-Y_1+Y_2+0.5)$.

Python check

for x1, x2 in [(0,0), (0,1), (1,0), (1,1)]:
    h1, h2 = step(x1 + x2 - .5), step(x1 + x2 - 1.5)
    print((x1, x2), "XOR", int(step(h1 - h2 - .5)), "XNOR", int(step(-h1 + h2 + .5)))

Key lesson

The same hidden layer supports different outputs.

Example 5 — Very Hard · Why non-linearity is essential

• Problem: (a) Show a 2-layer network with linear (identity) activations is equivalent to a single linear map. (b) Describe the decision region of the XOR network in the original plane: output $1$ iff $0<x_1+x_2-\frac{1}{2}\wedge x_1+x_2-\frac{3}{2}\le 0$.
• Asked: Collapse proof and region.
• Concept: Need for non-linearity; composite regions.
• Approach: Matrix product; two parallel lines.
• Solution: (a) Hidden $\vec{h}=W_1\vec{x}+{\vec{b}}_1$; output $\vec{y}=W_2\vec{h}+{\vec{b}}_2=(W_2{W}_1)\vec{x}+(W_2{\vec{b}}_1+{\vec{b}}_2)$ — affine in $\vec{x}$; extra layers only multiply matrices ⇒ no new expressive power. (b) $Y=1$ iff $Y_1=1,Y_2=0$ iff $\frac{1}{2}<x_1+x_2\le \frac{3}{2}$: a diagonal band between two parallel lines, containing $(0,1)$ and $(1,0)$ ($x_1+x_2=1$) but not $(0,0)$ ($0$) or $(1,1)$ ($2$).
• Final answer: Linear nets collapse; the XOR region is the strip $\frac{1}{2}<x_1+x_2\le \frac{3}{2}$.

 x2
  1 +  (0,1)=1 ╲     ╲  (1,1)=0
    |           ╲  band ╲        output = 1 only inside the band
  0 +  (0,0)=0   ╲     ╲ (1,0)=1
    +---------------------→ x1
         x1+x2 = ½     x1+x2 = 3/2

Key lesson

A hidden layer of threshold units can carve out a band, a union of intersections of half-spaces — the building block of arbitrary regions.

Common mistakes

• Believing deeper linear networks are more powerful.
• Forgetting the thresholds ($-\frac{1}{2},-\frac{3}{2}$).

Exam traps

• “Two-layer” ≠ two hidden layers (the lecture’s figure has 1 hidden + 1 output layer).
• XOR is the standard example of a non-linearly-separable problem.

Connections: C49 (single unit), C53–C54 (general networks and training), SVM kernels (C33: another way to make XOR separable).

Mastery checklist

• Realise OR and AND with threshold units.
• Prove XOR is not linearly separable.
• Build XOR / XNOR with two layers.

---

C53. Architecture and Forward Computation of a Multilayer Feedforward Network

Intuition

Signals flow forward: each node takes a weighted sum of the previous layer’s outputs (plus a bias), passes it through a squashing function, and sends the result on. The whole network is a composition of summations and sigmoids — a flexible, differentiable family of non-linear functions.

Formal definition (lecture 23.1–23.2)

• $L$ layers; layer 1 = input (it just fans out the inputs $y_i^1=x_i$, $n_1=m$), layer $L$ = output ($n_L=C$ nodes = number of classes), layers $\mathrm{2..}L-1$ hidden with arbitrary sizes $n_l$.
• Net input of node $j$ in layer $l+1$ and its output: $S_j^{l+1}={\sum }_{r=0}^{n_l}{w}_{rj}^l{y}_r^l(\text{with }{y}_0^l\equiv 1,w_{0j}^l=\text{bias}),y_j^{l+1}=f\left(S_j^{l+1}\right).$
• Activation: logistic $f(S)=\frac{1}{1+e^{-S}}$ (differentiable), with $f^{\prime }(S)=f(S)(1-f(S))=y(1-y)$ and $f^{\prime }\le \frac{1}{4}$.
• Parameters: $w=\{w_{ij}^l\mid i=\mathrm{0..}{n}_l;j=\mathrm{1..}{n}_{l+1};l=\mathrm{1..}L-1\}$; count $={\sum }_{l=1}^{L-1}(n_l+1)n_{l+1}$.

Key insights

• Training samples $({\vec{X}}_r,{\vec{Z}}_r)$: ${\vec{Z}}_r$ = desired output (one-hot for classification).
• Test-time use needs only the forward pass.

Python helper — the small 2-2-1 network used in Examples 3–5 and in C54

W1 = np.array([[-.5, 1, 1], [.3, -1, .5]])        # hidden layer: rows = nodes, cols = (bias, x1, x2)
W2 = np.array([.1, 2, -1])                        # output node:  (bias, from h1, from h2)
def forward(W1, W2, x):
    h = sigmoid(W1 @ np.r_[1, x]); y = sigmoid(W2 @ np.r_[1, h]); return h, y

Worked examples

Example 1 — Very Easy · Count the weights

• Problem: Network with layer sizes $3\text{-}4\text{-}2$. Count the weights including biases.
• Asked: Parameter count.
• Concept: $(n_l+1)n_{l+1}$.
• Approach: Per layer pair.
• Solution: $(3+1)\cdot 4=16$; $(4+1)\cdot 2=10$; total $26$.
• Final answer: $26$.

Key lesson

Each node in the next layer has one bias.

Example 2 — Easy · A small digit classifier

• Problem: Count parameters for $784\text{-}100\text{-}10$.
• Asked: Parameters.
• Concept: Same.
• Approach: $785\cdot 100+101\cdot 10$.
• Solution: $78,500+1,010=79,510$.
• Final answer: $79,510$.

Key lesson

Most weights sit between the large input layer and the first hidden layer.

Example 3 — Moderate · A forward pass

• Problem: A $2\text{-}2\text{-}1$ sigmoid network: hidden node 1: $w_0=-0.5,w_1=1,w_2=1$; hidden node 2: $w_0=0.3,w_1=-1,w_2=0.5$; output: $w_0=0.1$, weights $2$ (from hidden 1) and $-1$ (from hidden 2). Compute the output for $\vec{x}=(1,0)$ and the squared error $J=\frac{1}{2}(y-z{)}^2$ with target $z=1$.
• Asked: $y$ and $J$.
• Concept: Forward pass.
• Approach: Layer by layer.
• Solution: $S_1^2=0.5\Rightarrow y_1^2=\sigma (0.5)=0.6225$. $S_2^2=-0.7\Rightarrow y_2^2=\sigma (-0.7)=0.3318$. $S^3=0.1+2(0.6225)-0.3318=1.0131\Rightarrow y=\sigma (1.0131)=0.7336$. $J=\frac{1}{2}(0.2664{)}^2=0.0355$.
• Final answer: $y=0.734$, $J=0.0355$.

Python check

h, yout = forward(W1, W2, [1, 0]); print(h, yout, .5 * (yout - 1)**2)    # [0.6225 0.3318]  0.7336  0.0355

Key lesson

Keep the bias input $y_0=1$ at every layer.

Example 4 — Hard · The network as one formula

• Problem: For the same network, write the output as a single composite formula and compute the output for $\vec{x}=(0,0)$.
• Asked: Composite function and value.
• Concept: Composition of sigmoids.
• Approach: Substitute.
• Solution: $y=\sigma (0.1+2\sigma (-0.5+x_1+x_2)-\sigma (0.3-x_1+0.5x_2))$. At $(0,0)$: $\sigma (-0.5)=0.3775$; $\sigma (0.3)=0.5744$; inner $=0.1+0.7550-0.5744=0.2806$; $y=\sigma (0.2806)=0.5697$.
• Final answer: $y(0,0)=0.570$.

Python check

print(forward(W1, W2, [0, 0])[1])                         # 0.5697

Key lesson

A network is just a nested function — differentiable by the chain rule.

Example 5 — Very Hard · Bounded outputs, bounded slopes

• Problem: Show that a network with logistic units and arbitrarily many hidden layers still produces outputs strictly in $(0,1)$, and compute the largest possible value of $f^{\prime }$ and what it implies for a chain of $L$ layers.
• Asked: Range and bound.
• Concept: Properties of the logistic function.
• Approach: Calculus.
• Solution: $0<\sigma (S)<1$ for all finite $S$ ⇒ every hidden and output value lies in $(0,1)$. $f^{\prime }(S)=y(1-y)$; maximised at $y=\frac{1}{2}$ ($S=0$): $f_{\max }^{\prime }=\frac{1}{4}$. In a chain $x\to y^2\to \cdots \to y^L$ the derivative $\partial y^L/\partial x={\prod }_l{w}^l{f}^{\prime }(S^{l+1})$ is at most ${\prod }_l|w^l|\cdot (\frac{1}{4}{)}^{L-1}$ in magnitude: with $|w|\le 1$ it shrinks by a factor $\ge 4$ per layer (e.g. $4^{-4}=0.0039$ for $L=5$).
• Final answer: Outputs in $(0,1)$; $f^{\prime }\le \frac{1}{4}$ ⇒ gradients can vanish in deep networks.

Key lesson

The sigmoid derivative’s bound explains why deep sigmoid nets are hard to train (vanishing gradients).

Common mistakes

• Omitting bias weights from the count.
• Indexing weights backwards ($w_{ij}^l$ goes from $i$ in layer $l$ to $j$ in layer $l+1$).

Exam traps

• Input nodes do no computation (fan-out).
• Output layer size $=C$ classes.

Connections: C52, C54, softmax output (C28).

Mastery checklist

• Do a forward pass by hand.
• Count parameters.
• State $f^{\prime }=y(1-y)$ and its maximum.

---

C54. The Backpropagation Algorithm

Intuition

To adjust a weight deep inside the network you need to know how the final error changes when that weight changes. The chain rule lets you compute this for every weight by sweeping once forward (to get outputs) and once backward (to get “error signals” $\gamma$ node by node), re-using shared factors instead of re-differentiating from scratch.

flowchart LR
    X[input] -->|forward| H[hidden y¹] -->|forward| O[output y]
    O --> E["error J = ½(y−z)²"]
    E -->|"γᴸ = (y−z)f′"| GO["γ output"]
    GO -->|"γˡ = f′ Σ γˡ⁺¹ w"| GH["γ hidden"]
    GH -->|"∂J/∂w = γ·y"| U["update weights"]

Formal derivation (lecture 23.3)

Training pairs $({\vec{X}}_r,{\vec{Z}}_r)$, $r=\mathrm{1..}N$. Squared-error criterion per sample and total: $J_r(w)=\frac{1}{2}{\sum }_{j=1}^C(y_j^L(w,{\vec{X}}_r)-z_{rj}{)}^2,J(w)={\sum }_{r=1}^N{J}_r(w)(\text{empirical risk }{R}_N=\frac{2}{N}J).$ Gradient descent: $w(k+1)=w(k)-\eta \nabla J_r(w(k))$ (per sample) or $-\eta {\sum }_r\nabla J_r$ (batch).

Weight gradient. $w_{ij}^l$ influences $J$ only through $S_j^{l+1}$ with $\frac{\partial S_j^{l+1}}{\partial w_{ij}^l}=y_i^l$. Define the error (delta) ${\gamma }_j^l=\partial J/\partial S_j^l$. Then $\boxed{\frac{\partial J}{\partial w_{ij}^l}={\gamma }_j^{l+1}{y}_i^l.}$ Output layer: ${\gamma }_j^L=\frac{\partial J}{\partial y_j^L}\frac{\partial y_j^L}{\partial S_j^L}=(y_j^L-z_j)f^{\prime }(S_j^L)$. Hidden layers (recursion): $S_j^l$ affects $J$ only via the net inputs of layer $l+1$: ${\gamma }_j^l={\sum }_{r=1}^{n_{l+1}}\frac{\partial J}{\partial S_r^{l+1}}\frac{\partial S_r^{l+1}}{\partial y_j^l}\frac{\partial y_j^l}{\partial S_j^l}=\boxed{f^{\prime }(S_j^l)\sum _{r=1}^{n_{l+1}}{\gamma }_r^{l+1}{w}_{jr}^l.}$ Algorithm: (1) initialise weights randomly; (2) feed a sample; (3) forward pass computing all $y_j^l$; (4) backward pass: ${\gamma }^L$ then ${\gamma }^{L-1},\dots ,{\gamma }^2$; (5) update $w_{ij}^l\leftarrow w_{ij}^l-\eta {\gamma }_j^{l+1}{y}_i^l$; (6) repeat until convergence. Test time: forward pass only.

Remarks (lecture): no convergence proof exists for backpropagation; there is no sharp stopping rule — in practice stop when the Euclidean norm of the gradient falls below a threshold.

Key insights

• The cost of the gradient $\approx$ cost of two passes, independent of the number of weights.
• With logistic units $f^{\prime }(S)=y(1-y)$, so ${\gamma }_j^L=(y_j-z_j)y_j(1-y_j)$.

Worked examples

Example 1 — Very Easy · Sigmoid slopes

• Problem: $f^{\prime }(S)$ for logistic outputs $y=0.5$ and $y=0.9$.
• Asked: Derivatives.
• Concept: $f^{\prime }=y(1-y)$.
• Approach: Direct.
• Solution: $0.5(0.5)=0.25$; $0.9(0.1)=0.09$.
• Final answer: $0.25,0.09$.

Key lesson

Saturated units ($y$ near $0$ or $1$) learn slowly.

Example 2 — Easy · One neuron, one step

• Problem: A single logistic neuron, input $x=1$, weights $w_0=w_1=0$, target $z=1$, $J=\frac{1}{2}(y-z{)}^2$, $\eta =1$. One gradient step.
• Asked: New weights and $J$.
• Concept: Output-layer rule.
• Approach: $\gamma =(y-z)y(1-y)$.
• Solution: $S=0\Rightarrow y=0.5$. $\gamma =(0.5-1)(0.25)=-0.125$. $\partial J/\partial w_0=-0.125$; $\partial J/\partial w_1=-0.125$. $w\leftarrow 0+0.125=0.125$ (both). New $S=0.25$, $y=0.5622$; $J$ from $0.125$ to $\frac{1}{2}(0.4378{)}^2=0.0958$.
• Final answer: $w_0=w_1=0.125$, $J:0.125\to 0.0958$.

Python check

y0 = sigmoid(0); gam = (y0 - 1) * y0 * (1 - y0); w = 0 - 1 * gam
print(gam, w, sigmoid(2 * w), .5 * (sigmoid(2 * w) - 1)**2)   # -0.125  0.125  0.5622  0.0958

Key lesson

A negative gradient ⇒ weights increase ⇒ the output moves toward the target.

Example 3 — Moderate · A full backprop step

• Problem: Network of C53 Ex. 3 (input $(1,0)$, target $z=1$). Compute all $\gamma$‘s, all weight gradients and perform one update with $\eta =0.5$; recompute $J$.
• Asked: Full backprop step.
• Concept: Algorithm.
• Approach: Forward values: $y_1^2=0.6225,y_2^2=0.3318,y=0.7336$.
• Solution: Output: ${\gamma }^3=(0.7336-1)(0.7336)(0.2664)=-0.05205$. Hidden: ${\gamma }_1^2=0.6225(0.3775)(-0.05205)(2)=-0.02446$; ${\gamma }_2^2=0.3318(0.6682)(-0.05205)(-1)=0.01154$. Gradients: output weights $(\text{bias},h_1,h_2)$: ${\gamma }^3(1,0.6225,0.3318)=(-0.05205,-0.03240,-0.01727)$. Hidden 1: ${\gamma }_1^2(1,1,0)=(-0.02446,-0.02446,0)$; hidden 2: ${\gamma }_2^2(1,1,0)=(0.01154,0.01154,0)$. Update ($\eta =0.5$): output $(0.1,2,-1)\to (0.1260,2.0162,-0.9914)$; hidden 1: $(-0.5,1,1)\to (-0.4878,1.0122,1)$; hidden 2: $(0.3,-1,0.5)\to (0.2942,-1.0058,0.5)$. New forward pass: $y=0.7439$; $J=\frac{1}{2}(0.2561{)}^2=0.0328$.
• Final answer: ${\gamma }^3=-0.0521$, ${\gamma }^2=(-0.0245,0.0115)$; $J:0.0355\to 0.0328$.

Python check — a complete backprop step

x = np.array([1, 0.]); h, yout = forward(W1, W2, x)
g3 = (yout - 1) * yout * (1 - yout)                       # output delta
g2 = h * (1 - h) * g3 * W2[1:]                            # hidden deltas  γ = f'(S) · γ_next · w
gW2 = g3 * np.r_[1, h]; gW1 = np.outer(g2, np.r_[1, x])   # ∂J/∂w = γ · y_in
print(g3, g2); print(gW2); print(gW1)
W2n, W1n = W2 - .5 * gW2, W1 - .5 * gW1
print(W2n, W1n.round(4).tolist()); print(.5 * (forward(W1n, W2n, x)[1] - 1)**2)   # 0.0328

Key lesson

One backprop step lowers the error; a hidden delta = (output delta) × (connecting weight) × $f^{\prime }$.

Example 4 — Hard · Gradient checking

• Problem: Verify the analytic gradient of the output weight from hidden node 1 and of the hidden weight (input $x_1\to$ hidden 1) by finite differences.
• Asked: Gradient check.
• Concept: Correctness of backprop.
• Approach: $[J(w+\epsilon )-J(w)]/\epsilon$ with $\epsilon =10^{-6}$.
• Solution: Analytic: output weight: ${\gamma }^3{y}_1^2=-0.03240$; hidden weight: ${\gamma }_1^2{x}_1=-0.02446$. Numerical: perturb the output weight $2\to 2+10^{-6}$: slope $-0.032401$ ✓. Perturb the hidden weight $1\to 1+10^{-6}$: slope $-0.024466$ ✓.
• Final answer: Analytic and numerical gradients agree to $\sim 5$ digits.

Python check

J = lambda W1, W2: .5 * (forward(W1, W2, x)[1] - 1)**2; e = 1e-6
W2p = W2.copy(); W2p[1] += e; W1p = W1.copy(); W1p[0, 1] += e
print((J(W1, W2p) - J(W1, W2)) / e, gW2[1])               # -0.032401  -0.032401
print((J(W1p, W2) - J(W1, W2)) / e, gW1[0, 1])            # -0.024466  -0.024466

Key lesson

Gradient checking is the standard way to debug a backprop implementation.

Example 5 — Very Hard · Deltas, vanishing gradients, no guarantees

• Problem: (a) Derive the hidden-layer recursion for a node that feeds two next-layer nodes. (b) For a chain of $L$ single logistic neurons with all weights $1$ and every unit at $S=0$, find ${\gamma }^2/{\gamma }^L$ and comment. (c) Why are there no convergence guarantees?
• Asked: Derivation, magnitude, comment.
• Concept: Chain rule; vanishing gradient.
• Approach: Apply the formula repeatedly.
• Solution: (a) $J$ depends on $S_j^l$ through $y_j^l=f(S_j^l)$, which enters $S_a^{l+1}$ with weight $w_{ja}$ and $S_b^{l+1}$ with weight $w_{jb}$: ${\gamma }_j^l=f^{\prime }(S_j^l)[w_{ja}{\gamma }_a^{l+1}+w_{jb}{\gamma }_b^{l+1}]$ ✓ (sum over all paths). (b) With $w=1$ and $f^{\prime }=\frac{1}{4}$ at every layer: ${\gamma }^l=\frac{1}{4}{\gamma }^{l+1}$ ⇒ ${\gamma }^2=(\frac{1}{4}{)}^{L-2}{\gamma }^L$; $L=6$: $(\frac{1}{4}{)}^4=0.0039$ — the first layers receive $\approx 0.4\%$ of the output error signal ⇒ they learn extremely slowly. (c) $J(w)$ is a non-convex function of the weights (products of weights through non-linearities) so gradient descent may reach local minima or plateaus; the lecture states no convergence proof exists and uses a gradient-norm threshold as a practical stop rule.
• Final answer: ${\gamma }_j^l=f^{\prime }(S_j^l){\sum }_r{\gamma }_r^{l+1}{w}_{jr}^l$; attenuation $(\frac{1}{4}{)}^{L-2}$; no guarantee of global convergence.

Python check

print([0.25**(L - 2) for L in (3, 4, 5, 6, 10)])          # 0.25  0.0625  0.0156  0.0039  1.5e-05

Key lesson

Backprop is exact differentiation, not an optimiser with guarantees — depth and activation choice affect trainability.

Common mistakes

• Using the output-layer formula for hidden layers.
• Forgetting $f^{\prime }(S)$ in the recursion.
• Updating weights during the backward pass before all $\gamma$‘s are computed (the $\gamma$‘s use the old weights).

Exam traps

• ${\gamma }_j^L=(y_j^L-z_j)f^{\prime }(S_j^L)$ requires squared error; for softmax + cross-entropy it becomes $\hat{y}-z$ (C28).
• Per-sample (online) updates (23.6) vs summed batch updates (23.7).

Connections: C27–C28 (the gradient of logistic / softmax has the same shape), C51 (gradient descent), C53.

Mastery checklist

• Derive $\partial J/\partial w={\gamma }^{l+1}{y}^l$ and the $\gamma$ recursion.
• Execute a full backprop step by hand.
• Verify a gradient numerically.