A wrong label need not make learning impossible
Realizable PAC learning assumes that every observed label agrees with a target concept. If a label is occasionally flipped, a learner that insists on fitting every example can reject a perfectly useful hypothesis or fit the noise instead. The remedy is not to ignore assumptions about labels: it is to specify a noise mechanism and analyze the resulting observed risk.
We study binary classification with a finite hypothesis class. The exact model lets us compare errors against corrupted labels with errors against the unobserved clean target. It also shows why noise close to one half makes the learning problem statistically harder. This is a guarantee for a particular independent noise model, not a claim that arbitrary mislabeling is harmless.
Clean and observed errors
Let have probability distribution on a measurable instance space , let be measurable, and let be a finite nonempty set of measurable classifiers. Fix , and before sampling. All logarithms below are natural. For , define the clean error
Definition 9.1.1
(Random classification noise)
In the random classification noise model, a label is , where is a Bernoulli random variable with , independent of . The pairs used for the examples are independent and identically distributed copies of . Assume . The learner sees , not or the clean label.
For , let be observed-label error. Conditioning on whether agrees with gives the key identity
A correct clean prediction becomes wrong exactly when the noise bit is one; a wrong clean prediction remains wrong exactly when the bit is zero. Since , the ordering of hypotheses by observed error is the same as their ordering by clean error. The errors themselves are not equal: even the target has observed risk .
Worked example 9.1.2
(A numerical comparison)
If , a classifier with clean error has observed error . Another with clean error has observed error . The second is still worse, but the observed gap is smaller than the clean gap . Detecting a small gap therefore requires enough samples to overcome sampling variation.
Finite-class learning guarantee
Given independent corrupted examples , define
Choose any empirical risk minimizer , with a fixed tie rule. The class is finite, so the minimum exists. The algorithm does not need to know to compare empirical errors; the sample-size guarantee below does depend on it. Searching the class may be computationally expensive, so the statistical bound alone does not prove efficient learning.
Theorem 9.1.3
(Clean excess error under independent label flips)
For and , put
With probability at least over the corrupted sample,
Consequently, for , it suffices that
for clean excess error at most with probability at least . If , the minimum clean error is zero.
Proof
(Uniform deviation, then translate observed risk to clean risk)
For a fixed , the indicators are independent, lie in and have mean . The two-sided Hoeffding inequality and a union bound give
On the complementary event choose . The risk identity makes also a minimizer of . By empirical minimization and two uses of the uniform deviation bound,
Subtract and divide by the positive factor to obtain the clean-error bound. Substituting the displayed sample size ensures .
Proof X-ray
Where the noise penalty enters
The union bound controls noisy empirical errors uniformly, so it remains valid for a hypothesis selected after seeing the sample. The factor appears only when translating an observed-risk gap into a clean-risk gap. As approaches , this inverse factor magnifies the estimation error; the resulting squared factor in the sample bound is a sufficient upper bound for this method, not by itself a matching lower bound.
Worked example 9.1.4
(A concrete sample size)
For instance, with , , and , the displayed condition is ; suffices. This conservative distribution-free number is not the exact sample requirement for every class and distribution.
What happens at and beyond one half?
At , the observed label is an independent fair bit regardless of , so the identity becomes for every . The loss of information can be made exact.
Proposition 9.1.5
(No learning at noise rate one half)
Let the instance space be a single point, let the two possible targets be the constants zero and one, and let the noise rate be . For every learner, possibly randomized and using any number of independent corrupted examples, at least one of the two targets has the following property: the probability that the output has clean error less than is at most .
Proof
(Both targets generate the same data)
Under either target each observed label is an independent fair bit, so the whole sample has the same distribution, and so does the learner's output. To have clean error less than the learner must predict the correct constant at the single point. If it outputs zero with probability , its success probabilities under the two targets are and , and at least one of them is at most . This remains true for a randomized learner and arbitrarily many samples.
If is known, the ordering is reversed rather than erased. Flipping every observed label changes the noise rate to , after which the preceding analysis applies. If the noise rate and target are both unknown, one cannot simply assume the same direction of ordering. The threshold is a property of the stated label-flip model, not a universal boundary for all noisy learning settings.
Worked example 9.1.6
(A known noise rate above one half)
Suppose the noise rate is known and a classifier has clean error . Before any flipping, its observed error is , while the target itself has observed error : the ordering is reversed. After the learner flips every received label the noise rate is and the same classifier has observed error , which agrees with . Empirical risk minimization on the flipped labels now prefers clean-better hypotheses. A learner that did not know whether was or could not choose the direction, which is why the unknown case is excluded.
Counterexample mode
Arbitrary mislabeling can reverse the preference
Let with uniform and clean target everywhere. Suppose labels at are never flipped, while labels at are always flipped. The classifier has zero observed risk but clean error ; the target has observed risk and clean error zero. The constant independent-noise identity does not apply because flip probability depends on and exceeds one half at one point. Minimizing corrupted error can therefore prefer the wrong classifier.
Common mistake
(Insisting on zero training error)
A consistent-hypothesis learner designed for the noiseless setting breaks under noise: even the target is inconsistent with the sample once a single label is flipped. With and examples the probability that no label is flipped is , so such a learner rejects with probability about . Minimizing the empirical error, which tolerates a fraction of disagreements, is the repair.
Common mistake
(Reading an observed gap as a clean gap)
The theorem divides the observed gap by to obtain the clean gap. An observed-risk gap of at is a clean gap of . Forgetting the division understates the clean excess error by a factor of five.
Practice with solutions
Quick check
(With , calculate observed error when clean error is . Recover clean error from observed error under the same model.)
Use in both directions.
Solution · Answer
. Conversely .
Quick check
(For , and , express the uniform radius for and give the resulting clean excess-error bound.)
Compute first.
Solution · Answer
and the theorem gives excess at most with probability at least .
Quick check
(Why can a learner not distinguish the two constant targets in the one-point example when , even with infinitely many independent samples?)
Compare the distribution of the data under the two targets.
Solution · Answer
Under either target each observed label is an independent fair bit; the entire data distribution is identical, so observing more data cannot distinguish the hypotheses. For any randomized prediction, the two success probabilities sum to one.
Quick check
(Suppose is known and labels are independently flipped at that constant rate. What happens if the learner flips every received label?)
Ask when the flipped label differs from .
Solution · Answer
The resulting label differs from exactly when the original noise bit is zero, with probability . Independence across examples is preserved, and the less-than-half analysis applies.