# Rectifying Mono-Label Boolean Classifiers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 17 Jun 2022.

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

- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [On the Tractability of SHAP Explanations](https://mlsanity.com/paper/2009.08634/) (2020)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [On the Computational Intelligibility of Boolean Classifiers](https://mlsanity.com/paper/2104.06172/) (2021)
- [On Efficiently Explaining Graph-Based Classifiers](https://mlsanity.com/paper/2106.01350/) (2021)
- [Trading Complexity for Sparsity in Random Forest Explanations](https://mlsanity.com/paper/2108.05276/) (2021)
- [On Relating 'Why?' and 'Why Not?' Explanations](https://mlsanity.com/paper/2012.11067/) (2020)

## Abstract (arXiv)

We elaborate on the notion of rectification of a Boolean classifier Sigma. Given Sigma and some background knowledge T, postulates characterizing the way Sigma must be changed into a new classifier Sigma star T that complies with T have already been presented. We focus here on the specific case of mono-label Boolean classifiers, i.e., there is a single target concept and any instance is classified either as positive (an element of the concept), or as negative (an element of the complementary concept). In this specific case, our main contribution is twofold: (1) we show that there is a unique rectification operator star satisfying the postulates, and (2) when Sigma and T are Boolean circuits, we show how a classification circuit equivalent to Sigma star T can be computed in time linear in the size of Sigma and T; when Sigma and T are decision trees, a decision tree equivalent to Sigma star T can be computed in time polynomial in the size of Sigma and T.