Generalization Properties of Decision Trees on Real-valued and Categorical Features

Understand

We revisit binary decision trees 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.
• We consider three types of features: real-valued, categorical ordinal and categorical nominal, with different split rules for each.
• For each feature type, we upper bound the partitioning function of the class of decision stumps before extending the bounds to the class of general decision tree (of any fixed structure) using a recursive approach.