Understanding Machine Learning: From Theory to Algorithms

80 The VC-Dimension

As inHdcon, the empty conjunction is interpreted as the all-positive hy-

pothesis. We augmentHdmconwith the all-negative hypothesish−. Show

that VCdim(Hdmcon) =d.

7. We have shown that for a finite hypothesis classH, VCdim(H)≤blog(|H|)c.
   However, this is just an upper bound. The VC-dimension of a class can be
   much lower than that:
   
   
   1. Find an example of a classHof functions over the real intervalX= [0,1]
      such thatHis infinite while VCdim(H) = 1.
   
   
   2. Give an example of a finite hypothesis classHover the domainX= [0,1],
      where VCdim(H) =blog 2 (|H|)c.
      8.(*)It is often the case that the VC-dimension of a hypothesis class equals (or
      can be bounded above by) the number of parameters one needs to set in order
      to define each hypothesis in the class. For instance, ifHis the class of axis
      aligned rectangles inRd, then VCdim(H) = 2d, which is equal to the number
      of parameters used to define a rectangle inRd. Here is an example that shows
      that this is not always the case. We will see that a hypothesis class might
      be very complex and even not learnable, although it has a small number of
      parameters.
      Consider the domainX=R, and the hypothesis class
   
   
   
   

H={x7→dsin(θx)e:θ∈R}

(here, we taked− 1 e= 0). Prove that VCdim(H) =∞.

Hint: There is more than one way to prove the required result. One option

is by applying the following lemma: If 0.x 1 x 2 x 3 ..., is the binary expansion of

x∈(0,1), then for any natural numberm,dsin(2mπx)e= (1−xm), provided

that∃k≥ms.t.xk= 1.

9. LetHbe the class of signed intervals, that is,
   H={ha,b,s:a≤b,s∈{− 1 , 1 }}where

ha,b,s(x) =

{

s ifx∈[a,b]

−s ifx /∈[a,b]

Calculate VCdim(H).

10. LetHbe a class of functions fromXto{ 0 , 1 }.
    
    
    1. Prove that if VCdim(H)≥d, for anyd, then for some probability distri-
       butionDoverX ×{ 0 , 1 }, for every sample size,m,
    
    
    
    

E

S∼Dm

[LD(A(S))]≥min

h∈H

LD(h) +

d−m

2 d

Hint: Use Exercise 3 in Chapter 5.

2. Prove that for everyHthat is PAC learnable, VCdim(H)<∞. (Note that
   this is the implication 3→6 in Theorem 6.7.)
   11.VC of union:LetH 1 ,...,Hrbe hypothesis classes over some fixed domain
   setX. Letd= maxiVCdim(Hi) and assume for simplicity thatd≥3.