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

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.

Similar Posts:

Rate this post

Leave a Comment