Motivation
A classifier can fit a training sample perfectly and still make many errors on unseen examples. To reason about this gap we need to say how the sample was obtained, how error is measured, and what probability statement the learner must satisfy. Probably approximately correct (PAC) learning makes these assumptions explicit. It asks for a hypothesis that is approximately right with high probability over a random training sample; it does not promise correctness for every possible sample.
We begin in the realizable binary setting. The labels are produced by a target concept in the chosen hypothesis class, examples are independent draws from one fixed but unknown distribution, and the learner sees labeled examples. Later models may relax these assumptions. In particular, a statistical sample bound does not automatically supply an efficient algorithm to find the required hypothesis.
Definitions
Definition 1.1.1
(Risk and PAC guarantee)
Let be a measurable instance space, a class of measurable functions, a probability distribution on , and the target. Take . An i.i.d. sample has empirical error
A realizable PAC learner, for every , target , and , returns satisfying with probability at least over its sample and any internal randomness. A sample-complexity bound controls how many labeled examples suffice. Efficient PAC learning additionally requires a suitable polynomial running-time bound in the relevant problem parameters.
A hypothesis is consistent when its empirical error is zero. Consistency refers to the observed data, not to every point of . The distribution determines which errors matter: disagreement on an instance of probability zero contributes nothing to risk.
Definition 1.1.2
(Shattering and VC dimension)
A set is shattered by if, for each of its binary labelings, some realizes that labeling on . The VC dimension is the largest size of a shattered finite set, or infinity if arbitrarily large finite sets are shattered. Existence of one shattered set of size suffices; every set of size need not be shattered.
Concept lensCombinatorial
Shattering as a count of label patterns
For a finite let be the set of label patterns that realizes on . Then is shattered if and only if , that is, . Several hypotheses may produce the same pattern, so . A finite class can therefore shatter only sets with , which gives . The same notion is thus read as a count of patterns instead of a pattern-by-pattern check.
Theorem/Proposition
Theorem 1.1.3
(Finite-class consistent learning bound)
Let be finite and suppose an algorithm always returns a member of consistent with a realizable i.i.d. sample of size . If
then with probability at least its output has risk at most .
Theorem 1.1.4
(A countable Occam bound)
Assign positive weights to a countable class with . With probability at least , every sample-consistent simultaneously satisfies
The weights must be fixed independently of the observed sample. A short description can be assigned larger weight, yielding a smaller bound for a consistent hypothesis with a shorter description.
Proof sketch or proof idea
Proof
(A bad hypothesis must avoid all sampled errors)
Fix with . Each independent example lands in its disagreement region with probability greater than . Thus the probability that is nevertheless consistent is at most
There are at most candidates. The union bound makes the probability that any bad candidate is consistent at most . On the complementary event every consistent output is good, even though the algorithm chooses it after inspecting the sample. The proof uses independence in the product probability and realizability to ensure a consistent target exists.
For the weighted result, put . If , the chance that is consistent while is at most ; if , the desired inequality is automatic. Summing these probabilities over the class gives at most . No independence between the bad events for different hypotheses is needed for this union bound.
Proof X-ray
Why a data-dependent choice is covered
First fix one bad hypothesis: independence bounds the chance that it escapes detection. Then take a union over every hypothesis before the learner chooses its output. On the resulting good event, every consistent candidate is accurate, so the guarantee also applies to an output selected after observing the sample.
The following separate four-point example makes the proof concrete. Inputs are drawn independently and uniformly from {a,b,c,d}, the target is 0000, and the fixed class is {0000,0001,0011}. For two draws, , and the largest-index consistent rule, four of sixteen ordered samples select a bad hypothesis. Change the rule to compare this learner-specific event with the event that any bad consistent hypothesis survives. The sample bound is sufficient and distribution-free; this exact count is for the stated uniform distribution.
Worked examples
Worked example 1.1.5
(A finite hypothesis class)
Suppose , and . The sufficient sample size is
This is a distribution-free sufficient bound, not an exact threshold for every distribution or class. A learner must still find a consistent hypothesis; the counting argument does not give a running time.
Worked example 1.1.6
(Thresholds on the real line)
Let , where . Any one point is shattered: choose on either side of it. Two ordered points cannot receive labels from a threshold, although the other three labelings are possible. Thus the VC dimension is one. The class is infinite, so the finite-cardinality bound cannot be applied by substituting an infinite value; capacity is better captured here by shattering.
Worked example 1.1.7
(Intervals on the real line)
Let hypotheses be indicators of bounded closed intervals, together with the empty set. Two distinct points can receive all four labelings, using an interval around either point, an interval containing both, or the empty set. For three ordered points, the labeling cannot be realized by any interval. Therefore the VC dimension is two. Even without the empty hypothesis, a bounded interval disjoint from the finite set realizes the all-zero labeling.
The explorer below lists every labeling of a fixed sample for thresholds and for intervals, each with a fitting hypothesis or an ordered obstruction, so both VC dimensions can be checked pattern by pattern.
Common mistakes
Common mistake
(Testing one set instead of all sets)
To show it is enough to exhibit one shattered set of size . To show one must rule out every set of size ; finding one unshattered set proves nothing. For example, let and let consist of the four functions that vanish at . The set is not shattered, since no hypothesis gives the label , yet is shattered and .
Common mistake
(Training error, population error and probability)
A zero empirical error does not imply zero population error. The confidence parameter bounds the probability of drawing a sample on which the guarantee fails; bounds the population error on the successful event. Neither parameter is itself a probability that one fixed test prediction is wrong.
Counterexample mode
Weights that sum to more than one
Suppose one tried the Occam bound with for every hypothesis. Take , uniform, target , and , where is the indicator of the single point . Then for every , and the weights sum to . With the claimed bound reads , and for it equals . But a sample of seven draws contains at most seven distinct points, so some point is unsampled; then is consistent with the sample while its risk is . The claimed event "every consistent hypothesis has risk at most " therefore has probability , not at least . With the legitimate weights the bound is , which is consistent with what happens. The condition is exactly what the union bound over hypotheses requires.
The guarantee is distribution-free only within the model: independently sampled examples from one fixed distribution and labels from a target in . It does not justify applying the same bound unchanged to dependent samples, distribution shift, or arbitrary label noise.
Summary
Consistency plus a finite class gives a distribution-free sample bound through a union bound. Weighted counting extends the argument to countable classes. VC dimension measures the label patterns a class can realize and remains informative for infinite classes. Statistical learnability and efficient computation are separate questions.
Exercises
Quick check
(For , and , find the sufficient integer sample size from the finite-class theorem.)
Evaluate and round up.
Solution · Answer
The bound is , so suffices after rounding up.
Quick check
(Let contain all binary functions on a finite domain of points. Find its VC dimension and explain why.)
Is the whole domain shattered? Can any subset be larger?
Solution · Answer
The entire domain is shattered, since all labelings are represented. No subset has more than points, so the dimension is exactly .
Quick check
(Suppose a class has a consistent hypothesis with weight , and . Give the weighted upper bound on its risk.)
Here .
Solution · Answer
On the simultaneous high-probability event, . The inequality applies to every consistent hypothesis on that event, including one chosen after seeing the sample.
Quick check
(Use the pattern-count description to show that a class of five hypotheses cannot shatter any set of three points.)
Compare with .
Solution · Answer
On any three points , the restriction contains at most one pattern per hypothesis, so . The eight labelings cannot all appear, so is not shattered.