0
$\begingroup$

I have seen in many places that the vc-dimension of H, an hypostases class which consists of rectangles parallel to the axis is 4.

enter image description here

yet when constructing this 2D constellation of points i can't seem to find any label assignment which can't be labeled by some rectangle. aka H shatters these 5 points. am i making some mistake ?

The one thing I'm not sure about is "flipping" the labels aka flipping whether whats inside the rectangle is considered 1 or -1, i believe it's the general assumption am i not correct?

points comstelation

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

This set of $5$ points cannot be shattered by $\mathcal{H}$. To see that, notice that any axis-aligned rectangle that contains the $4$ points $(-0.5,-0.5)$, $(0, 1)$, $(0.5,0.5)$ and $(0,-1)$ also contains the origin which means that we cannot find a hypothesis that positively classifies only those $4$ points.

I believe your confusion stems from your second question about "flipping" the labels. The labels are just labels, so you could, in theory, change them to whatever you want but you have to keep them consistent throughout your analysis. Getting back to the problem, when you try to find a hypothesis that positively labels ($+1$) every point except the origin, you cannot flip the labels and consider $+1$ to mean that a point is outside.

Improve this answer
$\endgroup$
7
  • $\begingroup$ but following the assumption that labels could not be switched. if i look at a half-space classifier i see that it cannot shatter 2 points (if we label 2 points differently we can switch what is classified above and below the decision boundary) $\endgroup$
    – Tomer Gigi
    Commented Jul 29, 2023 at 5:07
  • $\begingroup$ @TomerGigi I don't understand your question. Could you elaborate, please? $\endgroup$
    – George Giapitzakis
    Commented Jul 29, 2023 at 5:48
  • $\begingroup$ looking at the example given here by Abhishek Ghose it is clear to see that the labeling is "switched" the definition of label "above" the half space is once blue and once white. why can we say the same with rectangles? quora.com/Explain-VC-dimension-and-shattering-in-lucid-Way and as per your example we can put point (0,0) in a box and then by changeing what the labeling of "in" points we can rach all labels $\endgroup$
    – Tomer Gigi
    Commented Jul 29, 2023 at 10:42
  • $\begingroup$ @TomerGigi It's not the labeling that is switched. It's the normal vector to the hyperplane that's rotated so the halfspaces are inverted. $\endgroup$
    – George Giapitzakis
    Commented Jul 29, 2023 at 14:30
  • $\begingroup$ oh ok so in the half space case the "lable switching" is built into the definition of H while in the rectangle case it needs to be specified. i think i understand, is it trivial to say that for H' containing both cases the vc dimension will be 5? (H' containing H above and - H) maybe it's less trivial then thanks for the answer anyways $\endgroup$
    – Tomer Gigi
    Commented Jul 29, 2023 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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