VC dimension, growth functions, and classification sample complexity — Examples

If $s<t$, the midpoint $x=(s+t)\mathrm{/}2$ satisfies $h_s(x)=0$ and $h_t(x)=1$, so the functions $h_t$ are all distinct as $t$ varies over $\mathbb{R}$ and the class is infinite. For any single $x$, $t<x$ realizes label $0$ and $t=x$ realizes label $1$, so every one-point tuple is shattered.

For two distinct points $x<y$, the possible trace vectors are only $(0,0)$, $(1,0)$, and $(1,1)$ as the threshold passes from left to right; $(0,1)$ never occurs. If the two indexed points repeat, their labels always agree. Hence no two-point tuple is shattered, and $\mathrm{VCdim}(H_{\mathrm{t}\mathrm{h}})=1$.

For $m$ distinct points ordered $x_1<\cdots <x_m$, a threshold realizes exactly the $m+1$ vectors consisting of $k$ initial ones followed by $m-k$ zeros, for $0\le k\le m$. A tuple with only $r$ distinct points has at most $r+1\le m+1$ traces, while a distinct $m$-tuple attains $m+1$; for $m=0$ the unique empty trace is counted once. Thus ${\mathrm{\Pi }}_{H_{\mathrm{t}\mathrm{h}}}(m)=m+1$.

Fix $x_1<x_2$ and put $r=x_2-x_1>0$. The patterns $(0,0),(1,0),(0,1),(1,1)$ are realized respectively by $[x_1-2r,x_1-r]$ (strictly left of both points), $[x_1,x_1]$, $[x_2,x_2]$, and $[x_1,x_2]$. Thus the pair is shattered and the VC dimension is at least two.

For any three distinct ordered points, the labeling $(1,0,1)$ is impossible for an interval because containing $x_1$ and $x_3$ forces it to contain every point between them, including $x_2$. A repeated coordinate also prevents a tuple of length at least three from being shattered, since repeated instances receive the same label under every classifier. Hence no three-point indexed tuple is shattered and the VC dimension is exactly two.

On $m$ distinct ordered points, a nonempty interval has as its trace one contiguous block, and every such block is realized by the interval with those two sample endpoints. There are ${\sum }_{r=1}^m(m-r+1)=m(m+1)\mathrm{/}2$ such blocks; an interval outside the finite sample realizes the empty trace. For a tuple with $r\le m$ distinct points there are at most $1+r(r+1)\mathrm{/}2\le 1+m(m+1)\mathrm{/}2$ traces, while a distinct tuple attains that number. At $m=0$ the formula gives the single empty trace. Thus ${\mathrm{\Pi }}_{H_{\mathrm{i}\mathrm{n}\mathrm{t}}}(m)=1+m(m+1)\mathrm{/}2$.

The $p+1$ points $0,e_1,\dots ,e_p$ are shattered. Given arbitrary labels $y_0,\dots ,y_p\in \{0,1\}$, set $s_i=2y_i-1$, $b=s_0$, and $w_i=s_i-s_0$. The affine score $f(x)=w\cdot x+b$ then satisfies $f(0)=s_0$ and $f(e_i)=s_i$; since these values are $+1$ or $-1$, the rule $h(x)=\mathbf{1}\{f(x)\ge 0\}$ realizes exactly the chosen labels. Thus the VC dimension is at least $p+1$.

Take any $p+2$ indexed points $x_1,\dots ,x_{p+2}\in {\mathbb{R}}^p$. The augmented vectors $(x_i,1)\in {\mathbb{R}}^{p+1}$ form a list of $p+2$ vectors. If the list were linearly independent, [F4] would make its image a linearly independent set of $p+2$ distinct vectors, contradicting [F3]. [F3, F4] Hence the list is dependent, and [F5] gives real coefficients $a_i$, not all zero, with ${\sum }_i{a}_i(x_i,1)=0$, equivalently ${\sum }_i{a}_i{x}_i=0$ and ${\sum }_i{a}_i=0$. Both positive and negative coefficients occur. Label $x_i$ by $1$ when $a_i>0$ and by $0$ when $a_i<0$ (choose either label when $a_i=0$). If an affine score $f(x)=w\cdot x+b$ realized this labeling, then $a_{i}f(x_i)\ge 0$ for every positive coefficient and $a_{i}f(x_i)>0$ for every negative coefficient, because label $0$ means $f(x_i)<0$. Therefore ${\sum }_i{a}_{i}f(x_i)>0$, contradicting ${\sum }_i{a}_{i}f(x_i)=w\cdot {\sum }_i{a}_i{x}_i+b{\sum }_i{a}_i=0$. No $p+2$-tuple is shattered, so the VC dimension is at most $p+1$.

Steps 1.1 and 1.2 give matching lower and upper bounds, proving $\mathrm{VCdim}(H_p)=p+1$.

For distinct $a,b\in \mathbb{N}$, $h_a(a)=1$ and $h_b(a)=0$, so the classifiers $h_a$ are pairwise distinct and $H$ is infinite. For any single $a$, the zero function realizes label $0$ and $h_a$ realizes label $1$, so each one-point tuple is shattered.

For any two distinct points, no member of $H$ labels both points by $1$, so their $(1,1)$ pattern is absent; a repeated two-point tuple also cannot be shattered because both coordinates always agree. Thus no two-point tuple is shattered and $\mathrm{VCdim}(H)=1$.

On $m$ distinct natural numbers, the traces are the empty vector and the $m$ vectors with exactly one positive coordinate, so there are $m+1$. If a tuple repeats values, its trace is determined by its $r\le m$ distinct values and has at most $r+1\le m+1$ patterns. The empty tuple has one trace. Therefore ${\mathrm{\Pi }}_H(m)=m+1$ for every $m\ge 0$.