Source-linked AI summary
Falling Rule Lists
Fulton Wang, Cynthia Rudin
TL;DR
Healthcare decisions often require patients to be prioritized by risk, but traditional predictive models do not naturally express this ordered logic. The paper introduces a Bayesian framework for learning falling rule lists from interpretable rules with fully enforced monotonicity. In reported applications, falling rule lists sometimes match unrestricted methods while providing greater interpretability, although strong structural restrictions can reduce predictive accuracy.
Problem
Traditional predictive models do not naturally align with healthcare decisions that prioritize patients in ordered risk sets.
Method
A Bayesian framework selects and orders pre-mined interpretable rules into sparse falling rule lists with fully enforced monotonicity.
Results
35 seconds produced a mammographic-mass decision list whose calibrated risks began at 85% and 78% for its first two described risk sets.
Takeaways & Limitations
Falling rule lists can provide predictive models that directly encode risk stratification and may be practical for high-stakes decision-making.
Takeaways & Limitations
Strong monotonicity, rule sparsity, and condition sparsity restrictions are expected to reduce predictive accuracy, with the trade-off depending heavily on the application.
Abstract
from arXiv · showhide
Falling rule lists are classification models consisting of an ordered list of if-then rules, where (i) the order of rules determines which example should be classified by each rule, and (ii) the estimated probability of success decreases monotonically down the list. These kinds of rule lists are inspired by healthcare applications where patients would be stratified into risk sets and the highest at-risk patients should be considered first. We provide a Bayesian framework for learning falling rule lists that does not rely on traditional greedy decision tree learning methods.
1 Introduction
Falling rule lists align predictive models with risk-prioritized decisions by ordering interpretable rules and enforcing decreasing risk down the list. The Bayesian approach targets accuracy, interpretability, and computational practicality without relying on greedy decision-tree learning.
- Falling Rule Lists: Falling rule lists order if-then rules so examples are classified by the first applicable rule, with estimated success probabilities decreasing down the list.This directly stratifies observations into ordered risk sets.
- Illustrative Example: 85% malignancy risk is assigned to irregular, older tumors, followed by 78% for remaining tumors with spiculated margins and older patients.The mammographic example took 35 seconds to construct, and risks were calibrated directly to the data.
- Motivation: Falling rule lists jointly rank rules for prediction and stratify patients into decreasing risk sets, reducing the sorting physicians must perform.Physicians can inspect only the highest-risk rules when that is sufficient.
- Trade-offs: The approach imposes stronger whole-list monotonicity than feature-level monotonicity, sometimes sacrificing accuracy but generally not by much.The authors frame this as a trade-off for practicality and interpretability.
- Interpretability: Interpretability depends on context, while falling rule lists can be made as sparse as desired for medical practice.Their risk ordering lets physicians examine only as much of the list as needed.
- Method: The learning algorithm mines interpretable itemsets, then uses Bayesian modeling to select and permute rules while fully enforcing monotonicity.A Bayesian prior controls the desired rule-list size.
2 Falling Rule Lists Model
The model represents binary classification with an ordered decision list whose rule-associated risks decrease monotonically. A Bayesian prior and sampling-based inference select sparse clauses and rule-list lengths while preserving this structure.
- Model Structure: The model learns p(Y | x) for binary Y using an ordered IF-THEN decision list with decreasing probability of Y = 1 down the list.The first matching clause determines the highest-risk applicable group.
- Inference: A Bayesian posterior over falling rule lists is approximated using simulated annealing and Monte Carlo sampling to obtain a MAP estimate and posterior distribution.The prior and likelihood are conditioned on training data and hyperparameters.
- Parameters: Each list contains Boolean IF clauses, real-valued risk scores, and a monotonicity constraint requiring successive scores to decrease.The default node covers examples matching none of the L clauses.
- Rule Construction: Candidate clauses are restricted to Boolean itemsets returned by frequent itemset mining, limiting models to interpretable building blocks and aiding computation.The implementation uses FPGrowth on binary feature data.
- Prior: The prior draws list length L from a Poisson distribution whose parameter λ reflects the user’s desired decision-list length.Rules are sampled from remaining itemsets with user-designed weights.
- Monotonicity Prior: Truncated Gamma variables constrained above 1 encode multiplicative score spacing while preserving monotonicity and allowing diverse prior beliefs.The default risk score is represented through K, which is Gamma distributed.
3 Fitting the Model
The paper fits falling rule lists by first finding a maximum-a-posteriori ordered rule list, then approximating posterior inference with Monte Carlo sampling and an augmented update schedule. Simulated annealing searches over discrete rule-list structures while Gibbs and collapsed Metropolis-Hastings steps update model parameters and structure.
- MAP estimation and posterior sampling: The fitting procedure first seeks a MAP decision list and then performs Monte Carlo sampling from the posterior over list parameters.The parameterization includes list length, ordered rules, and risk parameters.
- MAP estimation and posterior sampling: Simulated annealing optimizes over the discrete space of ordered lists drawn from the finite pre-mined rule set.Each iteration proposes neighboring lists and accepts them according to the objective, proposal, and temperature schedule.
- MAP estimation and posterior sampling: Neighbor proposals use SWAP, REPLACE, ADD, and REMOVE operations, allowing optimization over the full set of itemset-based rule lists without greedy splitting.ADD changes list length by inserting a rule, while REMOVE deletes one.
- Posterior update schedule: The augmentation introduces Exponential variables, Poisson variables, and binary outcomes, enabling direct conditional sampling within the update schedule.For zero outcomes, the scheme sets the corresponding latent count to zero before sampling the augmentation variable.
- Posterior update schedule: Mixing Gibbs and collapsed Metropolis-Hastings steps requires a specific update order to preserve a proper Markov chain with the desired stationary distribution.The paper states that reversing the indicated ordering of the augmentation-variable updates would not be proper.
- Posterior update schedule: The augmented model uses Gibbs updates for rule-associated parameters and collapsed Metropolis-Hastings updates over list structure to improve chain mixing.Variable augmentation preserves the marginal distribution over the original variables and enables Gibbs sampling over selected parameters.
4 Simulation Studies
Simulation studies evaluate recovery of known falling rule lists from independently generated binary rule data. With simulated data generated by a known decision list, simulated annealing recovers the true decision list with high probability.
- Recovery result: With high probability, simulated annealing recovers the true decision list when data are generated by a known decision list.The result concerns the procedure that searches for the MAP decision list.
- Simulation design: The simulations represent observations as binary rule matrices with 100 independently generated rules, each feature set to 1 with probability 0.25.This representation preserves the relevant rule-application structure for binary classification.
- Simulation design: The study generates random decision lists of size 5 with approximately evenly spaced induced probabilities (.84, .70, .54, .40, .25, .14).For each sample size, the procedure is repeated 100 times with independently generated rule matrices, lists, and labels.
5 Experiments
Experiments evaluate Falling Rule Lists on simulated, hospital-readmission, and public-dataset tasks, emphasizing predictive performance, sparsity, and interpretability under strong structural restrictions.
- 5.1 Predicting Hospital Readmissions: Falling Rule Lists were applied to preliminary hospital-readmission data and compared with SVM, logistic regression, CART, random forests, and nFoil-based methods.Evaluation used AUROC from 5-fold cross-validation, with nested tuning for SVM and logistic regression.
- 5.1 Predicting Hospital Readmissions: No accuracy loss was observed for Falling Rule Lists on the readmission dataset, whose fitted lists contained only 6 or 7 rules across training folds.FRL performed on par with the best method despite using few features and a monotonic structure.
- 5.1 Predicting Hospital Readmissions: On the readmission ROC comparisons, nFoil-based methods performed worse, while FRL was on par with the best method; SVM RBF and CART performed poorly.The paper reports that the reason for SVM’s poor performance was unclear, despite cross-validation.
- 5.1 Predicting Hospital Readmissions: The readmission model ranked patients with bed sores and skipped appointments as most likely to be readmitted.The full-data point estimate took 88 seconds to train; its probability column records empirical readmission probabilities and support counts patients classified by each rule.
- 5.2 Performance on Public Datasets: Across several UCI datasets, performance remained on par with other methods and was not often substantially worse despite severe model restrictions.The authors attribute this pattern to avoiding greedy splitting, restricting to mined rules, careful formulation, and optimization.
- 5.2 Performance on Public Datasets: FRL outperformed nFoil-based methods on all public datasets, partly because nFoil produced a much smaller rule set that overly restricted the hypothesis space.The experiments also report running times for 5000 simulated annealing steps for each dataset.
6 Conclusion
The paper presents falling rule lists as interpretable predictive models with potential benefits for decision-making in some domains, especially high-stakes settings where model trust matters.
- The paper presents a new class of interpretable predictive models for decision-making in some domains.
- Falling rule lists could be used by physicians through models printed on laminated cards.
- In high-stakes decisions, falling rule lists help indicate when a model should or should not be trusted.