Boolean Decision Rules via Column Generation
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 tradeoff 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.
see also the survey [30]) of learning rules one by one and removing "covered" examples, a bottomup strategy of combining more specific rules into more general ones [45,22,41], and associative classification in which association rule mining is followed by rule selection using various criteria [38,36,54,50,12,13]. Broadly speaking, these approaches employ heuristics and/or multiple criteria not directly related to classification accuracy. Moreover, they do not explicitly consider model complexity, a problem that has been noted especially with associative classification. Rule set models have been generalized to rule ensembles [17,29,20], using boosting and linear combination rather than logical disjunction; the interpretability of such models is again not comparable to rule sets. Models produced by logical analysis of data [9,31] from the operations research community are similarly weighted linear combinations.
In recent years, spurred by the demand for interpretable models, several researchers have revisited Boolean and rule set models and proposed methods that jointly optimize accuracy and simplicity within a single objective function. These works however have both restricted the problem and approximated its solution. In [33,52,51], frequent rule miners are first used to produce a set of candidate rules. A greedy forward-backward algorithm [33], simulated annealing [52], or integer programming (IP) (in an unpublished manuscript [51]) are then used to select rules from the candidates. The drawback of rule mining is that it limits the search space while often still producing a large number of rules, which then have to be filtered using criteria such as information gain. [51] also presented an IP formulation (but no computational results) that jointly constructs and selects rules without pre-mining. [46] developed an IP formulation for DNF and CNF learning in which the number of clauses (conjunctions or disjunctions) is fixed. The problem is then solved approximately by decomposing into subproblems and applying a linear programming (LP) method [39], which requires rounding of fractional solutions.
In this paper, we also propose an IP formulation for Boolean rule (DNF or CNF) learning but one that avoids the above limitations. Rather than mining rules, we use the large-scale optimization technique of column generation (CG) to intelligently search over the exponential number of all possible clauses, without enumerating even a pre-mined subset (which can be large). Instead, only those clauses that can improve the current solution are generated on the fly. In practice, our approach solves the IP formulation to provable optimality for smaller datasets. For large datasets we employ an approximate version of CG by randomly selecting samples and candidate features that can be used in a clause. To speed up computation, we also generate additional clauses using a greedy algorithm that still optimizes the correct objective.
A numerical evaluation is presented using 16 datasets, including one from the ongoing FICO Explainable Machine Learning Challenge [1]. In terms of the trade-off achieved between accuracy and rule simplicity, our CG algorithm dominates three other recent proposals on 8 datasets, whereas each of the others dominates on at most two. When optimized for accuracy using cross-validation, CG remains competitive with rule learners such as RIPPER [16] that are designed for maximum accuracy. In some instances it provides significantly less complex models with no sacrifice in accuracy.
We note that CG has been proposed for other machine learning tasks such as boosting [21,7] and hash learning [37]. In [21] however, the pricing problem (see Section 2.2) is solved approximately by a weak learning algorithm ("weak" in the boosting sense), not IP, whereas in [7], pricing can be done tractably through enumeration.
The authors propose a mathematical programming approach to build interpretable machine learning models. In this case, the interpretable model is a system of Boolean rules in disjunctive (or conjunctive) normal form which is constructed using column generation for the linear relaxation of a mixed integer program (MIP) designed to minimize the number of positive samples classified incorrectly and the complexity of the learned system subject to complexity constraints. To remedy the fact that there are exponentially many potential clauses to optimize over, the authors propose a standard column generation approach that prices potential columns to add and solves a secondary integer program to find such potential columns. The authors also note that the column generation can also be done via heuristics or a greedy algorithm. Once the linear programming program is solved or reaches its time limit, the approach then solves the global mixed integer formulation to get a final set of rules. The authors perform many experiments comparing their model to a wide range of benchmark models testing improvements in model complexity as well as accuracy. Several benchmark models are built with only one of these two objectives in mind and the proposed model seems to give good tradeoffs in both objectives.  The goal of having an interpretable decision making model is very well motivated. Additionally, the proposed methodology is very clearly explained and the experimental design is nicely laid out. Overall, the column generation mechanism seems to scale better than previous work and the mathematical programming formulation allows easy access to bound the optimal accuracy and complexity. Furthermore, the mathematical programming formulation is very flexible and allows for various loss formulations as well as differing tradeoffs between accuracy and complexity. This methodology is seemingly extensible enough to account for other desired traits of a machine learning model such as fairness constraints. The approach can also be extended to explicitly trade off complexity and accuracy. Finally, the approach seems to do very well against several benchmark in terms of test accuracy and model complexity.   For these reasons, I recommend that this paper be accepted, and hope the authors can improve it by addressing the following questions/suggestions:  - The MIP is missing bounds on the 0 <= \xi_i <= 1 (same for \delta_i in the pricing problem). While you are right that you don’t need \xi_i \in \{0,1\}, if you don’t include lower/upper bounds, then if for a given i in constraint (2), the sum of w_k variables is large, then the optimal solution would make the corresponding \xi_i negative (to make the objective smaller) while maintaining feasibility of constraint (2). I think you probably have the bounds right in the implementation, but not in the text. - Derivation of the pricing problem: since this IP approach may be new to many NIPS readers, it may be better to give a more gentle derivation of the pricing problem, defining reduced costs; just a suggestion.  - Tables 1 and 2 are somewhat difficult to read and would benefit from either bolding the best value in the row or writing the value of the best entry in a final column. It would also be helpful to explain some of the more interesting rows such as the tic-tac-toe dataset having 100 test accuracy with 0.0 standard error for CG while the random forest has less accuracy. This could be resolved by reporting training accuracy or demonstrating that the CG approach enables better generalization due to its lack of complexity.  - It would be helpful to demonstrate the ability for the system to give lower bounds on complexity by reporting these metrics for the different experiments. - Can you elaborate on the FICO example end of page 7? What are these features, and why is this an intuitive rule? Without a few sentences explaining it, the example is kind of useless. - The related work section could include brief references to work that uses column generation for machine learning tasks, examples below.  [1] Demiriz, Ayhan, Kristin P. Bennett, and John Shawe-Taylor. "Linear programming boosting via column generation." Machine Learning 46.1-3 (2002): 225-254. [2] Bi, Jinbo, Tong Zhang, and Kristin P. Bennett. "Column-generation boosting methods for mixture of kernels." Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2004. [3] Li, Xi, et al. "Learning hash functions using column generation." arXiv preprint arXiv:1303.0339 (2013).