The perceptron

The perceptron is the simplest classifier with a learning rule[1]: a linear discriminant trained by walking through the data and nudging the weight vector each time it misclassifies. It is a useful first stop because the algorithm is trivial, its convergence proof is short, and the geometric intuition (margin matters) seeds the SVM that comes next.

The classifier

For binary labels $y_i \in \{-1, +1\}$ and features $x_i \in \mathbb{R}^d$ (with a constant 1 appended for an intercept), predict

A point is classified correctly when $y_i\, w^\top x_i > 0$. The decision boundary is the hyperplane $w^\top x = 0$.

The update rule

Start with $w = 0$ and pass through the data. On a mistake (a point with $y_i\, w^\top x_i \le 0$), update

Geometrically: rotate $w$ slightly toward the side of the misclassified point. Repeat until no mistakes occur in a full pass.

Novikoff's convergence theorem

If the data are linearly separable with a margin $\gamma > 0$, the perceptron makes a bounded number of mistakes[2].

Theorem. Assume there is a unit-norm vector $w^\star$ ($\lVert w^\star\rVert = 1$) and $\gamma > 0$ such that $y_i\, w^{\star\top} x_i \ge \gamma$ for all $i$, and that $\lVert x_i\rVert \le R$ for all $i$. Then the perceptron converges after at most $(R/\gamma)^2$ updates.

Proof. Let $w^{(k)}$ be the weight after $k$ updates. Two invariants:

Lower bound on alignment with $w^\star$. Each update with example $(x_i, y_i)$ increases $w^\top w^\star$ by $y_i\, x_i^\top w^\star \ge \gamma$. So $w^{(k)\top} w^\star \ge k\gamma$, and by Cauchy-Schwarz $\lVert w^{(k)}\rVert \ge k\gamma$.

Upper bound on weight norm. The squared norm grows by

using that updates happen only on mistakes ($y_i w^\top x_i \le 0$). So $\lVert w^{(k)}\rVert^2 \le k R^2$, i.e. $\lVert w^{(k)}\rVert \le \sqrt k\, R$.

Combining, $k\gamma \le \lVert w^{(k)}\rVert \le \sqrt k\, R$, so $k \le (R/\gamma)^2$. $\qquad\blacksquare$

The bound depends on the margin $\gamma$, not on the dataset size or dimension. A large margin makes learning fast; a tiny margin makes it slow. This is exactly the geometric quantity the SVM will maximize.

What the perceptron does not do

• It does not give probabilities.
• On nonseparable data it cycles forever (no convergence). Variants like the averaged perceptron or kernel perceptron address this.
• The hyperplane it finds is any separating hyperplane, not the maximum-margin one. The next lesson fixes this by explicitly maximizing the margin.

Check it on arrays

import numpy as np

rng = np.random.default_rng(0)

# Linearly separable dataset
n_per = 100
X_pos = rng.normal(loc=[2.5, 1.0], size=(n_per, 2))
X_neg = rng.normal(loc=[-1.5, -1.0], size=(n_per, 2))
X = np.vstack([X_pos, X_neg])
X = np.column_stack([np.ones(len(X)), X])
y = np.array([1] * n_per + [-1] * n_per)

def perceptron(X, y, max_passes=100):
    w = np.zeros(X.shape[1])
    mistakes = 0
    for _ in range(max_passes):
        any_mistake = False
        for i in range(len(y)):
            if y[i] * (w @ X[i]) <= 0:
                w += y[i] * X[i]
                mistakes += 1
                any_mistake = True
        if not any_mistake:
            return w, mistakes
    return w, mistakes

w, mistakes = perceptron(X, y)
print(f"converged after {mistakes} mistakes")

# Margin and bound: estimate gamma and R, check Novikoff prediction
acc = np.mean(np.sign(X @ w) == y)
print(f"training accuracy: {acc:.3f}")

R = np.max(np.linalg.norm(X, axis=1))
margins = y * (X @ w) / np.linalg.norm(w[1:])         # geometric margins (ignore intercept)
gamma = margins.min()
bound = (R / gamma)**2 if gamma > 0 else float("inf")
print(f"R = {R:.2f}, geometric margin gamma = {gamma:.3f}")
print(f"Novikoff bound (R/gamma)^2 = {bound:.0f}, actual mistakes = {mistakes}")

The perceptron separates the two Gaussian blobs, achieves 100% training accuracy, and the actual mistake count sits below the Novikoff bound.

Exercises

Exercise 1. Two one-dimensional points are given: $x_+ = 1$ with $y_+ = +1$ and $x_- = -1$ with $y_- = -1$. Using $w^\star = 1$ (unit norm in 1D), compute the margin $\gamma$ and radius $R$, then the Novikoff bound on the number of perceptron updates.

Exercise 2. Show that scaling every input by a constant $c > 0$ (so $x_i \mapsto c\, x_i$) leaves the geometric margin $\gamma/R$ unchanged, hence leaves the Novikoff bound unchanged.

Exercise 3 (code). The XOR labels are not linearly separable. Run the perceptron on the four XOR points for up to 1000 passes and confirm it never completes a mistake-free pass (it cycles), and that no setting of $w$ it reaches classifies all four correctly.

import numpy as np

# Bias-augmented XOR: first column is the constant intercept feature
X = np.array([[1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]], float)
y = np.array([-1, 1, 1, -1])           # XOR: differ -> +1, same -> -1

def perceptron(X, y, max_passes):
    w = np.zeros(X.shape[1])
    converged = False
    for _ in range(max_passes):
        any_mistake = False
        for i in range(len(y)):
            if y[i] * (w @ X[i]) <= 0:
                w += y[i] * X[i]
                any_mistake = True
        if not any_mistake:
            converged = True
            break
    return w, converged

w, converged = perceptron(X, y, max_passes=1000)
acc = np.mean(np.sign(X @ w) == y)
print(f"converged: {converged}, accuracy at stop: {acc:.2f}")
assert not converged                    # no mistake-free pass in 1000 tries
assert acc < 1.0                        # the final w cannot separate XOR

The next lesson asks for more: among all separating hyperplanes, which one is the best by a margin argument?