Learning Certifiably Optimal Rule Lists for Categorical Data

Abstract

We present the design and implementation of a custom discrete optimization technique for building rule lists over a categorical feature space. Our algorithm produces rule lists with optimal training performance, according to the regularized empirical risk, 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. Our results indicate that it is possible to construct optimal sparse rule lists that are approximately as accurate as the COMPAS proprietary risk prediction tool on data from Broward County, Florida, but that are completely interpretable. This framework is a novel alternative to CART and other decision tree methods for interpretable modeling.

A short version of this work appeared in KDD '17 as "Learning Certifiably Optimal Rule Lists"

References in corpus (6)

• European Union regulations on algorithmic decision-making and a "right to explanation"
• Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model
• Deep Learning for Case-Based Reasoning through Prototypes: A Neural Network that Explains Its Predictions
• Or's of And's for Interpretable Classification, with Application to Context-Aware Recommender Systems
• Causal Falling Rule Lists
• A Minimax Surrogate Loss Approach to Conditional Difference Estimation

Cited by in corpus (10)

• FairSight: Visual Analytics for Fairness in Decision Making
• Entropy-based Logic Explanations of Neural Networks
• Learning Interpretable Rules for Scalable Data Representation and Classification
• Efficient Learning of Interpretable Classification Rules
• QCBA: Improving Rule Classifiers Learned from Quantitative Data by Recovering Information Lost by Discretisation
• A Framework for Democratizing AI
• Learning Hybrid Interpretable Models: Theory, Taxonomy, and Methods
• Scalable Rule Lists Learning with Sampling
• Visualizing Image Content to Explain Novel Image Discovery
• Thirteen Simple Steps for Creating An R Package with an External C++ Library