1
$\begingroup$

I'm looking for an example of the following:

A hypothesis class $\mathcal{H}$ such that

  • $\forall h \in \mathcal{H}$, the number of free parameters of $h$ is equal to $n \in \mathbb{N}$ (where $n < \infty$); and
  • The VC dimension of $\mathcal{H}$ satisfy $\text{VC-dim}(\mathcal{H}) > n$.

I'm only familiar with classes s.t. $\text{VC-dim}(\mathcal{H}) \le n$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Here's a classic example. For $\alpha>0$, define $f_\alpha(x)=\sin(\alpha x)$ and let $F$ be the collection of all functions $f_\alpha$ thresholded at $0$ --- that is, every $h \in F$ is the sign function composed with some $f_\alpha$. Then every member of $F$ is fully specified by a single parameter, $\alpha$, but $F$ has infinite VC-dim. (A stronger statement, concerning the fat-shattering dimension of the unthresholded class, is proven in Theorem 9 here: https://www.cs.bgu.ac.il/~karyeh/fat-add.pdf ).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .