0
$\begingroup$

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<k=3$, 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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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). $\endgroup$
    – VK88
    Jan 17 at 8:44
  • $\begingroup$ @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$. $\endgroup$
    – Ben Reiniger ♦
    Jan 17 at 12:13
  • $\begingroup$ 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$. $\endgroup$
    – VK88
    Jan 17 at 20:22
  • $\begingroup$ @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. ? $\endgroup$
    – Ben Reiniger ♦
    Jan 17 at 21:10
  • 1
    $\begingroup$ 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! $\endgroup$
    – VK88
    Jan 18 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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