0
$\begingroup$

I have been reading in multiple places (e.g. [1], section 4) that the VC-dimension of the class of triangles (in 2D space) is 7. The issue is that, for the case when 4 points lying on a straight line with alternating signs (like - + - +), I don't see why a triangle could separate the points. Where am I making mistake?

[1] http://www.igi.tugraz.at/lehre/CI/SS08/tutorials/VC_examples/VC_examples.pdf

Improve this question
$\endgroup$
7
  • 8
    $\begingroup$ You are getting the quantifiers in the definition of VC dimension wrong. The VC dimension being 7 means that there exists a set of 7 points that can be shattered and no set of 8 points can be shattered $\endgroup$ – Sasho Nikolov Mar 17 '15 at 0:47
  • $\begingroup$ I am confused now. The thing is I can always find a set of 8 points such that a triangle shatters it. Draw a triangle, put 4 points inside it, and four points outside it. Right? $\endgroup$ – Daniel Mar 17 '15 at 1:09
  • 4
    $\begingroup$ @Daniel: Shattering means that you have to be able to separate all +/- labellings of the same set of points, I think. $\endgroup$ – Huck Bennett Mar 17 '15 at 2:06
  • 3
    $\begingroup$ A personal pet peeve, from teaching this stuff for years... A triangle (or any single concept) does NOT shatter a set of points. Only a CLASS of concepts can shatter a set. $\endgroup$ – Aryeh Mar 18 '15 at 9:38
  • 1
    $\begingroup$ I don't think this is a research level question, and therefore it probably doesn't belong on this site. $\endgroup$ – Lev Reyzin♦ Apr 18 '15 at 2:09
0
$\begingroup$

As Sasho and Huck mentioned in their comments, "shattering means that you have to be able to separate all +/- labelings of the same set of points, given the function class."

Therefore, since the set of points on a line is never separable by the class of triangles, it is not a valid set of points to decide the VC-dimension this class.

Improve this answer
$\endgroup$

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