The Perceptron Learning Algorithm
The perceptron is the simplest trainable classifier — a single linear threshold unit. Its learning algorithm adjusts weights only on mistakes, and its convergence theorem is one of the oldest guarantees in machine learning. Its limitation is equally clean: XOR defeats it, and proving that impossible forced the invention of the multi-layer perceptron.
The perceptron model
- — weight vector, normal to the decision hyperplane
- — bias, shifts the boundary off the origin
- Class 1 on the positive side of ; class 0 otherwise
The learning rule and convergence
The update is zero when the prediction is correct (). On a mistake:
- Predicted 0, label 1 (): push toward , increasing .
- Predicted 1, label 0 (): push away from , decreasing .
Convergence theorem. If the data is linearly separable with margin , the perceptron makes at most mistakes before finding a correct separator, where .
Learning OR step by step
With : OR is linearly separable (output 1 when at least one input is 1). Start from , , cycling through the four training points in order :
| Step | Input | Label | Pred | Update | State after |
|---|---|---|---|---|---|
| 1 | 1 | 0 | += , += 1 | ||
| 2 | 1 | 1 | no update | ||
| 3 | 1 | 1 | no update | ||
| 4 | 0 | 1 | -= , -= 1 | ||
| 5 | 1 | 1 | no update |
After step 4, , — boundary . Verify: ✓, ✓, ✓, ✓. Step 5 confirms one clean pass; two more correct passes complete the convergence check. The algorithm has converged in exactly 2 mistakes.
Watch it run — and watch it fail
The same code on both datasets, with the decision boundary redrawn after every update:
The perceptron rule — converging on OR, cycling forever on XOR
OR, with the perceptron starting from w = (0, 0), b = 0 — no boundary at all yet. The rule is deliberately lazy: it only changes the weights when it gets a point wrong, and the change always pushes the boundary toward the misclassified point (or away from it).
Teal = class 1, rose = class 0. A correct separator must put all three teal points on the positive side and the origin on the negative side.
The perceptron learning rule, step by step, with the decision boundary redrawn after every update. On OR it converges in two mistakes, exactly as the convergence theorem promises. Then the same code runs on XOR and never settles — not because the algorithm is broken, but because the four constraints XOR imposes are mutually contradictory. That failure is the reason hidden layers exist.
What to notice as you step:
- The boundary only moves on a mistake. Steps 2–4 and 6–9 change nothing — the perceptron is not doing gradient descent on a loss, it is patching counterexamples.
- The update direction is the input itself. On a false negative, gains , which raises for that exact point. The rule is the shortest possible fix for the mistake in front of it.
- On XOR the weights cycle rather than converge. The algorithm is not stuck or badly tuned — the four constraints below are mutually contradictory, so there is nothing to find. That distinction, between a hard problem and an impossible one, is what the next section proves.
Why XOR is impossible for a single perceptron
XOR outputs 1 when exactly one input is 1:
| XOR | ||
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
Proof by contradiction. Suppose weights and bias correctly classify all four points. The four constraints are:
Add the two "class 1" inequalities:
From the "class 0" constraints: and , so:
This contradicts . No linear separator exists for XOR.
How a hidden layer fixes XOR
A two-layer MLP transforms the inputs so the classes become linearly separable in hidden space. One exact solution (ReLU activations):
Forward pass for every XOR input:
| Input | ||||
|---|---|---|---|---|
The hidden layer maps the two class-1 inputs and to the same hidden representation . In hidden space the four points are with labels — the two class-0 points lie outside a band while the class-1 points coincide, and the single linear classifier separates them exactly. The hidden layer solved the problem by collapsing a geometrically impossible 2D arrangement into a separable one.
import numpy as np
def relu(z): return np.maximum(0, z)
W1 = np.array([[1, 1], [1, 1]], dtype=float)
b1 = np.array([0, -1], dtype=float)
W2 = np.array([[1, -2]], dtype=float)
b2 = 0.0
XOR_inputs = np.array([[0,0],[1,0],[0,1],[1,1]])
XOR_labels = np.array([0, 1, 1, 0])
for x, y in zip(XOR_inputs, XOR_labels):
h = relu(W1 @ x + b1)
y_hat = int((W2 @ h + b2)[0] > 0)
status = "OK" if y_hat == y else "FAIL"
print(f"x={tuple(x.astype(int))} h={tuple(h.astype(int))} y_hat={y_hat} y={y} {status}")
The perceptron's limitations
- Non-separable data: the rule never converges; weights oscillate indefinitely.
- Non-unique solution: the boundary found depends on example ordering and initialization.
- No probabilistic output: the threshold gives a hard 0/1, not a probability.
These motivated: SVMs (find the maximum-margin separator), logistic regression (smooth differentiable loss), and MLPs (hidden layers for non-linear problems).
Related concepts
- XOR, MLPs & Softmax: the full lesson: universal approximation, softmax, cross-entropy
- Logistic Regression: Gradient Derivation: the smooth differentiable loss that replaces the hard threshold
- What is a Neuron?: the single-neuron building block