1
$\begingroup$

What is the VC dimension of $k$ finite unions of one-sided intervals:

If we take 3 one-sided intervals like $(-\infty, a_1] $, $(-\infty, a_2] $ and $(-\infty, a_3] $, I think union of these intervals can shatter $4 $ points as below, assuming that $a_1>a_2>a_3>a_4$:

  • Point $p_1$ at interval $(-\infty, a_1]$

  • Point $p_2$ at interval $[a_1, a_2]$

  • Point $p_3$ at interval $[a_2,a_3]$

  • Point $p_4$ at interval $(-\infty, a_3]$

For $k$ finite unions I think answer is $k+1$, am I right?

Improve this question
$\endgroup$
4
  • $\begingroup$ Can you explain what you mean by "$k$ finite unions of one-sided intervals"? $\endgroup$
    – Yuval Filmus
    Aug 27, 2018 at 1:18
  • $\begingroup$ @YuvalFilmus I mean union of $(-\infty, a1] U (-\infty, a2] U (-\infty, a3] $ $\endgroup$
    – Joshna Gunturu
    Aug 27, 2018 at 2:21
  • 1
    $\begingroup$ This union is equal to $(-\infty, \max(a_1,a_2,a_3))$, that is, to a single interval. $\endgroup$
    – Yuval Filmus
    Aug 27, 2018 at 5:54
  • $\begingroup$ Is $[a1,+\infty)$ also a one-sided interval? Can you copy and past the full original problem statement or provide an accessible link? As implied by Yuval Filmus, it is not easy to comprehend your paraphrase of the problem. By the way, the VC dimension of the subsets of the real line formed by the union of $k$ intervals is $2k$. $\endgroup$
    – John L.
    Aug 28, 2018 at 8:44

1 Answer 1

Reset to default
1
$\begingroup$

Finite unions of one-sided intervals can shatter only 2 points, because as said by @YuvalFilmus in comments the union of Finite unions is a single one-sided interval, and a single one-sided interval can shatter only 2 points.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It seems more likely that you misunderstood the definition of one-sided interval. $\endgroup$
    – Yuval Filmus
    Sep 1, 2018 at 6:41

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.