Shattering coefficient ($s(\mathcal{H},n)$)

The shattering coefficient is

// The existing Shattering coefficient article supplies the definition.

For binary hypothesis classes,because the label vectors realized by the union form the union of the two sets of realized label vectors.

The VC dimension is the largest number of points on which a binary hypothesis class realizes every possible labeling.

The positive-radius closed Euclidean balls in ${\mathbb{R}}^d$ have VC dimension $d+1$ for $d\ge 1$. Vertices of a regular simplex are shattered: interpolate any desired signs by an affine function $a\cdot x+b$, then perturb a sphere through the vertices to the score $1+\eta b+\eta a\cdot x-\Vert x{\Vert }^2$. For the upper bound, take an affine dependence $\lambda$ among $d+2$ points and orient it so that $Q={\sum }_i{\lambda }_i\Vert x_i{\Vert }^2\ge 0$. Labelling the positive coefficients inside and the negative coefficients outside would force ${\sum }_i{\lambda }_i(r^2-\Vert x_i-c{\Vert }^2)>0$, while the affine dependence makes this sum equal $-Q\le 0$. The weaker $d+2$ upper bound from unrestricted lifted affine linear classifiers loses their fixed quadratic coefficient.

If $VC(H)=D<\infty$, then $s(H,n)\le {\sum }_{j=0}^D\left(\genfrac{}{}{0ex}{}{n}{j}\right)$.

If no $k$-set were shattered, the Sauer-Shelah lemma would bound the number of traces by ${\sum }_{i<k}\left(\genfrac{}{}{0ex}{}{2k}{i}\right)=(2^{2k}-(\genfrac{}{}{0ex}{}{2k}{k}))/2<2^{2k-1}$. This strict middle-layer gap contradicts the displayed lower bound. Therefore a family with such traces at every even size has unbounded finite VC dimension.

The elementary estimate ${\sum }_{j=0}^D\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le (n+1{)}^D$ converts finite VC dimension into a polynomial bound on the number of sample labelings.

The class of lower orthants ${\prod }_{j=1}^p(-\infty ,a_j]$ in ${\mathbb{R}}^p$ has VC dimension at most $p$. Among any $p+1$ points, choose a coordinate maximizer for each of the $p$ coordinates. A remaining point cannot be excluded while all those maximizers are included.

Indicators of real intervals have VC dimension two: two ordered points can be labeled arbitrarily, while an interval containing the two outer points of a triple must contain the middle point.

For a target positive set consisting of two disjoint intervals of total probability $p$, choosing its heavier component has misclassification risk at most $p/2$. Choosing the spanning interval has misclassification risk at most $1-p$. The smaller bound is at most $1/3$. The constant is sharp: on three ordered atoms with equal masses and labels $1,0,1$, every single interval makes a mistake on at least one atom. Together with the VC uniform convergence theorem, this gives weak PAC learning using an interval hypothesis class.

Intervals together with their label complements shatter three ordered points, but cannot realize an alternating labeling on four, so their VC dimension is three.