I'm new here on the site, I'm a final year student in computer science. In a machine learning course, there was a question on a test that I could not understand.

The question goes like this:

Suppose that $ F\subseteq\{0,1\}^\Omega $ is some collection of Boolean functions over $\Omega $.

Define $\Omega'=\Omega\times\{0,1\}$ and define $F'$ to be the collection of Boolean functions over $\Omega$ as follows:

for every $f\in F$, there is some $f'\in F'$ that maps $(x,y)\in\Omega'$ to $1[f(x)\neq y]$.
(Furthermore, $F'$ consists only of such $f'$; no other functions are allowed.)

Prove that the VC-dimensions of $F$ and $F'$ are equal.

What I was able to understand is that there is a collection of some functions $F$, and that all these functions with the addition of $0$ and $1$ are also in $F '$

I think $F '$is like $F$ only if an addition of $0$ and $1$ to the functions.

Can't figure out how to prove it.


1 Answer 1


Every $f \in F$ is mapped to $f' \in F'$ defined as follows: $f'|_{\Omega \times \{0\}} = f$ and $f'|_{\Omega \times \{1\}} = 1 - f$.

Let us call a subset of $\Omega'$ mixed if it contains both $(\omega,0)$ and $(\omega,1)$ for some $\omega \in \Omega$.

For $S' \subseteq \Omega'$, let $S'|_{\Omega} = \{ \omega \in \Omega : (\omega,0) \in S' \text{ or } (\omega,1) \in S' \}$.

For all $S \subseteq \Omega$, the set $S' = S \times \{0\}$ is not mixed and satisfies $S'|_{\Omega} = S$.

The proof is a combination of two simple observations:

  1. $F'$ doesn't shatter any mixed set.
  2. If $S'$ is not mixed then $F'$ shatters $S'$ iff $F$ shatters $S'|_{\Omega}$.
  • $\begingroup$ Thanks for the help, can you please explain to me this part: $f'|_{\Omega \times \{1\}} = 1 - f$ It is not clear to me how you got this connection between the 2 collections $\endgroup$
    – hah
    Commented Oct 20, 2021 at 18:57
  • 2
    $\begingroup$ This is not supposed to be a complete answer. You'll have to flesh it out. $\endgroup$ Commented Oct 20, 2021 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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