# Short Boolean Formulas as Explanations in Practice

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 23 references that are in the map.
- First posted on arXiv 13 Jul 2023.

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

- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [On the Computational Intelligibility of Boolean Classifiers](https://mlsanity.com/paper/2104.06172/) (2021)
- [Explainability via Short Formulas: the Case of Propositional Logic with Implementation](https://mlsanity.com/paper/2209.01403/) (2022)

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

- [Interpretable classifiers for tabular data via discretization and feature selection](https://mlsanity.com/paper/2402.05680/) (2024)
- [Graph Learning via Logic-Based Weisfeiler-Leman Variants and Tabularization](https://mlsanity.com/paper/2508.10651/) (2025)

## Abstract (arXiv)

We investigate explainability via short Boolean formulas in the data model based on unary relations. As an explanation of length k, we take a Boolean formula of length k that minimizes the error with respect to the target attribute to be explained. We first provide novel quantitative bounds for the expected error in this scenario. We then also demonstrate how the setting works in practice by studying three concrete data sets. In each case, we calculate explanation formulas of different lengths using an encoding in Answer Set Programming. The most accurate formulas we obtain achieve errors similar to other methods on the same data sets. However, due to overfitting, these formulas are not necessarily ideal explanations, so we use cross validation to identify a suitable length for explanations. By limiting to shorter formulas, we obtain explanations that avoid overfitting but are still reasonably accurate and also, importantly, human interpretable.