On Deciding Feature Membership in Explanations of SDD & Related Classifiers
This work addresses the computational complexity of explaining predictions for users of specific ML classifiers, though it is incremental as it builds on prior hardness results.
The paper tackles the feature membership problem (FMP) in explanations of machine learning classifiers, showing that for certain families like those using Sentential Decision Diagrams (SDDs), FMP is in NP and can be decided with one NP oracle call, with experimental results confirming practical efficiency.
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 $Σ_2^P$ 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.