Understanding Machine Learning: From Theory to Algorithms

6.8 Exercises 79

2.Hat−most−k={h∈{ 0 , 1 }X:|{x:h(x) = 1}|≤kor|{x:h(x) = 0}|≤k}.

3. LetXbe the Boolean hypercube{ 0 , 1 }n. For a setI⊆{ 1 , 2 ,...,n}we define
   aparity functionhIas follows. On a binary vectorx= (x 1 ,x 2 ,...,xn)∈
   { 0 , 1 }n,

hI(x) =

(

∑

i∈I

xi

)

mod 2.

(That is,hIcomputes parity of bits inI.) What is the VC-dimension of the

class of all such parity functions,Hn-parity={hI : I⊆{ 1 , 2 ,...,n}}?

4. We proved Sauer’s lemma by proving that for every classHof finite VC-
   dimensiond, and every subsetAof the domain,

|HA|≤|{B⊆A : HshattersB}|≤

∑d

i=0

(

|A|

i

)

.

Show that there are cases in which the previous two inequalities are strict

(namely, the≤can be replaced by<) and cases in which they can be replaced

by equalities. Demonstrate all four combinations of = and<.

5.VC-dimension of axis aligned rectangles inRd:LetHdrecbe the class of
axis aligned rectangles inRd. We have already seen that VCdim(Hrec^2 ) = 4.
Prove that in general, VCdim(Hdrec) = 2d.

6.VC-dimension of Boolean conjunctions:LetHdconbe the class of Boolean
conjunctions over the variablesx 1 ,...,xd(d≥2). We already know that this
class is finite and thus (agnostic) PAC learnable. In this question we calculate
VCdim(Hdcon).

1. Show that|Hdcon|≤ 3 d+ 1.


2. Conclude that VCdim(H)≤dlog 3.


3. Show thatHdconshatters the set of unit vectors{ei:i≤d}.
   4.(**)Show that VCdim(Hdcon)≤d.
   Hint: Assume by contradiction that there exists a setC={c 1 ,...,cd+1}
   that is shattered byHdcon. Leth 1 ,...,hd+1be hypotheses inHdconthat
   satisfy

∀i,j∈[d+ 1], hi(cj) =

{

0 i=j

1 otherwise

For eachi∈[d+ 1],hi(or more accurately, the conjunction that corre-

sponds tohi) contains some literal`iwhich is false onciand true oncj

for eachj 6 =i. Use the Pigeonhole principle to show that there must be a

pairi < j≤d+ 1 such that`iand`juse the samexkand use that fact

to derive a contradiction to the requirements from the conjunctionshi,hj.

5. Consider the classHdmconof monotone Boolean conjunctions over{ 0 , 1 }d.
   Monotonicity here means that the conjunctions do not contain negations.