Page 368 - Understanding Machine Learning

Proof of the Fundamental Theorem of Learning Theory
350

i.i.d. instances from X with labels according to c we have that any ERM hypothesis
has a true error of at most
.
c
Proof. Define the class H ={c h : h ∈ H},where c h = (h \ c) ∪ (c \ h). It is
c
easy to verify that if some A ⊂ X is shattered by H then it is also shattered by H
c
and vice versa. Hence, VCdim(H) = VCdim(H ). Therefore, using Theorem 28.3
c
we know that with probability of at least 1 − δ, the sample S is an
-net for H .
Note that L D (h) = D(h c). Therefore, for any h ∈ H with L D (h) ≥
we have that

|(h c)∩S| > 0, which implies that h cannot be an ERM hypothesis, which concludes
our proof.