Given four points in $\mathbb{R^{3}}$ real space,

$S = \{(1, 1, 1), (1, 1, -1), (-1, -1, 1), (-1, -1, -1)\} \in \mathbb{R^{3}}$.

Will these four points be shattered by a hyperplane in $\mathbb{R^{3}}$?

And how to justify that VC-dimension for hyperplane in $\mathbb{R^{3}}$ is strictly less than $\mathbb{R^{4}}$?

  • $\begingroup$ What distinction are you making with the phrase "real space"? $\endgroup$ – whuber Dec 22 '15 at 18:12
  • $\begingroup$ It can be removed. Only remain 'R3'. Thanks for your advice. $\endgroup$ – Husky Dec 22 '15 at 18:27

First, note that both shattering and VC dimension apply to an instance set and a hypothesis space, e.g. the set of all three-dimensional hyperplanes, rather than a single hypothesis. From Mitchell's Machine Learning:

A set of instances $S$ is shattered by hypothesis space $H$ if and only if for every dichotomy of $S$ there exists some hypothesis in $H$ consistent with this dichotomy.

To determine whether $H$ can shatter $S$, one may either:

  1. Show that some subset of $S$ can correctly classify every possible split of instances in $S$.
  2. Prove that no such subset exists.

In your example, you'll find that no plane can classify the opposite corners as different classes. (To confirm this, try to find a plane that classifies $(1,1,1)$ and $(-1,-1,-1)$ differently from the other points.)

This doesn't say much about whether $VC(H)=4$. Also from Mitchell:

The Vapnik-Chervonenkis dimension, $VC(H)$, of hypothesis space $H$ defined over instance space $X$ is the size of the largest finite subset of $X$ shattered by $H$. If arbitrarily large finite sets of $X$ can be shattered by $H$, then $VC(H) \equiv \infty.$

Since $VC(H)$ refers to the largest subset of $X$, to show that $VC(H)\ge 4$, one need only show that $|S| = 4$ for some $S \subseteq X$ that is shattered by $H$. That is, $H$ needn't shatter every four-point set in $X$, just some four-point set. For example, in $\mathbb{R}^3$ planes can shatter the vertices of any tetrahedron—really any set of four points not lying in the same plane—from which we know that $VC(H) \ge 4$.

To your second question, one can show that the VC dimension of hyperplanes in $\mathbb{R}^d$ is $d+1$. (See the sketch of the proof here.) It follows that $VC(H)$ for hyperplanes in $\mathbb{R}^d$ and $\mathbb{R}^{d+1}$ are $d+1, d+2$ respectively.

| cite | improve this answer | |

You can shatter S in $\mathbb{R}^3$. For hyperplanes in $\mathbb{R}^d$, the VC-dimension is $d+1$. For example, you can look at this, p. 5/14.

| cite | improve this answer | |

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.