Learning Certifiably Optimal Rule Lists

By Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo I. Seltzer, Cynthia Rudin. 2017

201 citations recorded by the source corpus.

We present the design and implementation of a custom discrete optimization technique for building rule lists over a categorical feature space. Our algorithm provides the optimal solution, with a certificate of optimality. By leveraging algorithmic bounds, efficient data structures, and computational reuse, we achieve several orders of magnitude speedup in time and a massive reduction of memory consumption. We demonstrate that our approach produces optimal rule lists on practical problems in seconds. This framework is a novel alternative to CART and other decision tree methods.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems, Optimization & Training, Safety, Robustness & Interpretability

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 Optimization & Training

In Safety, Robustness & Interpretability

Citations in the corpus

The accuracy, fairness, and limits of predicting recidivism (2018, background): “This finding is supported by earlier work that showed how to create simple, transparent, and interpretable predictive rules for recidivism prediction ( 7 , 14 , 15 ).”
Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “Some recent works can jointly optimize performance metrics and sparsity for decision lists (Rudin and Ertekin, 2016; Yu et al., 2020a; Angelino et al., 2017, 2018; Aı̈vodji et al., 2019) and decision sets (Wang and Rudin, 2015b; Lakkaraju et al., 2016; Ignatiev et al., 2018; Dash et al., 2018b;…”
FairSight: Visual Analytics for Fairness in Decision Making (2019, background): “A number of studies have focused on interpreting the interaction between inputs and predictions from the original model, by training a secondary interpretable model to capture instance-level [35] or global-level pattern [1, 14].”
Stop Explaining Black Box Machine Learning Models for High Stakes Decisions and Use Interpretable Models Instead (2018, methodology): “Figure 3: This is a machine learning model from the Certifiably Optimal Rule Lists (CORELS) algorithm [32].”
Learning Optimal Decision Trees with SAT (2018, methodology): “This is the case with decision trees [ Bessiere et al. , 2009 ] , but also with rule lists and rule sets [Lakkaraju et al. , 2016; Angelino et al. , 2017].”
Optimal Decision Lists using SAT (2020, methodology): “2020) as well as the only previous approach to optimal sparse decision lists we are aware of (Angelino et al. 2017; Wang et al. 2017).”
Ethical principles in machine learning and artificial intelligence: cases from the field and possible ways forward (2020, methodology): “These exercises (Rudin, 2019; Angelino et al., 2018) showed that it is possible to implement interpretable classification algorithms that lead to a similar accuracy as COMPAS.”
Learning Fair Rule Lists (2019, methodology): “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].”
Optimal Sparse Decision Trees (2019, methodology): “Some of our bounds could be adapted directly from CORELS [2], namely these two: (Hierarchical objective lower bound) Lower bounds of a parent tree also hold for every child tree of that parent (§3.”
Learning customized and optimized lists of rules with mathematical programming (2018, methodology): “A followup paper to the presentwork is that ofAngelino et al [2,3], who build off the constraints here and develop a customized branch-and-bound solver for (unweighted) classification.”
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.”
An optimization approach to learning falling rule lists (2017, background): “A recent work by Angelino et al. (2017) on (non-falling) rule lists showed that it is possible to exhaustively optimize an objective over rule lists, indicating that the space of lists is not as large as one might think. Our search space is a dramatically constrained version of their search space, a”
Learning Optimized Risk Scores (2016, background): “, 2017); sparse decision trees (Angelino et al., 2018; Letham et al., 2015; Lakkaraju et al., 2016; Wang and Rudin, 2015) and other `0-regularized models (Sato et al.”
Actionable Recourse in Linear Classification (2018, background): “1While transparency does not ensure recourse, simple models such as scoring systems and rule-based models [3, 28, 42, 49, 50] have the benefit that they allow end-users to check the feasibility of recourse without a computer.”
A SAT-Based Approach to Learn Explainable Decision Sets (2018, methodology): “Many other representations have been studied, including decision trees [34], rule lists [2], and sums of terms (i.”
Interpretable Companions for Black-Box Models (2020, methodology): “For example, one can train a rule list by using CORELS [8] and SBRL [9].”