VC Dimension — Hao Wu

Let $(S, R)$ be a set system, where $S$ is a set and $R$ is a collection of subsets in $S$ .

Definition. Given $(S, R)$ , $X \subset S$ is shattered by $R$ if,
$\forall X' \subset X,\, \exists R' \in R,\, \text{ such that } X' = S \cap R'.$

Definition. The VC dimension of $(S, R)$ is the maximum cardinality of some $X \subset S$ that is shattered by $R$ .

Note: If we view $(S, R)$ as a classification problem, i.e., $S$ is a set of points and $R$ a set of functions, the VC dimension $d$ is the maximum size of a subset $X$ in which $R$ could separate arbitrary set points from the rest. In some sense, it measures how complex a separation plane $R$ could form.

Definition. Given a nonnegative integer $n$ and $d$ , we define $\binom{n}{\le d} = \sum_{i = 0}^{d} \binom{n}{i}$

Lemma. If $(S, R)$ has $VC$ dimension $d$ , then $|R| \le \binom{n}{\le d}$ , where $|S| = n$ .

Proof. Let $X \subset S$ be the set that has size $d$ and is shattered by $R$ . Define $R|X$ as $\{R' \cap X | R' \in R \}$ . It is obvious that $(X, R|X)$ has VC dimension $d$ . Also, the number of subset of $X$ is given by

2^d = \binom{d}{\le d} = |\ R|X\ |

Now we will show this lemma by induction. Label the elements in $S - X$ in arbitrary order as $\{ x_{d + 1}, x_{d + 2}, ..., x_{n} \}$ . Define $X_i$ = $X \cup \{x_{d+1}, x_{d + 2}, ..., x_{d+i} \}$ for $0 \le i \le n - d$ , where $X_0 = X$ . So $|X_i| = d + i$ . We will show that $|R | X_i| \le \binom{d + i} {\le d}$ holds.

Suppose the assumption holds for $R|X_i$ , now consider $R|X_{i + 1}$ . The elements $r$ in $R|X_{i}$ can be divided into

$D_1 = \{ r | r \in R | X_{i + 1}, r \cup x_{d + 1} \in R|X_{i + 1} \}$ .
$D_2 = \{ r | r \notin R | X_{i + 1}, r \cup x_{d + 1} \in R|X_{i + 1} \}$ .
$D_2 = \{ r | r \in R | X_{i + 1}, r \cup x_{d + 1} \notin R|X_{i + 1} \}$ .

We can verify that $|R|X_i | = |D_1| + |D_2| + |D_3|$ , $|R|X_{i + 1}| = 2|D_1| + |D_2| + |D_3|$ .

We show that $|D_1| \le \binom{d + i}{\le d - 1}$ . This is because the VC dimension of $(X_i, D_1)$ is at most $d - 1$ . Otherwise, suppose $Y \subset X_i$ is shattered by $D_1$ and $|Y| = d$ . It is apparent $Y \cup x_{d + 1}$ is shattered by $R|X_{i + 1}$ in $X_{i + 1}$ . A contradiction.

Therefore,

\begin{aligned} |R | X_{i + 1}| & = |D_1| + |R | X_{i}| \\ & \le \binom{d + i}{\le d - 1} + \binom{d + i}{\le d} \\ & = \sum_{j = 0}^{d - 1} \binom{d + i}{j} + \sum_{j = 0}^{d}\binom{d +i}{j} \\ & = \sum_{j = 1}^{d} \binom{d + i}{j - 1} + \sum_{j = 1}^{d}\binom{d +i}{j} + \binom{d + i}{0} \\ & = \sum_{j = 1}^d \binom{d + i + 1}{j} + \binom{d + i +1}{0} \\ & = \sum_{j = 0}^d \binom{d + i + 1}{j} \\ & = \binom{d + i + 1}{\le d}. \end{aligned}