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.


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.


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)

  • $\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 '14 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$ Jun 17 '14 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 '14 at 22:18
  • $\begingroup$ @Ebraham Thanks for the feedback, which bracket insert is wrong and where are you stuck? $\endgroup$ Jun 18 '14 at 0:58
  • $\begingroup$ no you correct it. just i want to find different between [-infinity <x <a, x is real number] with this example. i think this is a threshold and has a VC= 1. it's not interval ? yes? $\endgroup$
    – Ebraham
    Jun 18 '14 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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