Trjtdtk

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

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 $C=23, 56$, it does not contain a classifier that gives $23 rightarrow 0, 56 rightarrow 1$.

For example, a classifier from $H$ would be $f(x)=Bbb 1_x le 40$ that gives $23 rightarrow 1, 56 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=leftBbb 1_x in C: C = leftbigcup_i=1^k(a_i, b_i): a_i, b_i in Bbb R, a_i < b_i, i=1,2,..,krightright$$
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: ordered set $A_2k+1=a_1<...<a_2k+1$, with labeling $a_k rightarrow 1_textk odd$, i.e. $a_1 rightarrow 1, a_2 rightarrow 0,...,a_2k+1 rightarrow 1$, has $k+1$ isolated $1$s which cannot be covered with $k$ intervals.