Decision trees are a cornerstone of machine learning due to their intuitiveness, ease of explanation, and strong performance on tabular data. However, they possess a fundamental limitation: they typically partition data using axis-parallel hyperplanes (e.g., "Is $x_1 > 10$? "). When real-world decision boundaries are diagonal or curved, standard decision trees must approximate these shapes through a series of "staircase" steps. This leads to bloated, complex trees that are difficult to interpret and computationally inefficient.
In their AAAI-24 paper, researchers Kei Sen Fong and Mehul Motani introduce SREDT (Symbolic Regression Enhanced Decision Trees). By replacing simple feature thresholds with mathematical expressions discovered via Symbolic Regression, they have developed a model that is significantly smaller, faster, and often more accurate than traditional trees.
The Problem: The "Staircase" Effect
Traditional Decision Trees (DTs) partition feature space using lines parallel to the axes. For complex datasets like XOR or non-linear boundaries like concentric circles, a standard DT requires numerous nodes to approximate the boundary. This "bloating" increases the cognitive load for human interpretation and slows down inference.
While Oblique Decision Trees (ODTs) allow for diagonal splits using linear combinations of features, they often involve every input feature in every split, making them susceptible to noise and still unable to capture truly non-linear relationships (like $x_1 \cdot x_2$) efficiently. SREDT aims to find the "perfect" split: one that is as simple as possible but as non-linear as necessary.
Methodology: Integrating Symbolic Regression
The core innovation of SREDT is the integration of Symbolic Regression (SR) directly into the tree-building process:
- The SREDT Algorithm: Instead of the standard CART approach of iterating through every feature to find a threshold, SREDT executes an evolutionary SR algorithm at each node.
- Splitting Rules: The SR search identifies concise mathematical expressions using operators such as $+$, $-$, $*$, and $/$. For instance, a single split like $x_1 \cdot x_2 > 0.5$ can replace multiple axis-parallel splits.
- Fitness Function: The SR process utilizes Gini Impurity as its fitness metric, ensuring that discovered expressions are optimized specifically for classification tasks.
- Local Search (Local SREDT): To refine the model, the authors introduced a variant that employs a differentiable squared hinge loss and the BFGS optimization algorithm to fine-tune numerical constants within the discovered expressions.
Key Results and Insights
The authors evaluated SREDT against synthetic benchmarks (XOR, Half-Moons, Concentric Circles) and 56 real-world datasets from the Penn Machine Learning Benchmark (PMLB).
Compactness and Interpretability
SREDT dramatically reduces tree complexity. On the Diabetes dataset, the ratio of leaves in a standard DT compared to SREDT was 2400%. By reducing tree depth from 6 levels to 1 or 2, SREDT significantly lowers the cognitive load required for human understanding.
Performance and Efficiency
- Accuracy: SREDT consistently outperformed standard DTs and ODTs, performing competitively against state-of-the-art ensemble methods like XGBoost and CatBoost.
- Inference Speed: Due to shallower trees, Local SREDT achieved an inference speed roughly 26% faster than traditional models.
- Robustness: Because SR naturally favors simpler expressions (parsimony), SREDT is less likely to overfit to noisy features compared to standard DTs.
Limitations and Future Work
The primary trade-off for SREDT's efficiency is training time. Because Symbolic Regression relies on evolutionary algorithms, training can take significantly longer than standard trees. However, the authors argue this is a worthwhile trade-off for the resulting gains in inference speed and explainability.
Future research directions include exploring "Symbolic Forests" (ensembles of SREDTs) and further optimizing the training process to reduce computational overhead.
Paper Citation: Fong, K. S., & Motani, M. (2024). Symbolic Regression Enhanced Decision Trees for Classification Tasks. Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24).
Summary updated