Interpretable Two-level Boolean Rule Learning for Classification

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.

• Publication year

  2015

• Venue

  arXiv.org

• Publication date

  2015-11-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1606.05798
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Engineering safety in machine learning

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

  2015cited by this paper
• Or's of And's for Interpretable Classification, with Application to Context-Aware Recommender Systems

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

  2014cited by this paper
• Computer-aided auditing of prescription drug claims

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

  2013cited by this paper
• Making machine learning models interpretable

  2012cited by this paper
• Building Interpretable Classifiers with Rules using Bayesian Analysis

  2012influential reference
• Foundations of Rule Learning

  2012cited by this paper
• Domain knowledge integration in data mining using decision tables: case studies in churn prediction

  2009cited by this paper
• From Local Patterns to Global Models: The LeGo Approach to Data Mining

  2008cited by this paper
• Learning decision lists

  2004cited by this paper
• Parkinson's disease: speech and voice disorders and their treatment with the Lee Silverman Voice Treatment.

  2004influential reference
• The Set Covering Machine

  2003cited by this paper
• Using Neural Network Rule Extraction and Decision Tables for Credit - Risk Evaluation

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

  2002influential reference
• Minimization of Boolean complexity in human concept learning

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

  2000cited by this paper
• Separate-and-Conquer Rule Learning

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

  1998cited by this paper
• Proof theory of many-valued logic—linear optimization—logic design: connections and interactions

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

  1996cited by this paper
• Fast Effective Rule Induction

  1995cited by this paper
• ESPRESSO-SIGNATURE: A New Exact Minimizer for Logic Functions

  1993cited by this paper
• A Nearest Hyperrectangle Learning Method

  1991cited by this paper
• in Advances in Neural Information Processing

  1989cited by this paper
• The CN2 Induction Algorithm

  1989cited by this paper
• On the learnability of Boolean formulae

  1987cited by this paper

• A review of explainable artificial intelligence in smart manufacturing

  2025cites this paper
• Explainable Evidential Clustering

  2025cites this paper
• Interpretable Intrusion Detection through Approximation of Complex Model

  2024cites this paper
• Application of Low-Cost IoT Sensors for Smart Public Transportation

  2024cites this paper
• XAI-CF - Examining the Role of Explainable Artificial Intelligence in Cyber Forensics

  2024cites this paper
• An Analysis of the Ingredients for Learning Interpretable Symbolic Regression Models with Human-in-the-loop and Genetic Programming

  2024cites this paper
• 'Put the Car on the Stand': SMT-based Oracles for Investigating Decisions

  2023cites this paper
• Boolformer: Symbolic Regression of Logic Functions with Transformers

  2023cites this paper
• Explainable AI using expressive Boolean formulas

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

  2023cites this paper
• Trade-off Between Efficiency and Consistency for Removal-based Explanations

  2022cites this paper
• Consistent and Truthful Interpretation with Fourier Analysis

  2022cites this paper
• Explainable digital forensics AI: Towards mitigating distrust in AI-based digital forensics analysis using interpretable models

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

  2022cites this paper
• Prostate cancer classification from ultrasound and MRI images using deep learning based Explainable Artificial Intelligence

  2022cites this paper
• Model learning with personalized interpretability estimation (ML-PIE)

  2021cites this paper
• Learning Accurate and Interpretable Decision Rule Sets from Neural Networks

  2021influential citation
• Classification Algorithm Using Branches Importance

  2021cites this paper
• On the Effectiveness of Interpretable Feedforward Neural Network

  2021cites this paper
• Classification of Explainable Artificial Intelligence Methods through Their Output Formats

  2021cites this paper
• Detection of Drug–Drug and Drug–Disease Interactions Inducing Acute Kidney Injury Using Deep Rule Forests

  2021cites this paper
• Model Agnostic Multilevel Explanations

  2020cites this paper
• Learning Global Transparent Models from Local Contrastive Explanations

  2020cites this paper
• Explainable Artificial Intelligence: a Systematic Review

  2020cites this paper
• Diverse Rule Sets

  2020cites this paper
• Discovering Drug-Drug and Drug-Disease Interactions Inducing Acute Kidney Injury Using Deep Rule Forests

  2020influential citation
• Classification Rules in Relaxed Logical Form

  2020cites this paper
• Principles and Practice of Explainable Machine Learning

  2020cites this paper
• Learning Global Transparent Models consistent with Local Contrastive Explanations

  2020cites this paper
• A Survey on the Explainability of Supervised Machine Learning

  2020influential citation
• AIST: An Interpretable Attention-Based Deep Learning Model for Crime Prediction

  2020cites this paper
• Explainability vs . Interpretability and methods for models ’ improvement Bachelorarbeit

  2020cites this paper
• The black box problem of AI in oncology

  2020cites this paper
• MINTERM AND IMPLICANT SELECTION CRITERIA FOR DIRECT COVER ALGORITHMS AND OFF-BASED MINTERM ORDERING

  2020cites this paper
• Generating Contrastive Explanations with Monotonic Attribute Functions

  2019cites this paper
• Leveraging Latent Features for Local Explanations

  2019cites this paper
• IMLI: An Incremental Framework for MaxSAT-Based Learning of Interpretable Classification Rules

  2019cites this paper
• Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI

  2019cites this paper
• Interpretable Classification Rules in Relaxed Logical Form

  2019cites this paper
• Model Agnostic Contrastive Explanations for Structured Data

  2019cites this paper
• Peeking Inside the Black-Box: A Survey on Explainable Artificial Intelligence (XAI)

  2018cites this paper
• The Tsetlin Machine - A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic

  2018cites this paper
• Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead

  2018cites this paper
• Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives

  2018cites this paper
• Please Stop Explaining Black Box Models for High Stakes Decisions

  2018cites this paper
• Learning customized and optimized lists of rules with mathematical programming

  2018cites this paper
• A Survey of Methods for Explaining Black Box Models

  2018cites this paper
• TIP: Typifying the Interpretability of Procedures

  2017cites this paper
• ProtoDash: Fast Interpretable Prototype Selection

  2017cites this paper
• From Myths to Norms: Demystifying Data Mining Models with Instance-Based Transparency

  2017cites this paper
• A Formal Framework to Characterize Interpretability of Procedures

  2017cites this paper
• BLAh: Boolean Logic Analysis for Graded Student Response Data

  2017cites this paper
• Efficient Data Representation by Selecting Prototypes with Importance Weights

  2017cites this paper
• Learning sparse two-level boolean rules

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

  2016cites this paper