1
$\begingroup$

As I read this lecture for being familiar with VC dimension we find on p. 8:

VC(half intervals in $\mathbb{R}$ ) = 1 .... no subset of size 2 can be shattered

VC(intervals in $\mathbb{R}$ ) = 2 .... no subset of size 3

It's not clear to me. I read on Wikipedia about the difference of Half Interval and Interval and why VC dimension are different.

For example can this set be half intervals or intervals?

$$ \{ (-\infty \le x \le a) \, \left|\, a \in \mathbb{R} \right. \} $$

Any direction or hint on this problem?

$\endgroup$

1 Answer 1

1
$\begingroup$

I assume a half interval $I_a$ is always of the form

$$ \{(-\infty \leq x \leq a) \mid a \in \mathbb{R}\} $$

This means that all points equal or smaller than $a$ belong to the interval. Now, choose any set $S = \{y,z\} \subset \mathbb{R}$ such that $y < z$. $S$ is not shattered, since it is impossible to find a half interval $I_a$ such that $S \cap I_a = \{z\}$ (if $z$ is included in the intersection, than $y$ has to be included as well).

When we consider intervals $I_{a,b} = \{(a \leq x \leq b \mid a,b \in \mathbb{R}\}$ in contrast to half intervals, we are able to find an interval $I_{a,b}$ such that $I_{a,b} \cap S = \{z\}$ (as well as for all other subsets of $S$). This makes the difference in the VC dimension.

$\endgroup$

Your Answer

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

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