Boolean Decision Rules via Column Generation

Understand

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.