Abstract
We present the design and implementation of a custom discrete optimizationtechnique for building rule lists over a categorical feature space. Ouralgorithm produces rule lists with optimal training performance, according tothe regularized empirical risk, with a certificate of optimality. By leveragingalgorithmic bounds, efficient data structures, and computational reuse, weachieve several orders of magnitude speedup in time and a massive reduction ofmemory consumption. We demonstrate that our approach produces optimal rulelists on practical problems in seconds. Our results indicate that it ispossible to construct optimal sparse rule lists that are approximately asaccurate as the COMPAS proprietary risk prediction tool on data from BrowardCounty, Florida, but that are completely interpretable. This framework is anovel alternative to CART and other decision tree methods for interpretablemodeling.