The Perceptron Algorithm

Most model fitting starts by writing down a loss over the whole dataset and then minimising it. The perceptron does not. It walks through the examples one at a time, makes a call on each, and only touches its weights when it gets one wrong — and even then it makes the smallest sensible correction, aimed squarely at the example that just embarrassed it. There is no loss surface to picture and no matrix to invert. It is the shortest path from "here is some labelled data" to "here is a classifier", and everything from stochastic gradient descent to neural networks inherits its shape.

Think of a trainee marking each trade as good or bad before the outcome is known. Their supervisor says nothing when the call is right. When it is wrong, the supervisor points at the trade and says "that one — lean more toward its features next time". The trainee does not rewrite their whole framework; they shift it slightly in the direction of the example they missed. Repeat, and the calls stop being wrong.

The rule

The model is a weighted score. Each feature $x_j$ gets a weight $w_j$ saying how much it counts, and a bias $b$ shifts the whole thing up or down. The prediction is the sign of

$$f(x) \;=\; w \cdot x + b$$

Positive means class $+1$, negative means class $-1$. So the boundary is the flat surface where the score is exactly zero, and $w$ is the arrow pointing perpendicular to it, toward the positive side.

Labels are written $y = +1$ or $y = -1$ rather than 1 and 0 for one reason: the single quantity $y \, f(x)$ then tells you everything. It is positive when the call was right and negative when it was wrong. The algorithm is one line:

$$\text{if } y_i\,f(x_i) \le 0: \qquad w \leftarrow w + y_i x_i, \qquad b \leftarrow b + y_i$$

In plain English: if this example is on the wrong side, add its own feature vector to the weights when it should have been positive, and subtract it when it should have been negative. Nothing happens on correct predictions.

Why does that help? Recompute the score for the same example straight after an update:

$$y_i\big(w_{\text{new}} \cdot x_i + b_{\text{new}}\big) \;=\; y_i\big(w \cdot x_i + b\big) \;+\; \lVert x_i \rVert^2 + 1$$

In plain English: the update moves that example's score in the right direction by an amount equal to its own squared length plus one. It might not be enough to flip the call in one go, but it never moves the wrong way.

Worked example 1: three updates by hand

Four labelled examples in two dimensions:

point	$x$	$y$
A	$(2, 1)$	$+1$
B	$(0, -1)$	$-1$
C	$(1, -1)$	$-1$
D	$(-1, 2)$	$+1$

Start at $w = (0,0)$, $b = 0$, and treat a score of exactly zero as a mistake.

A. Score $= 0$, so $y f = 0 \le 0$: mistake. Add $+1 \times (2,1)$ to the weights and $+1$ to the bias. Now $w = (2,1)$, $b = 1$.

B. Score $= 2(0) + 1(-1) + 1 = 0$, so another mistake. Subtract $(0,-1)$ and subtract 1: $w = (2, 2)$, $b = 0$.

C. Score $= 2(1) + 2(-1) + 0 = 0$: mistake again. Subtract $(1,-1)$ and subtract 1: $w = (1, 3)$, $b = -1$.

D. Score $= 1(-1) + 3(2) - 1 = 4$, and $y = +1$, so $yf = 4 > 0$. Correct. No update.

Now run a second pass with the same weights and check all four: A scores $2 + 3 - 1 = 4$ (correct), B scores $-3 - 1 = -4$ (correct, since $y = -1$), C scores $1 - 3 - 1 = -3$ (correct), D scores 4 (correct). A full sweep with no mistakes means the algorithm has stopped. The final rule is $x_1 + 3x_2 - 1 > 0$, found in three updates and six passes' worth of arithmetic you can do on a napkin.

Worked example 2: how many mistakes can it make?

The convergence guarantee has two ingredients. $R$ is the length of the longest example — how far out the data reaches. $\gamma$ is the margin: fold the bias into the features by appending a 1 to every $x$, find the unit-length weight vector that separates the data best, and $\gamma$ is the smallest score it gives any example. The Perceptron Convergence Theorem then says the algorithm makes at most $(R/\gamma)^2$ mistakes, no matter how the examples are ordered.

For the four points above, the augmented vectors are $(2,1,1)$, $(0,-1,1)$, $(1,-1,1)$ and $(-1,2,1)$, with lengths $\sqrt{6}$, $\sqrt{2}$, $\sqrt{3}$, $\sqrt{6}$. So $R = \sqrt{6}$ and $R^2 = 6$.

Use the separator the algorithm actually found, $(1, 3, -1)$, whose length is $\sqrt{11} = 3.317$. Its raw scores on the four points are 4, 4, 3, 4, so the smallest is 3 and the margin is $\gamma = 3 / \sqrt{11} = 0.905$. The mistake bound is

$$\left(\frac{R}{\gamma}\right)^{2} \;=\; \frac{6}{0.818} \;=\; 7.33$$

so at most seven mistakes. We made three. The bound is honest but loose, which is typical — and notice what is not in it: the number of features, and the number of examples. A perceptron on a million rows in a thousand dimensions makes the same bounded number of mistakes, provided the margin holds up.

What this means in practice

The perceptron is rarely the model you ship, but its shape is everywhere.

It is online: it consumes one example, updates, and forgets it. That suits a live signal that must absorb today's fill without refitting on ten years of history, and it is the ancestor of every Stochastic Gradient Descent variant, which is the same "look at a bit of data, take a step" idea with a proper loss attached.

It finds a separator, not the best one. Where an SVM picks the widest corridor, the perceptron stops the moment nothing is wrong, so its boundary can sit right up against a training point and generalise poorly. The averaged perceptron — keep a running mean of every weight vector you passed through and predict with that — recovers much of the lost stability for almost no extra code.

Its output is a signed distance with no calibration behind it. A score of 4 is not "80 percent confident"; feeding it into a sizing rule as though it were a probability is a real and common error. Use Logistic Regression when you need probabilities.