# Do I have the right definition of VC dimension?

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

## 1 Answer

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

• 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. – user27182 Sep 10 '17 at 15:23
• 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$. – Yuval Filmus Sep 10 '17 at 15:25
• 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? – user27182 Sep 10 '17 at 15:28
• If I remember correctly, VC dimension has many properties which don't seem to apply for the obvious generalization, which is what you suggest. – Yuval Filmus Sep 10 '17 at 15:30