2
$\begingroup$

Let $C\subseteq 2^X$ be a concept class over $X$ and let $\bar{C}:=\{X\setminus c\mid c\in C\}$ be the complement. Show that $VCdim(C)=VCdim(\bar{C})$.

Proof:

Let $d:=VC_{dim}(C)$, then there exists $S\subseteq X$, $|S|=d$, s.t. $S$ is shattered by $C$.

Let $d':=VC_{dim}(\bar{C})$, then there exists $S'\subseteq X$, $|S'|=d'$, s.t. $S'$ is shattered by $C$.

Show that $d\leq d'$ and $d' \leq d$. I know that a set $S$ is shattered by $C$ iff $\Pi_C(S):=\{c\cap S\mid c\in C\}=2^S$, but I have no clue how to show the two sides. Can someone help me with that?

$\endgroup$
1
$\begingroup$

First, observe that it is enough to prove that $d\le d'$. Then, the converse inequality follows from the fact that $\overline{\overline{C}}=C$, and by applying the initial argument to $\overline{C}$.

To prove the claim, we actually prove something stronger: we prove that if $C$ shatters $S$, then $\overline{C}$ also shatters $S$.

Let $S$ be a set that is shattered by $C$, and consider $\Pi_{\overline{C}}(S)$. Let $T\subseteq S$, then there exists $c\in C$ such that $c\cap S=S\setminus T$ (since every subset of $S$ can be reached this way). Let $c'=X\setminus c\in \overline{C}$, then $c'\cup c=X$. Thus, $c'\cap S=T$. Therefore, $\Pi_{C}(S)\subseteq\Pi_{\overline{C}}(S)$. Applying the same argument to $\overline{C}$, we get $\Pi_{\overline{C}}(S)\subseteq \Pi_{\overline{\overline{C}}}(S)=\Pi_{C}(S)$, and thus we have the equality we wanted, and we conclude the claim.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.