On Deciding Feature Membership in Explanations of SDD & Related Classifiers
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 $\Sigma_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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Feature Necessity & Relevancy in ML Classifier Explanations
Given a machine learning (ML) model and a prediction, explanations can be defined as sets of features which are sufficient for the prediction. In some applications, and besides asking for an explanation, it is also criti…
PredictionOn Logic-Based Explainability with Partially Specified Inputs
In the practical deployment of machine learning (ML) models, missing data represents a recurring challenge. Missing data is often addressed when training ML models. But missing data also needs to be addressed when decidi…
On Efficiently Explaining Graph-Based Classifiers
Recent work has shown that not only decision trees (DTs) may not be interpretable but also proposed a polynomial-time algorithm for computing one PI-explanation of a DT. This paper shows that for a wide range of classifi…
On the Privacy Risks of Model Explanations
Privacy and transparency are two key foundations of trustworthy machine learning. Model explanations offer insights into a model's decisions on input data, whereas privacy is primarily concerned with protecting informati…
modelPERFEX: Classifier Performance Explanations for Trustworthy AI Systems
Explainability of a classification model is crucial when deployed in real-world decision support systems. Explanations make predictions actionable to the user and should inform about the capabilities and limitations of t…