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$
  • 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 May 18 '12 at 20:48
  • $\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$ – BrotherJack May 18 '12 at 21:03
10
$\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$
  • $\begingroup$ There we go. Much better to have this as an answer, no? $\endgroup$ – BrotherJack May 19 '12 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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