Boolean Decision Rules via Column Generation

By Sanjeeb Dash, Oktay Günlük, Dennis Wei. 2018

200 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Optimization & Training, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

In Algorithms & Complexity

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “Some works optimize for individual rules (Dash et al., 2018; Rudin and Shaposhnik, 2019) Over the last few years, great progress has been made on optimizing the combination of accuracy and sparsity for logical models, but there are still many challenges that need to be solved.”
Mathematical optimization in classification and regression trees (2021, background): “…such models (Bertsimas and Shioda 2007; Fang et al. 2013; Fountoulakis and Gondzio 2016; Goodfellow et al. 2016), in interpreting their output (Carrizosa et al. 2020b; Dash et al. 2018; Rudin and Ertekin 2018; Ustun and Rudin 2016) or visualizing it (Carrizosa et al. 2017, 2018a, b, 2020a, c).”
Computing Optimal Decision Sets with SAT (2020, methodology): “blems, where the input is a set of instances with features and, as a label, a class to predict. For these problems, some of the most explainable forms of machine learning formalism are decisions sets [11,12, 15,20,31,34,39]. A decision set is a set of decision rules, each with conditions Cand decisi”
Learning Fair Rule Lists (2019, background): “For instance, when they have small or of reasonable size [44], ∗ Principal contributor. the following models can be considered as interpretable: rules sets [18, 43, 46, 54], rule lists [3, 59, 61], decision trees [9, 51] and scoring systems [39, 57, 64].”
Learning Optimal Classification Trees Using a Binary Linear Program Formulation (2019, background): “( Dash, G¨unl¨uk, and Wei 2018) propose a mathematical optimization model for learning boolean decision rules in disjunctive form or conjunctive normal form.”
Explainable AI: A Review of Machine Learning Interpretability Methods (2020, methodology): “Boolean Rule Column Generation [68] is a technique that utilises Boolean rules, either in their disjunctive normal form (DNF) or in their conjunctive normal form (CNF), in order to create predictive models.”
TED: Teaching AI to Explain its Decisions (2018, background): “yTrades ≤22 AND ExternalRiskEstimate ≥76 AND NetFractionRevolvingBurden ≤78. These two rules, from researchers at IBM Research, predict Y with 72% accuracy and were the winning entry to the challenge [6]. Since the TED approach requires 100% consistency between explanations and labels, we modified t”
Column generation based heuristic for learning classification trees (2020, methodology): “[7] propose an ILP model for learning Boolean decision rules”
Benchmarking and survey of explanation methods for black box models (2021, methodology): “Another interesting method proposed in this toolkit is ted (Hind et al. 2019; Dash et al. 2018), which provides intrinsic local explanations and provides global explanations based on rules.”
Interpretable Companions for Black-Box Models (2020, background): “Many state-of-the-art interpretable models are rule sets [1, 13, 14, 15] or rule lists [8, 9, 16] constructed via various learning algorithms like simulated annealing [17].”
IPBoost - Non-Convex Boosting via Integer Programming (2020, background): “, 2018; Verwer & Zhang, 2019); note that (Dash et al., 2018) also uses a column generation approach.”
Optimal decision trees for categorical data via integer programming (2021, methodology): “The authors of [8] construct a simple classifier in conjunctive normal form which in fact can also be seen as a small depth decision tree.”
One Explanation Does Not Fit All: A Toolkit and Taxonomy of AI Explainability Techniques (2019, methodology): “The published version of BRCG [17] relies on the use of an integer programming solver such as CPLEX, which is often prohibitive due to cost or other barriers to access.”
Questioning the AI: Informing Design Practices for Explainable AI User Experiences (2020, background): “, if-then rules [26, 93, 102] How, Why, Why not, What if”
Rule Covering for Interpretation and Boosting (2020, unknown): “[4] also use column generation to learn Boolean decision rules in either disjunctive normal form or conjunctive normal form.”
Constructing classification trees using column generation (2018, methodology): “In recent years, constructing decision trees by using mathematical programming techniques, especially Integer Optimization, became a hot topic among researchers (see Menickelly et al. (2016), Verwer et al. (2017), Bertsimas and Dunn (2017), Verwer and Zhang (2017), and Dash et al. (2018)).”