Page 64 - Understanding Machine Learning

The VC-Dimension
46

If someone can explain every phenomenon, his explanations are worthless.
This leads us directly to the definition of the VC dimension.
Definition 6.5 (VC-dimension). The VC-dimension of a hypothesis class H,
denoted VCdim(H), is the maximal size of a set C ⊂ X that can be shattered by H.If
H can shatter sets of arbitrarily large size we say that H has infinite VC-dimension.
A direct consequence of Corollary 6.4 is therefore:
Theorem 6.6. Let H be a class of infinite VC-dimension. Then, H is not PAC
learnable.
Proof. Since H has an infinite VC-dimension, for any training set size m, there exists
a shattered set of size 2m, and the claim follows by Corollary 6.4.

We shall see later in this chapter that the converse is also true: A finite VC-
dimension guarantees learnability. Hence, the VC-dimension characterizes PAC
learnability. But before delving into more theory, we first show several examples.

6.3 EXAMPLES
In this section we calculate the VC-dimension of several hypothesis classes. To show
that VCdim(H) = d we need to show that
1. There exists a set C of size d that is shattered by H.
2. Every set C of size d + 1 is not shattered by H.

6.3.1 Threshold Functions
Let H be the class of threshold functions over R. Recall Example 6.2, where we have
shown that for an arbitrary set C ={c 1 }, H shatters C; therefore VCdim(H) ≥ 1. We
have also shown that for an arbitrary set C ={c 1 ,c 2 } where c 1 ≤ c 2 , H does not
shatter C. We therefore conclude that VCdim(H) = 1.

6.3.2 Intervals
Let H be the class of intervals over R, namely, H ={h a,b : a,b ∈ R,a < b},where h a,b :
R →{0,1} is a function such that h a,b (x) = 1 [x∈(a,b)] .Takethe set C ={1,2}. Then, H
shatters C (make sure you understand why) and therefore VCdim(H) ≥ 2. Now take
an arbitrary set C ={c 1 ,c 2 ,c 3 } and assume without loss of generality that c 1 ≤ c 2 ≤ c 3 .
Then, the labeling (1,0,1) cannot be obtained by an interval and therefore H does
not shatter C. We therefore conclude that VCdim(H) = 2.

6.3.3 Axis Aligned Rectangles
Let H be the class of axis aligned rectangles, formally:

H ={h (a 1 ,a 2 ,b 1 ,b 2 ) : a 1 ≤ a 2 and b 1 ≤ b 2 }