Scalable Bayesian Rule Lists

By Hongyu Yang, Cynthia Rudin, Margo I. Seltzer. 2016

232 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Information Systems

In Probabilistic & Bayesian Methods

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “Sometimes decision lists or decision sets are optimized by sampling (Letham et al., 2015; Yang et al., 2017; Wang and Rudin, 2015a), providing a Bayesian interpretation.”
On the Art and Science of Machine Learning Explanations (2018, background): “They have developed several types of rule-based models [3], [31], linear model variants [28], and many other novel algorithms suitable for use in high stakes, mission-critical prediction and decision-making scenarios.”
Learning Certifiably Optimal Rule Lists (2017, methodology): “Some exploration of the search space is done by Bayesian decision tree methods [7, 8, 12] and Bayesian rule-based methods [25, 45].”
Learning Fair Rule Lists (2019, background): “[4, 9, 43, 57]. For instance, when they have small or of reasonable size [44], ∗Principal contributor. the following models can be considered as interpretable: rules sets [18, 43, 46, 54], rule lists [3, 59, 61], decision trees [9, 51] and scoring systems [39, 57, 64]. For the rest of the paper, we ”
Optimal Sparse Decision Trees (2019, methodology): “Our work builds upon the CORELS algorithm [1, 2, 13] and its predecessors [14, 21], which create optimal decision lists (rule lists).”
Learning customized and optimized lists of rules with mathematical programming (2018, methodology): “This work follows a line of work on optimal rule lists, motivated by Bayesian approaches [37,57,58,70,73], with earlier closely related ideas in the PhD thesis of Allison Chang [12], with direct follow-up work to this paper in Angelino et al.”
Boolean Decision Rules via Column Generation (2018, background): “Rule sets stand in contrast to decision lists [44, 35, 49, 3, 34, 53], where rules are ordered in an IF-ELSE sequence, and decision trees [11, 43, 6], where they are organized into a tree structure.”
Interpreting Blackbox Models via Model Extraction (2017, methodology): “inal test set. All results are medians over 20 random train/test splits. We compare to CART trees (Breiman et al.,1984) and born-again trees (Breiman & Shang,1996), rule lists (Letham et al.,2015;Yang et al., 2017), and decision sets (Lakkaraju et al.,2016;2017). The born-again algorithm require”
A Provable Algorithm for Learning Interpretable Scoring Systems (2018, background): “A similar idea, also based on Bayesian learning is considered by [16, 30] where the main motivation is to construct simple rules which are interpretable by human experts and can be used by healthcare providers.”
The explanation game: a formal framework for interpretable machine learning (2020, unknown): “Several iML solutions are built on recursive partitioning (Guidotti et al., 2018; Ribeiro et al., 2018; Yang et al., 2017) – the statistical procedure that produces rule lists – and a growing number of psychological studies suggests that users find such explanations especially intelligible (Lage et ”
The Price of Interpretability (2019, background): “Decision trees [7, 3] are considered interpretable for their discrete structure and graphical visualization, as are close relatives including rule lists [27, 36], decision sets [25], and case-based reasoning [21].”
Hybrid Decision Making: When Interpretable Models Collaborate With Black-Box Models (2018, background): “, [17, 22, 28, 34], Rule Lists [3, 36]), scoring systems [14, 32, 37], case based models [1, 4, 13], and etc.”
Interpretable Companions for Black-Box Models (2020, methodology): “For example, one can train a rule list by using CORELS [8] and SBRL [9].”
Evaluating Explanations by Cognitive Value (2018, unknown): “Second, we compare three state-of-the-art explanation methods namely Scalable Bayesian Rule Lists [7], Random Forests, and Causal models [5] in terms of their cognitive value to the business owner.”
Learning Interpretable Models with Causal Guarantees (2019, unknown): “…(Tib-shirani, 1996; Ustun and Rudin, 2016), generalized additive models (Lou et al., 2012; Caruana et al., 2015), rule lists (Wang and Rudin, 2015; Yang et al., 2017; Angelino et al., 2017), decision sets (Lakkaraju et al., 2016), and programs (Ellis et al., 2015; Verma et al., 2018; Valkov et…”
A Survey on the Explainability of Supervised Machine Learning (2020, methodology): “…et al. (2011) BLM Classification Rule-based Letham et al. (2012) BRL Classification Rule-based Letham et al. (2015) (S)BRL Classification Rule-based Yang et al. (2016) FRL Classification Rule-based Wang and Rudin (2015) IDS Classification Rule-based Lakkaraju et al. (2017) BRS Classification…”
RuleMatrix: Visualizing and Understanding Classifiers with Rules (2018, background): “There exist various algorithms that can construct a list of rules from training data [11,23,45,47].”
On Explaining Decision Trees (2020, background): “Motivated by this perception, there has been extensive work on learning DTs (and related logic ML models) with properties deemed important for interpretability, e.g. number of nodes, maximum/average depth, etc. [2,68,25,32,1,7,57,24,26,70,67,58,44,30,17,5,73,35,4,78,69,10,34,72,71,36,46,11,45] 2 .”