Source-linked AI summary
Interpretable Two-level Boolean Rule Learning for Classification
Guolong Su, Dennis Wei, Kush R. Varshney, Dmitry M. Malioutov
TL;DR
The paper addresses how to learn human-interpretable two-level Boolean classifiers while balancing classification accuracy and rule simplicity. It formulates the problem using error or Hamming-distance objectives, develops optimization algorithms and a binarization method, and finds that two-level rules and Hamming-distance algorithms generally perform favorably in the reported comparisons.
Problem
Learning Boolean classifiers that provide human-interpretable reasons while maintaining both high classification accuracy and sparse rules remains a central modeling challenge.
Source: §1 · p. 1Method
The paper introduces error-and-sparsity and Hamming-distance formulations, extends LP relaxation to two-level rules, develops block coordinate descent and alternating minimization, and proposes redundancy-aware binarization.
Source: §1 · pp. 1–2, §6 · p. 8Results
Two-level rules have lower error rates and more flexible accuracy–simplicity tradeoffs than one-level rules on certain complex datasets, while the Hamming-distance algorithms generally outperform compared alternatives.
Source: §6 · p. 9Takeaways & Limitations
Two-level Boolean rules provide a higher-capacity interpretable modeling option, with algorithm choice depending on the required sparsity level.
Source: §6 · p. 9Too many clauses may cause overfitting, and the optimal number of clauses may depend on dataset complexity.
Source: §5.2 · p. 8, §6 · p. 9
Abstract
from arXiv · showhide
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.
1 Introduction
The paper frames two-level Boolean rules as interpretable classifiers that jointly target accuracy and sparsity, introducing optimization formulations and algorithms for learning them. Experiments report lower error and more flexible accuracy–simplicity tradeoffs than one-level rules on certain complex datasets.
1 Introduction
- Two-level Boolean rules combine lower-level conjunctions or disjunctions into an interpretable predictor, such as an OR-of-ANDs DNF rule.The included features provide human-readable reasons for predictions, which matters in applications where decision makers must understand and justify model outputs.Source: §1 · p. 1
- The paper jointly optimizes classification accuracy and interpretability, measuring simplicity by the total number of features used.It introduces one formulation combining classification errors with sparsity and another based on Hamming distance to a closest correctly classifying rule.Source: §1 · p. 1
- The proposed methods include an LP-relaxation approach, block coordinate descent, alternating minimization, and binarization of fractional LP solutions.The latter three components address optimization of the Hamming-distance formulation and conversion of fractional solutions into binary rules.Source: §1 · pp. 1–2
- Two-level rules achieve noticeably lower error rates and more flexible accuracy–simplicity tradeoffs than one-level rules on certain complex datasets.The two Hamming-distance algorithms generally outperform the other compared two-level learning methods, while the new binarization method is effective.Source: §1 · p. 2
2 Review of Existing Work
Prior work established optimization methods for one-level Boolean rules, while two-level rules offer substantially greater modeling capacity but raise interpretability and optimization challenges. Existing alternatives include greedy, clustering, Bayesian, logical-analysis, PAC-learning, and circuit-optimization approaches, each differing in objective, assumptions, or rule representation.
2.1 One-level Rule Learning in
- One-level Boolean rules use only a conjunction or disjunction of selected features, with mixed-integer and LP formulations balancing classification accuracy against sparsity.The LP relaxation replaces binary feature-selection variables with continuous values and is efficiently solvable, with exactness requiring sufficient conditions.Source: §2.1 · p. 2
2.2 Two-level Rule Learning
- Two-level rules have significantly larger modeling capacity than one-level rules and can represent any Boolean function when feature negations are included.This expressive power motivates two-level learning while making sparse, interpretable representations important.Source: §2.2 · p. 2
- Existing rule-set methods include a greedy set-covering procedure and boosting, but boosting combines rules rather than producing a single two-level rule.The set-covering method trains clauses sequentially and removes samples already assigned a prediction, leaving room for improvement because it is one-pass and greedy.Source: §2.2 · p. 2
- Hamming Clustering learns DNF rules by greedily clustering nearby same-category samples, whereas the paper’s methods are top-down and treat the dataset more globally.Prior experiments appear to associate Hamming Clustering with a high number of clauses, which can hinder interpretability.Source: §2.2 · pp. 2–3
- Related approaches differ in representation and assumptions: Bayesian methods use approximate inference, Logical Analysis of Data often combines patterns, PAC learning assumes noiseless on-demand samples, and circuit optimization matches truth tables exactly.These distinctions separate the paper’s noisy-data rule-learning setting from neighboring fields.Source: §2.2 · p. 3
3 Problem Formulation
The paper formulates learning sparse two-level Boolean rules, primarily CNF, while providing a transformation for DNF, and introduces both 0-1-error and minimal-Hamming-distance accuracy costs.
3 Problem Formulation
- Two-level CNF rules use OR-based clauses at the lower level and an AND across clauses at the upper level, with R clauses and binary feature-selection variables.Negated features are assumed available as additional inputs.Source: §3 · p. 3
- A fixed clause budget can be sparsified by disabling clauses through an always-true feature, trading possible accuracy loss for fewer active clauses.The corresponding always-true-feature variables can receive a lower or zero sparsity cost.Source: §3 · p. 3
- DNF learning is reduced to CNF learning by negating all features and labels, then reconstructing the DNF rule with the learned feature-selection variables.The paper therefore focuses Sections 3 and 4 on CNF.Source: §3 · p. 3
3.1 Formulation with 0-1 Error Cost
- The first formulation minimizes total 0-1 classification errors plus a sparsity penalty equal to the number of selected features across clauses.Its combinatorial structure and symmetric clauses create challenges, including inefficient duplicate clauses.Source: §3.1 · p. 3
3.2 Formulation with Minimal Hamming Dis-
- The second formulation replaces 0-1 error with each sample’s minimal Hamming distance to a correctly classifying CNF rule, measuring the smallest number of feature-selection changes needed for correction.This finer-grained cost can favor a rule that is closer to correctness even when both current rules misclassify the sample.Source: §3.2 · p. 4
- Ideal clause outputs v_i,r use a ternary {0, 1, DC} representation consistent with the label, allowing each clause to train on a different subset of samples.For negative samples, at least one clause must output 0; for positive samples, every clause must output 1.Source: §3.2 · p. 4
- For positive samples, the minimal Hamming distance equals the number of clauses currently outputting 0, while negative-sample costs are obtained by minimizing clause-level changes over clauses.For a negative sample, the formulation considers the minimum distance for making one clause output 0.Source: §3.2 · p. 4
- The Hamming-distance formulation has a non-convex continuous relaxation when R > 1 because of the minimum over clauses, although an equivalent formulation with auxiliary clause-output variables supports later algorithmic treatment.Setting R = 1 recovers the one-level formulation, while eliminating the auxiliary variables recovers the Hamming-distance formulation.Source: §3.2 · p. 4
4 Optimization Approaches
The paper develops LP, block coordinate descent, alternating minimization, and binarization approaches for optimizing two-level Boolean rules. These methods address fractional LP solutions and decompose Hamming-distance optimization into tractable clause updates.
4 Optimization Approaches
- The optimization framework generalizes one-level LP relaxation to two-level rules, then adds Hamming-distance algorithms and a binarization procedure for fractional solutions.The LP formulation composes convex and concave interpolations of AND and OR; relaxing variables to [0, 1] yields a linear program.Source: §4 · p. 5, §4.1 · p. 5
4.1 Two-level Linear Programming Relaxation
- The LP relaxation selects interpolation directions according to the sample label, but can produce fractional variables and artificially low error-cost values.For positive samples the concave interpolation is used, whereas negative samples use the convex interpolation; the interpolation gap may loosen the relaxation.Source: §4.1 · p. 5
4.2 Block Coordinate Descent Algorithm
- Block coordinate descent updates one clause at a time with the remaining clauses fixed, removes already correctly handled negative samples, and solves the residual problem using one-level rule learning.Clause updates may be cyclic, random, or greedy; the experiments use greedy updates and set-covering initialization.Source: §4.2 · pp. 5–6
4.3 Alternating Minimization Algorithm
- Alternating minimization alternates ideal clause-output updates with clause updates, which decouple into parallel one-level learning problems after samples assigned DC are removed.Negative-sample ties are assigned using clause cluster centers and closest ℓ1 distance.Source: §4.3 · p. 6
4.4 Redundancy Aware Binarization
- Redundancy-aware binarization converts fractional LP solutions by selecting low-cost non-redundant feature combinations, while accounting for nested, complementary, and zigzag redundancy sets.The method sweeps non-redundant combinations within each continuous feature, then sequentially processes features ordered by their LP decision-variable sums.Source: §4.4 · p. 6
5 Numerical Evaluation
Across UCI datasets, the evaluation compares two-level rule-learning algorithms over clause counts and sparsity settings using cross-validated error and Pareto-front analyses. Two-level rules often improve error or accuracy–simplicity tradeoffs, while performance depends on algorithm, clause count, and dataset complexity.
5.2 Minimal Average Test Error Rate
- Two-level rules generally reduce error rates versus one-level rules, with block coordinate descent and alternating minimization usually outperforming the other compared methods.The two-level LP relaxation does not perform as well in the comparison.Source: §5.2 · p. 7, Table 1 · p. 7
- 24.9% and 22.7% test error rates use averages of 6.3 and 6 features, respectively, versus 25.0% and 85 features for Hamming Clustering on Pima.The comparison uses different cross-validation and binarization setups, limiting direct comparability.Source: §5.2 · p. 8, §5.4 · p. 8
5.1 Setup
- Pareto fronts compare average error rates with average feature counts across 18 sparsity settings and clause counts R = 1 to 5.The evaluation uses stratified 10-fold cross-validation on four binarized UCI datasets.Source: §5.1 · p. 7, §5.3 · p. 8
5.3 Pareto Fronts with Different Numbers of Clauses
- Increasing clause count typically adds features and lowers training error, but test-error Pareto fronts can worsen through overfitting or improve on more complex datasets.On Pima, test performance worsens beyond R = 2, whereas Liver reaches a lower minimum at R = 5.Source: §5.3 · p. 8, Figure 1 · p. 8
5.4 Pareto Fronts of Different Algorithms
- At very small feature counts, block coordinate descent typically has lower error, while alternating minimization may outperform it as feature counts increase.Redundancy-aware binarization generally produces sparser set-covering rules with improved or similar accuracy.Source: §5.4 · p. 8
5.5 Pareto Fronts with/without the Option to Disable a Clause
- Disabling a clause generally improves sparsity, although the error rate may remain similar or increase.This comparison is shown through Pareto fronts with and without the always-true feature option.Source: §5.5 · p. 8, Figure 1 · p. 8
6 Conclusion
The paper introduces optimization formulations, algorithms, and redundancy-aware binarization for two-level Boolean rule learning. Results show improved error, accuracy–simplicity tradeoffs, and strong performance from the Hamming-distance algorithms, while clause count remains important.
6 Conclusion
- Two optimization formulations, three algorithms, and a redundancy-aware binarization method are developed for two-level Boolean rule learning.The formulations use 0-1 classification error or Hamming distance; the algorithms are two-level LP relaxation, block coordinate descent, and alternating minimization.Source: §6 · p. 8
- Two-level rules achieve noticeably lower error rates and more flexible accuracy–simplicity tradeoffs than one-level rules on certain complex datasets.The paper also cautions that too many clauses may cause overfitting and that the optimal clause count depends on dataset complexity.Source: §6 · pp. 8–9
- Figure 3 compares Pareto fronts with and without the option to disable a clause for Pima AMR = 5 and Liver BCD R = 5.Source: Figure 3 · p. 9
- Block coordinate descent and alternating minimization generally outperform the other compared methods for two-level rule learning, including on noisy datasets.Block coordinate descent may be preferable with very few features, whereas alternating minimization may perform better as feature counts increase.Source: §6 · p. 9
- The redundancy-aware binarization is more effective than simple thresholding in certain situations.The approach accounts for redundancies among binary features induced from continuous features.Source: §6 · p. 9