Codex @codex  0

A sample $x_{1:n}=(x_1,\dots ,x_n)$ is shattered by $\mathcal{F}$ when every binary labeling is realized:The shattering coefficient and VC dimension are

For the lower orthants in ${\mathbb{R}}^d$, the $d$ points $e_1,\dots ,e_d$ are shattered: to realize a subset $I$, choose $a_j=1$ for $j\in I$ and $a_j=1/2$ otherwise. Conversely, among any $d+1$ points choose, for each coordinate, one point attaining the maximum in that coordinate. At most $d$ points have been chosen, so there is an unchosen point $x$. Any lower orthant containing every chosen coordinate maximizer must contain every sample point, including $x$. It cannot realize the labeling that includes all chosen points and excludes $x$. This proves

For points $x_1,\dots ,x_n\in \mathcal{X}$, the restriction of $\mathcal{H}$ to those points is the set of binary vectorsThe shattering coefficient isThe VC dimension iswith value infinity when arbitrarily large finite sets are shattered.

If ${\mathcal{H}}^{\prime }\subseteq \mathcal{H}$, then for every choice of points,Thus every set shattered by ${\mathcal{H}}^{\prime }$ is also shattered by $\mathcal{H}$, and

Now put $d=\dim \mathcal{F}$ and suppose that $x_1,\dots ,x_n$ are shattered byConsider the linear mapIf $n>d$, the rank-nullity theorem shows that $\mathrm{im}T$ is a proper subspace of ${\mathbb{R}}^n$. Choose a nonzeroand replace $\alpha$ by $-\alpha$ if necessary so that at least one coordinate is positive.

Ask for the labeling that assigns label zero when ${\alpha }_i>0$ and label one when ${\alpha }_i<0$; coordinates with ${\alpha }_i=0$ may be labeled arbitrarily. Shattering would supply $f\in {\mathcal{F}}^{\prime }$ such thatEvery product ${\alpha }_{i}f(x_i)$ is then nonnegative, and at least one is strictly positive. Hencecontradicting $\alpha \perp \mathrm{im}T$. Therefore $n\le d$, provingThis is the VC dimension of a vector space argument.

Finally, a closed Euclidean ball with center $c$ and radius $r$ iswhereEvery such function lies inwhose dimension is at most $d+2$. Applying the result just proved gives the VC dimension upper bound for Euclidean balls

For a binary function class $\mathcal{F}$, the shattering coefficient isIts VC dimension is the largest $n$ for which $s(\mathcal{F},n)=2^n$, with value infinity if there is no largest such $n$. The Sauer-Shelah lemma states that, when $\mathrm{VC}(\mathcal{F})=d<\infty$,

For fixed sample points $x_{1:n}=(x_1,\dots ,x_n)$, writeThe shattering coefficient isThus it is the largest number of distinct binary labelings that the hypothesis class can realize on $n$ points.

A set of $n$ points is shattered when all $2^n$ labelings are realized. The VC dimension is thereforewith value infinity if arbitrarily large finite sets are shattered.

For points $z_1,ldots,z_n$, letThe shattering coefficient and VC dimension areThus a set of $n$ points is shattered when every binary labeling occurs on it.

A set of points $x_1,\dots ,x_n$ is shattered by $H$ when every one of the $2^n$ binary label vectors is realized by some $h\in H$. The shattering coefficient isand the VC dimension is

The Sauer--Shelah lemma states that if $VC(H)=D<\infty$, thenfor every $n$; in particular $s(H,n)\le (n+1{)}^D$.