0
$\begingroup$

As i See in ML Course a VC dimension calculation is very theoretical.

What is the VC-dimension of intervals in R?

The target function is specifieed by an interval, and labels any example positive i it lies inside that interval.

Answers:

VC-dim = 2. A set of two points can be shattered, since there's only a single block of positive examples that could lie within the interval. But no set of 3 points can be shattered, because it can not be labeled in alternating +; - ; + order.

so i'm get stuck with meaning of interval.

for example, it means {(a, b) | "a is lower than b", a,b is real number} has VC-dim = 2?

Any idea or solution would be highly appreciated.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

Yes, an open interval in $\mathbb{R}$ is defined as $(a,b) = ]a,b[ = \left \{ x \in \mathbb{R}|\,a<x<b\right \} $. It has two parameters $a$ and $b$. The sets of all open intervals, i.e. $\left \{ \left \{ x \in \mathbb{R}|\,a<x<b\right \} | a,b \in \mathbb{R}\right\}$ has a VC dimension of 2 for the reason you mention. Keep in mind that the VC dimension of a hypothesis set $H$ is the most points $H$ can shatter.). To put it graphically:

enter image description here

(image from CalTech's free machine Learning online course by Yaser Abu-Mostafa Learning from Data)

Improve this answer
$\endgroup$
6
  • $\begingroup$ i confused !! yes or no :) Dear Richerby, be aware that a is lower than b, not lower equal than b ! $\endgroup$
    – Ebraham
    Jun 17, 2014 at 22:09
  • $\begingroup$ Thanks, I clarified the answer. Let me know If it's okay now. The strict inequality works too as you can take b arbitrarily close to a anyway. $\endgroup$
    – Franck Dernoncourt
    Jun 17, 2014 at 22:17
  • $\begingroup$ Dear Franck, some bracket insert wrongly in your anwers. can you put some detail to your answers? $\endgroup$
    – Ebraham
    Jun 17, 2014 at 22:18
  • $\begingroup$ @Ebraham Thanks for the feedback, which bracket insert is wrong and where are you stuck? $\endgroup$
    – Franck Dernoncourt
    Jun 18, 2014 at 0:58
  • 1
    $\begingroup$ [-infinity <x <a, x is real number] is a ray. A ray is an interval with an infinite endpoint. The set of rays has a VC dimension of 1. All rays are intervals, but the reciprocal is false. $\endgroup$
    – Franck Dernoncourt
    Jun 18, 2014 at 13:52

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.