1
$\begingroup$

I'm studying VC-dimension and sample complexity, and I'd like to understand whether I understand it correctly via the following example.

Let $X = \mathbb{R}$ and $\mathcal{H} = \{ h_{\theta}(x)=\text{sign}(x-\theta):\theta \in \mathbb{R}\}$. Assume $\text{sign}(z) = 1$ if $z\geq 0$

It's clear that e.g. $\{0\}$ is shattered, since for $\theta=1$, $h_{\theta}(0) = -1$ and for $\theta = -1$ we get $h_{\theta}(0) = +1$, so we represent all of the possible outcomes the point $0$ can be classified to. However for more than $1$ point it's not possible as we can have $(-,-)$, $(-,+)$, $(+,+)$ but we can't have $(+,-)$. So $VC(\mathcal{H}) = 1$.

Can I say that this is an example of an infinite hypothesis class with $\textbf{finite}$ sample complexity?

$\endgroup$

0

Your Answer

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