# understanding machine learning VC-dim

understanding machine learning Shai-ben-David: chapter $6$ ex.$6.3$

pls, give me a hint to solve this question.

Let $X$ be the Boolean hypercube $\{0,1\}^n$. For a set $I \subseteq \{1,2,\dots, n\}$ we define a parity function $h_I$ as follows. On a binary vector $x = (x_1, x_2,\dots, x_n) \in \{0,1\}^n$, $$h_I(x)=({\sum_{x\in I}x_i})\mod 2$$

(That is, $h_I$ computes parity of bits in $I$.) What is the VC-dimension of the class of all such parity functions, $H_{n-parity} = \{h_I : I \subseteq \{1,2,..., n\}\}$?

Observe that $|H_{n\text{-parity}}| = 2^n$. Therefore, its VC-dimension is at most $\log_2|H_{n\text{-parity}}| = n$. To prove that the VC-dimension of $H_{n\text{-parity}}$ is exactly $n$. Consider the set $S$ which consists of $n$ base vectors; that is, each of the $n$ vectors contains exactly one $1$. The proof that $S$ can be shattered by $H_{n\text{-parity}}$ is left as an exercise.