Perceptron

Update w ← w + y·x on every mistake; if the classes are linearly separable, it converges in finitely many steps.

16 min read1561 wordscore20 viewsupdated 2026-10-07

Definition

The perceptron is a linear classifier y^=sign⁡(w⋅x+b)\hat y=\operatorname{sign}(w\cdot x+b) trained by one rule: go through the examples, and whenever one is on the wrong side of the line, add y xy\,x to the weights. Correctly classified examples are ignored. Rosenblatt proposed it in 1957. It was the first learning algorithm that came with a proof that it works, and it is the ancestor of every neural network.

At a glance

Task
Binary classification (labels y∈{−1,+1}y\in\{-1,+1\}); multiclass by extension
Input → output
feature vector x∈Rdx\in\mathbb{R}^d → a hard label ±1\pm1 (no probability)
Learns
a weight vector w∈Rdw\in\mathbb{R}^d and a bias bb; the boundary is the hyperplane w⋅x+b=0w\cdot x+b=0
Training
O(n d)O(n\,d) per epoch (one pass over the data); on separable data at most (R/γ)2(R/\gamma)^2 updates in total
Prediction
O(d)O(d): one dot product and a sign
Hyperparameters
number of epochs, data order / shuffling, learning rate η (usually irrelevant), optional regularization and early stopping
Assumes
for convergence: the classes are linearly separable. Nothing is assumed about distributions

The problem

In 1943 McCulloch and Pitts described an artificial neuron as a threshold unit: add up weighted inputs and fire if the sum is above a threshold. Such a unit can compute AND, OR and NOT, but its weights had to be set by hand. The open question was how a machine could find the weights by itself, just from labelled examples.

Least squares was the obvious tool, but it solves a different problem. Regressing the ±1\pm1 labels on xx minimizes squared error, so a point that is correctly classified but far from the line still has a large residual and pulls the line toward itself. The fit can end up misclassifying points even when a perfect line exists. What we want is a rule that only reacts to errors, works one example at a time (the data may arrive as a stream), and is guaranteed to find a separating line whenever one exists. The perceptron is that rule.

The idea

The score s=w⋅x+bs=w\cdot x+b says which side of the line xx is on: positive means class +1+1, negative means class −1-1. A point is classified correctly exactly when yy and ss have the same sign, i.e. when y s>0y\,s>0. When a point is wrong, nudge ww so that its score moves toward the correct sign. Adding xx to ww raises the score of xx; subtracting xx lowers it. Both cases are covered by "add y xy\,x". Geometrically, ww is the normal of the boundary. Adding a misclassified positive point turns the normal toward that point, and subtracting a misclassified negative point turns it away, so the line rotates and shifts until the point is on the right side. Repeat until a full pass makes no mistakes.

Vocabulary

Augmented input
x~=(1,x1,…,xd)\tilde x=(1,x_1,\dots,x_d). Prepending a constant 1 lets the bias be the weight w0w_0, so w⋅x~=w0+w1x1+…w\cdot\tilde x=w_0+w_1x_1+\dots and one update rule trains both
Score (activation)
s=w⋅x~s=w\cdot\tilde x, the signed, unnormalized distance of xx from the boundary
Decision boundary
the hyperplane s=0s=0; ww (without w0w_0) is perpendicular to it and points toward the +1+1 side
Functional margin
y sy\,s. Positive means the point is correct; y s≤0y\,s\le0 is a mistake (a point exactly on the line counts as wrong)
Geometric margin
y s/∥w∥y\,s/\lVert w\rVert, the true distance to the boundary with a sign. The margin γ\gamma of a dataset is the largest achievable value of the smallest geometric margin
Linearly separable
some ww gives every point y s>0y\,s>0, i.e. a hyperplane with all +1+1 points on one side and all −1-1 points on the other
Epoch
one full pass over the training set in a fixed (or shuffled) order
Update
w←w+η y x~w\leftarrow w+\eta\,y\,\tilde x, applied only on a mistake. The perceptron is mistake-driven

The math

Absorb the bias into ww with the augmented input. The model and the mistake test are:

y^=sign⁡(w⋅x~),mistake on (xi,yi)  ⟺  yi (w⋅x~i)≤0\hat y=\operatorname{sign}(w\cdot\tilde x),\qquad \text{mistake on }(x_i,y_i)\iff y_i\,(w\cdot\tilde x_i)\le 0
ww
weights (w0,w1,…,wd)(w_0,w_1,\dots,w_d), where w0w_0 is the bias
x~i\tilde x_i
augmented input (1,xi1,…,xid)(1,x_{i1},\dots,x_{id})
yiy_i
true label, +1+1 or −1-1
y^\hat y
predicted label

From a loss to the update. The perceptron minimizes the perceptron criterion, which charges each misclassified point by how far it is on the wrong side and charges nothing for correct points:

L(w)=∑i=1nmax⁡(0, −yi w⋅x~i),∇wmax⁡(0,−yiw⋅x~i)={−yix~iyiw⋅x~i<00yiw⋅x~i>0L(w)=\sum_{i=1}^{n}\max\bigl(0,\,-y_i\,w\cdot\tilde x_i\bigr),\qquad \nabla_w \max(0,-y_i w\cdot\tilde x_i)=\begin{cases}-y_i\tilde x_i & y_iw\cdot\tilde x_i<0\\ 0 & y_iw\cdot\tilde x_i>0\end{cases}
L(w)L(w)
total perceptron loss; 0 exactly when every point is strictly correct
max⁡(0,−y s)\max(0,-y\,s)
a hinge at 0: zero on the correct side, growing linearly with the wrong-side score

Take a stochastic gradient step on a single example, w←w−η∇wLiw\leftarrow w-\eta\nabla_w L_i. On a correct point the gradient is 0, so nothing happens. On a mistake it is −yix~i-y_i\tilde x_i, which gives the perceptron rule:

w←w+η yi x~iif yi w⋅x~i≤0w \leftarrow w+\eta\,y_i\,\tilde x_i \quad\text{if } y_i\,w\cdot\tilde x_i\le 0
η\eta
learning rate (step size), η>0\eta>0; classically η=1\eta=1

Why one update helps. After the update the point's functional margin is yi(w+ηyix~i)⋅x~i=yi w⋅x~i+η∥x~i∥2y_i(w+\eta y_i\tilde x_i)\cdot\tilde x_i=y_i\,w\cdot\tilde x_i+\eta\lVert\tilde x_i\rVert^2, because yi2=1y_i^2=1. The margin rises by exactly η∥x~i∥2>0\eta\lVert\tilde x_i\rVert^2>0. One update does not always fix the point, and it can break others, which is why we keep cycling.

The convergence theorem (Novikoff, 1962). Suppose every ∥x~i∥≤R\lVert\tilde x_i\rVert\le R and some unit vector uu separates the data with margin γ\gamma, meaning yi u⋅x~i≥γ>0y_i\,u\cdot\tilde x_i\ge\gamma>0 for all ii. Start from w=0w=0 with η=1\eta=1, and let wkw_k be the weights after kk mistakes.

Proof sketch: at most (R/γ)² mistakes

  1. 1Progress toward uu. Each update adds yix~iy_i\tilde x_i, so wk⋅u=wk−1⋅u+yix~i⋅u≥wk−1⋅u+γw_{k}\cdot u=w_{k-1}\cdot u+y_i\tilde x_i\cdot u\ge w_{k-1}\cdot u+\gamma. After kk mistakes, wk⋅u≥kγw_k\cdot u\ge k\gamma.
  2. 2Slow growth of the norm. ∥wk∥2=∥wk−1∥2+2yi wk−1⋅x~i+∥x~i∥2\lVert w_k\rVert^2=\lVert w_{k-1}\rVert^2+2y_i\,w_{k-1}\cdot\tilde x_i+\lVert\tilde x_i\rVert^2. The middle term is ≤0\le0 because it was a mistake, so ∥wk∥2≤∥wk−1∥2+R2\lVert w_k\rVert^2\le\lVert w_{k-1}\rVert^2+R^2, and ∥wk∥2≤kR2\lVert w_k\rVert^2\le kR^2.
  3. 3Combine. Cauchy–Schwarz gives kγ≤wk⋅u≤∥wk∥≤k Rk\gamma\le w_k\cdot u\le\lVert w_k\rVert\le\sqrt k\,R. Squaring gives k≤R2/γ2k\le R^2/\gamma^2.
k  ≤  (Rγ)2k\;\le\;\left(\frac{R}{\gamma}\right)^{2}
kk
total number of updates (mistakes) over the whole run, across all epochs
RR
max⁡i∥x~i∥\max_i\lVert\tilde x_i\rVert, the radius of the (augmented) data
γ\gamma
margin of the best separating hyperplane through the origin in augmented space

The bound depends on neither nn nor dd, only on how wide the gap between the classes is relative to the size of the data. Wide margins mean few mistakes. If the data are not separable, no such uu exists, and the algorithm keeps making mistakes forever.

The learning rate does almost nothing. Starting from w=0w=0, every update adds η y x~\eta\,y\,\tilde x, so the weights are always η\eta times the weights of the η=1\eta=1 run. The signs of all scores are unchanged, so the same mistakes happen in the same order and the final classifier is the same. (On the worked example below, η=0.1\eta=0.1 gives exactly w=(−0.5,0.1,0.1)w=(-0.5,0.1,0.1).) η\eta matters only with a non-zero start or with regularization. The real hyperparameters are the number of epochs and the order of the data.

Worked example: eight points, seven updates

Two features x1,x2x_1,x_2 (think of two exam scores from 0 to 5) and a pass/fail label. The points are visited in the order of the table, every epoch, with w=(w0,w1,w2)w=(w_0,w_1,w_2) starting at (0,0,0)(0,0,0) and η=1\eta=1.

#x₁x₂yaugmented x̃
110−1(1, 1, 0)
200−1(1, 0, 0)
355+1(1, 5, 5)
401−1(1, 0, 1)
525+1(1, 2, 5)
611−1(1, 1, 1)
743+1(1, 4, 3)
835+1(1, 3, 5)
Training data, in visiting order. Highlighted rows are the +1 (pass) class.

Epoch 1 by hand

  1. 1Point 1 (1,0)(1,0), y=−1y=-1: s=(0,0,0)⋅(1,1,0)=0s=(0,0,0)\cdot(1,1,0)=0, so y s=0≤0y\,s=0\le0, a mistake. w←(0,0,0)−(1,1,0)=(−1,−1,0)w\leftarrow(0,0,0)-(1,1,0)=(-1,-1,0).
  2. 2Point 2 (0,0)(0,0), y=−1y=-1: s=−1s=-1, y s=1>0y\,s=1>0. Correct, no change.
  3. 3Point 3 (5,5)(5,5), y=+1y=+1: s=−1−5+0=−6s=-1-5+0=-6, y s=−6y\,s=-6, a mistake. w←(−1,−1,0)+(1,5,5)=(0,4,5)w\leftarrow(-1,-1,0)+(1,5,5)=(0,4,5).
  4. 4Point 4 (0,1)(0,1), y=−1y=-1: s=0+0+5=5s=0+0+5=5, y s=−5y\,s=-5, a mistake. w←(0,4,5)−(1,0,1)=(−1,4,4)w\leftarrow(0,4,5)-(1,0,1)=(-1,4,4).
  5. 5Point 5 (2,5)(2,5), y=+1y=+1: s=−1+8+20=27s=-1+8+20=27. Correct.
  6. 6Point 6 (1,1)(1,1), y=−1y=-1: s=−1+4+4=7s=-1+4+4=7, y s=−7y\,s=-7, a mistake. w←(−1,4,4)−(1,1,1)=(−2,3,3)w\leftarrow(-1,4,4)-(1,1,1)=(-2,3,3).
  7. 7Points 7, 8: s=−2+12+9=19s=-2+12+9=19 and s=−2+9+15=22s=-2+9+15=22, both positive and correct. Epoch 1: 4 mistakes, ending at w=(−2,3,3)w=(-2,3,3).
EpochPointyscore s (before)y·sw after update
11 (1, 0)−100(−1, −1, 0)
13 (5, 5)+1−6−6(0, 4, 5)
14 (0, 1)−15−5(−1, 4, 4)
16 (1, 1)−17−7(−2, 3, 3)
21 (1, 0)−11−1(−3, 2, 3)
24 (0, 1)−100(−4, 2, 2)
26 (1, 1)−100(−5, 1, 1)
3noneall > 0(−5, 1, 1), converged
Every update of the run. Epoch 3 visits all eight points with no mistake, so training stops at w = (−5, 1, 1).

Reading off the result

  1. 1Boundary. −5+x1+x2=0-5+x_1+x_2=0, i.e. pass when x1+x2>5x_1+x_2>5. The final scores of the eight points are −4,−5,5,−4,2,−3,2,3-4,-5,5,-4,2,-3,2,3, all with the correct sign.
  2. 2Predict a new student with x=(4,2)x=(4,2): s=−5+4+2=1>0s=-5+4+2=1>0, so y^=+1\hat y=+1 (pass). For (3,1)(3,1): s=−5+3+1=−1s=-5+3+1=-1, fail.
  3. 3Check the bound. The largest augmented norm is ∥(1,5,5)∥=51=7.14\lVert(1,5,5)\rVert=\sqrt{51}=7.14. The best margin through the origin in augmented space is γ=0.530\gamma=0.530 (from u∝(−1.8,0.4,0.4)u\propto(-1.8,0.4,0.4)). So Novikoff allows at most (7.14/0.530)2=181.6(7.14/0.530)^2=181.6 updates. The run needed 7. The bound is a worst case, not a prediction.
  4. 4Points 5 and 7 end closest to the line, at y s=2y\,s=2, a distance 2/2=1.412/\sqrt2=1.41 from it. The perceptron stopped at the first separating line it found, not the widest one.
▸ perceptron · separable datastep 1/35
001122334455x₁x₂12345678w = (w₀, w₁, w₂) (0, 0, 0)training errors now: 8 / 8mistakes per epoch123● +1 ● −1 → (w₁, w₂)
epoch 1updates 0‖w‖ = 0.00
  1. 1w ← (0, 0, 0) # w₀ = bias, x₀ = 1
  2. 2repeat (one epoch):
  3. 3 for each (xᵢ, yᵢ) in order:
  4. 4 s ← w · xᵢ
  5. 5 if yᵢ · s ≤ 0: # mistake
  6. 6 w ← w + η yᵢ xᵢ # η = 1
  7. 7until an epoch makes 0 mistakes

Start at w = (0, 0, 0). Every score is 0, and the rule counts a score of 0 as a mistake, so all 8 points are wrong.

fig.The worked example, one point visit per step. The violet arrow is the normal (w₁, w₂) drawn from the origin. On a mistake the dashed grey arrow is the old normal and the rose arrow is the added y·x, so you can see the vector sum turn the boundary. Points with a rose outline are currently misclassified. Separable data: 4, 3, then 0 mistakes per epoch, ending at w = (−5, 1, 1) after 7 updates. Switch to '+ mislabelled (4, 4)': every epoch ends with that point flipping w (to (−9, −1, −2) after 6 epochs, 4 errors), while the pocket keeps (−6, 3, 2) with 1 error.

The algorithm, step by step

Perceptron(X, y, epochs)

  1. 1Prepare. Append a constant feature 1 to every xix_i (or keep a separate bb and update it by η yi\eta\,y_i). Encode labels as ±1\pm1. Standardize features if their scales differ a lot.
  2. 2Initialize w=0w=0.
  3. 3For each epoch, optionally shuffle, then for each (xi,yi)(x_i,y_i) compute s=w⋅x~is=w\cdot\tilde x_i. If yis≤0y_i s\le0, set w←w+η yix~iw\leftarrow w+\eta\,y_i\tilde x_i and count a mistake.
  4. 4Stop when an epoch makes no mistakes (converged), or after max_epochs, or when the training loss stops improving (tol, n_iter_no_change).
  5. 5Predict y^=sign⁡(w⋅x~)\hat y=\operatorname{sign}(w\cdot\tilde x) for new points.

Complexity

Per update
O(d)O(d): one dot product plus one vector addition (for sparse inputs, O(non-zeros)O(\text{non-zeros}))
Per epoch
O(n d)O(n\,d)
Total (separable)
at most (R/γ)2(R/\gamma)^2 updates, plus the final clean epoch
Memory
O(d)O(d). It never needs more than one example at a time, so it works online and out of core

When the data are not separable

Add a single mislabelled point, (4,4)(4,4) with y=−1y=-1, sitting inside the pass region. Now no line can be perfect. In the run above (switch the figure to the second tab), every epoch's last update is that point, which flips the normal around. After 6 epochs the weights are w=(−9,−1,−2)w=(-9,-1,-2), a line that gets 4 of the 9 points wrong. Meanwhile the run passed through w=(−6,3,2)w=(-6,3,2), which gets only the mislabelled point wrong. The plain perceptron just returns whatever ww it holds when the epochs run out, and that can be any point in its cycle.

VariantChange to the ruleWhat it fixes
Pocket (Gallant 1990)keep a copy of the w with the fewest training errors seen so farnon-separable data: returns (−6, 3, 2), 1 error, instead of the last w
Averaged / voted (Freund & Schapire 1999)predict with the average of w over all steps (voted: weight each w by how long it survived)noise and order sensitivity; generalizes close to an SVM, at the same cost
Margin perceptronupdate when y·s ≤ τ for some τ > 0, not just ≤ 0the boundary hugging the data: forces a gap of at least τ/‖w‖
Kernel perceptronstore mistake counts αᵢ; s = Σ αᵢ yᵢ k(xᵢ, x)non-linear boundaries (XOR, circles) via a kernel
Multiclassone wᶜ per class; predict argmax wᶜ·x; on a mistake add x to the true class, subtract it from the predicted onemore than two classes in one model
Structured (Collins 2002)the same update on feature vectors of whole output sequencestagging and parsing with averaged updates
Multi-layer perceptronstack layers with smooth activations, train with backpropagationanything non-linear, at the price of convexity and guarantees
Variants of the perceptron, and what each one fixes.

Practical tuning (scikit-learn's Perceptron)

max_iter
the number of epochs. On non-separable data this decides where the cycle stops, so prefer early stopping or averaging
shuffle
on by default. It reshuffles every epoch, so set random_state for reproducibility; the result depends on the order
tol, n_iter_no_change
stop when the loss has not improved by tol for that many epochs; tol=None runs all max_iter epochs
eta0
the learning rate. From a zero start it only rescales w (see the math), so leave it at 1
penalty, alpha
optional L2/L1/elastic-net shrinkage. Here η does matter, because the penalty is scaled by it
early_stopping
hold out validation_fraction of the data and stop when validation accuracy stops improving: a cheap guard against non-separable cycling
class_weight
scales the update for each class. Use 'balanced' for imbalanced labels

In code

python
1import numpy as np
2
3def perceptron(X, y, eta=1.0, max_epochs=100):
4 Xa = np.c_[np.ones(len(X)), X] # prepend x0 = 1 so w[0] is the bias
5 w = np.zeros(Xa.shape[1])
6 for epoch in range(1, max_epochs + 1):
7 mistakes = 0
8 for xi, yi in zip(Xa, y):
9 if yi * (w @ xi) <= 0: # wrong side (or on the line)
10 w += eta * yi * xi # w <- w + eta * y * x
11 mistakes += 1
12 print(f"epoch {epoch}: {mistakes} mistakes, w = {w}")
13 if mistakes == 0: # a full clean pass: converged
14 return w, epoch
15 return w, None # not separable (or too few epochs)
16
17def predict(w, X):
18 return np.sign(np.c_[np.ones(len(X)), X] @ w)
19
20X = np.array([[1, 0], [0, 0], [5, 5], [0, 1], [2, 5], [1, 1], [4, 3], [3, 5]], float)
21y = np.array([-1, -1, 1, -1, 1, -1, 1, 1])
22w, epochs = perceptron(X, y)
23print("converged after", epochs, "epochs; w =", w)
24print("predict (4, 2):", predict(w, np.array([[4, 2]])))
25
26# epoch 1: 4 mistakes, w = [-2. 3. 3.]
27# epoch 2: 3 mistakes, w = [-5. 1. 1.]
28# epoch 3: 0 mistakes, w = [-5. 1. 1.]
29# converged after 3 epochs; w = [-5. 1. 1.]
30# predict (4, 2): [1.]
From scratch, on the worked example. Prints 4, 3, then 0 mistakes per epoch, converges to w = [-5, 1, 1], and predicts +1 for (4, 2).
python
1import numpy as np
2from sklearn.linear_model import Perceptron
3
4X = np.array([[1, 0], [0, 0], [5, 5], [0, 1], [2, 5], [1, 1], [4, 3], [3, 5]], float)
5y = np.array([-1, -1, 1, -1, 1, -1, 1, 1])
6
7clf = Perceptron(eta0=1.0, shuffle=False, max_iter=100, tol=None).fit(X, y)
8print("w0 =", clf.intercept_, " w1, w2 =", clf.coef_)
9print("training accuracy:", clf.score(X, y))
10print("predict (4, 2):", clf.predict([[4, 2]]), " score:", clf.decision_function([[4, 2]]))
11
12# w0 = [-5.] w1, w2 = [[1. 1.]]
13# training accuracy: 1.0
14# predict (4, 2): [1] score: [1.]
15
16# Equivalent: SGDClassifier(loss="perceptron", learning_rate="constant", eta0=1, penalty=None)
scikit-learn, same data and order (shuffle=False, eta0=1). It finds the same w, because Perceptron is SGD on the perceptron loss.

Use when

  • +You need a very fast, tiny, online linear classifier: one dot product per prediction and O(d) memory, and it updates from a stream one example at a time.
  • +The data are (close to) linearly separable, e.g. high-dimensional sparse text features, where the averaged perceptron is competitive with linear SVMs.
  • +You want a transparent baseline or a teaching model: every weight change has a one-line explanation.
  • +You need a learner for structured outputs (tagging, parsing) with simple, mistake-driven updates.

Avoid when

  • −You need probabilities or calibrated confidence: use logistic regression.
  • −The data are noisy or overlapping: the plain version cycles and its final weights are arbitrary.
  • −You want the best linear boundary: it stops at the first separator, with no margin. Use an SVM.
  • −The boundary is non-linear (XOR is the classic case): a single perceptron cannot represent it without kernels or hidden layers.

Where it's used

Mark I Perceptron (1958)

Rosenblatt's hardware: a 20×20 photocell retina wired to adjustable potentiometer weights, trained to recognize simple shapes and letters.

NLP tagging and parsing

The averaged structured perceptron (Collins 2002) was the workhorse for part-of-speech tagging, chunking and dependency parsing before neural models.

Online and streaming classification

Spam filtering, click and fraud filters on sparse hashed features: learn as data arrives, with no stored dataset.

The neuron in neural networks

Every unit of a multi-layer perceptron is a perceptron with a smooth activation. The perceptron's limits on XOR (Minsky & Papert, 1969) are why hidden layers matter.

Check yourself

w = (−2, 3, 3) (bias first). The point x = (1, 0) with y = −1 arrives, and η = 1. What is w after this step?

Check yourself

Every augmented input has norm at most R = 5, and the data are separable with margin γ = 0.5. Novikoff's theorem guarantees the perceptron makes at most how many updates?

Check yourself

Starting from w = 0, you change the learning rate from η = 1 to η = 0.1. What happens to the trained classifier?

Check yourself

You train a perceptron on XOR: (0,0) and (1,1) are −1, (0,1) and (1,0) are +1. What happens?

Remember

  • ✓Model: y^=sign⁡(w⋅x~)\hat y=\operatorname{sign}(w\cdot\tilde x), with the bias folded in as w0w_0 via x~=(1,x)\tilde x=(1,x).
  • ✓Rule: only on a mistake (y w⋅x~≤0y\,w\cdot\tilde x\le0), set w←w+η y x~w\leftarrow w+\eta\,y\,\tilde x. This is SGD on the loss max⁡(0,−y w⋅x~)\max(0,-y\,w\cdot\tilde x), and each update raises the point's margin by η∥x~∥2\eta\lVert\tilde x\rVert^2.
  • ✓Separable data: at most (R/γ)2(R/\gamma)^2 updates (Novikoff). The worked example converged to x1+x2=5x_1+x_2=5 in 7 updates, against a bound of 181.6.
  • ✓The result depends on the visiting order and has no margin guarantee. From w = 0 the learning rate is irrelevant.
  • ✓Non-separable data: it cycles forever, so use the pocket or averaged perceptron, early stopping, or logistic regression / SVM.
  • ✓No probabilities and no non-linear boundaries. It is the single neuron that multi-layer networks are built from.
← back to ML Algorithms roadmap