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}}$?
Best Answer
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:
- Show that some subset of $S$ can correctly classify every possible split of instances in $S$.
- 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.
Similar Posts:
- Solved – How to make the conclustion that VC-dimension for hyperplane in $mathbb{R^{3}}$ is strictly less than $mathbb{R^{4}}$
- Solved – VC dimension of a rectangle
- Solved – Can SVM be used for dimensionality reduction from n dimensions to n-1
- Solved – VC-Dimension of k-nearest neighbor
- Solved – SVM kernels and decision boundaries