--- title: Linear Models & the Perceptron module: Foundations moduleNumber: 1 lessonNumber: 3 order: 103 summary: > The simplest learners (linear regression, logistic regression, the perceptron) already contain the whole template: a weighted sum, a loss, a gradient step. They also fail on the XOR problem, which no linear model can solve — the limitation that motivates deep learning. topics: [Foundations] sources: - book: Goodfellow ref: "§5.1, §5.7 — Linear Regression, Logistic Regression" - book: Goodfellow ref: "§6.1 — Example: Learning XOR" --- 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, $$ z = w^\top x + b = \sum_{j=1}^{d} w_j x_j + b, $$ 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: | model | prediction $\hat y$ | output range | per-example loss | gradient $\nabla_w$ | use-case | | --- | --- | --- | --- | --- | --- | | linear regression | $w^\top x$ | $\mathbb{R}$ | $\tfrac12(w^\top x - y)^2$ | $(\hat y - y)\,x$ | real-valued targets | | logistic regression | $\sigma(w^\top x)$ | $(0,1)$ | $-y\log\hat y - (1-y)\log(1-\hat y)$ | $(\hat y - y)\,x$ | class probabilities | | perceptron | $\sign(w^\top x)$ | $\{-1,+1\}$ | $\max(0,\,-y\,w^\top x)$ | $-y\,x$ on a mistake, else $0$ | hard separation | 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.[^gf-linear] ## 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** $$ \hat{R}(w, b) = \frac{1}{n}\sum_{i=1}^n \parens{w^\top x_i + b - y_i}^2. $$ 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 $$ \hat{R}(w) = \tfrac1n \norm{Xw - y}_2^2, \qquad \nabla_w \hat{R} = \tfrac{2}{n}\,X^\top (Xw - y). $$ Setting the gradient to zero and dropping the scalar $\tfrac2n$ gives the _normal equations_ and, when $X^\top X$ is invertible, the closed-form optimum: $$ X^\top (Xw - y) = 0 \;\Longrightarrow\; X^\top X\,w = X^\top y \;\Longrightarrow\; w^\star = (X^\top X)^{-1} X^\top y. $$ 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 = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}$ and $y = (2, 2, 4)^\top$, so $$ X^\top X = \begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix}, \qquad X^\top y = \begin{bmatrix} 8 \\ 18 \end{bmatrix}. $$ Inverting the $2 \times 2$ system (determinant $3 \cdot 14 - 36 = 6$) gives $$ w^\star = (X^\top X)^{-1} X^\top y = \frac{1}{6}\begin{bmatrix} 14 & -6 \\ -6 & 3 \end{bmatrix} \begin{bmatrix} 8 \\ 18 \end{bmatrix} = \frac{1}{6}\begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} 0.67 \\ 1.0 \end{bmatrix}, $$ 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** $$ \sigma(z) = \frac{1}{1 + e^{-z}} \in (0, 1), \qquad \hat{y} = \sigma(w^\top x + b) = p(y = 1 \mid x). $$ $$ % caption: The logistic sigmoid $\sigma(z)=1/(1+e^{-z})$ squashes any score into a % probability in $(0,1)$, saturating at both ends. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} % axes \draw[->, thick] (-3.2,0) -- (3.4,0) node[right, font=\footnotesize] {$z$}; \draw[->, thick] (0,-0.2) -- (0,2.4) node[above, font=\footnotesize] {output}; % gridlines at 1 and 1/2 \draw[black, dashed] (-3.2,2.0) -- (3.2,2.0) node[black, right, font=\footnotesize] {$1$}; \draw[black, dashed] (-3.2,1.0) -- (0,1.0); \node[font=\footnotesize, anchor=east] at (-0.1,1.0) {$\tfrac12$}; % sigmoid curve, scaled to height 2 \draw[acc, very thick] plot[domain=-3.1:3.1, samples=80] (\x, {2/(1+exp(-2*\x))}); \node[acc, font=\footnotesize, anchor=west] at (1.05,1.72) {sigmoid}; \end{tikzpicture} $$ 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'(z) = \sigma(z)(1-\sigma(z))$: $$ \frac{\partial \ell}{\partial \hat y} = -\frac{y}{\hat y} + \frac{1-y}{1-\hat y} = \frac{\hat y - y}{\hat y\,(1-\hat y)}, \qquad \frac{\partial \hat y}{\partial z} = \hat y\,(1-\hat y). $$ The two factors cancel the awkward denominator, and a final $\partial z/\partial w = x$ delivers the same clean residual as least squares: $$ \nabla_w \ell = \underbrace{\frac{\hat y - y}{\hat y(1-\hat y)}}_{\partial\ell/\partial\hat y} \cdot \underbrace{\hat y(1-\hat y)}_{\partial\hat y/\partial z} \cdot \underbrace{x}_{\partial z/\partial w} = (\hat y - y)\,x. $$ 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.[^gf-logistic] 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 $$ \nabla_w \ell = (\hat y - y)\,x = -0.5 \cdot (1, 2) = (-0.5, -1). $$ Descending with learning rate $\eta = 1$ gives $w \gets 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)/\norm{w}$, 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 \tfrac12$. $$ % caption: A linear classifier splits the plane with a hyperplane whose normal is % the weight vector $w$; distance from the boundary sets the confidence. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % decision boundary line \draw[thick] (-0.3,2.7) -- (3.7,-0.5) node[anchor=west, font=\footnotesize, black] {$w^{T} x + b = 0$}; % weight vector normal to boundary (boundary slope ~ -0.8, normal slope ~ 1.25) \coordinate (mid) at (1.7,1.1); \draw[->, acc, very thick] (mid) -- ++(0.95,1.18) node[anchor=south west, font=\footnotesize, text=acc] {$w$}; % positive class (blue) on the w side \foreach \p in {(2.1,2.5),(2.9,2.1),(3.3,2.7),(2.6,3.2)} \fill[acc] \p circle (2.6pt); % negative class (red) on the other side \foreach \p in {(0.3,0.6),(0.9,0.2),(0.4,1.4),(1.2,0.7)} \fill[red] \p circle (2.6pt); \node[acc, font=\footnotesize] at (3.45,1.55) {\texttt{positive}}; \node[red, font=\footnotesize] at (0.1,-0.05) {\texttt{negative}}; \end{tikzpicture} $$ 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.[^gf-perceptron] Drawn as a unit, it is the template every later "neuron" copies — inputs scaled by weights, summed, thresholded: $$ % caption: A single artificial neuron: weighted inputs feed a summation, then an % activation produces the output $\hat y$. \begin{tikzpicture}[>=stealth, font=\small, inp/.style={circle, draw, minimum size=8mm, inner sep=0pt}, op/.style={circle, draw, thick, minimum size=11mm, inner sep=0pt}, act/.style={draw, minimum width=12mm, minimum height=9mm}] \definecolor{acc}{HTML}{2348F2} % input nodes \node[inp] (x1) at (0,1.6) {$x_1$}; \node[inp] (x2) at (0,0) {$x_2$}; \node[inp] (x3) at (0,-1.6) {$x_3$}; % summation node \node[op] (sum) at (3.2,0) {$z$}; % activation \node[act] (act) at (5.7,0) {step}; % output \node (yh) at (8.2,0) {$\hat y$}; % weighted edges \draw[->, acc, thick] (x1) -- (sum) node[pos=0.42, above, font=\footnotesize, text=acc] {$w_1$}; \draw[->, acc, thick] (x2) -- (sum) node[pos=0.5, above, font=\footnotesize, text=acc] {$w_2$}; \draw[->, acc, thick] (x3) -- (sum) node[pos=0.42, below, font=\footnotesize, text=acc] {$w_3$}; % bias \node[font=\footnotesize] (b) at (3.2,1.7) {bias $b$}; \draw[->, thick] (b) -- (sum); % forward edges \draw[->, thick] (sum) -- (act); \draw[->, thick] (act) -- (yh); \end{tikzpicture} $$ 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: $$ \partial_w \max(0,\,-y\,w^\top x) = \begin{cases} -y\,x & \text{if } y\,w^\top x < 0 \quad(\text{mistake}),\\[2pt] 0 & \text{if } y\,w^\top x > 0, \end{cases} $$ so the descent step $w \gets w - \eta\,\partial_w \ell$ with $\eta = 1$ is exactly $w \gets w + y\,x$ on a mistake and a no-op otherwise, the algorithm below. ```algorithm caption: $\textsc{Perceptron}$ — online learning of a linear separator initialize $w \gets 0,\ b \gets 0$ repeat for each example $(x_i, y_i)$ with $y_i \in \{-1, +1\}$ do if $y_i\,(w^\top x_i + b) \le 0$ then // misclassified $w \gets w + y_i\,x_i$ $b \gets b + y_i$ until no mistakes on a full pass return $w, b$ ``` 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: | step | example | $w^\top x + b$ | $y\cdot(\cdot)$ | action | new $(w, b)$ | | --- | --- | --- | --- | --- | --- | | 1 | $(2,1),+1$ | $0$ | $0$ | mistake: $w{+}x,\ b{+}1$ | $((2,1),\ 1)$ | | 2 | $(1,-1),+1$ | $2$ | $2$ | correct: no change | $((2,1),\ 1)$ | | 3 | $(-1,1),-1$ | $0$ | $0$ | mistake: $w{-}x,\ b{-}1$ | $((3,0),\ 0)$ | | 4 | $(-2,-1),-1$ | $-6$ | $6$ | correct: no change | $((3,0),\ 0)$ | 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\cdot2 + 0\cdot1 + 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. $$ % caption: One perceptron update: the step $w \gets w + x$ swings the weight % toward a misclassified point $x$, rotating the boundary so $x$ becomes correct. \begin{tikzpicture}[>=stealth, font=\small, scale=1.15] \definecolor{acc}{HTML}{2348F2} \definecolor{green}{HTML}{1F9D4D} \definecolor{red}{HTML}{C0392B} \coordinate (O) at (0,0); % --- OLD state --- % old weight w = (-1, 2); old boundary perpendicular to w, direction (2,1) \draw[black, dashed, thick] (-2.2,-1.1) -- (2.2,1.1) node[anchor=south west, font=\footnotesize, text=black] {old boundary}; \draw[->, black, very thick] (O) -- (-1,2) node[anchor=south east, font=\footnotesize, text=black] {$w$}; % misclassified positive point x = (2.4,-0.6): w . x = -3.6 < 0 (wrong side) \fill[red] (2.4,-0.6) circle (2.8pt); \node[red, font=\footnotesize, anchor=west] at (2.55,-0.6) {$x$ (\texttt{label} +1)}; % --- the added vector: translate x to the tip of w to show w + x --- \draw[->, red, thick, dashed] (-1,2) -- (1.4,1.4) node[pos=0.5, above, font=\footnotesize, text=red] {$+\,x$}; % --- NEW state --- % new weight w' = w + x = (1.4, 1.4) \draw[->, green, very thick] (O) -- (1.4,1.4) node[anchor=south west, font=\footnotesize, text=green] {$w + x$}; % new boundary perpendicular to w' = (1.4,1.4), direction (-1,1) \draw[green, thick] (1.5,-1.5) -- (-1.5,1.5) node[anchor=south east, font=\footnotesize, text=green] {new boundary}; % x now correct under w': w' . x = 2.52 > 0 \node[green, font=\footnotesize, anchor=north west] at (1.55,-1.45) {$x$ now correct}; \end{tikzpicture} $$ If the data is linearly separable this rotation cannot continue forever: the number of updates is bounded independently of the data's size.[^gf-mistake] > **Theorem (Perceptron mistake bound).** Let the training data satisfy > $\norm{x_i} \le R$ and be separable with margin $\gamma > 0$: there exists > a unit vector $u$, $\norm{u} = 1$, with $y_i\,(u^\top x_i) \ge \gamma$ for > all $i$. Then the perceptron makes at most $(R/\gamma)^2$ updates before it stops > making mistakes. > **Proof.** Track $w$ across the mistakes only; let $w_k$ be the weight after the > $k$-th update, $w_0 = 0$. On a mistake at $(x,y)$ we have $w_{k} = w_{k-1} + y\,x$. > _Alignment grows linearly._ Taking the inner product with the separator $u$, > $u^\top w_k = u^\top w_{k-1} + y\,(u^\top x) \ge u^\top w_{k-1} + \gamma$, so by > induction $u^\top w_k \ge k\gamma$. _Norm grows at most as $\sqrt{k}$._ Because the > example was a mistake, $y\,(w_{k-1}^\top x) \le 0$, hence > $\norm{w_k}^2 = \norm{w_{k-1}}^2 + 2y\,(w_{k-1}^\top x) + \norm{x}^2 > \le \norm{w_{k-1}}^2 + R^2$, giving $\norm{w_k}^2 \le kR^2$. Combining, > and using Cauchy–Schwarz $u^\top w_k \le \norm{w_k}$ since $\norm{u}=1$, > > $$ > k\gamma \;\le\; u^\top w_k \;\le\; \norm{w_k} \;\le\; \sqrt{k}\,R > \;\Longrightarrow\; > k\gamma \le \sqrt{k}\,R > \;\Longrightarrow\; > k \le (R/\gamma)^2. > $$ > > The mistake count cannot exceed $(R/\gamma)^2$, so the algorithm terminates. $\qed$ 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 \norm{x_i} = \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/\norm{u}$ 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. $$ % caption: XOR is not linearly separable: its two output classes sit on opposite % diagonals, so any straight line strands a blue and a red point together. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % axes \draw[->, thick] (-0.5,0) -- (3.4,0) node[right, font=\footnotesize] {$x_1$}; \draw[->, thick] (0,-0.5) -- (0,3.4) node[above, font=\footnotesize] {$x_2$}; % two failed separating lines (dashed): neither works \draw[black, dashed, thick] (-0.35,1.7) -- (3.1,1.05); \draw[black, dashed, thick] (1.05,-0.35) -- (1.7,3.1); % output 0 (blue): (0,0) and (1,1) \fill[acc] (0,0) circle (3.6pt); \fill[acc] (2.5,2.5) circle (3.6pt); \node[acc, font=\footnotesize, anchor=north east] at (-0.08,-0.08) {(0, 0)}; \node[acc, font=\footnotesize, anchor=south west] at (2.62,2.58) {(1, 1)}; % output 1 (red): (0,1) and (1,0) \fill[red] (0,2.5) circle (3.6pt); \fill[red] (2.5,0) circle (3.6pt); \node[red, font=\footnotesize, anchor=south east] at (-0.12,2.62) {(0, 1)}; \node[red, font=\footnotesize, anchor=north west] at (2.62,-0.1) {(1, 0)}; \end{tikzpicture} $$ > **Claim.** No linear model can compute XOR. > **Proof.** A linear classifier outputs one label on each side of the line > $w^\top x + b = 0$. XOR's two "$1$" points $(0,1), (1,0)$ lie on a diagonal, > and its two "$0$" points $(0,0), (1,1)$ lie on the _other_ diagonal — the two > classes interleave. Any straight line splits the plane into two halves; by the > pigeonhole principle one half must contain points of both classes, which the > linear model then labels identically. So at least one point is wrong. $\qed$ 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.[^gf-xor] ## 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: | input $(x_1, x_2)$ | label | $h_1 = \max(0, x_1{+}x_2)$ | $h_2 = \max(0, x_1{+}x_2{-}1)$ | readout $h_1 - 2h_2$ | | --- | --- | --- | --- | --- | | $(0, 0)$ | $0$ | $0$ | $0$ | $0$ | | $(1, 1)$ | $0$ | $2$ | $1$ | $0$ | | $(0, 1)$ | $1$ | $1$ | $0$ | $1$ | | $(1, 0)$ | $1$ | $1$ | $0$ | $1$ | 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 $\tfrac12$ 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. $$ % caption: XOR in the learned hidden space. The two $0$-corners collapse onto one % point and the two $1$-corners onto another, so a single line (green) separates % the classes that no line could separate in the raw input. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \definecolor{green}{HTML}{1F9D4D} % hidden coords: (0,0)->(0,0), (1,1)->(2,1) are class 0; (0,1)&(1,0)->(1,0) class 1 % scale by 1.1 for drawing room \draw[->, thick] (-0.5,0) -- (3.4,0) node[right, font=\footnotesize] {$h_1$}; \draw[->, thick] (0,-0.6) -- (0,2.8) node[above, font=\footnotesize] {$h_2$}; % class 0: (0,0) and (2.2,1.1) -- both satisfy h1 = 2 h2 \fill[acc] (0,0) circle (3.4pt); \fill[acc] (2.2,1.1) circle (3.4pt); \node[acc, font=\footnotesize, anchor=west] at (0.35,2.3) {blue: class 0}; % class 1: (1.1,0) -- h1 = 2 h2 + 1.1 \fill[red] (1.1,0) circle (3.4pt); \node[red, font=\footnotesize, anchor=north] at (1.1,-0.12) {class 1}; % separating line h1 - 2 h2 = 0.55 -> h2 = (h1 - 0.55)/2, drawn across the frame \draw[green, very thick] (0.55,0) -- (3.2,1.325) node[anchor=south east, font=\footnotesize, text=green] {separable}; \end{tikzpicture} $$ That single move, stacked and scaled, is the [multilayer perceptron](/deep-learning/neural-networks/the-multilayer-perceptron) — and the rest of deep learning.[^chollet-mlp] ## 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 $\phi$, the **kernel trick** fixes a map into a very high-dimensional space and works with inner products $K(x, x') = \phi(x)^\top \phi(x')$ there without ever computing $\phi$ 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 $\phi$ that the [opening lesson](/deep-learning/foundations/what-is-deep-learning) frames as the whole point.[^minsky][^svm] [^gf-linear]: **Goodfellow**, _Deep Learning_, §5.1.4 — linear regression as the worked example of a learning algorithm: the squared-error objective, its closed-form normal-equations solution, and the residual gradient every later model inherits. [^gf-logistic]: **Goodfellow**, _Deep Learning_, §5.7.2; §6.2.2.2 — logistic regression and sigmoid output units: binary cross-entropy as the maximum-likelihood loss and the $(\hat y - y)\,x$ gradient shared across the exponential family. [^gf-perceptron]: **Goodfellow**, _Deep Learning_, §1.2.1; §6.1 — the perceptron in historical context: Rosenblatt's threshold unit as the ancestor of the modern artificial neuron, and the mistake-driven update rule. [^gf-mistake]: **Goodfellow**, _Deep Learning_, §5.9 — linear separability and convergence: a margin $\gamma$ and radius $R$ bound the perceptron's mistakes by $(R/\gamma)^2$, independent of sample size, when the data is separable. [^gf-xor]: **Goodfellow**, _Deep Learning_, §6.1 — Example: Learning XOR: the canonical proof that no linear model computes XOR, and the motivation for a nonlinear hidden layer. [^chollet-mlp]: **Chollet**, _Deep Learning with Python_, §2.3; §3.1 — stacking a nonlinear hidden layer to learn a representation in which the problem becomes linearly separable, the move that defines the multilayer perceptron. [^minsky]: Minsky and Papert (1969), _Perceptrons_, MIT Press — the proof that a single-layer perceptron cannot compute non-linearly-separable functions such as XOR; and Rumelhart, Hinton, Williams (1986), _Learning representations by back-propagating errors_, Nature 323, which supplied the gradient training the multi-layer network the critique had ruled out. [^svm]: Cortes and Vapnik (1995), _Support-Vector Networks_, Machine Learning 20 — the maximum-margin classifier and the kernel trick, the pre-deep-learning route to non-linear separation by a fixed high-dimensional feature map rather than a learned one.