Perceptron Learning Algorithm and Its Proof of Convergence

Start here We don’t want to guess weights by hand. We want the perceptron to look at examples and fix itself whenever it makes a mistake. The Perceptron Learning Algorithm (PLA) does exactly that, using a simple rule: add the point if you wrongly said 0, subtract it if you wrongly said 1.

Lecture example — movie data We have m movies. For each movie we know whether the user liked it (1) or not (0). Each movie is described by n features, some 0/1 and some real: $x_{1} =$ isActorDamon, $x_{2} =$ isGenreThriller, $x_{3} =$ isDirectorNolan, $x_{4} =$ imdbRating (scaled $0-1$), …, x_{n} = criticsRating (scaled 0–1). We assume the data is linearly separable and want the perceptron to find the separating plane, i.e. find $w_{0}, w_{1}, \ldots , w_{n}$.

This is called binary classification: put each input into one of 2 classes.

P ← inputs with label 1
N ← inputs with label 0
Initialise w randomly
while not converged:
    pick a random x from P ∪ N
    if x ∈ P and wᵀx < 0:    w = w + x
    if x ∈ N and wᵀx ≥ 0:    w = w − x
# converged = every input is classified correctly

Here $w^{T}x = w_{0}x_{0} + w_{1}x_{1} + \ldots + w_{n}x_{n}$ (the dot product), with $x_{0} = 1$.

In words:

A little vector geometry. Write $w = [w_{0}, w_{1}, \ldots , w_{n}]$ and $x = [1, x_{1}, \ldots , x_{n}]$.

The rule is now: $y = 1$ if $w^{T}x \ge 0$, else 0.

The boundary is the line $w^{T}x = 0$. For any point x on this line, $\cos \alpha = w^{T}x / (\Vert w\Vert \Vert x\Vert ) = 0$, so the angle α between w and x is 90°. Since w is at 90° to every point on the line, w is perpendicular to the line itself.

• Points with $w^{T}x > 0$ (positive side): angle with w is less than 90°.
• Points with $w^{T}x < 0$ (negative side): angle with w is more than 90°.

Case $1: x \in P$ but $w^{T}x < 0$ (angle $> 90{}^\circ$, we want $< 90{}^\circ$). New weight $w_{\mathrm{new}} = w + x$:

$\cos (\alpha _{\mathrm{new}})$ ∝ $(w + x)^{T}x = w^{T}x + x^{T}x$

$x^{T}x = \Vert x\Vert ^{2}$ is always positive, so $\cos (\alpha _{\mathrm{new}}) > \cos (\alpha )$. A bigger cosine means a smaller angle. w turns towards x. ✔

Case $2: x \in N$ but $w^{T}x \ge 0$ (angle $< 90{}^\circ$, we want $> 90{}^\circ$). New weight $w_{\mathrm{new}} = w - x$:

$\cos (\alpha _{\mathrm{new}})$ ∝ $(w - x)^{T}x = w^{T}x - x^{T}x$

$So \cos (\alpha _{\mathrm{new}}) < \cos (\alpha ) \to$ bigger angle. w turns away from x. ✔

(Small note: the slides write “∝ $\cos \alpha + x^{T}x$”. Strictly, it is $w^{T}x$ that grows by $x^{T}x$; the cosine also has $\Vert w_{\mathrm{new}}\Vert$ in the denominator. The direction of the change is what matters, and the idea is right.)

Start with $w = [0, 0, 0]$, go through the points in the order (0,0), (0,1), (1,0), (1,1), again and again. Each x is written as $[1, x_{1}, x_{2}]$.

Final: $w_{0} = -1, w_{1} = 1, w_{2} = 1$, i.e. fire when $x_{1} + x_{2} \ge 1$ — exactly OR. Only 5 corrections were needed.

Lecture example — the toy run In the lecture’s animation, w starts pointing the wrong way (all positive points at more than 90°). Picking $p_{1}, p_{2}$ gives $w + x$ corrections; $n_{1}$ gives $a w - x$ correction; $n_{3}$ and $n_{2}$ need nothing; $p_{3}$ gives one more $w + x$. After that, a full pass over all points makes no change → the algorithm has converged.

Definition — absolutely linearly separable: sets P and N in n dimensions are absolutely linearly separable if there are $n + 1$ numbers $w_{0}, \ldots , w_{n}$ such that every point in P has $\sum _{i=1}^{n} w_{i}x_{i}$ $>$ $w_{0}$ and every point in N has $\sum _{i=1}^{n} w_{i}x_{i} < w_{0}$.

Proposition: if P and N are finite and linearly separable, the PLA updates w only a finite number of times. (Test the points one after another in cycles; after finitely many steps, w separates the two sets.)

Setup tricks:

1. $If x \in N$, then −x behaves like a positive point ($w^{T}x < 0$ ⇔ $w^{T}(-x) > 0$). So make one set $P' = P ∪ N^{-}$ ($N^{-} =$ negated points of N). Now we only need $w^{T}p \ge 0$ for every $p \in P'$, and only one “if” in the algorithm.
2. Normalise every p so that $\Vert p\Vert = 1$. This does not change the answer (if $w^{T}(p/\Vert p\Vert ) \ge 0$ then $w^{T}p \ge 0$).
3. Let w* be a normalised solution. It exists because the data is separable — we just don’t know it.

Proof idea. $Let \beta$ be the angle between w* and the current w. Suppose by step t we have made k corrections $(k \le t)$. Look at

$\cos \beta = (w* \cdot w_{t+1}) / \Vert w_{t+1}\Vert (\Vert w*\Vert = 1)$

Numerator grows at least linearly. At a correction, $w_{t+1} = w_t + p_{i}$, so $w* \cdot w_{t+1} = w* \cdot w_t + w* \cdot p_{i} \ge w* \cdot w_t + \delta$, where $\delta = \min$ over i of $(w* \cdot p_{i}) > 0$. Repeating for every correction: numerator $\ge w* \cdot w_{0} + k\delta$.

Denominator grows slowly. $\Vert w_{t+1}\Vert ^{2} = \Vert w_t\Vert ^{2} + 2 w_t \cdot p_{i} + \Vert p_{i}\Vert ^{2} \le \Vert w_t\Vert ^{2} + 1$ (because we only correct when $w_t \cdot p_{i} \le 0$, and $\Vert p_{i}\Vert ^{2} = 1$). Repeating: $\Vert w_{t+1}\Vert ^{2} \le \Vert w_{0}\Vert ^{2} + k$.

Put together:

$\cos \beta \ge (w* \cdot w_{0} + k\delta ) / \sqrt{\Vert w_{0}\Vert ^{2} + k}$

The top grows like k, the bottom only like $\sqrt{k}$. So the right side grows like $\sqrt{k}$ and would become bigger than 1 for large k. But $\cos \beta \le 1$ always. So k cannot keep growing — there is a maximum number of corrections, and the algorithm converges.

(The slide writes the denominator as $\Vert w_{0}\Vert ^{2} + k$; it should be under a square root, since the denominator of $\cos \beta$ is ‖w‖, not $\Vert w\Vert ^{2}$. The conclusion is the same.)

In one line: PLA adds misclassified positive points to w and subtracts misclassified negative points; for linearly separable data it is guaranteed to stop after a finite number of corrections.

Exam words: binary classifier, Perceptron Learning Algorithm, convergence, dot product $w^{T}x$, angle between vectors, normalisation, absolutely linearly separable, $P' = P$ ∪ $N^{-}, \delta$, finite number of updates.