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.

Programming

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?

Yes, because γ is subtracted from 1/2
No, because the bound is still close to 1/2
Only when γ is larger than 1/2

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 − δ.

What does each symbol provide, and how do the learning setting and algorithm connect to produce the weak-learner guarantee?

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

Definition

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.

How much lower is the weak learner's allowed error than the random-guessing error rate?

Worked example

Interpreting a Positive Advantage

Suppose γ is 0.1. What error threshold does the weak-learner guarantee describe?

1
Start with the baseline
The random-guessing error level in the definition is 1/2.
2
Subtract the advantage
The guarantee lowers that baseline by γ, which is 0.1 in this example.
3
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.

Result

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.

How does receiving at least m_H labeled examples make the error guarantee hold with probability at least 1 − δ?

How does data sampled from D and labeled by f move through the algorithm to produce a hypothesis in H?

A Complete Guarantee

Worked example

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.

1
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.
2
Identify the data setting
Examples are sampled independently and identically from D and receive labels from f.
3
Check the sample condition
The algorithm must receive at least m_H labeled examples for the stated guarantee to apply.
4
Read the performance condition
The returned hypothesis must have error L_(D,f)(h) no greater than 1/2 − γ.
5
Read the confidence condition
The probability that this error guarantee holds is at least 1 − δ.

Result

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

Common mistake
Treating weak learning as highly accurate learning.
What it looks like
Assuming that a weak learner must have very small error.
Why it fails
The defining requirement is only that the error be at most 1/2 − γ, which is slightly better than the random-guessing level.
Do this instead
Read γ as the required improvement over random guessing, not as a demand for near-perfect predictions.
Common mistake
Forgetting the distribution and labeling function.
What it looks like
Describing the guarantee only in terms of H and the algorithm.
Why it fails
The error is written as L_(D,f)(h), and the learning guarantee depends on the specified D and f.
Do this instead
State which distribution supplies examples and which labeling function supplies their labels.
Common mistake
Confusing δ with the error threshold.
What it looks like
Saying that δ changes 1/2 − γ.
Why it fails
The error threshold is determined by 1/2 − γ, whereas δ appears in the probability guarantee.
Do this instead
Use δ to interpret how likely the error guarantee is to hold.
Common mistake
Ignoring the sample-size requirement.
What it looks like
Applying the guarantee without checking whether at least m_H labeled examples were supplied.
Why it fails
The definition requires sufficient i.i.d. labeled data, described through the sample-size function m_H.
Do this instead
Check the data condition before invoking the guarantee.
Common mistake
Confusing H with the learning algorithm.
What it looks like
Calling H the procedure that selects the hypothesis.
Why it fails
H is the hypothesis class, while the algorithm is the procedure that processes the labeled examples and returns h.
Do this instead
Keep the class H and the learning algorithm A as separate parts of the definition.

Check Your Understanding

MEDIUM

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.

Your attempt (not saved)

EASY

In your own words, explain why an algorithm with error only slightly below 1/2 can still be useful as a weak learner.