Interpretable Two-level Boolean Rule Learning for Classification

By Guolong Su, Dennis Wei, Kush R. Varshney, Dmitry M. Malioutov. 2015

55 citations recorded by the source corpus.

This paper proposes algorithms for learning two-level Boolean rules in Conjunctive Normal Form (CNF, i.e. AND-of-ORs) or Disjunctive Normal Form (DNF, i.e. OR-of-ANDs) as a type of human-interpretable classification model, aiming for a favorable trade-off between the classification accuracy and the simplicity of the rule. Two formulations are proposed. The first is an integer program whose objective function is a combination of the total number of errors and the total number of features used in the rule. We generalize a previously proposed linear programming (LP) relaxation from one-level to two-level rules. The second formulation replaces the 0-1 classification error with the Hamming distance from the current two-level rule to the closest rule that correctly classifies a sample. Based on this second formulation, block coordinate descent and alternating minimization algorithms are developed. Experiments show that the two-level rules can yield noticeably better performance than one-level rules due to their dramatically larger modeling capacity, and the two algorithms based on the Hamming distance formulation are generally superior to the other two-level rule learning methods in our comparison. A proposed approach to binarize any fractional values in the optimal solutions of LP relaxations is also shown to be effective.

Subfields: Artificial Intelligence

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

Citations in the corpus

Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI (2019, positive): “In line with rule extraction methods, the work in [215] presents a novel approach to learn rules in CNF (Conjunc-tive Normal Form) or DNF (Disjunctive Normal Form) to bridge from a complex model to a human-interpretable model.”
Learning customized and optimized lists of rules with mathematical programming (2018, methodology): “There are more modern techniques for creating more accurate individual rules (see, for instance, [61]).”
Interpretable Decision Sets: A Joint Framework for Description and Prediction (2016, methodology): “Other methods attempt to construct sets with fewer rules [38, 48, 53], but again do not account for rule overlap.”
Principles and Practice of Explainable Machine Learning (2020, background): “Another approach is introduced in [76], where the authors explore a way to learn rules in either Conjunctive Normal Form (CNF) or Disjunctive Normal Form (DNF).”
ProtoDash: Fast Interpretable Prototype Selection (2017, background): “The strategies involve building rule/decision lists [20, 19], to finding prototypes [12] in an unsupervised manner like us or strictly in a supervised manner as [2], to taking inspiration from psychometrics [10] and learning understandable models.”
TIP: Typifying the Interpretability of Procedures (2017, background): “The authors built a rule list [48] of size at most 4 which we showed to the engineer.”
Explainable Artificial Intelligence: a Systematic Review (2020, methodology): “Linear Programming Relaxation [285, 286] is a method for learning two-level Boolean rules in conjunctive normal form (AND-of-ORs) or disjunctive normal form (OR-of-ANDs) as a type of human-interpretable classification model.”
A Survey on the Explainability of Supervised Machine Learning (2020, background): “Two-Level Boolean Rules are either of the form AND-of-ORs or of the form OR-ofANDs (Su et al., 2015).”
Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives (2018, methodology): “Examples include establishment for rule/decision lists [36,39], prototype exploration [13, 19], developing methods inspired by psychometrics [17] and learning human-consumable models [6].”
Learning sparse two-level boolean rules (2016, background): “In the lower level of a CNF (DNF), disjunctions (conjunctions) of binary features build clauses and in the upper level, the conjunction (disjunction) of the clauses forms the predictor.”