Hello everyone I am new to the site, I have a question that was in the test and did not understand the parts that are in the question. This question from a test I failed to pass, in a machine learning course. the question:

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.

I think this is an easy question, but there are concepts and things I did not understand in the question itself. I tried to search for information on the internet but was unsuccessful

I did not understand it: what does this marking mean? $\Omega'=\Omega\times\{0,1\}$

I did not understand what x and y are, what do they mean? And what is the function with the number 1, what does this function do? $(x,y)\in\Omega'$ to $1[f(x)\neq y]$

Another question What is the VC dimension? Is it like a two-dimensional plane or a 3-dimensional space?

The question itself I think I will be able to solve only when I understand the question itself, I tried to understand the question, but I could not.

  • $\begingroup$ Are you familiar with the definition of VC dimension? If not, you won't be able to solve questions about VC dimension. $\endgroup$ Oct 23, 2021 at 21:41
  • $\begingroup$ The notation $\Omega \times \{0,1\}$ stands for the Cartesian product of sets. Once you understand what this means, you will know what $x,y$ are. $\endgroup$ Oct 23, 2021 at 21:41
  • $\begingroup$ The notation $1[B]$ stands for $1$ if $B$ holds and $0$ if $B$ doesn't hold. $\endgroup$ Oct 23, 2021 at 21:42
  • $\begingroup$ cs.stackexchange.com/q/144960/755 $\endgroup$
    – D.W.
    Oct 26, 2021 at 3:35
  • $\begingroup$ Please try to ask questions that will be useful to others, even if they are not looking at exactly the same exercise/question that you are. $\endgroup$
    – D.W.
    Oct 26, 2021 at 3:36


Your Answer

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