Interpretable and Fair Boolean Rule Sets via Column Generation
Authors: Connor Lawless, Sanjeeb Dash, Oktay Gunluk, Dennis Wei; Volume 24, Issue 229, Pages 1-50, 2023.
Abstract
This research focuses on the learning of Boolean rules in disjunctive normal form (DNF), which is equivalent to decision rule sets, as an interpretable model for classification. To balance classification accuracy and rule simplicity, an integer program is formulated. Additionally, the study considers fairness and extends the formulation to include explicit constraints on two measures of classification parity: equality of opportunity and equalized odds. Instead of using heuristic rule mining, column generation (CG) is employed to efficiently search through a vast number of candidate rules. For large data sets, an approximate CG algorithm utilizing randomization is proposed. In comparison to three recently proposed alternatives, the CG algorithm outperforms in terms of the accuracy-simplicity trade-off in 8 out of 16 data sets. When optimized for accuracy, CG is competitive with rule learners specifically designed for this purpose, sometimes discovering considerably simpler solutions that are equally accurate. Compared to other fair and interpretable classifiers, our method is capable of finding rule sets that satisfy stricter fairness criteria with a reasonable compromise in accuracy.
[Abstract]
[PDF]
[Bibliography]