In 1958 Frank Rosenblatt demonstrated a machine at Cornell that learned to distinguish simple visual patterns. The New York Times reported excitedly that the navy expected the device to one day "walk, talk, see, write, reproduce itself and be conscious of its existence". The reality was more modest — but the perceptron was the first practical learning algorithm for a neural model, and its ideas live on in every network today.
The model#
For input $\mathbf{x} \in \mathbb{R}^d$ and label $y \in \{-1, +1\}$, the perceptron predicts
a linear classifier with a hard threshold.
The learning rule#
Loop over training examples. Whenever an example is misclassified ($y_i(\mathbf{w}^\top\mathbf{x}_i + b) \le 0$), update:
Correct examples cause no change. Intuition: if a positive example scored too low, add it to $\mathbf{w}$, increasing $\mathbf{w}^\top\mathbf{x}_i$ next time; if a negative example scored too high, subtract it.
This is stochastic gradient descent on the perceptron loss $\max(0, -y_i(\mathbf{w}^\top\mathbf{x}_i + b))$ — a cousin of the SVM hinge loss without the margin.
import numpy as np
def perceptron(X, y, epochs=50, lr=1.0):
w, b = np.zeros(X.shape[1]), 0.0
for epoch in range(epochs):
mistakes = 0
for xi, yi in zip(X, y):
if yi * (w @ xi + b) <= 0:
w += lr * yi * xi; b += lr * yi; mistakes += 1
if mistakes == 0:
print(f"converged after {epoch + 1} epochs")
break
return w, b
rng = np.random.default_rng(0)
X = np.vstack([rng.normal([2, 2], 0.7, (50, 2)), rng.normal([-2, -2], 0.7, (50, 2))])
y = np.r_[np.ones(50), -np.ones(50)]
w, b = perceptron(X, y)
print("accuracy:", np.mean(np.sign(X @ w + b) == y))The perceptron convergence theorem#
Theorem (Novikoff, 1962). Suppose the data is linearly separable with margin $\gamma$: there is a unit vector $\mathbf{w}^*$ with $y_i\,\mathbf{w}^{*\top}\mathbf{x}_i \ge \gamma > 0$ for all $i$, and all $\|\mathbf{x}_i\| \le R$. Then the perceptron (with $b$ absorbed into $\mathbf{w}$) makes at most
mistakes, regardless of the order of examples or the dimension.
Proof sketch. After $k$ mistakes starting from $\mathbf{w} = \mathbf{0}$:
- Each update increases the projection onto $\mathbf{w}^*$ by at least $\gamma$: $\mathbf{w}_k^\top\mathbf{w}^* \ge k\gamma$.
- Each update increases the squared norm by at most $R^2$ (because the example was misclassified, the cross term is non-positive): $\|\mathbf{w}_k\|^2 \le kR^2$.
By Cauchy–Schwarz, $k\gamma \le \mathbf{w}_k^\top\mathbf{w}^* \le \|\mathbf{w}_k\| \le \sqrt{k}R$, hence $k \le R^2/\gamma^2$. $\blacksquare$
The XOR problem and the first AI winter#
If data is not linearly separable, the perceptron never converges; it cycles forever. The simplest example is XOR:
| $x_1$ | $x_2$ | XOR |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
No single line separates the ones from the zeros. Minsky and Papert's 1969 book Perceptrons rigorously analysed such limitations of single-layer perceptrons (for instance, computing connectedness of a figure). Although they knew multilayer networks could represent more, there was no known way to train them, and research funding for neural networks declined sharply.
The solution: hidden layers#
A two-layer network solves XOR easily: one hidden unit computes OR, another computes AND, and the output computes "OR and not AND". The problem was learning the hidden-layer weights — solved by backpropagation in the 1980s, as we will see shortly.
Variants#
- Averaged perceptron — average weights over all steps; generalises much better and was a strong NLP tagger for years.
- Voted perceptron — weighted vote of intermediate weight vectors.
- Kernel perceptron — replace dot products with kernels for non-linear boundaries.