Why the VC dimension to this linear hypothesis equal to 3?

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.

Topic vc-theory machine-learning-model model-selection machine-learning

Category Data Science

1
answered at

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.

1
answered at

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$.

About

Geeks Mental is a community that publishes articles and tutorials about Web, Android, Data Science, new techniques and Linux security.