Definition of shattering: video

Definition of VC dimension

the VC dimension (for Vapnik–Chervonenkis dimension) is a measure of the capacity (complexity, expressive power, richness, or flexibility) of a space of functions that can be learned by a statistical classification algorithm. It is defined as the cardinality of the largest set of points that the algorithm can shatter.

In $n$-dimensions, the VC dimension of the set of all linear classifiers is $n+1$

See also Probably approximately correct, Learning theory,

Applied for PAC learning with infinite concept classes

VC dimension is about the following.

You have a bunch of properties, like "being a policeman", "liking pineapple toppings on pizza", etc

And you want to estimate the fraction of people with each property in large population, from a single sample.

VC dimension tells you how much larger then sample needs to be, compared to when you are only estimating the fraction of people for a single property.

If all the properties are very decorrelated, it's about {number of properties} times what you needed before, but if they are correlated it can be much less, and that's what VC dimension measures

...........

See Probably approximately correct for context.

What happens when $H$ or $C$ is infinite?

Let $S \subseteq X$, define $\Pi_C(S) = \{c_S \mid c \in C\}$ (i.e. the concept class of concepts in $C$, but restricted to the subset of $X$, $S$. The size of $\Pi_C$ $\leq 2^m$, where $m$ is the size of $S$.

This is used to define a measure of concept class complexity: VC dimension (Vapnik-Chervonenkis):

We say $S \subseteq X$ is shattered by $C$, if $|\Pi_C(S)| = 2^{|S|}$

VC dimension of $C$ is the cardinality of the largest set shattered by $C$ (If $C$ shatters arbitrarily large sets, VC-dim is $\infty$).

intervals

$X=\mathbb{R}$

$C$ is intervals over $\mathbb{R}$, where $x$ in intervals are assigned $1$ and those outside $0$.

Can have interval that assigns anything to 1, and 2 points, but not for 3 points (+-+). This implies that the VC dimension of the class of intervals is 2.

rectangles

there is a set of 4 points that can be shattered by rectangles. However, there is no set of 5 points that is shattered by rectangles, because there is always a point within the extreme left, right, top, bottom.

Linear halfspaces or LTF (Linear threshold functions)

Like Support vector machines.

VC dimension is n+1 for n dimensional space, (in 2 dimensions, it is 3).

https://www.wikiwand.com/en/VC_dimension

https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma ; shows that for sets with finite number of elements, one can bound the cardinality of a family of sets with a finite VC dimension

Symmetrization argument