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

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.