1
$\begingroup$

Let $\chi$ be an instance space and $H \in \{0, 1\}^\chi$ a class with finite VC-dimension. For each $x \in X$ we consider $z_x\colon H \rightarrow \{0, 1\}$ s.t. $z_x(h) = h(x), \forall h \in H$.

Let $Z = \{z_x:H\rightarrow\{0,1\}\mid x\in\chi\}$. Is $\mathit{VCdim}(Z)<2^{\mathit{VCdim}(H)+1}$?


The only thing that comes to mind when seeing this is the Sauer lemma, but that's related to the growth function and I don't see how to apply it here. Anyone got any idea on how to approach this?

$\endgroup$
1
$\begingroup$

This is a classical result of Assouad (Densité et dimension) about dual VC dimension.

Let $A$ be a binary matrix. The VC dimension of $A$ is the maximal size of a set $S$ of columns which are shattered, that is, all possible rows appear when we restrict $A$ to the columns in $S$. The dual VC dimension of $A$ is the VC dimension of $A^T$, the transpose of $A$.

Suppose that $A^T$ has VC dimension $2^{d+1}$. Then there is a set $S$ of $2^{d+1}$ rows of $A$ such that when we restrict $A$ to this set of rows, we see all possible columns. If we number the rows using binary numbers of length $d+1$, then in particular we see the following columns: for each $i$, there is a column which contains the $i$'th bit of the row index. For example, if $d=1$ then we see the following columns: $$ \begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} $$ Therefore the VC dimension of $A$ is at least $d+1$.

If we take $d = \mathrm{VC}(A)$, then we deduce $\mathrm{VC}(A^T) < 2^{\mathrm{VC}(A)+1}$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.