# Explainable AI using expressive Boolean formulas

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 66 references that are in the map.
- First posted on arXiv 6 Jun 2023.

## Builds on (most cited first, 18 of 18)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [A Survey on the Explainability of Supervised Machine Learning](https://mlsanity.com/paper/2011.07876/) (2020)
- [Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model](https://mlsanity.com/paper/1511.01644/) (2015)
- [Supersparse Linear Integer Models for Optimized Medical Scoring Systems](https://mlsanity.com/paper/1502.04269/) (2015)
- [Falling Rule Lists](https://mlsanity.com/paper/1411.5899/) (2014)
- [Learning Certifiably Optimal Rule Lists for Categorical Data](https://mlsanity.com/paper/1704.01701/) (2017)
- [Robust and Stable Black Box Explanations](https://mlsanity.com/paper/2011.06169/) (2020)
- [Interpreting Blackbox Models via Model Extraction](https://mlsanity.com/paper/1705.08504/) (2017)
- [Learning Optimized Or's of And's](https://mlsanity.com/paper/1511.02210/) (2015)
- [MLIC: A MaxSAT-Based framework for learning interpretable classification rules](https://mlsanity.com/paper/1812.01843/) (2018)
- [Interpretable Two-level Boolean Rule Learning for Classification](https://mlsanity.com/paper/1511.07361/) (2015)
- [Interpretable and Fair Boolean Rule Sets via Column Generation](https://mlsanity.com/paper/2111.08466/) (2021)
- [IMLI: An Incremental Framework for MaxSAT-Based Learning of Interpretable Classification Rules](https://mlsanity.com/paper/2001.01891/) (2020)
- [Quantum speedup of branch-and-bound algorithms](https://mlsanity.com/paper/1906.10375/) (2019)
- [Mixed-Integer Programming Using a Bosonic Quantum Computer](https://mlsanity.com/paper/2112.13917/) (2021)

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

- [Boolformer: Symbolic Regression of Logic Functions with Transformers](https://mlsanity.com/paper/2309.12207/) (2023)
- [Towards consistency of rule-based explainer and black box model -- fusion of rule induction and XAI-based feature importance](https://mlsanity.com/paper/2407.14543/) (2024)

## Abstract (arXiv)

We propose and implement an interpretable machine learning classification model for Explainable AI (XAI) based on expressive Boolean formulas. Potential applications include credit scoring and diagnosis of medical conditions. The Boolean formula defines a rule with tunable complexity (or interpretability), according to which input data are classified. Such a formula can include any operator that can be applied to one or more Boolean variables, thus providing higher expressivity compared to more rigid rule-based and tree-based approaches. The classifier is trained using native local optimization techniques, efficiently searching the space of feasible formulas. Shallow rules can be determined by fast Integer Linear Programming (ILP) or Quadratic Unconstrained Binary Optimization (QUBO) solvers, potentially powered by special purpose hardware or quantum devices. We combine the expressivity and efficiency of the native local optimizer with the fast operation of these devices by executing non-local moves that optimize over subtrees of the full Boolean formula. We provide extensive numerical benchmarking results featuring several baselines on well-known public datasets. Based on the results, we find that the native local rule classifier is generally competitive with the other classifiers. The addition of non-local moves achieves similar results with fewer iterations, and therefore using specialized or quantum hardware could lead to a speedup by fast proposal of non-local moves.