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.

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$.

---

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.

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}\left(f\right)$. 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

• Single-layer perceptron = 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

• 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)+1(0)=1>0\Rightarrow +1$. $(0,0.5)$: $-1+0+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

• 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=0+0+1=1$, $yf=-1<0$ ✗. New $\vec{W}=(0,1,1)+(-1)(1,0,1)=(-1,1,0)$. Now $f=-1+0+0=-1$, $yf=+1>0$ ✓ (increase $=\Vert {\vec{X}}^{\prime }{\Vert }^2=2$).
• Final answer: $\vec{W}=(-1,1,0)$.
• Key lesson: One update can fix the offending point.

Example 3 — Moderate

• 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: Epoch 1: $(0,0)$: $f=0$ ⇒ update $\vec{W}=(-1,0,0)$. $(0,1)$: $f=-1$, $yf=1$ ✓. $(1,0)$ ✓. $(1,1)$: $f=-1$, $y=+1$ ⇒ update $\vec{W}=(0,1,1)$. Epoch 2: $(0,0)$: $f=0$ ⇒ $(-1,1,1)$; $(0,1)$: $f=0$ ⇒ $(-2,1,0)$; $(1,0)$: $f=-1$ ✓; $(1,1)$: $f=-1$ ⇒ $(-1,2,1)$. Epoch 3: $(0,1)$: $f=0$ ⇒ $(-2,2,0)$; $(1,0)$: $f=0$ ⇒ $(-3,1,0)$; $(1,1)$: $f=-2$ ⇒ $(-2,2,1)$. Epoch 4: $(1,0)$: $f=0$ ⇒ $(-3,1,1)$; $(1,1)$: $f=-1$ ⇒ $(-2,2,2)$. Epoch 5: $(0,1)$: $f=0$ ⇒ $(-3,2,1)$; $(1,1)$: $f=0$ ⇒ $(-2,3,2)$. Epoch 6: $(0,1)$: $f=0$ ⇒ $(-3,3,1)$; $(1,0)$: $f=0$ ⇒ $(-4,2,1)$; $(1,1)$: $f=-1$ ⇒ $(-3,3,2)$. Epoch 7: $(1,0)$: $f=0$ ⇒ $(-4,2,2)$; $(1,1)$: $f=0$ ⇒ $(-3,3,3)$. Epoch 8: $(0,1)$: $f=0$ ⇒ $(-4,3,2)$. Epoch 9: all correct: $(0,0)$: $-4$; $(0,1)$: $-2$; $(1,0)$: $-1$; $(1,1)$: $+1$ ✓. Total updates: $18$.
• Final answer: $\vec{W}=(-4,3,2)$ after $18$ updates; boundary $3x_1+2x_2=4$.
• Key lesson: The perceptron finds a separator, not the best one (the max-margin one is $(-3,2,2)$).

Example 4 — Hard

• 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 }$ ($\eta >0$) ⇒ 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 (confirmed by running).
• Final answer: $\eta \times (-4,3,2)$; identical classification.
• Key lesson: Only the direction of $\vec{W}$ matters, so with a zero start $\eta$ is irrelevant.

Example 5 — Very Hard

• 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: Epoch 1: $(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)$. We are back at $\vec{W}=\vec{0}$ after 4 updates — so the sequence repeats forever with period $4$. The sum of the four updates is $(-1)(1,0,0)+(+1)(1,0,1)+(+1)(1,1,0)+(-1)(1,1,1)=(0,0,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.
• 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 (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 (Example 4 of C49).
• Online perceptron = one sample at a time; classification: $\mathrm{sign}({\vec{W}}^T{\vec{X}}_0^{\prime })$.

Worked examples

Example 1 — Very Easy

• Problem: AND data (augmented ${\vec{X}}^{\prime }$): $R^2=\max \{1,2,2,3\}$. 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

• 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: $(0,0)$: $(-1)(-3)=3$; $(0,1)$: $(-1)(-3+2)=1$; $(1,0)$: $1$; $(1,1)$: $(+1)(-3+4)=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$).
• Key lesson: The bound is conservative.

Example 3 — Moderate

• 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}(1){\Vert }^2=1\le 1\cdot 3$ ✓; $\Vert \vec{W}(2){\Vert }^2=2\le 2\cdot 3=6$ ✓; $\Vert \vec{W}(3){\Vert }^2=3\le 9$ ✓. Alignment: $\vec{W}(1{)}^T{\vec{W}}^{\ast }=3\ge 1\cdot 1$ ✓; $\vec{W}(2{)}^T{\vec{W}}^{\ast }=0+2+2=4\ge 2$ ✓; $\vec{W}(3{)}^T{\vec{W}}^{\ast }=3+2+2=7\ge 3$ ✓.
• Final answer: All inequalities hold.
• 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

• 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

• 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

• Problem: For $\vec{W}=(0,1,1)$ find $S$ and $J$.
• Asked: $S,J$.
• Concept: Definition of $J$.
• Approach: Compute $yf$.
• Solution: $f={\vec{W}}^T{\vec{X}}^{\prime }=(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

• 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: Big jump — all three mistakes pushed at once.

Example 3 — Moderate

• Problem: Continue the batch algorithm to convergence from $(0,1,1)$ ($\eta =1$).
• Asked: Trajectory.
• Concept: Batch perceptron.
• Approach: Repeat.
• Solution: $\vec{W}=(-3,0,0)$: $yf=(3,3,3,-3)$, $S=\{(1,1)\}$, $J=3$ ⇒ add $(+1)(1,1,1)$ ⇒ $(-2,1,1)$. $(-2,1,1)$: $f=(-2,-1,-1,0)$, $yf=(2,1,1,0)$, $S=\{(1,1)\}$ (tie), $J=0$ ⇒ $(-1,2,2)$. $(-1,2,2)$: $f=(-1,1,1,3)$, $yf=(1,-1,-1,3)$, $S=\{(0,1),(1,0)\}$, $J=2$ ⇒ add $(-1)(1,0,1)+(-1)(1,1,0)=(-2,-1,-1)$ ⇒ $(-3,1,1)$. $(-3,1,1)$: $yf=(3,2,2,-1)$, $S=\{(1,1)\}$ ⇒ $(-2,2,2)$. $(-2,2,2)$: $f=(-2,0,0,2)$, $yf=(2,0,0,2)$, $S=\{(0,1),(1,0)\}$ (ties), $J=0$ ⇒ $(-4,1,1)$. $(-4,1,1)$: $yf=(4,3,3,-2)$, $S=\{(1,1)\}$ ⇒ $(-3,2,2)$. $(-3,2,2)$: $f=(-3,-1,-1,1)$, $yf=(3,1,1,1)$ all $>0$ ⇒ stop.
• Final answer: $\vec{W}=(-3,2,2)$ after 7 batch updates (this happens to be the maximum-margin separator).
• Key lesson: Batch converged in fewer steps (7) than online updates (18), though each step uses more points.

Example 4 — Hard

• 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})=-{\sum }_{j\in S}{y}_j(\vec{W}+\eta \vec{g}{)}^T{\vec{X}}_j^{\prime }=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 ⇒ $-(3+3+3)=-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

• 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 }$ = 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$ weight changes; both have $J=0$ ($S=\varnothing$).
• 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.

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}$ (classes: 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; generalises to any input dimension and numbers of layers/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.

Worked examples

Example 1 — Very Easy

• 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

• 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

• Problem: Prove no single perceptron computes XOR (classes: $0$ for $(0,0),(1,1)$; $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 hull of $\{(0,1),(1,0)\}$ and the hull of $\{(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

• 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 -1+0+0.5=-0.5\to 0$ ✓. $11$: $(1,1)\to -1+1+0.5=0.5\to 1$ ✓.
• Final answer: Hidden OR & AND; output $f(-Y_1+Y_2+0.5)$.
• Key lesson: The same hidden layer supports different outputs.

Example 5 — Very Hard

• Problem: (a) Show a 2-layer network with linear (identity) activations is equivalent to a single linear map. (b) Show the XOR network’s decision regions in the original plane: the output is $1$ iff $0<x_1+x_2-\frac{1}{2}\wedge x_1+x_2-\frac{3}{2}\le 0$ — describe this region.
• 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}$; adding layers only multiplies 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}$.
• Key lesson: A hidden layer of threshold units can carve out a band, a union of half-space intersections — 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).
• The XOR problem 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.

Worked examples

Example 1 — Very Easy

• 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

• Problem: Count parameters for $784\text{-}100\text{-}10$ (a small digit classifier).
• 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

• 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+1(1)+1(0)=0.5\Rightarrow y_1^2=\sigma (0.5)=0.6225$. $S_2^2=0.3-1(1)+0.5(0)=-0.7\Rightarrow y_2^2=\sigma (-0.7)=0.3318$. $S^3=0.1+2(0.6225)-1(0.3318)=1.0131\Rightarrow y=\sigma (1.0131)=0.7336$. $J=\frac{1}{2}(0.7336-1{)}^2=\frac{1}{2}(0.0710)=0.0355$.
• Final answer: $y=0.734$, $J=0.0355$.
• Key lesson: Keep the bias input $y_0=1$ at every layer.

Example 4 — Hard

• 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$.
• Key lesson: A network is just a nested function — differentiable by the chain rule.

Example 5 — Very Hard

• 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.

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

• 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

• 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

• 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=\gamma \cdot 1=-0.125$; $\partial J/\partial w_1=\gamma x=-0.125$. $w\leftarrow 0-1(-0.125)=0.125$ (both). New $S=0.25$, $y=\sigma (0.25)=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$.
• Key lesson: Negative gradient ⇒ weights increase ⇒ output moves toward the target.

Example 3 — Moderate

• 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.2664\times 0.1954=-0.05205$. Hidden: ${\gamma }_1^2=f^{\prime }(S_1^2){\gamma }^3{w}_1=0.6225(0.3775)(-0.05205)(2)=0.2350\times (-0.10411)=-0.02446$; ${\gamma }_2^2=0.3318(0.6682)(-0.05205)(-1)=0.2217\times 0.05205=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 weights $(\text{bias},x_1,x_2)$: ${\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 $w=(0.1,2,-1)-0.5(-0.05205,-0.03240,-0.01727)=(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_1^2=\sigma (-0.4878+1.0122)=\sigma (0.5244)=0.6282$; $y_2^2=\sigma (0.2942-1.0058)=\sigma (-0.7116)=0.3293$; $S^3=0.1260+2.0162(0.6282)-0.9914(0.3293)=0.1260+1.2666-0.3265=1.0661$ ⇒ $y=\sigma (1.0661)=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$.
• Key lesson: One backprop step lowers the error; hidden-layer deltas are the output delta times the connecting weight times $f^{\prime }$.

Example 4 — Hard

• Problem: Verify the analytic gradient of the output weight from hidden node 1 and of the hidden weight $w_1^{(1\to 1)}$ (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.05205(0.6225)=-0.03240$; hidden weight: ${\gamma }_1^2{x}_1=-0.02446$. Numerical: perturb the output weight $2\to 2+10^{-6}$: $J$ changes by $-3.2401\times 10^{-8}$ ⇒ slope $-0.032401$ ✓. Perturb hidden weight $1\to 1+10^{-6}$: slope $-0.024466$ ✓.
• Final answer: Analytic and numerical gradients agree to $\sim 5$ digits.
• Key lesson: Gradient checking is the standard way to debug a backprop implementation.

Example 5 — Very Hard

• 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.
• 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 (gradient of logistic/softmax is 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.