Fast Interpretable Greedy-Tree Sums

Yan Shuo Tan, Chandan Singh, Keyan Nasseri, Abhineet Agarwal, John S. Duncan, Omer Ronen, M. B. Epland, Aaron E. Kornblith, Bin Yu

TL;DR

This paper introduces Fast Interpretable Greedy-Tree Sums (FIGS), a novel algorithm that combines multiple decision trees additively to overcome the inductive bias of single trees against additive structures. FIGS achieves state-of-the-art predictive performance while maintaining interpretability, making it particularly useful for high-stakes domains like medicine, and its ensemble version, Bagging-FIGS, rivals top-performing black-box models.

What Problem Does This Paper Address?

Modern machine learning models, while powerful, often lack interpretability, which is crucial in high-stakes fields like medicine. Traditional interpretable models, such as decision trees, struggle with data that has an additive structure, leading to performance degradation. This is because a single decision tree needs many splits to represent additive components, making it prone to overfitting and high variance. The authors aim to bridge this gap by developing a method that can effectively model additive structures while remaining interpretable.

Methods

The core innovation is Fast Interpretable Greedy-Tree Sums (FIGS). It's a generalization of the CART algorithm. Instead of growing a single tree, FIGS greedily grows a sum of trees. At each step, it considers adding a split to any of the existing trees or starting a new tree (a "stump"). The decision is based on which split (across all trees) yields the largest impurity decrease, using residuals from the current sum of trees. This allows FIGS to adapt to additive structures by growing separate trees for different components.

Key aspects include:

  • Additive Structure Adaptation: By allowing multiple trees to contribute to the final prediction, FIGS can naturally model additive relationships that single trees struggle with.
  • Disentanglement: Theoretically, FIGS can "disentangle" additive components, meaning each tree in the sum learns a distinct part of the additive function. This is a key property for interpretability and efficiency.
  • Group-Weighted FIGS (G-FIGS): A variant designed for heterogeneous data (e.g., different patient groups). It first learns group membership probabilities and then uses these as weights to fit a separate FIGS model for each group, allowing for shared information while maintaining group-specific models.
  • Bagging-FIGS: An ensemble version that combines multiple FIGS models trained on bootstrap samples and with feature subsampling, similar to random forests, to reduce variance and improve robustness.

Datasets

The paper evaluates FIGS on a variety of real-world datasets for both classification and regression tasks. These include:

  • Classification Benchmarks: Readmission, Credit, Recidivism, Juvenile, German credit, Diabetes.
  • Regression Benchmarks: Breast tumor, CA housing, Satellite image, Echo months, Abalone, Diabetes (regression), Friedman1, Friedman2, Friedman3.
  • Clinical Decision Instruments (CDI) Datasets: Traumatic Brain Injury (TBI), Intra-abdominal Injury (IAI), and Cervical Spine Injury (CSI) datasets from the Pediatric Emergency Care Applied Research Network (PECARN). These are used to demonstrate G-FIGS's utility in high-stakes medical applications.

Key Insights and Ideas

  • Additive Structure is a Bottleneck for Single Trees: The paper clearly illustrates how additive functions require exponentially more splits in a single tree compared to a sum of trees, highlighting a fundamental limitation of standard decision trees.
  • FIGS Achieves "Disentanglement": The theoretical finding that FIGS can learn to disentangle additive components is crucial. It suggests that each tree in the sum learns a distinct, interpretable part of the overall function, rather than all trees learning overlapping or redundant information.
  • G-FIGS Handles Heterogeneity Effectively: The G-FIGS approach provides a principled way to model data from different groups (e.g., age groups) by leveraging shared information through instance weighting, leading to better specificity in medical applications.
  • Interpretability Doesn't Necessarily Mean Lower Performance: FIGS demonstrates that it's possible to achieve competitive, and in some cases state-of-the-art, predictive performance with highly interpretable models, challenging the common trade-off.

Key Results

  • Predictive Performance: FIGS consistently achieves strong predictive performance across a wide range of real-world datasets, often outperforming baseline interpretable models like CART, and sometimes even rivaling black-box models like Random Forests and XGBoost, especially with few splits.
  • Clinical Decision Instruments (CDIs): G-FIGS demonstrated improved specificity (up to 20% over CART) for predicting patient outcomes in medical datasets (TBI, IAI, CSI) without sacrificing sensitivity, and its learned models reflected domain knowledge.
  • Efficiency with Few Splits: FIGS achieves high performance with a significantly smaller number of splits compared to CART, making its models more interpretable and easier to use.
  • Bagging-FIGS Competitiveness: The ensemble version, Bagging-FIGS, achieved performance comparable to Random Forests and XGBoost on various datasets, and even outperformed them on some.
  • Stability: G-FIGS showed good stability to data perturbations, a critical property for deployment in high-stakes domains.

Limitations and Future Work

  • Computational Complexity: While FIGS is efficient, its run-time complexity is O(dm²n²) in the worst case, compared to CART's O(dmn²), though this gap is often benign in practice.
  • Oracle Conditions for Theory: The theoretical guarantees for disentanglement and generalization bounds are proven under oracle conditions (e.g., knowing the optimal tree structures), which are not met in practice.
  • External Clinical Validation: The CDI models developed using G-FIGS require external clinical validation before they can be used in practice.
  • Future Work: The authors suggest exploring global optimization for tree-sum models, incorporating pruning, using Bayesian frameworks, developing more sophisticated regularization techniques, and investigating FIGS for learning interactions. They also propose extending G-FIGS to other forms of data heterogeneity (e.g., temporal, geographical) and exploring data-driven identification of input data groups.

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 Classification and Regression Trees (CART) algorithm to simultaneously grow a flexible number of trees in summation. By combining logical rules with addition, FIGS adapts to additive structure while remaining highly interpretable. Experiments on real-world datasets show 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 decision-making. Specifically, we introduce a variant of FIGS known as Group Probability-Weighted Tree Sums (G-FIGS) that accounts for 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. Theoretically, we prove that FIGS learns components of additive models, a property we refer to as disentanglement. Further, we show (under oracle conditions) that tree-sum models leverage disentanglement to generalize more efficiently than single 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 performs competitively 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 John S. Duncan and Omer Ronen and M. B. Epland and Aaron E. 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