Learning Certifiably Optimal Rule Lists for Categorical Data
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.
Code (5)
Similar Papers 제목 키워드 기반
Scalable Rule Lists Learning with Sampling
Learning interpretable models has become a major focus of machine learning research, given the increasing prominence of machine learning in socially important decision-making. Among interpretable models, rule lists are a…
An Optimization Approach to Learning Falling Rule Lists
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 clause…
Binary ClassificationGeneral ClassificationCARD: Certifiably Robust Machine Learning Pipeline via Domain Knowledge Integration
The advent of ubiquitous machine learning (ML) has led to exciting revolution in computing today. However, recent studies have shown that ML, especially deep neural networks (DNNs), are vulnerable to adversarial examples…
BIG-bench Machine LearningSparse Density Trees and Lists: An Interpretable Alternative to High-Dimensional Histograms
We present sparse tree-based and list-based density estimation methods for binary/categorical data. Our density estimation models are higher dimensional analogies to variable bin width histograms. In each leaf of the tre…
Density EstimationVocal Bursts Intensity PredictionComputing the Collection of Good Models for Rule Lists
Since the seminal paper by Breiman in 2001, who pointed out a potential harm of prediction multiplicities from the view of explainable AI, global analysis of a collection of all good models, also known as a `Rashomon set…
Fairness