Year: 2021

Abstract:
Machine learning methods are getting increasingly better at making predictions, but at the same time they are also becoming more complicated and less transparent. As a result, explanation methods are often relied on to provide interpretability to these complicated and often black-box prediction models. As crucial diagnostics tools, it is important that these explainer methods themselves are reliable. In this paper we focus on one particular aspect of reliability, namely that an explainer should give similar explanations for similar data inputs. We formalize this notion by introducing and defining explainer astuteness, analogous to astuteness of classifiers. Our formalism is inspired by the concept of probabilistic Lipschitzness, which captures the probability of local smoothness of a function. For a variety of explainers (e.g., SHAP, RISE, CXPlain, PredDiff), we provide lower bound guarantees on the astuteness of these explainers given the Lipschitzness of the prediction function. These theoretical results imply that locally smooth prediction functions lend themselves to locally robust explanations. We evaluate these results empirically on simulated as well as real datasets.

heading: 1 INTRODUCTION
text: Machine learning models have improved over time at prediction and classification, especially with the advances made in deep learning and availability of large amounts of data. These gains in predictive power have often been achieved using increasingly complex and black-box models. This has led to significant interest in, and a proliferation of, explanation models that provide explanations for the predictions made by these black-box models. We focus our work in analyzing the behaviour of these explanation models. In particular, we explore when are explainers reliable by analyzing the connection between the robustness of explainer methods and the smoothness of the black-box functions they are trying to explain. We propose and formally define explainer astuteness – a property of explainers which captures the probability that a given method provides similar explanations to similar data points. We then provide a theoretical way to connect this explainer astuteness to the probabilistic Lipschitzness of the black-box function that is being explained. Since probabilistic Lipschitzness is a measure of the probability that a function is smooth in a local neighborhood, our results demonstrate how the smoothness of the black-box function itself impacts the astuteness of the explainer. This implies that enforcing smoothness on black-box functions lends them to more robust explanations.
Related Work. A wide variety of explainers have been proposed in the literature (Guidotti et al., 2018; Arrieta et al., 2020). Explainers can broadly be categorized as feature attribution or feature selection explainers. Feature attribution explainers provide continuous valued importance scores to each of the input features, while feature selection explainers provide binary decisions on whether a feature is important or not. Some popular feature attribution explainers can be viewed through the lens of shapley values such as SHAP (Lundberg & Lee, 2017), LIME (Ribeiro et al., 2016) and LIFT (Shrikumar et al., 2016). Some models such as CXPlain (Schwab & Karlen, 2019), PredDiff (Zintgraf et al., 2017) and feature ablation explainers (Lei et al., 2018) calculate feature attributions by simulating individual feature removal, while other methods such as RISE (Petsiuk et al., 2018) calculate the mean effect of a feature’s presence to attribute importance to it. Feature selection methods, on the other hand include individual selector approaches such as L2X (Chen et al., 2018) and INVASE (Yoon et al., 2018), and group-wise selection approaches such as gI (Masoomi et al., 2020). These models, while seemingly diverse have been shown to have striking underlying simi-
larities, for example Lundberg & Lee (2017) unify six different explanation models under a single umbrella. Recently, Covert et al. (2020) went a step ahead and combined 25 existing methods under the overall class of removal-based explanation models.
Similarly, there has been a recent increase in research focused on analyzing the behaviour of these explanation models themselves in ways similar to how classification models have been analyzed. Recent work has focused on dissecting various properties of explainers. Yin et al. (2021) propose stability and sensitivity (Yin et al., 2021) as measures of faithfulness of explainers to the decisionmaking process of the black-box model. Li et al. (2020) explore connections between local explainability and model generalization. Ghorbani et al. (2019) poke at the robustness of explainers to systemic and adversarial perturbations. Alvarez-Melis & Jaakkola (2018) empirically show that robustness, in the sense that explainers should provide similar explanations for similar inputs, is a desirable property and how forcing this property yields better explanations. Recently, Agarwal et al. (2021) explore the robustness of LIME (Ribeiro et al., 2016) and SmoothGrad (Smilkov et al., 2017), and prove that for these two methods their robustness is related to the maximum value of the gradient of the predictor function. Our work is closely related to Alvarez-Melis & Jaakkola (2018) and Agarwal et al. (2021) on explainer robustness. However, as opposed to only forcing explainers to be robust themselves (Alvarez-Melis & Jaakkola, 2018), our theoretical results suggest that ensuring robustness of explanations also depends on the smoothness of the black-box function that is being explained. Our results are complementary to the results obtained by Agarwal et al. (2021) in that our theorems cover a wider variety of explainers (see contributions below). We further relate robustness to probabilistic Lipschitzness of blackbox functions which is a quantity that can be empirically estimated.
Contribution:
• We formalize and define explainer astuteness which captures the probability that a given explainer provides similar explanations to similar points. This formalism allows us to theoretically analyze robustness properties of explainers. • We provide theoretical results that connect astuteness of three classes of explainers; shapley value based (e.g. SHAP), explainers that simulate mean effect of features (e.g. RISE), and explainers that simulate individual feature removal (e.g. CXPlain), to the smoothness of the black-box function. Our results suggest that enforcing Lipschitzness on black-box functions can result in explainers providing more astute explanations. Formally our theorems establish a lower bound on explainer astuteness that depends on the Lipschitness of the black-box function and square root of data dimensionality. Figure 1 summarizes this main contribution of our work. • We demonstrate experimentally that this lower bound indeed holds in practice by comparing the astuteness predicted by our theorems to the observed astuteness on simulated and real datasets.
The remainder of this paper is organized as follows: we first provide background on the type of explanation methods we restrict ourselves to, i.e. removal based feature explainers, and the summary of notation used in this paper in Section 2. We then provide formal definitions and theorems with proofs in Section 3. Finally, we conclude the paper by providing experimental results in Section 4.

heading: 2 BACKGROUND AND NOTATIONS

heading: 2.1 REMOVAL-BASED FEATURE EXPLAINERS
text: As mentioned in Section 1 a wide variety of explainer methods has been introduced. Owing to this diversity, in this work, we concern ourselves with removal-based feature attribution explainers as defined by Covert et al. (2020). Removal based feature attribution explainers are methods that define a feature’s influence through the impact of removing it from a model and assign continuous valued scores to each feature signifying its importance. This includes popular approaches such as SHAP and SHAP variants including KernelSHAP, LIME, DeepLIFT (Lundberg & Lee, 2017), mean effect based methods such as RISE (Petsiuk et al., 2018), and individual effects based methods such as CXPlain (Schwab & Karlen, 2019), PredDiff (Zintgraf et al., 2017), permutation tests (Strobl et al., 2008), and feature ablation explainers (Lei et al., 2018). All of these methods simulate feature removal either explicitly or implicitly. For example, SHAP explicitly considers effect of using subsets
that include a feature as compared to the effect of removing that feature from the subset. RISE removes subsets of features while always keeping the feature that is being evaluated, and estimates the average effect of keeping that feature when other features are randomly removed. CXPlain explicitly considers the impact of removing a feature on the loss function used in training the predictor function.

heading: 2.2 NOTATION
text: Before formalizing explainer astuteness and our theoretical results, we explain the notations used in the rest of the paper. We denote d-dimensional input data as x ∈ Rd, from a given dataset D. The black-box predictor function is denoted by f , where f(x) is the prediction given x, this function is assumed to have been trained on the given D. The explainer is represented by a function φ where φ(x) ∈ Rd is the feature attribution vector representing attributions for all features in x while φi(x) ∈ R is the attribution for the ith feature. To simulate the presence or absence of features in a given subset of features, we use an indicator vector z ∈ {0, 1}d, where zi = 1 when the ith feature is present in the subset. To indicate we are only using subsets where feature zi = 1, we use z+i; and to indicate only using subsets where feature zi = 0, we use z−i. Lastly, the p-norm induced distance between any two points x, x′ is denoted by dp(x, x′).

heading: 3 EXPLAINER ASTUTENESS
text: Our main interest is in defining a metric that can capture the difference in explanations provided by an explainer to points that are close to each other in the input space. The same question has been asked for classifiers and Bhattacharjee & Chaudhuri (2020) came up with the concept of Astuteness of classifiers, which captures the probability that similar points are assigned the same label by a classifier. Formally they provide the following definition:
Definition 1. Astuteness of Classifiers (Bhattacharjee & Chaudhuri, 2020): The astuteness of a classifier f over dataset D, denoted as Ar(f,D) is the probability that ∀x, x′ ∈ D such that d(x, x′) ≤ r the classifier will predict the same label.
Ar(f,D) = Px,x′∼D[f(x) = f(x′)|d(x, x′) ≤ r] (1)
The obvious difference in trying to adapt this definition of astuteness to explainers is that explanations for nearby points do not have to be exactly the same. Keeping this in mind, we propose and formalize explainer astuteness, as the probability that the explainer method assigns similar explanations to similar points. The formal definition is as follows:
Definition 2. Explainer astuteness: The explainer astuteness of an explainer E over dataset D, denoted as Ar,λ(E,D) is the probability that ∀x, x′ ∈ D such that dp(x, x′) ≤ r the explainer E will provide explanations that are at most λ ∗ dp(x, x′) away from each other, where λ ≥ 0
Ar,λ(E,D) = Px,x′∼D[dp(φ(x), φ(x)) ≤ λ ∗ dp(x, x′) ∣∣∣ dp(x, x′) ≤ r] (2)
A critical observation about definition 2 is that it not only relates to the previously defined notion of classifier astuteness, but also connects to the concept of probabilistic Lipschitzness. Probabilistic Lipschitzness captures the probability of a function being locally smooth given a radius r. It is specially useful for capturing a notion of smoothness of complicated neural network functions for which enforcing global and deterministic Lipschitzness is difficult. Mangal et al. (2020) formally defined probabilistic Lipchitzness as follows:
Definition 3. Probabilistic Lipschitz (Mangal et al., 2020): Given 0 ≤ α ≤ 1, r ≥ 0, a function f : X→ R is probabilistically Lipschitz with a constant L ≥ 0 if
Px,x′∼D(dp(f(x), f(x′)) ≤ L ∗ dp(x, x′) ∣∣∣ dp(x, x′) ≤ r) ≥ 1− α (3)
Notice the similarity between definitions 2 and 3. This very correspondence forms the basis of our motivation to explore the connection between the Lipschitzness of the black-box prediction function, and the astuteness of the explainer, which we explore theoretically in this section and experimentally in 4.

heading: 3.1 THEORETICAL BOUNDS OF ASTUTENESS
text: A cursory comparison between equation 2 and equation 3 hints at the two concepts being related to each other. In fact, explainer astuteness can be viewed as probabilistic Lipschitzness of the explainer when it is viewed as a function with a Lipschitz constant λ. However, a much more interesting question to explore is how the astuteness of explainers is connected to the Lipschitzness of the blackbox model they are trying to explain. We introduce and prove the following theorems which provide theoretical bounds that connect the Lipschitz constant L of the blackbox model to the astuteness of various explanation models including SHAP (Lundberg & Lee, 2017), RISE (Petsiuk et al., 2018), and methods that simulate individual feature removal such as CXPlain (Schwab & Karlen, 2019).

heading: 3.1.1 ASTUTENESS OF SHAP
text: SHAP (Lundberg & Lee, 2017) is one of the most popular feature attribution based explanation models in use today. Lundberg & Lee (2017) unify 6 existing explanation approaches within the SHAP framework. Each of these explanation approaches (including LIME, DeepLIFT, and kernelSHAP) can be viewed as approximations of SHAP, since SHAP in its theoretical form is difficult to calculate. However, in this section we use the theoretical definition of SHAP to establish bounds on astuteness.
For a given data point x ∈ X and a prediction function f the feature attribution provided by SHAP for the ith feature is given by:
φi(x) = ∑ z−i |z−i|!(d− |z−i| − 1)! d! [f(x z+i)− f(x z−i)] (4)
Theorem 1. (Astuteness of SHAP) For a given r ≥ 0 and 0 ≤ α ≤ 1, and a trained predictive function f that is probilistic Lipschitz with a constant L with probability at least 1− α at radius r. Then for SHAP explainers we have astuteness Ar,λ ≥ 1− α for λ ≥ 2 p √ dL.
Proof. Given input x and another input x′ s.t. d(x, x′) ≤ r. And letting |z−i|!(d−|z−i|−1)!d! = Cz . Using equation 4 we can write,
dp(φi(x), φi(x ′)) = dp( ∑ z−i Cz[f(x z+i)− f(x z−i)], ∑ z−i Cz[f(x ′ z+i)− f(x′ z−i)])
Using the fact that dp(x, y) = ||x− y||p where ||.||p is the p-norm, the right hand side gives us, dp(φi(x), φi(x ′)) = || ∑ z−i Cz[f(x z+i)−f(x z−i)]− ∑ z−i Cz[f(x ′ z+i)−f(x′ z−i)]||p
Combining the two sums and re-arranging,
dp(φi(x), φi(x ′)) = || ∑ z−i Cz[f(x z+i)− f(x z−i)− f(x′ z+i) + f(x′ z−i)]||p
= || ∑ z−i Cz[f(x z+i)− f(x′ z+i) + f(x′ z−i)− f(x z−i)]||p (5)
Using triangular inequality on the R.H.S twice,
dp(φi(x), φi(x ′)) ≤ || ∑ z−i Cz[f(x z+i)− f(x′ z+i)]||p + || ∑ z−i Cz[f(x ′ z−i)− f(x z−i)]||p
≤ ∑ z−i Cz||f(x z+i)− f(x′ z+i)||p + ∑ z−i Cz||f(x′ z−i)− f(x z−i)||p
(6)
We can replace each value inside the sums in equation 6 with the maximum value across either sums. Doing so would still preserve the inequality in equation 6, as the sum of n values is always less than the maximum among those summed n times. Without loss of generality let us assume this maximum is |f(x z∗+i)− f(x′ z∗+i)| for some particular z∗. This gives us:
dp(φi(x), φi(x ′)) ≤ ||f(x z∗+i)−f(x′ z∗+i)||p ∑ z−i Cz+||f(x z∗+i)−f(x′ z∗+i)||p ∑ z−i Cz (7)
However, ∑ z−i Cz = ∑ z−i |z−i|!(d−|z−i|−1)! d! = 1, which gives us,
dp(φi(x), φi(x ′)) ≤ 2||f(x z∗+i)− f(x′ z∗+i)||p = 2dp(f(x z∗+i), f(x′ z∗+i)) (8)
Using the fact that f is probabilistic Lipschitz with given some constant L ≥ 0, dp(x, x′) ≤ r and dp(x z∗+i, x′ z∗+i) ≤ dp(x, x′). From the definition of probablistic Lipschitz we get:
P [dp(f(x z∗+i), f(x′ z∗+i)) ≤ L ∗ dp(x, x′)] ≥ 1− α ⇒P [2dp(f(x z∗+i), f(x′ z∗+i)) ≤ 2L ∗ dp(x, x′)] ≥ 1− α
Since equation 8 establishes that dp(φi(x), φi(x′)) ≤ 2dp(f(x z∗+i), f(x′ z∗+i)), the below inequality can be now established:
P [dp(φi(x), φi(x ′)) ≤ 2L ∗ dp(x, x′)] ≥ 1− α (9)
Note that equation 9 is true for each feature i ∈ {1, ..., d}. To conclude our proof, we note that dp(φ(x), φ(x ′)) ≤ p √ d∗maxi dp(φi(x), φi(x′)) 1. Utilizing this in equation 9, assuming the i is the one corresponding to the maximum difference, gives us:
P [dp(φ(x), φ(x ′)) ≤ 2 p √ dL ∗ dp(x, x′)] ≥ 1− α (10)
Since P [dp(φ(x), φ(x′)) ≤ 2 p √ dL ∗ dp(x, x′)] in equation 10 defines Aλ,r for λ ≥ 2 p √ dL, this concludes the proof.
1dp(x, y) = p √∑d i ||xi − yi||p ≤ p √∑d i maxi ||xi − yi||p = p √ dmaxi dp(xi, yi)
Corollary 1.1. If the prediction function f is locally L−lipschitz at radius r then shapley explainers are λ−astute for radius r ≥ 0 for λ ≥ 2 p √ dL
Proof. Note that definition 3 reduces to the definition of deterministic lipschitz if α = 0. Which means equation 10 will be true with probability 1. Which concludes the proof.

heading: 3.1.2 ASTUTENESS OF RISE
text: RISE determines feature explanation for the ith feature by sampling subsets of features and then calculating the mean value of the prediction function when feature i is included in the subset. RISE feature attribution for a given point x and feature i for a prediction function f can be written as:
φi(x) = Ep(z|zi=1)[f(x z)] (11)
The following theorem establishes the bound on λ for explainer astuteness of RISE in relation to the Lipschitzness of blackbox prediction function. Theorem 2. (Astuteness of RISE) For a given r ≥ 0 and 0 ≤ α ≤ 1, and a trained predictive function f that is locally probabilistic lipschitz with a constant L with radius r and probability at least 1− α. Then for RISE explainer we have the astuteness Ar,λ ≥ 1− α, for λ ≥ p √ dL.
Proof. (Sketch, full proof in Appendix A)
Given input x and another input x′ s.t. d(x, x′) ≤ r, using equation 11 we can write
dp(φi(x), φi(x ′)) = dp(Ep(z|zi=1)[f(x z)],Ep(z|zi=1)[f(x ′ z)]) = ||Ep(z|zi=1)[f(x z)]− Ep(z|zi=1)[f(x
′ z)]||p = ||Ep(z|zi=1)[f(x z)− f(x ′ z)]||p (12)
Using Jensen’s inequality on R.H.S followed by the fact that E[f ] ≤ max f
dp(φi(x), φi(x ′)) ≤ max z dp(f(x z), f(x′ z)) (13)
Using the fact that f is probabilistic Lipschitz gives us and using dp(φ(x), φ(x′) ≤ p √ d ∗ maxi dp(φi(x), φi(x ′)) gives us,
P [dp(φ(x), φ(x ′) ≤ p √ dL ∗ dp(x, x′)] ≥ 1− α (14)
Since P [dp(φ(x), φ(x′) ≤ p √ dL ∗ dp(x, x′)] defines Aλ,r for λ ≥ p √ dL, this concludes the proof.
Corollary 2.1. If the prediction function f is locally L−Lipschitz at radius r ≥ 0, then RISE explanations are λ−astute for radius r and λ ≥ p √ dL
Proof. Same as proof for Corollary 1.1.

heading: 3.1.3 ASTUTENESS OF “REMOVE INDIVIDUAL” EXPLAINERS
text: Within the framework of feature removal explainers, a sub-category is the explainers that work by removing a single feature from the set of all features and calculating feature attributions based on change in prediction that result from removing that feature. This category includes Occlusion, CXPlain (Schwab & Karlen, 2019), PredDiff (Zintgraf et al., 2017) Permutation tests (Strobl et al., 2008), and feature ablation explainers (Lei et al., 2018).
Remove individual explainers determine feature explanations for the ith feature by calculating the difference in prediction with and without that feature included for a given point x. Let z−i ∈ 0, 1d represent a binary vector with zi = 0, then the explanation for feature i can be written as:
φ(xi) = f(x)− f(x z−i) (15)
Theorem 3. (Astuteness of Remove individual explainers) Consider a given r ≥ 0 and 0 ≤ α ≤ 1 and a trained predictive function f that is locally probabilistic Lipschitz with a constant L with radius r measured using dp(., .) induced by the p-norm and probability at least 1 − α. Then for Remove individual explainers, we have the astuteness Ar,λ ≥ 1− α, for λ ≥ 2 p √ dL, where d is the dimensionality of the data.
Proof. (Sketch, full proof in Appendix A) By considering another point x′ such that dp(x, x′) ≤ r and equation 15 we get,
dp(φ(xi), φ(x ′ i)) = dp(f(x)− f(x z−i), f(x′)− f(x′ z−i)) (16)
then following the exact same steps as the proof for Theorem 1 i.e. writing the right hand side in terms of p-norm, utilizing triangular inequality, and the definition of probabilistic Lipschitzness leads us to the desired result.
Corollary 3.1. If the prediction function f is locally L−Lipschitz at radius r ≥ 0, then remove individual explanations are λ−astute for radius r and λ ≥ 2 p √ dL.
Proof. Same as proof for Corollary 2.1.

heading: 3.2 IMPLICATIONS
text: The above theoretical results all provide the same critical implication, that is, explainer astutness is lower bounded by the Lipschitzness of the prediction function. This means that black-box classifiers that are locally smooth (have a small L at a given radius r) lend themselves to probabilistically more robust explanations. While there has already been work enforcing Lipschitzness on neural networks through regularization (Gouk et al., 2021), it has primarily been with the goal of improving performance. Our results provide motivation for the same except by showing that doing so will result in a higher lower bound on the astuteness of explanations on such Lipschitz controlled classifiers.

heading: 4 EXPERIMENTS
text: To demonstrate the validity of our experimental results, we perform a series of experiments on 7 datasets. We train four different classifiers on each of these datasets, and then explain the decisions of these classifiers using three explainer methods. The details are as follows:
Datasets. We use five simulated datasets based on datasets introduced by Chen et al. (2018). The first three, labelled XOR, Orange Skin(OS), and Nonlinear Additive(NA) are generated such that the ground truth predictions depend on the same features for all points. The last two labelled Switch and Switch++ are constructed such that the ground truth predictions depend on different features in different regions of the input space. More details about these datasets are provided in Appendix B.
In addition to the above simulated datasets, we also provide evaluations on two real datasets from the UCI Machine learning repository (Asuncion & Newman, 2007) for binary classification. Rice (Cinar & Koklu, 2019) consists of 3810 samples of rice grains of two different varieties (Cammeo and Osmancik). 7 morphological features are provided for each sample. Telescope (Ferenc et al., 2005) consists of 19000+ Monte-Carlo generated samples to simulate registration of high energy gamma particles in a ground-based atmospheric Cherenkov gamma telescope using the imaging technique. Each sample is labelled as either background or gamma signal and consists of 10 features.
Classifiers. For each dataset we train the following four classifiers; 2layer: A two-layer MLP with ReLU activations. For simulated datasets each layer has 200 neurons, while for the 2 real datasets we use 32 neurons in each layer. 4layer: A four-layer MLP with ReLU activations, with the same number of neurons per layer as 2layer. linear: A linear classifier constructed by removing the nonlinear activations from the 2layer classifier. svm: A support vector machine with Gaussian kernel.
The idea here is that each of these classifiers will have different probabilistically Lipschitz behavior, and that can be used to lower bound the explainer astuteness when explaining each of these classifiers according to our theoretical results.
Explainers. We evaluate 3 explainers here that are representative of the 3 theorems provided in SHAP (Lundberg & Lee, 2017) serves as Representative of Theorem 1. We use the gradient based
approximation for the neural-network classifiers and the kernel shap approximation for SVM. Both are included in the implementation provided by the authors2. RISE (Petsiuk et al., 2018)serves as representative method for Theorem 2. The official implementation provided by the authors is primarily for image datasets 3. We adapt this for tabular datasets. CXPlain (Schwab & Karlen, 2019) serves as representative method for Theorem 3. We use the official implementation provided by the authors 4.Section 3:

heading: 4.1 ESTIMATING PROBABILISTIC LIPSCHITZNESS AND LOWER BOUND FOR ASTUTENESS
text: To demonstrate the connection between explainer astuteness and probabilistic lipchitzness as alluded to by our theory we need to estimate probabilistic Lipschitzness for classifiers. In our experiments we achieve this by by empirically estimating the Px,x′ ∼ D (equation 3) for a range of values of L ∈ {0, 1} incremented at 0.1. We do this for each classifier and for each dataset D and set r as median of pairwise distance for all training points. According to equation 3 this gives us an upperbound on 1− α i.e. we can say that for a given L, r the classifier is Lipschitz with probability at least 1− α. We can use the estimates for probabilistic Lipschitzness to predict astuteness using our theorems. We do this by noting that our theorems imply that for λ ≥ CL √ d explainer astuteness is at least 1 − α. This means we can simply multiply the range of Lipschitz constant L with C √ d and for λ greater or equal to that value we can guarantee that explainer astuteness should be lower bounded by 1− α. This is how we arrive at the dashed lines in Figure 2.

heading: 4.2 RESULTS
text: The goal of our experiments is to empirically show that we can use the probabilistic Lipschitzness of classifiers to predict the lower bound for explainer astuteness. If we can plot astuteness lower bound predicted by our theory against observed astuteness for different values of epsilon and the observed astuteness curves are indeed shown to be lower bounded by the predicted astuteness curves, which are the desired result.
To this end, for each of the seven datasets we first train the four classifiers. We then measure the probabilistic Lipschitzness of each of these classifiers for each dataset. Afterwards we explain the predictions of these classifiers using each of the three explainer methods listed above. This results in 3 subplots for each dataset, one for each explainer, as shown in Figure 2, for Nonlinear Additive, Switch++, Rice and Telescope datasets. Plots for all datasets can be seen in Figure 3.
Each subplot in Figure 2 presents two types of curves, the dashed curves represent the predicted lower bound on explainer astuteness given a classifier, as described in Section 4.1. The solid curves are the actual estimations of explainer astuteness using Definition 2. According to our theoretical results, at a given λ the estimated explainer astuteness (solid curves) should stay above the predicted astuteness (dashed curves) based on the Lipschitzness of classifiers. As Figure 2 demonstrates, this is indeed the case. Notice that some deviations from this can be expected since the theoretical results assume the ideal scenario for each of the methods and assume that the probabilities can be computed exactly. In practice e.g. while our theorems use the theoretical definition of SHAP, the implementation uses a Gradient Explainer approximation provided by Lundberg & Lee (2017). Similarly, all probabilities are calculated using empirical estimates using the available training points. Table 1 presents the results in tabular form for all datasets. It shows the difference between the AUC under the estimated astuteness curves (AUC) and the AUC under the predicted lower bound (AUClb). This number captures the average tightness of the lowerbound over a range of λ values. This number should be non-negative, which we observe it is, except in one case where it’s a small negative value due to estimation errors. We also observe that given at least some of the values in this table are not close to 0 our proposed lower bound can be improved upon in the future to make it tighter.

heading: 4.3 CONCLUSION AND FUTURE WORK
text: In this paper we formally defined explainer astuteness which captures the probability that a given explainer will assign similar explanations to similar points. We theoretically prove that this explainer astuteness is proportional to the probabilistic Lipschitzness of the black-box function that is being
2https://github.com/slundberg/shap 3https://github.com/eclique/RISE 4https://github.com/d909b/cxplain
explained. As probabilistic Lipschitzness captures local smoothness properties of a function, this result suggests that enforcing smoothness on black-box models can lend these models to more robust explanations. By way of future work we observe that our experimental results suggest that our predicted lower bound can be tightened further. We intend to pursue this in future research.

heading: A DETAILED PROOFS
text: We include the detailed proofs for Theorems 2 and 3 here.
Proof. (For Theorem 2)
Given input x and another input x′ s.t. d(x, x′) ≤ r, using equation 11 we can write
dp(φi(x), φi(x ′)) = dp(Ep(z|zi=1)[f(x z)],Ep(z|zi = 1)[f(x ′ z)]) = ||Ep(z|zi=1)[f(x z)]− Ep(z|zi = 1)[f(x
′ z)]||p = ||Ep(z|zi=1)[f(x z)− f(x ′ z)]||p (17)
Using Jensen’s inequality on R.H.S,
dp(φi(x), φi(x ′)) ≤ Ep(z|zi=1)[||f(x z)− f(x ′ z)||p] (18)
Using the fact that E[f ] ≤ max f ,
dp(φi(x), φi(x ′)) ≤ max z ||f(x z)− f(x′ z)||p
= max z dp(f(x z), f(x′ z))
(19)
Using the fact that f is probabilistic Lipschitz with some constant L ≥ 0, and dp(x z, x′ z) ≤ dp(x, x ′),∀z. Then using the definition of probabilistic Lipschitz we get,
P (max z dp(f(x z), f(x′ z)) ≤ L ∗ d(x, x′) ≥ 1− α (20)
Using this in equation 19 gives us,
P [dp(φi(x), φi(x ′)) ≤ L ∗ d(x, x′)] ≥ 1− α (21)
Note that equation 21 is true for each feature i ∈ {1, ..., d}. To conclude the proof note that dp(φ(x), φ(x ′) ≤ p √ d ∗maxi dp(φi(x), φi(x′)). Utilizing this with equation 21 leads us to
P [dp(φ(x), φ(x ′) ≤ p √ dL ∗ dp(x, x′)] ≥ 1− α (22)
Since P [dp(φ(x), φ(x′) ≤ p √ dL ∗ dp(x, x′)] defines Aλ,r for λ ≥ p √ dL, this concludes the proof.
Proof. (For Theorem 3)
By considering another point x′ such that dp(x, x′) ≤ r and equation 15 we get,
dp(φ(xi), φ(x ′ i)) = dp(f(x)− f(x z−i), f(x′)− f(x′ z−i)) (23)
using the fact that dp(x, y) = ||x− y||p where ||.||p is the p-norm, the RHS gives us,
dp(φi(x), φi(x ′)) = ||f(x)− f(x z−i)− f(x′) + f(x′ z−i)||p (24)
using triangular inequality,
dp(φi(x), φi(x ′)) ≤ ||f(x)− f(x′)||p + ||f(x′ z−i)− f(x z−i)||p (25)
w.l.o.g assuming the first term on the right is bigger than the second term
dp(φi(x), φi(x ′)) ≤ 2||f(x)− f(x′)||p = 2dp(f(x), f(x′)) (26)
using the fact that f is probabilistic Lipschitz get us,
P [dp(φi(x), φi(x ′)) ≤ 2Ldp(x, x′)] ≥ 1− α (27)
to conclude the proof note that dp(φ(x), φ(x′)) ≤ p √ d ∗maxi dp(φi(x), φi(x′)), which gives us,
P [dp(φ(x), φ(x ′)) ≤ 2 p √ dL ∗ dp(x, x′)] ≥ 1− α (28)

heading: B DATASET DETAILS
text: • XOR: A dataset with 2 classes. The input data is generated from a 10-dimensional standard Gaussian distribution. The class probabilities are generated proportional to exp{X1X2}. That is only the first two features are important in generating predictions for all data points.
• Orange-skin: The input data is again generated from a 10-dimensional standard Gaussian distribution. The ground truth class probabilities are proportional to exp{ ∑4 i=1X 2 i − 4}.
In this case the first 4 features are important globally for all data points. • Nonlinear-additive: Similar to Orange-skin dataset except the ground trugh class proba-
bilities are proportional to exp{−100 sin 2X1 +2|X2|+X3 +exp{−X4}}, and therefore each of the 4 important features for prediction are nonlinearly related to the prediction itself.
• Switch: This simulated dataset is specifically for instancewise feature explanations. For the input data feature X1 is generated by a mixture of Gaussian distributions centered at ±3. If X1 is generated from the Gaussian distribution centered at +3, X2 to X5 are used to generate the prediction probabilities according to the Orange skin model. Otherwise X6 to X9 are used to generate the prediction probabilities according to the Nonlinear-additive model.
• Switch++: This is a modified version of the Switch dataset where instead of two classes there are 4 classes with varying weights.

heading: C ADDITIONAL RESULTS
text: Table 2 shows the normalized AUC for the estimated explainer astuteness and the predicted AUC based on the predicted lower bound curve. As expected the predicted AUC lower bounds the estimated AUC.
Figure 3 shows the same plots as shown in Figure 2 but includes all datasets.
15

Review summaries:
In this study, a metric called Astuteness is introduced as a criterion to evaluate the reliability of explanations. Intuitively, if the distance between explanations given for two samples that are within a certain distance is also within a certain distance, then the explanation has astuteness. This definition can be interpreted as defining the robustness of an explanation. More specifically, it relates the distance in the sample space to the distance in the explanation space by probabilistic Lipschitzness. In this study, the authors show that for some certain classes of explanatory methods, such as SHAP and CXplain, the probabilistic lower bound of the astuteness of an explanation depends on the square root of the number of feature dimensions D and the Lipschitz constant L. The reliability of this probabilistic lower bound is also evaluated experimentally with several datasets.

This paper studies the problem of robustness of local explanations of a classifier at some input x. Explanations can be generated by several methods: Shapley-value-based, mean-effect-based, and removal-based. Since the explanation methods use the output of the classifier f, the change in the explanations can be related to the change in the output of f, and the latter is quantified by the Lipschitz constant of f. Lower bounds of \epsilon that bounds the change in the explanation in "explanation astuteness" is proved for three example explanation methods. This gives the "best-case" robustness in the explanations given perturbation in the input x. Experiments on 7 datasets evaluated the tightness of a low-bound of "explanation astuteness", which is the probability that two close inputs x and x' have their explanations \phi(x) and \phi(x') differ by no more than some upper-bound related to d(x,x').

The paper focuses on the reliability of explainers, where an explainer should give similar explanations for similar data inputs. To this end, the authors introduce and define "explainer astuteness", which leverages the concept of "probabilistic Lipschitzness" (the probability of local smoothness of a predictor/classifier function). The paper explores the reliability of different types of explainers by analyzing the connection between the robustness of explanation methods and the smoothness of the black-box predictor function they are trying to explain. Finally, the authors provide a theoretical way to connect the explainer astuteness to the probabilistic Lipschitzness of the black-box function and explore how the smoothness of the black-box function impacts an explainers' astuteness.