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

Understanding how a learned black box works is of crucial interest for the
future of Machine Learning. In this paper, we pioneer the question of the
global interpretability of learned black box models that assign numerical
values to symbolic sequential data. To tackle that task, we propose a spectral
algorithm for the extraction of weighted automata (WA) from such black boxes.
This algorithm does not require the access to a dataset or to the inner
representation of the black box: the inferred model can be obtained solely by
querying the black box, feeding it with inputs and analyzing its outputs.
Experiments using Recurrent Neural Networks (RNN) trained on a wide collection
of 48 synthetic datasets and 2 real datasets show that the obtained
approximation is of great quality.

研究了如何从学习黑匣子中提取加权自动机，以评估其全局可解释性，不需要访问数据集或内部表示，充分利用黑匣子的输出结果，实验结果表明此算法在 48 个合成数据集和 2 个实际数据集上的逼近效果出色。

使用加权自动机解释顺序数据上的黑盒子

Explaining Black Boxes on Sequential Data using Weighted Automata

Learning probabilistic models over strings is an important issue for many
applications. Spectral methods propose elegant solutions to the problem of
inferring weighted automata from finite samples of variable-length strings
drawn from an unknown target distribution. These methods rely on a singular
value decomposition of a matrix $H_S$, called the Hankel matrix, that records
the frequencies of (some of) the observed strings. The accuracy of the learned
distribution depends both on the quantity of information embedded in $H_S$ and
on the distance between $H_S$ and its mean $H_r$. Existing concentration bounds
seem to indicate that the concentration over $H_r$ gets looser with the size of
$H_r$, suggesting to make a trade-off between the quantity of used information
and the size of $H_r$. We propose new dimension-free concentration bounds for
several variants of Hankel matrices. Experiments demonstrate that these bounds
are tight and that they significantly improve existing bounds. These results
suggest that the concentration rate of the Hankel matrix around its mean does
not constitute an argument for limiting its size.

本文通过提供一些新的用于 Hankel 矩阵的无维度的集中度界限的方案，增强了已有的含量界限，以探讨权重自动机这个概念。我们测试了这个界限并发现他们对于已有的界限相比，表现要好得多。