The local and global interpretability of various ML models has been studied
extensively in recent years. However, despite significant progress in the
field, many known results remain informal or lack sufficient mathematical
rigor. We propose a framework for bridging this gap, by using computational
complexity theory to assess local and global perspectives of interpreting ML
models. We begin by proposing proofs for two novel insights that are essential
for our analysis: (1) a duality between local and global forms of explanations;
and (2) the inherent uniqueness of certain global explanation forms. We then
use these insights to evaluate the complexity of computing explanations, across
three model types representing the extremes of the interpretability spectrum:
(1) linear models; (2) decision trees; and (3) neural networks. Our findings
offer insights into both the local and global interpretability of these models.
For instance, under standard complexity assumptions such as P != NP, we prove
that selecting global sufficient subsets in linear models is computationally
harder than selecting local subsets. Interestingly, with neural networks and
decision trees, the opposite is true: it is harder to carry out this task
locally than globally. We believe that our findings demonstrate how examining
explainability through a computational complexity lens can help us develop a
more rigorous grasp of the inherent interpretability of ML models.

使用计算复杂性理论评估机器学习模型的局部和全局解释性，证明了局部和全局解释之间的对偶性以及某些全局解释形式的独特性，并比较了线性模型、决策树和神经网络在计算解释复杂度方面的差异。

本地与全局可解释性：一个计算复杂性角度

Local vs. Global Interpretability: A Computational Complexity  Perspective

Explainability of intelligent models has been garnering increasing attention
in recent years. Of the various explainability approaches, concept-based
techniques are notable for utilizing a set of human-meaningful concepts instead
of focusing on individual pixels. However, there is a scarcity of methods that
consistently provide both local and global explanations. Moreover, most of the
methods have no offer to explain misclassification cases. To address these
challenges, our study follows a straightforward yet effective approach. We
propose a unified concept-based system, which inputs a number of
super-pixelated images into the networks, allowing them to learn better
representations of the target's objects as well as the target's concepts. This
method automatically learns, scores, and extracts local and global concepts.
Our experiments revealed that, in addition to enhancing performance, the models
could provide deeper insights into predictions and elucidate false
classifications.

本文提出了一个新的概念性系统，利用一定数量的超像素图像作为输入，可以自动学习、评分和提取局部和全局概念，在提高性能的同时，深入了解预测并阐明误分类。