Learning customized and optimized lists of rules with mathematical programming

By Cynthia Rudin, Ş. Ertekin. 2018

56 citations recorded by the source corpus.

We introduce a mathematical programming approach to building rule lists, which are a type of interpretable, nonlinear, and logical machine learning classifier involving IF-THEN rules. Unlike traditional decision tree algorithms like CART and C5.0, this method does not use greedy splitting and pruning. Instead, it aims to fully optimize a combination of accuracy and sparsity, obeying user-defined constraints. This method is useful for producing non-black-box predictive models, and has the benefit of a clear user-defined tradeoff between training accuracy and sparsity. The flexible framework of mathematical programming allows users to create customized models with a provable guarantee of optimality. The software reviewed as part of this submission was given the DOI (Digital Object Identifier) https://doi.org/10.5281/zenodo.1344142.

Subfields: Artificial Intelligence, Information Systems, Mathematical Optimization

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 Information Systems

In Mathematical Optimization

Citations in the corpus

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;…”
Optimal Decision Lists using SAT (2020, methodology): “…rules which are meaningful in the context of their position in the target decision list, but could by themselves not provide valuable information on the training data, and therefore would not have been mined by the approach of (An-gelino et al. 2017; Rudin and Ertekin 2018; Angelino et al. 2018).”
Generalized and Scalable Optimal Sparse Decision Trees (2020, methodology): “…have been used from the 1990’s (Bennett, 1992; Bennett & Blue, 1996) to the present (Verwer & Zhang, 2019; Blanquero et al., 2018; Nijssen et al., 2020; Bertsi-mas & Dunn, 2017; Rudin & Ertekin, 2018; Menickelly et al., 2018; Vilas Boas et al., 2019), but these generic solvers tend to be slow.”
Learning Optimized Risk Scores (2016, neutral): “[88] Rudin, Cynthia and S ̧eyda Ertekin.”
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 .”
Systems Optimizations for Learning Certifiably Optimal Rule Lists (2018, background): “Our previous work presents a branch-and-bound search strategy, full description of CORELS, and proofs of the bounds we use [1, 6].”