Past exam of the computer science course of the University of Oxford / 2015 / Computational learning theory / 1 / d

Expanding the squared Euclidean norm givesIn lifted coordinates $(z,t)=\Phi (x)=(x,\Vert x{\Vert }^2)$, this is the closed half-spaceEvery labelling of the original points obtainable by a Euclidean ball is therefore obtainable on their lifted images by an affine linear classifier. The feature map is injective, since it preserves the first $d$ coordinates; distinct original points remain distinct. If the original points are shattered, every labelling of the lifted points is realized, as required.

Here “linear separator” means a separator with an intercept, namely an affine hyperplane. If a convention demands strict separation on the finite sample, increase the constant term of the positive score $r^2-\Vert c{\Vert }^2+2c\cdot z-t$ by a sufficiently small positive amount. Positive points then have strictly positive score, and the finitely many negative scores remain strictly negative. A homogeneous separator can alternatively be obtained after adjoining one more constant coordinate; this distinction matters for dimension counts.

For $d\ge 1$, take the $d+1$ vertices $v_0,\dots ,v_d$ of a regular simplex in ${\mathbb{R}}^d$, centered at zero and scaled so that $\Vert v_j\Vert =1$. For example, realize them asin the $d$-dimensional vector subspace $\{z\in {\mathbb{R}}^{d+1}:{\sum }_j{z}_j=0\}$, identified isometrically with ${\mathbb{R}}^d$. These vertices are affinely independent.

Assign arbitrary desired signs $s_j\in \{-1,1\}$, positive for inclusion. Affine independence implies that there is an affine function $\ell (x)=a\cdot x+b$ with $\ell (v_j)=s_j$ for every $j$: the $d+1$ interpolation conditions form an invertible linear system. For a sufficiently small $\eta >0$, chooseAt every vertex,Thus the Euclidean ball contains exactly the positively labelled vertices, with none on its boundary. This construction also covers the all-positive and all-negative labellings. Therefore

An affine linear classifier in ${\mathbb{R}}^k$ has VC dimension $k+1$. The upper bound follows from the intersecting convex hull partition theorem: for any $k+2$ points, label the two parts oppositely. The two convex hulls cannot be strictly separated by an affine hyperplane, since they intersect. A weak boundary convention gives the same contradiction: an affine score is nonnegative on the positive convex hull and strictly negative on the negative convex hull. The lower bound comes from the $k+1$ affinely independent vertices of a simplex, because an affine score can interpolate arbitrary signs there.

Consequently, parts (i) and (ii) immediately giveThe one-sided orientation of the lifted separators permits the sharper, exact conclusionTo prove the remaining upper bound, take any $d+2$ distinct points and a nonzero affine dependence ${\lambda }_i$ as in part (c). Write $Q={\sum }_i{\lambda }_i\Vert x_i{\Vert }^2$. Reverse every coefficient if necessary so that $Q\ge 0$. Prescribe positive labels when ${\lambda }_i>0$ and negative labels when ${\lambda }_i<0$; zero coefficients may be labelled arbitrarily. If a Euclidean ball realized these labels, its score $g(x)=r^2-\Vert x-c{\Vert }^2$ would satisfyIndeed, every positive-coefficient term is nonnegative and every negative-coefficient term is strictly positive, with at least one of the latter. On the other hand, expanding the score and using the two affine dependence identities givesa contradiction. No $d+2$ points are shattered, completing the exact determination of the VC dimension of Euclidean balls. In the exceptional zero-dimensional Euclidean space, every positive-radius Euclidean ball is the whole singleton space, so the VC dimension is zero.