0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Are you familiar with the definition of VC dimension? If not, you won't be able to solve questions about VC dimension. $\endgroup$
    – Yuval Filmus
    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$
    – Yuval Filmus
    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$
    – Yuval Filmus
    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

0

Reset to default

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.