6. In this problem, we will get bounds on the VC-dimension of the class of (closed)...

Transcribed Image Text:

6. In this problem, we will get bounds on the VC-dimension of the class of (closed) balls in Rd, that is, where Bd = {Bvr : v Rd, r > 0}, 1 if ||xv||r Bv.r(x) = 0 - otherwise 1. Consider the mapping : Rd Rd+1 defined by (x) xm are shattered by Bd then (x1), ..., . . ., =(x, ||x||2). Show (xm) are shattered that if x1, by the class of halfspaces in Rd+1 (in this question we assume that sign(0) = 1). What does this tell us about VCdim(Ba)? 2. (*) Find a set of d+1 points in Rd that is shattered by Bd. Conclude that d+1 VCdim(Ba) d +2. 6. In this problem, we will get bounds on the VC-dimension of the class of (closed) balls in Rd, that is, where Bd = {Bvr : v Rd, r > 0}, 1 if ||xv||r Bv.r(x) = 0 - otherwise 1. Consider the mapping : Rd Rd+1 defined by (x) xm are shattered by Bd then (x1), ..., . . ., =(x, ||x||2). Show (xm) are shattered that if x1, by the class of halfspaces in Rd+1 (in this question we assume that sign(0) = 1). What does this tell us about VCdim(Ba)? 2. (*) Find a set of d+1 points in Rd that is shattered by Bd. Conclude that d+1 VCdim(Ba) d +2.