# On Deciding Feature Membership in Explanations of SDD & Related Classifiers

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 45 references that are in the map.
- First posted on arXiv 15 Feb 2022.

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

- [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)
- [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)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [PMLB: A Large Benchmark Suite for Machine Learning Evaluation and Comparison](https://mlsanity.com/paper/1703.00512/) (2017)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [On Guaranteed Optimal Robust Explanations for NLP Models](https://mlsanity.com/paper/2105.03640/) (2021)
- [The Challenge of Crafting Intelligible Intelligence](https://mlsanity.com/paper/1803.04263/) (2018)
- [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)
- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [Efficient Explanations for Knowledge Compilation Languages](https://mlsanity.com/paper/2107.01654/) (2021)

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

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [On Computing Probabilistic Abductive Explanations](https://mlsanity.com/paper/2212.05990/) (2022)

## Abstract (arXiv)

When reasoning about explanations of Machine Learning (ML) classifiers, a pertinent query is to decide whether some sensitive features can serve for explaining a given prediction. Recent work showed that the feature membership problem (FMP) is hard for Sigma2P for a broad class of classifiers. In contrast, this paper shows that for a number of families of classifiers, FMP is in NP. Concretely, the paper proves that any classifier for which an explanation can be computed in polynomial time, then deciding feature membership in an explanation can be decided with one NP oracle call. The paper then proposes propositional encodings for classifiers represented with Sentential Decision Diagrams (SDDs) and for other related propositional languages. The experimental results confirm the practical efficiency of the proposed approach.