3
$\begingroup$

It is often the case that the VC-dimension of a hypothesis class equals (or can be bounded above by) the number of parameters one needs to set in order to define each hypothesis in the class.

For instance, if $H$ is the class of axis aligned rectangles in $R^d$, then $VCdim(H) = 2d$ , which is equal to the number of parameters used to define a rectangle in $R^d$.

How do you understand such a phenomenon?

$\endgroup$

1 Answer 1

1
$\begingroup$

The intuition that VC-dimension is simply an instance of "parameter counting" is wrong.

Below is a famous counter-example. For any $t \in \mathbb{R}$ define a function $f_{t}$ taking values in $\{-1, +1\}$ as follows: \begin{align*} f_{t}(x) &= \begin{cases} +1 & \text{if }\sin(tx) \geq 0,\\ -1 & \text{if }\sin(tx) < 0. \end{cases} \end{align*}

Consider a concept (or hypothesis) class $$ \mathcal{C} = \{ f_{t} : t \in \mathbb{R} \}. $$

Then for any $d \in \mathbb{N}$ and any sample $x_{1}, \dots, x_{d} \in [-1, 1]$ the concept class $\mathcal{C}$ can achieve any labelling of the given sample. The key idea is that for large values of $t$ the function $\sin(tx)$ oscillates at a very high frequency. Since we are free to choose this frequency, any labeling of the sample $x_{1}, \dots, x_{d}$ is possible to achieve.

Hence, we have constructed a concept class of infinite VC-dimension which is parameterized with only one parameter.

$\endgroup$

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.