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 得分的积极复杂性结果，从而超越特征独立性假设的限制。