Widespread use of artificial intelligence (AI) algorithms and machine
learning (ML) models on the one hand and a number of crucial issues pertaining
to them warrant the need for explainable artificial intelligence (XAI). A key
explainability question is: given this decision was made, what are the input
features which contributed to the decision? Although a range of XAI approaches
exist to tackle this problem, most of them have significant limitations.
Heuristic XAI approaches suffer from the lack of quality guarantees, and often
try to approximate Shapley values, which is not the same as explaining which
features contribute to a decision. A recent alternative is so-called formal
feature attribution (FFA), which defines feature importance as the fraction of
formal abductive explanations (AXp's) containing the given feature. This
measures feature importance from the view of formally reasoning about the
model's behavior. It is challenging to compute FFA using its definition because
that involves counting AXp's, although one can approximate it. Based on these
results, this paper makes several contributions. First, it gives compelling
evidence that computing FFA is intractable, even if the set of contrastive
formal explanations (CXp's) is provided, by proving that the problem is
#P-hard. Second, by using the duality between AXp's and CXp's, it proposes an
efficient heuristic to switch from CXp enumeration to AXp enumeration
on-the-fly resulting in an adaptive explanation enumeration algorithm
effectively approximating FFA in an anytime fashion. Finally, experimental
results obtained on a range of widely used datasets demonstrate the
effectiveness of the proposed FFA approximation approach in terms of the error
of FFA approximation as well as the number of explanations computed and their
diversity given a fixed time limit.

人工智能和机器学习模型的广泛应用与一系列相关问题需要可解释的人工智能。形式特征归属是一种新的方法，定义了特征重要性作为包含给定特征的正式反演解释的比例。本文提出了一种高效的启发式算法以适应性地近似形式特征归属，在多个常用数据集上的实验结果表明了所提方法的有效性。