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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy