PAC Learnability

Why Capacity Matters

A learning algorithm must choose a hypothesis from a hypothesis class. If the class can represent many different labelings of the same points, it has considerable capacity. That flexibility can help the class represent a target rule, but it also means that the learner has many possible rules to consider. PAC learnability studies when a learner can still select a hypothesis that performs well beyond the training sample.

Tracing Every Labeling

Let C be a finite set of points from the input space. Each point in C can receive label 0 or label 1. If C contains two points, there are four possible labelings: both points labeled 0, the first labeled 0 and the second labeled 1, the first labeled 1 and the second labeled 0, and both points labeled 1. A hypothesis class shatters C when it contains hypotheses that realize every one of those possible labelings on C.

From Shattered Sets to VC-Dimension

A particular shattered set and the VC-dimension are different objects. A shattered set is one specific set of points. The VC-dimension is a size: it records the largest size of any set that the class can shatter. If a class shatters one set of size three, that establishes only that its VC-dimension is at least three. A larger shattered set might still exist. If the class can shatter sets of arbitrarily large size, its VC-dimension is infinite.

Capacity and Learnability

The connection to learning appears when an adversary may choose a distribution and a target labeling. If a hypothesis class contains every possible labeling of a chosen set, it has no useful restriction on the rules it may consider on that set. The No-Free-Lunch consequence is that, without restricting the hypothesis class, an adversary can construct a distribution on which a particular learning algorithm performs poorly, even though another algorithm succeeds on that same distribution.

PAC learnability places structure around this problem. The adversary is restricted to distributions for which some hypothesis in the class has zero risk. Under this realizability condition, the learner is not asked to approximate a target that the class cannot represent at all. The class's capacity still matters because it determines how many different rules are available to explain the observed sample.

The ERM Selection Process

ERM uses the sample to compare candidates. It does not directly observe the true risk on the whole distribution. The finite-class PAC result explains when this sample-based selection is reliable: under realizability and with a sufficiently large sample, every ERM hypothesis is probably approximately correct.

Probably Approximately Correct

The guarantee is probabilistic because it concerns the random training sample. It does not claim that every possible sample produces an accurate hypothesis. Instead, for samples of the required size, it states that the desired accuracy holds with probability at least 1 minus delta. The error tolerance describes how much true error is allowed; delta describes the probability of failing to meet that accuracy.

Sample Size and Guarantee Strength

The finite-class PAC result connects three parts of the learning situation: the sample size, the allowed error, and the confidence requirement. The source states that, under realizability, a sufficiently large sample makes the finite-class ERM rule probably approximately correct. The confidence statement is expressed as probability at least 1 minus delta over samples of the required size.

The Realizability Requirement

This assumption matters because the finite-class PAC result is stated only for distributions and labeling functions for which a zero-risk hypothesis exists in the class. Under that condition, ERM can search for a hypothesis that fits the sample while the theorem connects sufficient sample size to performance beyond the sample. If no perfect hypothesis exists in the class, the realizable finite-class result described here does not apply as stated.

Common Reasoning Mistakes

• Treating one shattered set as the VC-dimension

  Shattering a set of size three proves only that the VC-dimension is at least three. A larger shattered set may exist.

  Fix: Use the VC-dimension only after identifying the maximum size of any shattered set, or state the result as a lower bound.

• Checking only one labeling

  Shattering requires every possible 0/1 labeling on the same chosen set.

  Fix: List all possible binary labelings and verify that the class realizes each one.

• Reading PAC as a guarantee for every sample

  The guarantee is probabilistic over the random choice of the training sample.

  Fix: Interpret the statement as accuracy holding with probability at least 1 minus delta for samples of the required size.

• Ignoring realizability

  The stated finite-class PAC result assumes that a zero-risk hypothesis exists in the class.

  Fix: Check the realizability assumption before applying the result.

• Confusing empirical error with true error

  ERM directly compares empirical errors on the observed sample. PAC analysis is what connects this selection to performance beyond the sample under the stated assumptions.

  Fix: Keep the training-sample measurement and the distribution-wide guarantee conceptually separate.

Practice Check

Key Takeaways

1. A hypothesis class shatters a chosen set when it realizes every possible 0/1 labeling of that set.
2. The VC-dimension is the maximum size of any set the class can shatter; one shattered set gives a lower bound unless larger sets have been ruled out.
3. PAC means probably approximately correct: the learned hypothesis has bounded true error with high probability over the random training sample.
4. ERM selects a minimum-empirical-risk hypothesis from a finite hypothesis class.
5. Under realizability and with a sufficiently large sample, the finite-class ERM rule is probably approximately correct.