7 concepts20 worked examples30 exercises4 exam-level7 figures
What are you here for?
08 Perceptron, neural networks and backpropagation: learning from mistakes, stacking neurons, and training them by gradient descent
Start with this
One question before you read anything. Getting it wrong is the point: it shows you what this section is for.
§08.3 — one threshold unit for 'exactly one switch'
A unit reads two switches $x_1,x_2\in\{0,1\}$, forms $v=w_0+w_1x_1+w_2x_2$ and outputs $1$ when $v>0$, else $0$. We want the output to be $1$ exactly when one switch is on and the other is off.
Spot check of the tempting choices: $(-0.5,1,1)$ gives $v=1.5$ at $(1,1)$, and $(0,1,-1)$ gives $v=-1$ at $(0,1)$; both fail.
When four inequalities clash, no amount of tuning helps; the fix is structural, a .
Two switches, one lamp: the lamp must be on exactly when one switch is up and the other is down. No single unit that adds up weighted inputs and lights the lamp above a threshold can do this, whatever its weights. Three such units in two layers can.
By the end you can train a by hand, prove when one is not enough, run a forward and a backward pass through a small network, and write the SGD update with and .
In 60 seconds
A perceptron draws one straight boundary and learns it from its mistakes; layers of neurons with smooth activations draw any boundary, and backpropagation gets every weight's gradient from one forward and one backward pass, so gradient descent can train them.
regularizing a network: shrink every weight, then step against the gradient
Three most common mistakes
Updating the perceptron the wrong way: a missed 1 ($y=1$, $\hat y=0$) adds $\eta x$, a false 1 subtracts it, and a correct answer changes nothing.
Dropping $\varphi'$ from a delta, or evaluating the logistic slope at the field: $\varphi'(v)=x(1-x)$ with the neuron's output $x=\varphi(v)$, not $v(1-v)$.
Flipping the backpropagation update: $\delta=-\partial e/\partial v$, so $\partial e/\partial w_{ij}^{(l)}=-\delta_j^{(l)}x_i^{(l-1)}$ and SGD adds $\eta\,\delta_j^{(l)}x_i^{(l-1)}$.
Two course documents give different weights:
Chapter 1 slides, undergraduate line: midterm 25, final 25, four quizzes 20, two-phase project 30.
STARS syllabus page printed on 21 September 2026: midterm 30, final 30, problem sets and quizzes 20, project 20. It is the later document; confirm which split applies.
The STARS weekly list has this topic as its sixth item; the lecture slides number it chapter 8.
How much time do you have?
10 minutes
The perceptron rule and the three backpropagation formulas, which is what most by-hand questions ask you to run.
The 60-second card · The perceptron and its mistake-driven learning rule · Backpropagation · Formula card
45 minutes
Every block once with its first worked example, then one backpropagation step from a full solution down to a bare problem.
The 60-second card · The perceptron and its mistake-driven learning rule · When the rule stops · XOR · Feedforward networks · Losses and gradient descent · Backpropagation · Weight decay and momentum · Scaffolding comes off · Formula card
full read
Adds the proofs, the look-alike pairs and enough mixed practice to decide the method yourself.
The opening pages · Recall first · The perceptron and its mistake-driven learning rule · When the rule stops · XOR · Feedforward networks · Losses and gradient descent · Backpropagation · Weight decay and momentum · Look-alike pairs · Method boxes · Scaffolding comes off · Full exam-style question · Practice set · Check yourself
By the end of this section
Compute a perceptron's output and run its learning rule by hand, with the bias input $x_0=1$ and the right sign for every update.
Decide whether a data set is linearly separable, and state what the convergence theorem promises and what it does not.
Prove that XOR is not linearly separable, and build a one-hidden-layer network of step neurons that computes it.
Run a forward pass through a feedforward network in the layer notation, with logistic, tanh, , or identity activations.
Choose the output activation and the loss for regression or classification, and write the batch, stochastic and updates.
Compute output and hidden deltas and the weight gradients by backpropagation, and carry out one SGD update.
Apply weight decay and momentum to an update, and explain what each does to the weights.
Syllabus coverage
covered
Perceptron — covered
Binary classification and linear separability
the perceptron (weighted sum, bias $w_0$ on the input $x_0=1$, step activation, decision boundary)
the online learning rule with its and error signal
the convergence theorem
no guarantee of the best separating line
Spread over two blocks: the model with its rule, then separability and convergence.
covered
neural networks — covered
XOR and why one perceptron fails
one hidden layer solves it
networks as function builders
the feedforward structure and its notation
the logistic, tanh, softplus, ReLU and identity activations, and why the step is useless for gradient descent
output layers and losses: squared error, with
Spread over three blocks: XOR and hidden layers, the forward pass, and the losses.
covered
backpropagation — covered
Batch, stochastic and mini-batch gradient descent
deltas and their backward recursion
weight gradients
the backpropagation algorithm with SGD
weight decay as regularization
momentum
The gradient descent variants sit in the losses block, weight decay and momentum in the last block.
off syllabus
Proof of the convergence theorem — off syllabus
The bound of at most $(R/\gamma)^2$ updates, from two inequalities and Cauchy-Schwarz.
Further reading: the lecture states the theorem without proof. No exercise depends on reproducing it.
off syllabus
Cross-entropy against squared error at a saturated output — off syllabus
Why a logistic output trained with squared error learns slowly when it is confidently wrong, while cross-entropy does not.
Further reading: it follows from this section's output-delta formulas; the lecture derives the squared-error delta and notes that cross-entropy works similarly.
Recall first
Logistic function
$\sigma(v)=\dfrac{1}{1+e^{-v}}=\dfrac{e^{v}}{1+e^{v}}$, the curve of logistic regression, where $\pi(x)=\sigma(\beta_0+\beta_1x)$.
It replaces the perceptron's hard step with a smooth one.
Bernoulli log-likelihood
For labels $y_i\in\{0,1\}$ and probabilities $\pi_i$: $\log p(D)=\sum_i\big[y_i\log\pi_i+(1-y_i)\log(1-\pi_i)\big]$.
Its negative is the cross-entropy loss of a classifier network.
Gradient descent and Newton-Raphson
To minimize $f$: $w_{n+1}=w_n-\gamma\nabla f(w_n)$, or Newton's $w_{n+1}=w_n-H^{-1}(w_n)\nabla f(w_n)$ with the Hessian $H$.
Networks are trained with the first; the second needs a Hessian, too costly with many weights.
Multinomial logistic regression
With $K$ classes and class $K$ as reference, $\pi_j(x)=e^{\beta_j^Tx}\big/\big(1+\sum_{k=1}^{K-1}e^{\beta_k^Tx}\big)$.
Softmax is the same formula with a score for every class.
Each factor is the derivative of one link, at the values just found.
$$\frac{de}{dw}=2\cdot3\cdot2=12$$
Chain rule.
Answer $$\boxed{de/dw=12}$$
Check
Directly: $e=\tfrac12(1-6w)^2$, so $de/dw=-6(1-6w)=-6(1-3)=12$.
Backpropagation is this product of local slopes, computed from the output backward and shared between weights.
Notation
symbol
reads as
means
watch out
$D=\{(x_i,y_i)\}_{i=1}^n$
the data set D
$n$ examples, $x_i\in\mathbb R^p$; for the perceptron $y_i\in\{0,1\}$
Networks also take real targets or one-hot class vectors.
$x(n),\ y(n),\ w(n)$
x of n, y of n, w of n
the example and the weights at iteration $n$; $x(n)=(1,x_1(n),\dots,x_p(n))$
$x(n)$ carries the leading $1$ for the bias.
$b=w_0,\ \ x_0=1$
the bias
the weight on a constant input
Updated like every other weight.
$v,\ \ \varphi(v),\ \ \hat y$
v, phi of v, y hat
the weighted sum, the activation applied to it, the prediction
For the perceptron $\varphi$ is the step, with $\varphi(0)=0$.
$\eta$
eta
the learning rate
The generalized linear models section wrote $\gamma$ for the same step size.
$l=0,\dots,L,\ \ d^{(l)}$
layer l, d of l
layer index, with $0$ the input and $L$ the output; the number of neurons in layer $l$
$d^{(l)}$ does not count the bias neuron.
$w_{ij}^{(l)}$
w i j of layer l
the weight from neuron $i$ of layer $l-1$ to neuron $j$ of layer $l$
First index: where the edge starts. $i$ runs from $0$, $j$ from $1$.
$v_j^{(l)},\ \ x_j^{(l)}$
v j of layer l, x j of layer l
the and the output of neuron $j$ in layer $l$
$x_0^{(l)}=1$ for the bias neuron; $x^{(0)}$ is the input.
$f_w(x)=x^{(L)}$
f sub w of x
the network's output for the input x
A vector when $d^{(L)}>1$; $f_{w,k}(x)=x_k^{(L)}$.
$l\big(f_w(x),y\big),\ \ J(w),\ \ e(w)$
the loss, the total loss, the example loss
the loss on one example; its sum over the training set; the loss on the example SGD is using
The letter $l$ also indexes layers; context tells them apart.
$\delta_j^{(l)}$
delta j of layer l
$-\partial e/\partial v_j^{(l)}$
Note the minus sign.
$\lambda,\ N,\ \alpha$
lambda, N, alpha
the weight decay constant, the number of training examples, the momentum constant
$0\le\alpha<1$.
$B_n,\ \lvert B_n\rvert$
the mini-batch and its size
the examples used at step $n$ of mini-batch gradient descent
The lecture writes $K$ for the batch size; here $K$ counts classes.
Conventions used here
Step at zero.
The step activation gives $1$ only for $v>0$: a field of exactly $0$ is read as class 0. A weight vector of zeros therefore calls everything 0.
Hand runs often hit v = 0 at the very first example, and this settles it.
Iteration numbers.
Iteration $n=0,1,2,\dots$ uses $x(n)$ and $w(n)$ and produces $w(n+1)$, starting from $w(0)$. A pass shows every example once, in the stated order.
Traces are graded line by line, and an off-by-one n is the commonest slip.
Augmented vectors.
Inputs are written $(1,x_1,\dots,x_p)$ and weights $(w_0,w_1,\dots,w_p)$ with the bias first, so $w^Tx$ includes the bias.
The bias then needs no separate rule.
Deltas carry a minus sign.
As in the lecture, $\delta_j^{(l)}=-\partial e/\partial v_j^{(l)}$. Gradient descent subtracts $\eta\,\partial e/\partial w$, which therefore adds $\eta\,\delta\,x$.
Other books drop the minus sign and subtract instead; the weights come out the same.
The half in the squared error.
Backpropagation examples use $e=\tfrac12\sum_k(y_k-x_k^{(L)})^2$. The regression loss $\sum_k(y_k-f_{w,k}(x))^2$ without the half doubles every gradient.
The half only rescales the learning rate, but it changes every number.
Sums over the training set.
$J(w)$ is a sum over the examples, as in the lecture; the mini-batch update averages over its batch.
Summing or averaging only rescales the learning rate.
Weight decay constants.
With $J_{\text{aug}}=J+\frac{\lambda}{N}w^Tw$ a batch step shrinks the weights by $1-\frac{2\eta\lambda}{N}$. The lecture's per-example backpropagation form is $w\leftarrow(1-\eta\lambda)\,w-\eta\,\partial e/\partial w$, with the constants folded into $\lambda$. Both penalties include the bias weights.
Questions state which form they use; the idea, shrink then step, is the same.
ReLU at zero.
$\max(0,v)$ has no derivative at $v=0$; this section takes it as $0$ there.
Libraries make the same choice, and a field of exactly 0 is rare.
Logarithms in the losses.
$\log$ is the natural logarithm, in the cross-entropy and everywhere else here.
A different base would only rescale the loss.
Four decimals.
Numbers are shown to four decimals and computed from unrounded values, so recomputing from the rounded ones can move the last digit by one.
Deltas and weight changes are small; fewer decimals would hide them.
8.1The perceptron and its mistake-driven learning rule
Adds up weighted inputs and answers 0 or 1; each misread example pushes the weights toward the right answer.
Logistic regression turned $\beta_0+\beta_1x$ into a probability and was fitted on all the data at once; the perceptron keeps the weighted sum, answers a hard 0 or 1, and learns from one example at a time.
Solvable with what we have
Fit least squares to 0/1 labels and call a point 1 when the fit exceeds $0.5$.
Fit logistic regression by Newton-Raphson, using every example at every step.
Not solvable yet
Promise zero training mistakes when one cut separates the classes.
Learn from examples that arrive one at a time.
Six sensor readings, in volts from a reference: off at $x=-1.5,-1,-0.5$ ($y=0$), on at $x=0.5,1,6$ ($y=1$); the $6$ is a surge. Fit least squares to the labels and cut where the fit crosses $0.5$. The labels average $0.5$, so the cut lands at $\bar x=0.75$.
Why it fails
The on-reading at $0.5$ has fit $0.46$ and is called off, although any cut between $-0.5$ and $0.5$ is perfect. Least squares chases the surge at $6$: it minimizes squared distance to the labels, not mistakes.
RuleThe perceptron and the perceptron learning rule
Conditions
labels $y\in\{0,1\}$; inputs augmented with $x_0=1$, so the bias is $b=w_0$
step activation: $\varphi(v)=1$ if $v>0$, else $0$
iterations $n=0,1,2,\dots$ from starting weights $w(0)$, with a constant learning rate $\eta>0$
Weigh the inputs, add the bias, and answer 1 if the sum is positive. A right answer gives $y-\hat y=0$ and changes nothing; a missed 1 adds $\eta x$, a false 1 subtracts it. The decision boundary is where $w^Tx=0$.
Why each update moves the right way
On a missed 1 ($y=1$, $\hat y=0$) the new field on the same example is $w(n+1)^Tx(n)=v(n)+\eta\,x(n)^Tx(n)$.
$x(n)^Tx(n)=\lVert x(n)\rVert^2\ge1$ because $x_0=1$, so the field rises by at least $\eta$.
On a false 1 the same computation gives a drop of $\eta\lVert x(n)\rVert^2$. One push may not cross zero, and it can disturb other examples; the next block says when the pushes stop.
The six readings. The $\textcolor{#8250df}{\text{least squares fit}}$ crosses $0.5$ at $0.75$ and misreads the on-reading at $0.5$ (ringed). The $\textcolor{#d1690a}{\text{perceptron}}$ from the first worked example answers 1 for $x>0$ and gets all six right.
Looks like this, but is not
The perceptron's output $\hat y=\varphi(w^Tx)$ is a probability of class 1, like the logistic regression output.
It is a hard 0 or 1 and carries no confidence: with $w=(0,1)$ the readings $0.5$ and $6$ both get $\hat y=1$, although their fields are $0.5$ and $6$. Logistic regression would give them different probabilities.
reading x
label y
least squares fit
its call
perceptron field v = x
its call
$-1.5$
$0$
$0.1839$
$0$
$-1.5$
$0$
$-1$
$0$
$0.2542$
$0$
$-1$
$0$
$-0.5$
$0$
$0.3244$
$0$
$-0.5$
$0$
$0.5$
$1$
$0.4649$
$0$ (wrong)
$0.5$
$1$
$1$
$1$
$0.5351$
$1$
$1$
$1$
$6$
$1$
$1.2375$
$1$
$6$
$1$
Only the reading at $0.5$ separates the two rules: its fit $0.4649$ is below $0.5$, while its field under $w=(0,1)$ is $0.5>0$.
Running the perceptron rule on the six sensor readings
Readings in volts from a reference level: $x=-1.5,\,-1,\,-0.5$ are off ($y=0$) and $x=0.5,\,1,\,6$ are on ($y=1$). Start from $w(0)=(w_0,w_1)=(0,0)$ with $\eta=1$, present the readings in the order $0.5,\, \allowbreak -0.5,\, \allowbreak 1,\, \allowbreak -1,\, \allowbreak 6,\, \allowbreak -1.5$, and repeat the pass until a full pass makes no update.
FindThe final weights, the cut they define, and the number of updates.
Every sign matches its label, so $w(n)=(0,1)$ for all $n\ge2$: the rule has converged.
Read off the cut
$$v=0+1\cdot x>0\iff x>0$$
The boundary is where the field is $0$, here at $x=0$, between the last off-reading and the first on-reading.
Answer $$\boxed{\begin{aligned}&w=(0,\,1):\ \ \hat y=1\iff x>0\\ &2\text{ updates, no mistakes}\end{aligned}}$$
Check
Direct check of the final rule: the fields $-1.5,\,-1,\,-0.5$ are not positive and $0.5,\,1,\,6$ are, so all six readings are right, where least squares misread $0.5$.
Two updates and twelve iterations: the second pass only confirms.
This settles the opening attempt: the perceptron only asks which side each example lands on, so the far reading at $6$ cannot drag its cut.
One update on a false 1 in three inputs, and why it may not be enough
A perceptron with three inputs has $w=(w_0, \allowbreak w_1, \allowbreak w_2, \allowbreak w_3)=(0.5,\, \allowbreak 1,\, \allowbreak -1,\, \allowbreak 2)$ and $\eta=0.25$. It sees $x=(x_1, \allowbreak x_2, \allowbreak x_3)=(2,\, \allowbreak 1,\, \allowbreak 0.5)$ with label $y=0$. Update the weights, then present the same example again.
FindThe weights after one update, the field on the same example before and after, and what a second presentation does.
Given
$w=(0.5,\,1,\,-1,\,2)$, bias first
example $x=(2,\,1,\,0.5)$, $y=0$
$\eta=0.25$
Solution
We augment $x$ with $x_0=1$ first, because the bias is updated like any other weight.
A second subtraction takes the field from $0.9375$ to $-0.625$, and the example is fixed.
Answer $$\boxed{\begin{aligned}&w=(0.25,\,0.5,\,-1.25,\,1.875)\\ &v:\ 2.5\to0.9375\\ &\text{fixed by a second update}\end{aligned}}$$
Check
The drop $2.5-0.9375=1.5625$ equals $\eta\lVert x\rVert^2$, computed separately from the length of $x$.
One update moves the field by $\eta\lVert x\rVert^2$ and may leave the example misread; the rule keeps cycling through the data until no example is.
Checkpoint
§08.1 — one perceptron update by hand
A perceptron has weights $w=(w_0, \allowbreak w_1, \allowbreak w_2)=(-1,\, \allowbreak 2,\, \allowbreak 1)$ and learning rate $\eta=0.5$. It is shown the example $x=(x_1,x_2)=(0.2,\,0.4)$ with label $y=1$.
Find(a) What are the weights after this example?
Given
$w=(-1,\,2,\,1)$, bias first
$x=(0.2,\,0.4)$, $y=1$, $\eta=0.5$
$\varphi(v)=1$ if $v>0$, else $0$
Hint 1/4
Decide first whether the perceptron gets this example right; the update depends only on that.
Hint 2/4
$\hat y=\varphi(w^Tx)$ with $x_0=1$, and $w\leftarrow w+\eta\,(y-\hat y)\,x$.
Hint 3/4
Here $w=(-1,2,1)$, the augmented input is $(1,\,0.2,\,0.4)$, $y=1$, $\eta=0.5$, so $v=-1+2(0.2)+1(0.4)$.
Hint 4/4
$v=-0.2$, so $\hat y=0$ and the new weights are $(-0.5,\,2.1,\,1.2)$.
Show solution
Classify first, because only a mistake changes the weights.
If some flat cut puts every class 1 point above a level $k$ and every class 0 point at or below it, the rule makes finitely many updates from any start and then never changes again. If no such cut exists, every pass misreads something and the weights never settle.
Why it stops, with a bound on the number of updates (further reading)
Write $t_i=2y_i-1\in\{-1,1\}$. On a mistake $y-\hat y=t$, so every update is $w\leftarrow w+\eta\,t\,x$ with the augmented $x$.
Move $k$ to the middle of the gap between the classes and normalize: this gives a unit vector $u$ and a $\gamma>0$ with $t_i\,u^Tx_i\ge\gamma$ for all $i$. Let $R=\max_i\lVert x_i\rVert$.
Start at $w(0)=0$. Each update adds $\eta\,t\,u^Tx\ge\eta\gamma$ to $u^Tw$, so after $m$ updates $u^Tw\ge m\eta\gamma$.
A mistake means $t\,w^Tx\le0$, so $\lVert w+\eta tx\rVert^2\le\lVert w\rVert^2+\eta^2R^2$, and after $m$ updates $\lVert w\rVert^2\le m\eta^2R^2$.
By Cauchy-Schwarz $m\eta\gamma\le u^Tw\le\lVert w\rVert\le\eta R\sqrt m$, so $m\le(R/\gamma)^2$, whatever $\eta$ is. For the six operating points below, $R^2=14$ and $\gamma=1.5/\sqrt{8.25}$ allow at most $51$ updates; the run makes $4$.
The safe (filled) and unsafe (hollow) operating points of the worked example. Before the update at $n=4$ the $\textcolor{#8250df}{\text{boundary }1-2x_1-x_2=0}$ misreads the safe point $(1,0)$ (ringed). Adding $x=(1,1,0)$ gives the $\textcolor{#d1690a}{\text{boundary }x_1+x_2=2}$, with $(1,0)$ on the safe side. Each arrow is $(w_1,w_2)$: perpendicular to its boundary and pointing to the side called 1, because a step along it raises $v$.
Looks like this, but is not
When the perceptron stops, it has found the best separating line.
It stops at the first line with no mistakes. The worked run ends at $x_1+x_2=2$, $0.71$ from the nearest safe points but $1.41$ from the unsafe ones; $x_1+x_2=2.5$ would leave $1.06$ on both sides. The same data in reverse order end at $x_1=2$, which runs through two unsafe points.
point
class
to x₁ + x₂ = 2
to x₁ + x₂ = 2.5
$(0,0)$
safe
$1.414$
$1.768$
$(0,1)$
safe
$0.707$
$1.061$
$(1,0)$
safe
$0.707$
$1.061$
$(2,2)$
unsafe
$1.414$
$1.061$
$(3,1)$
unsafe
$1.414$
$1.061$
$(2,3)$
unsafe
$2.121$
$1.768$
The perceptron's line hugs the safe points at $0.707$; the line $x_1+x_2=2.5$ splits the gap evenly at $1.061$.
Training on six operating points until a pass makes no mistake
A machine is safe ($y=1$) at the operating points $(0,0),(0,1),(1,0)$ and unsafe ($y=0$) at $(2,2),(3,1),(2,3)$, where $x_1$ measures vibration and $x_2$ temperature rise. Run the perceptron from $w(0)=(0,0,0)$ with $\eta=1$, presenting $(0,0), \allowbreak (2,2), \allowbreak (0,1), \allowbreak (3,1), \allowbreak (1,0), \allowbreak (2,3)$ in that order, until a full pass makes no update.
FindThe final weights, the boundary, the number of updates and the first $n_0$ after which nothing changes.
Directly: $x_1+x_2$ is $0,1,1$ at the safe points and $4,4,5$ at the unsafe ones. The bound in the proof above allows at most $51$ updates here, and $4\le51$.
Keep a table of $v$, $\hat y$ and $w$, and stop only after a full pass without an update; a pass with one late update has not converged yet.
Separability depends on the features: three points on a line
On a line, class 1 sits at $x=1$ and $x=3$ and class 0 at $x=2$. Show that no threshold on $x$ separates them. Then add the feature $x^2$ and find perceptron weights on $(1,x,x^2)$ that do.
FindA proof that $x$ alone fails, and weights $(w_0,w_1,w_2)$ that work.
Given
class 1: $x=1,\,3$; class 0: $x=2$
a perceptron on $x$ alone, then on the features $(x,\,x^2)$
Solution
For three points, a contradiction from three inequalities is quicker than a picture; for the new feature we choose a parabola with the right signs.
Answer $$\boxed{\begin{aligned}&\text{no cut on }x\text{ alone}\\ &w=(3.5,\,-4,\,1)\text{ on }(1,\,x,\,x^2)\end{aligned}}$$
Check
The zeros of $x^2-4x+3.5$ are $2\pm\sqrt{0.5}$, about $1.29$ and $2.71$: class 0 at $2$ lies between them and class 1 outside.
When one line fails, a new feature can make the data separable; a hidden layer learns such features instead of guessing them.
Checkpoint
§08.2 — what a long run tells you
A perceptron has made $400$ updates on a training set of $50$ examples and its weights are still changing. The run uses $\eta=1$ and started at $w(0)=0$.
Find(a) What can you conclude?
Given
$50$ training examples, presented in repeated passes
$400$ updates so far; $\eta=1$, $w(0)=0$
Hint 1/4
Ask what the theorem promises about the number of updates, and what that number depends on.
Hint 2/4
From $w(0)=0$ the number of updates is at most $(R/\gamma)^2$, with $R$ the largest input length and $\gamma$ the margin.
Hint 3/4
The run has made $400$ updates on $50$ examples; the bound reaches $400$ as soon as $R/\gamma\ge20$.
Hint 4/4
A separable set with a thin margin is still possible, so nothing is proved yet.
Show solution
The proof's bound is the only quantitative promise, so we compare 400 with it.
Compare with the bound
$$\text{updates}\le\Big(\frac{R}{\gamma}\Big)^2$$
Separable data with margin $\gamma$ and input lengths at most $R$ stop within this many updates.
right$$w(0)=0:\ \ w_\eta(n)=\eta\,w_1(n),\ \ \text{the same updates}$$
⚠ Drawing the weight vector along the boundary
the weights and the boundary both feel like 'the line'
wrong$$(w_1,w_2)\parallel\text{boundary}$$
right$$(w_1,w_2)\perp\text{boundary, toward class 1}$$
Step through the worked run below: the $\textcolor{#d1690a}{\text{boundary after}}$ each update, the $\textcolor{#8250df}{\text{boundary before}}$ dashed, and the misread point ringed. After its own update at $n=2$ the point $(0,1)$ still sits on the boundary with $v=0$; it is fixed only at $n=4$.
At the edges
w(0) = 0 no boundary
Every field is $0$, so everything is called 0 until the first update.
n ≥ 5 w = (2, −1, −1)
The second pass makes no update, so the weights never change again: $n_0=5$.
8.3XOR: why one perceptron is not enough, and how a hidden layer fixes it
Shows a two-input rule no single perceptron can learn, and computes it with two hidden neurons feeding a third.
The theorem needs one flat cut; with two binary inputs, the rule 'exactly one is on' already has none.
TheoremXOR is not linearly separable; one hidden layer computes it
Conditions
inputs $x_1,x_2\in\{0,1\}$ and target $y=1$ exactly when $x_1\neq x_2$
step neurons: $\varphi(v)=1$ if $v>0$, else $0$
$$\boxed{\begin{aligned}&\nexists\,w:\ \ \varphi(w^Tx)=x_1\oplus x_2\\ &\qquad\text{on all four inputs}\\ &\textcolor{#8250df}{h_1=\varphi(x_1-x_2-0.5)}\\ &\textcolor{#8250df}{h_2=\varphi(x_2-x_1-0.5)}\\ &\textcolor{#d1690a}{\hat y=\varphi(h_1+h_2-0.5)}\end{aligned}}$$
No single weighted sum and threshold outputs 1 on exactly the two mixed inputs. Two hidden neurons split the job: one fires only for $(1,0)$, the other only for $(0,1)$, and the output fires if either did.
Why no single perceptron works
$(0,0)\mapsto0$ needs $w_0\le0$, and $(1,1)\mapsto0$ needs $w_0+w_1+w_2\le0$.
$(1,0)\mapsto1$ and $(0,1)\mapsto1$ need $w_0+w_1>0$ and $w_0+w_2>0$.
Adding the last two gives $w_0+w_1+w_2>-w_0\ge0$, which contradicts the first step.
The four inputs and the lines of the two $\textcolor{#8250df}{\text{hidden neurons}}$. The output fires in the $\textcolor{#d1690a}{\text{shaded strips}}$, which hold exactly $(0,1)$ and $(1,0)$; the band between the lines, with $(0,0)$ and $(1,1)$, gives 0.
Looks like this, but is not
A second layer of neurons with the identity activation gives the network the extra power XOR needs.
Linear layers compose to one linear map: $h=W^Tx$ followed by $a^Th$ is again a single weighted sum of $x$, so the output neuron is still one perceptron. The nonlinearity between the layers is what bends the boundary.
Checking the XOR network on all four inputs
Take $h_1=\varphi(x_1-x_2-0.5)$, $h_2=\varphi(x_2-x_1-0.5)$ and $\hat y=\varphi(h_1+h_2-0.5)$ with the step $\varphi$. Compute every field and output for the four inputs and compare with $x_1\oplus x_2$.
Find$h_1$, $h_2$ and $\hat y$ for $(0,0), \allowbreak (0,1), \allowbreak (1,0), \allowbreak (1,1)$.
Given
hidden weights $(w_0,w_1,w_2)$: $(-0.5,\,1,\,-1)$ for $h_1$, $(-0.5,\,-1,\,1)$ for $h_2$
output weights $(-0.5,\,1,\,1)$ on $(1,\,h_1,\,h_2)$
$\varphi(v)=1$ if $v>0$, else $0$
Solution
Four inputs are few enough to check exhaustively, and an exhaustive check is the only complete proof that the wiring is right.
Hidden layer
$$v_1=x_1-x_2-0.5:\ \ -0.5,\ -1.5,\ 0.5,\ -0.5$$
In the order $(0,0), \allowbreak (0,1), \allowbreak (1,0), \allowbreak (1,1)$; only $(1,0)$ is positive, so $h_1=0,0,1,0$.
Geometric check: $\hat y=1$ exactly when $\lvert x_1-x_2\rvert>0.5$, which on $\{0,1\}^2$ means $x_1\neq x_2$.
To compute a rule one line cannot draw, give each hidden neuron an easy piece of it and let the output neuron combine the pieces.
Following the curve y = x² on [0, 3] with three step neurons
A network with one input $x\in[0,3]$ has hidden step neurons $h_1=\varphi(x)$, $h_2=\varphi(x-1)$, $h_3=\varphi(x-2)$ and an identity output $f(x)=0.25h_1+2h_2+4h_3$, meant to follow $g(x)=x^2$. Find $f$ on each piece, its largest error, and the largest error with six neurons whose cuts are $0.5$ apart.
Find$f$ on $(0,1]$, $(1,2]$, $(2,3]$; the worst error; the worst error with six neurons.
Given
hidden fields $x$, $x-1$, $x-2$ with the step $\varphi$
Spot check at $x=1.5$: $(h_1, \allowbreak h_2, \allowbreak h_3)=(1, \allowbreak 1, \allowbreak 0)$ gives $f=2.25=1.5^2$, exact at the middle of the piece as designed.
More hidden neurons give a finer staircase, which is why one hidden layer can follow a continuous curve on an interval as closely as we want.
Checkpoint
§08.3 — wiring XOR from an OR and an AND neuron
Two hidden step neurons compute $g_1=\varphi(x_1+x_2-0.5)$ and $g_2=\varphi(x_1+x_2-1.5)$ on inputs $x_1,x_2\in\{0,1\}$. The output neuron is $\hat y=\varphi(a\,g_1+c\,g_2-0.5)$.
Find(a) Which output weights $(a,c)$ make $\hat y$ equal to XOR?
right$$\text{XOR needs all four: }\hat y=0,\,1,\,1,\,0$$
Three frames: a single line always misreads an input; the two $\textcolor{#8250df}{\text{hidden lines}}$ each isolate one mixed input; in the $(h_1,h_2)$ plane the four inputs sit at three points, and one $\textcolor{#d1690a}{\text{output line}}$ separates them.
At the edges
one line at least one wrong
The proof in the box: the four inequalities cannot all hold.
(h₁, h₂) plane separable
$(0,0)$ and $(1,1)$ both map to $(0,0)$, so the hidden layer has moved the points to where one line suffices.
8.4Feedforward networks: layers, weights and the forward pass
Names every weight and signal in a layered network, and computes the output in one sweep from input to output.
The XOR network had one hidden layer and weights chosen by hand; learning them needs a name for every signal in a network of any depth.
DefinitionFeedforward network and forward propagation
Conditions
layer $0$ is the input, layers $1,\dots,L-1$ are hidden, layer $L$ is the output
layer $l$ has $d^{(l)}$ neurons plus a bias neuron $0$ with $x_0^{(l)}=1$
each neuron of layer $l-1$ feeds every neuron of layer $l$, and there are no other connections
Each neuron adds up the previous layer's outputs with its own weights, bias included, and passes the sum through its activation. Doing this for layer 1, then layer 2, up to layer $L$ is the forward pass, and the last layer's outputs are the prediction.
A $2$-$2$-$1$ network in the lecture's notation. The $\textcolor{#1f6feb}{\text{blue edges}}$ carry the three weights into hidden neuron 1: $w_{01}^{(1)}$ from the bias, $w_{11}^{(1)}$ and $w_{21}^{(1)}$ from the inputs. The first index is where an edge starts, the second where it ends.
Looks like this, but is not
The bias neuron $x_0^{(l)}$ is a neuron like the others, with incoming weights and a field of its own.
It is fixed at $x_0^{(l)}=1$ and only sends. That is why $i$ starts at $0$ but $j$ at $1$ in $w_{ij}^{(l)}$, and why layer $l$ receives $(d^{(l-1)}+1)\,d^{(l)}$ weights.
activation
φ(v)
φ′(v)
φ(0)
φ′(0)
range
identity
$v$
$1$
$0$
$1$
all reals
logistic
$\frac{1}{1+e^{-v}}$
$\varphi(v)\big(1-\varphi(v)\big)$
$0.5$
$0.25$
$(0,1)$
tanh
$\tanh v$
$1-\tanh^2v$
$0$
$1$
$(-1,1)$
softplus
$\ln(1+e^v)$
$\frac{1}{1+e^{-v}}$
$\ln2=0.6931$
$0.5$
$(0,\infty)$
ReLU
$\max(0,v)$
$0$ or $1$
$0$
$0$ by convention
$[0,\infty)$
step
$1$ if $v>0$, else $0$
$0$ for $v\neq0$
$0$
none
$\{0,1\}$
The lecture's versions $1/(1+e^{-av})$ and $a\tanh(bv)$ scale these slopes by $a$ and $ab$. Only the step has no usable slope; the logistic's slope never exceeds $0.25$.
A forward pass through a 2-2-1 network
Inputs $x=(x_1,x_2)=(2,\,-1)$. The two hidden neurons use the logistic $\varphi(v)=1/(1+e^{-v})$, with weights $w_{01}^{(1)}=0$, $w_{11}^{(1)}=0.5$, $w_{21}^{(1)}=1$ into neuron 1 and $w_{02}^{(1)}=w_{12}^{(1)}=w_{22}^{(1)}=0.5$ into neuron 2. The output is linear, with $w_{01}^{(2)}=0.1$, $w_{11}^{(2)}=1$, $w_{21}^{(2)}=-0.4$. Compute $f_w(x)$ and the error $e=\tfrac12\big(y-f_w(x)\big)^2$ for the target $y=1$.
Find$v^{(1)}$, $x^{(1)}$, $f_w(x)$ and $e$.
Given
$x^{(0)}=(1,\,2,\,-1)$, bias first
into hidden neuron 1: $(0,\,0.5,\,1)$; into hidden neuron 2: $(0.5,\,0.5,\,0.5)$; logistic
into the output: $(0.1,\,1,\,-0.4)$; identity; target $y=1$
Solution
The forward pass goes layer by layer by definition; we write each field as the bias plus the products, in the order of the index $i$.
Layer 1
$$v_1^{(1)}=0\cdot1+0.5\cdot2+1\cdot(-1)=0$$
The weights into neuron 1 are the ones whose second index is $1$.
Range check: with both hidden outputs in $(0,1)$, the output must lie between $0.1-0.4=-0.3$ and $0.1+1=1.1$, and $0.3076$ does.
Keep every $v$ and every $x$ from the forward pass; the backward pass needs all of them.
Softplus is a smooth ReLU
The lecture asks how softplus $s(v)=\ln(1+e^v)$ relates to the ReLU $r(v)=\max(0,v)$. Compare them at $v=-2,\,0,\,2$, find their gap for every $v$, and compare their slopes.
Find$s$, $r$ and $s-r$ at the three fields; a formula for $s-r$; the two slopes.
Given
softplus $s(v)=\ln(1+e^v)$, ReLU $r(v)=\max(0,v)$
the fields $v=-2,\ 0,\ 2$
Solution
A few values show the pattern, and one line of algebra turns it into a formula for every $v$.
At $v=2$ the formula gives $\ln(1+e^{-2})=0.1269$, the same as $2.1269-2$ from the direct values.
Softplus never differs from ReLU by more than $\ln2\approx0.69$, and its slope is the logistic; ReLU is the cheaper version with a corner at $0$.
Checkpoint
§08.4 — counting the weights of a network
A feedforward network takes $4$ inputs, has one hidden layer of $5$ neurons and an output layer of $3$ neurons. Layers 0 and 1 each have a bias neuron.
Find(a) How many weights $w_{ij}^{(l)}$ does the network have?
Given
$d^{(0)}=4$, $d^{(1)}=5$, $d^{(2)}=3$
full connections between consecutive layers; $x_0^{(0)}=x_0^{(1)}=1$
Hint 1/4
Count the weights between each pair of consecutive layers, then add.
Hint 2/4
Layer $l$ receives $(d^{(l-1)}+1)\,d^{(l)}$ weights: every neuron of layer $l-1$, bias included, feeds every neuron of layer $l$.
Hint 3/4
Here layer 1 receives $(4+1)\cdot5$ and layer 2 receives $(5+1)\cdot3$.
Hint 4/4
$25+18=43$ weights.
Show solution
Weights only join consecutive layers, so we count each pair of layers separately.
Into layer 1
$$(d^{(0)}+1)\,d^{(1)}=5\cdot5=25$$
Each of the $5$ hidden neurons receives $4$ input weights and $1$ bias weight.
Into layer 2
$$(d^{(1)}+1)\,d^{(2)}=6\cdot3=18$$
Each output neuron receives $5$ hidden weights and $1$ bias weight.
Total
$$25+18=43$$
Sum over the two layers.
Answer $$\boxed{43}$$
Check
The same formula on the $2$-$2$-$1$ network of the figure gives $(2+1)\cdot2+(2+1)\cdot1=9$, the nine edges drawn there.
Every neuron that receives weights also receives one from the bias neuron below it.
⚠ Leaving the bias out of the count
the bias neuron is not one of the $d^{(l)}$ neurons of its layer
wrong$$d^{(l-1)}\,d^{(l)}\ \text{weights into layer }l$$
right$$\big(d^{(l-1)}+1\big)\,d^{(l)}\ \text{weights into layer }l$$
⚠ Swapping the two indices of a weight
matrix habits read the first index as the receiving neuron
Five activations, each with $\textcolor{#1f6feb}{\varphi}$ solid and $\textcolor{#d1690a}{\varphi'}$ dashed. The step's slope is $0$ wherever it exists, which is why gradient descent needs the smooth ones. In the softplus frame the $\textcolor{#8250df}{\text{ReLU}}$ is dotted for comparison.
At the edges
v → ±∞
The logistic and tanh flatten, so their slopes fade to 0; ReLU and softplus keep slope 1 on the right.
v = 0
The logistic has its largest slope $0.25$ here and tanh its largest slope $1$; ReLU has a corner, and its slope there is taken as $0$.
8.5Losses and gradient descent: batch, stochastic and mini-batch
Turns predictions into one number to minimize, and steps downhill using all examples, one random example, or a few.
The forward pass turns weights into a prediction; a loss scores the prediction, and gradient descent changes the weights to lower the score.
MethodLosses for networks and three gradient descent updates
Conditions
$J(w)=\sum_{i=1}^n l\big(f_w(x_i),y_i\big)$ over the training set
$l_i(w)=l\big(f_w(x_i),y_i\big)$; $I$ is a random index and $B$ a random batch of indices, drawn afresh at every step; $\overline{\nabla l}_B=\frac{1}{\lvert B\rvert}\sum_{i\in B}\nabla l_i$ is the batch's average gradient
For a number, score the prediction by squared error; for a class, turn the output fields into probabilities with softmax and pay minus the log of the true class's probability. Then step against the gradient of the whole sum, of one random example's loss, or of a small random batch.
Why one random example points the right way on average
SGD draws $I$ uniformly from $\{1,\dots,n\}$, so $E\big[\nabla l_I\big]=\sum_{i=1}^n\frac1n\nabla l_i=\frac1n\nabla J(w)$.
An SGD step with rate $\eta$ is, on average, a batch step with rate $\eta/n$; the noise around that average is the price of a step that costs one example instead of $n$.
Contours of $J(w_0,w_1)=\sum_{i=1}^4\big(y_i-w_0-w_1x_i\big)^2$ for the points $(-1,-1), \allowbreak (0,1), \allowbreak (1,0.5), \allowbreak (2,2.5)$, from the start $(-1.5,\,2.2)$ with $\eta=0.05$. $\textcolor{#d1690a}{\text{Batch gradient descent}}$ takes $10$ smooth steps; $\textcolor{#8250df}{\text{SGD}}$ takes $40$ noisy ones for the same $40$ example gradients and keeps jittering near the minimum $(0.25,\,1)$.
Looks like this, but is not
A classifier can output the class number itself, $\hat y\in\{1,2,3\}$, from one linear output neuron trained with squared error.
Squared error on class numbers says class 3 is farther from class 1 than class 2 is, an order the classes do not have. One output per class, with softmax and cross-entropy, treats every pair of classes alike.
Softmax probabilities and the cross-entropy for three classes
A network's output fields for one example are $v^{(L)}=(2,\,1,\,0)$ over three classes, and the true class is the second, $y=(0,1,0)$. Find the softmax probabilities, the predicted class and the cross-entropy loss.
Find$f_{w,k}(x)$ for $k=1,2,3$; $\hat y=\arg\max_kf_{w,k}(x)$; $l=-\sum_ky_k\log f_{w,k}(x)$.
Given
$v^{(L)}=(2,\,1,\,0)$
one-hot label $y=(0,\,1,\,0)$
$\log$ is the natural logarithm
Solution
Exponentiate once and reuse the sum for all three probabilities; the one-hot label then leaves a single term in the loss.
Shift check: subtracting $2$ from every field gives $(0,-1,-2)$, exponentials $(1,\,0.3679,\,0.1353)$ with sum $1.5032$, and the same probabilities.
Adding a constant to all fields leaves softmax unchanged, so only differences between fields matter; the loss is small only when the true class gets most of the probability.
One batch step and one SGD step on a linear neuron
A single neuron with the identity activation predicts $f_w(x)=wx$, with no bias. The examples are $(x,y)=(1,2),\,(2,3),\,(-1,-1)$ and the loss is $l_i=(y_i-wx_i)^2$. At $w=0$ with $\eta=0.05$, take one batch step, one SGD step on the second example, and compare with the average SGD step.
FindThe batch step, the SGD step on $(2,3)$, and the average of the three possible SGD steps.
Given
examples $(1,2),\ (2,3),\ (-1,-1)$
$l_i=(y_i-wx_i)^2$ and $J=\sum_il_i$
$w=0$, $\eta=0.05$
Solution
Both methods need per-example gradients, so we compute the three of them once and combine them two ways.
The least squares slope is $\sum_ix_iy_i/\sum_ix_i^2=9/6=1.5$, so every step moves from $0$ toward $1.5$, the batch step the furthest.
An SGD step costs one example instead of all $n$ and points the right way on average, at $1/n$ of the batch step; that is why SGD makes $n$ updates in the time makes one.
Checkpoint
§08.5 — cross-entropy for one example
A three-class network outputs the softmax probabilities $(0.2,\,0.5,\,0.3)$ for an example whose true class is class 3.
Find(a) What is the cross-entropy loss on this example?
Given
$f_w(x)=(0.2,\,0.5,\,0.3)$
one-hot label $y=(0,\,0,\,1)$
natural logarithm
Hint 1/4
The one-hot label switches off every term but one; find which one survives.
Hint 2/4
$l=-\sum_ky_k\log f_{w,k}(x)$.
Hint 3/4
With $y=(0,0,1)$ and $f_w(x)=(0.2,0.5,0.3)$ only $-1\cdot\log0.3$ remains.
Hint 4/4
$l=-\log0.3=1.204$.
Show solution
A one-hot label turns the sum into a single term, so we find that term first.
The zeros in the label remove the other two terms.
Evaluate
$$-\log0.3=1.204$$
Natural logarithm.
Answer $$\boxed{l=1.204}$$
Check
Range check: a perfect prediction scores $-\log1=0$ and a uniform one $-\log\tfrac13=1.0986$; $0.3$ is just below $\tfrac13$, so the loss is just above $1.0986$.
Cross-entropy looks only at the true class's probability; how the rest is split does not matter.
⚠ Taking the log of the predicted class's probability
8.6Backpropagation: deltas flow backward, gradients fall out
Gets every weight's gradient from one forward and one backward pass, reusing each layer's deltas for the layer before.
SGD needs $\partial e/\partial w_{ij}^{(l)}$ for every weight, and the chain rule applied weight by weight would recompute the same products over and over.
TheoremBackpropagation
Conditions
one example: $e(w)=l\big(f_w(x),y\big)$, with every $v$ and $x$ from its forward pass
$\delta_j^{(l)}=-\partial e/\partial v_j^{(l)}$, minus sign included
output delta shown for $e=\tfrac12\sum_k\big(y_k-x_k^{(L)}\big)^2$
Start at the output: its delta is the error times its activation's slope. A hidden neuron's delta is its own slope times the weighted sum of the deltas of the neurons it feeds. A weight's gradient is minus the delta at its end times the signal at its start, so SGD adds $\eta$ times that product.
Where the three formulas come from
The weight $w_{ij}^{(l)}$ enters $e$ only through $v_j^{(l)}$, and $\partial v_j^{(l)}/\partial w_{ij}^{(l)}=x_i^{(l-1)}$. So $$\frac{\partial e}{\partial w_{ij}^{(l)}}=\frac{\partial e}{\partial v_j^{(l)}}\,x_i^{(l-1)}=-\delta_j^{(l)}x_i^{(l-1)}.$$
The field $v_i^{(l-1)}$ reaches $e$ through $x_i^{(l-1)}=\varphi(v_i^{(l-1)})$ and then through every $v_j^{(l)}$, with $\partial v_j^{(l)}/\partial x_i^{(l-1)}=w_{ij}^{(l)}$.
Adding the paths gives the recursion: $$-\frac{\partial e}{\partial v_i^{(l-1)}}=\sum_j\Big(-\frac{\partial e}{\partial v_j^{(l)}}\Big)w_{ij}^{(l)}\,\varphi'\big(v_i^{(l-1)}\big).$$
At the output, $v_j^{(L)}$ appears only in $\tfrac12\big(y_j-\varphi(v_j^{(L)})\big)^2$, whose derivative is $-\big(y_j-x_j^{(L)}\big)\varphi'\big(v_j^{(L)}\big)$; the minus sign of $\delta$ removes the minus.
The worked example's network after the forward pass ($\textcolor{#1f6feb}{\text{blue}}$) and the backward pass ($\textcolor{#d1690a}{\text{orange}}$). Each hidden delta is the output delta $0.6924$, sent back along one output weight and multiplied by that neuron's slope $\varphi'(v)=x(1-x)$.
Looks like this, but is not
Backpropagation is a training method of its own, used by networks instead of gradient descent.
It is only a way to compute the gradient. The update is still gradient descent, batch, stochastic or mini-batch; backpropagation makes that gradient cost a small, fixed multiple of one forward pass instead of one chain-rule derivation per weight.
One SGD step by backpropagation on a 2-2-1 network
Take the network and example of the forward pass above: $x=(2,-1)$, target $y=1$; logistic hidden neurons with weights $(0,\,0.5,\,1)$ into neuron 1 and $(0.5,\,0.5,\,0.5)$ into neuron 2; a linear output with weights $(0.1,\,1,\,-0.4)$; and $e=\tfrac12\big(y-f_w(x)\big)^2$. The forward pass gave $x^{(1)}=(0.5,\,0.7311)$ and $f_w(x)=0.3076$. Compute all deltas, the nine gradients and the weights after one SGD step with $\eta=0.5$.
Find$\delta^{(2)}$, $\delta_1^{(1)}$, $\delta_2^{(1)}$, the gradients $\partial e/\partial w_{ij}^{(l)}$ and the updated weights.
Given
$x^{(0)}=(1,\,2,\,-1)$; $y=1$; $\eta=0.5$
into hidden neuron 1: $(0,\,0.5,\,1)$; into hidden neuron 2: $(0.5,\,0.5,\,0.5)$; logistic
Backpropagation reuses the forward values, so we go: output delta, hidden deltas, all nine gradients from one formula, and only then the update, with the old weights throughout.
Finite differences: nudging $w_{21}^{(2)}$ by $\pm0.0001$ changes $e$ at the rate $-0.5062$, and nudging $w_{11}^{(1)}$ at the rate $-0.3462$, as computed. After the step the output is $1.0792$ and $e$ falls from $0.2397$ to $0.0031$.
One backward pass gave all nine gradients: three deltas and nine products.
Forward pass, deltas from the output back, every gradient as $-\delta\times$ the signal at the start of the weight, and only then the update.
The output delta for softmax with cross-entropy
With a softmax output and the cross-entropy $e=-\sum_ky_k\log x_k^{(L)}$ for a one-hot $y$, show that $\delta_j^{(L)}=y_j-x_j^{(L)}$. Evaluate it for the fields $v^{(L)}=(2,1,0)$ with true class 2.
FindA formula for $\delta_j^{(L)}=-\partial e/\partial v_j^{(L)}$ and its three values.
Given
$x_k^{(L)}=e^{v_k^{(L)}}\big/\sum_me^{v_m^{(L)}}$ and $\sum_ky_k=1$
$v^{(L)}=(2,1,0)$, $y=(0,1,0)$, so $x^{(L)}=(0.6652,\,0.2447,\,0.0900)$
Solution
Writing $\log x_k^{(L)}=v_k^{(L)}-\log\sum_me^{v_m^{(L)}}$ splits the derivative into two easy pieces instead of a quotient rule.
The deltas add to $0$, because both $y$ and the softmax output add to $1$; a numerical derivative of $e$ in $v_2^{(L)}$ also gives $-0.7553$.
Softmax with cross-entropy gives the output delta 'target minus output' with no slope factor, the same form as the perceptron's error signal.
Checkpoint
§08.6 — one hidden delta
A hidden neuron with the logistic activation has output $x_i^{(l-1)}=0.8$. It feeds two neurons through $w_{i1}^{(l)}=2$ and $w_{i2}^{(l)}=-1$, whose deltas are $\delta_1^{(l)}=0.1$ and $\delta_2^{(l)}=0.3$.
Find(a) What is $\delta_i^{(l-1)}$?
Given
logistic neuron with output $x_i^{(l-1)}=0.8$
$w_{i1}^{(l)}=2$, $w_{i2}^{(l)}=-1$
$\delta_1^{(l)}=0.1$, $\delta_2^{(l)}=0.3$
Hint 1/4
A hidden neuron's delta collects the deltas it feeds, scaled by its own slope.
Hint 2/4
$\delta_i^{(l-1)}=\varphi'\big(v_i^{(l-1)}\big)\sum_jw_{ij}^{(l)}\delta_j^{(l)}$, and for the logistic $\varphi'=x(1-x)$.
Hint 3/4
Here $x=0.8$, so $\varphi'=0.8\cdot0.2=0.16$, and $\sum_jw_{ij}^{(l)}\delta_j^{(l)}=2(0.1)+(-1)(0.3)$.
Hint 4/4
$\delta_i^{(l-1)}=0.16\cdot(-0.1)=-0.016$.
Show solution
The recursion needs two numbers, the slope and the weighted sum of deltas, so we compute each and multiply.
Weight decay adds a ridge-type penalty on all the weights; in the update it shrinks every weight by the same factor, then steps against the gradient. Momentum makes each change a fraction $\alpha$ of the previous change plus the new gradient step, so steady steps build up and steps that flip sign cancel.
Where the shrink factor and the speed-up come from
$\nabla\big(\tfrac{\lambda}{N}w^Tw\big)=\tfrac{2\lambda}{N}w$, so $w-\eta\nabla J_{\text{aug}}=w-\tfrac{2\eta\lambda}{N}w-\eta\nabla J$.
With the same gradient step $g$ every time, momentum gives $\Delta w(n)=g\,(1+\alpha+\dots+\alpha^{n})\to\frac{g}{1-\alpha}$: steady steps grow up to $1/(1-\alpha)$ times.
With steps alternating $\pm g$, the changes approach $\pm\frac{g}{1+\alpha}$: an oscillation is damped by the factor $1/(1+\alpha)$.
$f(w)=\tfrac12\big(w_1^2+20w_2^2\big)$, $\eta=0.09$, $20$ steps from $(-4,\,1)$. $\textcolor{#8250df}{\text{Plain gradient descent}}$ flips sign across the steep direction and crawls along the gentle one; $\textcolor{#d1690a}{\text{momentum }\alpha=0.5}$ damps the zigzag and reaches the minimum. The first step is the same for both.
Looks like this, but is not
Weight decay is a new kind of regularization invented for neural networks.
It is the ridge penalty on the network's weights. For a single linear neuron with squared error, $J+\frac{\lambda}{N}w^Tw$ is ridge regression with penalty $\lambda/N$, bias included; only the shrink before each gradient step is new.
One gradient step with weight decay
A network is trained on $N=50$ examples with $\eta=0.1$ and weight decay $\lambda=5$. One weight is $w=1.5$, and the gradient of the unpenalized loss with respect to it is $\partial J/\partial w=-0.4$. Take one batch step with and without weight decay.
FindThe shrink factor, the new weight with decay, and the new weight without it.
Given
$N=50$, $\lambda=5$, $\eta=0.1$
$w=1.5$, $\partial J/\partial w=-0.4$
Solution
The shrink-then-step form of the box keeps the two effects apart, so we compute the factor first.
Straight from $J_{\text{aug}}$: its gradient is $-0.4+\tfrac{2\cdot5}{50}\cdot1.5=-0.1$, and $1.5-0.1\cdot(-0.1)=1.51$.
Weight decay costs one multiplication per weight per step and pulls the largest weights back the hardest, which keeps a network from fitting noise with extreme weights.
Momentum on a steady slope and on an oscillating one
With $\alpha=0.5$ and $\Delta w(-1)=0$, a weight receives the gradient term $\eta\,\delta_j^{(l)}(n)\,x_i^{(l-1)}(n)$ equal to (i) $0.1$ at every step, (ii) $+0.1, \allowbreak -0.1, \allowbreak +0.1, \allowbreak -0.1, \allowbreak \dots$ Find the first four changes $\Delta w(0),\dots,\Delta w(3)$ in each case and their long-run size.
Find$\Delta w(0),\dots,\Delta w(3)$ in both cases, and their limits.
Given
$\alpha=0.5$, $\Delta w(-1)=0$
(i) the gradient term is $0.1$ at every step
(ii) the gradient term alternates $+0.1,\,-0.1,\,\dots$
Solution
The recursion is one multiply and one add per step, so we iterate it and then read the limit from a geometric series.
Steady slope
$$\Delta w=0.1,\ \ 0.15,\ \ 0.175,\ \ 0.1875$$
Each change is half the previous one plus $0.1$.
$$\Delta w(n)\to\frac{0.1}{1-0.5}=0.2$$
The geometric series $0.1\,(1+0.5+0.25+\cdots)$ doubles the step.
Oscillating slope
$$\Delta w=0.1,\ \ -0.05,\ \ 0.075,\ \ -0.0625$$
Half of the previous change points the other way and cancels part of the new step.
The error is only $0.5$, so the step is half the perceptron's.
Answer $$\boxed{w=(0.25,\ 1,\ 0.75)}$$
Check
New field $0.25+2-0.75=1.5$, so $\hat y=0.8176$, closer to $1$.
A logistic neuron moves on every example, a little when it is nearly right.
Same example, same weights, same $\eta$ and the same formula $w+\eta\,(y-\hat y)\,x$: the perceptron's hard $\hat y=0$ gives a full step to $(0.5,\,1.5,\,0.5)$, the logistic neuron's $\hat y=0.5$ gives half of it.
How to tell them apart
A hard 0/1 output updates only on mistakes and by the full $\eta x$; a probability output with cross-entropy updates on every example by $\eta\,(y-\hat y)\,x$, and only that one is gradient descent on a smooth loss.
A confidently wrong logistic output trained with squared error
A logistic output neuron has field $v=-4$ on an example with target $y=1$. With the squared error $e=\tfrac12(y-\hat y)^2$, find the output delta.
Find$\delta=(y-\hat y)\,\varphi'(v)$.
Given
$v=-4$, so $\hat y=1/(1+e^{4})=0.0180$
$y=1$; $e=\tfrac12(y-\hat y)^2$
Solution
The box's output delta applies directly, with the logistic slope $\hat y(1-\hat y)$.
The error is nearly $1$, but the slope at $v=-4$ is only about $0.018$.
Answer $$\boxed{\delta=0.0173}$$
Check
The logistic slope never exceeds $0.25$, so this delta can never exceed $0.25$; at $v=-4$ it is far below that.
Squared error with a saturated logistic output learns slowly exactly when it is most wrong.
The same output trained with cross-entropy
Same neuron and example, now with the cross-entropy $e=-[y\log\hat y+(1-y)\log(1-\hat y)]$.
Find$\delta=-\partial e/\partial v$.
Given
$v=-4$, $\hat y=0.0180$, $y=1$
cross-entropy loss
Solution
For a logistic output with cross-entropy the slope cancels, so $\delta=y-\hat y$.
Delta
$$\delta=y-\hat y=1-0.0180=0.9820$$
$\partial(-\log\hat y)/\partial\hat y=-1/\hat y$ meets the slope $\hat y(1-\hat y)$, and only $1-\hat y$ is left.
Answer $$\boxed{\delta=0.9820}$$
Check
Ratio $0.9820/0.0173\approx57$: at this example the cross-entropy delta is about $57$ times larger.
Cross-entropy keeps the delta large while the output is wrong, which is why classifiers use it.
Same neuron, same field $v=-4$, same target: the squared-error delta is $0.0173$ and the cross-entropy delta $0.9820$, about $57$ times larger.
How to tell them apart
Squared error keeps the factor $\varphi'(v)$, which vanishes when a logistic output saturates; cross-entropy with a logistic or softmax output cancels it and leaves $y-\hat y$.
Scaffolding comes off
The common skeleton
Forward: compute every field $v$ and output $x$, layer by layer, and keep them.
Output delta: $\delta^{(L)}=(y-x^{(L)})\,\varphi'(v^{(L)})$ for squared error.
Hidden deltas: $\delta_i^{(l-1)}=\varphi'(v_i^{(l-1)})\sum_jw_{ij}^{(l)}\delta_j^{(l)}$, with the old weights.
Backpropagation on a 1-1-1 network with a logistic hidden neuron
One input $x=2$, one logistic hidden neuron with bias $w_{01}^{(1)}=-1$ and weight $w_{11}^{(1)}=0.5$, one linear output with $w_{01}^{(2)}=0.2$ and $w_{11}^{(2)}=1$. Target $y=1$, $e=\tfrac12\big(y-f_w(x)\big)^2$, $\eta=0.5$. Do one SGD step.
New forward pass: $v^{(1)}=0.1875$, $x^{(1)}=0.5467$, $f_w(x)=0.35+1.075\cdot0.5467=0.9377$, so $e$ drops from $0.045$ to $0.0019$.
The same five moves work at any depth; only the number of deltas grows.
2 · you write the reasoning
Easier: the same shape with a ReLU hidden neuron, where every slope is $0$ or $1$. One input $x=1$; hidden bias $0.5$ and weight $1$ (ReLU); output bias $0$ and weight $2$ (linear); target $y=2$; $\eta=0.1$. For each line, write why it is allowed.
The hidden weights add $\eta\,\delta^{(1)}$ times $1$ and $x=1$, so the hidden output shrinks too.
3 · find the buried error
Harder, and the solution below hides two errors. A 2-2-1 network: $x=(1,\,2)$, target $y=2$; logistic hidden neurons with weights $(-1,\,1,\,0.5)$ into neuron 1 and $(0.5,\,-1,\,0.25)$ into neuron 2; a linear output with weights $(0,\,2,\,-1)$; $e=\tfrac12\big(y-f_w(x)\big)^2$ and $\eta=0.1$. Find the new $w_{11}^{(1)}$ and $w_{22}^{(1)}$.
Step 1.$v_1^{(1)}=-1+1+1=1,\ \ v_2^{(1)}=0.5-1+0.5=0;\ \ x^{(1)}=(0.73106,\ 0.5)$: forward pass through the hidden layer.
Step 2.$f_w(x)=0+2\cdot0.73106-1\cdot0.5=0.9621$ and $\delta^{(2)}=2-0.9621=1.0379$: output and output delta.
Step 3.$\varphi'(v_1^{(1)})=1\cdot(1-1)=0\ \Rightarrow\ \delta_1^{(1)}=0\cdot2\cdot1.0379=0$: hidden delta of neuron 1.
Step 4.$\delta_2^{(1)}=0.5\,(1-0.5)\cdot(-1)\cdot1.0379=-0.2595$: hidden delta of neuron 2.
Step 5.$w_{11}^{(1)}\leftarrow1+0.1\cdot0\cdot1=1$: update of $w_{11}^{(1)}$.
Step 6.$w_{22}^{(1)}\leftarrow0.25-0.1\cdot(-0.2595)\cdot2=0.3019$: update of $w_{22}^{(1)}$.
the two buried errors (2)
⚠ step 3
The logistic slope was evaluated at the field: $\varphi'(1)$ is $x(1-x)$ with $x=\varphi(1)=0.7311$, not $1\cdot(1-1)$.
$\varphi(1-\varphi)$ is remembered as '$v(1-v)$', and at $v=0$ or $v=1$ it even gives round numbers.
right
$\varphi'(1)=0.7311\cdot0.2689=0.1966$, so $\delta_1^{(1)}=0.1966\cdot2\cdot1.0379=0.4081$, and Step 5 becomes $w_{11}^{(1)}=1+0.1\cdot0.4081\cdot1=1.0408$.
⚠ step 6
The update subtracts $\eta\,\delta\,x$; with $\delta=-\partial e/\partial v$ it must add it.
Gradient descent is remembered as 'minus', but the minus sign already sits inside the delta.
§08.6 — one backpropagation step with a tanh hidden neuron
A network has two inputs, one hidden neuron with $\varphi(v)=\tanh v$ and a linear output. It is trained on one example with the squared error $e=\tfrac12\big(y-f_w(x)\big)^2$.
Find
(a) Find all five weights after one SGD step.
(b) Explain why $w_{11}^{(2)}$ does not change.
Given
$x=(1,\,-1)$, $y=0.5$, $\eta=0.2$
into the hidden neuron: $w_{01}^{(1)}=0$, $w_{11}^{(1)}=0.5$, $w_{21}^{(1)}=0.5$
into the output: $w_{01}^{(2)}=0.25$, $w_{11}^{(2)}=1$
$\tanh'(v)=1-\tanh^2v$
Hint 1/4
Run the skeleton: forward pass, output delta, hidden delta, then one update per weight.
Hint 2/4
$\delta^{(2)}=y-f_w(x)$ for a linear output, $\delta^{(1)}=\big(1-\tanh^2v^{(1)}\big)\,w_{11}^{(2)}\,\delta^{(2)}$, and $w\leftarrow w+\eta\,\delta\times$(its start signal).
Hint 3/4
Here $v^{(1)}=0+0.5\cdot1+0.5\cdot(-1)=0$, so $x^{(1)}=\tanh0=0$ and $f_w(x)=0.25$; $y=0.5$ and $\eta=0.2$.
Hint 4/4
$\delta^{(2)}=\delta^{(1)}=0.25$, giving $w^{(2)}=(0.3,\,1)$ and $w^{(1)}=(0.05,\,0.55,\,0.45)$.
Show solution
The skeleton applies unchanged; only the slope formula of tanh is new.
New forward pass: $v^{(1)}=0.05+0.55-0.45=0.15$, $x^{(1)}=0.1489$, $f_w(x)=0.3+0.1489=0.4489$, closer to the target $0.5$.
A weight whose start signal is 0 gets no gradient on that example, however large the delta at its end.
Full exam-style question
Exam-style: ReLU hidden layer, logistic output, cross-entropy and weight decayexam format
A network has inputs $x=(x_1,x_2)$, two ReLU hidden neurons and one logistic output neuron $\hat y=1/(1+e^{-v^{(2)}})$, trained with the cross-entropy $e=-[y\log\hat y+(1-y)\log(1-\hat y)]$. Weights into hidden neuron 1: $(0.5,\,1,\,-1)$; into hidden neuron 2: $(-1,\,0.5,\,1)$; into the output: $(-0.5,\,2,\,1)$, bias first. One example: $x=(1,\,2)$, $y=1$.
(a) Carry out the forward pass and find $e$.
(b) Show that $\delta^{(2)}=y-\hat y$ for this output and loss.
(c) Find both hidden deltas.
(d) With the per-example weight decay update $w\leftarrow(1-\eta\lambda)\,w-\eta\,\partial e/\partial w$, $\eta=0.5$ and $\lambda=0.1$, update $w_{11}^{(2)}$, $w_{21}^{(2)}$ and $w_{22}^{(1)}$.
(e) What happens to the weights into hidden neuron 1 on this example, and why?
Find$e$; the output delta; $\delta_1^{(1)}$ and $\delta_2^{(1)}$; three updated weights; what happens to neuron 1's weights.
Given
$x^{(0)}=(1,\,1,\,2)$, $y=1$
hidden (ReLU): into neuron 1 $(0.5,\,1,\,-1)$, into neuron 2 $(-1,\,0.5,\,1)$
output (logistic): $(-0.5,\,2,\,1)$
$\eta=0.5$, $\lambda=0.1$; the ReLU slope is $0$ for $v<0$ and $1$ for $v>0$
Solution
Every part feeds the next, so we keep all forward values, derive the output delta once and reuse it; the decay factor $1-\eta\lambda=0.95$ is the same for every weight.
A numerical derivative of $-\log\big(1/(1+e^{-v})\big)$ at $v=1$ gives $-0.2689$, confirming (b). A forward pass with all nine updated weights gives $\hat y=0.9029$ and $e=0.1021$, down from $0.3133$.
Two deltas were needed; the zero one came free from the ReLU slope.
A ReLU that is inactive on an example passes back no gradient, so its incoming weights change only through weight decay; a unit inactive on every example stops learning.
Practice
A · concept 4 questions
1§08.3 — do linear hidden layers help?
A classmate claims that a network with two hidden layers of $10$ neurons each, all with the identity activation $\varphi(v)=v$, followed by one step output neuron, can compute XOR on $\{0,1\}^2$ once it has enough neurons.
Find(a) Is the claim true or false?
Given
hidden activations: identity
output: one step neuron
XOR: $y=1$ exactly when $x_1\neq x_2$
Hint 1/4
Ask what the output neuron's field is as a function of the two inputs.
Hint 2/4
A composition of maps of the form $x\mapsto W^Tx+b$ is again of that form.
Hint 3/4
Here both hidden layers are linear, so the output field is $a_0+a_1x_1+a_2x_2$ for some numbers, fed to one step neuron.
Hint 4/4
That is a single perceptron, which cannot compute XOR, so the claim is false.
Show solution
Following the fields through the layers shows the whole network in one formula, which settles the question for every choice of weights at once.
Each identity layer is an affine map, and affine maps compose to an affine map.
$$v_{\text{out}}=a^Tg+c=a_0+a_1x_1+a_2x_2$$
The output field is one weighted sum of the inputs plus a constant.
Verdict
$$\hat y=\varphi(a_0+a_1x_1+a_2x_2)$$
This is a single perceptron, and no perceptron computes XOR.
Answer $$\boxed{\text{False}}$$
Check
Contrast: with step activations in the hidden layer, the network of this section's XOR block does compute XOR, so the nonlinearity is what matters, not the neuron count.
Hidden layers add power only through their nonlinear activations; stacking linear layers adds nothing.
2§08.2 — does the learning rate change the answer?
Two students run the perceptron on the same data, in the same order, both from $w(0)=0$. One uses $\eta=1$, the other $\eta=0.1$.
Find(a) True or false: they make the same updates at the same iterations and end with the same boundary.
Given
same data, same order of presentation
$w(0)=0$; $\eta=1$ against $\eta=0.1$
Hint 1/4
Compare the two weight vectors after each step, not their sizes.
Hint 2/4
If $w'(n)=0.1\,w(n)$, then $w'(n)^Tx=0.1\,w(n)^Tx$ has the same sign, and the update adds $0.1$ times the same vector.
Hint 3/4
Both start at $w(0)=0=0.1\cdot0$, so the relation holds at $n=0$ and then at every step.
Hint 4/4
Same signs, same mistakes, same updates up to the factor $0.1$, and the same boundary $w^Tx=0$: true.
Show solution
An induction on n compares the two runs step by step without running either.
Numerical check: nudging any weight by a small amount leaves every step output, and so the loss, unchanged, unless a field sits exactly at 0.
Gradient training needs activations with useful slopes, which is why networks use the logistic, tanh or ReLU instead of the step.
4§08.6 — reading the sign of an output delta
A regression network with a linear output neuron and the squared error $e=\tfrac12\big(y-x^{(L)}\big)^2$ has output delta $\delta^{(L)}=0.4$ on an example.
Find(a) True or false: the network's output was below the target, and SGD will raise the output bias.
Given
linear output: $\varphi'(v)=1$
$\delta^{(L)}=-\partial e/\partial v^{(L)}=0.4$
Hint 1/4
Translate the delta back into target and output.
Hint 2/4
For a linear output with this loss, $\delta^{(L)}=y-x^{(L)}$, and the bias update is $+\eta\,\delta^{(L)}\cdot1$.
Hint 3/4
Here $\delta^{(L)}=0.4$, so $y-x^{(L)}=0.4$.
Hint 4/4
The output was $0.4$ below the target, and the bias rises by $0.4\,\eta$: true.
Show solution
Writing the delta in terms of target and output makes both parts of the claim readable.
Classify each example with the current weights, and update only on a mistake.
Hint 2/4
$v=w^Tx$ with $x_0=1$; a missed 1 adds $\eta x$, a false 1 subtracts it.
Hint 3/4
The augmented inputs are $(1,1,1)$, $(1,0,1)$ and $(1,1,0)$, with labels $1,0,0$ and $\eta=0.5$.
Hint 4/4
$w(1)=(0.5,0.5,0.5)$, $w(2)=(0,0.5,0)$, $w(3)=(-0.5,0,0)$, which misreads one example, $(1,1)$.
Show solution
A table line per example keeps the three updates apart.
n = 0
$$v=0\ \Rightarrow\ \hat y=0\neq1$$
The field of the zero vector is $0$, read as class 0: a missed 1.
$$w(1)=0+0.5\,(1,1,1)=(0.5,\,0.5,\,0.5)$$
Add half the input.
n = 1
$$v=0.5+0.5=1>0\ \Rightarrow\ \hat y=1\neq0$$
The example with label 0 is called 1: a false 1.
$$w(2)=(0.5,0.5,0.5)-0.5\,(1,0,1)=(0,\,0.5,\,0)$$
Subtract half the input.
n = 2
$$v=0+0.5=0.5>0\ \Rightarrow\ \hat y=1\neq0$$
Another false 1.
$$w(3)=(0,0.5,0)-0.5\,(1,1,0)=(-0.5,\,0,\,0)$$
Subtract half the input again.
Test w(3)
$$v=-0.5\ \text{for every input}\ \Rightarrow\ \hat y=0,\,0,\,0$$
Only $(1,1)$, with label 1, is misread.
Answer $$\boxed{\begin{aligned}&w(3)=(-0.5,\ 0,\ 0)\\ &\text{one example misclassified}\end{aligned}}$$
Check
Each update changed the field on its own example by $\pm\eta\lVert x\rVert^2$: $+1.5$, $-1$, $-1$, for example $0\to1.5$ at $n=0$.
Three updates in one pass are normal early on; the pass must be repeated until a clean one.
2§08.2 — one set that separates and one that cannot
Two small data sets are given. For each one, decide whether a single perceptron can classify every point correctly.
Find
(a) Give weights $(w_0,w_1,w_2)$ that separate set 1, and check all four points.
(b) Prove that set 2 is not linearly separable.
Given
set 1 (NAND): $y=0$ only at $(1,1)$, and $y=1$ at $(0,0),(0,1),(1,0)$
set 2: class 1 at $(0,0)$ and $(2,2)$; class 0 at $(1,1)$ and $(3,3)$
Hint 1/4
For set 1, look for a line that cuts off the corner $(1,1)$; for set 2, notice where all four points lie.
Hint 2/4
A perceptron's field is affine: along the line $x=(t,t)$ it is $v(t)=w_0+(w_1+w_2)\,t$, so $v(1)=\tfrac12\big(v(0)+v(2)\big)$.
Hint 3/4
Set 1: try $w=(1.5,-1,-1)$ on $(0,0), \allowbreak (0,1), \allowbreak (1,0), \allowbreak (1,1)$. Set 2: class 1 needs $v(0)>0$ and $v(2)>0$, class 0 needs $v(1)\le0$.
Hint 4/4
Set 1 is separated by $(1.5,-1,-1)$; set 2 would need $v(1)=\tfrac12\big(v(0)+v(2)\big)>0$ and $v(1)\le0$ at once.
Show solution
A picture finds the cut for set 1; for set 2 the points are collinear, so the field along that line is a straight function of one variable.
Set 1
$$v=1.5-x_1-x_2:\ \ 1.5,\ 0.5,\ 0.5,\ -0.5$$
At $(0,0), \allowbreak (0,1), \allowbreak (1,0), \allowbreak (1,1)$: positive exactly where $y=1$.
An affine function takes the average value at the midpoint.
$$\begin{aligned}&v(0)>0,\ v(2)>0\ \Rightarrow\ v(1)>0\\ &\text{but class 0 needs }v(1)\le0\end{aligned}$$
Contradiction: no weights exist.
Answer $$\boxed{\begin{aligned}&\text{set 1: }w=(1.5,-1,-1)\\ &\text{set 2: not separable}\end{aligned}}$$
Check
Picture check for set 2: along $x_1=x_2$ the labels read $1,0,1,0$, and a single cut on a line can change the label only once.
Collinear points with alternating labels can never be separated; averaging the field over two points is a quick proof.
3§08.3 — rewiring the output for 'equal'
The XOR network of this section has hidden neurons $h_1=\varphi(x_1-x_2-0.5)$ and $h_2=\varphi(x_2-x_1-0.5)$. Keep them and change only the output neuron $\hat y=\varphi(a_0+a_1h_1+a_2h_2)$.
Find
(a) Find output weights $(a_0,a_1,a_2)$ that compute XNOR.
The probabilities add to $1.0000$, and subtracting $3$ from every field gives $(-2,0,-3)$ with the same shares.
Cross-entropy punishes confident mistakes hardest: a network sure of the wrong class scores worse than one that shrugs.
6§08.6 — a tanh hidden delta and one weight update
A hidden neuron $j$ in layer 1 uses $\varphi(v)=\tanh v$ and has field $v_j^{(1)}=0.5$. It feeds two output neurons through $w_{j1}^{(2)}=1.5$ and $w_{j2}^{(2)}=-2$, whose deltas are $0.2$ and $0.1$. One of its incoming weights is $w_{1j}^{(1)}=0.4$, from the input $x_1=3$.
Find
(a) Find $\delta_j^{(1)}$.
(b) Find $\partial e/\partial w_{1j}^{(1)}$ and the updated weight.
Size check: the tanh slope is at most $1$, so $\lvert\delta_j^{(1)}\rvert\le\lvert0.1\rvert$, and $0.0786$ fits.
The two outgoing paths nearly cancel here, which is why the delta is small even though both output deltas are not.
7§08.7 — three steps with momentum
A weight starts at $w=1$ with no previous change. Its gradient terms $\eta\,\delta_j^{(l)}x_i^{(l-1)}$ at three steps are $0.2$, $0.2$ and $-0.1$, and the momentum constant is $\alpha=0.9$.
Find
(a) Find the three changes and the weight after each step.
(b) Compare with plain SGD, and say whether the weight still rises at the third step.
Given
$w=1$, $\Delta w(-1)=0$, $\alpha=0.9$
gradient terms $0.2,\ 0.2,\ -0.1$
Hint 1/4
Track two things at every step: the change, which remembers the previous change, and the weight, which adds the change.
Hint 2/4
$\Delta w(n)=\alpha\,\Delta w(n-1)+\eta\,\delta_j^{(l)}(n)x_i^{(l-1)}(n)$ and $w\leftarrow w+\Delta w(n)$.
Hint 3/4
With $\alpha=0.9$: $\Delta w(0)=0.2$, $\Delta w(1)=0.9\cdot0.2+0.2$, $\Delta w(2)=0.9\,\Delta w(1)-0.1$, from $w=1$.
Hint 4/4
Changes $0.2,\,0.38,\,0.242$ and weights $1.2,\,1.58,\,1.822$; plain SGD gives $1.2,\,1.4,\,1.3$, so with momentum the weight still rises at step 3.
Show solution
The recursion is iterated directly; the plain run is the same with alpha equal to 0.
The entries add to $0$, as they must when both $y$ and $x^{(L)}$ add to $1$.
Softmax with cross-entropy: output delta equals target minus output; keep the slope factor only for squared error.
2§08.1 — how far one update moves a field
A perceptron misreads the augmented example $x=(1,\,2,\,2)$ with label $y=0$: its field is positive. It updates once with $\eta=0.5$.
Find(a) How does the field on this same example change?
Given
$x=(1,\,2,\,2)$ including $x_0=1$; $y=0$ but $\hat y=1$
$\eta=0.5$
Hint 1/4
Write the new field in terms of the old one.
Hint 2/4
A false 1 gives $w\leftarrow w-\eta x$, so $w_{\text{new}}^Tx=w^Tx-\eta\,x^Tx$.
Hint 3/4
Here $x^Tx=1+4+4$ and $\eta=0.5$.
Hint 4/4
The field drops by $0.5\cdot9=4.5$.
Show solution
The change does not depend on the current weights, so we compute it from x alone.
New field
$$(w-\eta x)^Tx=w^Tx-\eta\,x^Tx$$
Expand the product.
$$\eta\,x^Tx=0.5\,(1+4+4)=4.5$$
The squared length of the augmented input is 9.
Answer $$\boxed{\text{it drops by }4.5}$$
Check
Example: from $w=(0,1,1)$ the field is $4$ and after the update $w=(-0.5,0,0)$ gives $-0.5$, a drop of $4.5$.
Each update shifts its own example's field by exactly eta times the squared length of the input, bias entry included.
3§08.2 — find the first wrong step in a trace
A student runs the perceptron from $w(0)=(0,\,1,\,-1)$ with $\eta=1$ on three examples, in this order: $(2,1)$ with $y=1$, $(1,2)$ with $y=0$, $(0,0)$ with $y=1$. The student's four steps are listed below.
Find(a) Which step contains the first error?
Given
Step 1. $(2,1)$: $v=0+2-1=1>0$, $\hat y=1$, correct, no update.
Step 2. $(1,2)$: $v=0+1-2=-1$, $\hat y=0$, correct, no update.
Step 3. $(0,0)$: $v=0$, so $\hat y=1$, correct, no update.
Step 4. No update in the whole pass, so the rule has converged at $w=(0,1,-1)$.
Hint 1/4
Recompute each field and each call, one step at a time, with the step activation's rule for 0.
Hint 2/4
$\hat y=1$ only if $v>0$; a field of exactly $0$ gives $\hat y=0$.
Hint 3/4
Step 1 has $v=1$ with $y=1$, Step 2 has $v=-1$ with $y=0$, and Step 3 has $v=0$ with $y=1$.
Hint 4/4
Step 3 is wrong: $v=0$ gives $\hat y=0$, a missed 1, so $w$ becomes $(1,1,-1)$ and the pass is not clean.
Show solution
Recomputing each field is cheaper than judging the conclusion.
The corrected weights classify all three examples: $(2,1)\mapsto1$, $(1,2)\mapsto0$ with $v=0$, $(0,0)\mapsto1$.
When a trace declares convergence, recheck the steps where a field equals 0; that is where the class-0 convention bites.
4§08.5 — output layers for two tasks
Two networks share the same kind of hidden layers. One predicts a house's price in thousands of lira; the other sorts handwritten digits into the ten classes 0 to 9.
Find(a) Which output layers and losses fit the two tasks?
Given
task 1: one real number per example
task 2: one of ten unordered classes per example
Hint 1/4
Decide for each task what kind of object the network must output.
Hint 2/4
A real number needs an unbounded output and squared error; a class needs one probability per class and cross-entropy.
Hint 3/4
The price is one real number; the digit is one of ten classes with no order.
Hint 4/4
Price: one linear output with squared error; digits: ten softmax outputs with cross-entropy.
Show solution
The output layer must be able to produce the target, and the loss must compare like with like.
Price
$$f_w(x)=v^{(L)},\qquad l=\big(y-f_w(x)\big)^2$$
A linear output can take any value; squared error measures the miss.
Check against the lecture's rule of thumb: regression usually takes the identity output with one neuron, and classification with K classes takes K softmax outputs.
Choose the output activation from what the target is, then the loss that matches it.
D · interleaved 4 questions
1§08.5 — one yes/no example and a single unit
Logistic regression $\pi(x)=1/\big(1+e^{-(\beta_0+\beta_1x)}\big)$ can be read as one neuron with the logistic activation. Its parameters are $\beta_0=\beta_1=0$, and it sees one example $x=2$, $y=1$.
Find
(a) Find the gradient of the example's log-likelihood with respect to $(\beta_0,\beta_1)$.
(b) Take one SGD step on the cross-entropy with $\eta=0.1$, and compare it with one gradient ascent step on the log-likelihood.
Given
$\beta_0=\beta_1=0$; example $x=2$, $y=1$
log-likelihood of one example: $y\log\pi+(1-y)\log(1-\pi)$
$\eta=0.1$
Hint 1/4
Write the loss of this one example in terms of the field, then differentiate.
Hint 2/4
With $\pi=\sigma(\beta_0+\beta_1x)$: $\frac{\partial}{\partial(\beta_0,\beta_1)}\big[y\log\pi+(1-y)\log(1-\pi)\big]=(y-\pi)\,(1,\,x)$, and the cross-entropy is its negative.
Hint 3/4
Here $\pi=\sigma(0)=0.5$, $y=1$, $x=2$ and $\eta=0.1$.
Hint 4/4
The gradient is $(0.5,\,1)$; both steps give $(\beta_0,\beta_1)=(0.05,\,0.1)$.
Show solution
The cross-entropy is minus the log-likelihood, so we differentiate the log-likelihood once and use it twice.
After the step $\beta_0+\beta_1x=0.25$ and $\pi=0.5622$, closer to the label $1$.
A single logistic neuron trained by SGD on cross-entropy is logistic regression fitted by stochastic gradient ascent on its likelihood.
2§08.7 — a penalty on a single linear unit
A single neuron with the identity activation and no bias predicts $f_w(x)=wx$. It is trained on $N=4$ examples with $\sum_ix_i^2=10$ and $\sum_ix_iy_i=6$ by minimizing $J_{\text{aug}}(w)=\sum_i(y_i-wx_i)^2+\frac{\lambda}{N}w^2$ with $\lambda=8$.
Find
(a) Find the minimizer of $J_{\text{aug}}$.
(b) Which ridge penalty $\lambda_R$ gives the same estimate, and how does it compare with least squares?
Decide which of the two error columns can pick a model.
Hint 2/4
Choose by validation error; training error always prefers the most flexible model.
Hint 3/4
Validation MSE is $0.95,\, \allowbreak 0.52,\, \allowbreak 0.47,\, \allowbreak 0.88$ for $2,\,8,\,32,\,128$ neurons, and training MSE falls to $0.01$ at $128$.
Hint 4/4
Use $32$ neurons (validation $0.47$); at $128$ the network overfits, and weight decay with $\lambda$ chosen on validation data can help.
Show solution
Only the validation column measures performance on data the fit has not seen, so it is the one to minimize.
Sanity check: picking by training error would choose 128 neurons, the model with the worst validation error but one, which is exactly the mistake validation prevents.
Model size and weight decay are both flexibility knobs, and both are set by validation error, never by training error.
4§08.5 — four numbers and a random pick
At the current weights, the per-example gradients of a one-weight model on its four training examples are $2,\ -1,\ 3,\ 0$. SGD picks one example uniformly at random.
Find
(a) Find $\nabla J$, $E[g_I]$ and $\operatorname{Var}(g_I)$.
(b) A mini-batch averages two examples drawn independently, with replacement. What is the variance of its gradient?
Given
per-example gradients $g_i=2,\ -1,\ 3,\ 0$
$J=\sum_il_i$, so $\nabla J=\sum_ig_i$
$I$ uniform on $\{1,2,3,4\}$
Hint 1/4
Treat the picked gradient as a random variable with four equally likely values.
Hint 2/4
$E[g_I]=\frac14\sum_ig_i$, $\operatorname{Var}(g_I)=E[g_I^2]-(E[g_I])^2$, and the average of two independent draws has half the variance.
Hint 3/4
$\sum_ig_i=4$ and $\sum_ig_i^2=4+1+9+0=14$.
Hint 4/4
$\nabla J=4$, $E[g_I]=1$, $\operatorname{Var}(g_I)=3.5-1=2.5$, and the mini-batch variance is $1.25$.
Show solution
Expectation and variance of a uniform pick follow from the four values directly.
$0\le\alpha<1$; a steady gradient step $g$ grows to $g/(1-\alpha)$
Check yourself
Close the page and write down from memory:
the perceptron rule, and what it does on a correct answer, a missed 1 and a false 1;
when the rule is guaranteed to stop, and why XOR is not linearly separable;
the forward pass in the layer notation;
the three backpropagation formulas and the SGD update;
the weight decay factor and the momentum recursion.
Then reopen the page and compare; whatever is missing is your reread list.
Run the perceptron rule by hand on a few points, with the bias and the $v=0$ convention right?
c-perceptron
Decide whether a small data set is linearly separable, and say what the convergence theorem does and does not promise?
c-convergence
Prove that XOR is not linearly separable, and wire a hidden layer of step neurons that computes it?
c-xor
Compute a forward pass through a 2-2-1 network, with the indices of $w_{ij}^{(l)}$ the right way round?
c-forward
Pick the output layer and loss for a regression and a classification task, and write the batch, SGD and mini-batch updates?
c-loss-gd
Compute the output and hidden deltas and one SGD update for a small network, and check a gradient by finite differences?
c-backprop
Apply one weight decay step and three momentum steps, and explain what each changes?
c-regularize
Glossary (24 terms)
perceptronalgılayıcı
A single neuron with a step activation: it outputs 1 when the weighted sum of its inputs plus a bias is positive, 0 otherwise, and learns its weights from its mistakes.
linearly separabledoğrusal ayrılabilir
A labelled data set is linearly separable when some hyperplane $w^Tx=k$ has every class 1 point strictly on one side and every class 0 point on the other side or on it.
perceptron learning rule
The online update $w(n+1)=w(n)+\eta\,[y(n)-\hat y(n)]\,x(n)$, which changes the weights only when an example is misclassified.
learning rateöğrenme oranı
The step size $\eta>0$ that multiplies every update, in the perceptron rule and in gradient descent.
perceptron convergence theorem
If the classes are linearly separable, the perceptron learning rule makes finitely many updates from any starting weights and then stops changing.
margin
The smallest distance from a separating hyperplane to the data points; a small margin allows many perceptron updates.
XORözel veya
The rule on two binary inputs that is 1 exactly when the inputs differ; the standard example of a data set that is not linearly separable.
hidden layergizli katman
A layer of neurons between the input and the output of a network; its outputs are new features for the next layer.
çok katmanlı algılayıcı
A network of neurons arranged in layers, with at least one hidden layer between the inputs and the outputs.
ileri beslemeli sinir ağı
A layered network in which every neuron of a layer feeds every neuron of the next layer, and no connection goes backward, skips a layer or stays inside a layer.
induced local field
The weighted sum $v_j^{(l)}=\sum_iw_{ij}^{(l)}x_i^{(l-1)}$, bias included, that a neuron passes to its .
activation functionaktivasyon fonksiyonu
The function $\varphi$ that turns a neuron's field into its output, such as the step, the logistic, tanh, softplus or ReLU.
ReLUdoğrultulmuş doğrusal birim
The rectified linear unit $\max(0,v)$: zero for negative fields and the field itself for positive ones.
softplus
The smooth activation $\ln(1+e^v)$; it stays within $\ln2$ of the ReLU, and its derivative is the logistic function.
softmax
The output layer $e^{v_k}/\sum_je^{v_j}$ that turns $K$ fields into $K$ probabilities adding to 1.
A class label written as a vector with a 1 at the position of the true class and 0 elsewhere.
cross-entropyçapraz entropi
The classification loss $-\sum_ky_k\log f_{w,k}(x)$: minus the log of the probability the network gives to the true class.
batch gradient descenttoplu gradyan inişi
Gradient descent that uses the gradient of the loss summed over the whole training set at every step.
stokastik gradyan inişi
Gradient descent that uses the gradient of one randomly chosen example's loss at every step; on average it points along the full gradient.
mini-batch gradient descent
Gradient descent that averages the gradient over a small random batch of examples at every step.
forward propagationileri yayılım
Computing every field and output of a network layer by layer, from the input to the output.
backpropagationgeri yayılım
Computing the gradient of every weight for one example by passing deltas from the output layer back toward the input with the chain rule.
weight decayağırlık sönümü
Adding $\frac{\lambda}{N}w^Tw$ to the loss, which shrinks every weight by a constant factor before each gradient step.
momentummomentum
Adding a fraction $\alpha$ of the previous weight change to the current gradient step, which speeds up steady descent and damps oscillations.
What comes next
§09 · PCA, ICA and blind source separation
Here every example came with a label, and the network learned to reproduce it. Next the labels are gone, and the task is to find the directions and sources hidden in the data themselves.
Sources
textbookT. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer (course textbook) The weekly line names no chapter of the book, so no section numbers are cited here.
course materialEEE 485 lecture slides and lecture notes, chapter 8: Perceptron, neural networks and backpropagation Scope, order of topics and notation (x(n), w(n), η, the step activation, d^(l), w_ij^(l), v_j^(l), x_j^(l), δ_j^(l), J_aug, the momentum update) follow these materials; all explanations, data, figures and exercises here are original.
course materialEEE 485 syllabus page on STARS, Fall 2026-27, printed 21 September 2026 Assessment weights, the weekly topic list and the recommended books.
textbookS. Haykin, Neural Networks and Learning Machines, 3rd edition The lecture's figure of a feedforward network with two hidden layers comes from it.
standard resultA Neural Network Playground (TensorFlow Playground)The interactive demo the lecture points to: train small networks in the browser and watch the decision regions change with the activation, the size and the regularization.
standard resultThe chain rule, geometric series and the Cauchy-Schwarz inequality Standard results used in the derivations. Every number and figure on this page was computed for it.