# VC-dimension of the class of hypotheses that assign label $1$ to exactly $k$ points of some finite domain $\mathcal{X}$

Let $$\mathcal{X}$$ be a finite domain and $$k$$ a number such that $$k\leq|\mathcal{X}|$$. Consider the hypothesis class

$$\mathcal{H}:=\big\{h:|\{\mathbf{x}\in\mathcal{X}:h(\mathbf{x})=1\}|=k\bigr\}$$;

that is, the class of hypotheses $$h:\mathcal{X}\to\{0,1\}$$ that assign label $$1$$ to exactly $$k$$ elements of $$\mathcal{X}$$.

Question: What is the VC-dimension of $$\mathcal{H}$$?

(Note that this is Exercise 6.2 (1) in the book "Understanding Machine Learning: From Theory to Algorithms" from Shalev-Shwartz & Ben-David.)

The claim is that $$\mathrm{VCdim}(\mathcal{H})=\min\{k,|\mathcal{X}|-k\}$$. The solution that was provided to me proceeds as follows:

1. Show that $$\mathrm{VCdim}(\mathcal{H})\leq\min\{k,|\mathcal{X}|-k\}$$.
2. Show that $$\mathrm{VCdim}(\mathcal{H})\geq\min\{k,|\mathcal{X}|-k\}$$.

I'm already struggling with the first part. Let $$C\subseteq\mathcal{X}$$ be a set of size $$k+1$$. Then, $$C$$ is not shattered by $$\mathcal{H}$$ as there is no $$h\in\mathcal{H}$$ satisfying $$h(\mathbf{x})=1$$ for all $$\mathbf{x}\in C$$ $$\Rightarrow\;\mathrm{VCdim}(\mathcal{H})\leq k$$. On the other hand, if $$C\subseteq\mathcal{X}$$ is of size $$|\mathcal{X}|-k+1$$, then $$C$$ is not shattered by $$\mathcal{H}$$ as there is no $$h\in\mathcal{H}$$ satisfying $$h(\mathbf{x})=0$$ for all $$\mathbf{x}\in C$$. Hence, $$\mathrm{VCdim}(\mathcal{H})\leq\min\{k,|\mathcal{X}|-k\}$$.

I don't see why the second step in this line of reasoning is true. For example, consider some domain of cardinality $$|\mathcal{X}|=4$$ and let $$k=3$$. Then, $$|\mathcal{X}|-k+1=2$$. So when I pick any $$2$$ instances from $$\mathcal{X}$$ so that $$C=\{\mathbf{x}_1,\mathbf{x}_2\}$$, why is there no $$h\in\mathcal{H}$$ satisfying $$h(\mathbf{x}_1)=h(\mathbf{x}_2)=0$$? In my opinion, as $$2, this is actually the only possible labeling.

I am convinced the general claim is correct but I believe the proof of the upper bound in the form above is incomplete. Or did I completely misunderstand the problem setting?

In your example, there is no such $$h$$. Every $$h$$ assigns 1 to three elements of the four, so can only assign 0 to one element.

• This is the obvious part to me. If $C\subseteq\mathcal{X}$ is of size $k+1$, then there must be at least one element that is labeled as 0 $\Rightarrow\,\mathrm{VCdim}(\mathcal{H})\leq k$. Next step is to show that also $\mathrm{VCdim}(\mathcal{H})\leq |\mathcal{X}|-k$. So in the proof that I found it is argued that if $C\subseteq\mathcal{X}$ is of size $|\mathcal{X}|-k+1$ that no $h\in\mathcal{H}$ exists that assigns label $0$ to every $\mathbf{x}\in C$. This is what my example is about. It shows there is such $h$ (maybe it is just a typo in the proof that I found, I don't know).
– VK88
Jan 17 at 8:44
• @VK88 my answer is addressing the $|\mathcal{X}|-k$ case. There is no such $h\in \mathcal{H}$. Perhaps being more concrete will help: in your example, you wanted $h(x_1)=h(x_2)=0$; what values do you propose for $h(x_3)$ and $h(x_4)$? Remember you had $|\mathcal{X}|=4$ and $k=3$. Jan 17 at 12:13
• In case $|\mathcal{X}|=4$ and $k=3$, any set $C\subseteq\mathcal{X}$ of size $|\mathcal{X}|-k+1$ has only two elements $x_1$ and $x_2$. Hence, the labeling $h(x_1)=h(x_2)=1$ is not possible by any $h\in\mathcal{H}$, which is why $C$ is not shattered. But this is in contrast to the claim in the proof that I found that says there is no $h\in\mathcal{H}$ satisfying $h(x_1)=h(x_2)=0$. The latter is in my opinion the only labeling that is possible for this two element set. But maybe this is just a typo and they meant $=1$ instead $=0$.
– VK88
Jan 17 at 20:22
• @VK88 I think $h(x_1)=h(x_2)=1$ is possible, with $h(x_3)=1$ and $h(x_4)=0$. But $h(x_1)=h(x_2)=0$ is not possible. ? Jan 17 at 21:10
• Oh, the penny has dropped! Of course, $h:\mathcal{X}\to\{0,1\}$ not $C\to\{0,1\}$. I've confused $\mathcal{H}$ with $\mathcal{H}_C$, where the latter is the restriction of $\mathcal{H}$ to $C$. The definition of shattering I'm aware of is "A class $\mathcal{H}$ shatters a finite set $C\subset\mathcal{X}$ if the restriction of $\mathcal{H}$ to $C$ is the set of all functions from $C$ to $\{0,1\}$ (book of Shalev-Schwartz & Ben-David). But the line of reasoning in my original post refers directly to $\mathcal{H}$ instead of $\mathcal{H}_C$. Thanks a lot for helping me out!
– VK88
Jan 18 at 22:07