5
$\begingroup$

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}}$?

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

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.