I have the following concept: $$C = \left\{\bigcup_{i=1}^{k}(a_i, b_i): a_i, b_i \in {\Bbb R}, a_i < b_i, i=1,2,..,k\right\} $$ and was wondering how to determine the VC dimension of C?


1 Answer 1


VC dimension is defined for a hypothesis space $H$, e.g. a set of binary classifiers $C \rightarrow \{0, 1\}$. For example, hypothesis space $$H=\{{\Bbb 1}_{x \le \theta}: \theta \in {\Bbb R}\}$$ has VC dimension $1$, because for any $C=\{a<b\}$, it does not contain a classifier that gives $\{a \rightarrow 0, b\rightarrow 1\}$.

For example, a classifier from $H$ would be $f(x)={\Bbb 1}_{x \le a}$ that gives $\{a \rightarrow 1, b \rightarrow 0\}$.

From C to H

As you have illustrated in the comments, we can build a hypothesis space $H$ from $C$ as follows: $$H=\left\{{\Bbb 1}_{x \in C}: C = \left\{\bigcup_{i=1}^{k}(a_i, b_i): a_i, b_i \in {\Bbb R}, a_i < b_i, i=1,2,..,k\right\}\right\}$$ Meaning, each classifier in $H$ is a union of $k$ intervals that labels a point inside the union as $1$ and outside as $0$.

VC dimension of this $H$ is $2k$:

  1. For VC $\geq 2k$: Let $A$ be an arbitrary set , and $A \rightarrow \{0, 1\}$ be an arbitrary labeling. By going from minimum to maximum member of $A$, we can cover all adjacent $1$s with one interval, and only need to use another interval when there is a $0$ barrier. Therefore, we need $k$ intervals to cover $k$ isolated regions of $1$s. Furthermore, a set with $2k$ members has at most $k$ isolated $1$s (since to have $k+1$ isolated $1$s there should be $k$ $0$ barriers in-between), and thus, needs at most $k$ intervals.

  2. For VC $< 2k+1$ by contradiction: for any ordered set $A_{2k+1}=\{a_1<...<a_{2k+1}\}$, there is labeling $a_k \rightarrow 1_{\text{k odd}}$, i.e. $\{a_1 \rightarrow 1, a_2 \rightarrow 0,...,a_{2k+1} \rightarrow 1\}$ with $k+1$ isolated $1$s which cannot be covered with $k$ intervals.

  • $\begingroup$ Hi, thanks for the response. It turns out the problem C is actually the hypothesis set. You can label an arbitrary number x using C in the following way: if x is in some interval, say, (a_i, b_i) \in C, its label is 1, otherwise, its label is -1.More concisely, only the number in the union of k intervals would be labeled 1. $\endgroup$ Mar 28, 2019 at 5:55
  • $\begingroup$ @LarsErik That works! Updated. $\endgroup$
    – Esmailian
    Mar 28, 2019 at 10:54

Your Answer

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

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