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

The hypothesis class $H$ shatters a set $S$ when it realizes every binary labelling of $S$: for every function $g:S\to \{0,1\}$ there is an $h\in H$ with $h{|}_S=g$. Identifying each classifier with its positive set, this sayswhere $\mathcal{P}(S)$ is the power set. Different labellings may require different members of the hypothesis class.

The VC dimension isIt is infinite if arbitrarily large finite sets are shattered. A hypothesis class has VC dimension zero when it shatters no one-point set; for a nonempty hypothesis class, the empty set is always shattered.

The shattering coefficient, also called the growth function of a hypothesis class, counts the largest number of labellings obtainable on $m$ inputs:When $X$ has at least $m$ points, the same value is obtained by maximizing $|\{h{|}_S:h\in H\}|$ over $m$-point sets $S$. Always ${\Pi }_H(m)\le 2^m$, with equality exactly when some $m$-point set is shattered.

The Sauer-Shelah lemma says that a hypothesis class of finite VC dimension $d$ satisfiesIn particular, for $m\ge d\ge 1$,Here the binomial coefficients count small subsets. One way to obtain the last inequality is to set $t=d/m\le 1$: since $t^j\ge t^d$ for $j\le d$,Thus finite VC dimension replaces the unrestricted exponential number of labellings by a polynomial bound in the sample size.

Fix an $m$-point set $S$. The restriction of an intersection $c_1\cap c_2$ to $S$ is determined by the ordered pair of restrictions $c_1{|}_S,c_2{|}_S$. Some pairs can yield the same intersection, so the growth function of a hypothesis class satisfiesAssume first that $d\ge 1$. If $12d$ points were shattered by $H_2$, the Sauer-Shelah lemma would implyBut $e<3$, so $(12e{)}^2<36^2=1296<4096=2^{12}$. Raising this strict inequality to the positive integer power $d$ gives a contradiction. No $12d$-point set can therefore be shattered; neither can any larger set, since shattering passes to subsets. ConsequentlyThe printed strict inequality needs $d\ge 1$. For example, on a nonempty domain let $H$ contain only the identically zero classifier. Then $\mathrm{VC}(H)=\mathrm{VC}(H_2)=0$, whereas the stated conclusion would require $0<0$. More generally, a nonempty hypothesis class of VC dimension zero has only one distinct labelling function, since two different functions would shatter a point on which they differ. Its self-intersection class also has VC dimension zero.

Choose distinct points $x_1,\dots ,x_{d+2}$ of $S$. The $d+2$ vectors $(x_i,1)$ lie in the $(d+1)$-dimensional vector space ${\mathbb{R}}^{d+1}$, so they are linearly dependent. Hence there are real numbers ${\lambda }_i$, not all zero, such thatThe second equality forces both a positive and a negative coefficient. Put $I_{+}=\{i:{\lambda }_i>0\}$, $I_{-}=\{i:{\lambda }_i<0\}$, andRearranging the first equality givesEach side is a convex combination: the coefficients are positive and sum to one. Thus $z$ belongs to both convex hulls. Place the points with indices in $I_{+}$ in $A$, those with indices in $I_{-}$ in $B$, and assign every zero-coefficient point and every remaining point of $S$ to $A$. Then $A,B$ are nonempty, disjoint, and have union $S$. Adding points cannot shrink a convex hull, soThis proves the intersecting convex hull partition theorem, including when $S$ has more than $d+2$ points or is infinite: only the initial finite collection was needed.

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.