Linear Models & the Perceptron

The shortest path into deep learning is to start with the shallowest model and watch exactly where it breaks. A linear model computes a weighted sum of its inputs plus a bias,

and reads a prediction off $z$. Three classic learners differ only in how they turn $z$ into an answer and how they measure error, but all three share the template every network inherits: score, compare, descend. Folding the bias into $w$ via the convention $x_0=1$, they line up term-for-term:

The middle column is the activation; the loss column is the only place the three truly diverge. Yet the gradient column nearly collapses: every entry is the same prediction-minus-target-times-input residual, which is why one descent loop trains all three.¹

Linear regression

For real-valued targets, take the prediction to be $z$ itself, $\hat{y}=w^{\top }x+b$, and measure error by squared distance. Over the training set that is the mean squared error

This one is special: it is convex and quadratic, so it has a closed-form minimizer. Stack the examples as rows of $X\in {\mathbb{R}}^{n\times d}$ and targets as $y\in {\mathbb{R}}^n$ (bias absorbed via $x_0=1$); the objective and its gradient are

Setting the gradient to zero and dropping the scalar $\frac{2}{n}$ gives the normal equations and, when $X^{\top }X$ is invertible, the closed-form optimum:

We will almost never have that luxury again — but the residual gradient $X^{\top }(Xw-y)$, one row of which is $({\hat{y}}_i-y_i)x_i$, is the object every later model descends.

For example, take data $(x,y)=(1,2),(2,2),(3,4)$ and fit a line $\hat{y}=w_{1}x+w_0$. With the bias column of ones, $X=\left[\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\end{array}\right]$ and $y=(2,2,4{)}^{\top }$, so

Inverting the $2\times 2$ system (determinant $3\cdot 14-36=6$) gives

the best-fit line $\hat{y}=x+0.67$. Its residuals are $(0.33,-0.67,0.33)$, which sum to zero — the signature of a least-squares fit, where the residual vector is orthogonal to every column of $X$, including the all-ones bias column. That orthogonality restates the normal equation $X^{\top }(Xw-y)=0$ as a geometric fact.

Logistic regression

For binary classification we want a probability, not an unbounded score. Squash $z$ through the logistic sigmoid

The right loss is again maximum likelihood: the binary cross-entropy$\ell (w)=-[y\log \hat{y}+(1-y)\log (1-\hat{y})]$ with $\hat{y}=\sigma (z)$, $z=w^{\top }x$. Its gradient follows from the chain rule and the identity ${\sigma }^{\prime }(z)=\sigma (z)(1-\sigma (z))$:

The two factors cancel the awkward denominator, and a final $\partial z/\partial w=x$ delivers the same clean residual as least squares:

That identical gradient across both models is no coincidence; it is a property of the whole exponential family, and it is the reason a single optimization loop trains them all.²

One gradient step, worked end to end, shows how the residual drives the update. Take a single example $x=(1,2{)}^{\top }$ with label $y=1$, current weights $w=(0,0)$. The score is $z=w^{\top }x=0$, so $\hat{y}=\sigma (0)=0.5$: the model is maximally unsure. The residual is $\hat{y}-y=0.5-1=-0.5$, and the gradient is

Descending with learning rate $\eta =1$ gives $w\leftarrow w-\eta {\nabla }_w\ell =(0.5,1)$. Re-scoring the same point, $z=0.5\cdot 1+1\cdot 2=2.5$, so $\hat{y}=\sigma (2.5)\approx 0.92$ — the prediction has moved decisively toward the correct label $1$. The step magnitude scaled with the residual: a confident correct prediction ($\hat{y}\approx y$) would have produced almost no update, which is why cross-entropy training slows as the model gets the answer right.

Geometrically, the model splits the input space with a flat decision boundary, the hyperplane $w^{\top }x+b=0$. The weight vector $w$ points perpendicular to it, toward the positive class; the signed distance of a point from the boundary is $(w^{\top }x+b)/\Vert w\Vert$, and the sigmoid turns that distance into a probability: far on the positive side $\to 1$, far on the negative side $\to 0$, on the boundary $\to \frac{1}{2}$.

Three models, then, and one shared skeleton: linear regression reads $z$ directly, logistic regression squashes it to a probability, and, historically first, the perceptron simply thresholds it.

The perceptron

Historically first (Rosenblatt, 1958), the perceptron is the hard-threshold version: predict $+1$ if $z\ge 0$, else $-1$, and on each misclassified example nudge the weights toward getting it right.³ Drawn as a unit, it is the template every later neuron copies — inputs scaled by weights, summed, thresholded:

The update is not ad hoc: it is stochastic (sub)gradient descent on the perceptron loss $\ell (w)=\max (0,-y{w}^{\top }x)$, which is zero when $y{w}^{\top }x>0$ (correct, off the boundary) and grows linearly into the misclassified region. Its subgradient is piecewise:

so the descent step $w\leftarrow w-\eta {\partial }_w\ell$ with $\eta =1$ is exactly $w\leftarrow w+yx$ on a mistake and a no-op otherwise, the algorithm below.

Tracing the loop on four points shows it converge. Take $(x,y)=((2,1),+1),((1,-1),+1),((-1,1),-1),((-2,-1),-1)$, and start from $w=(0,0)$, $b=0$. Each row below checks $y_i(w^{\top }{x}_i+b)$, updates on a mistake ($\le 0$), and carries the new weights forward:

A second pass over all four points now finds every product $y_i(w^{\top }{x}_i+b)>0$ (for instance the first point gives $3\cdot 2+0\cdot 1+0=6>0$, the third $-1\cdot (3\cdot (-1))=3>0$), so the loop halts with the separator $w=(3,0)$, $b=0$ — the vertical line $x_1=0$, which cleanly divides the two positive points on the right from the two negatives on the left. Each update moved the boundary exactly toward the point it had misclassified, and because the four points are separable, the mistake bound below guarantees this could not go on forever.

Geometrically the update rotates the boundary toward the missed point. With $y=+1$ but $w^{\top }x<0$, the point $x$ sits on the wrong side; adding $x$ to $w$ swings the weight vector toward $x$, and since the boundary is the hyperplane normal to $w$, it rotates with it until $x$ falls on the correct side.

If the data is linearly separable this rotation cannot continue forever: the number of updates is bounded independently of the data's size.⁴

The bound is worth reading as a rate, not just a finiteness guarantee. For the four-point run above, the points have radius $R={\max }_i\Vert x_i\Vert =\sqrt{5}$ (from $(2,1)$ or $(-2,-1)$), and the separator $x_1=0$ places every point at horizontal distance $1$ or $2$, so the margin is $\gamma =1/\Vert u\Vert$ with the unit normal $u=(1,0)$ giving $\gamma =1$. The bound predicts at most $(R/\gamma {)}^2=5$ updates; the run made just $2$, comfortably inside it. The ratio shows that thin margins (small $\gamma$) are expensive: halving the margin quadruples the worst-case number of updates, which is why the maximum-margin classifiers discussed below deliberately maximize $\gamma$.

The hypothesis is the catch: the data must be linearly separable, and often it is not.

The wall: XOR

Consider four points and the exclusive-or labelling: output $1$ when exactly one input is on.

This is not a quirk of XOR; it is the generic situation. Real data — pixels, phonemes, words — is shot through with such interactions, regions where the useful boundary is curved, folded, disconnected. A single linear layer can never bend.⁵

The fix is composition

The fix is to map the inputs through a nonlinear intermediate layer first, then apply a linear model to that. With one hidden layer of two ReLU units, XOR becomes linearly separable in the new representation — the network learns coordinates in which a straight line does work.

Concretely, take hidden units $h_1=\max (0,x_1+x_2-0)$ and $h_2=\max (0,x_1+x_2-1)$. Pushing all four inputs through gives the hidden coordinates in full:

Both $0$-labelled corners $(0,0)$ and $(1,1)$ land at $h_1-2h_2=0$, while the two $1$-labelled corners collapse onto $h_1-2h_2=1$. The readout weights $(1,-2)$ with a threshold at $\frac{1}{2}$ now split the classes perfectly. In the $(h_1,h_2)$ plane a single line separates them, so the linear readout that failed on the raw inputs succeeds on the learned ones — the nonlinear ReLU folded the plane so that the two diagonals no longer interleave.

That single move, stacked and scaled, is the multilayer perceptron — and the rest of deep learning.⁶

The XOR wall and the kernel escape

The XOR limitation shaped the field's history. Minsky and Papert's Perceptrons (1969) proved exactly the claim above — that a single-layer perceptron cannot represent XOR (or any function that is not linearly separable) — and their book is often blamed for the funding collapse that became the first AI winter. The escape they doubted, a trainable multi-layer network, waited until back-propagation was popularized by Rumelhart, Hinton, and Williams (1986), which supplied the gradient that the perceptron's discrete update could not.

A second, parallel fix for the same limitation is worth knowing. Instead of learning a nonlinear feature map $\varphi$, the kernel trick fixes a map into a very high-dimensional space and works with inner products $K(x,x^{\prime })=\varphi (x{)}^{\top }\varphi (x^{\prime })$ there without ever computing $\varphi$ explicitly. The support vector machine (Cortes and Vapnik, 1995) pairs this with a maximum-margin objective — a principled version of the perceptron's separator that chooses the boundary of largest margin $\gamma$ rather than any separator at all. XOR becomes trivially separable under a quadratic kernel. For two decades SVMs were the dominant method precisely because they, too, broke linear separability; deep learning won out because it learns the representation rather than fixing it in advance, exactly the automation of $\varphi$ that the opening lesson frames as the whole point.⁷⁸