Learning Certifiably Optimal Rule Lists: A Case for Discrete Optimization in the 21st Century
Author
Larus-Stone, Nicholas
Metadata
Show full item recordAbstract
We demonstrate a new algorithm, CORELS, for constructing rule lists. It finds the optimal rule list and produces proof of that optimality. Rule lists, which are lists composed of \emph{if-then} statements, are similar to decision trees and are useful because each step in the model's decision making process is understandable by humans. CORELS uses the discrete optimization technique of branch-and-bound to eliminate large parts of the search space and turn this into a computationally feasible problem. We use three types of bounds: bounds inherent to the rules themselves, bounds based on the current best solution, and bounds based on symmetries between rule lists. In addition, we use efficient data structures to minimize the memory usage and runtime of our algorithm on this exponentially difficult problem. Our algorithm demonstrates the feasibility of finding optimal solutions in a search space using discrete optimization on modern computers. Our algorithm therefore allows for the discovery and analysis of optimal solutions to problems requiring human-interpretable algorithms.Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:38811502
Collections
- FAS Theses and Dissertations [6566]
Contact administrator regarding this item (to report mistakes or request changes)