A rule needs a tie convention
Consider a finite nonempty collection of labeled vectors , where , , and . Start with . When an example is presented, compute its signed score . If the score is at most zero, update
otherwise leave unchanged. In particular a zero score triggers an update. We count updates, including zero-score ties; depending on a classifier's separate tie-breaking convention, not all of them need be strict classification mistakes.
This is the homogeneous rule: its decision boundary passes through the origin. For an affine score , append a constant coordinate to form and ; then apply the same rule to the augmented vectors. Radius and margin must be calculated in the augmented space, not with the original feature norm alone.
Common mistake
(Looking for the margin in the original coordinates)
Take the one-dimensional data with label and with label . For a homogeneous score , the point has signed score for every , so no positive margin exists in the original coordinate. After augmenting to and , the unit vector gives signed margins and . The margin assumption must be checked in the space where the rule is actually run.
Two estimates on the same updates
Theorem 5.1.1
(Finite-update bound for the perceptron)
Assume there are constants , and a unit vector such that for every example
Start from and update on every presentation with signed score at most zero. Then, for any presentation order, the total number of updates satisfies
If the finite dataset is presented in repeated complete passes, a pass with no update occurs after at most passes, and then every training example has strictly positive signed score.
For finite data a finite always exists; the substantive assumption is the strictly positive margin for the data actually used by the algorithm.
Proof
(Linear progress against square-root growth)
Let be the weight immediately after the th update, with ; ignored presentations do not increment . At an update on ,
By induction . On the other hand, the update condition gives , so
Thus . Cauchy–Schwarz and yield . For , division gives .
For the statement about passes: the updates number at most , and every pass before the last contains at least one update, so at most passes are needed. In a pass with no update the weight stays fixed, so every example had positive signed score for that weight.
Proof X-ray
Where the tie convention and the zero start are used
The two estimates need different features of the rule. The lower bound needs only the margin assumption, applied once per update. The upper bound needs the update condition , and the word "at most" matters: with the first score is exactly zero, so a rule that updated only on strictly negative scores would never move away from the origin. The start makes both bounds begin at zero, so they can be compared. The proof closes because a quantity growing linearly in is squeezed under one growing like . The bound counts total updates, not passes or computation time, and it says nothing about performance on new data.
If a separator is not normalized but satisfies , use and . The resulting bound is . A small margin makes this guarantee weak; the bound need not be attained.
Worked examples
Worked example 5.1.2
(A two-dimensional trace)
Use the ordered homogeneous examples
With , the first score is zero, so becomes . The second score is also zero, so the negative label updates to . The third signed score is , so no update occurs. A further pass has positive signed scores and makes no update.
For , the signed margins are , and . The largest input norm is , so gives an upper bound of updates. The trace used updates; the theorem is an upper bound, not an exact prediction.
Worked example 5.1.3
(An unnormalized separator)
Take the examples and and the separator . The signed scores are and , so . Also and , so the bound is , that is, at most updates. The run: gives score on the first example, so . The second example has score , so . In the next pass the scores are and , so there is no further update. The actual count is .
Worked example 5.1.4
(Augmenting for a bias)
Take the one-dimensional points with label and with label , with an affine score. Augment to and and present them in this order. From , the first score is , so . The second score is , so . In the next pass the first score is again, so ; then the scores are and and no update remains. Three updates occur. With both signed margins are , and the largest augmented norm is , so the bound is . The original feature radius would omit the constant coordinate.
What can fail without separation
Counterexample mode
Bounded inputs do not force termination
Claim: if all training vectors have norm at most , the perceptron makes only finitely many updates. Take the two examples and , so . From the first score is , so . The second example has signed score , so . The weight has returned to its start, so presenting the two examples again repeats the same two updates forever. No unit vector gives both examples a positive margin, since their signed margins are and . The theorem's margin assumption cannot be omitted, and a finite bound on the training-vector norms alone is insufficient. A degenerate version is the dataset containing only with label : every presentation counts an update while the zero vector leaves unchanged.
Exercises
Quick check
(If a unit separator has margin at least and all input norms are at most , give the theorem's update bound. If the stopping rule requires a complete pass with no update, what pass bound follows?)
Substitute and into the bound.
Solution · Answer
At most updates. If stopping at the first complete no-update pass, at most passes are needed: every earlier pass contains at least one update.
Quick check
(In the two-dimensional trace, calculate the signed scores of all three examples after the second update. Why does the next complete pass make no updates?)
Use .
Solution · Answer
The scores are . All are strictly positive, so the specified nonpositive-score rule makes no updates.
Quick check
(A separator has norm and signed scores at least on every example. If , find a margin for the unit vector and an update bound.)
Divide by its norm.
Solution · Answer
The unit separator has margin at least , hence at most updates.