Timezone: »

 
Spotlight
Boolean Decision Rules via Column Generation
Sanjeeb Dash · Oktay Gunluk · Dennis Wei

Thu Dec 06 06:45 AM -- 06:50 AM (PST) @ Room 517 CD
in Thu Track 3 -- Session 1 »

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 8 out of 16 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.

Author Information

Sanjeeb Dash (IBM Research)
Oktay Gunluk (IBM Research)
Dennis Wei (IBM Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors