VC-dimension of the class of decision trees

Question

I need to show that the VC-dimension of the class of decision trees over the domain ${0,1}^d$ is $2^d$

I tried to show that any binary classier can be implemented as a decision tree of height at most $d + 1$.

Can you help?

Answer 1

Let $h$ be any binary classifier. i.e, for any input $x= {0,1}^d$, it return 0 or 1.

Let the general decision tree, in which on the d+1 height, there are leaves that represent the value of the input.

Each input $x$ can be uniquely expressed as a path in this decision tree. For any $h$, we can express its output on the domain as a set of leaves, while any leaf is a unique identifier of an input. We can manually take each input, and assign its leaf the output of the binary classifier $h$.

Now, on any input, walking on the decision tree will result the output of $h$. Therefore, any binary classifier can be implemented as a decision tree of height at most $d+1$.

The output vector of the tree hypothesis is represented by a vector of leafs of size of $2^d$. The leafs can be assigned accordingly to any hypothesis, inducing $2$ in power of $2^d$ implementations by the class of decision trees.

Therefore, any sample S of size $2^d$ from the domain ${0,1}^d$ can be shattered by this tree.

This conclude that the VC-Dimension of the class of decision trees over the space of ${0,1}^d$ is $2^d$.