CORELS - Certifiably Optimal Rule Lists

Try it in your browser [Interactive CORELS]

CORELS is an algorithm for constructing Certifiably Optimal RulE ListS to perform (binary) classification on a relational dataset. Rule lists are one-sided decision trees: they give a direct classification whenever a rule’s antecedent evaluates to true. You can think of them as lists composed of if-then-else statements. One rule antecedent can check for multiple features of a sample. Rule lists are useful because each step in the model’s decision making process is understandable by humans, thus ensuring transparency in decision processes. CORELS finds the optimal rule list and certifies its optimality against all feasible alternatives.

We use 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 different types of bounds inherent to the rules themselves, bounds based on the current best solution, and bounds based on symmetries between rule lists. In addition, we design efficient data structures to minimize the memory usage and runtime of our algorithm on this factorially difficult problem. In comparison to black-box models such as neural networks, we show that it is possible to build machine learning models that are more interpretable to humans without sacrificing accuracy.