Generalization Bounds
The update bound is obtained from that separation.
Why the Margin Matters
A Perceptron may update its weight vector whenever it makes a mistake. The important question is not only whether it eventually finds a classifier that makes no mistakes, but also how many updates may be required. A separation margin γ supplies that information: when the training set is separated with margin γ, the Perceptron makes at most 1/γ² updates before reaching a solution with no mistakes on the entire training set.
The margin is the condition that makes the Perceptron's finite convergence guarantee possible in this setting.
Margin-Separated Training Sets
A training set is separated with margin γ when a separating boundary places every positive example and every negative example on its correct side, with the separation from the boundary measured by γ. The larger the margin, the stronger the separation condition. The generalization-bound result uses this condition to control how many mistakes-driven updates the Perceptron can make.
Following the Perceptron Updates
The Perceptron update process can be viewed as a sequence. A mistake causes an update to the weight vector. The algorithm continues processing the training set. Once it reaches a classifier that makes no mistakes on the entire training set, convergence has been reached.
Reading the Guarantee
Suppose a training set is separated with margin γ = 1/5. What maximum number of Perceptron updates is supplied by the bound?
- 1Identify the bound
For a training set separated with margin γ, the maximum number of updates is 1/γ².
- 2Substitute the margin
With γ = 1/5, the bound becomes 1/(1/5)².
- 3Evaluate
Since (1/5)² = 1/25, the expression is 25.
The bound allows at most 25 Perceptron updates.
The Update Bound
- 1Start with the separation margin γ.
- 2Square the margin to obtain γ².
- 3Take the reciprocal to obtain the maximum-update bound 1/γ².
The bound makes the relationship between margin and work explicit. A larger margin produces a smaller value of 1/γ², while a smaller margin produces a larger value. Thus, stronger separation corresponds to a lower upper bound on the number of updates. The guarantee says that the Perceptron reaches a solution with no mistakes on the entire training set after at most this many updates.
Comparing Two Margins
Compare the update bounds for γ = 1/2 and γ = 1/4.
- 1Use γ = 1/2
The bound is 1/(1/2)² = 4.
- 2Use γ = 1/4
The bound is 1/(1/4)² = 16.
- 3Compare
The smaller margin has the larger maximum-update bound.
The bound is 4 updates for γ = 1/2 and 16 updates for γ = 1/4.
Updates as a Compression Scheme
The Perceptron update bound also gives a compression result. The examples that triggered Perceptron updates can be retained as a compressed representation of the final classifier. Because there are at most 1/γ² updates, the associated compression scheme has size k satisfying k ≤ 1/γ².
Finding the Compression Size
Suppose a training set is separated with margin γ = 1/10. What size bound does the associated compression scheme have?
- 1Apply the compression bound
The compression size satisfies k ≤ 1/γ².
- 2Substitute the margin
With γ = 1/10, k ≤ 1/(1/10)².
- 3Evaluate
The expression equals 100.
The associated compression scheme has size k ≤ 100.
Connecting the Three Results
The reasoning chain is compact. First, assume the training set is separated with margin γ. Second, use that condition to bound the Perceptron's updates by 1/γ². Third, interpret the result in two ways: after at most that many updates, the Perceptron reaches a classifier with no mistakes on the entire training set; and the examples that triggered those updates provide a compression scheme of size at most 1/γ².
Common Reasoning Mistakes
Common mistake Treating 1/γ² as the exact number of updates.
What it looks likeFor γ = 1/2, the bound is 4.Why it failsThe result gives a maximum number of updates, not necessarily the number the algorithm actually performs.
Do this insteadSay that the Perceptron makes at most 1/γ² updates.
Common mistake Describing convergence as merely finding a boundary.
What it looks likeThe algorithm has converged because it produced a candidate classifier.
Why it failsThe stated convergence meaning is stronger: the solution makes no mistakes on the entire training set.
Do this insteadCheck convergence against the whole training set.
Common mistake Using γ² instead of 1/γ² as the update bound.
What it looks likeA margin of 1/10 would give an update bound of 1/100.
Why it failsThe guarantee uses the reciprocal of the squared margin.
Do this insteadCompute the bound as 1 divided by γ².
Common mistake Separating the compression size from the update bound.
What it looks likeThe update bound is 1/γ², but the compression size has a different bound.
Why it failsThe associated compression scheme has size k ≤ 1/γ².
Do this insteadUse the same upper bound for the retained update-triggering examples.
Check Your Understanding
A training set is separated with margin γ = 1/4. State the maximum number of Perceptron updates guaranteed by the bound, and state the corresponding compression-size bound.
Hints
- Use the expression 1/γ² for the update bound.
- The compression-size bound uses the same expression.
What do you think happens?
If the margin changes from γ = 1/2 to γ = 1/4, does the maximum-update bound become smaller or larger?
Reveal answer
Larger
The bound is 1/γ². The smaller margin γ = 1/4 gives 16, whereas γ = 1/2 gives 4.
Key Takeaways
- A training set separated with margin γ has its positive and negative examples on the correct sides of a separating boundary with separation measured by γ.
- For such a training set, the Perceptron makes at most 1/γ² updates.
- Convergence means reaching a classifier that makes no mistakes on the entire training set.
- The update bound becomes a compression bound because the examples that triggered updates can be retained, with compression size k ≤ 1/γ².
- A larger margin gives a smaller upper bound, while a smaller margin gives a larger upper bound.