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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
