Source-linked AI summary
Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model
Benjamin Letham, Cynthia Rudin, Tyler H. McCormick, David Madigan
TL;DR
The paper addresses how to build predictive models that remain interpretable while achieving high accuracy. It introduces Bayesian Rule Lists, which use posterior inference over sparse decision lists, and reports performance comparable to leading machine-learning methods, including stronger stroke prediction than established clinical scores.
Problem
Predictive models should be accurate yet interpretable, particularly for medical risk assessment where users need explanations for predictions.
Method
Bayesian Rule Lists use a posterior distribution over permutations of pre-mined if...then... rules with a prior favoring concise, sparse lists.
Results
BRL achieved accuracy comparable to state-of-the-art machine-learning methods; BRL-point significantly outperformed CHADS2 and CHA2DS2-VASc for stroke prediction, while BRL-post matched random forests.
Takeaways & Limitations
BRL provides medical scoring systems with a balance of predictive accuracy and interpretability comparable to established interpretable scores.
Takeaways & Limitations
Interpretable models may not be unique or stable under small data perturbations; the authors recommend the full posterior when stability is desired.
Abstract
from arXiv · showhide
We aim to produce predictive models that are not only accurate, but are also interpretable to human experts. Our models are decision lists, which consist of a series of if...then... statements (e.g., if high blood pressure, then stroke) that discretize a high-dimensional, multivariate feature space into a series of simple, readily interpretable decision statements. We introduce a generative model called Bayesian Rule Lists that yields a posterior distribution over possible decision lists. It employs a novel prior structure to encourage sparsity. Our experiments show that Bayesian Rule Lists has predictive accuracy on par with the current top algorithms for prediction in machine learning. Our method is motivated by recent developments in personalized medicine, and can be used to produce highly accurate and interpretable medical scoring systems. We demonstrate this by producing an alternative to the CHADS$_2$ score, actively used in clinical practice for estimating the risk of stroke in patients that have atrial fibrillation. Our model is as interpretable as CHADS$_2$, but more accurate.
1. Introduction.
The paper develops Bayesian Rule Lists to balance predictive accuracy with human interpretability and computational tractability. It applies this approach to interpretable medical prediction, including an alternative to CHADS2 for stroke risk.
- Interpretability: Decision lists explain predictions through ordered if...then... statements that partition feature space and associate each region with a predicted outcome.In the Titanic example, the list explains lower predicted survival for passengers in 3rd class.
- Method: Bayesian Rule Lists produce a posterior distribution over permutations of if...then... rules, with a hierarchical prior favoring concise lists and short rule conditions.The model starts from a large, pre-mined rule set.
- Contribution: BRL balances accuracy, interpretability, and computation without greedily constructing models through splitting and pruning.Its feasible problem scale includes applications in modern healthcare.
- Computation: Pre-mined rules reduce the search space to rule permutations, so computational complexity depends on the number of rules rather than all feature combinations.This approach can scale with data sparsity when the rule set is sufficiently expressive.
- Contribution: BRL’s sparse prior improves interpretability while reducing computation by concentrating sampling on permutations corresponding to sparse decision lists.The resulting models can match state-of-the-art accuracy while retaining the interpretability of medical scoring systems.
- Application: The stroke application constructs an alternative to CHADS2 using 12,586 patients and 4148 factors, enabling substantially broader feature consideration than the original study.The experiments compare BRL with clinical scores and several state-of-the-art machine-learning algorithms.
2. Bayesian rule lists.
This section defines Bayesian decision lists and BRL’s generative framework, combining ordered antecedents with posterior label distributions and a sparse hierarchical prior. It also describes antecedent mining, posterior inference, prediction, and point-estimate choices.
- Bayesian decision lists: Bayesian decision lists order antecedents so each observation is classified by the first rule that applies, or by a default rule if none applies.Each rule uses a posterior consequent distribution based on observations satisfying that antecedent but no earlier one.
- Antecedent mining: Antecedents are selected from a pre-mined collection, with frequent itemset mining enforcing minimum support and maximum cardinality to favor sufficiently common, concise rules.The experiments use FP-Growth for binary features; equivalent exhaustive itemset algorithms would produce the same eligible antecedents under identical constraints.
- Generative model: BRL generates a decision-list length, antecedent cardinalities, antecedents, and rule parameters before sampling labels according to the first applicable rule.The model includes a default parameter for observations unmatched by all listed antecedents.
- Hierarchical prior: A hierarchical truncated-Poisson prior controls list length and antecedent cardinality, allowing λ and η to encode prior beliefs about model size and rule complexity.When the antecedent collection is large, expected list length is approximately λ; under analogous conditions, expected cardinality is close to η.
- Likelihood: The likelihood multiplies multinomial probabilities for label counts assigned to each rule and the default rule, with consequent parameters corresponding to all list positions.The model can marginalize over these parameters and use posterior samples for inference.
- Posterior prediction and point estimates: BRL supports both point estimates and full posterior prediction, but using the entire posterior for classification sacrifices the decision list’s interpretability.Posterior samples can approximate prediction, while several point estimates may serve as example explanations.
3. Simulation studies.
Simulation studies evaluated whether BRL can recover decision lists from generated data, with posterior concentration on the true list increasing as observations grew. A deterministic Tic–Tac–Toe benchmark further tested classification performance against other methods.
- Simulated data sets: BRL recovered the true decision list when data were generated by a decision-list model.The evaluation used simulation studies and a deterministic data set.
- Simulated data sets: The simulations represented observations with a binary matrix whose columns corresponded to pre-mined rules.An entry was 1 when a rule applied to an observation and 0 otherwise.
- Simulated data sets: Each simulated data set used a random five-rule decision list plus a default rule, with informative rule-specific label distributions.Consequent distributions were sampled from Beta(1/2,1/2).
- Simulated data sets: 600 simulated data sets across six sample sizes were analyzed with three-chain MCMC, and 20,000 samples were sufficient for convergence.The sample sizes were N ∈ {100,250,500,1000,2500,5000}.
- Simulated data sets: As the number of observations increased, posterior mass concentrated on the true decision list.Levenshtein distance measured the minimum substitutions, additions, or removals needed to transform one list into another.
- A deterministic problem: On the deterministic Tic–Tac–Toe Endgame task, greedy C5.0 and CART failed to find a perfect classifier even though decision trees could provide one.The benchmark contained all possible end-board configurations and was evaluated with five-fold cross-validation.
4. Stroke prediction.
Using five-fold cross-validation on Medicaid claims data, BRL produced stroke-risk decision lists with complexity similar to CHADS2 and stronger reported prediction performance than established interpretable scores. The model also remained competitive with machine-learning methods while requiring substantially less training time than SVM and random forests.
- 12,586 patients with atrial fibrillation were analyzed, including 1,786 (14%) who experienced stroke within one year.
- BRL used five-fold cross-validation with 2,162–2,240 pre-mined antecedents per fold and priors chosen for complexity similar to CHADS2.
- All five BRL point-estimate lists had length 7, comparable to CHADS2 and CHA2DS2-VASc, with substantial overlap across folds.The lists emphasized prior stroke history, followed by age and vascular-disease factors.
- With similar complexity and interpretability to CHADS2, BRL point estimates significantly outperformed CHADS2 and CHA2DS2-VASc for stroke prediction.The ROC curves compare BRL-point, CHADS2, and CHA2DS2-VASc across five folds.
- BRL-point was comparable to SVM and not substantially worse than l1-regularized logistic regression and random forests, while BRL-post matched random forests for the best performance.
- BRL MCMC simulation was more than ten times faster than SVM training and more than thirty times faster than random-forest training.The comparison used the same single virtual core and 4 GB of memory; Bayesian CART could not fit because it ran out of memory.
- Additional experiments: In sex-specific analyses, BRL-point again outperformed the other interpretable models, while BRL-post matched random forests for the best performance.
5. Related work and discussion.
The discussion contrasts hand-designed and greedily constructed interpretable models with BRL’s Bayesian, sparse rule-list approach. It situates BRL among related rule, tree, optimization, and Bayesian methods while noting model-stability considerations.
- Hand-designed medical scoring systems use few calculations and heuristically chosen features and coefficients rather than being fully learned from data.
- Unlike greedy trees and associative classifiers, BRL samples Bayesian decision lists whose pre-mined-rule space is smaller than the decision-tree space, easing convergence and local-optima problems.
- Inductive Logic Programming can replace frequent itemset mining, but the authors report substantial performance loss in follow-up experiments.
- Interpretable models are generally non-unique, so the authors recommend using the full posterior when stability under small data perturbations is desired.
- BRL differs from HARM because it learns an ordering of rules, whereas HARM estimates rule probabilities jointly without explicitly learning such an ordering.
- BRL targets a balance among predictive accuracy, interpretability, and computational tractability by favoring surprisingly small predictive models.
6. Conclusion.
The conclusion presents interpretable models as concise and convincing tools for communicating with domain experts and supporting wider implementation. It also identifies predictive medicine and many other technical domains as suitable applications.
- Small, trustworthy rule sets can communicate with domain experts and help machine-learning systems become more widely implemented and trusted.
- Preliminary interpretable models can help domain experts troubleshoot complex models and make them more accurate and better tailored to the domain.
- The authors demonstrate interpretable models in predictive medicine and identify science, engineering, and industry as additional natural application domains.
APPENDIX
The appendix documents implementation settings for comparison algorithms, including tuned support-vector-machine parameters and default or pruned configurations for other libraries.
- Support vector machines used LIBSVM with a radial basis function kernel and grid-searched slack and kernel parameters.The search selected the parameters with the best 3-fold cross-validation performance.
- The SVM parameter grid used CSVM ∈ {2^-2, 2^0, ..., 2^6} and γ ∈ {2^-6, 2^-4, ..., 2^2}.
- C5.0 and CART used R libraries, with C5.0 at default settings and CART using default parameters followed by pruning.
Comparison algorithm implementations.
The comparison-algorithm appendix specifies random-forest tuning and Bayesian CART configuration, alongside an acknowledgement of data-support contributors.
- Random forests tuned mtry with tuneRF, then fit 500 trees using the library default.
- Bayesian CART used the R tgp library’s bcart function with default settings.
- The authors acknowledge Zachary Shahn and the OMOP team for assistance with the data.
SUPPLEMENTARY MATERIAL
The supplementary material provides code for fitting decision lists and BRL point estimates from the stroke prediction experiments.
- Python code is provided to fit decision lists to data, with an example data set.
- BRL point estimates are provided for all cross-validation folds in the stroke prediction experiment.
- Additional BRL point estimates cover female-only and male-only experiments.