Timezone: »

 
Poster
Decision trees as partitioning machines to characterize their generalization properties
Jean-Samuel Leboeuf · Frédéric LeBlanc · Mario Marchand

Tue Dec 08 09:00 AM -- 11:00 AM (PST) @ Poster Session 1 #438
in Poster Session 2 »
Decision trees are popular machine learning models that are simple to build and easy to interpret. Even though algorithms to learn decision trees date back to almost 50 years, key properties affecting their generalization error are still weakly bounded. Hence, we revisit binary decision trees on real-valued features from the perspective of partitions of the data. We introduce the notion of partitioning function, and we relate it to the growth function and to the VC dimension. Using this new concept, we are able to find the exact VC dimension of decision stumps, which is given by the largest integer $d$ such that $2\ell \ge \binom{d}{\floor{\frac{d}{2}}}$, where $\ell$ is the number of real-valued features. We provide a recursive expression to bound the partitioning functions, resulting in a upper bound on the growth function of any decision tree structure. This allows us to show that the VC dimension of a binary tree structure with $N$ internal nodes is of order $N \log(N\ell)$. Finally, we elaborate a pruning algorithm based on these results that performs better than the CART algorithm on a number of datasets, with the advantage that no cross-validation is required.

Author Information

Jean-Samuel Leboeuf (Université Laval)
Frédéric LeBlanc (Université de Moncton)
Mario Marchand (Université Laval)

More from the Same Authors