Question 1

Figure from the original question paper Consider a sample of 5 data-points for a classification problem with 3 classes. We can have at most *k* different labellings of these 5 points. What is the tightest upper bound for *k*? For a binary classification setup with a single feature in $\mathbb{R}$ and labels in $\{0, 1\}$, consider this hypothesis class: $$\mathcal{H} = \{h_{a_1 \ldots a_6} : a_1 < a_2 < a_3 < a_4 < a_5 < a_6, \quad a_i \in \mathbb{R}\}$$ where $h_{a_1 \ldots a_6}$ is defined as: $$h_{a_1 \ldots a_6}(x) = \begin{cases} 1, & x \in [a_1, a_2] \cup [a_3, a_4] \cup [a_5, a_6] \\ 0, & \text{otherwise} \end{cases}$$ Find the VC dimension of $\mathcal{H}$.