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

Contents

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.

Rate this post