Why the Update Works: Dot Products and Angles

The update rule was stated without a reason. Let us get one, using a little linear algebra.

The weighted sum is a dot product

With weights $w = (w_0, \dots, w_n)$ and an example $x = (1, x_1, \dots, x_n)$, the weighted sum is the dot product

So the perceptron rule is just: output 1 if $w \cdot x \ge 0$, output 0 if $w \cdot x < 0$.

Angles decide the side

The dot product is also $w \cdot x = \|w\|\,\|x\|\cos\alpha$, where $\alpha$ is the angle between the two vectors. Since lengths are positive, the sign of $w \cdot x$ is the sign of $\cos\alpha$. Therefore:

• $w \cdot x > 0$ means $\alpha < 90^\circ$: the example is on the positive side,
• $w \cdot x < 0$ means $\alpha > 90^\circ$: the example is on the negative side,
• $w \cdot x = 0$ means $\alpha = 90^\circ$: the example lies on the boundary.

The last line says something about the boundary $w \cdot x = 0$: every point on it is perpendicular to $w$. So the weight vector $w$ is orthogonal to the decision boundary, pointing into the positive side.

So learning has a clear target: make every positive example within $90^\circ$ of $w$ and every negative example beyond $90^\circ$.

What the update does

Missed positive ($w \cdot x < 0$, but it should be at least 0). We set $w_{\text{new}} = w + x$. Then

The score for this example rises by $\|x\|^2$, which is always positive. The example has moved toward the correct side. Geometrically, adding $x$ tilts $w$ toward $x$, so the angle between them shrinks.

Accepted negative ($w \cdot x \ge 0$, but it should be negative). We set $w_{\text{new}} = w - x$, so

and the score falls by $\|x\|^2$, pushing the example toward the negative side.

There is a catch. Fixing one example can hurt another that was already correct, since the same $w$ serves them all. Nothing so far says the algorithm cannot go round in circles. The next lesson shows that it cannot, when the data is separable.

A full run on AND

Let us run the algorithm by hand. Write each example with its leading 1, so AND has the points $(1,0,0)$, $(1,0,1)$, $(1,1,0)$ with label 0 and $(1,1,1)$ with label 1. Start from $w = (0, 0, 0)$ and go through the examples in this order every pass. Note that with $w = 0$, every score is $0$, which counts as 1.

Pass 1

Pass 2

Passes 3, 4 and 5 continue the same way. After pass 5 the weights are $w = (-3, 2, 1)$, and pass 6 makes no corrections, so the algorithm has converged. Check it:

All four are right. The boundary $-3 + 2x_1 + x_2 = 0$ is a different line from the textbook one, but it separates the classes just as well. There are many valid answers, and the algorithm stops at the first one it finds.