Source-linked AI summary
Scalable Bayesian Rule Lists
Hongyu Yang, Cynthia Rudin, Margo Seltzer
TL;DR
Decision-tree methods use greedy splitting and pruning, whereas this paper seeks accurate, interpretable, and computationally practical probabilistic rule lists. SBRL globally optimizes the Bayesian Rule List posterior over pre-mined frequent patterns using bounds and computational efficiencies, achieving much faster computation and strong example-dataset performance. Its scope is limited by the frequent-pattern support approximation for rule-list leaves.
Problem
Greedy splitting and pruning in decision trees can make early errors difficult to undo and produce long or less accurate models, motivating globally optimized interpretable rule lists.
Method
SBRL optimizes the Bayesian Rule List posterior over pre-mined frequent patterns, using posterior bounds and computational reuse to make global rule-list optimization efficient.
Results
Over two orders of magnitude faster than previous work, SBRL also achieved perfect mushroom-dataset out-of-sample accuracy and higher adult-dataset out-of-sample AUC than heavily tuned CART or C4.5.
Takeaways & Limitations
SBRL is intended as an interpretable decision aid for humans rather than a competitor to black-box classifiers, with global optimization supporting high-quality sparse rule lists.
Takeaways & Limitations
The method assumes each rule-list leaf captures at least a bounded number of observations, restricting antecedents to frequent patterns.
Abstract
from arXiv · showhide
We present an algorithm for building probabilistic rule lists that is two orders of magnitude faster than previous work. Rule list algorithms are competitors for decision tree algorithms. They are associative classifiers, in that they are built from pre-mined association rules. They have a logical structure that is a sequence of IF-THEN rules, identical to a decision list or one-sided decision tree. Instead of using greedy splitting and pruning like decision tree algorithms, we fully optimize over rule lists, striking a practical balance between accuracy, interpretability, and computational speed. The algorithm presented here uses a mixture of theoretical bounds (tight enough to have practical implications as a screening or bounding procedure), computational reuse, and highly tuned language libraries to achieve computational efficiency. Currently, for many practical problems, this method achieves better accuracy and sparsity than decision trees; further, in many cases, the computational time is practical and often less than that of decision trees. The result is a probabilistic classifier (which estimates P(y = 1|x) for each x) that optimizes the posterior of a Bayesian hierarchical model over rule lists.
1. Introduction
SBRL globally optimizes probabilistic rule lists to address the limitations of greedy decision-tree construction, using statistical approximations, computational reuse, and theoretical bounds for speed. It achieves substantially faster computation and strong out-of-sample performance in example datasets.
- Decision trees rely on greedy splitting and pruning, so early mistakes are difficult to undo and pruning can reduce accuracy.
- SBRL optimizes the Bayesian Rule List posterior over pre-mined frequent patterns, producing probabilistic predictions P(y = 1|x).The frequent-pattern approximation narrows the optimization problem to pre-mined rules and their order.
- Tight analytical posterior bounds screen association rules and bound the optimal solution, while computational reuse avoids recomputing unchanged portions of rule-list evaluations.
- Over two orders of magnitude faster than the previous best code, SBRL showed major computational gains in controlled experiments.
- Perfect out-of-sample accuracy was achieved on the UCI mushroom dataset in about 9 seconds, while the adult model took approximately 18 seconds and exceeded heavily tuned CART and C4.5 in out-of-sample AUC.
2. Review of Bayesian Rule Lists of Letham et al. (2015)
Bayesian Rule Lists mine frequent antecedents first, then learn an ordered rule list whose Bayesian posterior combines a beta-binomial likelihood with priors controlling list and rule complexity. Each observation receives the probability associated with its first matching rule or the default rule.
- Each rule predicts with a beta-binomial model, and observations are assigned to the first antecedent they satisfy; unmatched observations use the default rule.
- Bayesian Rule Lists are associative classifiers: antecedents are mined from the database before selecting the rules and their order.The difficult step is learning the rule list rather than mining sufficiently supported conditions.
- The likelihood increases when a rule’s captured observations are concentrated in one class rather than split between classes.
- The prior controls list length, rule cardinality, and antecedent choice through hyperparameters λ and η, with α typically set to avoid favoring either label.
- The algorithm selects rules and their order from the pre-mined set A by optimizing the posterior, proportional to likelihood times prior.
3. Representation
SBRL accelerates repeated rule-list evaluation by representing captures as bit vectors and reusing unchanged computations during MCMC updates. A controlled ablation shows that progressively optimized implementations substantially reduce runtime.
- MCMC proposes neighboring rule lists by adding, removing, or swapping rules, repeatedly evaluating each proposal’s posterior.
- Most construction time is spent determining which observations each rule captures under a particular ordering.
- Bit vectors encode each rule’s true observations, replacing set operations with memory- and computation-efficient logical operations.
- Because each observation is captured by only its first matching rule, unchanged portions of a rule list can be reused when rules are modified.
- Four implementations progress from original Python sets to Python bit operations, gmpy, and C with GMP multiprecision integers.
- Over two orders of magnitude faster than the original optimized Python code, the final implementation reduced runtime under matched adult-dataset experiments.
4. Theoretical Bounds with Practical Implications
The paper derives two bounds that make Bayesian rule-list optimization more tractable: one limits MAP list length, while the other prunes prefixes that cannot yield an optimum. Demonstrations show how these bounds screen candidate lists using posterior comparisons.
- Theoretical bounds: Two bounds restrict optimization: one upper-bounds MAP rule-list length, and the other eliminates prefixes that cannot produce a MAP solution.The first narrows the search space by list size; the second removes entire regions of the rule space.
- 4.1 Upper Bound on the Number of Rules in the List: The bound is constructed by exhausting binary antecedents from smaller to larger sizes, using the resulting b sequence to lower-bound remaining rule counts.For P features, the number of possible binary rules at each size can be calculated directly.
- 4.1 Upper Bound on the Number of Rules in the List: Theorem 1 derives an upper bound m_max on the size m* of any MAP rule list.The bound depends on the number of features and prior parameters λ, η, and α.
- 4.1 Upper Bound on the Number of Rules in the List: With P = 10, λ = 3, α0 = α1 = 1, and approximately 100 positive and 100 negative observations, Theorem 1 permits at most about 36 rules.Figure 5 plots the corresponding upper bounds for P = 10 and P = 15.
- 4.2 Prefix Bound: Theorem 2 prunes a prefix dp when its best possible posterior cannot exceed the current best posterior v*.This branch-and-bound step stops exploration of every rule list beginning with that prefix.
- 4.2 Prefix Bound: In implementation, rejecting an initial rule under Theorem 2 can provide a full order-of-magnitude speedup in some cases.The algorithm discards the initial rule and samples a new one when the bound proves it cannot begin an optimal list.
5. Experiments
The experiments compare SBRL with uninterpretable classifiers and greedy interpretable methods across accuracy, sparsity, and computation time. Across datasets, SBRL generally occupies a favorable accuracy–sparsity frontier with practical runtimes.
- Experimental setup: SBRL is evaluated against logistic regression, SVM RBF, random forests, boosted trees, CART, C4.5, RIPPER, CBA, and CMAR.The comparisons use 10-fold cross-validation and assess AUC, sparsity, and computation time.
- Tic tac toe: SBRL sacrifices less AUC than CART and produces sparser solutions than methods such as C4.5 on tic tac toe.Other methods, including random forests, SVM, logistic regression, and boosting, do not provide sparse solutions.
- Tic tac toe: SBRL defines the tic tac toe AUC–sparsity efficient frontier, while tested CART and C4.5 settings do not reach it.The scatter plot contains one SBRL point per fold and many points for CART and C4.5 parameter settings.
- Tic tac toe: SBRL’s average runtime on tic tac toe is three quarters of a second.The reported models come from the first three cross-validation folds.
- Adult: On adult, untuned sparse SBRL slightly trails several uninterpretable methods in AUC but dominates CART and C4.5, with runtime around 18 seconds.Approximately 14 seconds of the adult runtime were spent on MCMC iterations.
- Mushroom and nursery: On mushroom and nursery, SBRL obtains near-perfect or perfect accuracy while remaining sparse and computationally practical.Mushroom has several perfect solutions between 8 and 22 rules, while nursery places SBRL on the optimal accuracy–sparsity frontier without tuning.
- Overall findings: Across datasets, SBRL produces reliable and sparse results with reasonable, user-adjustable runtimes.The paper contrasts reliability with CART and sparsity with C4.5.
6. Scalability
The scalability experiment tests SBRL on substantially larger USCensus1990 rule-mining problems and compares its runtime with CART. Runtime is similar for the smaller large-scale problem, while the larger problem takes 2.5 hours for SBRL.
- Scalability: SBRL is tested on 1 million observations with approximately 1 thousand rules and on about 50 thousand observations with 50 thousand rules.These are designated problems (A) and (B), respectively.
- Scalability: For problem (A), SBRL and CART have similar runtimes.The experiment uses USCensus1990 data.
- Scalability: 2.5 hours is SBRL’s runtime for problem (B), which the paper describes as not prohibitive for important problems.Problem (B) uses about 50 thousand observations and 50 thousand rules.
7. Related Works and Discussion
The discussion positions SBRL as a globally optimized, probabilistic rule-list competitor to decision trees and connects it to broader rule-learning and interpretable-modeling work. Its optimization framework also supports constrained rule-list variants beyond ordinary outcome prediction.
- Relation to decision trees: Rule lists can represent decision-tree leaves sequentially, making them direct competitors to CART with comparable model capacity.The paper describes rule lists as an automatic type of decision tree.
- Extensions: Global optimization enables constrained models such as Falling Rule Lists and Causal Falling Rule Lists.These variants can target high-probability subgroups or model conditional treatment effects.
- Applications: Rule lists are used in applications including text processing, treatment-regime discovery, and medical risk assessment.The discussion identifies these as existing application areas for rule lists and their variants.
- Relation to prior work: SBRL differs from greedy decision-list and tree methods by globally optimizing over pre-mined rules.The related work spans inductive logic programming, associative classification, and Bayesian rule-list methods.
- Theoretical context: The VC dimension of rule lists built from |A| predefined rules is exactly |A|, paralleling linear models with |A| features.Eliminating rules can reduce this effective complexity.
- Theoretical context: Unlike a later extension that certifies optimality without probabilistic predictions, SBRL optimizes a probabilistic model whose optimality is harder to prove.The paper states that finding optimal solutions is approximately equally difficult, but proving SBRL optimality is more difficult.
Conclusion
SBRL targets interpretable decision support with globally optimized rule lists rather than greedy tree procedures. This improves the reliability of high-quality solutions, while potentially requiring more computation.
- SBRL is intended for human-facing decision aids where model interpretability supports trust and data-driven decisions.
- Unlike CART and C4.5, SBRL avoids greedy splitting and pruning, more reliably computing high-quality solutions at a possible computational cost.
Code
The authors provide SBRL source code through GitHub and an R package through CRAN.
- SBRL code is available on GitHub, with an R package available through CRAN.
Appendix A. Proof of Theorem 1
Theorem 1 bounds the length of an optimal rule list by showing that sufficiently long lists have lower posterior than the empty list. The proof uses the posterior relationship between a MAP list and the trivial rule list.
- Any rule list with more than mmax rules has lower posterior than the trivial empty rule list and therefore cannot be a MAP rule list.
- The optimal rule-list length is bounded using the first m terms of the b_j values, with an additional limit of 2P −1 for including all possible rules.
Appendix B. Proof of Theorem 2
Theorem 2 derives posterior upper bounds by replacing imperfect rules with hypothetical perfect rules and consolidating same-label perfect rules. These bounds support branch-and-bound elimination of prefixes that cannot lead to a MAP solution.
- Definitions and lemmas: A perfect rule has no captured observations from at least one class and therefore correctly classifies every observation it captures.
- Definitions and lemmas: Lemma 1 shows that replacing an imperfect rule with two hypothetical perfect rules capturing the same observations improves likelihood under α0 = α1 = 1.
- Definitions and lemmas: Lemma 2 states that consolidating same-label perfect rules into one rule improves likelihood when the consolidated rule captures their combined observations.
- Posterior bound construction: The proof combines both lemmas so only one hypothetical perfect rule for each class remains, allowing the likelihood of the hypothetical list to be decomposed into rule-level terms.
- Posterior bound construction: The posterior bound factors into priors over rule-list number and sizes together with likelihood terms for the prefix and hypothetical perfect rules.
- Posterior bound construction: The rule-count prior is maximized near the Poisson parameter λ when feasible; otherwise, it is maximized at the current prefix length p.
- Prefix screening: Branch-and-bound eliminates every prefix whose best possible posterior upper bound is below the best posterior already found, proving that prefix cannot lead to a MAP solution.