The perceptron

Four points lie on a flat plane, and each one carries a label. The points (1, 1) and (2, 1) carry +1, while the points (-1, -1) and (-2, -1) carry -1. A single small unit has to decide, for each point in turn, which side of a straight boundary it falls on, and it has to reach that decision with arithmetic alone.

A neural network does one thing to its inputs, and then repeats that operation in layer after layer. It multiplies every input by a weight, adds the products together, and passes the total through a fixed rule that never changes [S:67:36]. Everything else in this chapter is a consequence of that single operation, applied many times and adjusted from data. For one unit the fixed rule is a threshold, so the only shape it can draw is a straight line. !Four labelled points and the single boundary a unit with weights 1 and 1 and bias 0 can draw. The weighted sums are 2, 3, −2 and −3, so the sign of the sum answers every row, and the line is exactly the set of inputs where that sum is zero. The arrow is the weight vector, normal to the line, which is why changing the weights turns the boundary while changing the bias slides it. Status: re-simulated.

The unit itself holds two weights, one for each coordinate. Multiply each coordinate by its weight, add the two products, and compare the result with a threshold. The unit answers +1 above the threshold and -1 below it. This unit is a perceptron, and the rule it implements is called a linear threshold function. With weights of 1 and 1 and a threshold of 0, the four points score 2, 3, -2 and -3, so the answers run +1, +1, -1 and -1. !One pass of the training rule, drawn before and after. At weights (0, 0) every row scores zero and the tie rule answers −1, so the two rows labelled +1 are misread and the update adds the first of them to the weights, giving (1, 1). The arrow is the correction itself, and its length is the length of the point, which is why a rescaled copy of the same four rows produces a different sequence of updates. Status: re-simulated.

$$\hat{y}=+1\text{ if }w\cdot x+b>0,\hat{y}=-1\text{ otherwise}$$

That formula says the answer depends only on the sign of a weighted sum, so the decision boundary is exactly the collection of inputs where the sum is zero. The weights rotate that boundary, and the bias translates it across the plane without rotating it [S:47:45]. The tie at zero is a separate convention, and any fixed choice produces the same theorem, so this chapter sends the tie to -1 throughout.

A convenient picture is a committee of one question: each coordinate calls out a number, the calls are weighted before they count, and the chair answers yes whenever the weighted total passes a fixed mark. The picture breaks where it matters, because real committee members revise their opinions and these weights stay fixed until a training rule touches them.

Training replaces the chosen weights with a repeating procedure. Begin with every weight at zero, and present the examples one at a time. Whenever an example scores with an incorrect sign, or scores exactly zero, add the point times its label to the weight vector and leave every other example alone: w becomes w + yx, and the bias becomes b + y [S:47:43]. On the four points above, the first point scores zero, so its label +1 adds it and the weights become (1,1). The remaining three points then score 3, -2 and -3 with the correct sign, so the pass terminates after a single update.

That correction has a name and a justification, because it moves the boundary toward the point that was misread by an amount proportional to that point. A useful consequence follows: the correction increases the signed margin y(w·x+b) of the offending example by the squared length of the example. With a bias the margin rises by ||x||^2+1, because the bias is one more coordinate fixed at 1 and the augmented example is (x,1). The raw score w·x+b moves the other way when the example is negative.

The adjustment is the squared length, but the score is also proportional to the input scale. A uniform rescaling of a bias-free unit's inputs therefore multiplies every score by the square of the factor and every update by the factor itself. The sequence of updates does not change. What breaks that invariance is rescaling coordinates relative to each other, or relative to the bias coordinate fixed at 1, which is why feature normalisation matters for a unit with a bias.

Worked example. Three additional examples demonstrate what the bias provides. Take (2, 2) and (3, 1) labelled +1, together with (1, 1) labelled -1. With weights of 1 and 1 the scores are 4, 4 and 2, all positive, so a threshold of zero puts every example on the +1 side.

Raise the threshold to 3, which sets the bias to -3, and the answers become +1, +1 and -1, correct on every row. The threshold is the negative of the bias: the unit answers +1 when the weighted sum plus the bias is positive, so a bar at 3 is a bias of -3. The bias lets the boundary miss the origin.

Without it the boundary passes through the origin, so a unit fails exactly on tables that no line through the origin separates. The pair (1, 1) and (-1, -1), both labelled +1, is the simplest, since any line through the origin puts them on opposite sides. Sitting on one side of the origin is neither necessary nor sufficient for that failure.

That single line is the limitation, and it has two edges. When no line separates the labels, the training passes never terminate, because the training error never reaches zero [S:58:214]. When a separating line does exist, the number of updates still depends on the order of presentation, so two readers who run the same procedure on the same table can obtain different totals [S:47:45]. A reasonable guess is that the error falls at every step, and that guess is wrong as well, since a correction for one example can push a correctly classified example across the boundary [S:58:213-214]. None of these facts is an accident of the code, because each one follows from the geometry of a straight boundary.

The formal statement. Take examples $(x_t,y_t)$ with $x_t$ in ${\mathbb{R}}^d$ and $y_t$ in $\{-1,+1\}$. The unit keeps a weight vector $w$ and a bias $b$, and answers $\hat{y}=+1$ when $w\cdot x+b>0$ and $-1$ otherwise, with the tie sent to $-1$ as in the Core. Training is online: you present one example at a time and, when $y_t(w\cdot x_t+b)\le 0$, you replace $w$ by $w+y_t{x}_t$ and $b$ by $b+y_t$ [S:58:214].

The convergence guarantee needs three hypotheses. Every input has length at most $r$. Some fixed vector $v$ separates the data with margin $\rho >0$, meaning $y_t(v\cdot x_t)\ge \rho \Vert v\Vert$ for every $t$. The run starts at $w=0$. Under those conditions the number of updates is at most $r^2/{\rho }^2$ [S:75:209].

The derivation. Count only the steps that update. After $k$ updates, the squared length of $w$ is at most $k{r}^2$. Each update adds $\Vert x_t{\Vert }^2$ and twice the old score, and the old score is not positive, because the example was misclassified [S:79:120]. The projection onto $v$ grows by at least $\rho \Vert v\Vert$ at every update, so $v\cdot w\ge k\rho \Vert v\Vert$. Cauchy–Schwarz bounds that projection by $\Vert v\Vert \Vert w\Vert$, which is at most $\Vert v\Vert \sqrt{k{r}^2}$. Cancelling $\Vert v\Vert$ leaves $k\rho \le \sqrt{k{r}^2}$, and squaring gives $k\le r^2/{\rho }^2$. Nothing is omitted here; the proof is four lines of algebra.

The edge case. The Core says a correction raises the signed margin of the offending example by the squared length of the example. That holds for the weight vector alone. Carry a bias and the margin rises by $\Vert x_t{\Vert }^2+1$, because the bias enters as one more coordinate fixed at 1. The raw score $w\cdot x_t+b$ moves the other way when the example is negative. The convergence bound changes with it: the radius $r$ must bound the augmented input, not the raw one. The tie is a separate matter: the update tests the signed score, not the predicted label, so $y_t(w\cdot x_t+b)\le 0$ triggers on a zero score for either label. The convention changes only the answer printed at exactly zero, and both choices give the same mistake bound.

What the Core hid. The theorem counts mistakes on the sequence you present, and it says nothing about examples you never show. It also does not claim that training error falls. The perceptron criterion assigns zero cost to a correct example and a linear cost to a wrong one, and it is not the count of errors [S:58:213]. A single update can push a correctly classified example across the boundary [S:58:213-214]. Finally, a separable set can admit many separating vectors, and which one you reach depends on the starting point and on the order of presentation [S:58:214].

Where the analogy breaks. The committee picture suggests independent voters who each hold an opinion. In the arithmetic there is one hyperplane, and its normal is the whole weight vector. Adding a point rotates that plane about the origin rather than adding a vote, and a tie sends the answer to a fixed side instead of abstaining.

Original sources. The unit and its training rule come from Rosenblatt's perceptron, and Bishop and Bishop record the 1962 book [S:67:37]. Bishop's chapter states the rule as stochastic descent on the perceptron criterion and lists the convergence proofs: Rosenblatt, Block, Nilsson, Minsky and Papert, Hertz and coauthors [S:58:214]. Mohri and coauthors give the margin statement used in the Deepen layer, and they show that the update is the stochastic subgradient method applied to a convex and non-differentiable objective [S:75:208] [S:75:209].

An open question. The bound is only as good as the margin, and the margin can be thin. The number of updates grows with the square of the smallest norm that separates the data with unit margin, and that norm can be exponentially large in the number of features [S:79:122]. When no separating vector exists, finding the best halfspace is computationally hard [S:79:119]. The field has not settled which conditions on a data distribution make one of those two situations avoidable. Evidence that would settle a case: an algorithm with a proved polynomial bound for a named distribution family, together with a matching lower bound for the same family.

A frontier result. The voted and averaged perceptron keep every weight vector the run visits, each weighted by how long it survived. The voted version is guaranteed to generalize better than the plain perceptron [S:47:52]. The averaged perceptron is the practical approximation: it predicts with the survival-weighted average of the same vectors, and the source presents it as a cheaper substitute rather than as a second guaranteed improvement [S:47:52]. The method depends on this section twice over. The vectors are the ones the update rule produces, and the averaging is over the order of presentation that the Core warns about.

What to read next. Read Bishop 4.1.7 for the criterion and the history [S:58:213] [S:58:214]. Read Mohri's chapter on linear classification for the margin proof written as a telescoping sum [S:75:208] [S:75:209]. Read Shalev-Shwartz and Ben-David 9.1 for the linear-programming view of the same problem, which shows what you give up by insisting on the iterative rule [S:79:119] [S:79:122]. Then read Daume 4.5 for the averaging trick and its cost [S:47:52].