Trade-off Between Efficiency and Consistency for Removal-based Explanations
Authors: Yifan Zhang
Haowei He
Zhiquan Tan
Yang Yuan
Venue: NeurIPS 2023 poster (2023)
Keywords: AI interpretability
explainable AI
deep learning theory
TL;DR: We prove the impossible trinity theorem for removal-based explanations, which asserts that interpretability, efficiency, and consistency cannot coexist, and propose algorithms to exploit the tradeoff between efficiency and consistency.

Abstract: In the current landscape of explanation methodologies, most predominant approaches, such as SHAP and LIME, employ removal-based techniques to evaluate the impact of individual features by simulating various scenarios with specific features omitted. Nonetheless, these methods primarily emphasize efficiency in the original context, often resulting in general inconsistencies. In this paper, we demonstrate that such inconsistency is an inherent aspect of these approaches by establishing the Impossible Trinity Theorem, which posits that interpretability, efficiency, and consistency cannot hold simultaneously. Recognizing that the attainment of an ideal explanation remains elusive, we propose the utilization of interpretation error as a metric to gauge inefficiencies and inconsistencies. To this end, we present two novel algorithms founded on the standard polynomial basis, aimed at minimizing interpretation error. Our empirical findings indicate that the proposed methods achieve a substantial reduction in interpretation error, up to 31.8 times lower when compared to alternative techniques.

Trade-off Between Efficiency and Consistency for Removal-based Explanations
Yifan Zhang*)
Haowei He
Zhiquan Tan
Yang Yuan 133,4
IIS, Tsinghua University
2 Department of Math, Tsinghua Univesity
Shanghai Artificial Intelligence Laboratory
'Shanghai Qizhi Institute
(zhangyif21 hhw19, tanzq21 | @mails. tsinghua, edu. cn yuanyang@tsinghua. edu cn
Abstract
In the current landscape of explanation methodologies, most predominant ap- proaches, such as SHAP and LIME, employ removal-based techniques evaluate the impact of individual features by simulating various scenarios with specific features omitted. Nonetheless, these methods primarily emphasize efficiency in the original context, often resulting in general inconsistencies. In this paper, we demonstrate that such inconsistency is an inherent aspect of these approaches by establishing the Impossible Trinity Theorem, which posits that interpretability. efficiency, and consistency cannot hold simultaneously. Recognizing that the tainment of an ideal explanation remains elusive, we propose the utilization of interpretation error metric to gauge inefficiencies and inconsistencies. To this end, we present two novel algorithms founded on the standard polynomial basis, aimed at minimizing interpretation error. Our empirical findings indicate that the proposed methods achieve a substantial reduction in interpretation error, up to 31.8 times lower when compared alternative techniques².
Introduction
Most existing explanation approaches are removal-based [18], which involve the sequential process of eliminating certain input features, examining the subsequent alterations in the model's behavior, and ascertaining each feature's impact through observation. However, most of these methods [60, 38] primarily focus on the original input with all features, often yielding inconsistent outcomes in alternative scenarios. Consequently, the resulting interpretations may not explain the network's behavior consistently even small neighborhood of the input, as demonstrated in Figure
Inconsistency is non-trivial concern. Imagine a doctor treating diabetic patient with the help of an AI system. The patient has features A. B, and C, representing three positive signals from various tests. The AI recommends administering 4 units of insulin with the following explanation: A, B, and C have weights 1, 1, and respectively, amounting to 4 units in total. The doctor might then ask the AI: what if the patient only has A and B, but not C? One might expect the answer to be close to 2, as A+B has weight of 2. However, network, being highly non-linear, might output different suggestion like units, explaining that both A and B have weight of 1.5. Such inconsistent
'Equal Contribution. Corresponding Author
Code available at https:///iithi/ http://htw..cccctttttt/ooooaataa http:///wwaaaaaaaooooooooooooooe expeenttixxlaaaiionn....
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

behaviors can significantly reduce the doctor's confidence in the interpretations, limiting the practical value the AI system.
Network Input
movie
prediction
haseline
Interpretation
12.7%
-3.6%
6.8%
50.4%
Network Input
this
movic
18
good
prediction
haseline
Interpretation
14.3%
-5.3%
9.1%
19.2%
87.7%
50.4%
Figure 1: Interpretations generated by SHAP movie review.
Consistency (see Definition 2.2) is certainly not the only objective for interpretability. Being equally important, efficiency is a commonly used axiom in the attribution methods [72, 22, 59], also called local accuracy [38] or completeness [60], stating that the model's output should be equal to the network's s output for the given input (see Definition 2.3). Naturally, one may ask the following question:
Q1: Can we generate an interpreting model that is both consistent and efficient?
Unfortunately, this is generally unattainable. We have proved the following theorem in Section 2:
Theorem 1(Impossible trinity, informal version). For post-hoc interpreting models, interpretability, efficiency and consistency cannot hold simultaneously.
A few examples following Theorem 1:
(a) Most attribution methods are interpretable and efficient, but not consistent.
(b) The original (deep) network is consistent and efficient, but not interpretable.
(C) If one model is interpretable and consistent, cannot be efficient.
However, consistency is necessary for many scenarios, leading to the follow-up question:
Q2: For consistent interpreting models, can they be approximately efficient?
The answer depends on the definition of "approximately efficient". We introduce new notion called truthfulness, which serves as a natural relaxation of efficiency, or partial efficiency. We divide the functional space of a network f into two subspaces: the readable part and the unreadable part. We call the interpreting model g truthful as V (see Definition 2.4). The unreadable part is not merely a "fitting error"; it truthfully represents the higher-order non-linearities in the network that our interpretation model g. even its best, cannot cover. In short, what g conveys is true, though it may not encompass the entire truth. Due to Theorem 1, this is essentially the best that consistent algorithms can achieve.
can accurately represent the readable part of f. denoted
Truthfulness is parameterized notion, depending on the choice of the readable subspace. While there are theoretically infinite possible choices, we follow previous researchers on interpretability with non-linearities [61, 41, 63], using the basis that induces interpretable terms like æııy 2 These capture higher-order correlations and are easy understand. The resulting subspace has the standard polynomial basis (or equivalently, the Fourier basis).
When truthfulness is parameterized with the polynomial basis, designing consistent and truthful interpreting models is equivalent to learning the Fourier spectrum (see Algorithm and Lemma 3.4). However, exact consistency is not always necessary for most real-world applications, approximate consistency is usually sufficient. We formally use the number of different interpreting models (in log scale) as a metric for inconsistency. Our last question
Q3: When a little inconsistency allowed, can we get better interpreting models?
We affirmatively answer this question in Section 4 by introducing a new algorithm called Harmonica- local. We then apply multiple times to develop Harmonica-anchan and Harmonica-anchor- constrained, which offer smaller interpretation emros with small degree of inconsistency.

---

In this paper, we focus on removal censval-based explanations [18], which implies that f and are Boolean functions. We remark that empirically most networks are not Boolean functions, i.e., the input variables are real valued. However, for every explanation algorithm (including LIME [47] and SHAP [38]) in the removal-based framework, the input z is not modified an arbitrary real value. Instead, z is fixed, and the algorithm only retain or remove each feature of x for generating the explanations. When æ is fixed with n features, it becomes natural to use Boolean functions to represent both the network and the interpreting model for their outputs in all 2n feature-removal scenarios. In other words, the algorithms in the framework only consider a fixed æ each time, and given this x, there are only 2" possible outcomes, treating f and 9 as Boolean functions is not a simplification, but an accurate characterization of the removal-bree based framework (see Figure 1 in [18] for an illustration).
for the models with real inputs. Therefore,
Our new algorithms, including Harmonica-local, Harmonica-anchor, and Harmonica-anchorr- constrained, are all based on the Harmonica algorithm from Boolean functional analysis [27], which has rigorous theoretical guarantees on recovery performance and sampling complexities. In Section we demonstrate that datasets like IMDb and ImageNet, our algorithms achieve up to 31.8x lower interpretation error compared with other methods.
In summary, our contributions are:
We prove the impossible trinity theorem for removal-based explanations, demonstrating that interpretable algorithms cannot be consistent and efficient simultaneously.
When a small inconsistency is allowed, we propose new algorithms using Harmonica-local and empirically demonstrate that these algorithms achieve significantly lower interpretation errors compared with other methods.
For interpretable algorithms that are consistent but not efficient, we introduce a new notion called truthfulness, which can be regarded as partial efficiency. Due to the impossible trinity theorem, this the best achievable outcome when consistency is required.
Our Framework on Interpretability
We consider Hilbert space H equipped with inner product (.. and induced norm -| We denote the input space by X. the output space by V. which means H. S X + V. We use C to denote the set of interpretable functions, and F c. H to denote the set of machine learning models that need interpretation. In this paper, if not mentioned otherwise we focus on models that are not G.
self-interpretable, i.e.,
Definition 2.1 (Interpretable and Interpretation Algorithm). We call A model is interpretable, if g E G. An interpretation algorithm A takes f H. E X' inputs, and outputs A(f, E 9 for interpreting f on x.
As we mentioned previously, for many interdisciplinary fields, the interpretation algorithm should be consistent.
Definition 2.2 (Consistent). Given f E H. an interpretation algorithm A is consistent with respect to f. if A(f, .)) remains the same (function) for every x X.
Efficiency is an important property of the attribution methods.
Definition 2.3 (Efficient). A model g E H efficient with respect to f E F on x E X, g(x) fx)).
The following theorem states that one cannot expect to achieve the best of all three worlds.
Theorem (Impossible Trinity for Removal-based Explanations). For any interpretation algorithm A and function sets C F C H. there exists f F such that with respect to f, either A is not consistent, or A(f, x) is not efficient on x for some x E X.
Proof. Please refer to Appendix B for all the proofs.
Theorem says efficiency is too restrictive for consistent interpretations. However, being inefficient does not mean the interpretation wrong, it can still be truthful. Recall a subspace V/ C H closed if whenever {fr} C. V converges some f E H. then f V. We have:
3

---

Definition 2.4 (Truthful gap and truthful). Given a closed subspace V S M V and f F. the truthful gap of g for V is:
(v - fl gll
inf |l e1l?.
-EV
When (f. = O. we say g is truthful for subspace with respect to f. and we know (see e.g. Lemma 4.1 in [56]) Vou E V. (f g. v) 0.
Truthfulness means g fully captures the information in the subspace of f. therefore it can be seen natural relaxation of efficiency. To characterize the interpretation quality, we introduce the following notion.
Definition 2.5 (Interpretation error). Given functions f.g E X y. the interpretation error between and with respect to measure is
1/P
Notice that interpretation error is only a loss function that measures the quality of the interpretation, instead of a metric in lp space. Therefore, Jr can be non-uniform weight distribution following the data distribution. If is uniform distribution over X, we abbreviate (f) g) as Ip(f.g). For real-world applications, interpreting the model over the whole X' is unnecessary, so p is usually defined as a uniform distribution on the neighborhood of input x (under a certain metric). in which case we denote the distribution Ng
3 Applying Our Framework to Removal-based Explanations
Now we focus on interpreting removal-based explanations [38, 18). Removal-based explanations are post-hoc, which means they are generated based on target network for a fixed input, by removing features from that input. There are three choices affecting the removal-based explanations: how features are removed, what behavior is analyzed after feature removal, and how to summarize the feature influence. For example, SHAP [38] considers all possible subsets of the features, and analyzes how holding out different features affects functional value, and finally summarizes the differences based on the Shapley value calculation.
Therefore, removal-baun based explanations can be represented as Boolean functions, as feature subset S S [n]] can be represented as Boolean input: f [- - E. where -1 means the specific feature i E S is removed, means the specific feature is retained. We use 1111 instead of 0/1 to represent the binary variables for ease of exposition using the Fourier basis.
3.1 Fourier Basis and Truthful Gap
Fourier analysis handy tool for analyzing Boolean functions. Due the space limit, defer the more comprehensive introduction on Fourier analysis for Boolean functions to Appendix A, and only present the necessary notions here.
Definition 3.1 (Fourier basis). For any subset of variables S C [n]]. we define the corresponding Fourier basis (x) 1lies2; 1-1, + 111
The Fourier basis also called polynomial basis in the literature. It is a complete orthonormal basis for Boolean functions, under the uniform distribution on 13" We remark that this uniform distribution is used for theoretical analysis and algorithm design, and is different from the measure fa for interpretation quality assessment in Definition 2.5.
Definition 3.2 (Fourier expansion). Any Boolean function f 11 + IR can be expanded as
f(x)
Σ Sclm
fsxs(x).
where fs = (f.x) is the Fourier coefficient on S.
Now we define the notion of C-Readable function.

---

Definition 3.3 (C- RC--Redable function). Given set of Fourier bases C, function is C-readable if it supported on C. That is, for any Xss & C. (f. Xs) = 0. Denote the corresponding subspace as Vc-
The Readable notion is parameterized with C, because it may differ case by case. If we set C to be all the single variable bases, only linear functions are readable; we set to all the bases with the degree at most 2, functions with pairwise interactions are also readable. Moreover, if we further add one higher order term to C, c.g., X(1 aa. means we can also reason about the factor an 2223344 in the interpretation, which might be an important empirical factor that people can easily understand. Starting from the bases set C, we have the following formula for computing the truthful gap.
Lemma 3.4 (Truthful gap for Boolean functions). Given a set of Fourier bases C, two functions fig E 1)" + I, the trutfuul gap of g to f for C' is
Tvc (f.g)
E(f-9) -
XsEC
With the previous definitions, it becomes clear that finding truthful interpretation g is equivalent to accurately learning a Boolean function with respect to the readable bases set C. Intuitively, means we want to find algorithms that can compute the coefficients for the bases in C. In other words, we want to find the importance of the bases like 21, 22 2 22 etc.
3.2 Representative Algorithms
Applying the impossible trinity theorem to removal- explanations, there are two notable algo- rithms on the extremes.
Shapley values: efficient but not consistent. Let N = {1,2, n} represent a set of n players, and let v: 2 + R be characteristic function that assigns real value to each coalition of players. The Shapley value of player is given by:
(n 11 1)!-1SI 1S!!
(.(v)
Σ SCNY
-
(4)
nd!
where |S] is the number of players coalition S, and the sum taken over possible coalitions S that do not include player i. One of the most important properties of Shapley values is efficiency,
iee. EiEN (x(v) = vi(
v(0) (or denoting explanation function 9 _ EieN (:(v) + v())). As Shapley value based explanations do not focus on consistency, its explanation is efficient only for the original input, but not for other scenarios when certain features are removed.
consistent but not efficient. What can we do if want address consistency? As mentioned in Definition 2.4, we do not expect the algorithm to be efficient, but it can still be truthful with respect to subspace V. which is naturally represented with the polynomial basis. Therefore, in order to learn truthful explanations for given subspace V, it is natural to consider LASSO regression over the coefficients on the polynomial basis. Harmonica (Algorithm fulfills this requirement [27] and has superior complexity shown in Theorem 2.
Harmonica:
Algorithm 1: Harmonica [27]
1. Given uniformly randomly sampled .1, , ,r, evaluate them on f: (f11), ..... ((rr)).
2. Solve the following regularized regression problem.
T
argmin aERICI
Σ
asxs(x;) asxs(u))- -(as) + +allalli
(5)
SXx8EC
3. Output the polynomial g(z) = Es.xee asXs(r).
Theorem 2 (Complexity of Harmonica). Given f E 1 + RR (e/4, bounded function, Algorithm finds a function with interpretation error at most in time O(T + [Clcc) (C)) and sample complexity T = Ō(s² /e- log (C]).
5

---

We defer detailed descriptions and theoretical guarantees of these algorithms to Appendix B.I, C and discussion on the comparison of our algorithms with the existing algorithms to Appendix E.
3.3 Quantifying Inconsistency
All the Fourier coefficients together are called the Fourier spectrum of f. We can define the fol- lowing distance between two functions based on their spectrums as the quantitative measure of the inconsistency between different explanations.
Definition 3.5 (Spectrum (Fourier) distance for Boolean functions), Given two interpretations g(),(()) E 1 + I, we define the spectrum p-distance between them as:
1/p
Do (g(), & 11g- -hlpp-
Σ SC
gs hs
(6)
As there may be many candidates p for evaluating interpretation error and spectrum distance. In the following, we will investigate the most natural choice for p. As the Fourier expansion uniquely determined a Boolean function. We would like the distance between their expansion to have the same tendency as the interpretation error, thus the spectrum can encode enough information reflect the accuracy of the interpretation. We shall first discuss the most "strict" case, i.e. the Lo norm.
Denote the support of an Boolean function f as sfpp(f) & E f(x) &f 0). The support of Fourier coefficients (Fourier spectrum), is defined by supp(f) & (S [n] f(()) + 0}. Based on Proposition C.I, we have the following uncertainty principle for removal- explanations: Theorem 3 (Uncertainty Principle for Removal-based Explanations), Assume f.g E (- IR and f + When evaluated under Lo norm, the interpretation error and spectrum distance (inconsistency value) have the following uncertainty principle (can be seen quantitative version of Impossible Trinity Theorem l):
To(J.g)Do(J.D) 2
We can see that the Lo norm is too strict for evaluating the differences between interpretations (inconsistency). Fortunately, the following proposition shows that the L2 relaxed version is much better, or to say, natural, due to Parseval's 's identity.
Proposition 3.6 (L2 norm is natural). When taking μ. uniform distribution, for f.g {-1,1)" " + R, we have (12 g) = (2(
Now we present a theorem on the trade-off between efficiency and consistency, quantified by total interpretation error and total inconsistency value (spectrum distance).
Theorem 4 (Trade-off between Efficiency and Consistency). Given function f f1- 1]" R
and a set of N interpretable functions {91: ,9N) defined on disjointed sets X; (X' = UX)),
each gi : (-1,1) 1)" + R. let denote the average (spectrum) of g; across the space X' {-1,1)
Define (we use L2 norm as default):
N
hotal
Σ
|| -9ilze>; ll2,
Donal
lorkex -
Then, we have the following inequality:
Towa
Diotal
|| - gleex:112.
In addition, denote gt as the globally consistent interpretation of defined on {-1,1}" with minimal interpretation error (can be obtained by Harmonica), we have:
||lex - Ilnex,112 >
M|,ex - g'Inex, 1|2 = I2(s.g') D2(f.g').

---

Algorithm 2: Harmonica-anchor
Input:
anchor number k, model f. a distance metric function :(- (Xs Xs) + which calculates distance between two anchors (e.g., Lp norm or Hamming distance), sampling number T, regularization coefficient A1-
Output: interpretation models yi with coefficients 0; RRC1, 1,2,3,
Fix random bases b,. i 1, 1,2, 2, ..... as anchors.
2: Randomly sample 7' bases b1. b2, ....... by and accordingly, we calculate ( f(rr). Assign each basis to the anchor with minimal distance and index using
d; = min min (argmin, d(b,, b)),,
2, ... and 3,
4: for i = 1, 3, ...,.,, do
5: Solve the following regularized regression problem:
T
argmin ECERIC
Σ
[[(i dn)
Σ ar,sx((an) - -f(e)) Allculle
(8)
SXsEC
6: end for
This theorem illuminates the inherent trade-offs in designing interpretable models. Specifically, to reduce Lonal. one would typically need to increase Dioall unless f itself is close to an interpretable model g. Theorem 4 can also be seen as a quantitative version of the Impossible Trinity Theorem for removal-baut based explanations.
Now we established the lower bound of Uoosal + Droal by 12(f.g') (the same as D2 ()). showing the trade-off between efficiency and consistency, and also bridging the locally consistent interpretations Ii and globally consistent interpretation g².
4 Trade-off Between Efficiency and Consistency
Harmonica recovers functions across the entire function space. However, in our setting, if Wf is small, is sufficient to recover a small neighborhood of the function. This inspires to apply Harmonica to local space instead of the entire space. By doing so, we obtain more concentrated samples in the local neighborhood. Consequently, minimizing the interpretation error in this neighborhood becomes more manageable. We refer to Harmonica with samples in the local neighborhood as Harmonica-local.
If we relax the consistency requirement, meaning that users are willing to accept minor inconsistencies interpretations when slight modification is made the input, we can achieve smaller interpretation error with Harmonica-ancie
as shown in Algorithm 2. Intuitively, Harmonic-anchor applies multiple Harmonica- local algorithms to different subspaces of the imput. Specifically, for given neighborhood region Nz, we now randomly select k, bases br.s, (i = 1, 3, .... kz) as interpretation anchors instead of only one basis Harmonica does. We calculate k, interpretation models Jr,i on each anchor and denote the coefficient of 9z.i as Oz,i. For simplicity, we omit the subscript in the following.
The number of bases k is highly related to consistency, so we could define the log value log k to evaluate the inconsistency of the interpretation models. The minimum inconsistency value as in Harmonica (k = 1). while for attribution methods, the inconsistency should be almost n. which the number input variables. The maximum inconsistency value depends on the neighborhood region Nz, since the number of interpretation models should not exceed the number of points in Mz. As special ease, the Harmonica algorithm achieves 0 inconsistency, making it the most consistent algorithm.
However, if one only considers the number of different interpretation algorithms, users may still encounter high level of inconsistency empirically when the interpretations significantly differ from one another. Thus, another critical constraint to add is the spectrum distance constraint among different interpretations of different anchors. Based on Theorem 4, we introduce Harmonica-anchor- constrained in Algorithm (in Appendix). In this algorithm, A2 serves as penalty coefficient for the difference between 9., and we solve the problem using iterative gradient descent. Intuitively, larger
7

---

A restricts the expressive power of the interpretation models Ii, leading to larger interpretation eπrо
Experiments
5.1 Analysis on Polynomial Functions
To investigate the performance of different interpretation methods, manually examine the output of various algorithms including LIME [47], SHAP [38], Shapley Interaction Index [45], Shapley Taylor [61, 26], Faith-SHAP [62]. Harmonica, and Low-degree (Appendix D) for lower-order polynomial functions.
We observe that all algorithms can accurately learn the coefficients of the first-order polynomial. For the second-order polynomial function, only Shapley Taylor, Faith-SHAP, Harmonica, and Low-degree can learn all the coefficients accurately. For the third-order polynomial function, only Faith-SHAP, Harmonica, and Low-degree succeed. Due space constraints, we defer the details to Appendix F.
5.2 Experimental Setup
In the rest of this section, we conduct experiments to evaluate the interpretation error Ip.Ng. (f.g) and truthful gap Tv (f.g g) of Harmonica and other bascline algorithms on language and vision tasks quantitatively. In our experiments, we choose 2nd order and 3rd order Harmonica algorithms,, which correspond to setting to include all terms with order at most and
The baseline algorithms chosen for comparison include LIME [47], Integrated Gradients [60], SHAP [38], Integrated Hessians [30], Shapley Taylor interaction index, and Faith-SHAP, where the first three are first-order algorithms, and the last three are second-order algorithms.
The language tasks select are the SST-2 [55] dataset for sentiment analysis and the IMDb [40] dataset for movie review classification. The vision task is the ImageNet [33] for image classification. To demonstrate the capability of interpretation framework applied to vision tasks, have generated two examples in Figure 2, compared with LIME, Integrated Gradients (IG), and SHAP. Note that all of these methods are applied the same ground- truth image segmentation provided by the MS-COCO dataset [35]. For ablations on using the SLIC superpixels [2]. please refer to Appendix H.
Cet
Harmonica 2nd
UIE
G
SHAP
Figure 2: Illustrative examples for applying our interpretation method on MS-COCO dataset.
For the SST-2 dataset, we attempt to interpret a convolutional neural network (see details Ap- pendix G) trained with the Adam [32] optimizer for 10 epochs. The IMDb dataset contains long paragraphs, and each paragraph has multiple sentences. By default, we use periods, colons, and exclamations to separate sentences. For the ImageNet [33] dataset, we aim provide class-specific interpretation, meaning that only the class with the maximum predicted probability is considered for each sample. We use the official pre- trained ResNet-101 [28] model from PyTorch.

---

Harmonica (2nd order) Harmonica (3rd order)
Integrated Gradients
Hamoniica-ame anchor (k=3)
Integrated Hessians
Hamonica-anchhn (k=5)
LIME
Shapley Taylor Index (2nd order)
Hamonicc-anee anchhrr (k=7)
SHAP
Faith-Shap (2nd order)
Hamonica-ancher (K=9)
ImageNet
Interpretation error
Interpretation error
10-1
10a
22.8x
31 31.Bx
10
10-
Subspace radius
Subspace radius
Figure 3: Visualization of L interpretation error 1, (f.g) of several state-of-the-art interpretation methods evaluated on IMDb and ImageNet datasets.
5.3 Results on Interpretation Error
For given input sentence with length we define the induced neighborhood N₂ by introducing masking operation on this sentence. The radius 0 < r S is defined as the maximum number of masked words.
Figure displays the 1,2 interpretation error evaluated under different neighborhoods with a radius ranging from to for all the considered datasets. Here, ac represents the maximum sentence length, which may vary for different data points. We also inspect L and L norms, Here, 2 and L are defined according to Eqn. (2) with p 2 and p respectively. And L denotes [x 11 f() - g(x)l 2 0.1dp(z).. We can see that Harmonica consistently outperforms all the other baselines all radii.
Note that for IMDb in Figure 3, we make a slight modification such that the masking operation is performed sentences in one input paragraph instead (we also change the definition of radii accordingly). For ImageNet in Figure 3, the interpretation error is evaluated on 1000 random images, and the masking operation is performed on 16 superpixels in one input image instead (we also change the definition of radii accordingly). We can see that when the neighborhood's radius is greater than 1, Harmonica outperforms all the other baselines. Specifically, when evaluated on ImageNet (k = 9) achieves 31.8 times lower interpretation error 12, compare Integrated Gradients [60]. Limited by space, the detailed numerical results and interpretation error under other norms are presented in Appendix I. In contrast, Harmonica-local achieves more accurate local consistency but high error outside the neighborhood. The relevant results are deferred in Appendix J due to limited space.
dataset, Harmonica-anchhe
As mentioned in Section 4, Harmonica-anchor further reduces the interpretation error by learning each subspace separately. Figure 3 shows that the T.2 interpretation error of Harmonica-anchor achieves lower error than Harmonica on various datasets, and the error further declines increase the number of anchors. Full results other norms and the results are shown Appendix L.
Table 1: Comparison C truthful gap Tc(f, g) results evaluated on IMDb and ImageNet datasets (lower truthful gap means better truhhfulness of the interpretation).
Harm. 2nd
Harm. 3rd
Shapley Taylor
Faith- Shap
Method
LIME
SHAP
IG
IH
IMDb
0.540
0.174
5.343
1.390
1,438
1.948
7.005
15.528
ImageNet
0.660
0.246
0.738
2.023
1.848
175.368
0.474
0.430
5.4 Results on Truthful Gap
For convenience, we define the set of bases Odd up to degree d as Cd = (xs|S c
[n],]S] < d).
We evaluate the truthful gap the set of bases 3 2 and C² For implementation details

---

calculating the truthful gap, please refer to Appendix K. Table I shows the C truthful gap evaluated on different datasets. We can see that Harmonica outperforms all the other baseline algorithms. Due to space limitations, C2 and Ct results are provided in Appendix K.
5.5 More Experimental Results
For more experimental results on different image segmentation methods, different neural network architectures, and different choices of baselines, please refer Appendix H. For more results on the Low-degree algorithm, please refer to Appendix M.
6 Related Work
Interpretability is a critical topic in machine learning, and we refer the reader to [20, 37] for insightful general discussions. Below we discuss different types of interpretable models.
Removal-based explanations. Covert et al. [18] presents unified framework for removal-based model explanation methods, connecting 26 existing techniques such as LIME [47], SHAP [38], Meaningful Perturbations [21], and permutation tests [10]. LIME [47] is a classical method that samples data points following predefined sampling distribution and computes function that empirically satisfies local fidelity.
The Shapley value [50, 72, 24] originates from cooperative game theory and is used to allocate the total value generated by group of players among individual players. It is the unique kind of method that satisfies few important properties, including efficiency, symmetry, dummy, additivity, etc. Shapley values have been extensively applied to machine learning model explanations [38, 39, 57, 59, 67, 78, 23, 77] and feature importance [17]. Recent research has focused on developing efficient approximation methods for Shapley values [38, 15, 5, 16, 31, 26, 68]. Many works have generalized Shapley values to higher-order feature interactions [45, 24, 61, 41, 63, 1, 62].
Gradient-base based explanations. Gradient-based explanations are popular for deep learning models, such as CNNs. These methods include SmoothGrad, Integrated Gradient, GradCAM, Deepl.ft, LRP, etc. [53, 54, 52, 60, 74, 49, 6, 51, 13, 42, 52, 48]. Although these methods have seen extensive use in various areas, gradient- based methods are often time-consuming and can be insensitive to random model parameterization [3].
Model-specific interpretable models. Interpretable or transparent (white-box) models are inherently ante-hoc and model-specific. One primary goal of utilizing interpretable models is to achieve inherent model interpretability. Prominent approaches include Decision Trees ([66, 7, 75]), Decision Rules (169, 58]). Decision Sets ([34, 70]), and Linear Models (164, 65]). Moreover, another research direction attempts to use an interpretable model surrogate to approximate the original black-box models. [14] employs two-layer additive risk model for interpreting credit risk assessments. [8] suggests an approach called model extraction that greedily learns a decision tree to approximate f. However, these methods primarily rely heuristics and lack theoretical guarantees.
7 Conclusion
In this paper, we tackled the problem of generating consistent interpretations and introduced the impossible trinity theorem of interpretabillty, under a formal framework for understanding the interplay between interpretability, consistency, and efficiency. Since consistent interpretation cannot be efficient, we relaxed efficiency to truthfulness, meaning the interpretation matches the target function in a specific subspace. This led to the problem of learning Boolean functions and the proposal of new algorithms based on the Fourier spectrum and a localized version of Harmonica. Our methods showed lower interpretation errors and improved consistency compared to the existing approaches.
While our work offers theoretical insights, many open questions and challenges remain in building more interpretable, consistent, and efficient models. We hope our work serves as a foundation for future research in the area of cxplainable AI.
10

---

Acknowledgments
Thanks to Jiaye Teng for the useful discussions. This work is supported by the Ministry of Science and Technology of the People's Republic China, the 2030 Innovation Megaprojects "Program on New Generation Artificial Intelligence" (Grant No. 2021 AAA01
References
[1] Kjersti Aas, Martin Jullum, and Anders Løland. Explaining individual predictions when features are dependent: More accurate approximations to shapley values. Artificial Intelligence, 298: 103502, 2021.
[2] Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk. Slic superpixels. Technical report, EPFL. 2010.
[3] Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. Advances in neural information processing systems, 31, 2018.
[4] Zeyuan Allen-Zhu and Yang Yuan. Improved svig for non-strongly-coneer or sum-of-non. convex objectives. In International Conference Machine Learning, pp. 1080-1089. PMLR, 2016.
[5] Marco Ancona, Cengiz Oztireli, and Markus Gross. Explaining deep neural networks with polynomial time algorithm for shapley value approximation. In International Conference on Machine Learning, pp. 272-281. PMLR, 2019.
[6] Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Claus-Robert Müller, and Wojciech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 10(7):00130100, 2015.
[7] Randall Balestriero. Neural decision trees. ArXiv, wws///02.001111 702.07360. 2017.
[8] Osbert Bastani, Carolyn Kim, and Hamsa Bastani, Interpretability via model extraction. ArXiv, abs/1706.09773, 2017.
[9] William Beckner. Inequalities fourier analysis. Annals of Mathematics, 102(():159-182,
1975.
[10] Leo Breiman. Random forests. Machine learning, 45:5-32, 2001.
[11] Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXhv:2303.12711 2023.
[12] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 9650-9660, 2021.
[13] Hila Chefer, Shir Gur, and Lior Wolf. Transformer interpretability beyond attention visualization. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pallern Recognition, pp- 782-791, 2021.
[14] Chaofan Chen, Kangcheng Lin, Cynthia Rudin, Yaron Shaposhnik, Sijia Wang, and Tong Wang. An interpretable model with globally consistent explanations for credit risk. ArXiv, abs/181 2018.
[15] Jianbo Chen, Le Song, Martin J. Wainwright, and Michael I. Jordan. L-shapley and c-shapley: Efficient model interpretation for structured data. ArXiv, abs/1808 000.02210, 2019.
[16] Ian Covert and Su-In Lee. Improving kernelshap: Practical shapley value estimation using linear regression. International Conference on Artificial Intelligence and Statistics, pp. 3457-3465. PMLR, 2021.
11

---

[17] Ian Covert, Scott M Lundberg, and Su-In Lee. Understanding global feature contributions with additive importance measures. Advances in Neural Information Processing Systems, 33: 17212-17223, 2020.
[18] Ian Covert, Scott M Lundberg, and Su-In Lee. Explaining by removing: A unified framework for model explanation. The Journal of Machine Learning Research, 22:209-1, 2021.
[19] Amir Dembo, Thomas M Cover, and Joy A Thomas. Information theoretic inequalities. IEEE Transactions on Information theory, 370)):50 1991.
[20] Derek Doran, Sarah Schulz, and Tarek R. Besold. What does explainable ai really mean? a new conceptualization of perspectives. ArXiv, (/bs/1710.00999 2017.
[21] Ruth C Fong and Andrea Vedaldi. Interpretable explanations of black boxes by meaningful perturbation. In Proceedings of the IEEE international conference on computer vision, pp. 3429-3437, 2017.
[22] Eric Friedman and Herve Moulin. Three methods share joint costs or surplus. Journal of Economic Theorr, 87222275-33,, 1999.
[23] Christopher Frye. Colin Rowat, and llya Feige. Asymmetric shapley values: incorporating causal knowledge into -ggnssig explainability. Advances in Neural Information Processing Systems, 33:1229-12333 2020.
[24] Michel Grabisch and Marc Roubens. An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of Game Theory, 28:547-565, 1999.
[25] Tom Gur and Omer Tamuz. Testing booleanity and the uncertainty principle. arXiv preprint 1204 0944, 2012.
[26] Mark Hamilton, Scott M. Lundberg, Lei Zhang, Stephanie Fu, and William T. Freeman. Ax- iomatic explanations for visual search, retrieval, and similarity learning. In International Conference on Learning Representations, 2022.
[27] Elad Hazan, Adam R. Klivans, and Yang Yuan. Hyperparameter optimization: A spectral approach. ArXiv, abs/1 706.00764 2018
[28] Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
[29] Isidore I Hirschman. A note on entropy. American journal of mathematics, 1957.
79(1)152--156.
[30] Joseph D. Janizek, Pascal Sturmfels, and Su-In Lee. Explaining explanations: Axiomatic feature interactions for deep networks. J. Mach. Learn. Res., 22: 12:1004:110::::: 2021.
[31] Neil Jethani, Mukund Sudarshan, Ian Connick Covert, Su-In Lee, and Rajesh Ranganath. Fastshap: Real-time shapley value estimation. In International Conference on Learning Repre- sentations, 2021.
[32] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Arxiv, abs/1412.6980, 2015.
[33] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60:84 - 90, 2012.
[34] Himabindu Lakkaraju, Ece Kamar, Rich Caruana, and Jure Leskovec. Faithful and customizable explanations of black box models. In Proceedings of the 2019 AAAI/ACM Conference on Al, Ethics, and Society, pp. 131-138, 2019.
[35] Tsung-Yi Lin, Michael Maire, Serge Belongie, Lubomir Bourdev, Ross Girshick, James Hays, Pietro Perona, Deva Ramanan, C. Lawrence Zitnick, and Piotr Dollár, Microsoft coco: Common objects in context, 2015.
12

---

[36] Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. Journal of the ACM (JACM), 4063):607-620, 1993.
[37] Zachary C Lipton. The mythos of model interpretability: In machine learning, the concept of interpretability is both important and slippery. Queue, 16(3):31-55) 2018.
[38] Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances Neural Information Processing Systems, 2017.
[39] Scott M. Lundberg, Gabriel G Erion, and Su In Lee. Consistent individualized feature attribution for tree ensembles. arXiv preprint arXiv:1802 03888, 2018.
[40] Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts, Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pp. 150,
2011.
[41] Aria Masoomi, Davin Hill, Zhonghui Xu, Craig Hersh, Edwin K. Silverman, Peter J. Castaldi, Stratis loannidis, and Jennifer G. Dy. Explanations of black-box models based on directional feature interactions. International Conference on Learning Representations, 2022.
[42] Grégoire Montavon, Sebastian Lapuschkin, Alexander Binder, Wojeiech Samek, and Klaus- Robert Müller. Explaining nonlinear classification decisions with deep taylor decomposition. Pattern recognition, 65:211 15:211-222, 2017.
[43] Ryan O'Donnell, Analysis of boolean functions. Cambridge University Press, 2014.
[44] Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo, Mare Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, et al. Dinov2: Learning robust visual features without supervision. arXiv preprint urXiv:2304.07/99 0733,, 2023.
[45] Guillermo Owen. Multilinear extensions of games. Management Science, (8(5-part-2):64--9 1972.
[46] Jeffrey Pennington, Richard Socher, and Christopher 1) Manning. Glove: Global vectors for word representation. Proceedings of the 2014 conference on empirical methods natural language processing, pp. 1543, 2014.
[47] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. wwh should trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 1135-11460 1144, 2016.
[48] Patrick Schwab and Walter Karlen, Cxplain: Causal explanations for model interpretation under uncertainty. Advances in Neural Information Processing Systems, 32, 2019.
[49] Ramprasaath R. Selvaraju, Abhishek Das, Ramakrishna Vedantam, Michael Cogswell, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. International Journal of Computer Vision, 128:336-359, 2017.
[50] Lloyd S. Shapley. Quota solutions of n-person games. Edited by Emil Artin and Marston Morse, pp. 343, 1953.
[51] Avanti Shrikumar, Peyton Greenside, Anna Shcherbina, and Anshul Kundaje. Not just black box: Learning important features through propagating activation differences. CORR, Abs/1605.0177 2016.
[52] Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International Conference on Machine Learning, pp. 3 3145-3153, PMLR, 2017.
[53] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. CoRR, abs/1312.600 2014.
[54] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda B. Viégas, and Martin Wattenberg. Smooth- grad: removing noise by adding noise. ArXiv, abs/1706.03825, 2017.
13

---

[55] Richard Socher, Alex Perelygin. Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 conference empirical methods in natural language processing. pp. 1631-1642, 2013.
[56] Elias M Stein and Rami Shakarchi. Real analysis: measure theory, integration, and Hilbert spaces. Princeton University Press, 2009.
[57] Erik Strumbelj and Igor Kononenko. with feature contributions. Knowledge and information systems, 41(3):647-666 2014.
Explaining prediction models and individual predictions
[58] Guolong Su, Dennis Wei, Kush R. Varshney, and Dmitry M. Malioutov. Interpretable two-level boolean rule learning for classification. ArXiv, abs/151 2015.
[59] Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. In International Conference on Machine Learning, pp. 9269-99999999 2269-9278. PMLR, 2020.
[60] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International Conference Machine Learning, pp. 3319-3328, PMLR, 2017.
[61] Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The shapley taylor interaction index. In International conference machine learning, pp. 9259-9268. PMLR, 2020.
[62] Che-Ping Tsai, Chih-Kuan Yeh, and Pradeep Ravikumar. Faith-shap: The faithful shapley shapley interaction index. arXiv preprint arXi::2203.00877, 2022.
[63] Michael Tsang, Sirisha Rambhatla, and Yan Liu. How does this interaction affect me? in- terpretable attribution for feature interactions. Advances in Neural Information Processing Systems, 33:6147-6159 2020.
[64] Berk Ustun and Cynthia Rudin. Methods and models for interpretable linear classification. ArXiv, abs/1405 4iss/1405.4047, 2014.
[65] Berk Ustun, Stefano Tracà, and Cynthia Rudin. Supersparse linear integer models for inter- pretable classification. ArXiv, abs/1306.6677, 2014.
[66] Jialei Wang, Ryohei Fujimaki, and Yosuke Motohashi. Trading interpretability for accuracy: Oblique treed sparse additive models. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1245-1254, 2015.
[67] Jiaxuan Wang, Jenna Wiens, and Scott Lundberg. Shapley flow: A graph-based approach interpreting model predictions. In International Conference on Artificial Intelligence and Statistics, pp. 721-729. PMLR, 2021.
[68] Rui Wang, Xiaoqian Wang, and David I. Inouye. Shapley explanation networks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
[69] Tong Wang, Cynthia Rudin, Finale Doshi- Velez, Yimin Liu, Erica Klampfl, and Perry MacNeille. Or's of and's for interpretable classification, with application to context-aware recommender systems. ArXiv, abs/ has/1504.07644. 2015.
[70] Tong Wang. Cynthia Rudin, Finale Doshi Velez, Yimin Liu, Erica Klampil, and Perry MacNeille. A bayesian framework for learning rule sets for interpretable classification. The Journal of Machine Learning Research, 18(1):3357-2393 2017.
[71] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint or 2rXiv:2203.111777 2022.
[72] Robert Weber. Probabilistic values for games, the shapley value, essays in honor of lloyd s. shapley (ac roth, ed.), 1988.
14

---

[73] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoe Le. and Denny Zhou. Chain of thought prompting elicits reasoning large language models. arXiv preprint arXiv:2201. 19003 2022.
[74] Shawn Xu, Subhashini Venugopalan, and Mukund Sundararajan. Attribution in scale and space. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 1 13-19, 2020, pp. 9677-9686. Computer Vision Foundation IEEE, 2020. doi: 10L1100CCVR4422002200000077
[75] Yongxin Yang, Irene Garcia Morillo, and Timothy M. Hospedales. Deep neural decision trees. ArXiv, abs/1 806.06986..8. 2018.
[76] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305.10600 2023.
[77] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang On explainability of graph neural networks via subgraph explorations. In International Conference Machine Learning, pp. 12241-12252. PMLR, 2021.
[78] Hao Zhang. Yichen Xie, Longjie Zheng, Die Zhang, and Quanshi Zhang. Interpreting mul- tivariate shapley interactions in dnns. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10877-10886, 2021.
[79] Yifan Zhang, Jingqin Yang, Yang Yuan, and Andrew Chi-Chih Yao. Cumulative reasoning with large language models. arXiv preprint arXiv:2308.0457 2023.
15

---

Pseudo Code for Harrmonic--ncbor-costttreeddd
Algorithm Harmoonice-anccoo-coossttniiei
Input:
anchor number k; model f. distance metric function d(-: -) (Xss xs) + R which calculates distance between two anchors (e.g., Hamming distance or Lp norm), sampling number T. loss balance coefficient Ag, update epochs E, update rate 1)
Output: interpretation models 9: with coefficients a;,, i 1, 2, ....k. k.
1: Fix random bases b; i 1, 3...., 1 as interpretation anchors.
2: Randomly initialize a; [RICI, 1,2,3, ...... k.
3: Randomly sample T bases b1, bb...... by and accordingly, calculate f(x1), f (x2), ... f(rr).
4: Assign each basis to the anchor with minimal distance and index with
d min { argmin, d(b,, b,),,,,),. 3, ...T and 1,2, 3, ....k.
5: for 1,2,3, E do
T.f Σ Exxeeo%, (amo))-(((x)) f(x)))
6:
7:
L, = - ||ailli.
8: L = = |lo; 1 Σ ==== 1y
9: Update 04 with oç a; 1f
+ t tobc))
da.
end for
A Fourier Analysis of Boolean Function
Fourier analysis of Boolean function is fascinating field, and refer the reader to [43] for more comprehensive introduction. We define the inner product as follows.
Definition A.1 (Inner product). Given two functions f.g E
1-1, 13"H + R. their inner product is:
(f.g)
IE 2-1-1,1j-
--1--..1- [[x)g(=))]
2 Σ
f())(()).
In addition, we define the induced norm ||/ VT,)), and more generally, for >> 0.
f PI)
(10)
The inner product defines one kind of similarity between two functions and is invariant under different
basis. Specifically, we have the following Theorem. Definition A.2 (Plancherel's Theorem). Given two functions f.g 111,1)" R.
(f.g)
Σ fsğs.
SCIm
When setting f g. get the Parseval's identity: -E
distribution over a discrete domain S is often represented as a non-negative function f S R which is normalized in L1.ie. i..., Exes f(z) 1.
Definition A.3 (Fourier p-norm). For any Boolean function f {-1,1}" + R, we define the Fourier (or spectral) p-norm of f as
1/p
Ms A
Σ SCIM
lsss
(11)
Definition A.4 (Fourier p-distance). For any Boolean function f.g E f-1,1}" + R, we define the Fourier (or spectral) p-distance between f and g as
fff 1-glp -
Σ
Ifs - 9s
(12)
SCIml
16

---

Using Fourier p-norm, we could rephrase Parseval's identity as: |/ = [//
B
Proofs
Proof of Theorem 1.
Proof. Pick EF If A consistent with respect for every I E X, ((x) = f(x), we know = f & G, this is contradiction. Therefore, there exists X such that g(x) + f(x).
E 9 for any a X. If
Proof of Lemma 3.4.
Proof. Denote the complement space as Vg. We may expand f. f, on both bases and get:
|/ a|I² inf DEV
|lʃ 0/22
Σ (J -g,xs)++++
SEC
E (1xxs)
inf VEVe
E (J - u, v,,xs) [(:xs)
SEC
SEC
SEC
Σ (f g.xx)²
inf oEVe
E (f--v,xs) x,xs)
SEC
SEC
Σ (f g.xs)
SEC
where the last equality holds because we can the Fourier coefficients 6g fss for every C. which further gives (J Xs) 0.
Proof of Theorem 3.
Proof. Taking μ as the uniform distribution, then To(f.g) Ever 111" 1(00)/(l))
ssupp( Sf
2
2
Note Do .g) Esgil ((s))K)) -I supp(f-ğ) J. The conclusion follows from Proposition C.I.
Proof of Proposition 3.6.
Proof. From the definition of T2(f.g) and Dz(f.g). By Parseval's identity, 13(f.) 2- Cxe(-1,1p-((at)) g(z))² = Escm)(((S) - @(S))² =D((f.g)
Proof of Theorem 4.
Proof. From Proposition 3.6 (Parseval's identity), we have (notice that our functions gi are defined on X = {}" globally and then restricted to X; C X).
[9. - glzex, 12 = [9. luex - gloex I2 = llgilee - Flaex 2 l1glleex, floexx112
Let employ the triangle inequality for norms. Specifically, for each i 1,,...., N, we apply the triangle inequality as follows:
|| - galzex;11z + llaslee, - - 2 Iiflex - Fleex|12-
Summing this inequality over all i yields:
I|aex - 9iloxx + Σ 11gib glaxx,11 2 Σ |1bex - glzex,12.
17

---

By the definitions of Lotal and Doast we arrive at:
N
Iotal
Diotal
M1ee, - Ilzex;lle
This completes the proof.
B.1 Harmonica Algorithm
To present the theoretical guarantees of the Harmonica algorithm, introduce the following definition, which is slightly different from its original version in [27]. Definition B.1 (Approximately sparse function). We say a function f E (-1111) - R (c, C)- bounded, if E(f Exsec f(5)xs)² S e and Es [f()) S s.
Here f is (c, 8, -')bounded means it almost readable and has bounded & norm. Our algorithm is slightly different from the original algorithm proposed by [27], but similar theoretical guarantees still hold, as stated below.
Proof of Theorem 2. Our proof is similar to the one in the original paper [27], with changes in the readable notion, which is now more flexible than being low order. First, recall the classical Chebyshev inequality.
Theorem B.2 MMultidimensional Chebyshev inequality). Let X be an m dimensional random vector. with expected value μ ][ and covariance matrix V E [(X - w) =) If is positive definite matrix, for any real number 8 >0
P (V(X- 1x 1) 1)>0
Proof of Theorem 2. Let f be (e/4, s, C)--buunded function written in the orthonormal basis as Es f(S)xs. We can equivalently write f f h + g. where is supported on C that only includes coefficients of magnitude at least e/4s and the constant term of the polynomial expansion of f.
Since (,( = Es [s| S 8, we know h 4s2 / + sparse. The function g is thus the sum of the
remaining f(S)xs terms not included in h. Denote the set of bases that appear in C' but not in g as R, so we know the coefficient of f on the bases in R is at most e/4s.
Draw (to be chosen later) random labeled examples {22 ...................... (z",,"") and enumerate all N |C| basis functions Xs C as (x....., XN). Form matrix A such that Ai = X, (2*) and consider the problem of recovering 4s² /2 + sparse x given Ar + e = y where x is the vector of coefficients of h, the th entry of y equals y². and e; = g (z').
We will prove that with constant probability over the choice random examples, ||e||2 S Vem. Applying Theorem in [27] by setting = v/ and observing that 02.2/s+ (x)1 = (see definition in the theorem), will recover x' such that | x' < c&e for some constant C2. As such, for the function f E xxx; will have E |A- F1( &3 by Parseval's identity. Note, however, that we may rescale by a constant factor 1/ (2c²) obtain error e/2 and only incur an additional constant (multiplicative) factor in the sample complexity bound. By the definition of g, we have
||g/12
Σ S.xs
i(s)
E(() SER
(13)
where each f(S) for S E R of magnitude at most e/4s. By Fact 4 in [27] and Parseval's identity we
have ER (R) < e/4. Since f is (e/4, -o-coceentre we have Σ Exxsec f(S)² < e/4. Thus,
I is at e/ Therefore, by triangle inequality E. [[|s FIP?] < E | AIP] +E [[|=]|]]
It remains bound ||e||2. Note that since the examples chosen independently, the entries
18

---

e (z') are independent random variables. Since is linear combination of orthonormal monomials (not including the constant term), we have Be-D(o(=)) = 0. Here we can apply linearity of variance (the covariance of Xi and Xj is zero for all o j and calculate the variance
(I
Var (g(
Σ f(S)²
SiXEEC
SER
With the same calculation as Eqn. (13), we know Var (g (z')) is most e/2. Now consider the covariance matrix V of the vector e which equals E [ee "] (recall every entry of e has mean 0). Then V is diagonal matrix (covariance between two independent samples is zero), and every diagonal entry is at most e/2. Applying Theorem B.2 we have
PP (lell2
1
Setting d 22m, we conclude that P (Ile|12 VEm) 1.2 Hence with probability at least 1/2,
we have that ||e||2 I Vem. From Theorem 5 in [27], we may choose in = Ô (s² /s- log nd)). This completes the proof. Note that the probability 1/2 above can be boosted any constant probability with constant factor loss in sample complexity.
For the running time complexity, we refer [4] for optimizing linear regression with regularization. The running time is O((T' log + L/E)- (C)), where L is the smoothness of each summand in the objective. Since each Xs takes value in {-1, 1}, the smoothness is bounded by the number of entries in each summand, which is |C|. Therefore, the running time is bounded by O(T log + [CI/e)- JCI).
C Uncertainty Principle for Boolean functions
In the field of modern physics, the state of a particle on a given domain is represented by a complex function on that domain, and the probability of finding the particle in specific position æ on $ given by the square of the modulus of the function evaluated at æ. To ensure that the function is normalized, in the case where S is continuous, the funetion must satisfy SHER (f = 1.
The Fourier transform of the function, denoted by f. is also normalized in Le under a unitary transformation, and [x represents the probability density function of the distribution of the particle's momentum.
The Heisenberg uncertainty principle states that the product of the variances of a particle's position and momentum at least one, with an appropriate choice of units. This principle has physical significance and relates a function on IR to its Fourier transform.
In 1957, [29] proposed entropic form of the uncertainty principle, which was later proven nearly two decades later by Beckner [9]. The inequality states that H.[S] + H.lf) 2 1 In 2, where H, [ʃ] is the differential entropy of f, defined as SHeR [=x) In [fx)
When the domain is F3 (equivalently, 1-1,13">. similar inequality [25] holds with different constant. Let ʃ : F + C have a Fourier transform f F3 + C. Then,
f |I
H
2 n,
where H[}] - [ log, [/(r) and ||/||
v Vineryy S(x)2.
Now we present the discrete uncertainty principle for Z as the following. It can be proved using Theorem 23 in Dembo, Cover, and Thomas [19].
All the Fourier coefficients together are called the Fourier spectrum of f. We can define the following distance between two functions based their spectrums.
19

---

As there may be many candidates p for evaluating interpretation error and spectrum distance. In the following, we will investigate the most natural choice for p. As the Fourier expansion uniquely determined a Boolean function, we would like the distance between their expansion to have the same tendency as the interpretation error, thus the spectrum can encode enough information reflect the accuracy of the interpretation. We shall first discuss the most "strictt case, i.e. the Lo norm.
We shall introduce some notations for better understanding. Denote the support of an Boolean function f as supp(J) - {ar 1 (x) + 0}. The support of Fourier coefficients (Fourier spectrum), is defined by supp(f) - (S C [m] f(S) # 0}. The uncertainty principle for Boolean functions is stated as follows.
Proposition C.1 (Uncertainty Principle for Boolean functions [25, 43]). For every nonzero functiin f: 1-, +.
supp(/)) (hup(/))-|supp((1 2".
D Low-degree Algorithm
The low-degree algorithm is based on the concentration inequality, and estimates the coefficient of each axis individually.
Algorithm 4: Low-degree
1. Given uniformly randomly sampled 21, Ir, evaluate them on f: (f(x1), (ioii,,,........ [(xr))
2. For any Xs E C, let ÿs Σ. ((x)xs(a,)
3. Output the polynomial g(z) Σ Sxeec (sxs(I).
Theorem D.1 ([36)). Given any e, 8 > assuming that function f is bounded by B, when T 2
28 log 5
2| we have
Pr (Vx E C, s.t.,, fsl S 21121
Theorem D.1 was proved using the Hoeffding bound, and we included the proof here for completeness.
Proof. Since we are given T samples to estimate f(S) for every S, we can directly apply the Hoeffding bound (notice that the function is bounded by B):
2T
Te²
Pr (las- - f(S)) |CI s 2exp
eexp
4B²
2B²
Notice that T 2 proved.
2Ba 22
log
2|C| 8
we know the right hand size is bounded by [c] so Theorem D.1 is
Remarks. The theoretical guarantee of Harmonica assumes the target function f is approximately sparse in the Fourier space, which means most of the energy of the function (Fourier coefficients) is concentrated in the bases in C. This is not strong assumption, because if f not approximately sparse, it means f has energy in many different bases, or more specifically, the bases with higher orders. In other words, has large variance and is difficult to interpret. In this case, no existing algorithms will be able to give consistent and meaningful interpretations.
Likewise, although the Low-degree algorithm does not assume sparsity for it cannot learn all possible functions accurately as well. There are 2n different bases, and if we want to learn the coefficients for all of them, the cumulative error for g is at the order of ?2(2")), which is exponentially large. This is not surprising due to the no free lunch theorem in the generalization theory, as we do not expect to be able to learn "any functions" without exponentially many samples.
E Discussion on the Existing Algorithms
In this section, we compare our approaches with the existing techniques from different perspectives of interpretation error (efficiency), truthfulness, and consistency.
20

---

LIME [47]. Given an input z, Lime samples the neighborhood points based on sampling distribu- tion II and optimizes the following program:
min L( [T,)) + ((gg). gEg
where is the loss function describing the distance between and g on the sampled data points, G is the set of readable functions (e.g. the set of linear functions), (2() is a function that characterizes the complexity
g. In other words, LIME tries to minimize the fitting error and simultaneously minimizes the complexity of g (which is usually the sparsity of the linear function). By minimizing L, LIME also works towards minimizing the interpretation error, but their approach is purely heuristic, without any theoretical guarantees. Although their readable function set can easily generalize to the set with higher order terms, the sampling distribution Il is not uniform, so it difficult to incorporate the orthonormal basis into their framework. In other words, the model they compute is not truthful.
Attribution methods. As we discussed in the introduction, attribution methods mainly focus on individual inputs, instead of the neighboring points. Therefore, it is difficult for the attribution methods to achieve low inconsistency, especially for first-order methods like SHAP [38] and IG [60].
Consider SHAP [38] as a motivating example, illustrated in Figure 1 for the task of sentiment analysis of movie reviews. In this example, the interpretations of two slightly different sentences are inconsistent. This inconsistency arises not only because the weights of each word differ significantly, but also because after removing the word "very" with weight of 15.0%, the network's output only drops by 6.6%. In other words, the interpretation does not explain the network's 's behavior even in a small neighborhood of the input.
For higher-order attribution methods, consistency can potentially be improved due to their enhanced representation power. The classical Shapley interaction index has the problem of not precisely fitting the underlying function, as observed by [61], who proposed Shapley Taylor interaction index [61] with better empirical performance. Shapley Taylor interaction index satisfies the generalized efficiency axiom, which says for all 111, + R.
Σ SCIM
I=(f)= = f(m)) - f(0)-
We should remark that both the Shapley interaction index and Shapley Taylor interaction index were not originally designed for consistent interpretations, so they did not specify how to generalize the interpretation for the neighboring points. To this end, we make a global extension to the Shapley value based interpretation, that is, using Shapley interaction indices Shapley Taylor interaction indices as the coefficients of corresponding terms of the polynomial surrogate function.
g (11, F2, .. ,T)) = f(0) +
Σ ICE
I(f.S).
However, these higher-order Shapley value based methods all focus on the original Shapley value framework, so their interpretations are not truthful. i.c., not getting the exact coefficient of f even the "simple bases". Moreover, as we will show in our experiments, higher-order methods still incur high interpretation errors compared with our methods.
When applying Shapley value techniques for visual search, [26] proposed an interesting and novel sampling + Lasso regression algorithm for efficiently computing higher order Shapley Taylor index in their experiments. However, their methods are based on sampling probability distribution generated from permutation numbers, which is far from the uniform distribution. Additionally, their algorithm based on the Shapley Taylor index, so their method is not truthful as well.
Discussion on universal consistency. When discussing consistency, there are two distinct settings: "global consisteney" and "universal consistency." This paper mainly focuses on global consistency (Definition 2.2), where the interpretation pertains only to input features and not to others. This scenario falls under the category of "removal-based explanations," and most existing interpretation methods belong to this category (26 of them were discussed in [18]). In contrast, universal consistency implies that the interpretation may depend on features different from the input features. An example of interpreting the sentence "I am happy" could be, "TTis sentence does not include [very], so this person is not extremely happy." Universal consistency more challenging than global consistency, and we hypothesize that more powerful machinery, such as foundation models, is needed.
21

---

Emergence of self-explainability in foundation models. In the groundbreaking work Sparks of AGI [11]. the authors conducted comprehensive experiments on GPT-4's self-explainabilityy Chain-of-thoughh reasoning [73, 71, 76, 79] can be considered an interpretation provided by the model itself, although current I.L.s are not always to be consistent or truthful. In the long run, however, this approach may represent the ultimate path to explainable AI In the computer vision area, DINO [12, 44] emerges the ability self-explanation provided by the attention map inside the model, which can be directly utilized as heatmap visualization or even applied to segmentation tasks.
Proposition E.1 (Omniscient LLM is the way). An (infinitely) large (multi-modal) language model pre- pre-trained using (infinitely) large corpus, with zero pre-training loss and generalization loss, which has been perfectly aligned to be truthful, is interpretable, efficient, and consistent.
Proof. To prove the proposition, let examine each attribute (interpretable, efficient, and consistent) in the context of an (infinitely) large (multi-modal) language model (LLM)):
1. Interpretable: By assumption, the LLM has zero pre-traine vre-training loss and generalization loss, implying perfect knowledge representation. Furthermore, is perfectly aligned to be truthful, satisfying the criteria for interpretability per Definition 2.4.
2. Efficient: The efficiency condition g(x) = fxx) is trivially satisfied because f -g by the condition of self-explainability. Thus, the LLM efficient as per Definition 2.3.
3. Consistent: Given that the I.L.'s responses are generated based on a perfect understanding and alignment, it will generate the same function A(f, x) for every X, thereby being consistent as per Definition 2.2.
It's crucial to note that self-explainability does not violate the Impossible Trinity (Theorem 1). When f 9. the LLM serves as its own interpreter, inherently satisfying all three criteria. Alternatiell, f " 9. where g has an even larger concept class than f. the interpretability criteria are also met, albeit this is not practical scenario for standard interpretation algorithms.
Therefore, (infinitely) large LLM, pre-trained with (infinitely) large corpus and aligned perfectly to be truthful, satisfies all the conditions to be interpretable, efficient, and consistent.
F Test with Low order Polynomial Functions
F.1
First order polynomial function
To investigate the performance of different interpretation methods, let us take closer look at a 1st order polynomial function:
1 2d1
1 22
Si (21,
+ 23
3
For this simple function, we can manually compute the outcome of each algorithm, as illustrated in Table 2. If the algorithm's 's output is correct, i.e., equal to the output of fI, we write check mark. Otherwise, we write down the actual output of the given interpretation algorithm.
As we can see, all methods are consistent and efficient for all cases. In fact, all variants of Shapley indices degraded to 1st order Shapley values.
Algorithom
(11-1,-1)
(-1,-1.4) (-1.-1,-1)
(-1,+1++1)
(+1--1,1)
(-1-1,+1) (+1+1,-1)
(+1++1+1)
Ground Truth
-417
-0,83
-1083
-0.800
+0383
-1003
-0083
+0.417
LIME
SHAP
Shapley Interaction Index (1st order)
Shapley Teclor Index (1st order)
Faith-Shap (1st order)
Lou-degree (Ist orders
Harmonica order)
Table 2: Interpretations by LIME, SHAP, Shapley Interaction Index, Shapley Taylor Index, Faith- Shap, Low-degree, and Harmonica the 1st order polynomial function fi.
22

---

F.2 Second order polynomial function
In addition, let take closer look at a 2nd order polynomial function:
1 fa (21, 2"1
1 5 2112
22
4 4=3
2113 -
For this simple function, we can manually compute the outcome of each algorithm, as illustrated in Table 3. If the algorithm's 's output is correct, i.c., equal to the output of f2. we write a check mark. Otherwise, we write down the actual output of the given interpretation algorithm.
As we can see, 2nd order interpretation algorithms, including Shapley Taylor index, Faithful Shapley, Low-degree, and Harmonica are consistent and efficient for all cases. Other methods can only fit few ipputs, the 2nd order Shapley interaction index misses all the cases because is not efficient, and LIME misses all the cases because f2 is not linear function.
Algocithuss
(-1-11-1) 1,-1)
(-1, 1,44]
(-1.+1,11)
(-1.-1.43
(+). -1,1)
(+1,-1,+1)
(+1,+1.-1
(+1, +1,+
Ground Truth
-0.00
-0.14
-0.774
-0.65
+0.474
+1.583
-1.07
+0.240
LIME
-0.17
-0083
-1.08
-0.885
+0.583
+1.085
1088
+0.17
SHAP
-0.200
-0233
11220
-0725
+0.726
+12250
-0283
Shapley Interaction Index (2nd onder)
-0.32
-0.085
-0781
+0.01
+1.005
-0.05
+0.152
Shapley Taylor Tndex order)
Faith-SSapp (2nd order)
Low-degree (3ad order)
Uarmmoniaa (2nd order)
Table 3: Interpretations by LIME, SHAP, Shapley Interaction Index, Shapley Taylor Index, Faith- Shap, Low-degree, and Harmonica on the 2nd order polynomial function f2.
F33
Third order polynomial function
Finally, we investigate the following 3rd order polynomial and present the result in Table 4.
1
1
1
1
1
1
fa T2, 23)
2 11
3 22
I3
21
+
2153
7 2223
8 2132T3.
5
6
As we can see, Faith-Shar Shap. Low- Low-degree, and Harmonica are consistent and efficient for all cases. Other methods can only fit few inputs, the 3rd order Shapley interaction index misses all the cases because it is not efficient, and LIME misses all the cases because fa is not a linear function.
Algerithms
-11--1-1
(-1--++1) (-1++,-1)
(-1,+1-1))
[+1, -1,1)
(-1,
-1,+)
(+1,-1-11
(+) ++++)
Ground Troth
-0.18
-0.15
+0.449
-18118
40.500
+1.408
-0.482
+0.365
LIME
-0.17
40.085
-1088
-1.585
40.583
+1.081
-0085
+0.17
SHAP
-0.65
+0.242
-1229
-0.85
+0.855
+1.292
-0.242
Interaction Index (3rd onder)
-0485
224
-0.43
-0.856
+0.724
+1.390
-0.10
+0.006
Shapley Tayler Index (3d onder)
0.008
00.900
+0.751
+1.025
-0642
Faith-Shap (3rd order)
Low-degree (3ed order)
Harmonica (3dd order)
Table 4:
Interpretations by LIME, SHAP, Shapley Interaction Index, Shapley Taylor Index, Faith- Shap, Low-degree, and Harmonica on the 3rd order polynomial function f3-
Faith-SHAP has an intricate representation theorem, assigning coefficients to different terms under the Möbius transform. Since the basis induced by the Möbius transform is not orthonormal, it is unclear to us whether Faith-SHAP can theoretically compute the accurate coefficients for higher- order functions. However, the running time of Faith-SHAP has an exponential dependency n, so empirically weighted sampling on subsets of features is needed [62]. This might be the main reason why our algorithms outperform Faith-SHAP experiments on real-world datasets.
G More on Experiment Details
In this section, we will first describe the detailed experimental settings. For the two language tasks, i.e., SST-2 and IMDb, we use the same CNN neural network. The model has a test accuracy of 85.6%. For the readability of results, treat sentences as units instead of words masking several
23

---

words in sentence may render the entire paragraph difficult to understand and even meaningless while masking a critical sentence has meaningful semantic effects. Therefore, the radius is defined as the maximum number of masked sentences for IMDb. The word embedding layer is pre-trained by GloVe [46] and the maximum word number is set to 25, 000. Besides the embedding layer, the network consists of several convolutional kernels with different kernel sizes (3, 4, and 5). After that, we use several fully connected layers, non-linear layers, and pooling layers to process the features. A Sigmoid function is attached to the tail of the network to ensure that the output can be seen probability distribution. Our networks are trained with an Adam [32] optimizer with a learning rate of 1e-2 for 5 epochs. For the vision task, choose the official ResNet [28] architecture, which is available on Py PyTorc and we do not discuss the architecture details here. All the experiments are run on server with 4 Nvidia 2080 Ti GPUs. A running time comparison can be found in Table 5, More information about the run-time Python environment and implementation details can be found in our code.
Table 5: Running time of different algorithms on SST2 dataset. The main characteristics affecting the running speed are listed in the table.
Main Characteristics Affecting Speed
Running
Algorithm
Time (s)
Harmonica-2nd Harmonica-3rd
Parallel perturbation, sample=2000
225
Parallel perturbation, sample=2000
616
LIME
1499
Seq. perturbation, Sample=2000,
Exp. cosine sim.
Integrated Gradients SHAP
Gradient step=500 Capuem..ttrKeemme/SSapp
82
1235
Seq. perturbation,
Sample=2000
Integrated Hessians Shapley Taylor Index Faith-Shap
Gradient step=50
3550
Parallel random perturbations
651
Parallel random perturbations
538
The accurate representation of the high non-linearity of deep neural networks (DNNs) can be quite complex, often leading to computationally expensive or practically infeasible interpretability methods. To strike a balance between computational efficiency and faithful representation, we employ higher- order polynomial approximations capture the non-linear aspects of the target DNNs. Specifically, we leverage Fourier basis (or polynomial basis) to represent Boolean functions over feature subsets, thus providing a compact and computationally efficient way to approximate DNNs. This is particularly useful for removal- based explanations, which inherently deal with Boolean functions representing the presence or absence of features.
is crucial to point out that our choice of using higher-order polynomials is not arbitrary but is guided by the principle of "truthfulnness. We introduce metric called the "truthful gap," mathematically defined as (J, g) (as per Equation 1), to quantify how well our polynomial approximations capture the information in a specific subspace V of the original function f. This notion of truthfulness serves as rigorous measure to validate the efficacy of our nigher-order polynomial approximations.
Our empirical results, particularly those outlined in Section 5, indicate that higher-order polynomials, specifically of orders 2 and 3, yield a favorable trade-off. They offer a substantial reduction in inter- pretation error and low truthful gap compared to other techniques, substantiating the reasonableness and effectiveness of our approach.
Notice that our algorithm is post-hoc -agostc interpretation algorithm, we only need to use the original neural network f to infer on given input as an oracle. This means that one can easily change the network architecture without any additional changes.
H More Experimental Results
In this section, we present ablation studies that examine the impact of various factors such as image segmentation format, neural network architecture, and choice of baselines. Our results demonstrate the robustness and efficacy of our approach in different experimental settings.
24

---

H.1 Image Segmentation Format
We employ the SLIC algorithm to generate segmentation superpixels the ImageNet dataset. We initially divide each 224 x 224 image into 16 superpixels for a balance between human readability and computational efficiency. The results, displayed Table 6 and Figure 4, validate the effectiveness of our approach. Further experiments with 10 superpixels are reported in Table 7, confirming the robustness of our method.
H.2 Neural Network Architectures
We also conduct experiments using diverse neural network architectures such as ResNet- 18 and VGGI6. Tables 8 and 9 respectively present the interpretation errors on ImageNet for these architec- tures.
H.3 Choice of Baselines
The choice of baseline is critical for removal-based interpretation methods. We investigate the interpretation emrors when using the average pixel value and blurred image as baselines. The results shown Tables 10 and 11.
Table 6: Interpretation error MS-COCO Bold indicates the best performance, and underline indicates the second best.
Radius
2
4
8
16
Harmonica-2nd
0.0291
0.0332
0.0363
0.0367
0.0367
Harmonica-3rd
0.0183
0.0218
0.0241
0.0244
0.0244
LIME
0.2264
0.2451
0.2478
0.2479
0.2479
SHAP
0.1952
0.2036
0.2041
0.2042
0.2042
IG
0.3473
0,3515
0.3464
0,3462
0,3438
IH
1.3717
1.5047
1.5141
1.5141
1.5141
Shapley Taylor
0.3554
0.3313
0.3269
0.3267
0.3267
Faith-Shap
0.2428
0.2397
0.2349
0.2347
0.2347
Table 7: Interpretation error ImageNet with the number of superpixels set 10.
Radius
8
16
Harmonica-2nd
0.0970
0.1054
0.1221
0.1416
0.1420
Harmonica-3rd
0.0705
0.0825
0.0997
0.1179
0.1183
LIME
0.1995
0.2121
0.2570
0.3052
0,3051
SHAP
0.1449
0.2077
0.2743
0.3064
0.3063
IG
0.2615
0.3567
0.4423
0.4628
0.4626
1.6707
2.2977
2.9443
3.1871
3.1877
Shapley Taylor
0.0982
0.1417
0.1761
0.1815
0.1814
Shith-Shap
0.0970
0.1250
0.1587
0.1811
0.1810
I Detailed Results on Interpretation Error
In this section, we provide interpretation error results under other norms (Figure 6, 7, and 8) and the corresponding numerical results (Table 12, 13 and 14).
25

---

Table 8: Interpretation error on ImageNet using ResNet18 (ACC@ 1-690000-69999900
Radius
8
16
Harmonica-2nd
0.1468
0.1433
0.1353
0.1357
0.1414
Harmonica-3rd
0.1247
0.1261
0.1231
0.1272
0.1319
LIME
0.2278
0.2209
0.2150
0.2382
0.2578
SHAP
0,1034
0.1436
0.1963
0.2323
0.2375
IG
0.1937
0.2613
0.3466
0.4028
0,4039
IH
0.6422
0.8686
1.1591
1.3939
1.4254
Shapley Taylor
0.1292
0.1530
0.1716
0.1744
0.1775
Faith-Shap
0.1239
0.1426
0.1532
0.1607
0.1693
Table 9: Interpretation error ImageNet using VGGI6 (ACC @ 1=71.592%).
Radius
4
8
16
Harmonica-2nd
0.1468
0.1404
0.1298
0.1303
0.1368
Harmonica-3rd
0.1290
0.1267
0.1204
0.1225
0.1289
LIME
0.2376
0,2280
0.2180
0.2448
0,2664
SHAP
0,1042
0.1461
0.2012
0.2407
0.2477
IG
0.1708
0.2331
0.3123
0.3659
0.3694
IH
0.5988
0.8132
1.1010
1.3663
1.4149
Shapley Taylor
0.1155
0.1435
0.1677
0.1720
0.1728
Faith-Shap
0.1085
0.1306
0.1456
0.1548
0,1621
Table 10: Interpretation error ImageNet using the average pixel value as the baseline.
Radius
Method
8
16
Harmonica-2nd
0.1341
0.1279
0.1201
0.1243
0.1304
Harmonica-3rd
0.1012
0.1025
0.1022
0.1095
0.1156
LIME
0.2205
0.2142
0.2095
0.2327
0.2520
SHAP
0.1022
0.1410
0.1934
0.2307
0.2357
IG
0.1824
0.2468
0.3280
0.3822
0.3835
IH
0.6292
0.8497
1.1356
1.3752
1,4115
Shapley Taylor Faith- Shap
0.1293
0.1665
0.2157
0.2550
0.2534
0.1219
0.1530
0.1918
0,2288
0,2302
Table 11: Interpretation error on ImageNet using the blurred image the baseline.
Radius
Method
8
16
Harmonica-2nd
0.0207
0.0209
0.0210
0.0218
0.0225
Harmonica-3rd
0.0200
0.0203
0.0204
0.0213
0.0220
LIME
0.0260
0.0276
0.0310
0.0372
0.0394
SHAP
0.0184
0.0258
0.0360
0.0460
0.0477
IG
0.0215
0.0299
0.0415
0.0524
0,0541
IH
0,0268
0.0373
0.0525
0.0684
0.0718
Shapley Taylor
0.0350
0.0370
0.0385
0.0372
0.0360
Faith-Shap
0.0343
0.0358
0.0368
0.0358
0.0350
26

---

Radius
norm
nomn
norm
Radius
norm
L norm
L" norm
Radios
L norm
L' norm
L norm
1
0.0536
0.0460
0.1154
0.0434
0.0363
0.0995
1
0.0981
0.0870
0.3572
0.0576
0.0463
0.1219
2
0.0484
0.0376
0.1046
2
0.1010
0.0861
0.3458
0.0639
0.0483
0.1350
4
0.0561
0.0405
0.1157
0.1043
0.0863
0.3421
8
0.0768
0.0549
0,1696
8
0.0700
0.0474
0,1456
8
0.1135
0.0919
0.3659
0.0945
0.0651
0.2173
16
0.0876
0.0575
0.1900
16
0.1285
0.3015
0.4034
32
0.0990
0.0677
0.2275
32
0.0921
0.0600
0,2003
32
0.1323
0,1038
0.4111
00
0.0991
0.0677
0.2279
00
0.0922
0.0601
0.2005
90
0.1322
0.1037
0.4112
Harmonica
Harmonica'
LIME
Radius
L norm
L' norm
L borm
Radius
L? norm
L' Dorm
L" norm
Radius
L norm
L norm
L norm
0.0792
0.0568
0.1819
0.1133
0.0681
0.2010
0.0865
0.0477
0.1215
0.1089
0.0836
0.3167
2
0.1551
0.1055
0,3361
2
0.1232
0.0756
0.2118
0.1470
0.1186
0.4847
4
0.208
0.1563
0,5066
4
0.1753
0.1183
0.3406
0.1865
0.1554
0.6252
0.2595
0.2075
0.6476
8
0.2343
0.1691
0.4859
16
0.2106
0.1783
0.6891
16
0.2852
0.2336
0,7058
16
0.2678
0.1994
0.5724
0.2137
0.1814
0.6958
32
0.2872
0.2357
0.7099
32
0.2709
0.2028
0.5823
0.2137
0,1814
0.6961
00
0,2874
0.2359
0.7105
0.2711
0.2029
0.5823
SHAP
Integrated Gradients
Integrated Hessians
Radius
L
L
L
Radius
L
L!
1 norm
0.0623
0.0472
0.1090
0,0602
0.0451
0.1034
0.0853
0.0649
2
0.0813
0.1144
0.0874
0.3069
4
0,1091
0,0824
0.2794
0.1426
0.1081
0,3909
0.1387
0,1042
0,1612
0,1217
0.4404
16
0.1586
0.1190
0.4271
0.1642
0.1241
0.4486
32
0.1616
0.1213
0.4356
0,1642
0.1240
0.4489
0.1616
0.1213
0.4357
Shapley Taylor Index?
Faith-Shap"
Table 12: The interpretation error of Harmonica and other baseline algorithms evaluated on the SST-2 dataset for different neighborhoods with radius ranging from to co under L L and L norms.
Radius
norm
norm
norm
Radius
nomm
L norm
1 norm
Radius
L norm
L norm
norm
0.0225
0.0193
0.0041
0.0175
0.0149
0.0027
1
0.0624
0.0525
0.1
0.0234
0.0193
0.0036
0.0193
0.0157
0.0022
2
0.0671
0.0546
0.1388
0.0300
0.0228
0.0141
4
0.0264
0.0195
0.0098
0.0740
0.0583
0.1606
8
0.0442
0.0298
0.0434
8
0.0407
0.0265
0.0367
8
0,084
0.0640
0.1903
0.0506
0.0330
0.0574
16
0.0472
0.0296
0.0506
16
0.0885
0.0664
0.2017
32
0.0515
0.0334
0.0596
32
0.0481
0.0301
0.0528
32
0.0892
0.0667
0.2033
0.0515
0.0334
0.0597
00
0.0481
0.0301
0.0529
00
0.0892
0.0667
Harmonica
Harmonica
LIME
Radius
_ norm
Z! norm
1 porm
Radius
L2 norm
L norm
Z norm
Radius
L porm
Z! norm
I norm
0.0849
0.0650
0.2266
0.1228
0.0810
0.2702
1
0.1178
0.0635
0.1929
0.1123
0,0903
0.3589
2
0,1576
0.1169
0.4102
2
0.1567
0.0997
0.3125
0.1406
0.1162
0,4891
4
0.1882
0.1494
0.5333
4
0.1969
0.1415
0.4501
0.1598
0,1341
0.5610
8
0,2031
0.1657
0.5885
8
0.2227
0.1702
0.5423
16
D.1662
0.1402
0.5817
16
0.2067
0.1697
0.6004
16
0.2308
0.1795
0.5702
0.1671
0.1411
0.5842
32
0.2071
0.1702
0.6014
32
0.2319
0,1807
0.5739
DC
0.1671
0.1411
0.5843
0.2071
0.1702
0.6015
0C
0.2319
0.1807
0.5738
SHAP
Integrated Gradients
Integrated Hessians
Radius
1 nomm
f.9
Radius
1.2 norm
1.A norm
1."
0.0444
0.0365
0.0554
1
0.0395
0.0313
0.0337
0.0590
0.0470
0.0999
0.0469
0.0466
0.0684
0.0538
0.1339
4
0.0547
0.0440
0.0657
0.0698
0.0542
16
0.0719
0.0558
0.1287
16
0.0684
0.0543
0.0851
0.0741
0.0575
32
0.0743
0.0577
0.1294
0.0744
0.0590
0.0859
Shapley Taylor Index
Faith- Faith-Shap"
Table 13: The interpretation error of Harmonica and other baseline algorithms evaluated on the IMDb dataset for different neighborhoods with radius ranging from to co under L?, I and I norms.
27

---

x10-1
laptop
Harmonica
LIME
IG
SHAP
(a) Laptop
x10-1
x10-1
x10-1
x10
flatworm
Harmonica
LIME
IG
SHAP
(b) Flatworm
Figure 4: Illustrative examples for applying our method to vision tasks.
0.6
Harmonica-
Harmonica
LIME
LIME
0.7
Probability erfor
IG
0.6
0.5
0.1
Number of inserted top important words
Number of deleted bottom important words
(a) Insertion
(b) Deletion
Figure 5: Insertion and deletion results SST2.
J Detailed Results on Harmonica-local
J.1 Additional Experiments
We further explore Harmonica's performance when limited to a local space instead of the whole space. It is worth noting that Lp is a regularization loss for Harmonica, ensuring the sparseness of each interpretation model 9: Additionally, L. is regularization loss penalizing the difference between interpretation models. The value of balance coefficients depends on the application scenario and can be determined by the end user.
Famoria ucert
CITP
10:
ooen
Famaniaa 2Png coler
Bal
Baa
10-1
20
Sobspace radins
Subapace nadl
Sulspace radiass
(a) L
(b) L
(c) L
Figure 6: Visualization of interpretation error I,, No (f. g) evaluated on SST-2 dataset.
28

---

Famercc peter
20-1
30-1
Ria tp
Interprrttatinnn
Rammeree na Dhi cnlert
Imber
10-1
and
16
Subspace redius
Subapace radias
Subspace redluss
(a) 1 norm
(b) L, norm
(c) 1 norm
Figure 7: Visualization of interpretation error up No (f. g) evaluated on IMDb dataset.
Lid
iiegresd and
Intepretation
Interpetttton
Hamanaa de sing Veter
Srap
12%
Subupate radios
Subspace radia
Subopace radius
(a) L norm
(b) L' norm
(c) L
Figure 8: Visualization of interpretation error N, (S,9) evaluated on ImageNet dataset.
Radius
norm
norm
Radius
norm
1.
Radius
L norm
L' norm
E norm
0.1290
0,1108
0.4248
1
0,1048
0.0880
0.3202
1
0.2422
0.2208
0.7274
0.1308
0.1073
0.4116
2
0.1108
0.0887
0.3260
2
0.2347
0.2036
0.6976
0.1373
0.1094
0.4332
4
0.1220
0.0955
0.3723
0.2346
0.1918
0.6540
8
0.1584
0.1264
0.5156
8
0.1443
0.1139
0.4698
8
0.2897
0.2304
0.6893
0.1693
0.1342
0.5405
0.1566
0.1230
0.5030
0c
Harmonica
Harmonica
LIME
Radius
norm
norm
norm
Radius
norm
1.2 norm
1. norm
Radius
1.2 norm
1.! norm
1 norm
0.1197
0.0867
0.2892
0.2322
0.1650
1.3681
0,9504
0.8443
0.1658
0.1261
0.4566
2
0,3141
0.2375
0.6406
2
1.3603
1.4006
0.9025
0.2306
0.1862
0.6483
4
0.4200
0.3346
0.7722
2.5168
2.0427
0.9394
0.2943
0,2409
0,7318
8
0.5010
0.4094
0,8300
8
3.1095
2,6844
0.9543
00
0.3115
0.2523
0.7362
00
0.5113
0.4177
0,8340
00
3.2139
2.8140
0.9562
SHAP
Integrated Gradients
Integrated Hessians
Radius
L borm
L norm
f norm
Radius
1 norm
1!! norm
1." norm
0.1337
0.1039
0.3939
0.1238
0.0948
0.3443
0.1681
0.1309
0.4906
2
0.1499
0.1161
0.4338
0.2028
0.1600
0.5830
4
0.1718
0.155
0.5126
0.2226
0.1771
0.6365
8
0.1960
0.1554
0.5872
DC
0.2274
0.1804
0.6418
00
0.2099
0614
0.6071
Shapley Taylor Index
Paith-Shap"
Table 14: The interpretation of Harmonica and other baseline algorithms evaluated the ImageNet dataset for different neighborhoods with a radius ranging from to ac under 1/2 L and 7 norms.
29

---

Figure 9, 10 and 11 compares Harmonica- -occll and Harmonica algorithms on SST-2, IMDb and ImageNet, respectively. Here we set the radius of N₁ be 4. The results reveal that Harmonica-local indeed performs better within the local region but fails to cover far region.
Hamosen THe over
Imtere Interpeetaae orror
Inserponaaioon
20.3
20-1
Subspace rodius
Subspace radias
Subspace radius
(a) L norm
(b) L' norm
(c) L norm
Figure 9: Visualization of interpretation error p. (f.g) evaluated on SST-2 dataset of algorithm Hanmonica and Harmonica-loca
dlivess
Han
Intorored coor
Intepratalann
20-1
20.2
10-1
Subapace
radius
Subspace radius
Subapace radius
(a) L norm
(b) L norm
(c) L norm
Figure 10: Visualization of interpretation error As (f evaluated IMDb dataset of algorithm Harmonica and Harmonica-local.
10"
Iterpretation wnD
Intororcattion CTTT
30
Subspace rodius
Subspace radius
Subopace radius
(a) L norm
(b) L' norm
(c) L norm
Figure 11: Visualization of interpretation error N, (J.9) evaluated on ImageNet of algorithm Harmonica and Harmonica-local.
K Detailed Results on Truthful Gap
Estimating truthful gap For convenience, we define the set of bases Cd up to degree d as Cdd Xs|S C [n], [S] < d. We evaluate the truthful gap on the set of bases C3. Ca and Cº. By definition in Eqn. (3), we have (f.g) Exsec (f g.xs)²
E. - [1(()) - g(x)) Exsec xx(x)))()))
Then we perform sampling-based estimation of the truthful gap. Worth mentioning that since the size of set Odd satisfies |Cd|| Ei (?) and the max number of words, sentences, superpixels
30

---

n' 50, Exsec Xs(x), as the summation function of orthonormal basis, is easy to compute on every sample I {-1,1)" (for n very large, will perform another sampling step this function).
Table shows the C truthful gap evaluated on different datasets. We can see that Harmonica outperforms all the other baseline algorithms. Figure 12 shows the truthful gap evaluated on the SST-2 dataset. We can see that Harmonica achieves the best performance for C² and C For the simple linear case C', Harmonica is almost as good as LIME. Figure 13 shows the truthful gap evaluated on the IMDb dataset under the same settings the SST-2 dataset. Figure 14 shows the truthful gap evaluated on the ImageNet dataset. We can see that Harmonica outperforms all the other baselines consistently.
Ge
wede Cled
Fet (Cdl gilf sotee
Marriatto thn weldged
for
(a) bases C
(b) bases C
(c) bases
C
Figure 12: Visualization of truthful gap Tc(f,)) evaluated on SST-2 dataset.
14.
Truntta
Trushlu
costrslt
Howvy Festr
Ideesttd fatioons
Shatwdaet intingee
itbertted dherried
paree Theler
(a) bases O
(b) bases C2
(c) bases O
Figure 13: Visualization of truthful gap (o(f.g evaluated on IMDb dataset.
16-
10"4
TTuebbl sap
12
Trutiu
10-2
Trutruu
30
10-
Got moaes
Loe
that Sone
toor
Ind fare
Cer Last
2014
(a) bases Ca
(b) bases C2
(c) bases C
Figure 14: Visualization of truthful gap (c(f.g) evaluated on ImageNet dataset.
31

---

L Detailed Results on Harmonica-anchor
L.1 Harmonica-ancee
Figure 15, 16, and 17 show the interpretation enror results evaluated on three datasets. All Harmonica- anchor algorithms further reduce the interpretation error compared to Harmonica. As we increase the number of anchors, the interpretation error slightly reduces, which is consistent with our intuition. Table 15, 16, and 17 show the numerical results.
samonca 250
raimann (n oder
samran sichal
20
25
Subopare redius
Subspece
Subspace redlis
(a) 1.2 norm
(b) T norm
(c) T,0 norm
Figure 15: Visualization of interpretation error Ap (f.g) evaluated on SST-2 of Harmonica-
anchor (2nd order) with different anchor number k.
Invegretaaao
10
Subapace radius
Subspace radius
Subapace radius
(a) L norm
(b) L' norm
(c) L norm
Figure 16: Visualization of interpretation error I, (J.9) evaluated on IMDb of Harmonica- anchor (2nd order) with different anchor number A:
Insegretaiiinn
10-4
Interprentee
da 2nd
Subapace radius
Subspace radius
Subopace rodius
(a) L norm
(b) L' norm
(c) L norm
Figure 17: Visualization of interpretation error Tp, (f evaluated on ImageNet of Harmonica- anchor (2nd order) with different anchor number k:
L.2 Harmonicc--ncoo--oostaannd
Here we provide the interpretation error of Jammonic--nchoo-ccnstraaaa evaluated on SST-2 dataset in Figure 18. As we increase the constraint coefficient A2, the interpretation error increases, but still smaller than that of Harmonica.
32

---

Radius
1.² norm
1!' norm
1." norm
Radius
1 norm
L, norm
J norm
0,0217
0.0178
0,0137
0.0201
0.0164
0.0116
2
0.0257
0.0196
0.0186
0.0239
0.0181
0.0157
(L0166
0.0258
0.0417
0.0343
0.0242
0.0381
0.0559
0,0396
0.1007
0.0544
0.0381
0.0963
16
0.0723
0.0518
0.1579
16
0.0715
0.0511
0.1565
32
0.0753
0.0541
0.1688
32
0.0749
0.0536
0.1678
00
0.0753
0.0541
0616
00
0.0748
0.0535
0.1677
Harmonica-anchor (k 3)
ceeemonica-anchon (k 5)
Radius
L' norm
Z' norm
L norm
Radius
L norm
L' norm
D norm
0.0195
0.0159
0.0114
0.0193
0.0158
0.0104
2
0.0231
0.0175
0.0144
2
0.0228
0.0172
0.0139
0.0330
0.0232
0.0356
0.0324
0.0227
0.0345
8
0.0535
0.0374
0.0948
8
0.0533
0.0371
0.0940
0.0719
0.0514
0.1598
16
0.0726
0.1631
32
0.0753
0.0540
0.1714
32
0.0762
0.0546
0.1750
00
0.0753
0.0540
0.1717
00
0.0761
0.0545
0.1746
Harmonica-anchhe (k 7)
carmonica-anchor (k-
9)
Table 15: The interpretation enror of Harmonica-anchan algorithms evaluated on the SST-2 dataset for different & with radius ranging from to co under I.2, I,² and 7,0 norms.
Radius 1.2 norm
1. norm
1. norm
Radius
12 norm
1.¹ norm
J norm
0.0078
0.0062
0.0013
0.0062
0.0049
0.0011
0,0088
0.0067
0,0005
0.0070
0.0051
0.0004
0.0124
0.0088
0.0015
0.0100
0.0068
0.0010
0,0199
0.0135
0,0074
0.0169
0.0110
0.0053
16
0.0231
0.0154
0.01
16
0.0200
0.0129
0.0090
32
0.0235
0.0157
0.0121
32
0.0204
0.0132
0.0097
00
0.0236
0.0157
0.0121
00
0.0204
0.0132
0.0098
Harmonica-anchor (k 3)
Harmonica-ancee anchor (k
5)
Radius
L' norm
L' norm
L norm
Radius
L norm
L' norm
1 norm
0.0057
0.0044
0.0010
0.0009
2
0.0062
0.0045
0.0003
2
0.0057
0.0041
0.0003
0.0088
0.0058
0.0052
8
0,0151
0.0097
0,0042
8
0.0139
0.0089
0.0016
0.0181
0.0116
0.0169
0.0071
32
0,0186
0.0118
0,0085
32
0.0174
0.0110
0.0079
00
0.0186
0.0119
0.0086
00
0.0174
0.0110
0.0080
Harmonica-ancee (k 7)
wewemoonnc--nnccoo (k 9)
Table 16: The interpretation error of Harmonica-anchor algorithms evaluated on the IMDb dataset for different i with a radius ranging from oo under I,2, L and L norms.
Radius
1. norm
1. norm
1. norm
Radius
1t norm
L norm
I norm
0.0573
0.0473
0.1281
0.0473
0.0389
0.0842
2
0,0681
0.0518
0.1524
0.0592
0.0442
0.1153
0.1025
0.0779
0,2855
0.0976
0.0728
0.2608
0.1382
0.1066
0.4240
0.1361
0.1040
0.4104
0.1485
0.1145
0.4562
0c
0.1462
0.1118
0.4422
Harmonica-anchor (k: 3)
Harmonica-anchor (k 5)
Radius
1" norm
L' norm
1. norm
Radius
L norm
L' norm
1 norm
0.0442
0.0362
0.0719
0.0351
0.06772
2
0.0561
0.0418
0.1053
2
0.0545
0.0404
0.0988
0.0952
8
0.1358
0.1032
0.4036
8
0.1366
0.1032
0.4011
00
0.1461
0.1110
0.1468
0.4320
Harronncaa-nnhhen (k 7)
Caamonica--nchoo (k 9)
Table 17: The interpretation error of Harmonica-anchor algorithms evaluated on the ImageNet dataset for different & with radius ranging from to co under L L' and L norms.
33

---

10
Integgreatton etrar
Intarge wetetettttnn anoor
Interppenntt
15
32
30
32
16 Subspace radius
32
Subspace radius
Subspace radius
(a) L norm
(b) L'
(c) L
Figure 18: Visualization of interpretation error I, (f 9) evaluated on SST-2 dataset of Harmonica- anchor-consttraieed (2nd order) with different coefficient X2. constrained algorithms use k 5.
Here all the Harmonica anchorr-
Radius
L
1.
1.
Radius
1.2 norm
L
1
0.0220
0.0182
0,0115
0.0234
0.0176
0.0250
0.0236
0.0166
0.0157
0.0287
0.0191
0.0329
0.0348
0.0210
0.0382
0.0251
0.0579
0.0587
0.0363
0.0977
0.0608
0.0382
0.1086
0.0777
0.1538
32
0.0813
0.0504
0.1581
32
0.0853
0.0517
0.1623
0.0812
0.0503
0,1579
0.0851
0.0516
0.1620
Harmonica-anchon
Harmonica-anchor
constrained (A2 = 0)
constrained (A2 1.0)
Radius
1 borm
norm
E norm
0.0304
0.0238
0.0317
2
0.0357
0.0258
0.0427
4
0.0461
0.0315
0.0701
8
0.0650
0.0435
0.1214
16
0,0839
0.0539
0.1663
0.0561
0.0881
0.0560
0.1745
Harmonica-ancie
constrained (A2 = =5.0)
Table 18: The interpretation error of Harmonnic-anchhor-costtii algorithms evaluated on the
SST-2 dataset for different A2 with radius ranging from to oo under L L and L norms.
M Discussion on the Low-degree algorithm
We also investigate the sample complexity of Harmonica and Low-degree algorithms, which demon- strates that Harmonica achieves better performance with the same sample size.
2004 diger aree samtin
Cnadiipee ceny semorna
deyien oteer anooee
20-1
Lnedagre po 25858
sempett
Interpreaaiee
10
Subspace
radius
Subspace redius
Subspace raduus
(a) L norm
(b) L' norm
(c) L norm
Figure 19: Visualization of interpretation error N, (J,9) evaluated on SST-2 dataset, while Har- monica and Lew-ee algorithms using different sample size varying from 2000 to 10000.
From Theorem 2 and Theorem D. we know that the sample complexity the Harmonica algo- rithm (Ō()) much more efficient than the Low-degree algorithm (Ó())). Figure shows that when evaluating the interpretation error on SST-2 dataset, with the same sample size, the Harmonica
34

---

algorithm outperforms the Low-degree algorithm by large margin. We further increase the sample size for the Low-degree algorithm and see that its interpretation error gradually approaches that of Harmonica. However, even with 5x sample size, the Low-degree algorithm still gives a larger interpretation error compared with Harmonica. However, since exactly computing the Low-degree algorithm is extremely time-consuming. here we present the results using five times the sample size to show the calculation difficulty of the Low-degree algorithm.
35


Reviews:
[{"review_id": "1mjsoT95bC", "reviewer": "Reviewer_k1pA", "summary": "This paper proposes using interpretation error as a metric to gauge inconsistencies and inefficiencies. The authors proposed three algorithms founded on the standard polynomial basis to minimize the interpretation errors. Authors perform experiments using both image and text classification to demonstrate the superior performance in terms of lowest interpretation error to the baseline methods.  ", "questions": "Besides efficiency and consistency, there are other factors that would influence the evaluation of model interpretability. Can you also show the prediction accuracy together with interpretability error for your experiments? What about computational complexity?   ", "limitations": "Not really a limitation but rather an assumption: using higher order polynomial to approximate the nonlinearity of DNN. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "A major issue for the removal-based explanation is that the change of input distribution with the removal of inputs. This makes the performance evaluation problematic. The trade-off between efficiency and consistency for removal-based explanations is well known. The novelty of this paper is to propose using a single metric, i.e., interpretation error, for evaluating the quality of model interpretation, followed by two algorithms for finding the best interpretation models assuming the interpretable model is polynomial. Authors also conducted comprehensive experiments to evaluate both interpretation error and truthful gap of Harmonica and other baseline algorithms.", "weaknesses": "To establish your approach is superior, comparison in terms of prediction accuracy and time complexity across multiple DNN architectures would be helpful. Indeed, the trade-off between prediction performance and interpretability can also be important. It would be nice to see your approach achieves lower interpretation errors without compromising prediction performance.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for dedicating their valuable time and effort to evaluate our manuscript. In the following sections, we provide detailed responses to the reviewer's comments:\n\n**Reply to Weaknesses**\n\nWe acknowledge the valid concerns surrounding prediction accuracy and computational efficiency over various DNN architectures. Central to our research is the exploration of interpretation error, providing a lens to assess the efficiency and consistency of removal-based explanations.\n\nWhile delving deeper into the intricacies of removal-based explanations, such as those typified by LIME and SHAP, we observe that they predominantly yield local or input-specific explanations. The $L_2$ interpretation error metric that we employ can be contextually visualized as a more expansive construct of inefficiency, particularly when the radius converges within 1.\n\nTo bolster our argument and cater to the reviewer's concerns, we expanded our experiments across DNN architectures, such as ResNet and VGG. Our additional findings, which can be referenced in **Table 1 and Table 2 in the PDF attached to General Response**, reveal that our method, including Harmonica and its variants, shows their superiority across different settings.\n\nFurthermore, an elucidation of the computational efficiency of these algorithms is shown in the following Table:\n\n**Table 3. Running time of different algorithms on the SST2 dataset using the model mentioned in our paper. The main characteristics affecting the running speed are listed in the table.**\n| | Main characteristics | Running time (s)|\n|---|---|---|\n| Harmonica-2nd  | parallel perturbation generation   | 225|\n| Harmonica-3rd  | parallel perturbation generation  | 616|\n| LIME  | captum.attr.LimeBase (sequential perturbation generation), exponential cosine similarity function   | 1499|\n| IG  | gradient step=500| 82|\n| SHAP  | captum.attr.KernelShap (sequential perturbation generation)   | 1235 |\n| IH  | gradient step=50| 3550|\n| Shapley Taylor Index| generate random perturbations in parallel   | 651|\n| Faith-Shap  | generate random perturbations in parallel   | 538|\n\nIt's crucial to highlight, echoing the reviewer's comment, that our algorithms, designed for interpretability, inherently don't affect the prediction accuracy of the original model $f$. In real-world applications, the unaltered model $f$ remains to be utilized for generating predictions, and this paradigm is called the post-hoc explanation. Given our positing of the Impossible Trinity Theorem, the expectation for our algorithm to excel in original efficiency, that is, interpretation error at a radius of 0—which Shapley algorithms pay attention to—may not be theoretically feasible (see **Table 6 in the PDF attached to General Response**). The enriched analyses and insights will seamlessly integrate into our revised manuscript, offering a more comprehensive view of the nuanced trade-offs in play.\n\n**Reply to Questions**\n\nRegarding the questions on other factors influencing the evaluation of model interpretability, we agree with the reviewer's point. Our focus on efficiency and consistency does not exclude the consideration of other essential aspects such as prediction accuracy and computational complexity. In fact, the interpretation error metric can be seen as a generalized version of inefficiency (prediction error), especially when the radius is set to within $1$.\n\nIn our additional experiments, we include prediction accuracy (**Table 1 and Table 2 in the PDF attached to General Response**) along with interpretability error as evaluation criteria. This will allow readers to understand the proposed method's performance in a broader context. Additionally, we will provide a thorough analysis of the computational complexity of our algorithms. It is already presented in Appendix C, Theorem 3. This additional information will offer a more in-depth understanding of the computational costs associated with achieving the improvements in interpretation error, thereby providing a more nuanced view of the trade-offs involved in our approach. \n\n**Reply to Limitations**\n\nThe assumption regarding the usage of higher-order polynomials to approximate the non-linearity of DNN is indeed an essential aspect of our approach. It is vital to recognize that this assumption while facilitating the development of our algorithms, has theoretical guarantees: all removal-based explanations can be seen as Boolean functions over feature subsets, and all Boolean functions can be represented as Boolean polynomials (using Fourier basis).\n\nHowever, we have carefully considered this aspect in the design of our algorithms and have chosen low-order polynomial approximation as a reasonable trade-off between model complexity and interpretability. To address the precision issue, we introduce the notion of truthfulness, making this low-order assumption reasonable and quantifiable. In the revised paper, we will expand on this assumption and its implications, providing insights into the rationale behind this choice and its potential limitations. This will further clarify the scope and applicability of our methods.\n"}, {"review_id": "fK3epFmZa8", "reviewer": "Reviewer_XVSh", "summary": "The paper analyses the trade-off between efficiency and consistency in the context of removal-based post-hoc explanations. The authors demonstrate that having an interpretability method that is both efficient and consistent is impossible. Further, on the problem of finding consistent explanations, the authors propose to relax the efficiency desiderata and instead propose a new desiderata called truthfulness (efficiency within a subspace). The authors argue that this maps to the problem of learning Boolean functions that can be tackled by using Fourier analysis.", "questions": "\n1.  In experiments mentioned in section 6.1, how did the authors choose the feature values to compute ground-truth?\n\n2. What version of the SHAP algorithm was used? Further, as LIME is very sensitive to the chosen hyperparameters[2], I wonder what are the hyperparameters for the LIME algorithm.\n\n\n[2]  https://arxiv.org/pdf/2005.07788.pdf\n\n\n", "limitations": "The authors do not mention any  limitations of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written. The motivation, definitions and key contributions are clearly explained.\n\n2. The core idea of leveraging Fourier analysis in the context of removal-based explanations is interesting.\n\n3. The experiments and bibliography sections are extensive. ", "weaknesses": "1. I do not understand why is consistency of explanations a more important desiderata than efficiency. Instead, one may argue that efficiency is critical since it acts as a proxy to the problem of lack of ground-truth. Specifically, one of the main advantages of using SHAP is that supports some mathematically properties which come handy in the absence of ground-truth. Since, due to impossibility, we can't achieve both, I would be keen to hear when is consistency more important than efficiency. Further, here we talk about consistency in Boolean sense which I guess is different in a non-Boolean sense (similar inputs should have similar explanations) as there this desiderata is referred to as robustness.\n\n2. Using Fourier analysis for Boolean functions is a well-explored topic. Hence, although interesting, I see limited novelty in applying this to post-hoc removal-based methods.\n\n3. Some experimental details seem to be missing. For example, all removal based methods use a baseline and the explanations are quite sensitive to the choice of the baseline [1]. I wonder what is baseline for SHAP/IG/LIME etc. and if the authors analysed the effect of choosing a different baseline.\n\n[1]  https://distill.pub/2020/attribution-baselines/\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for dedicating their valuable time and effort to evaluate our manuscript. In the following sections, we provide detailed responses to the reviewer's comments:\n\n**Reply to Weaknesses**\n\n1. The prioritization of consistency over efficiency in our paper stems from the need to establish a framework that provides coherent and reliable interpretations. Efficiency is, of course, crucial, particularly when it acts as a proxy to the problem of lack of ground-truth, as you rightly pointed out. However, we argue that consistency is vital in ensuring that the explanation methods provide stable and repeatable results, which align with our core objectives. In the Boolean sense, consistency refers to the agreement of an explanation over multiple instances around the input neighborhood, whereas in a non-Boolean sense, it aligns with robustness as you mentioned. We will expand upon this differentiation and emphasize scenarios where consistency might outweigh efficiency in the revised paper.\n\n2. While the application of Fourier analysis to Boolean functions may be well-explored in many areas, our work's novelty lies in the specific context and application to removal-based post-hoc methods. By leveraging Fourier analysis, we create a unique perspective that resonates with the fundamental challenges of consistency and efficiency in explainable AI. We will emphasize this aspect further to highlight the distinctiveness of our approach.\n\n3. Your observation regarding the sensitivity of explanations to the choice of baselines is valid, and indeed, this is a critical aspect of removal-based methods like SHAP, IG, and LIME. In our experiments, we have selected baselines that align with established practices for each method, and we have conducted additional analysis to understand the effect of choosing different baselines in **Table 7** and **Table 8**. The revised paper will include detailed information about these baselines and the implications of various choices.\n\n**Table 7. Interpretation error on ImageNet Using average as baseline. Bold means the best. Italic means the second.**\n|                | radius=1 | 2      | 4      | 8      | 16     |\n|----------------|----------|--------|--------|--------|--------|\n| Harmonica-2nd  | 0.1341   | _0.1279_ | _0.1201_ | _0.1243_ | _0.1304_ |\n| Harmonica-3rd  | **0.1012**   | **0.1025** | **0.1022** | **0.1095** | **0.1156** |\n| LIME           | 0.2205   | 0.2142 | 0.2095 | 0.2327 | 0.2520 |\n| SHAP           | _0.1022_   | 0.1410 | 0.1934 | 0.2307 | 0.2357 |\n| IG             | 0.1824   | 0.2468 | 0.3280 | 0.3822 | 0.3835 |\n| IH             | 0.6292   | 0.8497 | 1.1356 | 1.3752 | 1.4115 |\n| Shapley Taylor | 0.1293   | 0.1665 | 0.2157 | 0.2550 | 0.2534 |\n| Faith-Shap     | 0.1219   | 0.1530 | 0.1918 | 0.2288 | 0.2302 |\n\n**Table 8. Interpretation error on ImageNet Using blur as baseline. Bold means the best. Italic means the second.**\n|                | radius=1 | 2      | 4      | 8      | 16     |\n|----------------|----------|--------|--------|--------|--------|\n| Harmonica-2nd  | 0.0207   | _0.0209_ | _0.0210_ | _0.0218_ | _0.0225_ |\n| Harmonica-3rd  | _0.0200_   | **0.0203** | **0.0204** | **0.0213** | **0.0220** |\n| LIME           | 0.0260   | 0.0276 | 0.0310 | 0.0372 | 0.0394 |\n| SHAP           | **0.0184**   | 0.0258 | 0.0360 | 0.0460 | 0.0477 |\n| IG             | 0.0215   | 0.0299 | 0.0415 | 0.0524 | 0.0541 |\n| IH             | 0.0268   | 0.0373 | 0.0525 | 0.0684 | 0.0718 |\n| Shapley Taylor | 0.0350   | 0.0370 | 0.0385 | 0.0372 | 0.0360 |\n| Faith-Shap     | 0.0343   | 0.0358 | 0.0368 | 0.0358 | 0.0350 |\n\n**Reply to Questions**\n\n1. In the experiments delineated in Section 6.1, analytical close-form evaluation was employed for the computation of ground-truth feature values in the context of synthetic polynomial experiments. Conversely, in vision and language tasks, the computation of ground-truth feature values necessitated the selection predicated on the specific datasets and models utilized. This selection process was carefully carried out to ensure a comprehensive representation and alignment with the problem space.\n\n2. The SHAP algorithm is implemented from KernelShap in Captum v0.5.0. It reduces the computation cost of calculating Shapley values and is widely used in relevant works. The LIME algorithm is implemented from LimeBase in Captum v0.5.0. The choice of hyperparameters was based on an exhaustive series of trials to confirm the robustness of the results. We use the exponential cosine similarity function to evaluate the distance between sample embeddings. The perturbation function is set to be a Bernoulli distribution and the interpretable model is set to a Lasso model with sparsity coefficient $\\alpha=0.001$. An in-depth elaboration on the versions, hyperparameters, and underlying rationale for these particular selections will be furnished in the revised manuscript."}, {"review_id": "fIA4LbYu9d", "reviewer": "Reviewer_PY9W", "summary": "This paper explores the interplay between two properties of removal based explanations: efficiency and consistency. It established that these two properties cannot coexist when the set of predictive models (requiring explanation), and the set of interpreting models (doing the explaining) are disjoint. It proposes a new property: “truthfulness”, which is a relaxation of efficiency, and measures the information-capture within a functional sub-space (a chosen subset of the interpretable models). It proposes several algorithms for learning truthful interpreting models, grounded in methods from Boolean functional analysis, which allow for different trade-offs between consistency and efficiency. It compares these algorithms to existing methods by looking at the interpretation error on a few practical NLP and Vision tasks. ", "questions": "The paragraph starting on line 218 quantifies inconsistency, but does not explicitly explain how. What is an “amount” of inconsistency? It seems like what is being reported is the number of different explanation functions required in the neighbourhood.\n\nIs Figure 2 correctly labeled? Should the subspace radius for Imagenet not be 1-16 and 1-\\inf be for IMDB the \n\nShould the C in Harmonica-anchor be indexed by i? \n\nIn Table 1 and Section 6.4, it is not clear to me why we would expect (or even want) any of the other methods (other than Harm. 3rd) to have a small “truthful gap” in C^3. The other methods do not aim to explain with 3rd order polynomials. Why should we assess them in this way?\n\nIt would seem to me that Harmonica’s “truthful gap” should be a function of T and \\lambda, is this explored somewhere?", "limitations": "The paper would benefit from an explicit discussion of its limitations.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors demonstrate a solid understanding of existing removal-based (and other) explainability methods. The paper surveys a large number of these related works.\nThe paper explains a tension in post-hoc explanations: efficiency vs. consistency in a concise and easy to understand way. \nThe front half of the paper (sections 1 to 4.1), where most of the concepts are presented, is clearly written and easy to understand.\nThe paper draws insightful connections between producing interpreting models and work in Boolean functional analysis.\nBetween the theoretical discussion, the methods introduced, and the subsequent experiments, the paper makes numerous useful contributions. \n", "weaknesses": "The paper defines consistency for explanations (Definition 3.2). It is unclear whether the authors are proposing this particular definition, or if it has been previously defined in this way. This should be clarified. Furthermore, the term consistency has been used differently in the explainability and ML literature previously, albeit more casually. It would be helpful to contrast this definition to other ways the term has been used, and to relate/contrast it to other previously defined properties of explanations, such as fidelity.\n\nThe motivation for consistency could be improved. The extent to which consistency is desirable, and the size of the neighborhood in which it would be desired, both seem to be highly dependent on how the explanation is going to be used. As it stands, there is a single (simple) motivating example in the main text. Since the primary reason one would use the methods proposed in the paper is to improve consistency, it seems reasonable to further motivate this property.\n\nI question the choice of the words “truthful” and “truthfulness” for Definition 3.4 .When T_v = 0, g is a sort of best approximation to f within a space of interpretable models. The property is interesting, but it does not intuitively align with “truthfulness” for me. With the number of overloaded terms that already exist in the explainability space (many of which invoke their own “layman” concepts), I caution against introducing another, especially a term as loaded as “truth”. I strongly encourage the use of a more verbose and precise term. \n\nIt seems unfair to call Theorem 1 the “Impossible Trinity for Interpretability” when the set of interpretable models is separated from the set of predictive models in order to get the result. Interpretable models are a very important class of predictive models. If the authors wish to name the result, I would suggest something along the lines of “Impossible Trinity for Post-Hoc Explanation”.\n\nThere is something of a conceptual gap in the flow of the paper. Section 3, and all definitions consider an arbitrary input space X. While Section 4 onwards deals with Boolean functions. What is missing is any real discussion of the process of binarizing real-valued (or other) inputs and how that affects or relates to consistency. From what I understand, ensuring the consistency of an explanation in a neighborhood of removed features (the binarized input space) is different from ensuring the consistency of that explanation in some ball around the original real-valued input. This is simply because moving to another region of the original input space (for example by changing a word/token in an input sentence or by perturbing the input image) will require a different binarization, because what it means to include/exclude one (or more) of the features is different. This seems like it should be better explored and discussed.\n\nThe paper discusses “amounts” of inconsistency, but only defines what it means to be consistent, not how to measure deviation from consistency. This seems like a considerable omission, especially since Algorithm 3 aims to reduce inconsistency. \n\nThe second half of the paper (section 4.2 onwards) struggles with clarity. \n\nThe paper should include concrete examples of output explanations. Especially for Harmonica-anchor and the constrained variant. As it stands, I do not understand how one is meant to take a set of coefficients for some polynomial bases and produce a heatmap over an image or textual input. I can guess, but this should be made clear. \n\nThe algorithm boxes include some notation that is not explained elsewhere in the main text. For instance, C is introduced in the appendix. Algorithm 1 should define input and outputs.\n\nFor clarity I would also consider using different symbols when referring to Boolean models vs. models having arbitrary inputs, instead of f(x) for both. \n\nFinally, the paper relies heavily on the Appendix, and in that sense the main text does not truly seem self-contained. For instance, in the opening paragraph of the introduction the authors ask the reader to refer to a figure in the Appendix (Figure 3). I suggest shuffling some content around. For instance, the definition of the Shapley value (which is well-known in the field) and even Figure 1 (which isn’t really discussed), would both seem like more appropriate Appendix content than Figure 3, which helps to motivate consistency. The current introduction could also be compressed somewhat. \n\nSome typos:\nLine 72: “the algorithm only retain”\nLine 131 “We call A model g is interpretable”\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for dedicating their valuable time and effort to evaluate our manuscript. In the following sections, we provide detailed responses to the reviewer's comments:\n\n**Reply to Weaknesses**:\n\n1. *Definition of Consistency*: We acknowledge that the term \"consistency\" has been previously employed in different contexts within machine learning and explainability. We used the term to signify a unique attribute related to our framework, not intending to replicate or conflict with existing definitions. We will include references and draw contrasts with other uses of the term to avoid any confusion. Additionally, we will enhance the section by elaborating on the motivation for consistency and providing more examples to illustrate its importance.\n\n2. *Usage of “Truthful” and “Truthfulness”*: We understand the concern related to the terminology used. The terms were chosen to convey the aspect of a model’s accurate approximation within an interpretable space. However, recognizing the potential for confusion, we are happy to change the names of these terms. If you happen to have any good candidates, please do let us know!\n\n3. *Naming of Theorem 1*: The name “Impossible Trinity for Interpretability” was chosen to highlight the core result of our work. We see the reviewer's point and will revise the name to something more fitting, such as “Impossible Trinity for Post-Hoc Explanation.”\n\n4. *Conceptual Gap Regarding Binarization and Consistency*: Indeed, the transition from arbitrary input space to Boolean functions might seem abrupt. We will include a more comprehensive explanation of this process and explore the relationship between the real-valued input and the consistency in a neighborhood of removed features.\n\n5. *Measurement of Deviation from Consistency*: While the current framework defines what it means to be consistent, we understand the necessity to formalize how to measure deviation from consistency. We will extend our methodology to include this aspect.\n\n6. *Clarity in Sections 4.2 Onwards and Concrete Examples*: We acknowledge that the latter sections may benefit from improved clarity. We will revise the text to enhance readability and will incorporate concrete examples of output explanations, specifically for the mentioned algorithms.\n\n7. *Algorithm Notation and Other Typos*: We appreciate the attention to detail in pointing out the notation issues and typographical errors. These will be rectified in the revised version.\n\n8. *Reliance on the Appendix*: We agree with the suggestion to make the main text more self-contained. Necessary adjustments will be made to shuffle content appropriately between the main text and the appendix.\n\nWe believe these responses address the reviewer’s main concerns. We value this constructive feedback and commit to making the necessary revisions to clarify and enhance our work.\n\n\n**Reply to Questions**\n\n1. *Inconsistency Quantification*: The inconsistency definition in line 218 characterizes the fluctuation in explanation functions within a designated neighborhood. It is indeed a gauge reflecting the multiplicity of differing explanation functions required. Such metrics can quantify inconsistencies, and our objective is to measure this to further comprehend the trade-offs inherent in removal-based explanations. Alongside this inconsistency, we define the Spectrum distance in Appendix B, Definition B.2, which manifests as the $L_p$ version of the definition of inconsistency. Notably, as proclaimed in Proposition B.3 and B.4, for a uniform distribution $\\mu$, the $L_2$ inconsistency $\\mathbb{D}_2$ (spectrum distance) aligns with the $L_2$ interpretation error $\\mathbb{I}_2$. This elucidates why Harmonica emerges as the natural selection for balancing efficiency and consistency, as it concurrently minimizes both inefficiency (interpretation error) and inconsistency (spectrum distance).\n\n2. *Figure 2 Labeling*: Thank you for bringing this to our attention. Upon inspection, you are correct, and there is an error in labeling. The subspace radius for ImageNet should indeed be 1-16, while 1-$\\inf$ pertains to IMDB. This mistake will be corrected in our revised paper.\n\n3. *Harmonica-Anchor Indexing*: The choice to omit the indexing by $i$ in Harmonica-anchor was intentional for simplicity. However, we appreciate that the notation may cause confusion, and we will clarify this in the revised manuscript.\n\n4. *Assessment in Table 1 and Section 6.4*: The comparison using a 3rd-order polynomial in $C^3$ space is not meant to judge all methods equally, but rather to offer a standardized benchmark. It is acknowledged that some methods may not be tailored for this specific analysis, but this provides an informative baseline for the different approaches. Please refer to General Response and attached supplementary PDF for the Insert/Deletion experiments, where our method still shows consistent superior performance.\n\n5. *Harmonica's ``Truthful Gap''*: You are correct to observe that Harmonica's truthful gap is likely influenced by parameters $T$ and $\\lambda$. This relationship was considered during our internal experimentation but was not explicitly addressed in the paper. Noteworthy that by concentration inequalities (presented in Appendix C, Theorem 3) and the law of large numbers, We can prove the convergence rate for empirical estimation of the Truthful Gap, which means that when $T$ is large enough, this estimation is rigorous. Further exploration of these dependencies can be valuable, and we plan to include this analysis in extended work.\n\n**Reply to Limitations**\n\nWe acknowledge the limitations highlighted above and appreciate the opportunity to reflect on them. Specifically, we believe that future research can expand upon our work by adapting our methods to other paradigms beyond removal-based explanations, optimizing computational efficiency, and further validating our findings across diverse datasets and domains."}, {"review_id": "PJryMPLHNC", "reviewer": "Reviewer_ngxu", "summary": "This paper addresses the problem of tradeoffs between interpretability, consistency, and efficiency of AI models. The authors present “the Impossible Trinity Theorem”, which posits that interpretability, efficiency and consistency cannot hold simultaneously. To quantify the tradeoff, the authors define the utilization of interpretation error as a metric to gauge inconsistencies and inefficiencies of AI models in order to minimize an interpretation error. With such definitions of terms and metrics, the authors achieve a reduction in interpretation error, up to 31.8 times lower when compared to alternative techniques.\n", "questions": "In reference to “Note that all of these methods are applied to the same image segmentation using the SLIC superpixels [61]. “ it is not clear why the simple linear iterative clustering algorithm applied to 224 x 224 images split into 16 superpixels is used as ground truth for ImageNet rather ground truth segmentation obtained by manual segmentation.\n", "limitations": "Overall, the framework has introduced too much complexity for a problem that can be described very clearly. For example, Theorem 1(Impossible Trinity for Interpretation) could just state that the input-output relationship in a trained AI model is either accurate and non-linear or inaccurate and linear.\n\nThe focus should be rather on Fourier spectrum and the order of Harmonica algorithm (i.e., LASSO regression over the coefficients on the polynomial basis) needed to meet a given epsilon error.  \n", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The strength of the paper lies in the effort to formulate a mathematical framework including efficiency, consistency, and interpretability of AI models. The framework separates linear and non-linear parts of input-output functions represented by trained AI models by stating “only linear functions are readable” and therefore interpretable.", "weaknesses": "The weaknesses of the paper lie in \n(1)\tforcing reviewers to read Appendices because the main text does not contain sufficient results supporting the claims. This is unfair to other submissions.\n(2)\tobfuscating many simple concepts with too many theorems and definitions to formulate relationships.\n(3)\tmissing discussion why 2nd order Harmonica results are worse than Shapley in Table 1 which implies that the 3rd order Harmonica is needed. BTW, Standard deviation would help to understand statistical significance of the values when comparing the results.  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for dedicating their valuable time and effort to evaluate our manuscript. In the following sections, we provide detailed responses to the reviewer's comments:\n\n**Reply to Weaknesses**\n\n1. It is acknowledged that the main text may seem to lack sufficient results without referring to the Appendices. However, the appendices were employed to provide additional details without overcrowding the main paper. We are happy to move essential content into the main text if that serves the readability better.\n\n2. Regarding the use of theorems and definitions, the intention was to establish a robust mathematical foundation for the relationships explored. This rigorous formulation ensures precision and clarity for researchers in the field. However, the feedback is well taken, and a future revision will consider a more streamlined presentation without sacrificing the depth of the content.\n\n3. As for the comparison between the 2nd-order Harmonica and Shapley in Table 1, an additional explanation can indeed enhance the understanding of the findings. The 3rd-order Harmonica's necessity over the 2nd-order stems from its ability to capture higher complexity. The suggestion to include standard deviation is well-recognized, and we will include this statistical information to provide more robust insights into the data.\n\n**Reply to Questions**\n\nThe use of the simple linear iterative clustering (SLIC) algorithm applied to 224 x 224 images split into 16 superpixels was chosen due to its common usage in the field such as LIME (Ribeiro et. al, 2016) and its ability to provide a standardized benchmark for comparison. It must be noted that SLIC's adoption is not meant to serve as an absolute ground truth but as a comparative basis. Your concern is valid, and we have conducted a comparison with manual segmentation using the MS-COCO dataset. Note that the number of ground-truth segmentation superpixels is around 3 in MS-COCO. The results are shown in **Table 4 in the PDF attached to General Response** and two interpretation examples are shown in **Figure 1 in the PDF attached to General Response**. We also conducted experiments using SLIC algorithm and set the number of superpixels as 10. The results are shown in **Table 5 in the PDF attached to General Response** following exactly LIME (Ribeiro et. al, 2016).\n\n\n**Reply to Limitations**\n\nThe complexity of the framework was designed with the intention to provide a comprehensive understanding of the nuanced trade-offs between interpretability, consistency, and efficiency in AI models. The focus on the Fourier spectrum and the order of the Harmonica algorithm is indeed crucial, and we appreciate the suggestion to emphasize these aspects. This feedback will be carefully considered in the revisions to ensure that the complexity serves the purpose of clarity and thorough understanding.\n\n"}, {"review_id": "Nxexl5nj8D", "reviewer": "Reviewer_JLEA", "summary": "This paper studies the consistency and efficiency of removal-based explanation methods. By establishing the impossible trinity theorem, the authors show that consistency and efficiency cannot be achieved simutaneously. They further propose the interpretation error as a metric to gauge the trade-off between consistency and efficiency.  Then, two algorithms based on standard polynomial basis are developed to minimize the interpretation error for more consistent explanations, when relaxing the efficiency to truthfulness. ", "questions": "1. At line 136, if the consistency should be conditioned on a local input region which shares the same ground truth label?\n\n2. At line 139, how to match the definition of efficiency with that at line 194?\n\n3. How to approximately calculate the equation 2 and 3 in experiments?\n\n4. Apart from the proposed metrics, truthful gap and interpretation error, are there any existing metrics in current literature for consistency and efficiency? The existing ones should be compared with the proposed ones.", "limitations": "Please see the weakness and questions.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Consistency and efficiency are important properties for evaluating explanation methods.\n2. The finding of trade-off between efficiency and consistency is interesting and leads to some insights.", "weaknesses": "1. My major concern is that this paper is quite hard to follow and the presentation needs significant improvement. The authors present a lot of definitions and claims but not sufficient explanations and motivations for them.\n\n2. The definition for consistency and efficiency is not rigorous and seems to be different from that in previous literature. The authors should justify the correctness of definitions and give more explanations here.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our gratitude to the reviewer for dedicating their valuable time and effort to evaluate our manuscript. In the following sections, we provide detailed responses to the reviewer's comments:\n\n**Reply to Weaknesses**\n\n1. Acknowledging that the presentation may be complex for some readers, we appreciate the suggestion to clarify our definitions and claims. In light of the feedback, we'll further elucidate the concepts presented within the paper:\n\n    *a)* The definitions of consistency and efficiency are indeed tailored to suit the context of removal-based explanation methods. While they might differ from previous literature, these definitions are specifically designed to encapsulate the unique characteristics of our proposed framework. To address this concern, we will elaborate on the rationale behind our definitions in the revised version, providing a comprehensive justification.\n\n    *b)* The various definitions and theorems contribute to our primary objective of defining a trade-off between efficiency and consistency. We will enhance the motivation and explanations for these concepts, drawing clearer connections between them to foster a cohesive understanding of the paper's core ideas.\n\n2. We recognize the necessity for rigorous definitions and will ensure that our definitions for consistency and efficiency align with the theoretical foundations of our work. We will cross-reference the lines indicated, justifying the correctness of our definitions and providing additional context to clarify any ambiguities.\n\n\n**Reply to Questions**\n\n1. Consistency: In our framework, consistency is conceived as a general property. We recognize that conditioning it on a local input region with the same ground truth label is an insightful enhancement. This can be formalized using specific distribution $\\mu$ in the definition of interpretation error, other than uniform distribution without any prior. This aspect and its integration into our framework will be detailed in the revised paper.\n\n2. Efficiency: The definition of efficiency at lines 139 and 194 is aligned within our context. The discrepancies are likely due to notational conventions. If we denote $g:= \\sum_{i \\in N} \\phi_i (v) + v (\\emptyset)$, then these two efficiency definitions are aligned in the sense that function $g$ equals to function $f$ at specific input $x$: $g(x) = f(x)$.\n\n3. Approximation Methodology: For approximating equations 2 and 3 in our experiments, we have applied numerical sampling estimation specific to our problem structure (in Appendix J), which has concentration inequality guarantees presented in Appendix C, Theorem 3. We will further elucidate the estimation method in the experimental section to enhance the readability of our paper.\n\n4. Comparison with Existing Metrics: A meticulous analysis of the current literature will be conducted in our revised paper. Metrics such as Insert/Delection will be incorporated into our comprehensive evaluation strategy. We have now conducted Insertion and Deletion experiments on the SST2 dataset shown in **Figure 2a and 2b in the PDF attached to General Response**. Notice that these two metrics are limited to first-order interpretation algorithms, so we downgrade Harmonica to its first-order version. We can see that removal-based algorithms (Harmonica, LIME, and SHAP) perform comparably.  This comparison is designed to emphasize the innovation and benefits of our proposed approach. "}]

Author rebuttal:
# General Response

We are deeply grateful for the efforts and valuable feedback of the reviewers and area chairs in reviewing our manuscript. We have made a detailed response to each reviewer's concern, including some clarifications and additional experimental results, and adopted some of the reviewer's suggestions. Some tabular results and figures are placed in attached PDF. We hope these contents can help reviewers understand our manuscript better.

### **More Experimental Results**

In the supplementary PDF, we present more experimental results on:

1. Interpreting different neural network architectures such as ResNet and VGG, interpreting MS-COCO dataset with ground-truth segmentation labels (with illustrative examples).

2. Ablations on the feature subset size when applying the SLIC algorithm for image segmentation.

3. Comparison of different interpretation algorithms on other existing metrics such as Insert/Delection, where Fourier analysis-based method Harmonica still shows consistent superior performance.

We hope these supplementary experiments will illuminate the robustness and efficacy of our method, thereby strengthening both the credibility and relevance of our conclusions.


Meta-review: This paper has had a very positive assessment overall. Overall, I think the authors may have to include a lot of new experimental results and make some changes as suggested by the reviewers. But barring those issues, I recommend acceptance.

The main result is that the authors show an impossibility theorem -- namely, that an interpretable model cannot be simultaneously consistent and efficient for removal-based explanations. The authors first identify that all interpretable models for removal-based explanations can be written as a boolean function over the boolean hypercube formed by a number of variables equal to the number of features. This lets them use Fourier analysis tools.

The authors then show that a sparse polynomial regression model is consistent, at least with respect to the subspace of monomials considered, but is not efficient, while SHAP is efficient but not consistent. Therefore, the authors explore the possibility of a local version of sparse polynomial regression that trades off consistency with efficiency better.

Concerns raised during the rebuttal and discussion were addressed, with the authors performing additional experiments on running time, evaluating removal-based explainers with different baselines, and also expanding experiments for ResNet and VGG architectures.
Decision: Accept (poster)