1
$\begingroup$

Problem

Let $\mathcal{X}$ be a finite set, the support of a binary function $f: \mathcal{X} \rightarrow \{0,1\}$ is defined as $supp(f)=\{x\in\mathcal{X}: f(x)=1\}$. For any $k\leq \vert \mathcal{X}\vert$, consider the function class $\mathcal{F}_k=\{f: \vert supp(f)\vert \leq k\}$. Find $VC(\mathcal{F}_k)$.

What I Have Done

The function class $\mathcal{F}_k$ is just all functions that predict no more than $k$ positive labels. In order to find VC dimension of $\mathcal{F}_k$, we need to find the largest restriction of $\mathcal{F}_k$ onto $\mathcal{X}$. Therefore, I have $$ \sum_{i=0}^k \binom{n}{i}=2^{VC(\mathcal{F}_k)} $$

However, I do not know how to compute LHS and it seems that it does not have closed form by this answer.

Could someone help me, thank you in advance.

$\endgroup$
1
$\begingroup$

Denote the function in $\mathcal{F}_k$ whose support is $X \subset \mathcal{X}$ by $f_X$. Now consider any $X \subset \mathcal{X}$ with $|X| \leq k$. For any $Y \subset X$, $supp(f_Y) = Y$. Thus $\mathcal F_k$ shatters $X$, meaning $VC(\mathcal{F}_k) \geq k$. Note that $\mathcal{F}_k$ cannot shatter any subset $X \subset \mathcal X$ of size $\geq k$, since its support covers at max $k$ points. Hence $VC(\mathcal F_k) = k$.

I don't understand your argument; the expression you wrote would be true if $n$ (which is not defined) was replaced by $k$, in which case the equation simplifies to $VC(\mathcal F_k) = k$.

$\endgroup$
  • $\begingroup$ Welcome to this site and thank you for your help. I previously thought that $n$ in my description should be $\vert \mathcal{X}\vert$ and the LHS specifies all possible label configurations, but I just realized that $n$ actually should be $k$ since the function class $\mathcal{F}_k$ could give at most $k$ positive labels and the other $\vert \mathcal{X}\vert - k$ are all predicted 0. $\endgroup$ – Mr.Robot Feb 15 at 17:43

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.