The Perceptron Learning AlgorithmOpen in Colab

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

y^=1[w⊤x+b>0]\hat{y} = \mathbb{1}[\mathbf{w}^\top \mathbf{x} + b > 0]
  • w∈Rd\mathbf{w} \in \mathbb{R}^d — weight vector, normal to the decision hyperplane
  • b∈Rb \in \mathbb{R} — bias, shifts the boundary off the origin
  • Class 1 on the positive side of w⊤x+b=0\mathbf{w}^\top \mathbf{x} + b = 0; class 0 otherwise

The learning rule and convergence

w←w+η (y−y^) x,b←b+η (y−y^)\mathbf{w} \leftarrow \mathbf{w} + \eta\,(y - \hat{y})\,\mathbf{x}, \qquad b \leftarrow b + \eta\,(y - \hat{y})

The update is zero when the prediction is correct (y=y^y = \hat{y}). On a mistake:

  • Predicted 0, label 1 (y−y^=+1y - \hat{y} = +1): push w\mathbf{w} toward x\mathbf{x}, increasing w⊤x+b\mathbf{w}^\top\mathbf{x} + b.
  • Predicted 1, label 0 (y−y^=−1y - \hat{y} = -1): push w\mathbf{w} away from x\mathbf{x}, decreasing w⊤x+b\mathbf{w}^\top\mathbf{x} + b.

Convergence theorem. If the data is linearly separable with margin γ>0\gamma > 0, the perceptron makes at most R2/γ2R^2/\gamma^2 mistakes before finding a correct separator, where R=max⁡i∥xi∥R = \max_i \lVert \mathbf{x}_i \rVert.

Learning OR step by step

With η=1\eta = 1: OR is linearly separable (output 1 when at least one input is 1). Start from w=(0,0)\mathbf{w} = (0, 0), b=0b = 0, cycling through the four training points in order (1,1),(1,0),(0,1),(0,0)(1,1),(1,0),(0,1),(0,0):

StepInput (x1,x2)(x_1, x_2)LabelPredUpdateState after
1(1,1)(1, 1)10w\mathbf{w} += (1,1)(1,1), bb += 1w=(1,1), b=1\mathbf{w}=(1,1),\ b=1
2(1,0)(1, 0)11no updatew=(1,1), b=1\mathbf{w}=(1,1),\ b=1
3(0,1)(0, 1)11no updatew=(1,1), b=1\mathbf{w}=(1,1),\ b=1
4(0,0)(0, 0)01w\mathbf{w} -= (0,0)(0,0), bb -= 1w=(1,1), b=0\mathbf{w}=(1,1),\ b=0
5(1,1)(1, 1)11no updatew=(1,1), b=0\mathbf{w}=(1,1),\ b=0

After step 4, w=(1,1)\mathbf{w} = (1,1), b=0b = 0 — boundary x1+x2=0x_1 + x_2 = 0. Verify: (0,0)→0(0,0)\to 0 ✓, (1,0)→1(1,0)\to 1 ✓, (0,1)→1(0,1)\to 1 ✓, (1,1)→2(1,1)\to 2 ✓. 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

1/12

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).

python
1def train(data, epochs, eta=1.0):
2 w, b = [0.0, 0.0], 0.0
3 for _ in range(epochs):
4 for x, y in data:
5 z = w[0]*x[0] + w[1]*x[1] + b
6 pred = 1 if z > 0 else 0
7 err = y - pred
8 if err == 0:
9 continue # correct: no update
10 # push the boundary toward x (or away)
11 w[0] += eta * err * x[0]
12 w[1] += eta * err * x[1]
13 b += eta * err
14 return w, b
state
OR — labels shown on each point
-0.61.61.6-0.61110x₁x₂
state
w₁ → 0w₂ → 0b → 0

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, w\mathbf{w} gains x\mathbf{x}, which raises w⊤x\mathbf{w}^\top\mathbf{x} 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:

x1x_1x2x_2XOR
000
101
011
110

Proof by contradiction. Suppose weights w1,w2w_1, w_2 and bias bb correctly classify all four points. The four constraints are:

b≤0((0,0)→0)b \le 0 \tag{$(0,0) \to 0$} w1+b>0((1,0)→1)w_1 + b > 0 \tag{$(1,0) \to 1$} w2+b>0((0,1)→1)w_2 + b > 0 \tag{$(0,1) \to 1$} w1+w2+b≤0((1,1)→0)w_1 + w_2 + b \le 0 \tag{$(1,1) \to 0$}

Add the two "class 1" inequalities:

(w1+b)+(w2+b)>0  ⟹  w1+w2+2b>0.(w_1 + b) + (w_2 + b) > 0 \implies w_1 + w_2 + 2b > 0.

From the "class 0" constraints: b≤0b \le 0 and w1+w2≤−bw_1 + w_2 \le -b, so:

w1+w2+2b≤(−b)+2b=b≤0.w_1 + w_2 + 2b \le (-b) + 2b = b \le 0.

This contradicts w1+w2+2b>0w_1 + w_2 + 2b > 0. 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):

W1=[1111],b1=[0−1],W2=[1−2],b2=0\mathbf{W}_1 = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}, \quad \mathbf{b}_1 = \begin{bmatrix} 0 \\ -1 \end{bmatrix}, \quad \mathbf{W}_2 = \begin{bmatrix} 1 & -2 \end{bmatrix}, \quad b_2 = 0

Forward pass for every XOR input:

Inputz1=W1x+b1\mathbf{z}_1 = \mathbf{W}_1\mathbf{x} + \mathbf{b}_1h=ReLU(z1)\mathbf{h} = \text{ReLU}(\mathbf{z}_1)z2=W2h+b2z_2 = \mathbf{W}_2\mathbf{h} + b_2y^\hat{y}
(0,0)(0,0)(0, −1)(0,\ {-1})(0, 0)(0,\ 0)0000
(1,0)(1,0)(1, 0)(1,\ 0)(1, 0)(1,\ 0)1111
(0,1)(0,1)(1, 0)(1,\ 0)(1, 0)(1,\ 0)1111
(1,1)(1,1)(2, 1)(2,\ 1)(2, 1)(2,\ 1)0000

The hidden layer maps the two class-1 inputs (1,0)(1,0) and (0,1)(0,1) to the same hidden representation (1,0)(1, 0). In hidden space the four points are (0,0),(1,0),(1,0),(2,1)(0,0),(1,0),(1,0),(2,1) with labels 0,1,1,00,1,1,0 — the two class-0 points lie outside a band while the class-1 points coincide, and the single linear classifier h1−2h2>0h_1 - 2h_2 > 0 separates them exactly. The hidden layer solved the problem by collapsing a geometrically impossible 2D arrangement into a separable one.

Python
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

  1. Non-separable data: the rule never converges; weights oscillate indefinitely.
  2. Non-unique solution: the boundary found depends on example ordering and initialization.
  3. 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

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
The Perceptron Learning AlgorithmLogistic Regression: Grad…XOR, MLPs & SoftmaxWhat is a Neuron?