Linear Classification · Machine Learning

01 · Motivation

Why regression is not enough

In Chapter 02 we predicted continuous numbers — prices, temperatures, blood pressure — where the output could be any real number and Gaussian noise made least squares the natural fit. But a huge slice of machine learning asks a different question: which bucket does this input belong to? Not “how much” but “which one.”

That is classification. And it turns out that pointing the linear-regression machinery straight at the problem — fitting a line to 0/1 labels — fails in two quietly catastrophic ways. This chapter shows what goes wrong and introduces the principled alternatives that replaced it.

Medical diagnosis

Given a tumour’s measurements, is it malignant or benign? The answer is a label, not a number — a regression output of $1.7$ or $-0.3$ has no medical meaning.

Spam detection

A message is spam or not. You could set spam $=1$ , ham $=0$ , fit a line and threshold at $0.5$ — but points deep in the “very spammy” regime drag the threshold the wrong way.

Digit recognition

A handwritten digit belongs to exactly one of ten classes. The output must express competition between classes, not an unconstrained real number.

The two failure modes of naive regression

Suppose you have binary labels $t_n \in \{0,1\}$ , fit a least-squares line $\hat y(\mathbf{x}) = \mathbf{w}^\top\mathbf{x} + w_0$ , and predict class $\mathcal{C}_1$ whenever $\hat y > 0.5$ . This works in easy cases — so where does it break?

Failure 1 — outlier sensitivity

A point that is clearly class 1 but far from the boundary (predicted value $3.8$ ) incurs a large residual $(3.8-1)^2 = 7.84$ . Least squares reduces it by rotating the boundary toward the outlier, misclassifying perfectly sensible points nearby.

Failure 2 — wrong noise model

Least squares is the MLE under Gaussian noise (Ch. 02). But $t_n \in \{0,1\}$ is Bernoulli, not Gaussian. Maximising the wrong likelihood gives biased estimates and outputs outside $[0,1]$ that cannot be read as probabilities.

key

The core insight of this chapter

Classification needs a model that respects the discrete, competitive nature of class labels. The fix is a nonlinear activation function — a “squashing” layer that maps any real-valued score to a valid class probability. Everything else in the chapter flows from this one design decision.

Every linear classifier here belongs to one of three families. Understanding each family’s philosophy matters more than memorising any single formula.

① Discriminant function

Learns a mapping $\mathbf{x} \mapsto \text{class}$ directly, without modelling probabilities. The decision boundary is the primary object. Examples: linear discriminant, perceptron, SVM.

② Probabilistic discriminative

Models $p(\mathcal{C}_k \mid \mathbf{x})$ directly — calibrated probabilities without modelling the data distribution. Examples: logistic regression, softmax regression.

③ Probabilistic generative

Models the joint $p(\mathbf{x}, \mathcal{C}_k) = p(\mathbf{x}\mid\mathcal{C}_k)\,p(\mathcal{C}_k)$ and derives the posterior via Bayes. Can generate new data. Examples: Gaussian discriminant analysis, Naive Bayes.

!

Chapter scope — and a recurring exam question

This chapter covers approaches 1 and 2 in depth; generative models (approach 3) appear in a later chapter on Gaussian classifiers. The discriminative vs. generative distinction is asked almost every year — know what each models, how many parameters it needs, and whether it yields calibrated probabilities.

02 · Intuition

Decision boundaries as fences in feature space

Scatter two classes of points on a plane. Your job is to draw a fence separating them as cleanly as possible. A linear classifier draws a straight fence — a line in 2-D, a plane in 3-D, a hyperplane in higher dimensions.

The fence is the set where $y(\mathbf{x}) = \mathbf{w}^\top\mathbf{x} + w_0 = 0$ . Points on one side give $y > 0$ (class 1); points on the other give $y < 0$ (class 2). Two knobs control it:

$\mathbf{w}$ — the weight vector. It points perpendicular to the fence, toward increasing $y$ . Rotating $\mathbf{w}$ rotates the fence.
$w_0$ — the bias. It shifts the fence toward or away from the origin without rotating it.

tip

The ruler and its position

$\mathbf{w}$ is like the angle of a ruler — which way the fence faces. $w_0$ is like the ruler’s position on the desk — where the fence sits. Two completely independent controls: one for orientation, one for location. That separation drives the geometry in §3.

Why the activation must be nonlinear

The fence $y(\mathbf{x}) = 0$ is perfectly linear in $\mathbf{x}$ . But we wrap that score in a nonlinear activation $\hat y = f\bigl(y(\mathbf{x})\bigr)$ — why? Because we want the output to be a probability, bounded in $[0,1]$ , not an arbitrary real number. The logistic sigmoid is the standard choice:

\sigma(a) = \frac{1}{1 + e^{-a}}, \qquad \sigma(a)\to 1 \;(a\to+\infty), \quad \sigma(a)\to 0 \;(a\to-\infty), \quad \sigma(0) = 0.5.

This is the essence of a generalised linear model: the prediction is a nonlinear function of a linear combination of the inputs. The boundary $\sigma(\mathbf{w}^\top\mathbf{x}) = 0.5$ is still a linear hyperplane, but the probability output is curved and bounded.

Encoding class labels

Before any formula we need a convention for representing classes as numbers — and the right choice depends on the algorithm.

Binary {0, 1}

Class 1 $= 1$ , class 2 $= 0$ . Convenient for logistic regression: the target $t$ reads directly as a target probability, and the cross-entropy loss has a clean form.

Bipolar {+1, −1}

Class 1 $= +1$ , class 2 $= -1$ . The perceptron uses this to check whether $\mathbf{w}^\top\boldsymbol{\phi}(\mathbf{x})$ and $t$ share a sign: a misclassified point has $\mathbf{w}^\top\boldsymbol{\phi}(\mathbf{x})\,t_n < 0$ .

key

Multi-class: 1-of-K (one-hot) encoding

For $K$ classes use a target vector $\mathbf{t} \in \{0,1\}^K$ with exactly one $1$ . If the true class is $\mathcal{C}_3$ and $K=5$ , then $\mathbf{t} = (0,0,1,0,0)^\top$ . The $1$ is a flag for the winning class — nothing more. Softmax uses this encoding.

Escaping linearity with basis functions

Exactly as in linear regression (Ch. 02), we can replace the raw inputs $\mathbf{x}$ with a nonlinear feature map $\boldsymbol{\phi}(\mathbf{x}) = (\phi_1(\mathbf{x}), \dots, \phi_M(\mathbf{x}))^\top$ . The model is then linear in $\boldsymbol{\phi}$ -space, which means:

The decision boundary is a hyperplane in $\boldsymbol{\phi}$ -space.
Mapped back to $\mathbf{x}$ -space, that same hyperplane is a curved surface.
So a “linear” classifier can carve arbitrarily complex boundaries in the original space.

map

The bridge to Chapter 02

The mechanics are identical to linear regression: the same design matrix $\boldsymbol{\Phi}$ , the same weight vector $\mathbf{w}$ , the same linear algebra. Only the loss and the activation change. The architecture is reused; only the output layer and training objective are new.

03 · Formalism

Three blocks of theory

The formalism splits into three self-contained blocks, each a different answer to “how do we learn a decision boundary?“

x: an input vector in $\mathbb{R}^{D}$ ; or its feature map $\boldsymbol{\phi}(\mathbf{x})$ .
w: the weight vector; with the convention $\phi_0 \equiv 1$ , the bias $w_0$ folds in.
w₀: the bias (threshold weight) — sets the location of the decision surface.
t: the target label: $\{0,1\}$ for logistic, $\{+1,-1\}$ for the perceptron, 1-of-K for softmax.
y: the model output: a score, a hard label, or a probability, depending on the method.
σ: the logistic sigmoid $\sigma(a) = 1/(1+e^{-a})$ .

A · Discriminant functions

The simplest classifier assigns every input to one of two classes via a single linear function:

Two-class linear discriminant

y(\mathbf{x}) = \mathbf{w}^\top\mathbf{x} + w_0, \qquad \text{assign } \mathcal{C}_1 \text{ if } y(\mathbf{x}) \geq 0,\; \text{else } \mathcal{C}_2.

The decision surface is the set $\mathbf{w}^\top\mathbf{x} + w_0 = 0$ — a hyperplane in $\mathbb{R}^D$ .

Geometry — $\mathbf{w}$ is orthogonal to the surface. Take any two points $\mathbf{x}_A, \mathbf{x}_B$ on the surface, so $y(\mathbf{x}_A) = y(\mathbf{x}_B) = 0$ . Subtracting, $\mathbf{w}^\top(\mathbf{x}_A - \mathbf{x}_B) = 0$ — so $\mathbf{w}$ is perpendicular to every vector lying in the surface. $\mathbf{w}$ is the surface’s normal. Projecting the origin onto the surface, its signed distance from the origin is

\text{distance} = -\frac{w_0}{\lVert\mathbf{w}\rVert}.

view

The perpendicular foot

Any input decomposes as $\mathbf{x} = \mathbf{x}_\perp + r\,\dfrac{\mathbf{w}}{\lVert\mathbf{w}\rVert}$ , where $\mathbf{x}_\perp$ lies on the surface and $r = \dfrac{y(\mathbf{x})}{\lVert\mathbf{w}\rVert}$ is the signed perpendicular distance to the fence. So $y(\mathbf{x})$ is literally how far you are from the boundary, scaled by $\lVert\mathbf{w}\rVert$ .

Multi-class — the $K$ -class solution. Two naive extensions both fail by creating ambiguous regions:

One-vs-Rest (OvR)

Train $K$ binary classifiers, each separating one class from all others. A point can be claimed by several classes at once — or by none. Regions near boundaries are genuinely ambiguous.

One-vs-One (OvO)

Train $\binom{K}{2}$ pairwise classifiers. Voting can tie, and pairwise verdicts can be inconsistent (A beats B, B beats C, C beats A).

The clean fix is a single set of $K$ linear discriminants with an argmax rule:

K-class discriminant

y_k(\mathbf{x}) = \mathbf{w}_k^\top\mathbf{x} + w_{k0}, \qquad \text{assign } \mathbf{x}\to\mathcal{C}_k \iff y_k(\mathbf{x}) > y_j(\mathbf{x})\;\;\forall j \neq k.

One weight vector per class; the winner is whichever discriminant scores highest. No ties, no gaps.

Exam-relevant proof Why the K-class regions are provably convex

The decision region for class $\mathcal{C}_k$ is $\mathcal{R}_k = \{\mathbf{x} : y_k(\mathbf{x}) > y_j(\mathbf{x}),\ \forall j \neq k\}$ . Take any two points $\mathbf{x}_A, \mathbf{x}_B \in \mathcal{R}_k$ and any $\alpha \in [0,1]$ . By linearity of each discriminant,

y_k\bigl(\alpha\mathbf{x}_A + (1-\alpha)\mathbf{x}_B\bigr) = \alpha\,y_k(\mathbf{x}_A) + (1-\alpha)\,y_k(\mathbf{x}_B).

Since $y_k(\mathbf{x}_A) > y_j(\mathbf{x}_A)$ and $y_k(\mathbf{x}_B) > y_j(\mathbf{x}_B)$ for every $j \neq k$ , the same convex combination of those strict inequalities gives $y_k > y_j$ at the midpoint. So the midpoint is also in $\mathcal{R}_k$ — the region is convex and singly connected. Equivalently, each pairwise condition $y_k > y_j$ rearranges to $(\mathbf{w}_k - \mathbf{w}_j)^\top\mathbf{x} + (w_{k0} - w_{j0}) > 0$ , a half-space; $\mathcal{R}_k$ is an intersection of $K-1$ half-spaces, and an intersection of half-spaces is convex by construction.

Least squares for classification. With 1-of-K targets you can stack all class weights into a matrix and solve in closed form — the exact machinery of Ch. 02:

\widetilde{\mathbf{W}} = (\widetilde{\boldsymbol{\Phi}}^\top\widetilde{\boldsymbol{\Phi}})^{-1}\widetilde{\boldsymbol{\Phi}}^\top\mathbf{T}.

×

Why least-squares classification breaks

Two failures remain. First, OLS penalises correct, confident predictions: a point with $y = 2$ when the target is $1$ still pays $(2-1)^2 = 1$ , pulling the boundary toward confident points. Second, the Gaussian noise assumption is violated for binary targets, so outputs stray outside $[0,1]$ and can’t be read as probabilities. The same two failures from §1, now formal.

B · The perceptron

The perceptron (Rosenblatt, 1958) is the oldest linear classifier and the ancestor of every neural network. It is an online algorithm: it processes one point at a time and updates immediately on each mistake, replacing the smooth sigmoid with a hard step — trading probabilities for simplicity.

Perceptron model

y(\mathbf{x}) = f\bigl(\mathbf{w}^\top\boldsymbol{\phi}(\mathbf{x})\bigr), \qquad f(a) = \begin{cases} +1 & a \geq 0 \\ -1 & a < 0 \end{cases}, \qquad t_n \in \{+1,-1\}.

The step (Heaviside) activation outputs hard $\pm 1$ labels — no probability, no confidence.

Why not just minimise mistakes? The natural 0/1 loss (count misclassifications) is piecewise constant in $\mathbf{w}$ — flat over whole regions, then jumping. A flat function has zero gradient almost everywhere, so gradient descent cannot move. The perceptron’s fix is a piecewise-linear surrogate that grows with the distance of each misclassified point from the boundary:

Perceptron criterion

L_P(\mathbf{w}) = -\sum_{n \in \mathcal{M}} \mathbf{w}^\top\boldsymbol{\phi}(\mathbf{x}_n)\,t_n, \qquad \nabla_{\mathbf{w}} L_P = -\sum_{n \in \mathcal{M}} \boldsymbol{\phi}(\mathbf{x}_n)\,t_n.

$\mathcal{M}$ is the currently misclassified set. For those points $\mathbf{w}^\top\boldsymbol{\phi}\,t_n < 0$ , so $-\mathbf{w}^\top\boldsymbol{\phi}\,t_n > 0$ — a non-negative loss. Correctly classified points contribute nothing.

Stochastic gradient descent on $L_P$ , one misclassified point at a time, gives the famous update:

\mathbf{w}^{(\tau+1)} \leftarrow \mathbf{w}^{(\tau)} + \alpha\,\boldsymbol{\phi}(\mathbf{x}_n)\,t_n.

The step $\boldsymbol{\phi}(\mathbf{x}_n)\,t_n$ pushes $\mathbf{w}$ in the direction that would correct this mistake. The learning rate $\alpha$ can be set to $1$ without loss of generality — the solution set is invariant to scaling $\mathbf{w}$ .

!

Perceptron Convergence Theorem

If the training data is linearly separable in feature space (some $\mathbf{w}^\star$ classifies every point), the perceptron converges to an exact solution in a finite number of updates. If the data is not separable, it cycles forever — and crucially, you cannot tell “slow convergence” from “non-convergence” by watching it run. The only safe test is to prove separability.

The perceptron’s limitations are the price of that simplicity: no probabilistic output (hard $\pm 1$ ); the solution is not unique (initialisation- and order-dependent); and on non-separable data it never converges at all.

C · Probabilistic discriminative models

Instead of a hard boundary, logistic regression models the posterior probability directly with the sigmoid:

Logistic regression

p(\mathcal{C}_1 \mid \boldsymbol{\phi}) = \sigma(\mathbf{w}^\top\boldsymbol{\phi}), \qquad p(\mathcal{C}_2 \mid \boldsymbol{\phi}) = 1 - \sigma(\mathbf{w}^\top\boldsymbol{\phi}).

The score $a = \mathbf{w}^\top\boldsymbol{\phi}$ is the log-odds (logit): $a = \ln\dfrac{p(\mathcal{C}_1\mid\boldsymbol{\phi})}{p(\mathcal{C}_2\mid\boldsymbol{\phi})}$ . The boundary $a = 0$ is exactly where the odds are 1:1, i.e. $p = 0.5$ .

So logistic regression fits a linear model to the log-odds. We derive its training loss by maximum likelihood — and the gradient that drops out is the punchline of the chapter.

Derivation Deriving the cross-entropy gradient

1 · Bernoulli likelihood

Each label is Bernoulli with success probability $y_n = \sigma(\mathbf{w}^\top\boldsymbol{\phi}_n)$ :

p(\mathbf{t}\mid\mathbf{w}) = \prod_{n=1}^N y_n^{t_n}(1-y_n)^{1-t_n}.

2 · Negative log-likelihood = cross-entropy

Take $-\ln$ of the likelihood (MLE $=$ minimise this):

L(\mathbf{w}) = -\sum_{n=1}^N \bigl[\,t_n \ln y_n + (1-t_n)\ln(1-y_n)\,\bigr].

This is the cross-entropy loss.

3 · Chain rule

With $a_n = \mathbf{w}^\top\boldsymbol{\phi}_n$ ,

\frac{\partial L}{\partial\mathbf{w}} = \sum_{n=1}^N \frac{\partial L}{\partial y_n}\cdot\frac{\partial y_n}{\partial a_n}\cdot\boldsymbol{\phi}_n.

4 · The two factors

\frac{\partial L}{\partial y_n} = -\frac{t_n}{y_n} + \frac{1-t_n}{1-y_n} = \frac{y_n - t_n}{y_n(1-y_n)}, \qquad \frac{\partial y_n}{\partial a_n} = \sigma'(a_n) = y_n(1-y_n).

5 · The miracle cancellation

The $y_n(1-y_n)$ cancels exactly:

\frac{\partial L}{\partial y_n}\cdot\frac{\partial y_n}{\partial a_n} = \frac{y_n - t_n}{y_n(1-y_n)}\cdot y_n(1-y_n) = y_n - t_n.

6 · The gradient

\boxed{\;\nabla L(\mathbf{w}) = \sum_{n=1}^N (y_n - t_n)\,\boldsymbol{\phi}_n\;}

A clean prediction-minus-target, times feature form — with no closed-form solution, because $\sigma$ is nonlinear.

=

The 'same form as linear regression' is no coincidence

Compare the OLS gradient from Ch. 02: $\nabla L_\text{OLS} = \sum_n (y_n - t_n)\,\boldsymbol{\phi}_n$ — algebraically identical. This is the exponential family at work: both Gaussian (regression) and Bernoulli (logistic) are exponential-family distributions, and for any generalised linear model the gradient of the negative log-likelihood factors as $(\text{predicted} - \text{actual})\times\text{feature}$ . The maths is telling you something deep: error $=$ predicted $-$ actual, regardless of output type.

Logistic regression’s properties follow from that gradient: no closed form (iterate with gradient descent, Newton–Raphson, or L-BFGS); the loss is strictly convex, so there are no local minima; outputs are calibrated probabilities; and it is outlier-robust via saturation — a confident, correct point has $y_n - t_n \approx 0$ , so the sigmoid stops caring and the outlier barely pulls.

Multiclass — softmax. For $K$ classes, generalise the sigmoid to the softmax:

Softmax

p(\mathcal{C}_k \mid \boldsymbol{\phi}) = \frac{\exp(\mathbf{w}_k^\top\boldsymbol{\phi})}{\sum_{j=1}^K \exp(\mathbf{w}_j^\top\boldsymbol{\phi})}, \qquad \nabla_{\mathbf{w}_j} L = \sum_{n=1}^N (y_{nj} - t_{nj})\,\boldsymbol{\phi}_n.

$\exp$ keeps every probability positive; the shared denominator forces the $K$ outputs to sum to $1$ . The gradient is the same prediction-error form again, now per class.

key

Perceptron and logistic regression share one update

Both step with $\mathbf{w} \leftarrow \mathbf{w} - \alpha\,(y_n - t_n)\,\boldsymbol{\phi}_n$ . The only difference is what $y_n$ means: for the perceptron it is a hard $\text{step}(\mathbf{w}^\top\boldsymbol{\phi}_n)$ — so the update is non-zero only on mistakes; for logistic regression it is a smooth $\sigma(\mathbf{w}^\top\boldsymbol{\phi}_n) \in (0,1)$ — non-zero on every point, but tiny for confident correct ones. Replace $\sigma$ with a step and logistic regression becomes the perceptron.

Summary — what is each method optimising?

Method	Objective	Output	Closed form?
Least-squares classifier	$\sum_n \lVert \mathbf{y}_n - \mathbf{t}_n\rVert^2$	real-valued score	Yes (normal equations)
Perceptron	$-\sum_{n\in\mathcal{M}} \mathbf{w}^\top\boldsymbol{\phi}_n\, t_n$	hard label $\pm 1$	No (online SGD)
Logistic regression	$-\sum_n [\,t_n \ln y_n + (1-t_n)\ln(1-y_n)\,]$	probability in $(0,1)$	No (iterative, convex)
Softmax regression	$-\sum_n\sum_k t_{nk}\ln y_{nk}$	probability vector	No (iterative, convex)

Only the wrong-for-the-job least-squares method has a closed form. The probabilistically principled methods need iteration — but convexity guarantees they reach the global optimum. The perceptron is the odd one out: not closed-form, not smooth-convex, yet finite-step convergent when the data cooperates.

04 · Worked example

Logistic regression by hand

We run two full gradient-descent steps on a tiny 2-D dataset — every number explicit, no black boxes.

Worked example Two gradient steps of logistic regression

1 · The toy dataset

Four points, two per class, with features augmented by a leading $1$ to absorb the bias:

Point	$x_1$	$x_2$	$t$	$\boldsymbol{\phi}_n = (1, x_1, x_2)^\top$
$\mathbf{x}_1$	1	1	1 (C₁)	$(1,1,1)$
$\mathbf{x}_2$	2	1	1 (C₁)	$(1,2,1)$
$\mathbf{x}_3$	1	2	0 (C₂)	$(1,1,2)$
$\mathbf{x}_4$	2	2	0 (C₂)	$(1,2,2)$

Class 1 has $x_2 = 1$ ; class 2 has $x_2 = 2$ . The natural separator is the horizontal line $x_2 = 1.5$ , so we expect $w_2$ to grow negative and $w_0$ to grow positive.

2 · Step 1 — forward pass from w = 0

Initialise $\mathbf{w}^{(0)} = (0,0,0)^\top$ , learning rate $\alpha = 0.1$ . Then $a_n = 0$ and $y_n = \sigma(0) = 0.5$ for all $n$ :

Point	$y_n$	$t_n$	$y_n - t_n$
$\mathbf{x}_1$	0.500	1	$-0.500$
$\mathbf{x}_2$	0.500	1	$-0.500$
$\mathbf{x}_3$	0.500	0	$+0.500$
$\mathbf{x}_4$	0.500	0	$+0.500$

3 · Gradient and first update

Sum the prediction-error contributions $\nabla L = \sum_n (y_n - t_n)\,\boldsymbol{\phi}_n$ :

\nabla L = \begin{pmatrix} -0.5-0.5+0.5+0.5 \\ -0.5-1.0+0.5+1.0 \\ -0.5-0.5+1.0+1.0 \end{pmatrix} = \begin{pmatrix} 0.0 \\ 0.0 \\ 1.0 \end{pmatrix}, \qquad \mathbf{w}^{(1)} = \mathbf{0} - 0.1\begin{pmatrix}0\\0\\1\end{pmatrix} = \begin{pmatrix}0\\0\\-0.1\end{pmatrix}.

Only $w_2$ moved, becoming negative — exactly as predicted.

4 · Why didn't w₁ move?

Both classes share the same $x_1$ values $\{1,2\}$ — so $x_1$ carries zero information about the class. The $w_1$ component of the gradient is $\sum_n (y_n - t_n)\,x_{1n}$ , and the symmetry cancels it to exactly zero. The optimiser is correctly inferring that $x_1$ is an irrelevant feature.

5 · Step 2 — second forward pass and update

With $\mathbf{w}^{(1)} = (0,0,-0.1)^\top$ : the C₁ points ( $x_2=1$ ) get $y = \sigma(-0.1) \approx 0.475$ ; the C₂ points ( $x_2=2$ ) get $y = \sigma(-0.2) \approx 0.450$ . The new gradient and update:

\nabla L^{(1)} = \begin{pmatrix} -0.150 \\ -0.225 \\ 0.750 \end{pmatrix}, \qquad \mathbf{w}^{(2)} = \begin{pmatrix}0\\0\\-0.1\end{pmatrix} - 0.1\begin{pmatrix}-0.150\\-0.225\\0.750\end{pmatrix} = \begin{pmatrix}+0.015\\+0.0225\\-0.175\end{pmatrix}.

6 · Interpreting the result

After two steps $\mathbf{w}^{(2)} \approx (0.015,\,0.023,\,-0.175)^\top$ : $w_2$ is negative (correctly discounting high $x_2$ ), $w_0$ slightly positive, and $w_1 \approx 0.023$ — nearly zero, since the true boundary has no $x_1$ dependence. The boundary $\mathbf{w}^{(2)\top}\boldsymbol{\phi} = 0$ gives $x_2 \approx 0.086 + 0.131\,x_1$ — still far from the true $x_2 = 1.5$ , but heading the right way. Gradient descent makes slow, steady progress.

Optional Bonus: a perceptron trace that converges in one step

Take a 1-D separable set with $\pm 1$ targets and features $\boldsymbol{\phi} = (1, x)^\top$ : point $A = (1,-2)$ with $t = -1$ , point $B = (1,+2)$ with $t = +1$ . Start at $\mathbf{w}^{(0)} = (0,0)^\top$ .

Check A: $\text{sign}(\mathbf{w}^\top\boldsymbol{\phi}_A) = \text{sign}(0) = +1 \neq -1$ — misclassified. Update: $\mathbf{w}^{(1)} = (0,0) + (1)(1,-2)(-1) = (-1,+2)$ .
Re-check A: $\text{sign}\bigl((-1)(1) + (2)(-2)\bigr) = \text{sign}(-5) = -1$ ✓.
Check B: $\text{sign}\bigl((-1)(1) + (2)(+2)\bigr) = \text{sign}(3) = +1$ ✓.

Converged in one update — the data was linearly separable in $\boldsymbol{\phi}$ -space.

05 · Visual explanation

Four diagrams that make it click

The geometry of a decision boundary

$\mathbf{w}$ points perpendicular to the boundary, into the $y > 0$ half-space; $w_0$ slides the boundary along $\mathbf{w}$ without rotating it, at signed distance $-w_0/\lVert\mathbf{w}\rVert$ from the origin.

The three approaches at a glance

The same problem, three philosophies — what each models, outputs, and trades off.

Discriminant — e.g. perceptron

Models: $f(\mathbf{x}) \to$ class, directly. Output: hard label. Pro: fast, simple. Con: no probability. (covered in Ch. 03)

Discriminative — e.g. logistic

Models: $p(\mathcal{C}_k\mid\mathbf{x})$ directly. Output: probability in $(0,1)$ . Pro: fewer parameters than generative. Con: can’t generate data. (covered in Ch. 03)

Generative — e.g. Gaussian DA

Models: $p(\mathbf{x}\mid\mathcal{C}_k)$ and $p(\mathcal{C}_k)$ . Output: posterior via Bayes. Pro: can generate data, handle missing inputs. Con: more parameters, harder fit. (later chapter)

Sigmoid vs. step

The logistic sigmoid is the smooth, differentiable cousin of the perceptron’s step. Both cross at $a = 0$ ; replace $\sigma$ with the step and logistic regression becomes the perceptron.

The softmax probability simplex

For three classes, every prediction is a point inside a triangle: the corners are pure classes, the centroid is the uniform $(\tfrac13,\tfrac13,\tfrac13)$ , and every interior point sums to $1$ .

Why least squares fails on classification

With no outliers, least squares and logistic regression agree. Add a cluster of far outliers and least squares rotates its boundary to shrink their squared residuals, wrecking the bulk fit — while logistic regression barely moves, because the sigmoid saturates and the outliers contribute almost no gradient.

06 · Hands-on

Try it yourself

Four labs, each drilling one idea you need to see move before it sticks. Push the controls, watch the numbers, then read the takeaway.

Hands-on 1

Decision boundary explorer

Drag the sliders to move and rotate the fence y = w₁x₁ + w₂x₂ + w₀ = 0. Points the boundary gets wrong glow amber; the gold arrow is w, always perpendicular to the line and pointing into the y > 0 half-space.

w₀ (bias)0.00

w₁1.00

w₂-1.00

Boundary

1.0x₁ − 1.0x₂ + 0.0 = 0

Misclassified

12

C₁ correct

7/12

C₂ correct

5/12

Try thisPush w₀ to +3 — the line slides toward the origin without tilting. Now set w₁ = 0 and vary only w₂: the fence becomes horizontal and only its height moves.

Takeawayw sets the orientation of the fence (its tilt); w₀ sets its position (how far from the origin). Two independent controls — one rotates, one translates.

Hands-on 2

Perceptron step-through

Each Next step applies one update w ← w + φ(xₙ)·tₙ on the first misclassified point (glowing amber, with learning rate α = 1). The data is linearly separable, so the perceptron is guaranteed to reach zero mistakes in finite steps.

step 0

w₀

0.00

w₁

0.00

w₂

0.00

Misclassified

4

4 points still misclassified — keep stepping.

Try thisStep to convergence and note the count. Hit Reset and step again — the same initialisation gives the same path and the same number of steps.

TakeawayThe perceptron converges in finitely many steps on separable data, but the boundary it lands on depends on initialisation and point order — there is no margin or optimality guarantee (that comes from the SVM in Ch. 7).

Hands-on 3

Logistic regression live fit

Gradient descent fits σ(wᵀφ) in real time. Raise class noise to overlap the blobs, or add a far outlier (a wrong-class point flung into the opposite territory) and watch how little the boundary flinches.

class noise0.40

Iteration

0

Loss

0.693

Outliers

0

Accuracy

50%

Try thisClick Add outlier a few times. The gold boundary barely budges — with OLS classification those same far points would wrench it around to shrink their squared residuals.

TakeawayLogistic regression is outlier-robust because the sigmoid saturates: a confident-but-wrong point has gradient (yₙ − tₙ) ≈ ±1 times a feature, but once the model is sure it stops caring — the contribution flattens, so extreme points barely pull.

Hands-on 4

Softmax probability explorer

Adjust the three raw scores a₁, a₂, a₃. Softmax exponentiates and normalises them into probabilities that always sum to 1 — so the classes compete. The dot on the simplex is the resulting (p₁, p₂, p₃).

a₁ (C₁ score)1.0

a₂ (C₂ score)0.0

a₃ (C₃ score)-1.0

p₁

0.665

p₂

0.245

p₃

0.090

Σ exp

4.086

Try thisSet all three equal (say a₁=a₂=a₃=2) — each probability is exactly ⅓ and the dot sits dead centre. Now raise a₁ alone: p₂ and p₃ both fall even though you never touched them.

TakeawayThe shared denominator makes the classes compete — probabilities always sum to 1, so lifting one score steals from the rest. That is exactly why K independent sigmoids are wrong: they never normalise.

07 · Exam intel

What examiners actually test

Q1

Three approaches — know when to use which

Discriminant (perceptron): maps $\mathbf{x}$ straight to a label, no probabilities, fast. Discriminative (logistic): models $p(\mathcal{C}_k\mid\mathbf{x})$ directly — fewer parameters than generative, calibrated probabilities, the gold standard. Generative (Gaussian DA): models $p(\mathbf{x}\mid\mathcal{C}_k)$ and $p(\mathcal{C}_k)$ , derives the posterior via Bayes, can generate data. Exam pattern: “compare discriminative and generative” — state what each models, parameter count, and whether it gives calibrated probabilities.

Q2

The logistic-regression gradient — the gift

$\nabla L(\mathbf{w}) = \sum_n (y_n - t_n)\,\boldsymbol{\phi}_n$ has the same algebraic form as the least-squares gradient — a consequence of the exponential family, not a coincidence. Examiners test: (i) no closed form, since $\sigma$ is nonlinear; (ii) the loss is strictly convex, so the global minimum is guaranteed; (iii) gradient descent, Newton–Raphson, and L-BFGS all apply.

Q3

Perceptron Convergence Theorem

Statement: if the data is linearly separable in feature space, the perceptron converges in finitely many steps to an exact solution. Caveat: if it is not separable, the algorithm never converges — and you cannot tell slow from non-convergent from the outside. $\alpha$ can be set to 1: the update is invariant to scaling $\mathbf{w}$ , so the learning rate is immaterial to the solution set.

Q4

Softmax gradient — same pattern again

For multi-class cross-entropy, $\nabla_{\mathbf{w}_j} L = \sum_n (y_{nj} - t_{nj})\,\boldsymbol{\phi}_n$ . The derivation hinges on the softmax Jacobian $\dfrac{\partial y_j}{\partial a_k} = y_j(\delta_{jk} - y_k)$ ; multiply by the cross-entropy term $-t_j/y_j$ and sum over $j$ and it collapses to $y_k - t_k$ . Memorise the Jacobian — exams ask you to derive this.

tip

Four formulas to memorise

Sigmoid: $\sigma(a) = \dfrac{1}{1+e^{-a}}$ , with $\sigma'(a) = \sigma(a)\bigl(1-\sigma(a)\bigr)$ .
Cross-entropy: $L(\mathbf{w}) = -\sum_n \bigl[t_n \ln y_n + (1-t_n)\ln(1-y_n)\bigr]$ .
Logistic gradient: $\nabla L(\mathbf{w}) = \sum_n (y_n - t_n)\,\boldsymbol{\phi}_n$ .
Softmax: $p(\mathcal{C}_k\mid\boldsymbol{\phi}) = \dfrac{\exp(\mathbf{w}_k^\top\boldsymbol{\phi})}{\sum_j \exp(\mathbf{w}_j^\top\boldsymbol{\phi})}$ .

08 · Common mistakes

Traps to avoid

×

Regression loss ≠ classification loss

Sum-of-squares on binary $0/1$ targets is wrong twice over: it assumes Gaussian noise (labels are Bernoulli), and it penalises correct, confident predictions ( $y = 2$ for $t = 1$ pays $1$ ), pulling the boundary toward outliers. Always use cross-entropy for classification.

×

The boundary is linear — the model is not

Logistic regression’s boundary $\sigma(\mathbf{w}^\top\boldsymbol{\phi}) = 0.5$ reduces to $\mathbf{w}^\top\boldsymbol{\phi} = 0$ , a linear hyperplane. But the probability output $\sigma(\mathbf{w}^\top\boldsymbol{\phi}(\mathbf{x}))$ is nonlinear in the inputs. On an exam, always say what is linear (the boundary / logit) and what is nonlinear (the probability).

×

Perceptron ≠ logistic regression

They share the update $\mathbf{w} \leftarrow \mathbf{w} + \alpha\,\boldsymbol{\phi}(x_n)\,t_n$ , so they look identical on the board. But the perceptron uses a hard $\pm 1$ label with no probabilistic loss and a finite-step convergence theorem (only if separable); logistic regression has calibrated probabilities, a cross-entropy loss, and converges to a unique global minimum even on non-separable data.

×

Softmax ≠ K independent sigmoids

Applying $\sigma$ to each score separately, $p_k = \sigma(a_k)$ , gives outputs that do not sum to 1 — not a valid distribution. Softmax normalises globally, $p_k = e^{a_k}/\sum_j e^{a_j}$ , forcing $\sum_k p_k = 1$ and making the classes compete: raising $a_1$ lowers every other $p_k$ .

×

The class-imbalance blind spot

With 95% class-A data, “always predict A” scores 95% accuracy and is useless. Cross-entropy does not automatically protect you — the boundary can collapse to one side while the loss still drops. Monitor per-class recall and the boundary’s position, not just overall accuracy.

×

Linear in feature space ≠ linear in input space

“Linear classifiers can’t solve XOR” is true only in the raw input space. With the right basis (e.g. $\phi = x_1 x_2$ ), a linear classifier in $\boldsymbol{\phi}$ -space draws a nonlinear boundary in $\mathbf{x}$ -space — and solves XOR trivially.

×

Convergence does not mean uniqueness

The Perceptron Convergence Theorem guarantees the algorithm finds a separating hyperplane — not the best one. Different initialisations and orderings give different solutions, all with zero training error but different generalisation. No margin guarantee (that is the SVM, Ch. 7).

09 · Self-check

Can you answer these?

Seven questions mirroring how the chapter gets tested. Click an option for instant feedback.

What are the two failure modes of using ordinary least squares for binary classification?

In the linear discriminant y(x) = wᵀx + w₀, what geometric role does w₀ play?

State the exact condition under which the Perceptron Convergence Theorem applies.

Write the gradient of the logistic cross-entropy loss. Why is the result described as surprising?

You apply K independent sigmoids pₖ = σ(wₖᵀφ) instead of a softmax. What is the fundamental problem?

A classmate says: 'Linear classifiers can never solve XOR because XOR is not linearly separable.' Is this correct?

For the K-class argmax rule (assign x to Cₖ iff yₖ(x) > yⱼ(x) for all j ≠ k), why are the decision regions convex?

10 · Recap

One-screen summary

Chapter 03 — load-bearing ideas

Regression is not classification. Fitting a line to $0/1$ targets fails twice: outlier sensitivity and a violated Gaussian-noise assumption. The fix is a nonlinear, probability-valued activation.
Three strategies: discriminant (boundary first), probabilistic discriminative ( $p(\mathcal{C}_k\mid\mathbf{x})$ directly), probabilistic generative (model the joint, invert with Bayes). This chapter does the first two.
Boundary geometry. $\mathbf{w}$ is the normal — it sets orientation; $w_0$ sets position, at signed distance $-w_0/\lVert\mathbf{w}\rVert$ from the origin. $y(\mathbf{x})/\lVert\mathbf{w}\rVert$ is the perpendicular distance.
The $K$ -class rule. A single set of $K$ discriminants with argmax gives convex, gap-free regions — beating one-vs-rest and one-vs-one, which both leave ambiguous zones.
Perceptron. Online updates on misclassified points only; converges in finite steps iff separable; no probabilities, non-unique, order-dependent; $\alpha$ can be $1$ .
Logistic regression. $\sigma(\mathbf{w}^\top\boldsymbol{\phi})$ is a calibrated posterior; cross-entropy is the ML loss; the gradient $\sum_n (y_n - t_n)\,\boldsymbol{\phi}_n$ matches linear regression’s — exponential-family structure. No closed form; strictly convex.
Softmax generalises to $K$ classes; outputs always sum to $1$ and compete globally, which is why $K$ independent sigmoids are wrong.
One update, two algorithms. Perceptron and logistic regression step identically; swapping the step for a sigmoid turns one into the other.

→

Looking ahead → Chapter 04

Given several classifiers, how do we pick the best without overfitting? The bias–variance tension from Ch. 02 returns — a logistic model with too many basis functions overfits just like a high-degree polynomial. Cross-validation, regularisation, and information criteria are next.

Why regression is not enough

Medical diagnosis

Spam detection

Digit recognition

The two failure modes of naive regression

Failure 1 — outlier sensitivity

Failure 2 — wrong noise model

Three strategies — a navigation map

① Discriminant function

② Probabilistic discriminative

③ Probabilistic generative

Decision boundaries as fences in feature space

Why the activation must be nonlinear

Encoding class labels

Binary {0, 1}

Bipolar {+1, −1}

Escaping linearity with basis functions

Three blocks of theory

A · Discriminant functions

One-vs-Rest (OvR)

One-vs-One (OvO)

B · The perceptron

C · Probabilistic discriminative models

Summary — what is each method optimising?

Logistic regression by hand

Four diagrams that make it click

The geometry of a decision boundary

The three approaches at a glance

Discriminant — e.g. perceptron

Discriminative — e.g. logistic

Generative — e.g. Gaussian DA

Sigmoid vs. step

The softmax probability simplex

Why least squares fails on classification

Try it yourself

Decision boundary explorer

Perceptron step-through

Logistic regression live fit

Softmax probability explorer

What examiners actually test

Traps to avoid

Can you answer these?

One-screen summary

Chapter 03 — load-bearing ideas