The perceptron

Move the line only when it is wrong. Below, a line learns from twelve dots, then meets four more. Before it plays: will the line always stop moving?

The rule

The perceptron is the line rule of What machine learning is, now with its name. A point $\mathbf{x}$ gets the score $\mathbf{w}^\top\mathbf{x}+b$, and the prediction is its sign:

$+1$ for class A and $-1$ for class B. Here the labels are signs too: $y=+1$ for class A and $y=-1$ for class B. That makes a mistake easy to write. The prediction is right when the score has the sign of the label, so a dot is a mistake when

which counts a dot exactly on the line as a mistake too.

After a mistake on the dot $\mathbf{x}$ with label $y$, the update is

For a class A dot, add it; for a class B dot, subtract it. Why does that help? The dot’s new score is its old score plus $y\big(\lVert\mathbf{x}\rVert^2+1\big)$, so $y$ times its score rises by $\lVert\mathbf{x}\rVert^2+1$, which is always positive. The line turns and shifts towards being right about that dot. It may not get there in one update, and it may now be wrong about another dot; it moves only when it is wrong, and never otherwise.

When it stops

Now the answer to the question, the first half. When some line puts every dot on its own side, the data are separable, and then the perceptron always stops: after finitely many mistakes a whole pass makes none. How many at most depends on two sizes.

• The margin $\gamma$: take a line that separates the dots, scaled so that $\mathbf{w}$ and $b$ together, as one vector, have length 1. Every dot’s $y$ times its score is then positive, and $\gamma$ is the smallest of them. A wide gap between the classes means a large margin.
• The radius $R$: append a 1 to each dot, as with the bias term in Linear regression with many features, and take the largest length of these vectors.

Then, starting from all zeros, the number of mistakes is at most

whatever the order of the dots. Each mistake pushes the weights at least $\gamma$ further along the separating line’s direction, while their length grows more slowly, and the two can only go on together for so many mistakes. A narrow gap, as in the clip, means a small $\gamma$ and possibly many mistakes.

The line the perceptron stops on is any line that separates the dots, not the best one. It depends on the start and on the order of the dots, and it often ends close to some of them.

Worked example

Four dots: class A at $P_1=(1,3)$ and $P_2=(2,3)$, class B at $P_3=(2,1)$ and $P_4=(3,1)$. Start from $\mathbf{w}=(0,0)$ and $b=0$, and visit $P_1$, $P_2$, $P_3$, $P_4$ in that order on every pass. Each row is one correction.

In pass 5 the scores are 10, 6, −4 and −8: both class A dots positive, both class B dots negative. The run stops after seven corrections, on the line $-4x_1+5x_2-1=0$, that is $x_2=(4x_1+1)/5$.

Four of the seven corrections were for $P_3$. One update did not fix it: its first correction left it on the line (score 0), and later updates for $P_1$ and $P_2$ put it back on or across the line.

The bound. The line $x_2=2$ separates the dots: as one vector, its weights and bias term are $(0,1,-2)$, of length $\sqrt5$, and every dot’s $y$ times its score is 1. Scaled to length 1, the margin is $\gamma=1/\sqrt5=0.447$. With a 1 appended, the farthest dot is $P_2$, $(2,3,1)$, of length $\sqrt{14}=3.742$. The bound is $(R/\gamma)^2=14\times5=70$ mistakes, far above the seven used: it is a guarantee, not a forecast.

Another order. Visit the same dots as $P_4$, $P_3$, $P_2$, $P_1$, from the same start. The run again needs seven corrections, in passes 1 to 4, but it stops on $\mathbf{w}=(-5,5)$, $b=-1$, the line $x_2=x_1+0.2$: a different separating line.

A quick check. With $\mathbf{w}=(1,0)$ and $b=0$, the class A dot $(-1,2)$ scores $-1$: a mistake. The update gives $\mathbf{w}=(0,2)$ and $b=1$.

When it never stops

Now the second half of the answer. Four dots at the corners of a square, class B at $(0,0)$ and $(1,1)$, class A at $(0,1)$ and $(1,0)$: the pattern called XOR, class A when exactly one coordinate is 1. (The clip uses the corners $\pm1$; it is the same pattern.) No line separates them. Suppose one did, even allowing the class B dots to sit on the line. Then:

• the class B dots need $b\le0$ and $w_1+w_2+b\le0$, which add to $w_1+w_2+2b\le0$;
• the class A dots need $w_2+b>0$ and $w_1+b>0$, which add to $w_1+w_2+2b>0$.

Both cannot hold, so no line works. The data are not separable, and the perceptron makes at least one mistake in every pass for ever: more passes never help.

The way out is to combine several lines. Neurons and activation functions builds a network from units like this one, and Multilayer networks separates XOR with two layers. Logistic regression is a soft version of the same line, with a chance in place of a sign.

Where you’ll meet this

Learning as data arrive. The perceptron needs one example at a time and a single update, so it suits classifiers that learn from a stream: sorting messages or tagging text as they come in.

Neural networks. A perceptron is one unit of a network: a weighted sum, then a threshold. Networks replace the hard threshold with a smooth one, so they can be fitted by gradient descent.

An early learning machine. It was one of the first machines that learned from examples, built in hardware in the late 1950s, with adjustable weights set by this rule.

Reference card