论文标题
在SDD及相关分类器的说明中确定功能会员资格
On Deciding Feature Membership in Explanations of SDD & Related Classifiers
论文作者
论文摘要
当推理机器学习（ML）分类器的解释时，一个相关的查询是确定某些敏感功能是否可以用于解释给定的预测。最近的工作表明，特征会员问题（FMP）对于$σ_2^p $而言很难为$σ_2^p $而言。相比之下，本文表明，对于许多分类器家庭，FMP在NP中。具体而言，该论文证明了可以在多项式时间内计算说明的任何分类器，然后可以用一个NP Oracle调用来确定解释中的功能成员资格。然后，本文提出了用句子决策图（SDD）和其他相关命题语言表示的分类器的命题编码。实验结果证实了所提出方法的实际效率。
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.
