# 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.

Source: https://www.mlfoundry.in/learn/perceptron-learning-algorithm  
Section: Deep Learning › Neural Network Algorithms  
Level: advanced · 10 min read · updated 2026-10-11

**The perceptron learning algorithm:** is the online procedure that visits labelled examples $(x_i,y_i)$, $y_i\in\{-1,+1\}$, one at a time and, whenever $y_i\,w\cdot\tilde x_i\le0$, updates $w\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, $\tilde x=(1,x)$ folds the bias into $w=(b,w_1,\dots,w_d)$, and $w$ starts at $0$ with $\eta=1$. From a zero start, $\eta$ only rescales $w$ and changes no prediction.

## The geometry of one update

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

$$
y\,(w+y\tilde x)\cdot\tilde x \;=\; y\,w\cdot\tilde x+\lVert\tilde x\rVert^2
$$

- $y\,w\cdot\tilde x$: functional margin of the point before the update (≤ 0 on a mistake)
- $\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 $u$ ($\lVert u\rVert=1$) satisfies $y_i\,u\cdot\tilde x_i\ge\gamma>0$ for every $i$. Let $R=\max_i\lVert\tilde x_i\rVert$. Novikoff (1962) proved:

$$
\#\text{mistakes}\;\le\;\left(\frac{R}{\gamma}\right)^{2}\qquad\text{for any order of presentation, any number of epochs}
$$

- $R$: radius of the augmented data, $\max_i\lVert(1,x_i)\rVert$
- $\gamma$: margin of a unit-norm separator $u$; the bound is tightest for the max-margin $u$, but any separating $u$ gives a valid bound

**Proof sketch: two inequalities that cannot both keep holding**

1. **Alignment grows linearly.** On the $k$-th mistake, $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 $w_0=0$: $w_k\cdot u\ge k\gamma$.
2. **Length grows only like $\sqrt k$.** $\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 $\le0$ *because the update happened on a mistake*, so $\lVert w_k\rVert^2\le\lVert w_{k-1}\rVert^2+R^2$, giving $\lVert w_k\rVert\le\sqrt k\,R$.
3. **Squeeze.** Cauchy–Schwarz with $\lVert u\rVert=1$: $k\gamma\le w_k\cdot u\le\lVert w_k\rVert\le\sqrt k\,R$. Hence $\sqrt k\le R/\gamma$, i.e. $k\le R^2/\gamma^2$.

The geometric reading is an angle. $\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 $n$ nor the dimension $d$, only on the ratio of data radius to margin. That dimension-free property is what kernel methods later exploited.

> Figure: 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,2),(2,1),(2,2)$ and $-1$: $(0,0),(1,0),(0,1)$, visited in that order. The max-margin unit separator in augmented space is $u^\*=(-2,1,1)/\sqrt6$, i.e. the line $x_1+x_2=2$. Its margin is $\gamma^\*=1/\sqrt6=0.4082$, attained by four points, and $R^2=\lVert(1,2,2)\rVert^2=9$. The bound is therefore $(R/\gamma^\*)^2=9\cdot6=54$.

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.

| 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 $2x_1+3x_2=4$ separates the data, but its geometric margin is only $\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^\*$ is small, $\cos=0.986$. Note also how often the bias moved. $(1,0)$ caused four of the twelve mistakes, because the boundary keeps sliding back and forth across it.

## The dual form, and kernels

Since $w$ starts at 0 and only ever adds $y_i\tilde x_i$, it is always a combination of training points. Let $\alpha_i$ count the mistakes made on example $i$:

$$
w=\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
$$

- $\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 $\langle\tilde x_i,\tilde x\rangle$ by a kernel $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 $\pm1$, with $k(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 $\alpha=(1,1,1,1)$, and the second epoch is clean. Expanding $f$ gives $f(x)=-8\,x_1x_2$, which is exactly the product feature XOR needs. Novikoff's bound still applies, with $R$ and $\gamma$ measured in feature space.

## When the data are not separable

Without a separating $u$ 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 $w$ you get depends on when you stop.

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

Repairs for the cases the plain algorithm handles badly

| 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** | $\bar w=\frac1T\sum_t w_t$ over all $T$ visits, a single vector | a cheap approximation of voting; long-lived weights dominate, so noise flips average out |
| **Kernel / dual** | the counts $\alpha_i$, predicting with $\sum_i\alpha_iy_ik(x_i,x)$ | non-linear boundaries; prediction cost grows with the number of mistaken examples |

> **Averaging trades training consistency for stability:** On the six-point example the average of the 30 visited weight vectors is $\bar w=(-2.33,1.40,2.63)$. It still remembers the poor early weights and misclassifies $(0,1)$ (score $+0.30$), although the final $w$ is perfect. On long noisy runs the effect reverses: the averaged weights are dominated by the vectors that survived longest, and they generalize much better than the last iterate. This is why averaged perceptrons were a standard baseline for tagging and parsing (Collins 2002).

> **The margin lives in augmented space:** Novikoff's $R$ and $\gamma$ are measured for $\tilde x=(1,x)$. Data far from the origin make $R$ large, and the separator must tilt a lot in the bias direction, which makes $\gamma$ small, so the bound and the actual mistake count both blow up. Centre and scale the inputs before training. The bias only moves by $\pm1$ per update, while the other weights move by whole feature values.

```python
import torch

X = torch.tensor([[1., 2.], [2., 1.], [2., 2.], [0., 0.], [1., 0.], [0., 1.]])
y = torch.tensor([1., 1., 1., -1., -1., -1.])
Xa = torch.cat([torch.ones(len(X), 1), X], 1)            # x̃ = (1, x)

def perceptron(Xa, y, epochs=100):
    w, w_sum, T = torch.zeros(Xa.shape[1]), torch.zeros(Xa.shape[1]), 0
    pocket, pocket_err, alpha = w.clone(), len(y), torch.zeros(len(y))
    for _ in range(epochs):
        mistakes = 0
        for i in range(len(y)):
            if y[i] * (w @ Xa[i]) <= 0:
                w += y[i] * Xa[i]; alpha[i] += 1; mistakes += 1
                err = int(((Xa @ w) * y <= 0).sum())
                if err < pocket_err: pocket, pocket_err = w.clone(), err
            w_sum += w; T += 1
        if mistakes == 0: break
    return w, pocket, w_sum / T, alpha

w, pocket, w_avg, alpha = perceptron(Xa, y)
print(w, alpha)        # tensor([-4., 2., 3.])  tensor([2., 2., 0., 1., 4., 3.])
print(w_avg)           # tensor([-2.3333, 1.4000, 2.6333])

# dual form with the kernel k(x, z) = (1 + x·z)^2 on XOR coded as ±1
Xx = torch.tensor([[-1., -1.], [-1., 1.], [1., -1.], [1., 1.]]); yx = torch.tensor([-1., 1., 1., -1.])
K = (1 + Xx @ Xx.T) ** 2                                  # 9 on the diagonal, 1 elsewhere
a = torch.zeros(4)
for _ in range(10):
    for j in range(4):
        if yx[j] * (a * yx) @ K[:, j] <= 0: a[j] += 1
print(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

**Question:** You multiply every input by 10, with the bias coordinate still fixed at 1. What happens to Novikoff's bound $(R/\gamma)^2$ on a dataset whose best separator passes through the origin?

- A. It is unchanged: R and γ both grow by about 10×
- B. It grows 100×
- C. It shrinks 100×
- D. It becomes infinite

**Answer:** A. It is unchanged: R and γ both grow by about 10× — If the max-margin separator has zero bias, $u=(0,v)$ and $\gamma$ scales with the inputs, so it grows 10×. $R=\max\lVert(1,x)\rVert$ also grows by almost exactly 10×. The ratio, and the bound, stay essentially the same. This is the dimension-free, scale-free character of the theorem. Shifting the data away from the origin, by contrast, does hurt.

**Question:** Step 2 of the proof uses the inequality 2y·(w·x̃) ≤ 0. Where does it come from?

- A. From the margin assumption on u
- B. From the fact that updates happen only on mistakes, where y·(w·x̃) ≤ 0
- C. From Cauchy–Schwarz
- D. From choosing η = 1

**Answer:** B. From the fact that updates happen only on mistakes, where y·(w·x̃) ≤ 0 — The algorithm only updates when the current $w$ gets the point wrong, i.e. $y\,w\cdot\tilde x\le0$. That is why $\lVert w\rVert^2$ grows by at most $R^2$ per update. An algorithm that also updated on correct points would lose this inequality, and the bound with it.

**Key points**

- An update adds $y\tilde x$ to the normal vector, raising that point's functional margin by $\lVert\tilde x\rVert^2$; it can break other points.
- Novikoff: $w\cdot u\ge k\gamma$ and $\lVert w\rVert\le\sqrt k R$ force $k\le(R/\gamma)^2$, independent of $n$, $d$ 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=\sum\alpha_iy_i\tilde x_i$ uses only inner products, which gives the kernel perceptron; on ±1 XOR it finds $f=-8x_1x_2$.
- Non-separable data: the weights stay bounded and cycle. Return the pocket or the averaged weights, not the last iterate.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
