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:
- 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).
- 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.
- 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.
- 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.
- 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.
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.
- 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.
- 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