3
$\begingroup$

I am having some trouble understanding the notion of the VC dimension. The definition I have is the following:

The VC dimension of a set of hypothesis functions $H$ is the cardinality of the largest set which $H$ can shatter. We say that $H$ shatters some set $S \subseteq \mathcal{X}$ if we can realise any labelings on $S$ using functions from $H$.

To me, this means that for any (countable) set of labels $L \subseteq \mathbb{Z}$, there is some $h \in H$ that provides a surjection $h: S \mapsto T$, where $T \subseteq \mathcal{X}$ with $|T| = |L| \leq |S|$. (There is then a trivial bijection from $T$ to $L$.)

Is this the correct interpretation?

The reason I ask is because the above interpretation leads me to think that the singleton set $H = \{h\}$ has $VC(H) = 1$, since it always sends a single point to a single point, so we can get any labelling we like on this single point by a trivial bijection.

That is, suppose we wanted to label the point $x \in \mathbb{R}$ as $l$, then $h: y \in \mathbb{R} \mapsto 0$ will do since we can just change the name of 0 to $l$. Note that this chosen $h$ does not shatter a two-set from $\mathbb{R}$, since we can only label the points in one distinct way.

However, I have read that the VC of a singleton is 0. I don't understand this.

(I see hypothesis functions $g: \mathcal{X} \to \{1, \dots, n\}$ as belonging to an equivalence class of functions that sends $\mathcal{X}$ to any set of size $n$. Please correct me if this is the wrong intuition.)

$\endgroup$
4
$\begingroup$

A family of hypothesis functions on domain $\cal X$ is a subset of $\{0,1\}^{\cal X}$. A family $H$ shatters a set $S \subseteq \cal X$ if for every subset $T \subseteq S$ there exists a function $h \in H$ such that $h(s) = 1_{s \in T}$ for all $s \in S$, that is, $h(s) = 1$ if $s \in T$ and $h(s) = 0$ if $s \in S \setminus T$.

A singleton family $H$ cannot shatter any non-empty set $S$. Indeed, suppose that $H = \{h\}$ shatters $S \neq \emptyset$, and take any $s \in S$. Taking $T = \emptyset$, we see that $h(s) = 0$, whereas taking $T = S$, we see that $h(s) = 1$.

$\endgroup$
4
  • $\begingroup$ Thanks. It seems to me that the point is that $H$ can realise any binary labelling on $S$. Is that correct? I thought it could be any labelling at all. $\endgroup$
    – user27182
    Sep 10 '17 at 15:23
  • 1
    $\begingroup$ Right, VC dimension is defined for binary classification. As far as I understand, a satisfactory analog for $d$-way classification isn't known for $d > 2$. $\endgroup$ Sep 10 '17 at 15:25
  • $\begingroup$ Cool. If you don't mind me asking, whats wrong with just extending the definition to any n-tuple labelling? So we require that $H$ can realise $x \in \{0, 1, 2\}$ for it to shatter $S$ into three classes? $\endgroup$
    – user27182
    Sep 10 '17 at 15:28
  • 1
    $\begingroup$ If I remember correctly, VC dimension has many properties which don't seem to apply for the obvious generalization, which is what you suggest. $\endgroup$ Sep 10 '17 at 15:30
0
$\begingroup$

I'm not sure when you mean that the VC dimension of a singleton is 0? I have always thought it was 1. How I think about it is that given some $H$ of classifiers, I will pick any one point in the domain space $\mathcal{X} = \mathbb{R}$. Then an adversary will have to label it whichever way he wants. And if one of my classifiers in $H$ is able to classify correctly the points no matter how the adversary labels the points, then we say that $H$ shatters 1 point and should have at least VC dimension of 1.

So let the classifier set be $H = \{ h_i \}$ where $h_i(x) = 1$ if $x=i$ and 0 otherwise, for all $i \in \mathbb{R}$. So say for instance, I pick the point at $x=6$. The adversary comes in to label it with a 1, then I can provide the adversary with a classifier that labels this point with 1 (i.e. $h_6$). If he labels the point with 0 instead, then I instead give him another classifier that is not $h_6$ (that will label it 0 for sure).

So now, we check if $H$ can shatter two points. Apparently if we picked two points $x_i,x_j \in \mathbb{R}$, then the adversary will just label both with 1s and thus I am unable to find a classifier in $H$ that labels both with 1s. I try to give him $h_i \in H$ but that labels $x_i$ with 1 and $x_j$ with 0. I could try giving him $h_j \in H$ but $x_i$ labelled with 0 and $x_j$ with 1 (i.e. none of the classifiers in $H$ can give me a (1,1) labelling due to the nature of the singleton property).

$\endgroup$
1
  • 1
    $\begingroup$ I disagree. The VC dim of your singleton set is 0. The point is that if your adversary labels the point with a 0, you cannot use a classifier that's not $h_6$ (since it's the only thing in $H$ by assumption). $\endgroup$
    – user27182
    Oct 10 at 10:51

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.