Symbolic Regression Enhanced Decision Trees for Classification Tasks

Kei Sen Fong, Mehul Motani

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.

Standard decision trees create 'staircase' boundaries to approximate non-linear data like the Half-Moons dataset.

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:

  1. 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.
  2. 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.
  3. Fitness Function: The SR process utilizes Gini Impurity as its fitness metric, ensuring that discovered expressions are optimized specifically for classification tasks.
  4. 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.

SREDT simplifies the XOR problem into a single node using a symbolic expression (X0 * X1).

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

Abstract

We introduce a conceptually simple yet effective method to create small, compact decision trees - by using splits found via Symbolic Regression (SR). Traditional decision tree (DT) algorithms partition a dataset on axis-parallel splits. When the true boundaries are not along the feature axes, DT is likely to have a complicated structure and a dense decision boundary. In this paper, we introduce SR-Enhanced DT (SREDT) - a method which utilizes SR to increase the richness of the class of possible DT splits. We evaluate SREDT on both synthetic and real-world datasets. Despite its simplicity, our method produces surprisingly small trees that outperform both DT and oblique DT (ODT) on supervised classification tasks in terms of accuracy and F-score. We show empirically that SREDTs decrease inference time (compared to DT and ODT) and argue that they allow us to obtain more explainable descriptions of the decision process. SREDT also performs competitively against state-of-the-art tabular classification methods, including tree ensembles and deep models. Finally, we introduce a local search mechanism to improve SREDT and evaluate it on 56 PMLB datasets. This mechanism shows improved performance on 77.2% of the datasets, outperforming DT and ODT. In terms of F-Score, local SREDT outperforms DT and ODT in 82.5% and 73.7% of the datasets respectively and in terms of inference time, local SREDT requires 25.8% and 26.6% less inference time than DT and ODT respectively.
BibTeX
@inproceedings{fong2024symbolic,
  author = {Kei Sen Fong and Mehul Motani},
  title = {{Symbolic Regression Enhanced Decision Trees for Classification Tasks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i11.29091},
}
Figure