Boolean Decision Rules via Column Generation
It provides an interpretable model for classification, but it is incremental as it builds on existing rule learning with efficiency improvements.
The paper tackles learning Boolean rules (DNF/CNF) for interpretable classification by formulating an integer program to trade accuracy for simplicity, using column generation to efficiently search clauses and bound optimality gaps. It shows the method dominates accuracy-simplicity trade-offs in 7 out of 15 datasets and finds simpler solutions with competitive accuracy.
This paper considers the learning of Boolean rules in either disjunctive normal form (DNF, OR-of-ANDs, equivalent to decision rule sets) or conjunctive normal form (CNF, AND-of-ORs) as an interpretable model for classification. An integer program is formulated to optimally trade classification accuracy for rule simplicity. Column generation (CG) is used to efficiently search over an exponential number of candidate clauses (conjunctions or disjunctions) without the need for heuristic rule mining. This approach also bounds the gap between the selected rule set and the best possible rule set on the training data. To handle large datasets, we propose an approximate CG algorithm using randomization. Compared to three recently proposed alternatives, the CG algorithm dominates the accuracy-simplicity trade-off in 7 out of 15 datasets. When maximized for accuracy, CG is competitive with rule learners designed for this purpose, sometimes finding significantly simpler solutions that are no less accurate.