A linear classifier gives a score to a feature vector and uses its sign to choose a class. The perceptron learns that score by reacting to examples whose signed scores are not yet positive. Its convergence argument is geometric: every update makes progress toward a separating direction, while the weight norm cannot grow fast enough to permit infinitely many such updates when a positive margin exists.
The assumptions and the stopping condition matter. A finite run may fail to finish because the data are not linearly separable, but a small training budget alone does not prove that. We will make the bias coordinate explicit, follow an exact training trace, and prove the update bound before discussing what happens outside its hypotheses.
Absorb the bias into one extra coordinate
Let an example be with label . An affine classifier uses score . Define the augmented vector and weight by
Thus the bias is a learned coordinate, not a fixed contribution that can be omitted from the updates. For ordinary prediction, take class at a zero-score tie. During training, however, require strictly positive signed score and update on both errors and zero-score boundaries.
Definition 9.1.1
(Perceptron update and strict separation)
Initialize . When an example has , replace
Otherwise leave unchanged. This is the unit-step perceptron. A weight strictly separates the training set if every training example has .
The update count includes zero-margin examples, even if a prediction tie rule happened to label one correctly. The customary name “mistake bound” below refers to this count of updates including boundaries.
In original coordinates, the rule is and . Positive examples add their augmented vectors; negative examples subtract them.
Common mistake
(Updating only on strictly negative scores)
A tempting simplification is to update only when . Starting from , every score is zero, so no example ever triggers an update: the loop ends at once with and every signed score still equal to zero, which is not a strict separator. For the points (label ) and (label ) this rule returns , whereas the rule with separates them after three updates (see the first worked example below). The boundary case must trigger an update.
An update improves the current margin without necessarily fixing it
For the example causing an update,
The signed score increases because , and augmentation makes nonzero. It can still remain negative. Updates may also change the scores of other examples in either direction, which is why a global convergence proof is needed.
Counterexample mode
One correction need not classify that example correctly yet
Starting from zero, first see a negative one-dimensional example . Its augmented update gives . Next see a positive example , with . Its old signed score is ; the update gives and a new signed score of .
The score improved by , but the point is still incorrectly classified. These two examples are nevertheless separable: score is positive at 1 and negative at 3. The issue is not a contradiction in the data; one unit update simply need not finish the correction.
State the margin assumptions in the augmented space
Definition 9.1.2
(A bounded, uniformly separated training set)
Assume every presented augmented example satisfies . Assume there is one fixed unit vector such that
for every training example. The number is a uniform positive margin for this unit separator.
The radius and normalization of include the bias coordinate. The algorithm need not know , or ; their existence is what supports the analysis.
For finite data with a strict separator, normalizing that separator and taking the minimum of finitely many positive signed scores gives such a . It may be very small, so the resulting numerical bound need not be tight or practical.
Theorem 9.1.3
(Perceptron mistake bound)
Let be augmented training examples with labels . Assume for all and that one unit vector satisfies for all . Run the perceptron update rule on these examples, presented in any order and for any number of passes. Then the number of updates triggered satisfies
Proof
(Linear progress against square-root growth)
Number only the updates. Let be the example that triggers the -th update and the weight after updates.
Progress along : since ,
so because .
Growth of the norm: the update condition gives , hence
so .
Combine the two with Cauchy–Schwarz and :
For , divide by and square to obtain . The case satisfies the bound trivially.
Proof X-ray
Which hypothesis drives which half
The proof is two inequalities pulling in opposite directions. The margin assumption is used only in the lower bound: each update moves by at least along one fixed direction , whichever violating example triggered it. The update condition is used only in the upper bound: it makes the cross term nonpositive, so the squared norm grows by at most per update. Cauchy–Schwarz with links the two, and the argument closes because fails for large . The initial weight starts both bounds at zero, and the bias coordinate enters through and , which must be taken in the augmented space. If the algorithm also updated on examples that already have a positive score, the cross term could be positive and the upper bound would not follow.
The theorem applies to any order of examples sharing these bounds. For a finite training set visited in repeated full passes, an entire pass with no update certifies strict separation: the weights stayed fixed and every example had positive signed score. Each pass that does update consumes at least one of the finitely many permitted updates, so repeated passes eventually reach such a clean pass.
Follow the bias and boundary updates exactly
Worked example 9.1.4
(Two training points need three updates)
Use one-dimensional points with label and with label , always in that order. The augmented vectors are and .
| Pass and example | Weight before | Signed score before | Weight afterwards |
|---|---|---|---|
| Pass 1, negative | |||
| Pass 1, positive | |||
| Pass 2, negative | |||
| Pass 2, positive |
There are three updates. The final signed scores are 1 and 3, so both points are strictly separated; a further pass would make no change.
For the bound, choose . Both examples have signed projection , so . The largest augmented norm is . Thus the proven upper bound is , while the actual count is three.
Using only the original feature radius two would omit the constant bias coordinate. The theorem's geometry is the geometry of , not just .
The final score is , whose boundary is . It does not maximize the usual geometric margin on the original input line: a threshold at 1 has distance one from both training points, while threshold is only distance from the negative point. A convergence theorem for a separator is not a maximum-margin optimization theorem. This distinction motivates the course's later support-vector-machine topic.
Concept lensAlgebraic
The weight as a signed sum of examples
Every update adds for the triggering example, so , where counts the updates triggered by example and . A score is then , which uses the examples only through inner products. In the first worked example , and .
Worked example 9.1.5
(Two points in the plane)
Take with label and with label , presented in that order. The augmented vectors are and . From the positive example has score , so . The negative example then has signed score , so . In the second pass both signed scores equal , so no update occurs: two updates in all. The bias coordinate was nonzero in the middle of the run and ends at zero. With both signed projections equal , and both augmented vectors have norm , so the bound is .
Worked example 9.1.6
(A single example attains the bound)
Let the only training example be with label , so and . The initial score is , so one update gives with signed score , and no further update occurs. Taking gives and , so , which equals the actual count. The bound is attained here; for most data sets it lies far above the true count, as in the first worked example, where the bound is and the count is three.
A budget is not a proof that no separator exists
The bound assumes a common positive margin. If that assumption fails, the perceptron need not stop. For example, the same input with opposite labels would require its score to be both strictly positive and strictly negative. Repeated presentations can keep causing updates.
Counterexample mode
Consistent labels can still require a nonlinear feature
Give and label , and label . An affine score would need , and . The last two inequalities imply both and , impossible when .
The labels are well-defined, but there is no affine separator on the original line. With feature , however, score separates them. The classifier is linear in the transformed feature, while its boundary in the original input is nonlinear. The margin theorem must be checked in whichever feature space is actually used.
Conversely, a finite run that has not yet separated the data does not prove nonseparability. Even separable data may need more updates than the chosen budget. A returned status should distinguish a verified current separator from the mere end of the training loop.
An implementation with an explicit verification result
The function accepts Python integers or finite floats as feature values, integer labels , and a positive integer epoch limit. It learns the bias through the appended coordinate and uses unit updates. Integer arithmetic stays exact in Python; floating-point scores are approximations. Nonfinite inputs are rejected, and any overflow or nonfinite intermediate raises an error rather than producing a verification result.
import math
def perceptron(rows, labels, max_epochs=100):
rows = [tuple(row) for row in rows]
labels = tuple(labels)
if not rows or len(rows) != len(labels) or type(max_epochs) is not int or max_epochs < 1:
raise ValueError("nonempty paired data and a positive integer epoch limit are required")
dimension = len(rows[0])
if not dimension or any(len(row) != dimension for row in rows):
raise ValueError("rows must have the same positive dimension")
if any(type(label) is not int or label not in (-1, 1) for label in labels):
raise ValueError("labels must be integer -1 or +1")
if any(type(x) not in (int, float) or (type(x) is float and not math.isfinite(x))
for row in rows for x in row):
raise ValueError("features must be integers or finite floats")
def checked(a, b, operation):
try:
result = a * b if operation == "multiply" else a + b
except OverflowError as exc:
raise ArithmeticError("floating-point operation overflowed") from exc
if type(result) is float and not math.isfinite(result):
raise ArithmeticError("nonfinite floating-point intermediate")
return result
def signed_score(weights, vector, label):
total = 0
for w, x in zip(weights, vector):
total = checked(total, checked(w, x, "multiply"), "add")
return checked(label, total, "multiply")
augmented = [row + (1,) for row in rows]
weights = [0] * (dimension + 1)
updates = 0
for _ in range(max_epochs):
changed = False
for vector, label in zip(augmented, labels):
if signed_score(weights, vector, label) <= 0:
weights = [checked(w, checked(label, x, "multiply"), "add")
for w, x in zip(weights, vector)]
updates += 1
changed = True
if not changed:
break
scores = [signed_score(weights, vector, label)
for vector, label in zip(augmented, labels)]
verified = all(score > 0 for score in scores)
return weights, updates, verified
For perceptron([(0,), (2,)], [-1, 1], max_epochs=2), the result is ([2, -1], 3, True). The explicit final check recognizes that the last allowed pass already produced a separator. With only one pass, the result is ([2, 0], 2, False): the negative point still has zero signed score, although this dataset is separable.
The weight list ends with the bias. Before returning, the function recomputes every signed score. True means all computed scores are finite and strictly positive; False means at least one computed score is nonpositive. With floats, rounding can change a score near zero, so this numerical check is not a rigorous exact-real separation certificate. Neither status is a probability estimate or a guarantee on unseen examples.
For examples, original features and passes, this implementation uses arithmetic work, plus a final check when needed. The stored weight takes space; the teaching implementation also materializes the augmented training rows. The margin bound limits updates under its assumptions, while the pass budget controls work even when those assumptions fail.
Exercises and worked solutions
Quick check
(The current augmented weight is and a positive example has original coordinate . Compute its old signed score, the updated weight and the new signed score. Is one update enough to classify it correctly?)
Augment the example with the constant coordinate first.
Solution · Answer
The augmented example is , so the old score is . Add that vector to obtain , with new score . The improvement is two, its squared norm, but the score is still negative. One update is not necessarily a complete repair.
Quick check
(For the points and with labels , use . Give the augmented radius, the common margin and the update bound. How many updates does the traced run actually make?)
Use the augmented vectors and .
Solution · Answer
The augmented vectors have norms one and , so . Both signed projections are , giving bound . The trace makes three updates. The bound is sufficient, not an exact prediction of the run length.
Quick check
(In expanding , why can the cross term be discarded for an upper bound? Would the same argument work if the algorithm also updated on correctly classified examples with positive margin?)
Look at the sign of when an update is triggered.
Solution · Answer
The cross term is , which is nonpositive precisely because an update is triggered only when the signed score is at most zero. Arbitrary positive-margin updates could make this term positive, so the stated upper bound would no longer follow from the same argument.
Quick check
(The two-point example is run for only one pass and the function reports that it is not verified. Does that prove the data have no affine separator? What does the returned weight fail to satisfy, and what happens in the second pass?)
Recompute the signed scores of the weight after one pass.
Solution · Answer
It does not prove nonseparability. Weight leaves the negative point at signed score zero. The second pass changes the weight to , with both signed scores positive, and the final verification succeeds after three total updates.
Quick check
(The learned threshold for the negative point and the positive point is . Compare its distance to the nearest point with that of threshold . Does finite convergence imply the largest possible geometric margin?)
Measure the distance from each threshold to the nearest training point.
Solution · Answer
Threshold has nearest-point distance ; threshold has distance one to both points. Thus this converged perceptron is not a maximum-margin separator. The theorem bounds updates until separation, rather than optimizing the original-space geometric margin.
Quick check
(For the negative points and the positive point , explain why no score separates them. Which single transformed feature makes the score work?)
Write the three strict inequalities in and .
Solution · Answer
The positive point requires . The negatives require and , a contradiction. Choose : the positive point scores , and each negative scores . This is separation in the transformed feature space, not an affine separator in the original coordinate.