Definition
The perceptron learning algorithm is the online procedure that visits labelled examples , , one at a time and, whenever , updates . It is mistake-driven: correctly classified examples change nothing. Its analysis, Novikoff's theorem (1962), was one of the first convergence guarantees for any learning algorithm.
The perceptron article introduced the neuron, the rule and the XOR failure. This one is about the algorithm as an object of study: what one update does geometrically, why it must stop on separable data and how fast, what happens when it cannot stop, and the three classic repairs (pocket, averaging, kernels). Throughout, folds the bias into , and starts at with . From a zero start, only rescales and changes no prediction.
The geometry of one update
Read as the normal vector of the decision hyperplane : it points into the half-space. A mistake on a point means sits on the wrong side, at an obtuse angle to . Adding to tilts the normal toward . A mistake on a point subtracts , tilting the normal away. In both cases the new normal is the vector sum , and the hyperplane rotates and shifts toward putting that point on the correct side.
- functional margin of the point before the update (≤ 0 on a mistake)
- the guaranteed improvement on that point; it may still be wrong afterwards, and other points may break
So a single update is a local repair with no global guarantee. The update can make other points wrong, which is why the algorithm takes repeated passes (epochs). The theorem below shows that on separable data the repairs cannot go on forever.
Margin and the convergence theorem
Assume the data are linearly separable with margin : some unit vector () satisfies for every . Let . Novikoff (1962) proved:
- radius of the augmented data,
- margin of a unit-norm separator ; the bound is tightest for the max-margin , but any separating gives a valid bound
Proof sketch: two inequalities that cannot both keep holding
- 1Alignment grows linearly. On the -th mistake, . By induction from : .
- 2Length grows only like . . The middle term is because the update happened on a mistake, so , giving .
- 3Squeeze. Cauchy–Schwarz with : . Hence , i.e. .
The geometric reading is an angle. . Every mistake forces the normal closer in angle to some good separator, and a cosine cannot exceed 1. The bound depends on neither the number of examples nor the dimension , only on the ratio of data radius to margin. That dimension-free property is what kernel methods later exploited.
Worked example: six points, twelve mistakes
Take : and : , visited in that order. The max-margin unit separator in augmented space is , i.e. the line . Its margin is , attained by four points, and . The bound is therefore .
| epoch | mistake on | y | score before | w after |
|---|---|---|---|---|
| 1 | (1, 2), (0, 0), (1, 0), (0, 1) | +, −, −, − | 0, 1, 1, 1 | (1, 1, 2) → (0, 1, 2) → (−1, 0, 2) → (−2, 0, 1) |
| 2 | (1, 2), (1, 0), (0, 1) | +, −, − | 0, 0, 1 | (−1, 1, 3) → (−2, 0, 3) → (−3, 0, 2) |
| 3 | (2, 1), (1, 0), (0, 1) | +, −, − | −1, 0, 0 | (−2, 2, 3) → (−3, 1, 3) → (−4, 1, 2) |
| 4 | (2, 1), (1, 0) | +, − | 0, 0 | (−3, 3, 3) → (−4, 2, 3) |
| 5 | none | (−4, 2, 3): scores 4, 3, 6, −4, −2, −1 |
The final line separates the data, but its geometric margin is only , less than half of . The perceptron stops at the first separator it reaches, not the best one. Its angle to is small, . Note also how often the bias moved. caused four of the twelve mistakes, because the boundary keeps sliding back and forth across it.
The dual form, and kernels
Since starts at 0 and only ever adds , it is always a combination of training points. Let count the mistakes made on example :
- how many times example i triggered an update; in the run above α = (2, 2, 0, 1, 4, 3), which sums to the 12 mistakes
- the data enter only through inner products, so they can be replaced by a kernel k(xᵢ, x)
Replacing by a kernel gives the kernel perceptron (Aizerman, Braverman and Rozonoer, 1964). It runs the same algorithm in the kernel's feature space without ever forming the features. On XOR coded as , with , the Gram matrix has 9 on the diagonal and 1 everywhere else. The first epoch makes one mistake per point, giving , and the second epoch is clean. Expanding gives , which is exactly the product feature XOR needs. Novikoff's bound still applies, with and measured in feature space.
When the data are not separable
Without a separating the proof's first inequality has nothing to hold on to, and there is always some misclassified point, so the algorithm never stops. Something rigid survives: the perceptron cycling theorem (Minsky and Papert 1969; Block and Levin 1970) says that on a finite dataset the weights stay inside a bounded region. With integer or rational data they take finitely many values, so the sequence eventually repeats exactly. The weights neither diverge nor converge. They wander, and the you get depends on when you stop.
Freund and Schapire (1999) also bounded the mistakes on non-separable data. For any unit and target margin , let be how far point falls short, and . Then a single pass makes at most mistakes. A few bad points cost a little; they do not make the algorithm useless.
| Variant | What it returns | Why it helps |
|---|---|---|
| Pocket (Gallant 1990) | the best w seen so far, kept "in the pocket" while the plain run continues: originally the one with the longest run of consecutive correct visits; the ratchet version swaps only if the training error is lower (as in the figure) | the output no longer depends on where the cycle happened to stop |
| Voted (Freund & Schapire 1999) | every intermediate w, each with a vote equal to the number of visits it survived | comes with generalization bounds; costs memory proportional to the number of mistakes |
| Averaged | over all visits, a single vector | a cheap approximation of voting; long-lived weights dominate, so noise flips average out |
| Kernel / dual | the counts , predicting with | non-linear boundaries; prediction cost grows with the number of mistaken examples |
1import torch23X = torch.tensor([[1., 2.], [2., 1.], [2., 2.], [0., 0.], [1., 0.], [0., 1.]])4y = torch.tensor([1., 1., 1., -1., -1., -1.])5Xa = torch.cat([torch.ones(len(X), 1), X], 1) # x̃ = (1, x)67def perceptron(Xa, y, epochs=100):8 w, w_sum, T = torch.zeros(Xa.shape[1]), torch.zeros(Xa.shape[1]), 09 pocket, pocket_err, alpha = w.clone(), len(y), torch.zeros(len(y))10 for _ in range(epochs):11 mistakes = 012 for i in range(len(y)):13 if y[i] * (w @ Xa[i]) <= 0:14 w += y[i] * Xa[i]; alpha[i] += 1; mistakes += 115 err = int(((Xa @ w) * y <= 0).sum())16 if err < pocket_err: pocket, pocket_err = w.clone(), err17 w_sum += w; T += 118 if mistakes == 0: break19 return w, pocket, w_sum / T, alpha2021w, pocket, w_avg, alpha = perceptron(Xa, y)22print(w, alpha) # tensor([-4., 2., 3.]) tensor([2., 2., 0., 1., 4., 3.])23print(w_avg) # tensor([-2.3333, 1.4000, 2.6333])2425# dual form with the kernel k(x, z) = (1 + x·z)^2 on XOR coded as ±126Xx = torch.tensor([[-1., -1.], [-1., 1.], [1., -1.], [1., 1.]]); yx = torch.tensor([-1., 1., 1., -1.])27K = (1 + Xx @ Xx.T) ** 2 # 9 on the diagonal, 1 elsewhere28a = torch.zeros(4)29for _ in range(10):30 for j in range(4):31 if yx[j] * (a * yx) @ K[:, j] <= 0: a[j] += 132print(a, (a * yx) @ K) # tensor([1., 1., 1., 1.]) tensor([-8., 8., 8., -8.])Check yourself
You multiply every input by 10, with the bias coordinate still fixed at 1. What happens to Novikoff's bound on a dataset whose best separator passes through the origin?
Check yourself
Step 2 of the proof uses the inequality 2y·(w·x̃) ≤ 0. Where does it come from?
Remember
- ✓An update adds to the normal vector, raising that point's functional margin by ; it can break other points.
- ✓Novikoff: and force , independent of , and order.
- ✓It stops at the first separator, not the max-margin one: 12 mistakes, margin 0.186 vs the optimal 0.408 in the worked example.
- ✓Dual form uses only inner products, which gives the kernel perceptron; on ±1 XOR it finds .
- ✓Non-separable data: the weights stay bounded and cycle. Return the pocket or the averaged weights, not the last iterate.