# VC Dimension of the support of a function

## 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.

## 1 Answer

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$$.

• 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. – Mr.Robot Feb 15 at 17:43