Boolean Decision Rules via Column Generation

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.

• Publication year

  2018

• Venue

  Neural Information Processing Systems

• Publication date

  2018-05-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1805.09901
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Integer Programming

  2018cited by this paper
• Optimal classification trees

  2017cited by this paper
• Learning Cost-Effective and Interpretable Treatment Regimes

  2017cited by this paper
• Learning Certifiably Optimal Rule Lists

  2017cited by this paper
• A Bayesian Framework for Learning Rule Sets for Interpretable Classification

  2017influential reference
• Scalable Bayesian Rule Lists

  2016cited by this paper
• Interpretable Decision Sets: A Joint Framework for Description and Prediction

  2016cited by this paper
• Learning sparse two-level boolean rules

  2016influential reference
• Learning Optimized Or's of And's

  2015cited by this paper
• Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model

  2015cited by this paper
• Falling Rule Lists

  2014cited by this paper
• Integer Programming

  2014cited by this paper
• Screening for learning classification rules via Boolean compressed sensing

  2014cited by this paper
• Comprehensible classification models: a position paper

  2014cited by this paper
• Exact Rule Learning via Boolean Compressed Sensing

  2013cited by this paper
• Learning Hash Functions Using Column Generation

  2013cited by this paper
• Classification and regression trees

  2012influential reference
• Learning DNF Expressions from Fourier Spectrum

  2012cited by this paper
• Foundations of Rule Learning

  2012cited by this paper
• Scikit-learn: Machine Learning in Python

  2011cited by this paper
• ENDER: a statistical framework for boosting decision rules

  2010cited by this paper
• PREDICTIVE LEARNING VIA RULE ENSEMBLES

  2008cited by this paper
• Discriminative Frequent Pattern Analysis for Effective Classification

  2007cited by this paper
• A new approach to classification based on association rule mining

  2006cited by this paper
• Logical analysis of data—An overview: From combinatorial optimization to medical applications

  2006cited by this paper
• HARMONY: Efficiently Mining the Best Rules for Classification

  2005cited by this paper
• An implementation of the FP-growth algorithm

  2005cited by this paper
• Learning decision lists

  2004cited by this paper
• Column-generation boosting methods for mixture of kernels

  2004cited by this paper
• Learning DNF in time 2Õ(n1/3)

  2004cited by this paper
• CPAR: Classification based on Predictive Association Rules

  2003cited by this paper
• The Set Covering Machine

  2003cited by this paper
• Binary Rule Generation via Hamming Clustering

  2002cited by this paper
• Linear Programming Boosting via Column Generation

  2002cited by this paper
• Learning DNF in time 2 Õ(n 1/3 ) .

  2001cited by this paper
• Random Forests

  2001cited by this paper
• CMAR: accurate and efficient classification based on multiple class-association rules

  2001cited by this paper
• An Implementation of Logical Analysis of Data

  2000cited by this paper
• A simple, fast, and effective rule learner

  1999cited by this paper
• Bump hunting in high-dimensional data

  1999cited by this paper
• Fast Algorithms for Mining Association Rules

  1998influential reference
• Generating Accurate Rule Sets Without Global Optimization

  1998cited by this paper
• Integrating Classification and Association Rule Mining

  1998cited by this paper
• Branch-and-Price: Column Generation for Solving Huge Integer Programs

  1998cited by this paper
• Unifying Instance-Based and Rule-Based Induction

  1996cited by this paper
• Fast Effective Rule Induction

  1995influential reference
• An exact algorithm for IP column generation

  1994cited by this paper
• Programs for Machine Learning

  1994cited by this paper
• C4.5: Programs for Machine Learning

  1992cited by this paper
• A Nearest Hyperrectangle Learning Method

  1991cited by this paper
• Rule Induction with CN2: Some Recent Improvements

  1991cited by this paper
• The CN2 Induction Algorithm

  1989cited by this paper
• A theory of the learnable

  1984cited by this paper
• Linear Programming and Network Flows

  1977cited by this paper

• Explainable Artificial Intelligence for Deepfake Detection: Pipeline, Open Source and Comparisons

  2026cites this paper
• Features of using EXPLAINABLE AI in biomedical image processing: transparency and interpretability of models

  2026cites this paper
• Leveraging generative AI to enhance Synthea model development

  2026cites this paper
• Intersectional Fairness via Mixed-Integer Optimization

  2026cites this paper
• Precise Bayes Regression: Approaching Optimality, Using Multi-Dimensional Space Partitioning Trees

  2025cites this paper
• Counterfactual Explanation Through Latent Adjustment in Disentangled Space of Diffusion Model

  2025cites this paper
• Questioning the Robot: Using Human Non-verbal Cues to Estimate the Need for Explanations

  2025cites this paper
• Models That Are Interpretable But Not Transparent

  2025cites this paper
• GSM-EL: A Generalizable Symbol-Manipulation Approach for Entity Linking

  2025cites this paper
• Interpretable optimisation-based approach for hyper-box classification

  2025influential citation
• CoFrNets: Interpretable Neural Architecture Inspired by Continued Fractions

  2025cites this paper
• Augmenting Intelligence: A Hybrid Framework for Scalable and Stable Explanations

  2025cites this paper
• Bias Detection via Maximum Subgroup Discrepancy

  2025cites this paper
• MetaExplainer: A Framework to Generate Multi-Type User-Centered Explanations for AI Systems

  2025cites this paper
• Dynamic Prediction of Treatment Failure in Ocular Tuberculosis Using Machine Learning and Explainable AI

  2025cites this paper
• A Survey on Explainable Artificial Intelligence for Internet Traffic Classification and Prediction, and Intrusion Detection

  2025cites this paper
• Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees

  2024cites this paper
• Towards consistency of rule-based explainer and black box model - fusion of rule induction and XAI-based feature importance

  2024cites this paper
• CausalPrism: A Visual Analytics Approach for Subgroup-based Causal Heterogeneity Exploration

  2024cites this paper
• CURLS: Causal Rule Learning for Subgroups with Significant Treatment Effect

  2024cites this paper
• Are Logistic Models Really Interpretable?

  2024cites this paper
• SLIM: A Scalable Light-Weight Root Cause Analysis for Imbalanced Data in Microservice

  2024cites this paper
• Learning Cut Generating Functions for Integer Programming

  2024cites this paper
• A Meta Algorithm for Interpretable Ensemble Learning: The League of Experts

  2024cites this paper
• A General Theoretical Framework for Learning Smallest Interpretable Models

  2024cites this paper
• Forest-ORE: Mining Optimal Rule Ensemble to interpret Random Forest models

  2024cites this paper
• Explainable Multistage Ensemble 1D Convolutional Neural Network for Trust Worthy Credit Decision

  2024cites this paper
• Orthogonal Gradient Boosting for Simpler Additive Rule Ensembles

  2024cites this paper
• Trust Regions for Explanations via Black-Box Probabilistic Certification

  2024cites this paper
• Probabilistic Truly Unordered Rule Sets

  2024cites this paper
• Optimization Over Trained Neural Networks: Taking a Relaxing Walk

  2024cites this paper
• An on-the-fly framework for usable access control policy mining

  2024cites this paper
• A Reciprocity Between Tree Ensemble Optimization and Multilinear Optimization

  2024cites this paper
• HyperLogic: Enhancing Diversity and Accuracy in Rule Learning with HyperNets

  2024cites this paper
• MimicAI: An LLM based system that mimics and explains

  2024influential citation
• Biological and Radiological Dictionary of Radiomics Features: Addressing Understandable AI Issues in Personalized Prostate Cancer; Dictionary Version PM1.0

  2024cites this paper
• Interpretable neural network classification model using first-order logic rules

  2024cites this paper
• RuleMiner: An Interactive Web Tool for Rule-Based Data Analysis

  2024cites this paper
• SLIM: a Scalable and Interpretable Light-weight Fault Localization Algorithm for Imbalanced Data in Microservice

  2024cites this paper
• VIME: Visual Interactive Model Explorer for Identifying Capabilities and Limitations of Machine Learning Models for Sequential Decision-Making

  2024cites this paper
• Neural Reasoning Networks: Efficient Interpretable Neural Networks With Automatic Textual Explanations

  2024cites this paper
• Alert Prioritisation in Security Operations Centres: A Systematic Survey on Criteria and Methods

  2024cites this paper
• ESC: Explaining the Predictions of Deep Neural Networks via Concept Similarity

  2024cites this paper
• DiffVersify: a Scalable Approach to Differentiable Pattern Mining with Coverage Regularization

  2024cites this paper
• Aligning XAI with EU Regulations for Smart Biomedical Devices: A Methodology for Compliance Analysis

  2024cites this paper
• Efficient Decision Rule List Learning via Unified Sequence Submodular Optimization

  2024cites this paper
• Explainable AI for Text Classification: Lessons from a Comprehensive Evaluation of Post Hoc Methods

  2024cites this paper
• A Polyhedral Study of Multivariate Decision Trees

  2024influential citation
• Obtaining Explainable Classification Models using Distributionally Robust Optimization

  2023influential citation
• Explainable Machine Learning Models of Consumer Credit Risk

  2023cites this paper
• AIMEE: An Exploratory Study of How Rules Support AI Developers to Explain and Edit Models

  2023influential citation
• A New Interpretable Neural Network-Based Rule Model for Healthcare Decision Making

  2023cites this paper
• Explainable AI for clinical risk prediction: a survey of concepts, methods, and modalities

  2023cites this paper
• Reinforcement Logic Rule Learning for Temporal Point Processes

  2023cites this paper
• Survey on Explainable AI: From Approaches, Limitations and Applications Aspects

  2023cites this paper
• Global Explanations for Multivariate time series models

  2023cites this paper
• Re-interpreting rules interpretability

  2023cites this paper
• Co-creating a globally interpretable model with human input

  2023influential citation
• Disjunctive Threshold Networks for Tabular Data Classification

  2023influential citation
• Discovering Intrinsic Spatial-Temporal Logic Rules to Explain Human Actions

  2023cites this paper
• Learning Locally Interpretable Rule Ensemble

  2023cites this paper
• Interpretable Differencing of Machine Learning Models

  2023cites this paper
• Improving the Validity of Decision Trees as Explanations

  2023cites this paper
• A Framework Quantifying Trustworthiness of Supervised Machine and Deep Learning Models

  2023cites this paper
• Interpretable Regional Descriptors: Hyperbox-Based Local Explanations

  2023cites this paper
• CGXplain: Rule-Based Deep Neural Network Explanations Using Dual Linear Programs

  2023influential citation
• Toward practical and plausible counterfactual explanation through latent adjustment in disentangled space

  2023cites this paper
• Visualizing the Implicit Model Selection Tradeoff

  2023cites this paper
• Decision tree post-pruning without loss of accuracy using the SAT-PP algorithm with an empirical evaluation on clinical data

  2023cites this paper
• Neural-based classification rule learning for sequential data

  2023cites this paper
• Scalable Optimal Multiway-Split Decision Trees with Constraints

  2023cites this paper
• Rethinking Logic Minimization for Tabular Machine Learning

  2023influential citation
• Explaining with Greater Support: Weighted Column Sampling Optimization for q-Consistent Summary-Explanations

  2023cites this paper
• Personalized Interpretable Classification

  2023cites this paper
• RIDDLE: Rule Induction with Deep Learning

  2023cites this paper
• Optimal multivariate decision trees

  2023cites this paper
• Efficient learning of large sets of locally optimal classification rules

  2023cites this paper
• Finding Interpretable Class-Specific Patterns through Efficient Neural Search

  2023cites this paper
• based heuristic for learning classification

  2022cites this paper
• Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach

  2022influential citation
• FROTE: Feedback Rule-Driven Oversampling for Editing Models

  2022cites this paper
• Differentiable Rule Induction with Learned Relational Features

  2022influential citation
• Visual Exploration of Machine Learning Model Behavior With Hierarchical Surrogate Rule Sets

  2022cites this paper
• POTATO: exPlainable infOrmation exTrAcTion framewOrk

  2022cites this paper
• Analogies and Feature Attributions for Model Agnostic Explanation of Similarity Learners

  2022cites this paper
• Post-hoc Global Explanation using Hypersphere Sets

  2022cites this paper
• Netrca: An Effective Network Fault Cause Localization Algorithm

  2022cites this paper
• Interpretable Off-Policy Learning via Hyperbox Search

  2022cites this paper
• Building Trust in Interactive Machine Learning via User Contributed Interpretable Rules

  2022influential citation
• Explaining Point Processes by Learning Interpretable Temporal Logic Rules

  2022cites this paper
• Shattering Inequalities for Learning Optimal Decision Trees

  2022cites this paper
• Human-centered explainability for life sciences, healthcare, and medical informatics

  2022cites this paper
• Mixed integer linear optimization formulations for learning optimal binary classification trees

  2022cites this paper
• Truly Unordered Probabilistic Rule Sets for Multi-class Classification

  2022cites this paper
• Machine Learning in Sports: A Case Study on Using Explainable Models for Predicting Outcomes of Volleyball Matches

  2022influential citation
• Policy Optimization with Sparse Global Contrastive Explanations

  2022cites this paper
• Boolean Decision Rules for Reinforcement Learning Policy Summarisation

  2022cites this paper
• Leveraging explanations in interactive machine learning: An overview

  2022cites this paper
• Explainable prediction of Qcodes for NOTAMs using column generation

  2022influential citation
• From Black Boxes to Conversations: Incorporating XAI in a Conversational Agent

  2022cites this paper