Understanding Machine Learning: From Theory to Algorithms

6.8 Exercises 81

1. Prove that
   VCdim (∪ri=1Hi)≤ 4 dlog(2d) + 2 log(r).

Hint: Take a set ofkexamples and assume that they are shattered by

the union class. Therefore, the union class can produce all 2kpossible

labelings on these examples. Use Sauer’s lemma to show that the union

class cannot produce more thanrkdlabelings. Therefore, 2k< rkd. Now

use Lemma A.2.

2.(*)Prove that forr= 2 it holds that

VCdim (H 1 ∪H 2 )≤ 2 d+ 1.

12.Dudley classes:In this question we discuss an algebraic framework for
defining concept classes overRnand show a connection between the VC
dimension of such classes and their algebraic properties. Given a function

f:Rn→Rwe define the corresponding function,POS(f)(x) = (^1) [f(x)>0]. For
a classFof real valued functions we define a corresponding class of functions
POS(F) ={POS(f) :f∈ F}. We say that a family,F, of real valued func-
tions islinearly closed if for allf,g∈ Fandr∈R, (f+rg)∈ F(where
addition and scalar multiplication of functions are defined point wise, namely,
for allx∈Rn, (f+rg)(x) =f(x) +rg(x)). Note that if a family of functions
is linearly closed then we can view it as a vector space over the reals. For a
functiong:Rn→Rand a family of functionsF, letF+gdef={f+g:f∈F}.
Hypothesis classes that have a representation asPOS(F+g) for some vector
space of functionsFand some functiongare calledDudley classes.

1. Show that for everyg:Rn→Rand every vector space of functionsFas
   defined earlier, VCdim(POS(F+g)) = VCdim(POS(F)).
   2.(**)For every linearly closed family of real valued functionsF, the VC-
   dimension of the corresponding classPOS(F) equals the linear dimension
   ofF(as a vector space).Hint: Letf 1 ,...,fdbe a basis for the vector space
   F. Consider the mappingx7→(f 1 (x),...,fd(x)) (fromRntoRd). Note
   that this mapping induces a matching between functions overRnof the
   formPOS(f) and homogeneous linear halfspaces inRd(the VC-dimension
   of the class of homogeneous linear halfspaces is analyzed in Chapter 9).


2. Show that each of the following classes can be represented as a Dudley
   class:
   
   
   1. The classHSnof halfspaces overRn(see Chapter 9).
   
   
   2. The classHHSnof all homogeneous halfspaces overRn(see Chapter 9).
   
   
   3. The classBdof all functions defined by (open) balls inRd. Use the
      Dudley representation to figure out the VC-dimension of this class.
   
   
   4. LetPnddenote the class of functions defined by polynomial inequalities
      of degree≤d, namely,
   
   
   
   

Pnd={hp:pis a polynomial of degree≤din the variablesx 1 ,...,xn},