3 Perceptron
Context
Frank Rosenblatt (Cornell) wants more than a network that computes — he wants a self-teaching pattern-recognition machine. The "Mark I Perceptron" was hardware: a "retina" of 400 photocells, weights held in motorised potentiometers, training turning the knobs. The 1958 demonstration set off a wave of hype (the press, quoting the Navy, wrote about a machine that would "be conscious of its own existence").
The idea and the mechanism
The perceptron takes a weighted sum and applies the sign:
What is genuinely new is the learning rule. You show it examples with a label t ∈ {−1, +1}; on a mistake you nudge the weights towards the correct answer:
Geometrically w is the normal to the separating hyperplane; on a mistake we add the input vector itself, rotating the plane towards the misclassified point.
linear algebra The convergence theorem: why there are no more than (R/γ)² mistakes
Suppose the data is separated by a unit w* (‖w*‖ = 1) with margin γ, that is ti(w*·xi) ≥ γ for every point, and all ‖xi‖ ≤ R. Start from w = 0. Bound the norm of w after k mistakes from both sides.
From below. Every mistake moves w ← w + tixi, and the projection onto w* grows by at least γ:
From above. On a mistake ti(w·xi) ≤ 0, so the norm grows by no more than R²:
Put them together. kγ ≤ ‖wk‖ ≤ √ k R, hence √ k ≤ R/γ and finally:
The number of mistakes is finite and does not depend on the dimensionality — only on the geometry (radius of the data / margin). This is an early specimen of margin-based generalization, an idea that will come into full bloom in the SVM (#10).
NumPy Implementation: training a perceptron
import numpy as np
def perceptron(X, y, eta=1.0, epochs=100):
w = np.zeros(X.shape[1]); b = 0.0
for _ in range(epochs):
errors = 0
for xi, ti in zip(X, y): # ti ∈ {−1, +1}
if ti * (w @ xi + b) <= 0: # misclassification
w += eta * ti * xi # rotate the plane towards the point
b += eta * ti
errors += 1
if errors == 0: # separable → converged
break
return w, bWhy it matters
The perceptron is the direct ancestor of the modern artificial neuron: linear combination → nonlinearity → a gradient-flavoured weight update. Any deep network is a multi-layer construction out of such elements. And this is the first case of provable machine learning. The flip side is cautionary: inflated expectations and a real limitation (linearly separable data only) will collide in Minsky and Papert's book.
Connections
The same threshold neuron, but now with trainable weights and an algorithm that tunes them from labeled examples. The perceptron is the MP neuron taught how to learn.
The convergence theorem holds only for linearly separable data. Minsky and Papert show rigorously that XOR does not fall into that class — and cut the theorem off exactly where linear separability ends.
The limitation goes away once you add hidden layers — but you have to be able to train them. Backprop generalizes "move the weights along the error" to the multi-layer case via the chain rule, and XOR falls.
Both are linear separators, and both hinge on the margin γ. But the perceptron only uses the margin (for its convergence guarantee), whereas the SVM maximizes it — it picks not just any separating plane, but the most robust one.
Questions worth asking
The theorem guarantees convergence — but what if the data is NOT linearly separable?
Then there is no guarantee: the algorithm oscillates forever, hopping between weight vectors, and never stops. In practice you take the "pocket" variant (keep the best weights seen so far) or move to methods that tolerate errors (logistic regression, soft-margin SVM). This very failure on non-separable data is what Minsky and Papert will expose with XOR.
The (R/γ)² bound does not depend on the dimensionality — isn't that odd?
On the contrary, it is a deep result. The number of mistakes is set by the geometry (radius of the data and the margin), not by the number of features — you can work in a million-dimensional space and the bound is the same. This is an early example of margin-based analysis of generalization: "quality depends on the margin, not the dimensionality". The same philosophy underpins the SVM and Vapnik's theory.
How does the perceptron rule differ from gradient descent and logistic regression?
The perceptron rule is a subgradient of a piecewise (hinge-like) loss that fires only on mistakes and gives you no probabilities. Logistic regression minimizes a smooth probabilistic loss and updates on every example. The perceptron is the hard-edged ancestor of that family; SGD and logistic regression are its smoothed, probabilistic descendants.
What to read in the original
Read selectively: the model and the update rule. The psychological framing can be skimmed. The convergence theorem, though (the role of the R/γ ratio), is worth understanding — it is the first bridge to the idea of the margin, which will become the core of the SVM and of generalization theory.