2
$\begingroup$

I am trying hard to understand this. Here is the scenario:

X = R^2
H = { h(x) = x + 10 }

I need to calculate the VC dimension for the above linear separator. Somehow, the VC dimension for this linear separator is 3. I just cannot understand how.

According to what I understand, VC dimension is the size of the largest finite subset of X which can be shattered by h. So if there exists a subset of size n where all points are shattered by h and there exists a subset of size n+1 where at least one point is not shattered by h, then the VC dimension will be n.

  • Is the VC dimension >= 1?

Yes. We just need to pretend there is a single point on the line and by keeping the line (X-axis) steady we can flip which side is positive/negative

  • Is the VC dimension >= 2?

Yes, because we could separate all 4 combinations { ++, --, +-, -+ } using a single line

  • Is the VC dimension >= 3?

This should be NO, according to what I understand. How could we separate this case + - +?

But I was going through a video, that explains VC dimensions which says it is three and I do not understand how.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I thought they explained it quite well (at about 2:30 in the video). I think the key is to remember that you only have to shatter just one specific set of $d$ points in order for the VC-dimension to be greater or equal to $d$ ($d=3$ in this case). You don't have to shatter any combination of points (e.g. you can't shatter $+-+$ if they are on a line but it doesn't matter because you can shatter a different set of points if they form a triangle as in the video!) $\endgroup$
    – oW_ ♦
    Oct 2, 2018 at 15:33

2 Answers 2

Reset to default
2
$\begingroup$

The VC dimension for the classifier depends on the dimension of space that your data points belong to.

In your problem, if your mean $x\in \mathbb{R^2}$, then the VC dimension is 3. For $\mathbb{R^2}$, you can always shatter any three general position points ("general position" means they do not coincidentally lie on the same line). For instance, consider three points (0,0), (0,1), (1,0). No matter how you assign labels to them, you can always seperate them by a line. If you consider point points with label (0,0), (0,1), (1,0), (1,1) with label [+,-,-,+], this is the "xor" case which cannot be seperated by a line.

For $x\in \mathbb{R}$, then the VC dimension is 2 because you cannot separate +-+.

In general for $x\in \mathbb{R^d}$, the VC dimension for a linear classifier is $d+1$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ But how do we separate +-+ for x ∈ ℝ𝟚? $\endgroup$
    – Suhail Gupta
    Oct 2, 2018 at 14:30
  • 2
    $\begingroup$ in $\mathbb{R}^2$ do don't consider the case where the three points lie on the same line. Is that what you mean? $\endgroup$
    – user12075
    Oct 2, 2018 at 15:55
1
$\begingroup$

The VC dimension depends on the dimension of your data and on the family of functions you are evaluating.

In $\mathbb R^2$, the VC dimesion of the family $h(x)$ of oriented lines is 3 beacause, with oriented lines, you can only classify correctly three points taking into account all the 8 possible label assignments, as depicted in the figure below:

enter image description here

Figure from: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/svmtutorial.pdf

Yor family of functions $h(x) = x + 10$ is a subset of the family of lines, then the VC is 3, you can try to draw the same figure as the one above but whith your particular $h(x)$. You won't be able to separate 4 points taking into account their 16 possible labelings with this family of functions.

Improve this answer
$\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.