Falling Trees: A Model Class for Interpretable Risk Prioritization
Varun Babbar, Zachery Boner, Margo Seltzer, Cynthia Rudin
cs.LG
Quick verdict
New 'falling trees' model class + GRAVITree Rashomon-set algorithm; promising interpretable-ML work, but cross-table number inconsistencies need clarification.
Summary
This paper generalizes falling rule lists (FRLs) — ordered if–then rules with monotonically decreasing risk — to 'falling trees', an interpretable model class in which, along every root-to-leaf path, adjacent leaves' positive-class probabilities must decrease with depth. The authors propose GRAVITree, a dynamic-programming-with-bounds algorithm that enumerates the Rashomon set of falling trees under depth, minimum-support, and a novel branching-cost penalty μ (counting internal nodes with two internal children), letting users interpolate between rule lists and full decision trees. Two theorems characterize the falling constraint and justify pruning; quantized caching accelerates the probability-ceiling-aware search. Across 21 UCI/Kaggle datasets (five splits, metrics averaged over each Rashomon set), GRAVITree with μ=0.01 attains lower test loss than its μ=1 rule-list mode and sparser positive-class decisions than TreeFARMS at slightly higher overall loss, running roughly 3–22× faster (FICO: 45.6 s vs 223.5 s); a MIMIC-III ICU case study reaches accuracy 0.66–0.71 versus 0.73 for binarized XGBoost. Main limitations: GRAVITree numbers are inconsistent across tables under seemingly identical settings (e.g., Spambase 0.105 vs 0.126), quantized caching conflicts with the exactness claim, Welch's tests lack multiple-comparison correction, Rashomon-set sizes show huge split variance, and no code release is stated.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Falling trees generalize the FRL monotone-risk constraint to tree structures while permitting controlled branching (Definitions 3.1–3.2; Theorem 4.1).
- GRAVITree enumerates the Rashomon set of falling trees under depth, min-support, and branching-cost constraints using falling-specific pruning bounds (Theorem 4.2), modulo the quantized-caching approximation admitted in Appendix D.2.
- The branching cost μ lets users interpolate between rule lists and full decision trees, evidenced by the normalized Colless index approaching 1 as μ increases (Figure 4).
- On 21 benchmarks, falling trees with μ=0.01 trade a small overall-loss increase versus TreeFARMS for sparser decisions and often lower FNR on positive-class instances, and they dominate falling rule lists on test loss (Tables 1–2).
Strengths
Novel and cleanly formalized model class
Definitions 3.1–3.2 generalize FRL monotonicity to trees via 'adjacent leaves along each path'; Theorem 4.1 gives an if-and-only-if local characterization with a complete two-direction proof (Appendix A), and Theorem 4.2 proves the candidate-pruning rule via a convex-combination argument.
Genuine algorithmic machinery
Algorithm 1 resolves coupled child subproblems (shared branching penalty plus probability ceiling) by recursing on the higher-p+ child first and carrying best/second-best solutions; Algorithm 4's sorted merge turns quadratic cross-products log-linear; Table 6 shows the falling constraint itself speeds search (FICO 2302 s vs 3785 s unconstrained; Bike 63.0 s vs 111.1 s).
Useful structural control knob
Broad, largely honest evaluation
Clear runtime advantage over TreeFARMS
Weaknesses
Cross-table numerical inconsistencies under identical stated configurations
Exactness claim conflicts with quantized caching
Statistical rigor gaps
No black-box reference on the benchmarks
Reproducibility gaps
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper introduces **falling trees**, a decision-tree model class inheriting the monotone-risk property of falling rule lists (FRLs): along every root-to-leaf path, adjacent leaves' positive-class probabilities must decrease with depth (Definitions 3.1–3.2). Contributions are (i) a branching-cost regularizer H(T) counting internal nodes with two internal children, (ii) GRAVITree, a dynamic-programming-with-bounds algorithm claiming exact enumeration of the Rashomon set under depth d, minimum support α, and branching penalty μ, and (iii) experiments on 21 UCI/Kaggle datasets plus a MIMIC-III ICU case study. The central claims — interpolation between rule lists and full trees (Fig 4: NCI→1 as μ grows), a small loss traded for sparser high-risk decisions, and dominance of FRLs on loss — are mostly well-scoped to interpretable baselines. Table 2 honestly shows TreeFARMS retains a clear test-loss edge on several datasets (Mushroom 0.007 vs 0.030; MGH 0.031 vs 0.061).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is a falling tree in machine learning?
A falling tree is a decision tree in which, along every root-to-leaf path, the positive-class probability of adjacent leaves must decrease with depth. It generalizes falling rule lists (FRLs) — ordered if–then rules whose risk falls monotonically — so that the highest-risk cases are decided near the top of the model, which is useful for risk prioritization in high-stakes settings like medicine.
What is the GRAVITree algorithm?
GRAVITree is a dynamic-programming-with-bounds algorithm that enumerates the full Rashomon set (all near-optimal models) of falling trees under depth, minimum-support, and branching-cost constraints. It uses falling-specific pruning bounds, a recursion that handles coupled sibling subproblems via best and second-best solutions, sorted-set merging, and quantized caching to keep the search tractable.
How do falling trees compare to falling rule lists and TreeFARMS?
Across 21 UCI/Kaggle benchmarks with five train-test splits, GRAVITree with a mild branching penalty (μ=0.01) achieved lower test loss than its own forced-rule-list mode (μ=1) on most datasets, and sparser decisions on positive-class examples than TreeFARMS at slightly higher overall loss. It also ran roughly 3–22× faster than TreeFARMS (e.g., 45.6 s vs 223.5 s on FICO), though the SORTeD baseline was typically faster still.
Is code or data for the falling trees paper available?
The paper text reviewed here does not announce a public code release. The experiments use public UCI/Kaggle datasets plus MIMIC-III-derived and MGH clinical data (the MGH dataset's license is listed as N/A), and the algorithms are fully specified in pseudocode, but availability of an official implementation is not stated.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 1–5 are not analyzable from the extracted text; assessments of the MIMIC trees and the NCI-vs-μ trend rely on captions and reported numbers.
- Some table values may suffer OCR/extraction noise; the flagged cross-table discrepancies (e.g., Car Evaluation 0.141 vs 0.242, Spambase 0.105 vs 0.126, Adult 0.204 vs 0.293 vs 0.227) should be verified against the PDF before treating them as confirmed errors.
- The Rashomon tolerance ε for Table 1 and the caching quantization q used for headline results are not stated in the extracted text, limiting exact reproduction.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.