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

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.