8
$\begingroup$

So I'm reading "Introduction to Machine Learning" 2nd edition, by Bishop, et. all. On page 27 they discuss the Vapnik-Chervonenkis Dimension which is,

"The maximum number of points that can be shattered by H [the hypothesis class] is called the Vapnik-Chervonenkis (VC) Dimension of H, is denoted VC(H) and measures the capacity of H."

Whereas "shatters" indicates a hypothesis $h \in H$ for a set of N data points such that it separates the positive examples from the negative. In such an example it is said that "H shatters N points".

So far I think I understand this. However, the authors lose me with the following:

"For example, four points on a line cannot be shattered by rectangles."

There must be some concept here I'm not fully understanding, because I cannot understand why this is the case. Can anyone explain this to me?

$\endgroup$
3
  • 2
    $\begingroup$ Call the four points $p,q,r,s$ in order along the line. There is no rectangle that contains $p$ and $r$ but excludes $q$ and $s$. $\endgroup$
    – JeffE
    Commented May 18, 2012 at 20:48
  • 1
    $\begingroup$ Yes, but there are rectangles that can contain $p$ and $q$, excluding $r$ and $s$; or contain $q$ and $r$ and exclude $p$ and $s$. Are you saying that each combination must be possible for the points to be shattered, and if so WHY IS THIS NOT AN ANSWER :P ? $\endgroup$ Commented May 18, 2012 at 21:03
  • $\begingroup$ I don't get the answer and I believe your point is right bro @BrotherJack can you explain why I am wrong ? $\endgroup$ Commented Feb 11, 2022 at 9:33

1 Answer 1

11
$\begingroup$

The definition of "a set $P$ can be shattered by rectangles" is that for every subset of $P$, there is a rectangle that contains precisely that subset and excludes the rest of $P$. Equivalently, every labeling of the points as positive and negative is consistent with at least one hypothesis in $H$.

Now consider four points $p,q,r,s$ along a line in the plane. Since there is no rectangle that contains $p$ and $r$ but excludes $q$ and $s$, these four points cannot be shattered by rectangles.

$\endgroup$
1
  • $\begingroup$ There we go. Much better to have this as an answer, no? $\endgroup$ Commented May 19, 2012 at 21:49

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.