An optimization approach to learning falling rule lists

By Cynthia Rudin. 2017

41 citations recorded by the source corpus.

A falling rule list is a probabilistic decision list for binary classification, consisting of a series of if-then rules with antecedents in the if clauses and probabilities of the desired outcome ("1") in the then clauses. Just as in a regular decision list, the order of rules in a falling rule list is important -- each example is classified by the first rule whose antecedent it satisfies. Unlike a regular decision list, a falling rule list requires the probabilities of the desired outcome ("1") to be monotonically decreasing down the list. We propose an optimization approach to learning falling rule lists and "softly" falling rule lists, along with Monte-Carlo search algorithms that use bounds on the optimal solution to prune the search space.

Subfields: Computational Theory and Mathematics, Information Systems, Statistical Learning Theory, Algorithms & Complexity, Signal Processing

How researchers see this paper

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

In Computational Theory and Mathematics

In Information Systems

In Statistical Learning Theory

In Algorithms & Complexity

In Signal Processing

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “constraints (Wang and Rudin, 2015a; Chen and Rudin, 2018) enforce decreasing probabilities along a rule list, which make the list more interpretable and useful in practice, but make the optimization problem harder, even though the search space itself becomes smaller.”
Stop Explaining Black Box Machine Learning Models for High Stakes Decisions and Use Interpretable Models Instead (2018, background): “is to create algorithms that solve logical modeling problems in a reasonable amount of time, for practical datasets. We have been extending CORELS to more complex problems, such as Falling Rule Lists [41, 42], and optimal binary-split decision trees, but there is much work to be done on other types ”
Please Stop Explaining Black Box Models for High Stakes Decisions (2018, methodology): “We have been extending CORELS to more complex problems, such as Falling Rule Lists [Wang and Rudin, 2015, Chen and Rudin, 2018], and optimal binary-split decision trees, but there is much work to be done on other types of logical models, with various kinds of constraints.”
Learning Certifiably Optimal Rule Lists (2017, methodology): “CORELS does not automatically rank the subgroups in order of the likelihood of a positive outcome; doing so would require an algorithm such as Falling Rule Lists (Wang and Rudin, 2015a; Chen and Rudin, 2017), which forces the estimated probabilities to decrease along the list.”
Generalized and Scalable Optimal Sparse Decision Trees (2020, methodology): “CORELS has been generalized (A¨ıvodji et al., 2019; Chen & Rudin, 2018) to handle some constraints, but not to the wide variety of different objectives one might want to handle in practice.”
An Interpretable Model with Globally Consistent Explanations for Credit Risk (2018, background): “Some work finds optimal rules [1], but rules are not natural for datasets with many real valued features, like FICO’s data.”
Learning customized and optimized lists of rules with mathematical programming (2018, methodology): “Another follow-up work to this one is that of Chen and Rudin [13], who create a customized branch-and-bound solver for rule lists where the proportions of positive observations are constrained to be monotonically decreasing as we go down the list (called falling rule lists, also see Wang and Rudin, ”
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 .”
Optimized Scoring Systems: Toward Trust in Machine Learning for Healthcare and Criminal Justice (2018, background): “2017, Lakkaraju and Rudin 2017), credit scoring (Chen and Rudin 2018), hospital readmission (Wang and Rudin 2015), and stroke prediction in atrial fibrillation patients (Letham et al.”