The Realizable Assumption
Realizability is a condition on the learning setting, not a claim that the algorithm immediately returns the hypothesis that realizes f.
Why Slightly Better Matters
A learning algorithm does not always need to produce highly accurate predictions immediately to be useful. In boosting, even a learner whose error is only slightly better than random guessing can provide a useful starting point. This motivates weak learnability: an algorithm is useful as a weak learner when it can reliably return a hypothesis whose error is below the random-guessing level.
The Guarantee in Motion
What do you think happens?
If random guessing has error 1/2 and γ is positive, is an error of 1/2 − γ better or worse than random guessing?
Reveal answer
Better
Subtracting the positive quantity γ from 1/2 produces an error below 1/2. The amount of improvement over random guessing is γ.
- 1L_(D,f)(h) is the error of the returned hypothesis h under distribution D and labeling function f.
- 2The value 1/2 is the random-guessing error level described by the definition.
- 3γ represents the improvement below that level.
- 4The inequality says that the returned hypothesis has error no greater than 1/2 − γ.
Reading a Weak-Learner Bound
Suppose a weak-learner guarantee uses γ = 0.1. What error threshold does the expression 1/2 − γ describe?
- 1Start with the random-guessing level
The definition uses 1/2 as the reference error level.
- 2Subtract the improvement
With γ = 0.1, the threshold is 0.5 − 0.1.
- 3Interpret the result
The returned hypothesis is required to have error at most 0.4, which is 0.1 below the random-guessing level.
The guarantee is an error of at most 0.4, or 1/2 − 0.1.
Five Parts of the Setting
The weak-learner definition specifies the learning setting before the algorithm runs. H is the hypothesis class: the class for which the algorithm is being considered a weak learner. D is the data distribution, and f is the labeling function. The realizable assumption connects these ingredients by requiring the labeling function to be realizable by some hypothesis in H. The algorithm then receives enough i.i.d. labeled examples from this setting and returns a hypothesis h.
| Symbol or term | Role in the guarantee |
|---|---|
| H | The hypothesis class for which the algorithm is being considered. |
| D | The distribution used to describe the data setting and the returned hypothesis's error. |
| f | The labeling function in the learning setting. |
| h | The hypothesis returned after the algorithm runs. |
| γ | The amount by which the error guarantee improves over 1/2. |
| δ | The confidence parameter; the guarantee holds with probability at least 1 − δ. |
| m_H | The sample-size function indicating how many sufficient i.i.d. labeled examples are required for the guarantee. |
The main objects and parameters in the weak-learnability setting.
Realizability Before Learning
The realizable assumption means that the labeling function f can be realized by some hypothesis in H. In other words, the learning setting assumes that H contains at least one hypothesis capable of representing the labeling function relevant to the setting. Under this assumption, the weak-learner guarantee is stated for the algorithm's returned hypothesis h.
Confidence and Sample Requirements
The guarantee is probabilistic. With sufficient i.i.d. labeled data, the algorithm returns a hypothesis h satisfying the error bound with probability at least 1 − δ. The parameter δ controls the required confidence: the guarantee is expressed in terms of the complementary probability 1 − δ. The sample-size function m_H describes how many examples are sufficient for the guarantee, with the required amount depending on H, γ, and δ.
Changing the Confidence Requirement
Compare two guarantees that use the same H and γ but different values of δ.
- 1Identify the success probabilities
For any selected δ, the guarantee holds with probability at least 1 − δ.
- 2Interpret a smaller δ
A smaller δ means a larger value of 1 − δ, so the requested confidence is higher.
- 3Connect confidence to data
The sample-size function m_H depends on δ as well as H and γ, so the sufficient sample requirement is tied to the chosen confidence level.
δ changes the probability attached to the guarantee, while m_H specifies the sufficient sample size associated with H, γ, and δ.
Common Misreadings
Common mistake Treating 1/2 − γ as worse than random guessing because it contains a subtraction.
What it looks likeReading 1/2 − γ as a penalty rather than as an error threshold.
Why it failsγ is the improvement below the random-guessing level 1/2.
Do this insteadInterpret the bound as requiring an error no greater than 1/2 − γ.
Common mistake Confusing the realizing hypothesis in H with the hypothesis returned by the algorithm.
What it looks likeAssuming that realizability means the algorithm must return the hypothesis that realizes f.
Why it failsThe setting assumes that f is realizable by some hypothesis in H, while the algorithm returns h and the guarantee concerns h's error.
Do this insteadKeep the existence condition for H separate from the algorithm's output h.
Common mistake Ignoring the probabilistic wording of the guarantee.
What it looks likeClaiming that every run must return a hypothesis satisfying the error bound.
Why it failsThe guarantee holds with probability at least 1 − δ.
Do this insteadInclude both the error bound and its probability statement.
Common mistake Treating m_H as unrelated to the learning setting.
What it looks likeAssuming that one fixed number of examples works regardless of H, γ, and δ.
Why it failsThe sufficient sample-size function depends on H, γ, and δ.
Do this insteadRead m_H as the required sample-size condition associated with those choices.
Apply the Definition
Describe, in one paragraph, what must be specified before a learning algorithm can be called a γ-weak-learner for H. Include H, D, f, the realizable assumption, δ, sufficient i.i.d. labeled data, the returned hypothesis h, and the error guarantee.
Hints
- Begin with the hypothesis class and the learning setting.
- Explain what realizability says about f and H.
- End with the bound and the probability with which it holds.
- 1A γ-weak-learner is useful because it reliably produces an error below the random-guessing level. The definition is set in terms of H, D, and f, with the realizable assumption requiring f to be realizable by some hypothesis in H. Given sufficient i.i.d. labeled examples, the algorithm returns h whose error satisfies L_(D,f)(h) ≤ 1/2 − γ with probability at least 1 − δ. The function m_H describes the sufficient sample size needed in relation to H, γ, and δ.
Key Takeaways
- Weak learnability requires an error below the random-guessing level of 1/2.
- The defining bound is L_(D,f)(h) ≤ 1/2 − γ, where γ measures the improvement over random guessing.
- H, D, and f define the learning setting, and realizability means that f can be realized by some hypothesis in H.
- With sufficient i.i.d. labeled data, the guarantee holds with probability at least 1 − δ.
- The sample-size function m_H describes the sufficient number of examples in relation to H, γ, and δ.