2
$\begingroup$

The book "Understanding Machine Learning" has the following example in the section on VC dimension:

Let $\mathcal{H}$ be the class of threshold functions over $\mathbb{R}$ (real numbers). Take a set $C = \{c_1\}$. Now, if we take $a = c_1 + 1$, then we have $h_a(c_1) = 1$, and if we take $a = c_1 − 1$, then we have $h_a(c_1) = 0$. Therefore, $\mathcal{H}_C$ is the set of all functions from $C$ to $\{0,1\}$, and $\mathcal{H}$ shatters $C$. Now take a set $C = \{c_1,c_2\}$, where $c_1 \leq c_2$. No $h \in \mathcal{H}$ can account for the labeling $(0,1)$, because any threshold that assigns the label 0 to $c_1$ must assign the label 0 to $c_2$ as well. Therefore not all functions from $C$ to $\{0, 1\}$ are included in $\mathcal{H}_C$ ; hence C is not shattered by H.

I don't get why (0,1) labelling is not possible. You can choose a threshold to be between $c_1$ and $c_2$ that assigns a 0 to $c_1$ and a 1 to $c_2$.

I might be misunderstanding something here so any help is appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

The quoted text is admittedly a little vague, but it sounds like the implicit definition of a single hypothesis is $$ h_a(x) = \mathbb{1}\{x \leq a\}, $$ where $\mathbb{1}$ is the indicator function. In this case, choosing a threshold $a$ such that $c_1 < a < c_2$ doesn't work, since this produces the labeling $(1,0)$ as opposed to $(0, 1)$.

$\endgroup$

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.