A PHP Error was encountered

Severity: 8192

Message: Non-static method URL_tube::usage() should not be called statically, assuming $this from incompatible context

Filename: url_tube/pi.url_tube.php

Line Number: 13

Learning certifiably optimal rule lists for categorical data

KDD Papers

Learning certifiably optimal rule lists for categorical data

Elaine Angelino (UC Berkeley);Nicholas Larus-Stone (Harvard);Daniel Alabi (Harvard);Margo Seltzer (Harvard University);Cynthia Rudin (Duke)


We present the design and implementation of a custom discrete optimization technique for building rule lists over a categorical feature space. Our algorithm provides the optimal solution, 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. This framework is a novel alternative to CART and other decision tree methods.