Fast Interpretable Greedy-Tree Sums

Yan Shuo Tan, Chandan Singh, Keyan Nasseri, Abhineet Agarwal, James Duncan, Omer Ronen, Matthew Epland, Aaron Kornblith, Bin Yu

TL;DR

Fast Interpretable Greedy-Tree Sums (FIGS) is a novel algorithm that generalizes the standard CART decision tree by simultaneously growing a sum of small trees. By overcoming the inherent bias of single decision trees against additive structures, FIGS achieves state-of-the-art predictive performance while remaining compact enough for human experts to audit and emulate.

What Problem Does This Paper Address?

In high-stakes fields like medicine or law, "black-box" models (like deep neural networks or large ensembles) are often rejected because their decision-making process is opaque. Practitioners instead turn to interpretable models like decision trees.

However, standard decision trees (CART) suffer from a significant inductive bias against additive structure. If a target outcome is the sum of several independent factors (e.g., $y = x_1 + x_2$), a single decision tree must repeatedly split on the same variables in different branches to approximate that sum. This leads to deep, complex trees that are hard to interpret, prone to overfitting, and statistically inefficient. FIGS aims to bridge this gap, providing the performance of additive models with the clear logic of decision trees.

Methods

The core innovation is the FIGS algorithm, which extends the greedy nature of CART to a collection of trees:

  1. Simultaneous Growth: Instead of growing one deep tree, FIGS maintains a set of $K$ trees. At each iteration, it considers all possible splits across all existing trees, as well as the option to start a new "stump" (a tree with one split).
  2. Residual Fitting: To decide the next split, FIGS calculates the residuals (the remaining error) of the current model. It chooses the split that most reduces the impurity of these residuals.
  3. Disentanglement: This process allows the algorithm to "disentangle" additive components. If two features contribute independently to the outcome, FIGS will naturally place them into separate trees in the sum.
  4. G-FIGS: The authors also introduce a variant for heterogeneous data. It uses group membership probabilities (e.g., age-based groups) as instance weights, allowing the model to share information across groups while still producing tailored models for each.
  5. Bagging-FIGS: For scenarios where interpretability is less critical, the authors developed an ensemble version that uses bootstrap sampling and feature subsetting, similar to Random Forests.
The FIGS algorithm avoids the repeated splits required by CART to model additive functions, resulting in a much more compact model.

Datasets

The authors evaluated FIGS across a diverse range of benchmarks:

  • Standard Benchmarks: 6 large classification datasets (e.g., Readmission, Credit, Diabetes) and 9 regression datasets (e.g., CA housing, Breast tumor, Friedman synthetic functions).
  • Clinical Decision Instruments (CDIs): Three real-world pediatric emergency care datasets from the PECARN network: Traumatic Brain Injury (TBI), Intra-abdominal Injury (IAI), and Cervical Spine Injury (CSI). These are particularly challenging due to high data heterogeneity and the critical need for high sensitivity.

Key Insights and Ideas

  • The "Aha" Moment on Additivity: The paper demonstrates that a single tree requires exponentially more leaves to represent a sum of independent components compared to a tree-sum model. This explains why CART often feels "clunky" when dealing with simple additive risks.
  • Disentanglement as Interpretability: By separating different clinical domains into different trees (e.g., one tree for "signs and symptoms" and another for "mechanism of injury"), FIGS provides a framework that matches how clinicians naturally think, making the model more trustworthy.
  • Statistical Efficiency: The authors provide theoretical proof that tree-sum models can achieve faster generalization rates than single trees when the underlying data-generating process is additive.

Key Results

  • Superior Performance with Fewer Splits: FIGS consistently outperformed CART, RuleFit, and Boosted Stumps at low levels of complexity. On the Diabetes dataset, FIGS reached peak performance with significantly fewer splits than other methods.
Performance comparison on the Diabetes classification dataset.
  • Beating Black Boxes: On larger datasets like Credit and Juvenile, FIGS achieved higher AUC than black-box Random Forests while using fewer than 15 total splits.
Performance comparison on the Juvenile classification dataset.
  • Clinical Impact: In medical CDI tasks, G-FIGS improved specificity by up to 20% over CART while maintaining the required 95%+ sensitivity. This translates to fewer unnecessary CT scans for children without sacrificing safety.

Limitations and Future Work

  • Greedy Optimization: Like CART, FIGS is a greedy algorithm. While fast, it might miss globally optimal structures. The authors suggest exploring global optimization or Bayesian frameworks (like BART) in future iterations.
  • Threshold Selection: Choosing the "right" number of splits currently relies on cross-validation or domain expertise. Developing more automated, data-driven regularization techniques (like BIC-based criteria) is a noted area for improvement.
  • Interaction Discovery: While FIGS excels at disentangling additive components, its ability to discover and represent complex high-order interactions compared to Random Forests is an ongoing area of research.

Summary updated

Abstract

Modern machine learning has achieved impressive prediction performance, but often sacrifices interpretability, a critical consideration in high-stakes domains such as medicine. In such settings, practitioners often use highly interpretable decision tree models, but these suffer from inductive bias against additive structure. To overcome this bias, we propose Fast Interpretable Greedy-Tree Sums (FIGS), which generalizes the CART algorithm to simultaneously grow a flexible number of trees in summation. By combining logical rules with addition, FIGS is able to adapt to additive structure while remaining highly interpretable. Extensive experiments on real-world datasets show that FIGS achieves state-of-the-art prediction performance. To demonstrate the usefulness of FIGS in high-stakes domains, we adapt FIGS to learn clinical decision instruments (CDIs), which are tools for guiding clinical decision-making. Specifically, we introduce a variant of FIGS known as G-FIGS that accounts for the heterogeneity in medical data. G-FIGS derives CDIs that reflect domain knowledge and enjoy improved specificity (by up to 20% over CART) without sacrificing sensitivity or interpretability. To provide further insight into FIGS, we prove that FIGS learns components of additive models, a property we refer to as disentanglement. Further, we show (under oracle conditions) that unconstrained tree-sum models leverage disentanglement to generalize more efficiently than single decision tree models when fitted to additive regression functions. Finally, to avoid overfitting with an unconstrained number of splits, we develop Bagging-FIGS, an ensemble version of FIGS that borrows the variance reduction techniques of random forests. Bagging-FIGS enjoys competitive performance with random forests and XGBoost on real-world datasets.
BibTeX
@inproceedings{tan2025fast,
  author = {Yan Shuo Tan and Chandan Singh and Keyan Nasseri and Abhineet Agarwal and James Duncan and Omer Ronen and Matthew Epland and Aaron Kornblith and Bin Yu},
  title = {{Fast Interpretable Greedy-Tree Sums}},
  booktitle = {Proceedings of the National Academy of Sciences},
  year = {2025},
  doi = {10.1073/pnas.2310151122},
}
Figure