Universal guarantees for decision tree induction via a higher-order splitting criterion
This provides universal guarantees for decision tree induction, addressing a known limitation of existing heuristics that perform poorly on simple functions, which is significant for machine learning practitioners seeking reliable tree-based models.
The paper tackles the problem of decision tree learning by proposing a new splitting criterion that considers correlations between the target function and small subsets of attributes, achieving provable guarantees for all Boolean functions with respect to the uniform distribution. It constructs decision trees of size s^{ ilde{O}((log s)^2/ε^2)} with error ≤ O(opt_s) + ε, where opt_s is the error of the optimal size-s tree.
We propose a simple extension of top-down decision tree learning heuristics such as ID3, C4.5, and CART. Our algorithm achieves provable guarantees for all target functions $f: \{-1,1\}^n \to \{-1,1\}$ with respect to the uniform distribution, circumventing impossibility results showing that existing heuristics fare poorly even for simple target functions. The crux of our extension is a new splitting criterion that takes into account the correlations between $f$ and small subsets of its attributes. The splitting criteria of existing heuristics (e.g. Gini impurity and information gain), in contrast, are based solely on the correlations between $f$ and its individual attributes. Our algorithm satisfies the following guarantee: for all target functions $f : \{-1,1\}^n \to \{-1,1\}$, sizes $s\in \mathbb{N}$, and error parameters $ε$, it constructs a decision tree of size $s^{\tilde{O}((\log s)^2/ε^2)}$ that achieves error $\le O(\mathsf{opt}_s) + ε$, where $\mathsf{opt}_s$ denotes the error of the optimal size $s$ decision tree. A key technical notion that drives our analysis is the noise stability of $f$, a well-studied smoothness measure.