The power of choices in decision tree learning

Guy Blanc, Jane Lange, Chirag Pabbaraju, Li-Yang TanICLR 2023 · OpenReview

TL;DR

This paper introduces "Top-k," a simple yet powerful generalization of classic greedy decision tree algorithms. By considering the k best attributes for splitting instead of just the single best, Top-k achieves significantly higher accuracy, bridging the gap between fast greedy methods and slow optimal tree algorithms, while maintaining much of their scalability.

What Problem Does This Paper Address?

Decision trees are a cornerstone of interpretable machine learning, but standard greedy algorithms like ID3, C4.5, and CART, while efficient, often produce suboptimal trees. On the other hand, "optimal decision tree" algorithms aim for perfect accuracy but suffer from severe scalability issues, making them impractical for large datasets. This leaves a gap: how can we achieve significantly better accuracy than greedy methods without sacrificing their efficiency and scalability?

Methods

The authors propose "Top-k," a generalization of greedy decision tree algorithms. Instead of selecting only the single best attribute for a split (as in standard algorithms), Top-k considers the k attributes with the highest scores according to a feature scoring function (e.g., information gain). The algorithm then chooses the best split among these top k candidates. When k=1, Top-k reduces to standard greedy algorithms. When k is set to the total number of features, it approaches optimal decision tree learning. The paper also introduces an optimized version of Top-k with caching and pruning for improved practical performance.

Datasets

The experiments were conducted on a variety of datasets from the UCI Machine Learning Repository. These datasets included both numerical and categorical features, with sizes in the thousands and feature counts ranging from approximately 50 to 300 after binarization. A subset of 20 such datasets was used for evaluation.

Key Insights and Ideas

  • The "Power of Choices": Even a small increase in the number of candidate splits (k) can lead to dramatic improvements in accuracy, as demonstrated by the "greediness hierarchy theorem." This suggests that simply allowing the algorithm to "look ahead" a bit more can unlock significant performance gains.
  • Bridging the Gap: Top-k offers a compelling middle ground between fast but suboptimal greedy algorithms and slow but optimal decision tree algorithms. It inherits the efficiency of greedy methods while achieving accuracy closer to optimal trees.
  • Scalability Advantage: Top-k scales significantly better than existing optimal decision tree algorithms, making it applicable to larger datasets and feature sets that are currently out of reach for optimal methods.
  • Overfitting vs. Underfitting: The experiments suggest that while increasing k generally improves accuracy, there's a point of diminishing returns. Very large k values can lead to overfitting, similar to how overly complex greedy trees can.

Key Results

  • Theoretical Guarantees: The authors prove a "greediness hierarchy theorem" showing that Top-(k+1) can achieve significantly higher accuracy than Top-k on certain data distributions, even with a larger depth budget for Top-k. This theoretical result holds for both adversarial and monotone data distributions.
  • Empirical Accuracy Gains: Experiments show that Top-k consistently achieves higher test accuracy than standard greedy algorithms (Top-1) across a range of datasets. For instance, Top-8/16 achieved accuracy comparable to optimal trees on some datasets.
  • Scalability: Top-k demonstrates much better training time scaling compared to state-of-the-art optimal decision tree algorithms like MurTree and GOSDT. For example, Top-16 could handle datasets with all features, while optimal algorithms struggled with a fraction of them.
  • Mild Training Slowdown: Increasing k leads to a mild increase in training time, which is considered a worthwhile trade-off for the significant accuracy gains.

Limitations and Future Work

  • Parameter Selection: The paper acknowledges that selecting the optimal value of k is an open question. Future work could explore principled approaches to automatically select or learn k.
  • Robustness to Noise: The authors suspect that the "power of choices" might also lead to more robust trees against noise, which is an avenue for future theoretical and empirical investigation.
  • Ensemble Methods: A natural next step is to integrate Top-k into modern ensemble methods like random forests and XGBoost to further extend the benefits of considering multiple split choices.
  • Overfitting: While Top-k generally improves accuracy, the experiments also show that excessively large k values can lead to overfitting, highlighting the need for careful parameter tuning.

Summary updated

Abstract

We propose a simple and natural generalization of standard and empirically successful decision tree learning algorithms such as ID3, C4.5, and CART. These classic algorithms, which have been central to machine learning for decades, are greedy in nature: they grow a decision tree by iteratively splitting on the "best" attribute. We augment these algorithms with an additional greediness parameter $k$ and our resulting algorithm, Top-$k$, considers the $k$ best attributes as possible splits instead of just the single best attribute. We demonstrate, theoretically and empirically, the power of this simple generalization. We first prove a sharp greediness hierarchy theorem showing that for every $k\in \mathbb{N}$, Top-$(k+1)$ can be much more powerful than Top-$k$: there are data distributions for which the former achieves accuracy $1-\epsilon$, whereas the latter only achieves accuracy $\frac{1}{2}+\epsilon$. We then show, through extensive experiments, that Top-$k$ compares favorably with the two main approaches to decision tree learning: classic greedy algorithms and more recent "optimal decision tree" algorithms. On one hand, Top-$k$ consistently enjoys significant accuracy gains over the greedy algorithms across a wide range of benchmarks, at the cost of only a mild training slowdown. On the other hand, Top-$k$ is markedly more scalable than optimal decision tree algorithms, and is able to handle dataset and feature set sizes that remain beyond the reach of these algorithms. Taken together, our results highlight the potential practical impact of the power of choices in decision tree learning.
BibTeX
@inproceedings{blanc2023power,
  author = {Guy Blanc and Jane Lange and Chirag Pabbaraju and Li-Yang Tan},
  title = {{The power of choices in decision tree learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=AYvLkPnDguL},
}
Figure