Research map / Learning theory and algorithms / Prediction and decision losses

Symbolic Regression Enhanced Decision Trees for Classification Tasks

AAAI 2024 · Learning theory and algorithms › Prediction and decision losses · approach: Optimal decision tree learning · 15 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes SREDT, a decision tree whose node splits are found by genetic-programming symbolic regression scored with Gini impurity, yielding smaller trees that beat DT and oblique DT on tabular classification.

Problem

Axis-parallel decision tree splits produce large, complex trees with dense decision boundaries when true class boundaries are oblique or nonlinear, hurting explainability and inference time.

Approach

Replace the per-feature split search of CART with a genetic-programming symbolic regressor that evolves arbitrary arithmetic split expressions over features and picks the best expression-threshold pair by Gini impurity, so each node can encode a richer boundary; a local-search variant optimizes constants with a squared hinge loss.

Key results

• SREDT reaches best accuracy on the 6 real-world datasets among single trees, outperforming DT and ODT, with trees about 2-8x shallower in depth and fewer leaves than DT (e.g., Diabetes leaves 2400% of SREDT size vs DT).
• Local SREDT improves accuracy over the original on 77.2% of 56 PMLB datasets and beats DT and ODT in F-score on 82.5% and 73.7% of datasets respectively.
• SREDT inference time is consistently lower than DT and ODT (e.g., DT-to-SREDT inference time ratio 186% on Raisin), but training takes about 1570 times longer than DT.

Measured effects reported in the paper

Surprising findings

• SREDT is not better than DT and ODT on the Iris dataset in accuracy/F-score.
• SREDT is largely robust to noisy added feature columns, while all other models except DT are influenced by them 100% of the time.

Limitations

• Greedy tree construction does not guarantee recovering the DT/ODT tree and can underperform on some datasets such as Iris.
• Training is much slower than DT because many candidate expressions are evaluated per split.
• Splits ignore distance of data points from the boundary, so boundaries can differ from margin-based solutions (e.g., ellipse instead of circle).

Experimental setup

Datasets: MLxtend XOR MLxtend Half-Moons MLxtend Concentric Circles Cancer Diabetes Forest Type Mapping Heart Disease Iris Raisin PMLB (56 datasets) AI Feynman equation corpus

Benchmarks: MLxtend XOR MLxtend Half-Moons MLxtend Concentric Circles Cancer Diabetes Forest Type Mapping Heart Disease Iris Raisin PMLB (56 datasets)

Metrics: accuracy F-score tree depth number of leaves number of terms inference time robustness to noisy columns

Baselines: DT ODT (Stree) AdaBoost CatBoost ExtraTrees XGBoost Gradient Boosting LightGBM Random Forest SVM NODE TabNet

Builds on: CART GP-based symbolic regression oblique decision trees (Stree) AI Feynman

Closest papers by meaning

• Learning Small Decision Trees with Few Outliers: A Parameterized Perspective (AAAI 2024 · similarity 0.89)
• Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again (NeurIPS 2026 · similarity 0.88)
• Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO* (ICML 2025 · similarity 0.87)
• GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent (AAAI 2024 · similarity 0.87)
• Witty: An Efficient Solver for Computing Minimum-Size Decision Trees (AAAI 2025 · similarity 0.86)
• Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.86)