The Realizable Assumption
Weak learnability allows a learning algorithm to be useful even when its accuracy is only slightly better than random guessing.
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
Answer: Better
Subtracting the positive quantity γ from 1/2 produces an error below 1/2. The amount of improvement over random guessing is γ.
L_(D,f)(h) ≤ 1/2 − γ
Reading a Weak-Learner Bound
Suppose a weak-learner guarantee uses γ = 0.1. What error threshold does the expression 1/2 − γ describe?
Start with the random-guessing level: The definition uses 1/2 as the reference error level.
Subtract the improvement: With γ = 0.1, the threshold is 0.5 − 0.1.
Interpret 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 δ.
Identify the success probabilities: For any selected δ, the guarantee holds with probability at least 1 − δ.
Interpret a smaller δ: A smaller δ means a larger value of 1 − δ, so the requested confidence is higher.
Connect 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
Treating 1/2 − γ as worse than random guessing because it contains a subtraction.
γ is the improvement below the random-guessing level 1/2.
Fix:
Interpret the bound as requiring an error no greater than 1/2 − γ.Confusing the realizing hypothesis in H with the hypothesis returned by the algorithm.
The setting assumes that f is realizable by some hypothesis in H, while the algorithm returns h and the guarantee concerns h's error.
Fix:
Keep the existence condition for H separate from the algorithm's output h.Ignoring the probabilistic wording of the guarantee.
The guarantee holds with probability at least 1 − δ.
Fix:
Include both the error bound and its probability statement.Treating m_H as unrelated to the learning setting.
The sufficient sample-size function depends on H, γ, and δ.
Fix:
Read 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.
- A γ-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 δ.