machine learningperceptronvc-dimension
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}}$?
If I'm not mistaken:
$[1 + \langle x,y\rangle]^2$ = $\langle[1, \sqrt{2}y_1, y_1^2, \sqrt{2}y_2, y_2^2, \sqrt{2}y_1y_2], [1, \sqrt{2}x_1, x_1^2, \sqrt{2}x_2, x_2^2, \sqrt{2}x_1x_2]^T\rangle$
So the separating rule is linear in $R^6$. Consequently, VC-dim is 7.
I'm not sure this is a question with a simple answer, nor do I believe it is a question that even needs to be asked about decision trees.
Consult Aslan et al., Calculating the VC-Dimension of Trees (2009). They address this problem by doing an exhaustive search, in small trees, and then providing an approximate, recursive formula for estimating the VC dimension on larger trees. They then use this formula as part of a pruning algorithm. Had there been a closed-form answer to your question, I am sure they would have supplied it. They felt the need to iterate their way through even fairly small trees.
My two cents worth. I'm not sure that it's meaningful to talk about the VC dimension for decision tres. Consider a $d$ dimensional response, where each item is a binary outcome. This is the situation considered by Aslan et al. There are $2^d$ possible outcomes in this sample space and $2^d$ possible response patterns. If I build a complete tree, with $d$ levels and $2^d$ leaves, then I can shatter any pattern of $2^d$ responses. But nobody fits complete trees. Typically, you overfit and then prune back using cross-validation. What you get at the end is a smaller and simpler tree, but your hypothesis set is still large. Aslan et al. try to estimate the VC dimension of families of isomorphic trees. Each family is a hypothesis set with its own VC dimension.
The previous picture illustrates a tree for a space with $d=3$ that shatters 4 points: $(1,0,0,1),(1,1,1,0),(0,1,0,1), (1,1,0,1)$. The fourth entry is the "response". Aslan et al. would regard a tree with the same shape, but using $x1$ and $x2$, say, to be isomorphic and part of the same hypothesis set. So, although there are only 3 leaves on each of these trees, the set of such trees can shatter 4 points and the VC dimension is 4 in this case. However, the same tree could occur in a space with 4 variables, in which case the VC dimension would be 5. So it's complicated.
Aslan's brute force solution seems to work fairly well, but what they get isn't really the VC dimension of the algorithms people use, since these rely on pruning and cross-validation. It's hard to say what the hypothesis space actually is, since in principle, we start with a shattering number of possible trees, but then prune back to something more reasonable. Even if someone begins with an a priori choice not to go beyond two layers, say, there may still be a need to prune the tree. And we don't really need the VC dimension, since cross-validation goes after the out of sample error directly.
To be fair to Aslan et al., they don't use the VC dimension to characterize their hypothesis space. They calculate the VC dimension of branches and use that quantity to determine if the branch should be cut. At each stage, they use the VC dimension of the specific configuration of the branch under consideration. They don't look at the VC dimension of the problem as a whole.
If your variables are continuous and the response depends on reaching a threshold, then a decision tree is basically creating a bunch of perceptrons, so the VC dimension would presumably be greater than that (since you have to estimate the cutoff point to make the split). If the response depends monotonically on a continuous response, CART will chop it up into a bunch of steps, trying to recreate a regression model. I would not use trees in that case -- possibly gam or regression.
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:
To determine whether $H$ can shatter $S$, one may either:
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:
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.