# How to make the conclustion that VC-dimension for hyperplane in $\mathbb{R^{3}}$ is strictly less than $\mathbb{R^{4}}$?

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

• What distinction are you making with the phrase "real space"? – whuber Dec 22 '15 at 18:12
• It can be removed. Only remain 'R3'. Thanks for your advice. – 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.

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.