# Interpretable Two-level Boolean Rule Learning for Classification

arXiv: https://arxiv.org/abs/1511.07361 · HTML: https://mlsanity.com/paper/1511.07361/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Nov 2015.

## Built on by (most cited first, 10 of 10)

- [Learning Accurate and Interpretable Decision Rule Sets from Neural Networks](https://mlsanity.com/paper/2103.02826/) (2021)
- [Model Learning with Personalized Interpretability Estimation (ML-PIE)](https://mlsanity.com/paper/2104.06060/) (2021)
- [Trade-off Between Efficiency and Consistency for Removal-based Explanations](https://mlsanity.com/paper/2210.17426/) (2022)
- [Boolformer: Symbolic Regression of Logic Functions with Transformers](https://mlsanity.com/paper/2309.12207/) (2023)
- [Neural-based classification rule learning for sequential data](https://mlsanity.com/paper/2302.11286/) (2023)
- [Analogies and Feature Attributions for Model Agnostic Explanation of Similarity Learners](https://mlsanity.com/paper/2202.01153/) (2022)
- [Explainable AI using expressive Boolean formulas](https://mlsanity.com/paper/2306.03976/) (2023)
- [On the Effectiveness of Interpretable Feedforward Neural Network](https://mlsanity.com/paper/2111.02303/) (2021)
- [XAI-CF -- Examining the Role of Explainable Artificial Intelligence in Cyber Forensics](https://mlsanity.com/paper/2402.02452/) (2024)
- [Explainable Evidential Clustering](https://mlsanity.com/paper/2507.12192/) (2025)

## Abstract (arXiv)

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.