Fisher's iris data record four measurements on 150 flowers, 50 from each of three species. Plotted by petal length against petal width, the 50 flowers of Iris setosa sit in a tight cluster with petals no longer than 1.9 cm and no wider than 0.6 cm, while every flower of the other two species has petals at least 3.0 cm long and 1.0 cm wide. A straight line can be drawn between the groups in many ways. The perceptron finds one of them by trial and error: it starts with a line that classifies nothing correctly in particular, visits the flowers one at a time, and nudges the line whenever a flower is on the wrong side. On these data, in 30 runs that visited the flowers in different random orders, it needed a median of 8 nudges before every flower was on the correct side, and never more than 20.
The perceptron is the simplest neural network: one artificial neuron, described in Introduction to Artificial Neural Networks, with a step activation and a learning rule. This article states the rule, proves that it always succeeds when a separating line exists, and shows what happens when none does. Its learning rule is the ancestor of the gradient methods that train the networks of the later articles, and its relation to logistic regression explains why the smooth version replaced it.
The perceptron as a classifier
A perceptron with inputs $\mathbf{x} = (x_1, \ldots, x_n)$, weights $\mathbf{w}$ and bias $b$ computes the weighted sum $z = \mathbf{w}^{\mathsf{T}}\mathbf{x} + b$ and outputs
$$\hat{y} = \operatorname{step}(z) = \begin{cases} 1 & \text{if } z \geq 0, \\ 0 & \text{if } z < 0. \end{cases}$$
The single layer of the name is the one layer of adjustable weights between the inputs and the output; there are no hidden units. The perceptron of Rosenblatt (1958) was a more elaborate system, with a layer of association units between a retina and the response units, but its association units were wired at random and only the influence of the association units on the responses was learned (see the introduction). The perceptron taught today, and treated here, is that last learned layer on its own: in the words of Novikoff (1962), "a single threshold element acting on a weighted set of inputs."
The perceptron's decision boundary is the set of inputs with $z = 0$, a hyperplane: a line for two inputs, a plane for three. The weight vector $\mathbf{w}$ is perpendicular to it and points toward the side the perceptron calls 1, and the value of $z$ at a point is proportional to the point's signed distance from the boundary: the distance is $z / \lVert \mathbf{w} \rVert$ (Hastie, Tibshirani and Friedman, 2009, §4.5, eq. 4.40). Changing the weights tilts the boundary; changing the bias slides it without tilting.
Why the bias is needed
The AND function of two binary inputs outputs 1 only for $(1, 1)$. Without a bias, $z = w_1 x_1 + w_2 x_2$ and the boundary passes through the origin. But then the input $(0, 0)$ has $z = 0$ whatever the weights are, so a perceptron without a bias outputs 1 for it and gets AND wrong. (With the opposite convention, output 0 at $z = 0$, it would fail on OR instead.) No choice of weights helps: the input at the origin is always on the boundary. With a bias the boundary can move away from the origin; $x_1 + x_2 - 1.5 = 0$, for example, separates $(1, 1)$ from the other three inputs. It is standard to absorb the bias into the weights by appending a constant input 1 to every example, $\tilde{\mathbf{x}} = (\mathbf{x}, 1)$ and $\tilde{\mathbf{w}} = (\mathbf{w}, b)$, so that $z = \tilde{\mathbf{w}}^{\mathsf{T}} \tilde{\mathbf{x}}$; the bias is then learned like any other weight.
The learning rule
Rosenblatt's rule learns from mistakes. Start from some weights, often all zero. Visit the training examples one at a time; for an example $(\mathbf{x}_i, y_i)$ with $y_i \in \{0, 1\}$, compute the prediction $\hat{y}_i$, and update
$$\mathbf{w} \leftarrow \mathbf{w} + r\,(y_i - \hat{y}_i)\,\mathbf{x}_i, \qquad b \leftarrow b + r\,(y_i - \hat{y}_i),$$
where $r > 0$ is the learning rate. A correct prediction makes $y_i - \hat{y}_i = 0$ and changes nothing. A missed positive ($y_i = 1$, $\hat{y}_i = 0$) adds $r\,\mathbf{x}_i$ to the weights, which raises $z$ for this example by $r \lVert \mathbf{x}_i \rVert^2 + r$ (counting the bias), moving the boundary toward putting it on the positive side; a false positive subtracts the same amount. One pass through all the examples is an epoch, and training repeats epochs until one passes with no mistakes, or until a limit on the number of epochs is reached.
When the weights start at zero, the learning rate has no effect on what the perceptron predicts. Every update adds $\pm r\,\tilde{\mathbf{x}}_i$, so after any sequence of updates the weights are $r$ times what they would be with $r = 1$, and multiplying all the weights by a positive number does not change the sign of $z$. Run on AND with $r = 0.1$ or $r = 0.5$ instead of 1, the rule makes the same mistakes and ends at weights exactly 0.1 or 0.5 times those below. (From nonzero starting weights the learning rate does matter, because it sets the size of the updates relative to the starting point.)
Tracing the rule on AND
Start from $\mathbf{w} = (0, 0)$, $b = 0$, with $r = 1$, and visit the inputs in the order $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ in every epoch. The first epoch goes:
| Input | Target | $z$ | Prediction | Update | Weights after, bias after |
|---|---|---|---|---|---|
| (0, 0) | 0 | 0 | 1 | $b \mathrel{-}= 1$ | (0, 0), −1 |
| (0, 1) | 0 | −1 | 0 | none | (0, 0), −1 |
| (1, 0) | 0 | −1 | 0 | none | (0, 0), −1 |
| (1, 1) | 1 | −1 | 0 | add (1, 1), $b \mathrel{+}= 1$ | (1, 1), 0 |
The second epoch makes three mistakes, on $(0, 0)$, $(0, 1)$ and $(1, 1)$, ending at $\mathbf{w} = (2, 1)$, $b = -1$. The following epochs make 3, 2 and 1 mistakes, and the sixth makes none. The final perceptron has $\mathbf{w} = (2, 1)$ and $b = -3$, after 11 updates in all:
| Input | $z = 2x_1 + x_2 - 3$ | Prediction | AND |
|---|---|---|---|
| (0, 0) | −3 | 0 | 0 |
| (0, 1) | −2 | 0 | 0 |
| (1, 0) | −1 | 0 | 0 |
| (1, 1) | 0 | 1 | 1 |
The final boundary passes exactly through $(1, 1)$, which is classified 1 only because the step function outputs 1 at $z = 0$. The rule stops at the first weights that make no mistakes on the training data, however close to the boundary an example sits. Nothing in it prefers a boundary with room to spare, which is what the support vector machine adds.
The rule as stochastic gradient descent
The rule can be derived as the minimization of a loss. Write the labels as $\tilde{y}_i = +1$ or $-1$ instead of 1 or 0. An example is misclassified when $\tilde{y}_i\,\tilde{\mathbf{w}}^{\mathsf{T}}\tilde{\mathbf{x}}_i \leq 0$. Rosenblatt's criterion, as Hastie et al. (2009, §4.5.1) present it, is
$$D(\tilde{\mathbf{w}}) = -\sum_{i \in \mathcal{M}} \tilde{y}_i\, \tilde{\mathbf{w}}^{\mathsf{T}} \tilde{\mathbf{x}}_i,$$
summed over the set $\mathcal{M}$ of misclassified examples. Each term is nonnegative and proportional to the example's distance from the boundary, so $D$ measures how badly the misclassified examples are misclassified, and it is zero exactly when there are none. With $\mathcal{M}$ held fixed, the gradient of the term for example $i$ is $-\tilde{y}_i \tilde{\mathbf{x}}_i$, and a step against it is $\tilde{\mathbf{w}} \leftarrow \tilde{\mathbf{w}} + r\,\tilde{y}_i\,\tilde{\mathbf{x}}_i$. Taking such a step after each misclassified example, rather than summing over all of them first, is stochastic gradient descent (Hastie et al., 2009, eq. 4.44). Since $y_i - \hat{y}_i = \tilde{y}_i$ for a misclassified example and 0 otherwise, this is the 0/1 rule above with the same learning rate. The two forms differ only for an example lying exactly on the boundary: the 0/1 rule, whose step function outputs 1 at $z = 0$, counts it as correct when its label is 1, while the $\pm 1$ form counts every example with $\tilde{y}_i\,\tilde{\mathbf{w}}^{\mathsf{T}}\tilde{\mathbf{x}}_i = 0$ as a mistake. The convergence theorem below uses the $\pm 1$ form.
The convergence theorem
The rule only changes the weights on mistakes, and each change can undo the progress made on other examples. That it nevertheless stops is the perceptron convergence theorem, one of the first theorems about a learning machine. Novikoff (1962) called it "one of the most often re-proved results in the field" and gave a short proof; the version below is the form in which his argument is usually stated.
Assumptions. Use the $\pm 1$ labels and the augmented inputs $\tilde{\mathbf{x}}_i$, which include the constant 1. Suppose the data are linearly separable with margin $\gamma > 0$: there is a weight vector $\mathbf{u}$ of length $\lVert \mathbf{u} \rVert = 1$ such that
$$\tilde{y}_i\, \mathbf{u}^{\mathsf{T}} \tilde{\mathbf{x}}_i \geq \gamma \quad \text{for every example } i.$$
Every example is on the correct side of the hyperplane $\mathbf{u}^{\mathsf{T}}\tilde{\mathbf{x}} = 0$, at least $\gamma$ from it. Let $R = \max_i \lVert \tilde{\mathbf{x}}_i \rVert$ be the length of the longest input. Run the rule with $\tilde{\mathbf{w}}_0 = \mathbf{0}$ and $r = 1$, visiting the examples in any order.
Theorem. The rule makes at most $(R/\gamma)^2$ mistakes. After the last of them, every example is classified correctly.
Proof. Let $\tilde{\mathbf{w}}_k$ be the weights after the $k$-th mistake, made on some example $(\tilde{\mathbf{x}}, \tilde{y})$, so that $\tilde{\mathbf{w}}_k = \tilde{\mathbf{w}}_{k-1} + \tilde{y}\,\tilde{\mathbf{x}}$. Two quantities are tracked.
The weights move toward $\mathbf{u}$ at a steady rate. Taking the inner product of the update with $\mathbf{u}$,
$$\mathbf{u}^{\mathsf{T}}\tilde{\mathbf{w}}_k = \mathbf{u}^{\mathsf{T}}\tilde{\mathbf{w}}_{k-1} + \tilde{y}\,\mathbf{u}^{\mathsf{T}}\tilde{\mathbf{x}} \geq \mathbf{u}^{\mathsf{T}}\tilde{\mathbf{w}}_{k-1} + \gamma,$$
by the margin assumption. Starting from $\mathbf{u}^{\mathsf{T}}\tilde{\mathbf{w}}_0 = 0$ and applying this $k$ times, $\mathbf{u}^{\mathsf{T}}\tilde{\mathbf{w}}_k \geq k\gamma$.
The length of the weights grows slowly. Expanding the squared length of the update,
$$\lVert \tilde{\mathbf{w}}_k \rVert^2 = \lVert \tilde{\mathbf{w}}_{k-1} \rVert^2 + 2\,\tilde{y}\,\tilde{\mathbf{w}}_{k-1}^{\mathsf{T}}\tilde{\mathbf{x}} + \tilde{y}^2 \lVert \tilde{\mathbf{x}} \rVert^2 \leq \lVert \tilde{\mathbf{w}}_{k-1} \rVert^2 + R^2.$$
The middle term is at most zero because the example was misclassified, which is exactly the condition $\tilde{y}\,\tilde{\mathbf{w}}_{k-1}^{\mathsf{T}}\tilde{\mathbf{x}} \leq 0$; and $\tilde{y}^2 = 1$ and $\lVert \tilde{\mathbf{x}} \rVert \leq R$. Starting from $\lVert \tilde{\mathbf{w}}_0 \rVert = 0$, $\lVert \tilde{\mathbf{w}}_k \rVert^2 \leq kR^2$.
The two are incompatible for large $k$. By the Cauchy-Schwarz inequality and $\lVert \mathbf{u} \rVert = 1$, $\mathbf{u}^{\mathsf{T}}\tilde{\mathbf{w}}_k \leq \lVert \tilde{\mathbf{w}}_k \rVert$. Combining the two bounds,
$$k\gamma \;\leq\; \mathbf{u}^{\mathsf{T}}\tilde{\mathbf{w}}_k \;\leq\; \lVert \tilde{\mathbf{w}}_k \rVert \;\leq\; \sqrt{k}\,R,$$
so $\sqrt{k} \leq R/\gamma$, that is, $k \leq (R/\gamma)^2$. The number of mistakes is bounded, so after finitely many there are no more: once an epoch passes without a mistake, every example is classified correctly and the weights never change again. $\square$
The heart of the argument is a race. The component of the weights along $\mathbf{u}$ grows linearly in the number of mistakes, while their length can grow only like its square root; since a component cannot exceed the length, the mistakes must stop. Novikoff (1962) put it as a lower bound on the squared length of the weights growing like $n^2$ against an upper bound on it growing like $n$, after $n$ corrections, which "are incompatible for $n$ sufficiently large"; his version allows a positive threshold and any starting weights and leaves the constant implicit, and the bound $(R/\gamma)^2$ is what the same two inequalities give when the start is zero.
Several features of the bound are worth noting. It does not depend on the number of examples, the number of inputs, or the order in which the examples are visited; only on how far apart the classes are relative to the size of the inputs. It bounds mistakes, not epochs: a run can take many epochs that each make few mistakes. It is a worst case, and typical runs make far fewer mistakes. And it guarantees only that the training data end up separated, by whichever separating hyperplane the run happens to reach.
The bound checked
For each problem below, $\gamma$ is the largest margin of any unit vector $\mathbf{u}$ in the augmented space, found by solving the quadratic program "minimize $\lVert \mathbf{w} \rVert^2$ subject to $\tilde{y}_i \mathbf{w}^{\mathsf{T}}\tilde{\mathbf{x}}_i \geq 1$" (then $\gamma = 1/\lVert \mathbf{w} \rVert$); this gives the tightest bound the theorem allows. The rule was then run in 30 random orders, each epoch a fresh shuffle.
| Problem | $R$ | $\gamma$ | Bound $(R/\gamma)^2$ | Mistakes: median (IQR) | Max |
|---|---|---|---|---|---|
| AND | 1.732 | 0.2425 | 51.0 | 17.5 (15.0–20.0) | 22 |
| Iris, setosa or not, raw petal sizes | 7.342 | 0.2685 | 747.7 | 8.0 (4.0–11.8) | 20 |
| Iris, petal sizes centered | 3.476 | 0.4014 | 75.0 | 2.0 (1.0–4.0) | 6 |
Every run stayed well inside the bound. The iris rows show the bound's sensitivity to how the inputs are expressed. With raw petal measurements in centimeters, the longest input has length 7.34, mostly because a petal 6.9 cm long is far from the origin, and the constant input 1 is small beside the measurements. Subtracting the mean petal length (3.758 cm) and width (1.199 cm) moves the data around the origin, halves $R$ and increases $\gamma$, cutting the bound tenfold; the runs speed up too, from a median of 8 mistakes to 2. Centering and scaling the inputs, as K-Nearest Neighbors shows for distances, matters for perceptrons and for neural networks generally.
When no separating hyperplane exists
The theorem needs a margin. Without one the rule never stops changing the weights.
XOR is the standard example: the targets are 0 for $(0, 0)$ and $(1, 1)$ and 1 for $(0, 1)$ and $(1, 0)$. Suppose a perceptron computed it. Then $(0, 0)$ needs $b < 0$; $(1, 0)$ and $(0, 1)$ need $w_1 + b \geq 0$ and $w_2 + b \geq 0$; and $(1, 1)$ needs $w_1 + w_2 + b < 0$. Adding the middle two gives $w_1 + w_2 + 2b \geq 0$, so $w_1 + w_2 + b \geq -b > 0$, contradicting the last. No weights work, so XOR is not linearly separable. Run on XOR from zero weights in the fixed order above, the rule makes 3 mistakes in each of the first two epochs and 4 in every epoch after that, for as long as it is run (1,000 epochs here): from the start of the third epoch on, the weights return to $\mathbf{w} = (-1, 0)$, $b = 0$ at the start of every epoch and go round the same cycle. Hastie et al. (2009, §4.5.1), following Ripley (1996), list this as one of the rule's problems: on data that are not separable the algorithm does not converge, and cycles develop that "can be long and therefore hard to detect." The introduction shows how one hidden layer computes XOR; Minsky and Papert's Perceptrons (1969) made the limits of single-layer machines on problems of this kind a central argument of its analysis.
Separable data can be almost as bad when the margin is small, because the bound grows with $1/\gamma^2$. The breast cancer data (Wolberg, Mangasarian, Street and Street, 1993) describe 569 tumors by 30 measurements of their cell nuclei. In 30 random splits into 398 training and 171 test tumors, with the inputs standardized on the training part, a linear program found that the training tumors were linearly separable in all 30. But for the first split $\gamma = 0.0565$ and $R = 19.77$, so the theorem allows up to 122,415 mistakes. The rule needed 1,335 mistakes and 234 epochs to separate those training tumors. After 100 epochs it was still making a median of 7.5 mistakes per epoch across the 30 splits, ranging from 0 to 13, and its weights were still jumping from one boundary to another.
Stopping such a run after a fixed number of epochs leaves whatever weights the last update produced. A common remedy is the averaged perceptron, which predicts with the average of the weight vectors over all the steps of training rather than the last one, damping the jumps (Freund and Schapire, 1999). On the 171 test tumors of each split, after 100 epochs:
| Classifier | Test accuracy: median (IQR) | Lowest |
|---|---|---|
| Perceptron, final weights | 0.9649 (0.9532–0.9708) | 0.9298 |
| Averaged perceptron | 0.9708 (0.9591–0.9766) | 0.9298 |
scikit-learn Perceptron, defaults |
0.9649 (0.9532–0.9708) | 0.9181 |
| Logistic regression (L2, $C = 1$) | 0.9766 (0.9708–0.9825) | 0.9532 |
Logistic regression was more accurate than the plain perceptron in 26 of the 30 splits, tied in 3 and less accurate in 1, by a median of 1.2 percentage points, two tumors out of 171.
The perceptron and logistic regression
A single neuron with a sigmoid activation, trained to minimize the log loss, is logistic regression. Trained one example at a time by stochastic gradient descent, its update is
$$\mathbf{w} \leftarrow \mathbf{w} + r\,(y_i - p_i)\,\mathbf{x}_i, \qquad p_i = \sigma(\mathbf{w}^{\mathsf{T}}\mathbf{x}_i + b),$$
because the derivative of the log loss with respect to $z$ is $p_i - y_i$, as derived in Logistic Regression. The perceptron rule has the same form with the hard prediction $\hat{y}_i$ in place of the probability $p_i$. The difference matters. With weights giving $z = 0.2$ for some example, logistic regression's probability is $p = 0.5498$; if the true label is 0, the perceptron's error term is $-1$ and logistic regression's is $-0.5498$, and if the label is 1, the perceptron's is 0, no update at all, while logistic regression's is $0.4502$, still pushing an example that is barely on the correct side further from the boundary. Logistic regression learns from every example in proportion to how wrong its probability is; the perceptron learns only from mistakes, and all mistakes count the same.
The two also behave differently on separable data. The perceptron stops at the first separating hyperplane. Unpenalized logistic regression has no finite maximum likelihood estimate there: the likelihood keeps rising as the weights grow, the problem of separation described in Logistic Regression. A penalty, such as scikit-learn's default, gives it a unique answer. The support vector machine instead picks the separating hyperplane with the largest margin, a choice that the perceptron's convergence theorem shows to be natural, since the margin is what controls how hard the problem is.
In the margin notation of Loss Functions for Classification, with $m = \tilde{y}z$, the perceptron criterion charges $\max(0, -m)$ per example, the logistic loss $\ln(1 + e^{-m})$ and the hinge loss of the support vector machine $\max(0, 1 - m)$. The perceptron's loss is zero for any correctly classified example, however close to the boundary; the hinge loss keeps charging until the margin reaches 1; the logistic loss never quite reaches zero. Logistic regression's smooth loss, and the probabilities that come with it, are why multilayer networks are built from sigmoid-like or other differentiable units trained on the log loss, not from step units trained by the perceptron rule: the step function's derivative is zero almost everywhere, so it gives the hidden layers no gradient to learn from. The activation functions article takes up that thread.
In Python
scikit-learn implements the rule in sklearn.linear_model.Perceptron:
from sklearn.datasets import load_iris
from sklearn.linear_model import Perceptron
iris = load_iris()
X = iris.data[:, 2:4] # petal length and width (cm)
y = (iris.target == 0).astype(int) # 1 = setosa
clf = Perceptron(random_state=0).fit(X, y)
print(clf.coef_, clf.intercept_) # the weights and the bias
print(clf.score(X, y)) # 1.0: the classes are separable
Its defaults shuffle the data every epoch, use a learning rate eta0 of 1, and stop after at most max_iter=1000 epochs, or earlier once the loss stops improving. The rule itself fits in a few lines of NumPy, with the bias absorbed as a constant input:
import numpy as np
def perceptron(X, y, epochs=100, seed=0):
"""y in {-1, +1}. Returns weights for the inputs followed by the bias."""
Xa = np.column_stack([X, np.ones(len(y))])
w = np.zeros(Xa.shape[1])
rng = np.random.default_rng(seed)
for _ in range(epochs):
mistakes = 0
for i in rng.permutation(len(y)):
if y[i] * (Xa[i] @ w) <= 0: # wrong side, or on the boundary
w += y[i] * Xa[i]
mistakes += 1
if mistakes == 0:
break
return w
The numbers in this article, including the convergence bounds, the XOR cycle and the breast cancer comparison, are computed by tools/experiments/data-science/single-layer-perceptron.py in the site's repository.
References
- Fisher, R. A. (1936). The use of multiple measurements in taxonomic problems. Annals of Eugenics, 7(2), 179–188. Cited for the iris data; not read for this article. record
- Fisher, R. A. (1936). Iris [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C56C76 record
- Freund, Y., and Schapire, R. E. (1999). Large margin classification using the perceptron algorithm. Machine Learning, 37(3), 277–296. Cited by attribution for the averaged perceptron; not read for this article. record
- Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. §4.5. record · 23 pages
- Minsky, M., and Papert, S. (1969). Perceptrons: An Introduction to Computational Geometry. MIT Press. Cited by attribution; not read for this article. record · 2 pages
- Novikoff, A. B. J. (1962). On convergence proofs for perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata (Vol. 12, pp. 615–622). Polytechnic Institute of Brooklyn. record
- Ripley, B. D. (1996). Pattern Recognition and Neural Networks. Cambridge University Press. Cited through Hastie et al. (2009). record
- Rosenblatt, F. (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), 386–408. record · 2 pages
- scikit-learn developers (2024). Perceptron. scikit-learn 1.6 documentation. https://scikit-learn.org/1.6/modules/generated/sklearn.linear_model.Perceptron.html record
- Wolberg, W., Mangasarian, O., Street, N., and Street, W. (1993). Breast Cancer Wisconsin (Diagnostic) [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C5DW2B record · 14 pages