Thanks to its solid theoretical foundation, the SHAP framework is arguably
one the most widely utilized frameworks for local explainability of ML models.
Despite its popularity, its exact computation is known to be very challenging,
proven to be NP-Hard in various configurations. Recent works have unveiled
positive complexity results regarding the computation of the SHAP score for
specific model families, encompassing decision trees, random forests, and some
classes of boolean circuits. Yet, all these positive results hinge on the
assumption of feature independence, often simplistic in real-world scenarios.
In this article, we investigate the computational complexity of the SHAP score
by relaxing this assumption and introducing a Markovian perspective. We show
that, under the Markovian assumption, computing the SHAP score for the class of
Weighted automata, Disjoint DNFs and Decision Trees can be performed in
polynomial time, offering a first positive complexity result for the problem of
SHAP score computation that transcends the limitations of the feature
independence assumption.

通过引入马尔可夫视角，我们研究了 SHAP 得分的计算复杂性，并在一些模型类中展示了多项式时间内计算 SHAP 得分的积极复杂性结果，从而超越特征独立性假设的限制。

关于马尔可夫分布下 SHAP 解释的可处理性

On the tractability of SHAP explanations under Markovian distributions

When used in the context of decision theory, feature importance expresses how
much changing the value of a feature can change the model outcome (or the
utility of the outcome), compared to other features. Feature importance should
not be confused with the feature influence used by most state-of-the-art
post-hoc Explainable AI methods. Contrary to feature importance, feature
influence is measured against a reference level or baseline. The Contextual
Importance and Utility (CIU) method provides a unified definition of global and
local feature importance that is applicable also for post-hoc explanations,
where the value utility concept provides instance-level assessment of how
favorable or not a feature value is for the outcome. The paper shows how CIU
can be applied to both global and local explainability, assesses the fidelity
and stability of different methods, and shows how explanations that use
contextual importance and contextual utility can provide more expressive and
flexible explanations than when using influence only.

这篇论文提供了一种统一的定义，可以应用于后续解释，评估不同方法的忠实度和稳定性，并且展示了使用上下文重要性和效用可以提供比只使用影响力时更富表达力和灵活性的解释。

特征重要性与特征影响：对可解释人工智能的意义

Feature Importance versus Feature Influence and What It Signifies for  Explainable AI

The increasing adoption of machine learning tools has led to calls for
accountability via model interpretability. But what does it mean for a machine
learning model to be interpretable by humans, and how can this be assessed? We
focus on two definitions of interpretability that have been introduced in the
machine learning literature: simulatability (a user's ability to run a model on
a given input) and "what if" local explainability (a user's ability to
correctly determine a model's prediction under local changes to the input,
given knowledge of the model's original prediction). Through a user study with
1,000 participants, we test whether humans perform well on tasks that mimic the
definitions of simulatability and "what if" local explainability on models that
are typically considered locally interpretable. To track the relative
interpretability of models, we employ a simple metric, the runtime operation
count on the simulatability task. We find evidence that as the number of
operations increases, participant accuracy on the local interpretability tasks
decreases. In addition, this evidence is consistent with the common intuition
that decision trees and logistic regression models are interpretable and are
more interpretable than neural networks.

本文探讨了人们对计算机可解释性的两个定义，即可模拟性和 “what if” 局部解释性。其中，通过对 1000 名参与者进行用户研究，我们测试了人类是否能够在通常被认为是局部可解释的模型上模仿可模拟性和 “what if” 局部可解释性的定义，并发现运行时间操作计数与局部解释性任务的准确性呈负相关关系。此外，我们发现决策树和逻辑回归模型相比于神经网络模型，是更加容易被解释的模型。