If we have $f:\mathbb{R} \rightarrow \{\pm 1\}$, and $\mathcal{F}$ and $\mathcal{F}'$, what are the VC dimensions of

$\mathcal{F} = \{sign(\prod_{i=1}^n (x-\theta_i), \forall a_i \in \mathbb{R} \}$

$\mathcal{F}' = \cup_{n=1}^n \mathcal{F}$

I think VC dimesion of $\mathcal{F}$ is $n$ and $\mathcal{F}'$ is infinity

For $\mathcal{F}$, we know that it is in 1D, and expanding the polynimals in makes it possible to separate the points with a large polynomial

For $\mathcal{F}'$ taking the union will add at least one in each increment, and there are infinite functions. Thus infinity.

Do I have the right approach?

  • $\begingroup$ If you can prove your claims, then you have the right approach. Have you tried that? $\endgroup$ – Yuval Filmus Apr 30 '20 at 7:23

Your Answer

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

Browse other questions tagged or ask your own question.