PAC Learnability

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.

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.

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.

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.

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.

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.

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.

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.