The Perceptron Algorithm
Margin separation supplies the condition for the Perceptron convergence guarantee.
Try it: Perceptron (Batch)
How the Batch Perceptron learns a halfspace: it looks for an example with y⟨w,x⟩ ≤ 0 and adds y·x to w, until no mistakes remain — which happens only when the data is linearly separable.
How it works
- Start with w = 0 (with a bias, each x is extended with a constant 1, so b is learned as a weight).
- Scan the examples in order and take the first one with y⟨w,x⟩ ≤ 0 — a mistake.
- Update w ← w + y·x; the separating line ⟨w,x⟩ + b = 0 moves towards classifying it correctly.
- Repeat until a full pass finds no mistake (converged) or the update cap is reached.
- If the data is not linearly separable (checked exactly), no w works and the Perceptron would cycle forever.
Default run (14 steps): Start with w = 0 (and b = 0: x is extended with a constant 1). Every example has y⟨w,x⟩ = 0 ≤ 0, so every one counts as a mistake. … A full pass finds no example with y⟨w,x⟩ ≤ 0 (smallest y⟨w,x⟩ = 1.25). Converged after 12 updates: w = (3, 3.5), b = -6.
Simplified: 2-D toy data (at most 12 points on a half-unit grid) and a deterministic 'first mistake in list order' rule; the textbook allows any example with y⟨w,x⟩ ≤ 0. The update cap stands in for 'run forever'.
Loading the simulation…
Why the Margin Matters
The Perceptron is an online learner: it sees one input vector at a time, predicts a label, and receives the true label only afterward. Its central goal is to make as few mistakes as possible. The key question is not only whether it eventually finds a classifier with no mistakes, but also how much work it may require before doing so. The separation margin γ supplies that information.
A training set is separated with margin γ when the positive and negative examples lie on their correct sides of a separating hyperplane, with the minimum signed distance from an example to that separator at least γ. A larger margin means the examples are separated more generously; a smaller positive margin permits examples to lie closer to the boundary.
One Online Round
On round t, the Perceptron receives an input vector x_t from Rd and already has a current weight vector w(t). It uses those two pieces of information to predict. The true label y_t is revealed only after the prediction, so the label is feedback for evaluating the prediction rather than an input used to produce that same prediction.
The Perceptron prediction rule is p_t = sign(<w(t), x_t>). The weight vector and the incoming input determine the predicted label. Afterward, comparing p_t with y_t reveals whether the learner made a mistake.
From Score to Mistake
Tracing a prediction
Suppose the current weight vector is w(t) = (1, 0), the incoming input is x_t = (2, 0), and the true label is y_t = +1. Determine the prediction and whether a mistake occurs.
- 1Compute the score
The inner product <w(t), x_t> is 1 multiplied by 2 plus 0 multiplied by 0, which gives a positive score.
- 2Apply the prediction rule
Because the score is positive, sign(<w(t), x_t>) produces the positive prediction p_t = +1.
- 3Compare with feedback
The revealed true label is y_t = +1, so the prediction agrees with the label.
The Perceptron predicts +1 and does not make a mistake on this round.
Updates Before Convergence
When a mistaken example is encountered, the Perceptron updates its weight vector. Repeating this online process changes the current classifier as feedback arrives. For a training set separated with margin γ, the Perceptron makes at most 1/γ² updates before reaching a solution that makes no mistakes on the entire training set. In this context, convergence means obtaining such a mistake-free solution on the whole training set.
The dependence on γ is quadratic and inverse: the update ceiling is 1/γ². Therefore, the margin is the quantity that turns separation into a quantitative convergence guarantee.
Updates as a Compression Set
The same update bound has a second interpretation. Focus on the examples that caused the Perceptron to update. These examples can serve as a compressed representation associated with the learned classifier. Because there are at most 1/γ² updates, the associated compression scheme has size k satisfying k ≤ 1/γ².
Reading the compression bound
Suppose a training set is separated with margin γ. What can be said about the number of examples in the Perceptron-associated compression scheme?
- 1Use the update guarantee
The Perceptron makes at most 1/γ² updates before reaching a solution with no mistakes on the entire training set.
- 2Identify the retained examples
The examples that caused those updates are used as the compressed representation.
- 3Transfer the bound
Since the compressed representation contains no more update-causing examples than there were updates, its size satisfies k ≤ 1/γ².
The associated compression scheme has size k ≤ 1/γ².
When No Finite Guarantee Exists
The margin guarantee is conditional: it applies when the training set is separated with margin γ. It should not be confused with a finite mistake guarantee for every possible online sequence in the hypothesis class. For the stated class when d is at least 2, the Littlestone dimension is infinite. Infinite Littlestone dimension means that few-mistake guarantees are unavailable in general: an adversary can follow a path through a complete mistake tree so that no learner has a finite worst-case mistake bound.
The source supports this conclusion using the density of the real numbers. For d at least 2, it describes vectors such as (1/2, 1, 0, ..., 0), (1/4, 1, 0, ..., 0), and (3/4, 1, 0, ..., 0), together with hypotheses whose parameter vectors have the form (-1, a, 0, ..., 0), where a ranges over [0, 1]. This construction yields a tree shattered by the hypotheses and supports the conclusion that the Littlestone dimension is infinite.
Mistakes in Reasoning
Common mistake Treating the true label as available before the prediction
What it looks likeUsing y_t together with x_t to compute p_t
Why it failsIn the online protocol, y_t is revealed only after the prediction.
Do this insteadCompute p_t from w(t) and x_t first, then compare p_t with the revealed y_t.
Common mistake Saying that convergence means the Perceptron stops after one update
What it looks likeAssuming any update proves that the classifier has converged
Why it failsConvergence means obtaining a solution with no mistakes on the entire training set.
Do this insteadInterpret the update bound as a limit on the total number of updates before reaching a mistake-free solution under margin separation.
Common mistake Using 1/γ² as an unconditional mistake bound
What it looks likeClaiming that every online sequence receives at most 1/γ² mistakes
Why it failsThe stated Perceptron guarantee requires a training set separated with margin γ.
Do this insteadState the separation condition whenever giving the update guarantee.
Common mistake Confusing the update bound with the compression size
What it looks likeClaiming that the compression scheme has size γ²
Why it failsThe associated compression scheme is built from update-causing examples, whose number is bounded above by 1/γ².
Do this insteadWrite the compression bound as k ≤ 1/γ².
Common mistake Assuming infinite Littlestone dimension contradicts Perceptron convergence
What it looks likeConcluding that a margin-separated training set cannot have a finite update bound
Why it failsThe two statements concern different conditions: one uses margin separation, while the other concerns a general worst-case online guarantee for the class.
Do this insteadKeep conditional margin-based convergence separate from unrestricted finite mistake guarantees.
Check Your Understanding
A training set is separated with margin γ, and the Perceptron processes it online. Explain what the margin condition guarantees, what information is available when the Perceptron predicts on round t, when an update is triggered, and why the same update count bounds the compression size.
Hints
- Begin with the location of the examples relative to the separating hyperplane.
- Use the prediction rule p_t = sign(<w(t), x_t>).
- Distinguish the prediction from the later arrival of y_t.
- Connect update-causing examples to k ≤ 1/γ².
What do you think happens?
If a training set has a smaller positive margin, should the stated maximum update bound become larger or smaller?
Reveal answer
Larger
The bound is 1/γ², so decreasing a positive γ increases the upper bound.
Key Takeaways
- 1Margin separation means that the examples lie on their correct sides of a separating hyperplane with minimum signed distance at least γ.
- 2For a training set separated with margin γ, the Perceptron makes at most 1/γ² updates before reaching a solution with no mistakes on the entire training set.
- 3The examples that cause updates form an associated compression scheme of size k ≤ 1/γ².
- 4On round t, the Perceptron uses w(t) and x_t to produce p_t = sign(<w(t), x_t>), and only afterward receives y_t to determine whether a mistake occurred.
- 5When d is at least 2, infinite Littlestone dimension prevents a finite general worst-case mistake guarantee for the stated class, even though a margin-separated training set has the conditional Perceptron bound.
At a glance
- The margin γ converts geometric separation into a quantitative Perceptron update guarantee.
- A margin-separated training set requires at most 1/γ² Perceptron updates before a mistake-free solution is reached.
- The update-causing examples provide an associated compression scheme with size k ≤ 1/γ².
- The Perceptron predicts from w(t) and x_t before the true label y_t is revealed.
- Infinite Littlestone dimension rules out a finite general worst-case mistake guarantee in the stated setting, without contradicting the conditional margin bound.