PaperlayerView exact revision on arXiv

Source-linked AI summary

Boolean Decision Rules via Column Generation

Sanjeeb Dash, Oktay Günlük, Dennis Wei

arXiv:1805.09901v2cs.AI

TL;DR

Learning compact, interpretable Boolean classifiers requires balancing classification accuracy with rule simplicity over a potentially exponential clause space. The paper formulates this problem as an integer program and uses column generation, including a randomized approximation for larger datasets. CG achieves strong accuracy–simplicity trade-offs and remains competitive with accuracy-focused rule learners, sometimes producing simpler models without sacrificing accuracy.

  • Problem

    The paper addresses how to learn interpretable DNF or CNF classifiers while jointly trading classification accuracy against rule simplicity.

  • Method

    The paper formulates Boolean rule learning as an integer program and uses column generation to search exponentially many clauses without pre-mining them, with randomized approximation for larger datasets.

  • Results

    CG dominated three recent proposals on the accuracy–simplicity trade-off on 8 of 16 datasets and remained competitive with RIPPER, sometimes finding significantly simpler models with no accuracy sacrifice.

  • Takeaways & Limitations

    CG provides interpretable DNF or CNF classification rules with strong accuracy–simplicity trade-offs and can match accuracy-focused rule learners using simpler models in some instances.

  • Takeaways & Limitations

    For large datasets, time limits and sampling sacrifice the framework’s optimality guarantees and can affect solution quality during cross-validation.

Abstract

from arXiv · show

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 7 out of 15 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.

1 Introduction

The paper motivates compact Boolean rule sets as interpretable classifiers and addresses limitations in existing rule-learning approaches. It proposes column generation to search the exponential clause space while jointly considering accuracy and simplicity.

  • Interpretability supports expert understanding, critique, trust, and explanation of individual decisions in high-consequence domains.The paper highlights medicine, criminal justice, and business as motivating applications.
  • Boolean rules use DNF or CNF structures to provide interpretable binary classification models, with compactness favored through few clauses and conditions.DNF rules are OR-of-ANDs, while CNF rules are AND-of-ORs.
  • Existing practical rule-learning strategies use heuristics or multiple criteria and do not explicitly model complexity alongside classification accuracy.The paper discusses covering, bottom-up, and associative-classification approaches.
  • Recent methods jointly optimize accuracy and simplicity but restrict candidate rules through frequent mining or approximate the subsequent optimization.Candidate selection has used greedy search, simulated annealing, or integer programming over mined rules.
  • Column generation searches over exponentially many possible clauses without enumerating a pre-mined subset, generating only clauses that can improve the current solution.The approach uses exact optimization for smaller datasets and randomized approximate column generation for larger ones.
  • Across 16 datasets, CG dominated three recent proposals on the accuracy–simplicity trade-off on 8 datasets and sometimes matched accuracy with substantially simpler models than RIPPER.When optimized for accuracy, CG remained competitive with rule learners designed for maximum accuracy.

2 Problem formulation

The paper formulates Boolean rule learning as an integer program that balances Hamming loss against an explicit complexity bound, then uses column generation to search the exponentially large clause space. The resulting procedure provides optimality guarantees or valid lower bounds, including when computation stops early.

  • 2 Problem formulation: Binary-feature Boolean classification is formulated using DNF clauses, with an equivalent CNF formulation obtained by negating labels and features.The formulation assumes binary features and supports multi-class classification through one-versus-rest extension.
  • 2.1 An integer program to minimize Hamming loss: The integer program minimizes Hamming loss, counting false negatives and selected clauses satisfied by negative samples.Positive misclassifications contribute one unit, while false positives contribute according to the number of selected clauses they satisfy.
  • 2.1 An integer program to minimize Hamming loss: Rule-set complexity is bounded by C, with each clause costing one plus its number of conditions.An additional complexity penalty can also be used, either instead of or together with the explicit bound.
  • 2.1 An integer program to minimize Hamming loss: The Master IP contains exponentially many clause variables, so the Restricted MLP starts with a small subset and supplies an upper bound on the full Master LP objective.Missing clauses are added only when they can improve the restricted solution.
  • 2.2 Column generation framework: Column generation repeatedly solves the Restricted MLP and searches for missing clauses with negative reduced cost using the optimal dual solution.The pricing problem selects clause features and enforces conjunction behavior through sample-specific zero-feature constraints.
  • 2.3 Optimality guarantees and bounds: When no missing clause has negative reduced cost, the Restricted MLP and Master LP have the same optimum; an integral restricted solution also solves the Master IP optimally.A fractional restricted solution may require branch-and-price, which is computationally intensive.
  • 2.3 Optimality guarantees and bounds: For fractional Master LP solutions, ⌈zMLP⌉ is a lower bound on zMIP and can certify optimality when matched by a feasible integer solution.Feasible integer solutions may come from the Restricted MIP or any heuristic method.
  • 2.3 Optimality guarantees and bounds: ⌈zRMLP + (C/2)zCG⌉ remains a valid lower bound on zMIP when column generation is terminated before solving the Master LP to optimality.The bound uses the last restricted-LP objective and the current pricing value.

3 Computational Approach

The computational approach uses exact optimization for smaller datasets and bounded-time column generation for larger ones. When pricing becomes difficult, heuristic and randomized approximations extend the search but can remove optimality guarantees.

  • Dataset regimes: Small datasets can use the optimization framework to find an optimal rule set for the training data.The paper loosely defines small datasets as fewer than a couple thousand samples and a few hundred binary features.
  • Dataset regimes: For medium and large datasets, pricing problems with at least 100,000 non-zeros may not be solvable to proven optimality within a reasonable time.The approach therefore terminates pricing after a fixed time limit.
  • Heuristic search: When pricing cannot prove that no improving clause exists, column generation continues with a fast heuristic search over clauses containing at most κ features, using κ = 5 in experiments.The heuristic enumerates candidate clauses by size and returns the best generated clauses before the next size.
  • Column-generation termination: If no negative reduced-cost clause is found or the overall time limit is reached, column generation terminates and the restricted MIP is solved.Termination can occur after proving that no improving clause exists or after the pricing and heuristic searches fail within their budgets.
  • Approximate pricing: For large datasets, approximate pricing randomly selects features and samples to create a smaller formulation when the full problem is too difficult.The sampling targets a formulation with a couple of thousand samples on average.

4 Numerical Evaluation

The evaluation compares CG with rule-learning alternatives on classification accuracy, rule simplicity, and optimization quality across 16 datasets. CG generally achieves stronger accuracy–simplicity trade-offs and remains competitive with accuracy-focused learners, while dataset size and cross-validation affect solution quality.

  • Experimental setup: 16 datasets, including FICO, were used to evaluate CG against BRS, AM, BCD, RIPPER, CART, and Random Forests.The experiments compare methods that control rule complexity with accuracy-oriented and uninterpretable benchmarks.
  • Accuracy–simplicity trade-offs: 8 of 16 datasets showed CG dominating three recent complexity-controlling alternatives in the accuracy–simplicity trade-off.The figure caption reports the same dominance count for the full dataset set.
  • Experimental setup: CG’s accuracy–simplicity trade-offs were evaluated under 300 seconds of training time and 45 seconds per pricing problem.Nested cross-validation used 120 seconds per candidate complexity bound and 30 seconds per pricing problem.
  • Accuracy-focused comparison: CG was no more than 1% less accurate than RIPPER on any dataset and often produced simpler, nearly as accurate or more accurate rule sets on larger datasets.Examples include bank-marketing, magic, and FICO; RIPPER was approximately 2% worse on ionosphere, liver, and tic-tac-toe.
  • Optimization quality: Optimal or near-optimal training solutions were certified for heart, liver, and transfusion, including an optimality gap of at most 0.7% for transfusion at C = 15.For medium and large datasets, pricing could not generally be solved to optimality or near-optimality within the time limits.
  • Illustrative rule: The learned FICO DNF rule identifies two groups differentiated by satisfactory accounts, revolving debt, and risk estimate.The second, riskier group requires a slightly higher ExtRiskEstimate.

5 Conclusion

The paper develops column generation for interpretable DNF and CNF classification rules, searching the clause space without pre-mining or other restrictions. Experiments support superior accuracy–simplicity trade-offs, although cross-validation and computational limits can reduce performance relative to the method’s potential.

  • Conclusion: CG searches exponentially many possible clauses without pre-mining or other restrictions when learning interpretable DNF or CNF rules.The approach generates only clauses that can improve the current solution.
  • Conclusion: Experiments support superior accuracy–rule simplicity trade-offs for the proposed method.This conclusion summarizes the reported evaluation results.
  • Limitations: Cross-validation sometimes produced lower accuracy than the potential indicated by the initial accuracy–complexity experiment.For heart disease, the maximum accuracy was 81.3% in Figure 1a versus 78.9% after cross-validation in Table 1.
  • Limitations: Aggressive time limits and sampling during cross-validation can affect solution quality, leaving improved optimization of C for future work.The paper also notes variability in test-accuracy estimates for small datasets.

A.1 Datasets and data processing

The evaluation primarily uses UCI datasets with several dataset-specific label, sample, and missing-value processing decisions. These transformations define the binary prediction tasks used in the experiments.

  • Data processing: The UCI datasets were used largely as-is, with documented deviations and label binarizations.The appendix lists dataset-specific preprocessing decisions.
  • Data processing: Liver disorders uses number of drinks, binarized as ≤2 or > 2, instead of the selector variable.This follows the data donors’ recommendation.
  • Data processing: Gas sensor array drift labels were binarized as ≤3 or > 3.The threshold follows prior work cited by the paper.
  • Data processing: The heart-disease experiment uses Cleveland data only, removes four samples with ca = ?, and binarizes labels as 0 or > 0.The resulting dataset contains 299 samples.
  • Data processing: For FICO, 588 all-missing records were removed and special values were transformed into numerical replacements or a null category with an indicator.The passage describes handling of −7, −8, and remaining −9 values before binarization.

A.2 BRS parameters

BRS and its FPGrowth candidate-rule miner were evaluated using parameters taken from prior work and its associated code. The setup fixes support, rule length, candidate reduction, objective weights, and simulated-annealing effort.

  • FPGrowth: FPGrowth used 5% minimum support, maximum rule length 3, and reduction to 5000 candidate rules using information gain.Candidate reduction was triggered in all cases.
  • BRS: BRS used α+ = α− = 500, β+ = β− = 1, and two simulated-annealing chains of 500 iterations.The parameters followed the cited prior work and associated implementation.

A.3 Accuracy-simplicity trade-offs for all datasets

Figures 2 and 3 provide the complete accuracy-simplicity trade-off plots for all 16 datasets, including the four datasets presented in the main text.

  • 16 datasets are covered in the full set of accuracy-simplicity trade-off plots.The plots include the four datasets from the main text and the remaining datasets.

A.4 Results for additional classifiers

Additional classifier results include constrained comparisons for IDS, benchmark results for other classifiers, and complexity measurements for rule sets.

  • IDS was run only when Apriori generated fewer than 900 candidates under the specified support and length settings.The authors did not use more than 1000 candidates because practical running time became infeasible.
  • IDS used deterministic local search with ϵ = 0.05, equal false-positive and false-negative costs, and tuned overlap and complexity parameters.The settings included λ6 = λ7 = 1, λ3 = λ4 = 0.5, λ5 = 0, and varying λ1 = λ2.
  • IDS was not competitive with other rule-set algorithms on most datasets despite selecting λ1 = λ2 after observing test results.The authors suspect both Apriori constraints and difficulty adapting the implementation from interval to (≤, >) feature representations.
  • Table 5 measures rule-set complexity as the number of clauses plus the total number of conditions.The paper's broader formulation defines clause complexity as one plus its number of conditions and sums clause complexities across the rule set.
Loading 1805.09901v2…