Perceptron

The perceptron is a binary classifier together with the rule that trains it. It classifies an input by the sign of a weighted sum of its features, a linear threshold unit, and learns the weights by error correction: whenever it misclassifies a training example, it adds that example’s feature vector to the weights, or subtracts it, so that the example’s score moves towards the correct side. Frank Rosenblatt proposed it in the late 1950s as a model of how a brain might learn to recognize patterns (Bottou, 2017; Nagy, 2011), and built a machine, the Mark I, that learned to classify images from a camera (Bishop, 2006, §4.1.7). It is also known as the single-layer perceptron, the perceptron learning rule or Rosenblatt’s perceptron.

The perceptron is a supervised linear classifier in the sense of machine learning; the neural network and multilayer perceptron articles cover the networks that grew from it.

Problem

Given images described by feature vectors $\mathbf{x}_i \in \mathbb{R}^d$ with labels $y_i \in \{-1, +1\}$, find a hyperplane that puts every positive example on one side and every negative example on the other, by looking at one example at a time. The features may be pixel values, hand-designed measurements of a shape, or the outputs of fixed random detectors, as in Rosenblatt’s machines.

Inputs and Outputs

• Input: labelled examples $(\mathbf{x}_i, y_i)$, presented one after another, and a limit on the number of passes (epochs) through them.
• Output: a weight vector $\mathbf{w}$. A new example is classified as $\hat{y} = \operatorname{sign}(\mathbf{w}^\top \mathbf{x})$. The bias is handled by appending a constant 1 to every $\mathbf{x}$, so its weight is the last entry of $\mathbf{w}$.

Intuition

The weight vector is the normal of the decision boundary, and it points into the positive side. When a positive example falls on the negative side, adding it to $\mathbf{w}$ tilts the normal towards it; when a negative example falls on the positive side, subtracting it tilts the normal away. A correction can spoil examples that were right before. But if some hyperplane separates the classes with room to spare, every correction moves $\mathbf{w}$ a fixed amount further in its direction while the length of $\mathbf{w}$ grows only slowly, so the corrections must stop.

Algorithm

1. Append a constant 1 to every feature vector. Set $\mathbf{w} = \mathbf{0}$.
2. For each example $(\mathbf{x}_i, y_i)$ in turn: if $y_i \, \mathbf{w}^\top \mathbf{x}_i \le 0$ (a mistake; a score of exactly zero counts as one), set $\mathbf{w} \leftarrow \mathbf{w} + y_i \mathbf{x}_i$. Otherwise leave $\mathbf{w}$ unchanged.
3. Repeat step 2 over the training set until a full pass makes no mistake, or until the epoch limit.

Mathematical Formulation

Model and update

Rosenblatt’s unit computes a fixed transformation $\phi(\mathbf{x})$ of the input and then $y(\mathbf{x}) = f(\mathbf{w}^\top \phi(\mathbf{x}))$, where $f$ is a step function returning $+1$ for a non-negative argument and $-1$ otherwise (Bishop, 2006, §4.1.7); the code below uses the features directly as $\phi$. Bishop derives the learning rule as stochastic gradient descent on the perceptron criterion

$$E_P(\mathbf{w}) = -\sum_{i \in \mathcal{M}} y_i \, \mathbf{w}^\top \mathbf{x}_i,$$

where $\mathcal{M}$ is the set of misclassified examples. The count of misclassified examples would be the natural loss, but its gradient is zero almost everywhere. A step on one misclassified example gives $\mathbf{w} \leftarrow \mathbf{w} + \eta \, y_i \mathbf{x}_i$; since scaling $\mathbf{w}$ by a positive constant changes no prediction, starting from $\mathbf{w} = \mathbf{0}$ any $\eta$ gives the same predictions as $\eta = 1$. An update can increase the error on other examples, so $E_P$ need not decrease at each step.

The convergence theorem

Freund and Schapire (1999, §3.1) credit the first proofs of the perceptron convergence theorem to Block (1962) and Novikoff (1962); Bishop (2006, §4.1.7) also lists Rosenblatt’s Principles of Neurodynamics (1962) among the places a proof can be found. Freund and Schapire state it as a mistake bound (their Theorem 1, credited to Block and Novikoff). Let $(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_m, y_m)$ be a sequence of labelled examples with $\lVert \mathbf{x}_i \rVert \le R$. Suppose there is a vector $\mathbf{u}$ with $\lVert \mathbf{u} \rVert = 1$ and

$$y_i \, \mathbf{u}^\top \mathbf{x}_i \ge \gamma > 0 \quad \text{for all } i.$$

Then the number $k$ of mistakes that the perceptron, started at $\mathbf{w} = \mathbf{0}$, makes on the sequence satisfies

$$k \le \left( \frac{R}{\gamma} \right)^2$$

The proof, as they give it: each mistake adds $y_i \mathbf{u}^\top \mathbf{x}_i \ge \gamma$ to $\mathbf{w}^\top \mathbf{u}$, so after $k$ mistakes $\mathbf{w}^\top \mathbf{u} \ge k\gamma$. Each mistake adds $2 y_i \mathbf{w}^\top \mathbf{x}_i + \lVert \mathbf{x}_i \rVert^2 \le R^2$ to $\lVert \mathbf{w} \rVert^2$, because $y_i \mathbf{w}^\top \mathbf{x}_i \le 0$ on a mistake, so after $k$ mistakes $\lVert \mathbf{w} \rVert \le \sqrt{k} R$. Since $\mathbf{w}^\top \mathbf{u} \le \lVert \mathbf{w} \rVert$, $k\gamma \le \sqrt{k} R$, which gives the bound.

The bound holds for any order of presentation and does not depend on the dimension $d$, which Freund and Schapire single out as the reason to expect the perceptron to work in high-dimensional spaces. Cycling through a separable training set is one long sequence, so the algorithm stops making mistakes after at most $(R/\gamma)^2$ updates. The best $\gamma$ is the largest margin of any separating hyperplane through the origin in the augmented space. A hard-margin support vector machine maximizes almost the same quantity, but leaves its bias out of the norm; the perceptron itself stops at the first separating hyperplane it reaches, which can lie close to some examples. By our reasoning, both $R$ and $\gamma$ change when features are rescaled or when the constant appended for the bias changes, so the bound is a statement about a particular representation of the data.

Non-separable data

If no separating hyperplane exists, the algorithm never converges: every pass contains a mistake, and the weight vector keeps moving. Bishop (2006, §4.1.7) adds that until convergence happens, a slow separable problem cannot be told apart from a non-separable one, and that on separable data the hyperplane found depends on the initialization and the order of the examples. For data that are not separable, Freund and Schapire (1999, Theorem 2) give a bound on the mistakes over any sequence, which they present as new: for any unit $\mathbf{u}$ and $\gamma > 0$, define the deviation $d_i = \max\{0, \gamma - y_i \mathbf{u}^\top \mathbf{x}_i\}$ and $D = \sqrt{\sum_i d_i^2}$; then the number of mistakes is at most $((R + D)/\gamma)^2$.

Linear Separability, XOR and Minsky and Papert

Two classes are linearly separable in a feature space when a hyperplane separates them: the case the convergence theorem covers. The textbook example of a function that no single threshold unit on its raw inputs can compute is the exclusive or (XOR) of two binary inputs: the four input patterns impose contradictory conditions on the weights. Minsky and Papert (1967, pp. 183–185) prove this for XOR’s complement, equality of the two inputs, which they call “a simple, almost trivial example”.

Minsky and Papert analysed a broader model. In their 1967 paper, a property $\psi$ of a figure $X$ is a linear threshold function of a family of fixed predicates $\phi$ if $\psi(X) = [\sum_\phi \alpha_\phi \phi(X) > \theta]$ for some weights $\alpha_\phi$ and threshold $\theta$, where each $\phi$ depends on a subset of the points of the input space (p. 179). The order of $\psi$ is the smallest $k$ for which a family whose predicates each depend on at most $k$ points suffices (pp. 176, 179–180). In this model XOR has order 2 (p. 180): a predicate that looks at both inputs, such as their product, makes it computable. Their results concern how order grows with the number of points $n$ of the input space:

• Parity (whether the number of points in a figure is odd) has order $n$: at least one predicate must look at every point (pp. 187–188).
• Connectedness is not of any finite order: no fixed $k$ suffices as the input space grows (stated on pp. 176–177). Their 1969 book Perceptrons analyses tasks such as parity and connectedness in the same terms, and Bottou (2017) cites its proof that no finite-order perceptron can represent connectedness (§5.2).

In our reading, these are statements about which properties a single layer of adaptive weights over predicates of bounded support can represent, not about XOR in particular and not about networks whose intermediate features are learned. Bishop (2006, §4.1.7) says the book was widely misread as showing that neural networks were fatally flawed, that it proved such limitations only for single-layer networks and conjectured, incorrectly, that they extended to more general networks, and that it contributed to the decline in funding for neural network research that lasted until the mid-1980s. Bottou (2017) gives the authors’ side: in the 1988 expanded edition they argued that progress had already stalled for lack of basic theory, and Papert wrote in 1988 that part of their drive came from funding spent on what he saw as misleading applications, but most of it from seeking a balance between romanticism and rigor. Bottou reads the book as an attempt to correct a flaw in the research rather than to end it.

For vision the lesson is in the features: whether two classes of images are separable depends on the representation, as the example below shows by changing only the size at which shapes are drawn.

Parameters and Complexity

The plain perceptron has no step size to tune. What it does have is an epoch limit, which on non-separable data decides which weight vector is returned; an order of presentation, which changes the result and is made reproducible by shuffling with a fixed seed; and the features, whose choice decides separability and whose scale, with the value of the bias constant, sets $R/\gamma$. Each example costs one inner product and, on a mistake, one vector addition, so an epoch over $m$ examples takes $O(md)$ time and the weights $O(d)$ memory.

Implementation

The example renders filled discs and squares in 24×24 binary images, at random positions, sizes and rotations (at the largest sizes a rotated square can reach past the image border and be cut off), and describes each by two features: the extent (the shape’s area divided by the area of its axis-aligned bounding box) and the largest distance from the centroid to a shape pixel, divided by the radius of a disc of the same area. A disc scores about 1 on the second feature and a square about $\sqrt{\pi/2} \approx 1.25$, whatever the rotation (our calculation). Features are standardized with training statistics and a constant 1 is appended.

The first part draws the shapes 8 to 18 pixels across. A linear program checks that the training set is separable, a hard-margin fit without a free bias gives the largest margin $\gamma$, and the perceptron is run to convergence for 20 presentation orders. The second part draws the same shapes 3 to 8 pixels across, where pixelation makes small discs and small rotated squares look alike, and runs 100 epochs, comparing the last weight vector with two variants described below: the pocket vector (here, the vector with the longest run of consecutive correct predictions) and the average of the weight vector over all steps. It runs in about a second.

import numpy as np
from scipy.optimize import linprog, minimize

N = 24                                    # images are 24 x 24 pixels
yy, xx = np.mgrid[0:N, 0:N] + 0.5         # pixel centres

def render(kind, size, angle, cx, cy):
    """Binary image of a disc (radius = size) or a square (half-side = size)."""
    dx, dy = xx - cx, yy - cy
    if kind == "disc":
        return dx**2 + dy**2 <= size**2
    c, s = np.cos(angle), np.sin(angle)
    u, v = c * dx + s * dy, -s * dx + c * dy
    return (np.abs(u) <= size) & (np.abs(v) <= size)

def features(mask):
    """Two shape features: extent (area / bounding-box area) and
    max centroid distance relative to the radius of a disc of equal area."""
    ys, xs = np.nonzero(mask)
    area = len(xs)
    extent = area / ((np.ptp(xs) + 1) * (np.ptp(ys) + 1))
    r_max = np.hypot(xs - xs.mean(), ys - ys.mean()).max()
    return extent, r_max / np.sqrt(area / np.pi)

def dataset(rng, n, smin, smax):
    X, y = [], []
    for i in range(n):
        kind = "square" if i % 2 == 0 else "disc"
        mask = render(kind, rng.uniform(smin, smax), rng.uniform(0, np.pi / 2),
                      *rng.uniform(10, 14, 2))
        X.append(features(mask))
        y.append(1 if kind == "square" else -1)
    return np.array(X), np.array(y)

def augment(X, mean, std):
    """Standardize with training statistics and append a constant 1 (the bias)."""
    return np.c_[(X - mean) / std, np.ones(len(X))]

def is_separable(X, y):
    """Feasibility LP: is there a w with y_i (w . x_i) >= 1 for all i?"""
    res = linprog(np.zeros(X.shape[1]), A_ub=-y[:, None] * X, b_ub=-np.ones(len(y)),
                  bounds=[(None, None)] * X.shape[1], method="highs")
    return res.status == 0

def max_margin(X, y):
    """Largest gamma = min_i y_i (u . x_i) over unit vectors u (hard-margin SVM, no free bias)."""
    res = minimize(lambda w: w @ w, np.ones(X.shape[1]), jac=lambda w: 2 * w,
                   constraints={"type": "ineq", "fun": lambda w: y * (X @ w) - 1,
                                "jac": lambda w: y[:, None] * X},
                   method="SLSQP", options={"ftol": 1e-12, "maxiter": 1000})
    return 1 / np.linalg.norm(res.x)

def perceptron(X, y, epochs, rng, stop_when_clean=True):
    """Rosenblatt's rule: on a mistake, w <- w + y_i x_i. Also tracks the pocket
    (the vector with the longest run of consecutive correct predictions) and the
    average of w over all steps."""
    w = np.zeros(X.shape[1]); w_sum = np.zeros_like(w)
    pocket, best_run, run, updates, steps, history = w.copy(), 0, 0, 0, 0, []
    for epoch in range(epochs):
        mistakes = 0
        for i in rng.permutation(len(y)):
            if y[i] * (w @ X[i]) <= 0:           # mistake (a score of 0 counts as one)
                w = w + y[i] * X[i]
                mistakes += 1; updates += 1; run = 0
            else:
                run += 1
                if run > best_run:
                    best_run, pocket = run, w.copy()
            w_sum += w; steps += 1
        history.append(mistakes)
        if stop_when_clean and mistakes == 0:
            break
    return w, pocket, w_sum / steps, updates, history

def error(w, X, y):
    return np.mean(np.sign(X @ w) != y)

# --- 1. Large shapes: linearly separable in the two features -------------------
rng = np.random.default_rng(0)
Xtr, ytr = dataset(rng, 200, 4, 9)        # discs and squares 8-18 px across, any rotation
mean, std = Xtr.mean(0), Xtr.std(0)
X = augment(Xtr, mean, std)
R = np.linalg.norm(X, axis=1).max()
gamma = max_margin(X, ytr)
print(f"separable: {is_separable(X, ytr)}   R = {R:.3f}   gamma = {gamma:.4f}   "
      f"Novikoff bound (R/gamma)^2 = {(R / gamma) ** 2:.0f}")
runs = [perceptron(X, ytr, 1000, np.random.default_rng(s)) for s in range(20)]
upd = np.array([r[3] for r in runs]); ep = np.array([len(r[4]) for r in runs])
print(f"20 presentation orders: updates min {upd.min()}, median {np.median(upd):.0f}, "
      f"max {upd.max()};  epochs to a clean pass {ep.min()}-{ep.max()}")
print("training error of every final w:", max(error(r[0], X, ytr) for r in runs))

# --- 2. Small shapes: pixelation makes the classes overlap ---------------------
rng = np.random.default_rng(1)
Xtr, ytr = dataset(rng, 200, 1.5, 4)      # 3-8 px across
Xte, yte = dataset(rng, 2000, 1.5, 4)
mean, std = Xtr.mean(0), Xtr.std(0)
X, Xt = augment(Xtr, mean, std), augment(Xte, mean, std)
print(f"\nseparable: {is_separable(X, ytr)}")
w, pocket, avg, updates, hist = perceptron(X, ytr, 100, np.random.default_rng(0),
                                           stop_when_clean=False)
print("mistakes in epochs 1, 10, 50, 100:", [hist[e - 1] for e in (1, 10, 50, 100)])
last_err = []
for E in (96, 97, 98, 99, 100):          # the last vector after each of the final epochs
    last_err.append(error(perceptron(X, ytr, E, np.random.default_rng(0), False)[0], X, ytr))
print("training error of the last w after epochs 96-100:", np.round(last_err, 3))
print(f"{'':10s}{'train':>8s}{'test':>8s}")
for name, v in [("last", w), ("pocket", pocket), ("average", avg)]:
    print(f"{name:10s}{error(v, X, ytr):8.3f}{error(v, Xt, yte):8.3f}")
te = np.array([[error(v, Xt, yte) for v in perceptron(X, ytr, 100, np.random.default_rng(s), False)[:3]]
               for s in range(20)])
print("test error over 20 orders (min-max): last %.3f-%.3f, pocket %.3f-%.3f, average %.3f-%.3f"
      % tuple(np.r_[te.min(0), te.max(0)].reshape(2, 3).T.ravel()))

separable: True   R = 2.564   gamma = 0.2569   Novikoff bound (R/gamma)^2 = 100
20 presentation orders: updates min 2, median 3, max 6;  epochs to a clean pass 2-4
training error of every final w: 0.0

separable: False
mistakes in epochs 1, 10, 50, 100: [46, 33, 44, 39]
training error of the last w after epochs 96-100: [0.11  0.255 0.11  0.18  0.415]
             train    test
last         0.415   0.390
pocket       0.100   0.113
average      0.110   0.133
test error over 20 orders (min-max): last 0.110-0.651, pocket 0.110-0.132, average 0.127-0.134

On the large shapes the two features separate the classes, and the perceptron needs between 2 and 6 corrections over the 20 orders, against a bound of 100. The bound is a worst case over every sequence of examples with the same $R$ and $\gamma$; in our reading, a shuffled training set whose examples mostly lie far from the boundary needs far fewer corrections than an adversarial order would. All 20 final vectors classify the training set without error, as the theorem guarantees.

On the small shapes the linear program finds no separating hyperplane, and the perceptron never completes a clean pass: the epochs shown still have 33 to 46 mistakes each. The last weight vector is wherever the latest correction left it, so its training error jumps between 0.11 and 0.415 in five consecutive epochs, and over 20 orders its test error ranges from 0.110 to 0.651, worse than guessing at the upper end. The pocket and averaged vectors give test errors of 0.110–0.132 and 0.127–0.134 over the same orders. In our reading, averaging damps the oscillation because corrections in opposite directions cancel in the sum; the pocket keeps the vector that survived longest, which Freund and Schapire (1999, §3.3) describe as likely to be better than one that survived only a few examples. Neither can beat the best hyperplane in these two features, so a lower error would need a different representation: another feature, a higher resolution or learned features.

Limitations

• Linear boundaries in fixed features. Rosenblatt’s machines relied on fixed, often random, feature detectors (Bishop, 2006, §4.1.7); the perceptron cannot learn better ones; and, by our reasoning, because its step function has zero gradient almost everywhere, layers of threshold units cannot be trained by backpropagation.
• No probabilities and two classes only. Bishop notes that it gives no probabilistic outputs and does not extend readily to more than two classes; logistic regression replaces the step by a sigmoid and gives both.
• Unstable on non-separable data, where the last weight vector depends on where training stops, unless one of the variants below is used.

Variants

• Pocket algorithm. Freund and Schapire (1999, §3.3) credit Gallant (1986) with the pocket method: keep, besides the running vector, the one that survived the longest run of correct predictions, and return it. It gives a usable answer on non-separable data.
• Voted and averaged perceptron. Freund and Schapire (1999) store every vector the algorithm produces with the number of examples it survived, and predict by a vote of their signs weighted by survival; the averaged variant weights their scores instead, which amounts to predicting with the average weight vector (our reasoning from their definition). They derived generalization bounds for the voted perceptron after one epoch, close to those for support vector machines on separable data. On the 10-class NIST handwritten digit data in the setup of Cortes and Vapnik (60,000 training and 10,000 test images, 28×28 pixels), they reported that voting and averaging performed about equally and better than the last vector, especially before convergence; without a kernel, after 10 epochs, the test errors were 8.1% for the vote and 13.5% for the last (unnormalized) vector (Table 1).
• Kernel perceptron. Starting from zero, the weights are a sum of the training examples on which mistakes were made, each with sign $y_j$. Therefore predictions need only inner products, which can be replaced by a kernel $K(\mathbf{x}_j, \mathbf{x})$: predict $\operatorname{sign}\big(\sum_j c_j y_j K(\mathbf{x}_j, \mathbf{x})\big)$, where $c_j$ counts the mistakes on example $j$. Freund and Schapire (1999, §4) attribute the combination of kernels with the perceptron to Aizerman, Braverman and Rozonoer (1964). With a polynomial kernel of degree 4 they reported 1.6% test error for the vote on the same digits after 30 epochs (Table 1), against 1.1% for Cortes and Vapnik’s support vector machine with the same kernel; in their account the perceptron is close to but not as accurate as the maximal-margin classifier, while saving computation time and programming effort.

History

Rosenblatt, trained in psychology at Cornell and working at the Cornell Aeronautical Laboratory, described the perceptron in a January 1957 laboratory report and in the 1958 Psychological Review paper, and summarized his work up to 1961 in Principles of Neurodynamics (Nagy, 2011, a former doctoral student of his). According to Bishop (2006, §4.1.7), he first simulated the perceptron on an IBM 704 computer at Cornell in 1957 and by the early 1960s had built special-purpose hardware. In the Mark I perceptron, a camera focused a brightly lit scene, such as a printed character, onto a 20×20 array of cadmium sulphide photocells, a 400-pixel image; a patch board wired these inputs to the feature units, often at random; and each adaptive weight was a potentiometer turned by an electric motor (Bishop, 2006, Fig. 4.8). Nagy gives the Mark I’s size as 400 sensory, 512 association and 8 response units, and stresses that Rosenblatt saw the perceptron first as a model of the brain rather than as a pattern-recognition device.

Bottou (2017) describes the convergence theorem, which followed almost at once, as equally surprising, and a wave of optimism after it; but the most obvious application, computer vision, needed far more computing than the 1960s offered, and by the time Minsky and Papert’s book appeared almost a decade later, perceptron research had produced no successful real-world application. In the same years Widrow and colleagues developed the closely related ADALINE, the same model trained by a different rule (Bishop, 2006, §4.1.7). After the book, research on such machines lacked fashion and funding until the mid-1980s, when the work of the PDP Research Group and the early successes of back-propagation in multilayer perceptrons revived it (Bottou, 2017), the step the deep learning article traces. Freund and Schapire (1999) later turned the perceptron into a large-margin classifier, in the voted and kernel forms above.