Abstract
Decision tree construction traditionally relies on manual selection of splitting criteria, such as Gini impurity or Shannon entropy. This work introduces a data-driven framework to automate this process by utilizing a flexible family of splitting criteria based on $(\alpha, \beta)$-Tsallis entropy. We provide theoretical sample complexity bounds and demonstrate empirically that the optimal splitting logic is highly dataset-dependent, allowing for the automated discovery of more accurate and interpretable models.
Introduction
Decision trees remain a cornerstone of interpretable machine learning. However, their performance is heavily influenced by the choice of splitting criterion—the heuristic used to determine how to branch the tree at each node. For decades, practitioners have manually toggled between standard options like Gini impurity (CART) and Shannon entropy (C4.5). This paper addresses whether this selection can be automated and optimized for specific data domains using a meta-learning approach.
Methodology
The authors propose a novel framework for data-driven algorithm design centered on three pillars:
- The $(\alpha, \beta)$-Tsallis Entropy: A two-parameter family of splitting criteria that generalizes common methods. By adjusting $\alpha$ and $\beta$, the algorithm can interpolate between Gini impurity, Shannon entropy, and other theoretical criteria.
- Empirical Risk Minimization (ERM): Instead of optimizing for a single dataset, the learner identifies the optimal $\alpha$ and $\beta$ parameters by training across multiple datasets from the same domain.
- Theoretical Guarantees: The paper establishes sample complexity bounds, proving that a near-optimal splitting criterion can be learned from a relatively small number of datasets.
The framework also extends to tuning Bayesian decision tree priors and pruning hyperparameters, such as the cost-complexity parameter $\tilde{\alpha}$.
Experimental Setup
The approach was validated using benchmark datasets from the UCI Machine Learning Repository, including Iris, Banknote Authentication, Breast Cancer, and Wine. These datasets represent diverse domains, allowing the authors to observe how optimal splitting parameters vary across different types of data.
Results and Discussion
The core finding is that there is no "one size fits all" splitting criterion. The empirical results demonstrate that the optimal $(\alpha, \beta)$ values vary significantly between datasets.
As shown in Figure 1, the accuracy heatmaps reveal distinct "sweet spots" for each dataset. For instance, the optimal region for the Iris dataset differs markedly from that of the Banknote or Wine datasets. This confirms that a continuous search space for splitting criteria allows for the discovery of "hybrid" logics that outperform standard discrete choices.
Furthermore, Theorem 1 in the paper provides a formal guarantee on the efficiency of this learning process. It shows that the number of datasets required scales logarithmically with the size of the node function class, making the meta-learning approach computationally viable.
Conclusion
This research shifts decision tree design from manual heuristic selection to an automated, provably efficient learning problem. By leveraging the $(\alpha, \beta)$-Tsallis entropy family, practitioners can automatically tailor decision tree algorithms to their specific data domains, achieving superior accuracy and interpretability. Future work will focus on navigating the non-linear optimization landscape more efficiently and incorporating more nuanced metrics for interpretability.
Summary updated