Perceptron

The perceptron is the simplest learning algorithm in machine learning: a single artificial neuron that classifies points with a straight line and corrects that line every time it misclassifies one. On linearly separable data it provably converges after a bounded number of updates; on data like XOR it provably never converges at all.

Picture a bouncer running a velvet rope across a courtyard, VIPs on one side, everyone else on the other. The bouncer has no plan and no taste — only a rule: whenever a guest ends up on the wrong side of the rope, that guest gets to grab it and yank it toward themselves. That is the entire perceptron. The displayed rule needs only the signed margin and an additive correction; it can also be interpreted through a perceptron loss, though this lesson does not derive that view. Just "wrong? yank." The astonishing part, proved in 1962 and demolished for one famous case in 1969, is that this can be enough — and exactly when it isn't.

How the Perceptron Works

A point x = (x₁, x₂) gets a score, w·x + b, and the perceptron reads only its sign: positive side of the rope, predict +1; negative side, predict -1. The weights w are the rope's normal vector — w points at the positive side — and b slides the rope away from the origin. Change the direction of w and the rope swings (scaling w alone leaves it where it is); change b and it shifts.

Training visits the points in a fixed order, over and over. Each visit is one check: a point with true label y is a mistake when y · score ≤ 0. Mind the ≤ — a point sitting exactly on the rope counts as wrong, whichever label it carries. That tie rule is what bootstraps learning: the run starts at w = (0, 0), b = 0, where every score is 0, so the very first check of every run is guaranteed to be a mistake and the first yank always fires.

The yank itself is one move: w ← w + y·x and b ← b + y. A misclassified positive point adds itself to the weights, pulling the rope's normal toward it; a misclassified negative point subtracts itself, pushing the rope away. The animation draws this literally — the pull y·x attaches tip-to-tail to w, and the boundary swings to its new pose. Correct points change nothing.

One detail that looks like a simplification but isn't: the learning rate is fixed at η = 1. Starting from w = 0, every state the run ever reaches is just a sum of the mistakes so far, so scaling η scales (w, b) by a constant — and a positive constant scale never flips the sign of any score. A different η changes the printed numbers and not one single prediction. It is not a knob worth turning, which is why the config panel doesn't offer it.

The run ends when a full pass over the data makes zero mistakes. At that moment the rope separates the classes, and every future pass would do nothing.

Perceptron Step by Step

The default Separable dataset has 8 points: four labeled +1 (indigo) in an upper arc, four labeled -1 (magenta) below, visited in index order, starting from w = (0, 0), b = 0.

Pass 1 — 3 mistakes. Point 0 is (4, 2) with label +1: its score is exactly 0, the tie rule calls it a mistake, and the first yank lands — w = (4, 2), b = 1. The boundary appears. Point 1 at (-2, -3), label -1, scores -13: correct, no change. Point 2 at (-4, 2), label +1, scores -11 — wrong side. It yanks: w = (0, 4), b = 2, and the rope swings nearly horizontal. Point 3 at (3, 0), label -1, scores 2 — also wrong. Another yank: w = (-3, 4), b = 1. Points 4 through 7 all check out (scores 11, -17, 19, -12).

Pass 2 — 2 mistakes, and both are repeat offenders. Point 0 scores -3 now — the pass-1 fixes for points 2 and 3 broke it — so it yanks again: w = (1, 6), b = 2. Point 3 scores 5 and forces a second correction: w = (-2, 6), b = 1. The other six points pass clean.

Pass 3 — all eight scores carry the right sign, the pass ledger commits a zero, and the run converges at w = (-2, 6), b = 1 after 5 updates total. Notice who complained twice: points 0 and 3, the two crowding the rope (point 2 complained once). Margins are expensive exactly where guests stand close to the line.

When the Perceptron Converges — and Why XOR Breaks It

The convergence theorem is the reason this algorithm matters. For the bias-updating rule here, augment each input as (x, 1) and the parameters as (w, b). If a unit separator gives every augmented example signed margin at least γ > 0, and augmented input norms are at most R, the standard bound is (R/γ)² updates. These augmented-space quantities are not simply the displayed 2-D boundary distance and radius. Read that bound again: it does not mention n. You pay for the width of the aisle between the classes, not for the size of the crowd. The Narrow margin preset makes this tangible — same 8-point size, same bounding box, same rule, but its thin aisle costs passes of 8, 5, 0 mistakes (13 updates) where the default's wide one costs 3, 2, 0 (5 updates).

And when no separating line exists, the rule never stops — and on integer data it fails in a way you can actually watch. For this XOR fixture, the same parameter state repeats at a pass boundary. With the same visit position and deterministic updates, that repeat proves a cycle; nonseparability alone does not establish bounded weights or a cycle for every dataset. The XOR preset shows this with four guests at four corners, diagonals sharing a label — a configuration no straight rope can honor. Run it and read the pass ledger: pass 2 ends in precisely the state that ended pass 1, so passes 3, 4, 5, and every later pass are foregone conclusions. You haven't watched it fail to converge; you've proved it never will.

This is the limit Minsky and Papert published in 1969 — one line cannot cut the XOR pattern — and illustrates the representational limitation later addressed by multi-layer networks trained with backpropagation dissolved it. One hidden layer is enough to carve the plane into regions no single rope can.

A simplification, named: the animation's "cycles forever" verdict is the visualization's bookkeeping — it watches pass-end states and flags the first repeat. A basic perceptron trainer has no such detector; it just exhausts its pass budget. Same update rule, one extra pair of eyes.

Edge Cases

• score = 0 is a mistake by the ≤ in the rule, for whichever label the point carries — there is no neutral zone on the rope itself.
• w = (0, 0) means no boundary exists: every point scores b, which is 0 here. True at init, and briefly true mid-run on the XOR preset, where the canvas honestly shows the boundary vanishing.
• The same point can force updates in several passes — points 0 and 3 each yank twice in the default run. Every pull overshoots or undershoots until the geometry finally accommodates everyone.
• Visit order changes the trajectory. The separable-data update bound does not require this fixed order, provided violated examples continue to be processed. A zero-error pass is impossible for XOR, but the particular repeated-state cycle shown here depends on the deterministic visit order.

Common Mistakes

• Believing convergence means a good line. The theorem guarantees a separator, not the widest one — the default run's final line hugs the negative class. Maximizing the margin is a different algorithm (the SVM).
• Blaming the learning rate for XOR. No η converges there; the failure is the data's geometry, not the step size. From w = 0, η doesn't even change predictions.
• Over-generalizing the bound. (R/γ)² counts updates, not passes, and only exists when the data is separable.
• Forgetting the tie rule. Implementing the mistake test as sign(score) ≠ y instead of y·score ≤ 0 leaves the all-zero start scoring every point as a tie and, depending on your sign convention, never firing the first update.