A perceptron is a hyperplane that moves toward every point it misclassifies, and it converges only if such a hyperplane exists.
One unit, one hyperplane, and a rule that moves it toward every point it gets wrong.
How this chapter is built
M3Load-bearing
The content is mathematics. Understanding is demonstrated by computation, not recall.
basics11/11what the words mean
concept2/2what to picture
theory4/4why it works, and when it does not
mathematics15/15derive it, then compute it
practice9/9build it, break it, read the papers
Five strands, not one. Mathematics is the spine; the other four are the body. A chapter cannot pay its way out of teaching with problems, nor out of problems with teaching.
The reader now knows a model is a parameterised function, but has seen no procedure that changes the parameters. The perceptron is the smallest thing that is genuinely a learning machine: its rule fits on one line, its convergence is a theorem with a proof short enough to write out, and its single failure — XOR — is the reason every remaining chapter of this book exists.
Fig. 2 — One unit: a weighted sum, a bias, and an activation. Everything before the activation is affine, and affine maps compose into a single affine map.
What this chapter covers
The perceptron
Weight vector and bias
Decision boundary
Signed distance and margin
Linear separability
The perceptron learning rule
The convergence theorem
XOR
Apparatus
The mathematics this chapter leans on, held in Book 0 so it can be assumed here without being taught here. Not a gate — follow a link when a step stops making sense.
A perceptron is a function ŷ = sign(⟨w, x⟩ + b) with w ∈ ℝᵈ and b ∈ ℝ. It partitions ℝᵈ into two half-spaces and assigns one label to each. It is the smallest object in Elementa that both computes and learns.
WA weight matrix
bA bias vector
Definition 2Decision boundary
The decision boundary of a perceptron is the set { x : ⟨w, x⟩ + b = 0 }. It is a hyperplane: a flat set of dimension d − 1. In two dimensions it is a line, in three a plane, and in every dimension it is the only shape a perceptron can draw.
Definition 3Signed distance
The signed distance from a point x to the boundary is (⟨w, x⟩ + b)/‖w‖. Its magnitude is the Euclidean distance and its sign is the predicted class, so one number carries both the decision and the confidence in it.
Definition 4Functional margin
The functional margin of an example (x, y) with y ∈ {−1, +1} is y(⟨w, x⟩ + b). It is positive exactly when the prediction is correct, so the whole learning rule can be written as a condition on its sign.
Definition 5Geometric margin
The geometric margin of a dataset under (w, b) is the smallest signed distance of any correctly classified point, γ = minᵢ yᵢ(⟨w, xᵢ⟩ + b)/‖w‖. Unlike the functional margin it does not change when w and b are both rescaled.
Definition 6Linear separability
A labelled set is linearly separable when some (w, b) gives every example a positive functional margin. Separability is a property of the data, not of the algorithm, and no learning rule creates it.
Definition 7The perceptron learning rule
On an example with margin ≤ 0, update w ← w + y x and b ← b + y; otherwise change nothing. The rule touches the parameters only when it is wrong, which is why a run on already-separated data terminates immediately.
Definition 8Mistake bound
A mistake bound is a cap on the total number of updates an online algorithm makes, valid for any presentation order of the data. It is not a bound on running time or on epochs, and it says nothing about the quality of the solution reached.
Formal results
I.2.T1
Perceptron convergence theorem (Novikoff, 1962)
If a dataset with ‖xᵢ‖ ≤ R for all i is separable with geometric margin γ > 0, then the perceptron learning rule makes at most (R/γ)² updates before classifying every example correctly — whatever order the examples arrive in, and whatever the initialisation scale.
What this does not promise
It promises nothing at all for non-separable data, where the rule does not terminate and cycles indefinitely — and there is no way to distinguish that case from slow convergence by watching it run. It also does not promise a maximum-margin solution: the hyperplane returned is merely the first one that happens to separate, and can sit arbitrarily close to a training point. Finally, the bound is on mistakes, not on epochs or wall-clock time.
I.2.T2
The XOR impossibility
No perceptron computes XOR on {0,1}². The four required inequalities are jointly inconsistent, so the failure is not one of training, initialisation or data volume — it is a property of the hypothesis class.
What this does not promise
It does not say XOR is hard. Two hidden units solve it exactly, with weights that can be written down by hand (I.5.B04). Nor does it generalise to a claim that linear models are weak: with a feature map that adds the product x₁x₂, XOR becomes linearly separable in three dimensions. The impossibility is relative to a fixed representation, and choosing the representation is the escape.
Assumptions
Each is paired with the problem that shows what its removal costs. An assumption nobody tests is a disclaimer.
The data is linearly separable, so a hyperplane with positive margin exists.I.2.X07
The margin γ is bounded away from zero, so the mistake bound is finite.I.2.X08
On non-separable data the rule never halts. Give it the four XOR points and it cycles forever, revisiting the same weight vectors with period 4; after ten thousand epochs the training accuracy is still 75% and the weights are back where they were at epoch 2. Nothing in the run distinguishes this from a hard but solvable problem.
Near-separable data makes the bound useless. Move one point of a separable set until γ falls from 0.5 to 0.01 with R = 1: the mistake bound rises from 4 to 10,000. The problem is visually unchanged and the guarantee has become vacuous.