Hypothesis Classes and Learning Algorithms
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, an algorithm whose predictions are only slightly better than random guessing can serve as a starting point for building stronger performance. This motivates weak learnability: the algorithm must reliably produce a hypothesis whose error is below the random-guessing level.
What do you think happens?
Suppose an algorithm has an error bound of 1/2 − γ for some positive γ. Is this bound better than the random-guessing level?
Reveal answer
Answer: Yes, because γ is subtracted from 1/2.
The random-guessing level in this definition is 1/2. Subtracting a positive γ makes the allowed error smaller than 1/2, so the learner is required to perform slightly better than random guessing.
The Learning Setting
The definition begins by specifying the learning setting before the algorithm runs. The setting includes a hypothesis class H, a distribution D, a labeling function f, a confidence parameter δ, and enough independently and identically distributed labeled examples. The algorithm uses this information in the form of labeled data and returns a hypothesis h. The success claim is about that returned hypothesis: its error L_(D,f)(h) must be at most 1/2 − γ with probability at least 1 − δ.
| Symbol | Role in the definition |
|---|---|
| H | The hypothesis class used to specify the learning problem and the hypotheses available to the learner. |
| D | The distribution from which the examples are sampled. |
| f | The labeling function used to label the examples. |
| A | The learning algorithm that processes labeled examples. |
| h | The hypothesis returned after the algorithm runs. |
| γ | The positive improvement over the random-guessing error level. |
| δ | The confidence parameter used in the probability guarantee. |
The symbols describe the setting, the procedure, the output, and the strength of the guarantee.
Reading the Error Bound
An algorithm is a γ-weak-learner for H when, under the specified learning setting and with sufficient labeled data, it can produce a hypothesis h whose error satisfies L_(D,f)(h) ≤ 1/2 − γ with probability at least 1 − δ.
The quantity 1/2 is the random-guessing level used by this definition. The term γ represents the amount by which the learner must improve on that level. Because γ is subtracted, a positive γ makes the permitted error smaller than 1/2. Weak learning therefore does not demand highly accurate predictions at the beginning; it demands a reliable improvement over random guessing.
Interpreting a Positive Advantage
Suppose γ is 0.1. What error threshold does the weak-learner guarantee describe?
Start with the baseline: The random-guessing error level in the definition is 1/2.
Subtract the advantage: The guarantee lowers that baseline by γ, which is 0.1 in this example.
Interpret the result: The resulting threshold is 0.4, so the returned hypothesis must have error no greater than 0.4 when the guarantee succeeds.
The weak learner is allowed an error of at most 0.4 in this generated numerical illustration, rather than the 0.5 random-guessing level.
From Examples to Guarantee
The sample-size function m_H determines how many labeled examples are sufficient for the guarantee in the definition. When the algorithm receives at least m_H examples, sampled independently and identically from D and labeled by f, the returned hypothesis is required to meet the error bound with probability at least 1 − δ. The guarantee is probabilistic: it does not say that every possible sample produces a successful hypothesis, but it specifies how likely the success claim is under the stated conditions.
A Complete Guarantee
Putting Every Symbol Together
Interpret a statement saying that algorithm A is a γ-weak-learner for H under distribution D and labeling function f, with confidence parameter δ and sample-size function m_H.
Identify the allowed hypotheses: H is the hypothesis class associated with the learning problem. The returned hypothesis h is considered in relation to this class.
Identify the data setting: Examples are sampled independently and identically from D and receive labels from f.
Check the sample condition: The algorithm must receive at least m_H labeled examples for the stated guarantee to apply.
Read the performance condition: The returned hypothesis must have error L_(D,f)(h) no greater than 1/2 − γ.
Read the confidence condition: The probability that this error guarantee holds is at least 1 − δ.
The complete claim concerns A, H, D, f, δ, m_H, and the returned h: with sufficient i.i.d. labeled data, A reliably returns a hypothesis whose error is below the random-guessing level.
Notice the order of the reasoning. First specify the class, distribution, labeling function, confidence parameter, and data requirement. Then run the algorithm on the labeled examples. Finally evaluate the returned hypothesis using the error bound and the probability guarantee. This prevents the common mistake of treating 1/2 − γ as an unconditional promise about every output and every dataset.
Mistakes in Reading the Definition
Treating weak learning as highly accurate learning.
The defining requirement is only that the error be at most 1/2 − γ, which is slightly better than the random-guessing level.
Fix:
Read γ as the required improvement over random guessing, not as a demand for near-perfect predictions.Forgetting the distribution and labeling function.
The error is written as L_(D,f)(h), and the learning guarantee depends on the specified D and f.
Fix:
State which distribution supplies examples and which labeling function supplies their labels.Confusing δ with the error threshold.
The error threshold is determined by 1/2 − γ, whereas δ appears in the probability guarantee.
Fix:
Use δ to interpret how likely the error guarantee is to hold.Ignoring the sample-size requirement.
The definition requires sufficient i.i.d. labeled data, described through the sample-size function m_H.
Fix:
Check the data condition before invoking the guarantee.Confusing H with the learning algorithm.
H is the hypothesis class, while the algorithm is the procedure that processes the labeled examples and returns h.
Fix:
Keep the class H and the learning algorithm A as separate parts of the definition.
Check Your Understanding
A learner receives fewer than m_H labeled examples but returns a hypothesis whose observed error is below 1/2 − γ. Can you directly invoke the stated weak-learning guarantee? Explain the roles of the missing sample-size condition and the probability 1 − δ.
Hints
- The guarantee includes a condition about the number of i.i.d. labeled examples.
- Separate the actual observed result from the conditions required to claim the formal guarantee.
- Remember that δ describes the probability attached to the guarantee, not the error threshold itself.
In your own words, explain why an algorithm with error only slightly below 1/2 can still be useful as a weak learner.
Hints
- Compare the error with the random-guessing level.
- Connect the small improvement to the motivation from boosting.
Key Takeaways
- A γ-weak-learner for H reliably returns a hypothesis h with error at most 1/2 − γ.
- The subtraction of γ makes the allowed error lower than the random-guessing level of 1/2.
- H specifies the hypothesis class, D specifies the example distribution, and f specifies the labeling function.
- The sample-size function m_H describes how many i.i.d. labeled examples are sufficient for the guarantee.
- The confidence parameter δ means that the error guarantee holds with probability at least 1 − δ.
Key Takeaways
- Weak learnability requires performance slightly better than random guessing, not immediate high accuracy.
- The central error condition is L_(D,f)(h) ≤ 1/2 − γ.
- The learning setting includes H, D, f, δ, and sufficient i.i.d. labeled data.
- The sample-size function m_H controls the required amount of data, while δ controls the confidence of the guarantee.
- The algorithm produces the hypothesis h; H is the class associated with the hypotheses.