Problems

STATEMENT

A perceptron’s parameters are given. Write the equation of its decision boundary, classify four points, and compute each point’s signed distance from the boundary.

GIVEN

$\vec{w} = \begin{bmatrix} 2 \\ -1 \end{bmatrix}, \qquad b = -1$

and the four points

$A = (2, 1), \quad B = (0, 1), \quad C = (1, -1), \quad D = (0, 3)$

FIND

The boundary as an equation in $x_1, x_2$; the predicted label of each point; and each signed distance, a scalar in the same units as the coordinates.

STRATEGY

Compute the raw score $s = \langle \vec{w}, \vec{x}\rangle + b$ once per point. The sign of $s$ gives the class and $s/\lVert\vec{w}\rVert$ gives the distance, so one quantity answers both questions.

SOLUTION

Step 1 — the boundary. By Definition 2 the boundary is the set where the score is zero:

$2x_1 - x_2 - 1 = 0 \qquad\text{equivalently}\qquad x_2 = 2x_1 - 1$

A line of slope $2$ through $(0.5, 0)$. Note that $\vec{w} = (2, -1)$ is perpendicular to it: the direction along the line is $(1, 2)$, and $\langle (2,-1),(1,2)\rangle = 2 - 2 = 0$. The weight vector is always the normal to the boundary. That single fact makes every later step geometric rather than algebraic.

Step 2 — the norm. Needed once, for all four points:

$\lVert \vec{w}\rVert = \sqrt{2^2 + (-1)^2} = \sqrt{5} = 2.2361$

Step 3 — the scores.

Step 4 — labels and distances. Divide each score by $\sqrt5$ (Projections and orthogonality · 0.LA.05):

Check — sanity

A point on the boundary has distance zero. Take $x = (0.5, 0)$, which satisfies $x_2 = 2x_1 - 1$. Its score is $(2)(0.5) - 0 - 1 = 0$, so its distance is $0$. The formula agrees with the definition it came from.

Rescaling the parameters changes nothing geometric. Double both: $\vec{w} = (4,-2)$, $b = -2$. Then $s_A = 4$ and $\lVert\vec{w}\rVert = 2\sqrt5$, so the distance is $4/(2\sqrt5) = 0.8944$ — unchanged. The scores doubled and the distances did not, which is exactly the difference between the functional margin (Definition 4) and the geometric one (Definition 5).

Moving a point along the boundary direction changes nothing. Shift $A$ by $(1,2)$, the direction along the line, to get $(3,3)$: its score is $6 - 3 - 1 = 2$, identical. Moving perpendicular to $\vec{w}$ cannot change the score, because $\vec{w}$ is what the score measures against.

STATEMENT

Run the perceptron learning rule on a separable four-point set until it stops changing. Show every weight update and every margin you tested, including the ones that produced no change.

GIVEN

Four labelled points, presented cyclically in this order:

Initialise $\vec{w} = (0,0)$ and $b = 0$. The rule (Definition 7): if $y(\langle\vec{w},\vec{x}\rangle + b) \le 0$, set $\vec{w} \leftarrow \vec{w} + y\vec{x}$ and $b \leftarrow b + y$; otherwise do nothing.

FIND

The sequence of parameter states, the total number of updates, and the final $(\vec{w}, b)$.

STRATEGY

Test the margin of every point in order, updating immediately when one is non-positive rather than at the end of a pass. Convergence is declared when a whole pass produces no update — which is the only stopping condition the rule has.

SOLUTION

Epoch 1.

Point $(1,1)$, $y=+1$. Margin $= 1\cdot(0 + 0 + 0) = 0$. Non-positive, so this counts as a mistake even though nothing is strictly misclassified. Update:

$\vec{w} = (0,0) + (+1)(1,1) = (1,1), \qquad b = 0 + 1 = 1$

Point $(2,0)$, $y=+1$. Margin $= 1\cdot\big((1)(2) + (1)(0) + 1\big) = 3 > 0$. Correct — no change.

Point $(-1,0)$, $y=-1$. Margin $= (-1)\cdot\big((1)(-1) + (1)(0) + 1\big) = (-1)(0) = 0$. Non-positive again. Update:

$\vec{w} = (1,1) + (-1)(-1,0) = (1+1,\; 1+0) = (2,1), \qquad b = 1 - 1 = 0$

Point $(0,-1)$, $y=-1$. Margin $= (-1)\cdot\big((2)(0) + (1)(-1) + 0\big) = (-1)(-1) = 1 > 0$. Correct.

Epoch 2. With $\vec{w} = (2,1)$, $b = 0$:

A complete pass with no update. The rule has converged.

Reading the updates. Both updates came from a margin of exactly zero, not from a confidently wrong prediction. The rule is not waiting to be badly wrong; it moves whenever a point is not strictly on the right side. That choice is what makes the zero-initialised first step happen at all.

Check — sanity

Every point is now correctly classified. The four margins in epoch 2 are $+3, +4, +2, +1$, all strictly positive. That is the definition of having separated the data, checked directly rather than inferred from the algorithm stopping.

The bound is respected. Here $R = \max\lVert\vec{x}_i\rVert = 2$ (from $(2,0)$). The final geometric margin is $\min_i y_i s_i / \lVert\vec{w}\rVert = 1/\sqrt5 = 0.4472$. Novikoff’s bound (I.2.4) gives $(R/\gamma)^2 = (2/0.4472)^2 = 20$. Two updates is comfortably under twenty, as a valid upper bound requires.

Each update moves toward the point that caused it. After the first update $\vec{w} = (1,1)$, which points at $(1,1)$ — the very example that triggered it. That is what $\vec{w} \leftarrow \vec{w} + y\vec{x}$ means geometrically, and it is the whole intuition of the rule.

STATEMENT

Prove Novikoff’s theorem: on separable data the perceptron makes at most $(R/\gamma)^2$ mistakes. State every assumption where it is used, and say at the end which step each assumption was load-bearing for.

GIVEN

A dataset $\{(\vec{x}_i, y_i)\}$ with $y_i \in \{-1,+1\}$ and $\lVert\vec{x}_i\rVert \le R$ for all $i$. Assume separability: there exists a unit vector $\vec{u}$, $\lVert\vec{u}\rVert = 1$, with

$y_i \langle \vec{u}, \vec{x}_i \rangle \ge \gamma > 0 \quad\text{for every } i$

The perceptron starts at $\vec{w}_0 = \vec{0}$ and updates $\vec{w}_{k+1} = \vec{w}_k + y_i\vec{x}_i$ on the $k$-th mistake. The bias is absorbed by appending a constant $1$ to every $\vec{x}_i$, so only $\vec{w}$ appears.

FIND

An upper bound on $k$, the total number of updates, in terms of $R$ and $\gamma$ only.

STRATEGY

Track one scalar from below and another from above. The inner product $\langle\vec{u},\vec{w}_k\rangle$ can only grow, and $\lVert\vec{w}_k\rVert^2$ cannot grow fast. Cauchy–Schwarz then traps $k$ between them. The whole proof is the observation that a quantity growing linearly cannot stay below one growing as a square root forever.

SOLUTION

Step 1 — the lower bound on the projection. Suppose the $k$-th mistake is on example $(\vec{x}_i, y_i)$. Take the inner product of the update with $\vec{u}$, using linearity:

By the separability assumption the last term is at least $\gamma$. So each mistake advances the projection by at least $\gamma$:

$\langle \vec{u}, \vec{w}_{k} \rangle \ \ge\ \langle \vec{u}, \vec{w}_{k-1} \rangle + \gamma$

Starting from $\vec{w}_0 = \vec{0}$, whose projection is $0$, induction over $k$ mistakes gives

\langle \vec{u}, \vec{w}_{k} \rangle \ \ge\ k\gamma \tag{lower}

Where the assumption entered: separability, and only there.

Step 2 — the upper bound on the norm. Expand the squared norm of the same update:

Now use the two facts available. First, the update happened because the example was a mistake, so its margin was non-positive: $y_i\langle\vec{w}_{k-1},\vec{x}_i\rangle \le 0$, and the cross term can only help. Second, $y_i^2 = 1$ and $\lVert\vec{x}_i\rVert^2 \le R^2$. Therefore

$\lVert \vec{w}_{k}\rVert^2 \ \le\ \lVert \vec{w}_{k-1}\rVert^2 + R^2$

and by induction from $\lVert\vec{w}_0\rVert = 0$:

Where the assumptions entered: the bounded radius, and — crucially — the fact that updates occur only on mistakes. Take that away and the cross term is unsigned, and the bound fails.

Step 3 — squeeze with Cauchy–Schwarz. For any vectors, $\langle \vec{u}, \vec{w}\rangle \le \lVert\vec{u}\rVert\,\lVert\vec{w}\rVert$ (Inner products, norms and cosine similarity · 0.LA.03), and $\lVert\vec{u}\rVert = 1$. Chaining the two bounds:

$k\gamma \ \overset{\text{(lower)}}{\le}\ \langle \vec{u}, \vec{w}_k\rangle \ \le\ \lVert\vec{w}_k\rVert \ \overset{\text{(upper)}}{\le}\ R\sqrt{k}$

Step 4 — solve for $k$. From $k\gamma \le R\sqrt{k}$, and since $k > 0$, divide by $\sqrt{k}$:

$\sqrt{k}\,\gamma \le R \quad\Longrightarrow\quad \sqrt{k} \le \frac{R}{\gamma} \quad\Longrightarrow\quad k \le \left(\frac{R}{\gamma}\right)^{2}$

$\blacksquare$

What made it work. The projection grows linearly in the number of mistakes, while the norm grows only as $\sqrt{k}$. A vector cannot have its shadow on a unit direction outrun its own length, so the two rates must collide, and the collision point is the bound.

Check — sanity

Dimensional consistency. $R$ and $\gamma$ are both lengths — $R$ a norm, $\gamma$ a projection onto a unit vector — so $R/\gamma$ is dimensionless and so is its square. A bound on a count must be dimensionless, and this one is.

It reproduces the run of I.2.B02. There $R = 2$ and $\gamma = 0.4472$, giving $k \le 20$. The observed count was $2$. A valid upper bound must be at least the truth, and $2 \le 20$.

Both monotonicities are right. Larger $R$ (data further from the origin) raises the bound; larger $\gamma$ (an easier separation) lowers it. If the inequality had come out the other way round in either variable, a sign was lost.

The degenerate case behaves. If the data is already separated at the start, no mistake occurs, $k = 0$, and $0 \le (R/\gamma)^2$ holds for any positive right-hand side.

STATEMENT

Prove that no perceptron computes XOR on $\{0,1\}^2$, by writing the four requirements as inequalities in $(w_1, w_2, b)$ and showing they are jointly inconsistent.

GIVEN

The XOR function:

A perceptron predicts $1$ when $w_1x_1 + w_2x_2 + b > 0$ and $0$ otherwise.

FIND

Either parameters that work, or a proof that none exist.

STRATEGY

Substitute each of the four inputs to turn the truth table into four linear inequalities. Then add pairs of them to derive a contradiction — the point being that this is ordinary algebra, not an appeal to geometry or intuition.

SOLUTION

Step 1 — write the four requirements. Substituting each row:

Step 2 — add (2) and (3). Adding two strict inequalities of the same direction is legal and preserves strictness:

$w_1 + w_2 + 2b > 0 \qquad (5)$

Step 3 — combine with (4). From (4), $w_1 + w_2 \le -b$. Substituting that upper bound into (5):

$0 < w_1 + w_2 + 2b \le (-b) + 2b = b$

so $b > 0$.

Step 4 — the contradiction. Step 3 concludes $b > 0$. Requirement (1) says $b \le 0$. Both cannot hold. Therefore no $(w_1, w_2, b)$ satisfies all four, and no perceptron computes XOR. $\blacksquare$

Why this is stronger than “training fails”. Nothing here mentions an algorithm, an initialisation, a learning rate, or a quantity of data. The inequalities describe every perceptron that could ever exist. The failure is a property of the hypothesis class $\mathcal{F}$ of Definition 3 in Chapter I.1 — XOR is simply not in it.

The geometric reading. The two positive points $(0,1)$ and $(1,0)$ lie on one diagonal of the unit square; the two negatives $(0,0)$ and $(1,1)$ lie on the other. The diagonals cross. Any straight line separating one diagonal’s endpoints must pass between them, and therefore also separates the other diagonal’s endpoints — putting one negative on each side. The algebra above is that picture with the geometry removed.

Check — sanity

The proposed three-dimensional solution works. With the extra feature $x_3 = x_1x_2$ and $(1, 1, -2, -0.5)$:

All four correct. So the impossibility really is about the representation and not about XOR being hard.

Three of the four are satisfiable. Drop requirement (4) and $(w_1,w_2,b) = (1,1,-0.5)$ satisfies (1), (2), (3). This confirms the contradiction genuinely needs all four rows, rather than arising from a slip in transcribing one of them.

AND and OR are fine. AND: $(1,1,-1.5)$. OR: $(1,1,-0.5)$. So the perceptron is not simply weak — it computes fourteen of the sixteen Boolean functions of two variables. XOR and its negation are the exceptions.

STATEMENT

Analyse the mistake bound $(R/\gamma)^2$ as $\gamma \to 0^{+}$ at fixed $R$. Tabulate it, state the limit, and say precisely what the theorem still guarantees for near-separable data — and what it stops guaranteeing.

GIVEN

Novikoff’s bound $k \le (R/\gamma)^2$ from I.2.B03, with the radius fixed at $R = 1$ and the geometric margin $\gamma$ shrinking.

FIND

The bound at $\gamma \in \{0.5,\ 0.1,\ 0.01,\ 10^{-3},\ 10^{-6}\}$; the limit as $\gamma \to 0^{+}$; and the status of the guarantee at $\gamma = 0$ exactly.

STRATEGY

Evaluate, then take the limit, then separate two cases that look continuous but are not: $\gamma$ small and $\gamma$ zero.

SOLUTION

Step 1 — tabulate. With $R = 1$ the bound is simply $\gamma^{-2}$.

Step 2 — the rate. The bound is quadratic in $1/\gamma$, so halving the margin quadruples the work:

$\frac{(R/(\gamma/2))^2}{(R/\gamma)^2} = 4$

This is worth stating as a rule of thumb, because it is the reason near-separable problems are qualitatively different from comfortably separable ones rather than merely slower.

Step 3 — the limit.

$\lim_{\gamma \to 0^{+}} \left(\frac{R}{\gamma}\right)^{2} = +\infty$

Step 4 — the two cases, which are not the same.

Case $\gamma > 0$, however small. The data is separable. The theorem applies and the algorithm does terminate, in finitely many updates. The guarantee is intact — it has merely become useless in practice, because a finite number can exceed any budget anyone has.

Case $\gamma = 0$ exactly. There is no separating $\vec{u}$ with positive margin. Step 1 of the proof in I.2.B03 has no lower bound to offer, the squeeze never closes, and the conclusion is not weakened but withdrawn. The algorithm does not terminate at all.

The distinction matters because the two cases are indistinguishable from outside. A run that has made $10^6$ updates might be at $\gamma = 10^{-3}$ and one update from finishing, or at $\gamma = 0$ and never finishing. The perceptron has no test that separates them, and no amount of patience resolves it.

Check — sanity

The tabulated values satisfy the quadratic rule. From $\gamma = 0.1$ to $\gamma = 0.01$ the margin fell by $10\times$ and the bound rose by $100\times$, as $\gamma^{-2}$ requires.

The bound is scale-invariant in the right way. Doubling every coordinate doubles both $R$ and $\gamma$, leaving $R/\gamma$ — and therefore the bound — unchanged. A mistake count must not depend on the units the data is measured in, and it does not.

It matches the worked run. I.2.B02 had $R = 2$, $\gamma = 0.4472$, bound $20$, actual $2$. Consistent.

STATEMENT

Count the parameters and the forward FLOPs of a single perceptron over $d$ inputs, then extend to a one-vs-rest bank of $K$ perceptrons. Evaluate at two realistic sizes.

GIVEN

A perceptron $\hat{y} = \mathrm{sign}(\langle\vec{w},\vec{x}\rangle + b)$ with $\vec{w} \in \R^{d}$. Count a multiply and an add as one FLOP each; ignore the sign, which is one comparison.

FIND

Parameters and FLOPs as functions of $d$; then of $d$ and $K$; then numbers at $(d, K) = (784, 10)$ and $(4096, 1000)$.

STRATEGY

Count the arithmetic in the definition literally rather than recalling a rule. The inner product is the only expensive part, and everything else is $O(1)$.

SOLUTION

Step 1 — one perceptron, parameters. The weight vector holds $d$ numbers and the bias holds one:

$N_{\text{params}} = d + 1$

Step 2 — one perceptron, FLOPs. The inner product $\sum_{j=1}^{d} w_j x_j$ needs $d$ multiplications and $d-1$ additions. Adding the bias is one more addition, bringing the additions to $d$. Total:

$N_{\text{FLOPs}} = d + d = 2d$

The convenient way to remember this: one multiply–add per parameter, and there are $d$ weights doing real work. That rule of thumb survives all the way to Chapter II.8, where the $2N$ per token in $C \approx 6ND$ is the same count.

Step 3 — a bank of $K$. One-vs-rest trains $K$ independent perceptrons, one per class, each over the same $d$ inputs. Nothing is shared:

$N_{\text{params}} = K(d+1), \qquad N_{\text{FLOPs}} = 2dK$

Equivalently the bank is one matrix $\mat{W} \in \R^{d\times K}$ and one bias row, so the forward pass is a single $(1\times d)(d\times K)$ product — the same object as a linear layer in Chapter I.5, arrived at from the other direction.

Step 4 — evaluate.

Check — sanity

FLOPs are about twice the parameters. $8{,}192{,}000 / 4{,}097{,}000 = 1.9995$, approaching $2$ as $d$ grows because the bias becomes negligible. If your ratio were near $1$ or near $4$, a multiply or an add went missing.

Both scale linearly in each variable separately. Ten times the classes gives ten times the cost; ten times the input width gives ten times the cost. There is no interaction term, because a one-vs-rest bank shares nothing between classes.

The $d = 784$, $K = 10$ figure is checkable against a known object. That is MNIST with a linear classifier, and $7{,}850$ is the familiar parameter count for exactly that model. Landing on a number that appears in the literature is weak evidence, but it is evidence.

STATEMENT

The perceptron rule looks like a hand-made heuristic. Show that it is exactly one step of subgradient descent, with learning rate $1$, on a specific loss — and identify that loss.

GIVEN

The perceptron loss for one example, sometimes called the hinge-at-zero loss:

$\ell(\vec{w}, b) = \max\big(0,\; -y(\langle\vec{w},\vec{x}\rangle + b)\big)$

and the update rule of Definition 7: on a mistake, $\vec{w} \leftarrow \vec{w} + y\vec{x}$ and $b \leftarrow b + y$.

FIND

The subgradient of $\ell$ with respect to $\vec{w}$ and $b$ in both regimes, and the resulting descent step at $\eta = 1$.

STRATEGY

Split on the sign of the margin, differentiate each branch, and compare the resulting step with the rule. The function is not differentiable at the join, which is why “subgradient” rather than “gradient” — and that is a feature worth naming rather than glossing.

SOLUTION

Step 1 — name the inner quantity. Let $m = y(\langle\vec{w},\vec{x}\rangle + b)$ be the functional margin, so $\ell = \max(0, -m)$.

Step 2 — the case $m > 0$ (correct). Then $-m < 0$, the maximum is achieved by the constant $0$, and $\ell$ is identically zero in a neighbourhood. A locally constant function has zero derivative:

$\nabla_{\vec{w}}\,\ell = \vec{0}, \qquad \partial \ell/\partial b = 0$

The descent step changes nothing. This matches the rule’s “otherwise do nothing” exactly.

Step 3 — the case $m < 0$ (wrong). Then $\ell = -m = -y(\langle\vec{w},\vec{x}\rangle + b)$, which is affine in the parameters and so differentiable. Using $\nabla_{\vec{w}}\langle\vec{w},\vec{x}\rangle = \vec{x}$ (The derivative of a linear map · 0.MC.04):

Step 4 — take a descent step. Gradient descent moves against the gradient (Gradient descent · 0.OP.02), with $\eta = 1$:

These are the update rule, term for term.

Step 5 — the join at $m = 0$. At exactly zero the function has a kink and no derivative exists. The subdifferential is the whole interval between the two one-sided slopes, $\{\,-\alpha\, y\vec{x} : \alpha \in [0,1]\,\}$. Any element is a legal subgradient step; the perceptron picks $\alpha = 1$, which is why it updates on $m \le 0$ rather than $m < 0$. That convention, which looked arbitrary in I.2.B02, is a choice of subgradient.

Check — sanity

The loss is zero exactly when the rule is idle. $\ell = 0 \iff m \ge 0 \iff$ no update. The two descriptions of “nothing to do here” agree, which they must if one is to be a restatement of the other.

The loss is convex. It is the maximum of two affine functions of the parameters, and a pointwise maximum of convex functions is convex (Convexity · 0.OP.01). So the perceptron is minimising a convex objective — and yet it still fails to terminate on XOR, because the minimum of that objective is not zero there. Convexity buys a well-posed problem, not a useful answer.

The learning rate is genuinely irrelevant here. Any $\eta > 0$ gives $\vec{w} \leftarrow \vec{w} + \eta y\vec{x}$, which rescales $\vec{w}$ but not the sign of any score when starting from $\vec{0}$ — so the sequence of predictions is identical. This is unique to the perceptron and stops being true the moment Chapter I.4 introduces a loss with curvature.