5.7 VC-dimension of canonical hyperplanes. The objective of this problem is derive a bound on the VC-dimension of canonical hyperplanes that does not depend on the dimension of feature space. Let S  fx: kxk  rg. We will show that the VC-dimension d of the set of canonical hyperplanes fx 7! sgn(w
x) : minx2S jw

xj = 1 ^ kwk  g veries d  r22 : (5.51)

(a) Let fx1; : : : ; xdg be a set that can be shattered. Show that for all y = (y1; : : : ; yd) 2 f????1; +1gd, d  k Pd i=1 yixik.

(b) Use randomization over the labels y and Jensen's inequality to show that d  
qPd i=1 kxik2.

(c) Conclude that d  r22.