Perceptron learning algorithm

On separable data the mistake-driven rule w += y·x̃ makes at most (R/γ)² mistakes; on non-separable data it cycles, so use the pocket, averaged or kernel variants.

10 min read1015 wordsadvanced0 viewsupdated 2026-10-11

Definition

The perceptron learning algorithm is the online procedure that visits labelled examples (xi,yi)(x_i,y_i), yi∈{−1,+1}y_i\in\{-1,+1\}, one at a time and, whenever yi w⋅x~i≤0y_i\,w\cdot\tilde x_i\le0, updates w←w+yix~iw\leftarrow w+y_i\tilde x_i. 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, x~=(1,x)\tilde x=(1,x) folds the bias into w=(b,w1,…,wd)w=(b,w_1,\dots,w_d), and ww starts at 00 with η=1\eta=1. From a zero start, η\eta only rescales ww and changes no prediction.

The geometry of one update

Read ww as the normal vector of the decision hyperplane w⋅x~=0w\cdot\tilde x=0: it points into the +1+1 half-space. A mistake on a +1+1 point means xx sits on the wrong side, at an obtuse angle to ww. Adding xx to ww tilts the normal toward xx. A mistake on a −1-1 point subtracts xx, tilting the normal away. In both cases the new normal is the vector sum w+yx~w+y\tilde x, and the hyperplane rotates and shifts toward putting that point on the correct side.

y (w+yx~)⋅x~  =  y w⋅x~+∥x~∥2y\,(w+y\tilde x)\cdot\tilde x \;=\; y\,w\cdot\tilde x+\lVert\tilde x\rVert^2
y w⋅x~y\,w\cdot\tilde x
functional margin of the point before the update (≤ 0 on a mistake)
∥x~∥2\lVert\tilde x\rVert^2
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 γ\gamma: some unit vector uu (∥u∥=1\lVert u\rVert=1) satisfies yi u⋅x~i≥γ>0y_i\,u\cdot\tilde x_i\ge\gamma>0 for every ii. Let R=max⁡i∥x~i∥R=\max_i\lVert\tilde x_i\rVert. Novikoff (1962) proved:

#mistakes  ≤  (Rγ)2for any order of presentation, any number of epochs\#\text{mistakes}\;\le\;\left(\frac{R}{\gamma}\right)^{2}\qquad\text{for any order of presentation, any number of epochs}
RR
radius of the augmented data, max⁡i∥(1,xi)∥\max_i\lVert(1,x_i)\rVert
γ\gamma
margin of a unit-norm separator uu; the bound is tightest for the max-margin uu, but any separating uu gives a valid bound

Proof sketch: two inequalities that cannot both keep holding

  1. 1Alignment grows linearly. On the kk-th mistake, wk⋅u=wk−1⋅u+yi x~i⋅u≥wk−1⋅u+γw_k\cdot u=w_{k-1}\cdot u+y_i\,\tilde x_i\cdot u\ge w_{k-1}\cdot u+\gamma. By induction from w0=0w_0=0: wk⋅u≥kγw_k\cdot u\ge k\gamma.
  2. 2Length grows only like k\sqrt k. ∥wk∥2=∥wk−1∥2+2yi wk−1⋅x~i+∥x~i∥2\lVert w_k\rVert^2=\lVert w_{k-1}\rVert^2+2y_i\,w_{k-1}\cdot\tilde x_i+\lVert\tilde x_i\rVert^2. The middle term is ≤0\le0 because the update happened on a mistake, so ∥wk∥2≤∥wk−1∥2+R2\lVert w_k\rVert^2\le\lVert w_{k-1}\rVert^2+R^2, giving ∥wk∥≤k R\lVert w_k\rVert\le\sqrt k\,R.
  3. 3Squeeze. Cauchy–Schwarz with ∥u∥=1\lVert u\rVert=1: kγ≤wk⋅u≤∥wk∥≤k Rk\gamma\le w_k\cdot u\le\lVert w_k\rVert\le\sqrt k\,R. Hence k≤R/γ\sqrt k\le R/\gamma, i.e. k≤R2/γ2k\le R^2/\gamma^2.

The geometric reading is an angle. cos⁡∠(wk,u)=wk⋅u∥wk∥≥k γR\cos\angle(w_k,u)=\dfrac{w_k\cdot u}{\lVert w_k\rVert}\ge\dfrac{\sqrt k\,\gamma}{R}. 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 nn nor the dimension dd, only on the ratio of data radius to margin. That dimension-free property is what kernel methods later exploited.

gap ≥ 0.1 · R = 1.58 · γ = 0.109- - uw = (b, w₁, w₂) = (0.00, 0.00, 0.00)update 0 of 15 · errors now 40 · bound 209Novikoff's bounds vs update k‖w‖ ≤ √k·R (dashed)w·u ≥ k·γ (dashed)k = 15 →mistakes (bar) vs (R/γ)² (dashed)11e11e21e31e40.020.040.060.080.10.130.160.20.250.3data gap → (click a bar)
fig.Separable mode: 40 seeded points labelled by the dashed line u, with every point closer than the data gap removed. Press update to apply one mistake-driven step. The arrows show old w + y·x = new w, and the top chart traces w·u and ‖w‖ against their bounds k·γ and √k·R. At gap 0.1 (γ = 0.109, R = 1.58) the run makes 15 mistakes against a bound of 209. The bar chart repeats this for every gap: 33 vs 3318 at 0.02, 2 vs 28 at 0.3. Noisy mode flips a share of the labels. The plain perceptron never stops, ‖w‖ stays bounded, and after 60 epochs at 10% noise the last w has 10 training errors while the pocket (mint) has 4 and the averaged w (violet) has 5.

Worked example: six points, twelve mistakes

Take +1+1: (1,2),(2,1),(2,2)(1,2),(2,1),(2,2) and −1-1: (0,0),(1,0),(0,1)(0,0),(1,0),(0,1), visited in that order. The max-margin unit separator in augmented space is u\*=(−2,1,1)/6u^\*=(-2,1,1)/\sqrt6, i.e. the line x1+x2=2x_1+x_2=2. Its margin is γ\*=1/6=0.4082\gamma^\*=1/\sqrt6=0.4082, attained by four points, and R2=∥(1,2,2)∥2=9R^2=\lVert(1,2,2)\rVert^2=9. The bound is therefore (R/γ\*)2=9⋅6=54(R/\gamma^\*)^2=9\cdot6=54.

epochmistake onyscore beforew 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)
5none(−4, 2, 3): scores 4, 3, 6, −4, −2, −1
Every update of the run, w = (b, w₁, w₂). Epoch 5 makes no mistakes, so training stops with 12 mistakes, well under the bound of 54.

The final line 2x1+3x2=42x_1+3x_2=4 separates the data, but its geometric margin is only min⁡iyi w⋅x~i/∥w∥=1/29=0.1857\min_i y_i\,w\cdot\tilde x_i/\lVert w\rVert=1/\sqrt{29}=0.1857, less than half of γ\*\gamma^\*. The perceptron stops at the first separator it reaches, not the best one. Its angle to u\*u^\* is small, cos⁡=0.986\cos=0.986. Note also how often the bias moved. (1,0)(1,0) caused four of the twelve mistakes, because the boundary keeps sliding back and forth across it.

The dual form, and kernels

Since ww starts at 0 and only ever adds yix~iy_i\tilde x_i, it is always a combination of training points. Let αi\alpha_i count the mistakes made on example ii:

w=∑iαi yi x~i,f(x)=∑iαi yi ⟨x~i,x~⟩,mistake on j ⇒ αj←αj+1w=\sum_{i}\alpha_i\,y_i\,\tilde x_i,\qquad f(x)=\sum_i\alpha_i\,y_i\,\langle\tilde x_i,\tilde x\rangle,\qquad \text{mistake on } j\ \Rightarrow\ \alpha_j\leftarrow\alpha_j+1
αi∈N\alpha_i\in\mathbb{N}
how many times example i triggered an update; in the run above α = (2, 2, 0, 1, 4, 3), which sums to the 12 mistakes
⟨⋅,⋅⟩\langle\cdot,\cdot\rangle
the data enter only through inner products, so they can be replaced by a kernel k(xᵢ, x)

Replacing ⟨x~i,x~⟩\langle\tilde x_i,\tilde x\rangle by a kernel k(xi,x)k(x_i,x) 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 ±1\pm1, with k(x,z)=(1+x⋅z)2k(x,z)=(1+x\cdot z)^2, the Gram matrix has 9 on the diagonal and 1 everywhere else. The first epoch makes one mistake per point, giving α=(1,1,1,1)\alpha=(1,1,1,1), and the second epoch is clean. Expanding ff gives f(x)=−8 x1x2f(x)=-8\,x_1x_2, which is exactly the product feature XOR needs. Novikoff's bound still applies, with RR and γ\gamma measured in feature space.

When the data are not separable

Without a separating uu 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 ww you get depends on when you stop.

Freund and Schapire (1999) also bounded the mistakes on non-separable data. For any unit uu and target margin γ\gamma, let di=max⁡(0,γ−yi u⋅x~i)d_i=\max(0,\gamma-y_i\,u\cdot\tilde x_i) be how far point ii falls short, and D=∑idi2D=\sqrt{\textstyle\sum_i d_i^2}. Then a single pass makes at most ((R+D)/γ)2\big((R+D)/\gamma\big)^2 mistakes. A few bad points cost a little; they do not make the algorithm useless.

VariantWhat it returnsWhy 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 survivedcomes with generalization bounds; costs memory proportional to the number of mistakes
Averagedwˉ=1T∑twt\bar w=\frac1T\sum_t w_t over all TT visits, a single vectora cheap approximation of voting; long-lived weights dominate, so noise flips average out
Kernel / dualthe counts αi\alpha_i, predicting with ∑iαiyik(xi,x)\sum_i\alpha_iy_ik(x_i,x)non-linear boundaries; prediction cost grows with the number of mistaken examples
Repairs for the cases the plain algorithm handles badly
python
1import torch
2
3X = 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)
6
7def perceptron(Xa, y, epochs=100):
8 w, w_sum, T = torch.zeros(Xa.shape[1]), torch.zeros(Xa.shape[1]), 0
9 pocket, pocket_err, alpha = w.clone(), len(y), torch.zeros(len(y))
10 for _ in range(epochs):
11 mistakes = 0
12 for i in range(len(y)):
13 if y[i] * (w @ Xa[i]) <= 0:
14 w += y[i] * Xa[i]; alpha[i] += 1; mistakes += 1
15 err = int(((Xa @ w) * y <= 0).sum())
16 if err < pocket_err: pocket, pocket_err = w.clone(), err
17 w_sum += w; T += 1
18 if mistakes == 0: break
19 return w, pocket, w_sum / T, alpha
20
21w, 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])
24
25# dual form with the kernel k(x, z) = (1 + x·z)^2 on XOR coded as ±1
26Xx = 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 elsewhere
28a = torch.zeros(4)
29for _ in range(10):
30 for j in range(4):
31 if yx[j] * (a * yx) @ K[:, j] <= 0: a[j] += 1
32print(a, (a * yx) @ K) # tensor([1., 1., 1., 1.]) tensor([-8., 8., 8., -8.])
Primal run with pocket and averaging, plus the dual (kernel) form on ±1 XOR

Check yourself

You multiply every input by 10, with the bias coordinate still fixed at 1. What happens to Novikoff's bound (R/γ)2(R/\gamma)^2 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 yx~y\tilde x to the normal vector, raising that point's functional margin by ∥x~∥2\lVert\tilde x\rVert^2; it can break other points.
  • ✓Novikoff: w⋅u≥kγw\cdot u\ge k\gamma and ∥w∥≤kR\lVert w\rVert\le\sqrt k R force k≤(R/γ)2k\le(R/\gamma)^2, independent of nn, dd 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 w=∑αiyix~iw=\sum\alpha_iy_i\tilde x_i uses only inner products, which gives the kernel perceptron; on ±1 XOR it finds f=−8x1x2f=-8x_1x_2.
  • ✓Non-separable data: the weights stay bounded and cycle. Return the pocket or the averaged weights, not the last iterate.
← back to Deep Learning roadmap