Finite Hypothesis Classes
i.i.d. sampling means independent examples drawn from the same distribution D.
The Learning Guarantee
A learning algorithm does not receive the distribution D directly. It receives a training set sampled from that distribution and must choose a hypothesis. Finite hypothesis classes give us a reassuring result: every finite collection of possible hypotheses is PAC learnable. The important question is how that conclusion is assembled from sampling, risk thresholds, probability bounds, and sample complexity.
The finite-class result establishes learnability, but the supplied result does not provide a numerical sample bound or a formula for calculating the exact number of required examples.
Building the Training Set
The notation S ∼ D^m describes a random training set S containing m examples. The i.i.d. assumption says two things about how those examples are obtained: they are independent of one another, and they are all drawn from the same distribution D. Thus, the training set is a sample of m independent draws from one common source distribution.
Reading S ∼ D^m
Interpret the statement S ∼ D^m.
Identify S: S is the random training set.
Identify m: m is the number of examples in that training set.
Identify D^m: The notation indicates that the m examples are independently drawn from the same distribution D.
S is a training set of m independent examples, all sampled from D.
Risk and the Accuracy Threshold
An ERM learner receives a training set rather than direct access to D. Its output depends on the sampled set S, so the analysis must connect what happened on S with what may happen under D. The notation L(D,f)(hS) refers to the risk of the hypothesis hS produced from the training set. The parameter ϵ sets the boundary for acceptable risk: a hypothesis whose risk is greater than ϵ is beyond the permitted accuracy level.
Classifying an Output
Suppose the permitted risk threshold is ϵ. How should two possible learner outputs be interpreted?
Output A: If L(D,f)(hS) is at most ϵ, the output meets the accuracy boundary being studied.
Output B: If L(D,f)(hS) is greater than ϵ, the output belongs to the unacceptable-risk case for this guarantee.
The threshold separates approximate correctness from learner failure; it does not separate perfection from imperfection.
Collecting Bad Events
To analyze failure, define the set HB of bad hypotheses. A hypothesis is in HB when its risk is beyond the permitted accuracy level. Instead of examining every possible training-set outcome separately, the analysis associates failure events with these bad hypotheses and then combines those events.
The Union Bound says that the probability of a union of events is no greater than the sum of the probabilities of the individual events. In a finite-class analysis, each bad hypothesis contributes an event, and the Union Bound turns the separate probability bounds into one overall bound on failure. The events do not need to be disjoint. If they overlap, adding their probabilities may overcount some outcomes, which is why the sum is an upper bound rather than necessarily the exact probability.
Applying the Union Bound
Suppose failure can occur through bad-hypothesis events A or B. What can be said about the probability of overall failure?
Name the combined event: Overall failure is the event that A or B occurs.
Add the separate bounds: The Union Bound uses the probability bound for A plus the probability bound for B.
Account for overlap: A and B may happen together, so the sum is an upper bound and need not equal the exact probability.
The probability of A or B is at most the sum of the probabilities of A and B.
Why Finiteness Is Sufficient
A finite hypothesis class contains a finite collection of possible hypotheses. When the bad hypotheses are considered, there are only finitely many associated bad-hypothesis events to combine. The Union Bound can therefore collect their individual probability bounds into one overall failure bound. This is the mechanism behind the result that every finite hypothesis class is PAC learnable with sample complexity.
Sample Complexity in Context
Sample complexity is the number of samples required for learning a hypothesis class. In a PAC learnability guarantee, the required sample size is connected to the accuracy threshold ϵ, the probability of failure, and the hypothesis class being learned. The supplied finite-class statement establishes that such a sample complexity exists for every finite hypothesis class, but it does not provide a numerical formula.
| Question | What the finite-class result says | What it does not say |
|---|---|---|
| Is learning possible? | Every finite hypothesis class is PAC learnable. | It does not give a numerical sample bound. |
| What is sample complexity? | It is the number of samples required for learning. | The result does not calculate the exact number here. |
| What role does finiteness play? | It makes the finite-class result sufficient for learnability. | Finiteness is not the complete characterization of learnability. |
Beyond Counting Hypotheses
Finiteness is sufficient in the result presented here, but it is not the deepest characterization of learnability. Some infinite hypothesis classes are learnable too. The broader measure introduced for this purpose is VC dimension, described as a combinatorial measure that determines the PAC learnability of a class. This shifts attention from simply counting hypotheses to examining structural properties of the class.
Common Reasoning Mistakes
Treating S ∼ D^m as m identical examples.
The examples are independent draws from the same distribution D; same distribution does not mean identical outcomes.
Fix:
Interpret S as a random set of m independent examples sampled from D.Calling every output with nonzero risk a failure.
The parameter ϵ defines the permitted risk boundary. The relevant failure case is L(D,f)(hS) greater than ϵ.
Fix:
Compare the output risk with ϵ rather than with zero.Assuming the Union Bound requires disjoint events.
The Union Bound still applies when events overlap; overlap is why the sum is an upper bound rather than necessarily the exact probability.
Fix:
Add the separate probability bounds to obtain an upper bound on their union.Claiming that the finite-class result supplies an exact sample count.
The result establishes learnability and the existence of sample complexity, but the supplied statement does not provide a numerical sample formula.
Fix:
State the qualitative conclusion and avoid inventing an exact number.Concluding that every infinite class is unlearnable.
The source notes that some infinite classes are learnable.
Fix:
Recognize finiteness as sufficient for the presented result, while VC dimension gives a broader perspective.
Check Your Understanding
A learner receives S ∼ D^m and outputs hS. Explain what must be true about the sampling process, what comparison determines whether the output crosses the accuracy boundary, and how the Union Bound helps when several bad hypotheses are possible.
Hints
- Mention independence and the common distribution D.
- Use the comparison between L(D,f)(hS) and ϵ.
- Describe the Union Bound as combining separate event-probability bounds.
A class is finite, but no numerical sample bound is provided. What conclusion is justified, and what conclusion is not justified?
Hints
- Use the finite-class PAC learnability result.
- Separate existence of sample complexity from an exact numerical formula.
Key Takeaways
- S ∼ D^m means that the training set contains m independent examples drawn from the same distribution D.
- The accuracy parameter ϵ is a risk threshold: the output is in the unacceptable-risk case when L(D,f)(hS) is greater than ϵ.
- The Union Bound combines probability bounds for separate bad-hypothesis events into an upper bound on their union, even when those events overlap.
- Every finite hypothesis class is PAC learnable with sample complexity, but the supplied result does not give an exact numerical sample formula.
- Finiteness is sufficient for the presented result, while VC dimension provides a broader combinatorial perspective because some infinite classes are also learnable.