Definition
The perceptron is a linear classifier trained by one rule: go through the examples, and whenever one is on the wrong side of the line, add 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 ); multiclass by extension
- Input → output
- feature vector → a hard label (no probability)
- Learns
- a weight vector and a bias ; the boundary is the hyperplane
- Training
- per epoch (one pass over the data); on separable data at most updates in total
- Prediction
- : 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 labels on 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 says which side of the line is on: positive means class , negative means class . A point is classified correctly exactly when and have the same sign, i.e. when . When a point is wrong, nudge so that its score moves toward the correct sign. Adding to raises the score of ; subtracting lowers it. Both cases are covered by "add ". Geometrically, 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
- . Prepending a constant 1 lets the bias be the weight , so and one update rule trains both
- Score (activation)
- , the signed, unnormalized distance of from the boundary
- Decision boundary
- the hyperplane ; (without ) is perpendicular to it and points toward the side
- Functional margin
- . Positive means the point is correct; is a mistake (a point exactly on the line counts as wrong)
- Geometric margin
- , the true distance to the boundary with a sign. The margin of a dataset is the largest achievable value of the smallest geometric margin
- Linearly separable
- some gives every point , i.e. a hyperplane with all points on one side and all points on the other
- Epoch
- one full pass over the training set in a fixed (or shuffled) order
- Update
- , applied only on a mistake. The perceptron is mistake-driven
The math
Absorb the bias into with the augmented input. The model and the mistake test are:
- weights , where is the bias
- augmented input
- true label, or
- 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:
- total perceptron loss; 0 exactly when every point is strictly correct
- 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, . On a correct point the gradient is 0, so nothing happens. On a mistake it is , which gives the perceptron rule:
- learning rate (step size), ; classically
Why one update helps. After the update the point's functional margin is , because . The margin rises by exactly . 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 and some unit vector separates the data with margin , meaning for all . Start from with , and let be the weights after mistakes.
Proof sketch: at most (R/γ)² mistakes
- 1Progress toward . Each update adds , so . After mistakes, .
- 2Slow growth of the norm. . The middle term is because it was a mistake, so , and .
- 3Combine. Cauchy–Schwarz gives . Squaring gives .
- total number of updates (mistakes) over the whole run, across all epochs
- , the radius of the (augmented) data
- margin of the best separating hyperplane through the origin in augmented space
The bound depends on neither nor , 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 exists, and the algorithm keeps making mistakes forever.
The learning rate does almost nothing. Starting from , every update adds , so the weights are always times the weights of the 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, gives exactly .) 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 (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 starting at and .
| # | x₁ | x₂ | y | augmented x̃ |
|---|---|---|---|---|
| 1 | 1 | 0 | −1 | (1, 1, 0) |
| 2 | 0 | 0 | −1 | (1, 0, 0) |
| 3 | 5 | 5 | +1 | (1, 5, 5) |
| 4 | 0 | 1 | −1 | (1, 0, 1) |
| 5 | 2 | 5 | +1 | (1, 2, 5) |
| 6 | 1 | 1 | −1 | (1, 1, 1) |
| 7 | 4 | 3 | +1 | (1, 4, 3) |
| 8 | 3 | 5 | +1 | (1, 3, 5) |
Epoch 1 by hand
- 1Point 1 , : , so , a mistake. .
- 2Point 2 , : , . Correct, no change.
- 3Point 3 , : , , a mistake. .
- 4Point 4 , : , , a mistake. .
- 5Point 5 , : . Correct.
- 6Point 6 , : , , a mistake. .
- 7Points 7, 8: and , both positive and correct. Epoch 1: 4 mistakes, ending at .
| Epoch | Point | y | score s (before) | y·s | w after update |
|---|---|---|---|---|---|
| 1 | 1 (1, 0) | −1 | 0 | 0 | (−1, −1, 0) |
| 1 | 3 (5, 5) | +1 | −6 | −6 | (0, 4, 5) |
| 1 | 4 (0, 1) | −1 | 5 | −5 | (−1, 4, 4) |
| 1 | 6 (1, 1) | −1 | 7 | −7 | (−2, 3, 3) |
| 2 | 1 (1, 0) | −1 | 1 | −1 | (−3, 2, 3) |
| 2 | 4 (0, 1) | −1 | 0 | 0 | (−4, 2, 2) |
| 2 | 6 (1, 1) | −1 | 0 | 0 | (−5, 1, 1) |
| 3 | none | all > 0 | (−5, 1, 1), converged |
Reading off the result
- 1Boundary. , i.e. pass when . The final scores of the eight points are , all with the correct sign.
- 2Predict a new student with : , so (pass). For : , fail.
- 3Check the bound. The largest augmented norm is . The best margin through the origin in augmented space is (from ). So Novikoff allows at most updates. The run needed 7. The bound is a worst case, not a prediction.
- 4Points 5 and 7 end closest to the line, at , a distance from it. The perceptron stopped at the first separating line it found, not the widest one.
- 1w ← (0, 0, 0) # w₀ = bias, x₀ = 1
- 2repeat (one epoch):
- 3 for each (xᵢ, yᵢ) in order:
- 4 s ← w · xᵢ
- 5 if yᵢ · s ≤ 0: # mistake
- 6 w ← w + η yᵢ xᵢ # η = 1
- 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.
The algorithm, step by step
Perceptron(X, y, epochs)
- 1Prepare. Append a constant feature 1 to every (or keep a separate and update it by ). Encode labels as . Standardize features if their scales differ a lot.
- 2Initialize .
- 3For each epoch, optionally shuffle, then for each compute . If , set and count a mistake.
- 4Stop when an epoch makes no mistakes (converged), or after
max_epochs, or when the training loss stops improving (tol,n_iter_no_change). - 5Predict for new points.
Complexity
- Per update
- : one dot product plus one vector addition (for sparse inputs, )
- Per epoch
- Total (separable)
- at most updates, plus the final clean epoch
- Memory
- . 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, with , 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 , a line that gets 4 of the 9 points wrong. Meanwhile the run passed through , which gets only the mislabelled point wrong. The plain perceptron just returns whatever it holds when the epochs run out, and that can be any point in its cycle.
| Variant | Change to the rule | What it fixes |
|---|---|---|
| Pocket (Gallant 1990) | keep a copy of the w with the fewest training errors seen so far | non-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 perceptron | update when y·s ≤ τ for some τ > 0, not just ≤ 0 | the boundary hugging the data: forces a gap of at least τ/‖w‖ |
| Kernel perceptron | store mistake counts αᵢ; s = Σ αᵢ yᵢ k(xᵢ, x) | non-linear boundaries (XOR, circles) via a kernel |
| Multiclass | one wᶜ per class; predict argmax wᶜ·x; on a mistake add x to the true class, subtract it from the predicted one | more than two classes in one model |
| Structured (Collins 2002) | the same update on feature vectors of whole output sequences | tagging and parsing with averaged updates |
| Multi-layer perceptron | stack layers with smooth activations, train with backpropagation | anything non-linear, at the price of convexity and guarantees |
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_statefor reproducibility; the result depends on the order - tol, n_iter_no_change
- stop when the loss has not improved by
tolfor that many epochs;tol=Noneruns allmax_iterepochs - 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_fractionof 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
1import numpy as np23def 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 bias5 w = np.zeros(Xa.shape[1])6 for epoch in range(1, max_epochs + 1):7 mistakes = 08 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 * x11 mistakes += 112 print(f"epoch {epoch}: {mistakes} mistakes, w = {w}")13 if mistakes == 0: # a full clean pass: converged14 return w, epoch15 return w, None # not separable (or too few epochs)1617def predict(w, X):18 return np.sign(np.c_[np.ones(len(X)), X] @ w)1920X = 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]])))2526# 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.]1import numpy as np2from sklearn.linear_model import Perceptron34X = 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])67clf = 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]]))1112# w0 = [-5.] w1, w2 = [[1. 1.]]13# training accuracy: 1.014# predict (4, 2): [1] score: [1.]1516# Equivalent: SGDClassifier(loss="perceptron", learning_rate="constant", eta0=1, penalty=None)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: , with the bias folded in as via .
- ✓Rule: only on a mistake (), set . This is SGD on the loss , and each update raises the point's margin by .
- ✓Separable data: at most updates (Novikoff). The worked example converged to 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.