Locally Invariant Explanations: Towards Stable and Unidirectional Explanations through Local Invariant Learning
Authors: Amit Dhurandhar
Karthikeyan Natesan Ramamurthy
Kartik Ahuja
Vijay Arya
Venue: NeurIPS 2023 poster (2023)
Keywords: Explainable AI
Game theory
Invariance
TL;DR: We provide a new local explanation method that is unidirectional and stable

Abstract: Locally interpretable model agnostic explanations (LIME) method is one of the most popular methods used to explain black-box models at a per example level. Although many variants have been proposed, few provide a simple way to produce high fidelity explanations that are also stable and intuitive. In this work, we provide a novel perspective by proposing a model agnostic local explanation method inspired by the invariant risk minimization (IRM) principle -- originally proposed for (global) out-of-distribution generalization -- to provide such high fidelity explanations that are also stable and unidirectional across nearby examples. Our method is based on a game theoretic formulation where we theoretically show that our approach has a strong tendency to eliminate features where the gradient of the black-box function abruptly changes sign in the locality of the example we want to explain, while in other cases it is more careful and will choose a more conservative (feature) attribution, a behavior which can be highly desirable for recourse. Empirically, we show on tabular, image and text data that the quality of our explanations with neighborhoods formed using random perturbations are much better than LIME and in some cases even comparable to other methods that use realistic neighbors sampled from the data manifold. This is desirable given that learning a manifold to either create realistic neighbors or to project explanations is typically expensive or may even be impossible. Moreover, our algorithm is simple and efficient to train, and can ascertain stable input features for local decisions of a black-box without access to side information such as a (partial) causal graph as has been seen in some recent works.

Locally Invariant Explanations: Towards Stable and Unidirectional Explanations through Local Invariant Learning
Amit Dhurandhar'
Karthikeyan Natesan Ramamurthy"
IBM Research
IBM Research
Yorktown Heights, USA
Yorktown Heights, USA knatesa@us ibm. com
adhurandus.. 1bm. com
Kartik Ahuja Mila Montreal, Canada
Vijay Arya IBM Research Bangalore, India vijay.aryaae arya@in. ibm. com
kartik. ahuj a@mila quebec
Abstract
Locally interpretable model agnostic explanations (LIME) method is one of the most popular methods used explain black-box models at per example level. Although many variants have been proposed, few provide simple way to produce high fidelity explanations that are also stable and intuitive. In this work, we provide a novel perspective by proposing model agnostic local explanation method inspired by the invariant risk minimization (IRM) principle originally proposed for (global) diitrr--dittiittiion generalization to provide such high fidelity explanations that are also stable and unidirectional across nearby examples. Our method is based game theoretic formulation where we theoretically show that our approach has strong tendency to eliminate features where the gradient of the black-box function abruptly changes sign in the locality of the example we want to explain, while in other cases it is more careful and will choose a more conservative (feature) attribution, a behavior which can be highly desirable for recourse. Empirically, we show on tabular, image and text data that the quality explanations with neighborhoods formed using random perturbations are much better than LIME and in some cases even comparable to other methods that use realistic neighbors sampled from the data manifold. This is desirable given that learning a manifold to either create realistic neighbors or to project explanations is typically expensive may even be impossible. Moreover, our algorithm simple and efficient to train, and can ascertain stable input features for local decisions of a black-box without access to side information such as a (partial) causal graph has been seen in some recent works.
1 Introduction
Deployment and usage of neural black-box models has significantly grown in industry over the last
few years creating the need for tools to help users understand and trust models (24. Even well- studied application domains such as image recognition require some form of prediction understanding
in order for the user incorporate the model into important decisions [46] 33). An example of
this could be doctor who is advised by model of a positive cancer diagnosis based on an image
Equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

scan. Since the doctor holds responsibility for the final diagnosis, the model must provide sufficient reason for its prediction. Even new text categorization tasks (2T are becoming important with the growing need for social media companies to provide better monitoring of public content. Twitter was monitoring tweets related to COVID-19 in order to label tweets containing misleading information, disputed claims, or unverified claims 42 Laws will likely emerge requiring explanations for why red flags were or were not raised in many examples. In fact, the General Data Protection and Regulation (GDPR) [5]] act passed in Europe already requires automated systems that make decisions affecting humans to be able to explain them. Given this acute need, a number of methods have been proposed
to explain local decisions (i.e. example specific decisions) of classifiers [41 35 46
33 B
Locally
interpretable -agnos-ai explanations (LIME) is arguably the most well-known local explanation method that requires only query (or black-box) access to the model. Although LIME is a popular method, it is known to be sensitive to certain design choices such as i) (random) sampling to create the (perturbation) neighborhood ii) the size of this neighborhood (number of samples) and iii) (local) fitting procedure to learn the explanation model [37 (4). The first, most serious issue could lead to nearby examples having drastically different explanations making effective recourse challenge. One possible mitigation is to increase the neighborhood size but one cannot arbitrarily do so as it not only leads to higher computational cost, but also in today's cloud computing-drive world it could have direct monetary implications where every query to black-box model has an associated cost There have been variants suggested to overcome these 39 [5] primarily through mechanisms that create realistic neighborhoods or through adversarial training [2), however, their efficacy is restricted to certain settings and modalities based on their assumptions and training strategies.
Confficient inconsistancy for LIME
limitations 8 45
4.5
3aa2 Baaii (cm)
8.0
3.0
2.5
In this paper we introduce a new method called Locally INvariant EXplanations (LINEX) inspired by the invari- ant risk minimization (IRM) principle 77]. that produces explanations in the form of feature attributions that are robust neighborhood sampling and can recover faithful (i.c. mimic -lxck-box behavior), stable (i.e. similar for closeby examples) and unidirectional (i.e. same sign attri- butions a.a.a feature importances) for closeby examples, see section 4.1 explanations across tabular, image, and text modalities. In particular, we show that our method performs better than the competitors for random as well as realistic neighborhood generation, where in some cases even with the prior strategy our explanation quality is close to methods that employ the latter. Qualitatively, our method highlights (local) features as important that in the particular locality i) have consistently high gradient with respect to (w.r.t)) the black-box function and ii) where the gradient does not change significantly, especially in sign. Such stable behavior for LINEX is visualized in Figure [] where we get similar explanations for nearby examples in the IRIS dataset. The (in)fidelity of LINEX is still similar to LIME (see Table 2), but of course our explanations are much more stable.
2.0
4.5
5.0
5.5
6.0
0.5
7.0
7.5
0.0
sepal longth (cm)
Conffident inconsistency LINEX
4.5
aggalln0 widd (cm)
4.0
3.5
sepal
2.5
2.0
4.5
8.0
(cm)
Figure 1: Above we visualize for the IRIS dataset the Coefficient Inconsis- tency (CI) (see Section 5 for exact def- inition and setup details) between the explanation (top two features) for an ex- ample and its nearest neighbor in the dataset. Each circle denotes an exam- ple and rainhow colormap depicts the degree of inconsistency w.r.t. its nearest neighbor where red implies least incon- sistency, while violet implies the most. As can be seen LINEX explanations are much more consistent than LIME's.
2 Related Work
Posthoc explanations can typically be partitioned into two broad categories global and local. Global explainability avers to trying to understand a black-box model at a holistic level where the typical tact is knowledge transfer (28 17 [6) where (soft/hard) labels of the black-box model are used to train an interpretable model such as a decision tree or rule list [43 Local explanations on the other hand avers to understanding individual decisions. These explanations are typically in two
By perturbation neighborhood or simply neighborhood, we mean neighborhoods generated for local explanations. By exemplar neighborhood, mean closest in dataset examples.

---

forms, either exemplar based or feature based. For exemplar based as the name suggests similar but diverse examples
25 are provided as explanations for the input in question. While for feature which is the focus of this work, important features are returned as being important for the decision made for the input. There are some methods that do both [39]. Moreover, there are methods which provide explanations that are local, global as well as at group level [40]. All of these methods though may not still provide stable and robust local feature based explanations which can be desirable in practice (23)
30
based 41 35
13
33
55
Given this there have been more recent works that try to learn either robust or even causal explanations. In [32) the authors try to learn robust and stable local explanations relative to distribution shifts and adversarial attacks. However, the distribution shifts they consider are linear shifts and adversarial training is performed which can be slow and sometimes unstable [53]. Moreover, the method seems to be applicable primarily to tabular data, There are also works [8 19] which try to robustify gradient based explanations assuming white box access to the model. Works on causal explanations mainly modify SHAP and assume access a partial causal graph. Some others 488 assume white-box access. In this work we do not assume availability of such additional information. There are also works which show that creating realistic neighborhoods by learning the data manifold for
22 27
LIME [8 45] can lead to better quality explanations, where in particular work [6] it is suggested that projecting explanations themselves on to the manifold can also make them more robust. The need for stability in exemplar neighborhood for LIME like methods has been highlighted in (54), with the general desire for stable explanations being also expressed in [52] 49). Furthermore, it was recently surmised through expert and crowd worker user studies that stability is key factor when it comes to assessing capability of a model or when learning a new domain 34
Given that our approach is inspired from IRM we now describe, how it is novel w.r.t. to it. It is important to realize that IRM approaches such as 3 4 are designed for the out-of-distribution (OOD) generalization, which learn global models directly from the data. The main similarity of these works to ours is only that they also are game theory based approaches, but with the details being quite different. For one, they assume accessibility to environments which (ideally) correspond to different interventional distributions and with assumptions on the structural causal model derive results on how the true causal factors could be divulged. In our case, we propose ways generate environments as they are not given, and have I and 1x constraints on the entire and environment specific parts of the model respectively, which is not the case with these prior works. As such those algorithms do not produce sparse unidirectional models that are also consumable. Moreover, the perspective we provide is novel in the context of local posthoc explanations where priori it is not obvious that approaches from OOD generalization could be extended and adapted. Additionally, we propose a novel metric Unidirectionality which is not part of any of these works, but as have argued it is desirable property for explanations.
Preliminaries
Invariant Risk Minimization: Given a collection of training datasets D (De)eee. gathered from a set of environments E,,, where De = {a Je is the dataset gathered from environment Ee, and ne is the number of points in environment e. The feature value for data point is at X and the corresponding label is y² E y. where X C Rd and y C RR Each point (æt v in environment is drawn i.i.d from a distribution Pe. Define predictor f X I.
The goal of IRM is to use these collection of datasets D construct predictor f that performs well across many unseen environments Eall, where Eall 2 Ey,. Define the risk achieved by f in environment e as (f) = E._ (Xx),, Ya)]. where & is the square loss when f(X.) ) is the predicted value and Y. is the corresponding label, (Xe, Ye) P. and the expectation E, is defined w.r.t. the distribution of points in environment e.
An invariant predictor is composed of two parts representation & E Rd and predictor (with the constant term) w E dx We say that a data representation & elicits an invariant predictor w" T & across the set of environments E,r if there is predictor w that achieves the minimum risk for all the environments w E argmin Re (w (T)) Ve E Et.. IRM may be phrased as the following constrained optimization problem (
min t BeRKn R
Σ RRow 4) s.t. w E argmin Re (wTT), Ve E Eor wER4x1
(I)
eEE.r
3

---

If w T solves the above, then it is an invariant predictor across the training environments Etr-
Nash Equilibrium (NE): To understand how certain key aspects of our method function let us revisit the notion of Nash Equilibrium [00] A standard normal form game is written as a tuple W takes actions from strategy set S, The utility of player i is u, S + R, where we write the joint set of actions of all the players as S St The joint strategy of all the players is given as 8 E S, the strategy of player i is 8; and the strategy of the rest of players is 8-4 (8/))
Ω = (N,, { JeN, (eA),)) where /V is finite set of players. Player
Definition 1. A strategy st is said be a pure strategy Nash equilibrium (NE) if it satisfies, u. (s L1,) 2 u. (k; s),), Ak E S Vi E N, where u,(s), s = (s 8/ s/)) u,(s)).
NE thus identifies a state where each player is using the best possible strategy in response to the rest of the players leaving no incentive for any player to alter their strategy. seminal work by [1]] was shown that for special class of games called concave games such pure NE always exists. This relevant because the game implied by Algorithm falls in this category.
Methodology
We first define desirable properties for our explanation methods. The first three have been seen in previous works, while the last Unidirectionality is new. We then describe our method where the goal explain black-box model f X - R for individual inputs 2 based predictors by looking at their corresponding components, also termed as feature attributions.
We take inspiration from IRM since, our goal here too is to extract robust features that are ideally stable and unidirectional. The main difference that we do not learn a new (possibly invariant) representation since, we desire interpretability and this new representation may not be interpretable. We hence, are restricted to the provided input or some other interpretable representation. Thus, given that & S X' where n = 1 (since local explanations) in our setup, goal is to find the best predictor w (viz. high fidelity) for an input that will eliminate or at least mitigate the effect of unstable features. In other words, importance (i.e. are invariant) in the neighborhood of the example we want to explain. Our approach as we will see is similar in spirit to IRM games [4], where adopt game theoretic strategy to obtain such explanations. The differences with IRM games are mentioned in the last paragraph of Section 2
want to identify features in the input space that will (roughly) have the same
4.1 Desirable Properties
We now discuss certain properties we would like our explainability method to have in order to provide robust explanations that could potentially be used for recourse. Let D, denote (test) dataset with examples (z, y) where (0(x) is the black-box models prediction on and ye (x) is the prediction on x (E X) using the explanation model at x'. The feature attributions (or coefficients) for the explanation model at denoted by c .N denotes the exemplar neighborhood of with |-leard denoting cardinality and |.| denoting absolute value.
Fidelity: This is the most standard property which all proxy model based explanation methods are evaluated against [41 35 32] as it measures how well the proxy model simulates the behavior the black-box (i.e. faithfulness to the black box) it is attempting to explain. Here we define inverse of it, that is Infidelity (INFD), as the MAE between the black-box and explanation model predictions across all the test points:
INFD
Σ (Z.0)ED.
yb (x) - vo (x)
De (eard
We also define another metric here called Generalized Infideiity (GI), which also been used in previous works [40] to measure the generalizability of local explanations to neighboring test points. It is defined as:
Gl
e'eN. lvo(x) vee (z:)--
(3)
De leard
W leard
(z,g)eD,

---

Stability: This is also popular notion [26] 40 52] to evaluate robustness of explanations. Largely. stability can be measured at three levels. One is prediction stability, which measures how much the predictions of an explanation model change for the same example subject to different randomizations within the method or across close by examples. The second is the variance the feature attributions again for the same or close by examples. It is good for method to showcase stability w.r.t. both even though in many cases the latter might imply the former. An interesting third notion of stability is the correlation between the feature attributions of explanation model and average feature values of examples belonging to a particular class. This measures how much does the explanation method pick features that important for the class, rather than spurious ones that seem important for just the example. We thus define two stability metrics.
Coefficient Inconsistency (CI): This notion has been used before 226 to measure explanation methods robustness. It can be defined as the MAE between the attributions of the test points and their respective neighbors:
CI Deleard (x.y)ED,
Σ - ''EN
(4)
N card
Class- Attribbttiittn Consistency (CAC): For local explanations of classification black-boxes, expect certain important features to be highlighted across most of the explanations of a class. This is codified by this metric which is defined as follows:
1
CAC
Σ yEV
Er(u My),
(5)
[V/eard
where y denotes the set of class labels in the dataset, My the mean (vector) of all inputs in class E V. pd the mean explanation for class and the Pearson's correlation coefficient. This metric quantifies the consistency between the important features for a class and attributions provided by the explanations.
This is the same implementation invariance defined in 47 Essentially, if two models have exactly the same behavior on all inputs then their explanations should also be the same. Since, our method is model agnostic with only query access to the model it is easy see that it satisfies this property if the same environments are created.
Black-box Invariance:
Unidirectionality. This is new property, but argue that this is natural one have. Loosely speaking, unidirectionality would measure how consistently the sign of the predictor for a feature is maintained for the same close by examples by explanation method. This is natural metric 36). which from an algorithmic recourse [29] perspective is also highly desirable. For instance, recommending a person increase their salary get loan and then recommending another person with a very similar profile to decrease their salary for the same outcome makes little sense.
We define the unidirectionality T as measure of how consistent the sign of the attribution for particular feature in a local explanation when varying neighborhoods for the same example or when considering different close by examples. As such, given m attributions for each of d features
(1) denoted by w :... (d) the metric for an example is:
sgn W (
T md
where |.| stands for absolute value. Clearly, the more consistent the signs for the attribution of particular feature across m attributions the higher the value, where the maximum value can be one. If equal number of attributions have different signs for all features then Y will be zero, the lowest possible value. This property thus measures how intuitively consistent (ignoring magnitude) the explanations are. Given its sole focus on the sign of the attributions it compliments the above metrics along with attributional robustness metrics g 44).
4.2 Method
4.2.1 Description
In Algorithm I we show the steps of our method LINEX. The input the example we want to explain æ, the black-box predictor, a few thresholds that we describe next and & (local) environments
5

---

Algorithm 1: Locally Invariant EXplanations (LINEX).
Input: example æ, black- predictor f(),, number of environments to be created (1aa)
threshold y > 0, (11) threshold & > 0 and convergence threshold c >> 0
Initialize: Vi {1,... k} w and A
Let (1)),.... (.) be k environment creation functions as described in section 4.2.2
do
A =0 for to k: do u _ b3# w wirev w
W, argmin (x) (f(Ø) w. w wTx) s.t. l + 20/ S and | S y
A max (/20, prev
wi A)
end A
while
2 E:
Output: w EiE(I W
whose creation is described in Section 4.2.2 4.2.2 In the algorithm we iteratively learn constrained least squares predictor for each environment, where the final (local) linear predictor is the sum of these individual predictors. In each iteration when computing the contribution of environment 6 to the final summed predictor, the most recent contributions of the other predictors are summed and the residual is optimized subject to the constraints. The first constraint is standard lasso type constraint which tries to keep the final predictor sparse as in LIME.
Why To constraint? The second constraint is more unique and is a lac constraint the predictor of just the current environment. This constraint as we prove in Section 4.3] is essential for obtaining robust predictors. To intuitively understand why this the case consider we have two environments. In this case if the optimal predictors for a feature in each environment have opposite signs, then the Nash equilibrium (NE) is when each predictor takes +7 or -? values as they try force the sum to have the same sign as them. In other words, features that have a disagreement in even the direction of their impact are eliminated by our method. LIME type methods on the other hand would simply choose some form of average value of the predictors which may be a risky choice especially for actionability/recourss given that the directions change so abruptly. On the other hand, the optimal predictors for feature in the two environments have the same sign, the lower absolute valued predictor would be chosen (assuming 7 is greater) making a careful choice. The reasoning for this and discussion involving more than two environments is given in Section 4.3
The overall algorithm resembles a (simultaneous) game where each environment a player trying to find the best predictor for its environment given all other predictors and constraints. Formally, for i [1, ...,..., }} the players are A {E.), their strategy space S, = [- 7 and their utility us (w0, w.) = Ees(((e) (()) - wt a u x
The optimization problem solved by each
player is convex as norms are convex.
4.2.2 Creating Local Environments
In standard IRM, environments are assumed to he given. In our case of local explainability we have decide how to produce them. We offer few options for the environment creation functions & vifl...., }} in Algorithm
This simple approach is similar to what LIME employs. We could perturb the input example by adding zero mean gaussian noise to create the base environment (used by LIME) and then perform bootstrap sampling create the i different environments. This will efficiently create neighbors in each environment, although they may be unrealistic in the sense that they could correspond to low probability points w.r.t. the underlying distribution.
Random Perturbation:
Realistic Generation/SSlection One could also create neighbors using data generators such as done in McLIME (8) or select neighboring examples from the training set as done in MAPLE 39 to create

---

the base environment following which bootstrap sampling could be done to form the k different environments. This could provide more realistic neighbors than the previous one, but may be much more computationally expensive. Other than bootstrapping one could also oversample and try to find the optimal hard/soft partition through various clustering type objectives 2 10
4.3 Theoretical Results
In this section, we analyze the output of Algorithm 1 with two environments. The extension to multiple environments discussed following this result, where the general intuition is still maintained but some special cases arise depending on whether there are an even or odd number of environments. To prove our main result we make two assumptions.
Assumption The features of the samples in the local environments are independent.
This assumption is satisfied by the most standard way of creating neighbothoodkeevinonment, where gaussian noise is used to create them as described Section 4.2.2
Assumption 2 t 2 yd, where d is the dimensionality of the feature vector:
Making this Here is the parameter in the & penalty and 7 in the foo as noted in Algorithm |
assumption ensures that we closely analyze the role the fo penalty, which is one of our main novelties.
Definition 2 Let the explanation that each environment & arrives at for an example based on unconstrained least squares minimization be wi where,
W
E argmin Ezec, (xr) ((f(z)) i x
wERd
The expectation is taken w.r.t the environment generation distribution.
Theorem 1. The output of Algorithm 7 under Assumptions 1, 2 and equation 7
is given by:
w
w
10 + = @ 1 [19]1>/101]
Lufow;20
(8)
where O is element wise product and 1 is the indicator function..
Sketch. Sketch. The above expression describes the NE of the game played between the two local environments each trying to move w towards their least squares optimal solution. Given assumptions 1 and we witness the following behavior of our method. Let the ith feature of the predictors új and Wh from [lgorithm[] be Wi: and W2; respectively. Let the corresponding least squares optimal predictors for the ith feature have the following relation: wi: > wi; and | > |w5zl- Then the two environments will push the ensemble predictor, Wn. + W2.. in opposite directions during their turns, with the first environment increasing its weight, W1s, and the second environment decreasing its weight, Wyg. Eventually, the environment with a higher absolute value (51 1 since [w > reaches the boundary (w0, = 7) and cannot move any further due to the Lac constraint. The other environment & best responds, where either hits the other end of the boundary (1i2; -7), in which case the weight of the ensemble for component i is zero, a case which occurs if w", and wi; have opposite signs; or gets close the other boundary while staying in the interior (w w05, 7), in which case the weight of the ensemble for feature i is wazs a situation which occurs if wf, and wiz have the same sign.
[ I)
Implications of the Theorem 1: The following are the main takeaways from Theorem I (1) If the signs of the explanations for unconstrained least squares for the two environments differ for some feature, then the algorithm outputs zero for that feature attribution. (2) If the signs of the explanations for the two environments are the same, then the algorithm outputs the lesser magnitude of the two. These two properties are highly desirable from an algorithmic recourse or actionability perspective, where the first biases us to not rely on features where the black-box function changes direction rapidly (unidirectionality). The second, provides reserved estimate so that we do not incorrectly over rely on the particular feature (stability). Based on similar logic presented in the proof sketch the behavior for more than two environments for LINEX is discussed in Suppl. C.

---

(4a) MeLIME> 0292 (4b) LINEX 0.633
(4c) Original
(d) M
(e) LINEX:r 0.962
(1) Original
13
30-
Figure 2: Sample results using FMNIST dataset for two classes. (a-c): Class Dress, (d-f): Class Sandal. (a, d): McLIME explanations. (b, d): LINEX explanations. (c, f): Original images. We observe that LINEX explanations capture important artifacts and thus exhibit significantly higher correlation with the original images for the same level of sparsity, where aggregate too the correlations high w.r.t. images belonging to particular class, thus showcasing higher stability (i.e. high CAC) as is seen in Table 2 More examples are shown in Suppl. G.
Table I: Below are three example positive sentiment sentences from the Rotten Tomatoes dataset. Green and red indicate the most important word highlighted by MeLIME and LINEX respectively. As seen LINEX highlights stronger positive sentiment words. More examples in Suppl. F.
Example
Example 2
Example
moving tale love destruction unexpected places, unexamined lives spare yet audacious...
one-of-a-kind near-masterpiece
Experiments
We test our method on five real world datasets covering all three modalities: IRIS (Tabular) [2]
Medical Expenditure Panel Survey (Tabular) [1], Fashion MNIST (Image) [50, CIFARIO (Image) 31 and Rotten Tomatoes reviews (Text) [38] with LIME-like random (rand) and MeLIME-like realistic neighborhood generation (real) or MAPLE-like realistic neighborhood selection (mpl). The summary of black-box classifier accuracies, and type of realistic perturbation used for the datasets provided in Table 3 in the Supplement. In other cases except FMNIST and CIFARIO which come with their own test partition we randomly split the datasets into 80/20% train/test partition and average this test partition. For LINEX produce environments
results for the local explanations where the two environments are formed by performing bootstrap sampling on the base environment which is created either by rand, real mpl type neighborhood generation. Thus in all cases the union of the environments is the same as a single neighborhood used to produce explanations for the competitors making it fair comparison. Behavior with more environments is in Suppl. E.
Given the neighborhood generation schemes we compare LINEX with LIME, Smoothed LIME (S-LIME), McLIME and MAPLE, where for S-LIME of LIME across the LINEX environments. SHAP's results are in Suppl. H, since it is not natural fit here. Nor are methods such as saliency maps, gradcam, inte- grated gradients as they are white-box methods requiring access to a differentiable model.
average the explanations
Metrics: We evaluate using five sim- ple metrics: Infidelity (INFD), Gen- eralized Infidelity (GI), Coefficient Inconsistency (CI), Class Attribution Consistency (CAC) and Unidirection- ality (T), which are defined in section 4.1 The first two evaluate faithful- ness, the next two stability and the last goodness for recourse.
Original
LINEX
MeLIME
Original
LINEX
MeLIME
64
02
Figure 3: Sample results using CIFAR1O dataset for dog and bird class. As can be seen LINEX focuses more on salient features such as head and legs for the dog, and wings for the bird (rather than also the background). More examples are shown in Suppl. G.
We the above metrics in Table Each result Table is mean + stan-
dard error of the mean over five kernel sizes r generally, where {0.05, 0.1. 0.25, 0.5, 0.75). Test neighborhoods do not make sense for random perturbations with FMNIST, CIFAR and Rotten Tomatoes because the features (viz. superpixels) used by neighboring test examples are different.
8

---

Table 2: Comparison of the different methods based on infidelity (INFD), generalized infidelity (GI), coefficient inconsistency (CI), class attribution consistency (CAC) and unidirectionality (T). indicates higher value for the metric better, and 4. indicates lower better. Statistically significant results based on paired t-test are bolded. LINEX is better than baselines in 21 out of 40 cases, and worse only in cases. Plots showing behavior with varying neighborhood size, number of environments and kernel width are in Suppl. E.
Dataset
Method
INED І
G
C
Y1
CAC
LIME
0.015 + 0.011
0.132 + 0.042
+.319:0.133
0.646 0.000
0.667 0.167
S-LIME
0.015 0.010
0.077 : 0.011
0
1.704
0
LINEX/rand
1.013
0.052 : 0.008
0.044
0.802
0.042
IRIS
MeLIME
0.008 1 0.003
0.049 0.001
0.219:0.100
0.629:000113
0,464 0.100
LINEX/real
0.009 0.003
0.029 0.003
0.024 0.744 0.002
0.942
0.023
MAPLE
0.009
0.038 0.004
0.261 0.033
0.458 0.032
0.586
0.035
LINEX/mpl
0.013 0.000
0.020 + 0.000
0.026 + 0.002
0.694 + 0.008
0.929 0.004
LIME
0.158 0.066
0.214 + 0.001
0.005 + 0.00T
0.981 0.006
S-LIME
0.158 + 0.066
0.214 + 0.012
0.005 + 0.001
0.974 + 0.008
NA
MEPS
LINEX/rand
0.130 + 0.052
0.164 + 0.021
0.003 + 0.001
0.979 + 0.006
MAPLE
0.063 1 0.000
0.067 1 0.000
0.007 = 0.000
0.957 = 0.000
NA
LINEX/mpl
0.098 0.001
0.094 + 0.001
0.007 = 0.000
0.950 = 0.000
LIME
0.162 0.003
S S-LIME
0.142 + 0.003
NA
NA
NA
NA
FMNIST
LINEX/rand
0.149 + 0.002
McLIME
0.001 + 0.000
0.277 0.000
0.007 = 0.000
0.769 = 0.000
0.327 = 0.000
LINEX/real
0.100 + 0.002
0.304 0.001
0.002 + 0.000
0.780 + 0.000
0.649 0.001
LIME
0.191 E 0.005
S-LIME
0.185 0.002
NA
NA
NA
NA
CIFARIO
LINEX/rand
0.186 + 0.002
McLIME
0.100 + 0.003
0.112 + 0.007
0.014 + 0.000
0.5416 + 0.003
NA
LINEX/real
0.090 + 0.005
0.279 0.001
0.006 = 0.000
0.679 = 0.004
LIME
0.079 0.036
S S-LIME
0.075 0.035
NA
NA
NA
NA
Rotten
LINEX/rand
0.069 + 0.032
Tomatoes
McLIME
0.029 + 0.001
0.391 + 0.000
0.000 = 0.000
0.999 - 0.000
0.909 + 0.000
LINEX/real
0.053 + 0.000
0.361 + 0.000
0.000 + 0.000
1.000 + 0.000
0.953 + 0.001
Also, we do not use realistic perturbations with MEPS since KDE and VAE generators do not work well with categorical data. In addition, since MEPS data uses regression black-box, CAC cannot be computed. Also for CIFARIO images in a class are not aligned so CAC is inapplicable. All these justify the missing entries in Table The results were generated on Linux machines with 56 cores and 242 GB RAM. More details regarding the exact perturbation schemes for LIME/McLIME//MPLLE the perturbation neighborhood sizes and the time taken by the methods are in Suppl. A and Suppl. D.
Quantitatively, we that in terms of CAC, LINEX is better than baselines in all cases which indicates that on average the LINEX explanations highlight the important features characterizing the entire class, making them more stable. This is also verified by looking at Y and CI metrics where LINEX is similar or better than others. For GI and INFD, the results are more evenly spread which implies that LINEX's key advantage is obtaining stable and unidirectional explanations that are faithful to similar degree. Ablation studies showing superiority of LINEX over MeL.ME on the FMNIST dataset where we have significantly higher INFD than McLIME are given in Suppl. J.
Observations:
An interesting observation is that when it comes to the stability metrics (CI and CAC) and unidirec- tionality LINEX with even random perturbation model is better than MeLIME in some cases. This is very promising as it means LINEX could be potentially be trusted without the need to generate realistic perturbations which may be computationally expensive not even possible.
Qualitatively, we see in Figures 2 and 3, that LINEX explanations are more coherent and highlight more salient features compared to MeL. Even on the text data we see more reasonable attributions in Table where "masterpiece", "moving" and "audacious" are highlighted as the most important words indicative of positive sentiment in the three examples. We also performed qualitative error

---

analysis on FMNIST where our INFD is much worse than MeLIME and is described in Suppl. I. We see that even where LINEX has high infidelity it invariably still focuses on salient features ignoring superfluous features which may result in lower fidelity but may not be critical for correct identification. The goodness of these features identified by LINEX can be further verified by looking at other metrics such as GI, CAC, CI and T in Table 2 where it is either comparable or better than MeLIME.
Discussion
In this paper we have provided a method based on game theoretic formulation and inspired by the invariant risk minimization principle to provide faithful, stable and unidirectional explanations. We have defined the latter property and argued that it somewhat of necessity (may not be sufficient) for recourse. We have theoretically shown that our method has strong tendency to be stable and unidirectional as we will mostly eliminate features where the black-box models gradient changes abruptly and in other cases choose conservative value. Empirically, we have verified this where we outperform competitors in majority of the cases on these metrics. Interestingly, in some cases our method provides more stable and unidirectional explanations with just random perturbation model relative to more expensive methods that use realistic neighbors.
We now discuss a real world use case we tested our method on. We worked with a large financial institution to explain the fraud detection model they had built. The Association of Certified Fraud Examiners (ACFE) claims that roughly 5% of a companies revenue is lost to fraud every year. Thus, catching fraud or even non-compliance is extremely important for any organization. Their model (fraud 1 else 0) had R 91 % accuracy. The inputs to the model were (transactional) invoices and details corresponding to those invoices such as vendor name, invoice amount, purchase order (PO) or not, vendor address, commodity code, country perception indices (CPI), etc. Since, one of the focuses is to reduce false positives accurate explanations are important. We applied LINEX to this setting to explain why certain invoices were classified as fraudulent. The experts found that in majority of the cases (913 out of 1000) the attributions of LINEX especially in terms of sign made sense. For instance, low CPI implies high risk and so LINEX gave negative coefficient for this feature for most examples, while LIME gave a positive coefficient for many instances. Going forward their plan is to incorporate such capabilities into their workflow to further improve fraud detection precision.
In the future, would worth experimenting with more varied strategies to form environments and if possible find the optimal ones [TO]. which may lead to picking even more relevant features that are "causal" to the local decision.
7 Summary of the Supplement
Information about black-box classifier accuracies and realistic perturbation methods used for the datasets are provided in Table 3. Suppl. A has run time comparisons. Suppl. B has proof of Theorem Suppl. C discusses theoretical behavior of LINEX for more than two environments. Suppl. D has dataset details and hyperparameter specifications. Suppl. E has experiments with different hyperparameter combinations (including more than 2 environments). Suppl. has additional examples of text data attributions. Suppl. G has example feature attributions with image data. Suppl. H has SHAP results. Suppl. I. J and has error analysis and ablation studies. Suppl. L has additional synthetic experiments. Suppl. M discusses sensitivity to y. Suppl. N demonstrates convergence of LINEX. Suppl. O discusses limitations of LINEX. Figure (30 SLIME variants using median and median of means which turn out to be worse than using the (typical) mean.
References
[1] Agency for Healthcare Research and Quality. Medical Expenditure Panel Survey (MEPS). https://meps... ahrr. wwt.rr/gg/////wwbb////// 2019. Last accessed 2019-08.
[2] C. Aggarwal and C. Reddy. Data Clustering: Algorithms and Applications. CRC Press, 2013.
[3] K. Ahuja, K. Shanmugam, and A. Dhurandhar. Linear regression games: Convergence guaran- tees to approximate out-of-distribution solutions. In AISTATS, 2021.
10

---

[4] K. Ahuja, K. Shanmugam, K. Varshney, and A. Dhurandhar, Invariant risk minimization game. In International Conference on Machine Learning, 2020.
[5] E. Amparore, A. Perotti, and P. Bajardi. To trust or not to trust an explanation: using leaf to evaluate local linear xai methods. PeerJ Computer Science, 7:e479, 2021.
[6] C. Anders, P. Pasliev, A.-. Dombrowski, K.-R. Muller, and P. Kessel. Fairwashing ex- planations with off aff-manifold detergent. In Intl. Conference on Machine Learning (ICML), 2020.
[7] M. Arjovsky, L. Bottou, I. Gulrajani, and D. Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv: 190.vv990.00288000 00090000.999.... 2019.
[8] T. Botari, F. Hvilshoj, Izbicki, and A. C. L. F. de Carvalho. Mclime: Meaningful local explanation for machine learning models, 2020.
[9] J. Chen, X. Wu, V. Rastogi, Y. Liang, and S. Jha. Robust attribution regularization, NeurIPS, 2019.
[10] E. Creager, J.-H. Jacobsen, and R. Zemel. Environment inference for invariant learning. In ICML 2020 Workshop on Uncertainty and Robustness in Deep Learning, 2020.
[11] G. Debreu. A social equilibrium existence theorem. Proceedings of the National Academy of Sciences, 38(10):886 893, 1952.
[12] D. Dheeru and Karra Taniskidou. UCI machine learning repository, 2017.
[13] A. Dhurandhar, P.-Y. Chen, R. Luss, C.-C. Tu, P. Ting, K. Shanmugam, and Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. In Advances in Neural Information Processing Systems, pages 592-603, 2018.
[14] A. Dhurandhar, T. Pedapati, A. Balakrishnan, K. A. Pin-Yu Chen, Karthikeyan Shan- mugam, and R. Puri. Model agnostic contrastive explanations for structured data. https://rrxiv.rg/abb////o
2019.
[15] A. Dhurandhar, K. N. Ramamurthy, and K. Shanmugam. Is this the right neighborhood? accurate and query efficient model agnostic explanations. In Advances in Neural Information Processing Systems, 2022.
[16] A. Dhurandhar, K. Shanmugam, and R. Luss. Enhancing simple models by exploiting what they already know. In Intl. Conference on Machine Learning. 2020.
[17] A. Dhurandhar, K. Shanmugam, R. Luss, and P. Olsen. Improving simple models with confi- dence profiles. In Advances in Neural Information Processing Systems, pages 10396- 2018.
[18] A.-K. Dombrowski, M. Alber, C. J. Anders, M. Ackermann, K.-R. Müller, and P. Kessel. Explanations can be manipulated and geometry is to blame. In Advances in Neural Information Processing Systems, 2019.
[19] A.-K. Dombrowski, C. J. Anders, K.-R. Müller, and Kessel. Towards robust explanations for deep neural networks. 121(C), 2022.
[20] K. Dutta. Strategies and games: theory and practice. MIT Press, 1999.
[21] S. Feng, Wallace, A. Grissom II, M. lyyer, Rodriguez, and J. Boyd-Grabae Pathologies of neural models make interpretations difficult. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Processing, pages 3719-3728, Brussels, Belgium, Oct.-Nov. 2018. Association for Computational Linguistics.
[22] C. Frye, C. Rowat, and I. Feige Asymmetric shapley values: incorporating causal knowledge into model-agnostic explainability. NeurIPS, 2020.
[23] A. Ghorbani, A. Abid, and J. Zou. Interpretation of neural networks is fragile, 2019.

---

[24] D. Gunning, Explainable artificial intelligence (xai), In Defense Advanced Research Projects Agency, 2017.
[25] K. Gurumoorthy, A. Dhurandhar, G. Cecchi, and C. Aggarwal. Efficient data representation by selecting prototypes with importance weights. In Proceedings of the IEEE International Conference on Data Mining, 2019.
[26] L. Hancox-Li. Robustness in machine learning explanations: does it matter? In Proceedings of the 2020 Conference on Fairness, Accountability, and Transpurency. ACM, 2020.
[27] T. Heskes, E. Sijben, I. G. Bucur, and T. Claassen. Causal shapley values: Exploiting causal knowledge to explain individual predictions of complex models. Advances in Neural Information Processing Systems, 2020.
[28] G. Hinton, O. Vinyals, and J. Dean. arXiv:1503.02530 2015.
Distilling the knowledge in a neural network.
[29] A.-H. Karimi, B. Schölkopf, and I. Valera. Algorithmic recourse: from counterfactual expla- nations to interventions. In ACM conference on Fairness, Accountability and Transparency (FAceT), 2021.
[30] B. Kim, R. Khanna, and O. Koyejo. Examples are not not enough, learn criticize! Critieism for interpretability. In In Advances of Neural Inf. Proc. Systems, 2016.
[31] A. Krizhevsky. Learning multiple layers of features from tiny images, 2009.
[32] H. Lakkaraju, N. Arsov, and O. Bastani. Robust and stable black box explanations. ICML, 2020.
[33] S. Lapuschkin, A. Binder, G. Montavon, K.-R. Müller, and W. Samek. The Irp toolbox for artificial neural networks. Journal of Machine Learning Research, 17(114):1-5, 2016.
[34] Q. V. Liao, Y. Zhang, R. Luss, F. Doshi- Velez, and A. Dhurandhar. Connecting algorithmic research and usage contexts: A perspective ofcontextualized evaluation for explainable ai. In Proceedings of the Tenth AAAI Conference on Human Computation and Crowdsourcing, 2022.
[35] S. M. Lundberg and S.-L. Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, pages 4765-4774, 2017.
[36] T. Miller. Explanation in artificial intelligence: Insights from the social sciences. Artificial Intelligence, 2018.
[37] C. Molnar, Interpretable machine learning, 2019.
[38] B. Pang, L. Lee, and S. Vaithyanathan. Thumbs up? sentiment classification using machine learning techniques. In Proceedings of EMNLP, pages 79-86, 2002.
[39] G. Plumb, D. Molitor, and A. Talwalkar, Model agnostic supervised local explanations. In Advances in Neural Information Processing Systems, page 2520-2529, 2018.
[40] K. N. Ramamurthy, Vinzamuri, Y. Zhang, and A. Dhurandhar. Model agnostic multilevel explanations, 2020.
[41] M. T. Ribeiro, S. Singh, and C. Guestrin. "Why should I trust you?": Explaining the predictions of any classifier. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1135-1144 144, 2016.
[42] Y. Roth and N. Pickles. Updating our approach to misleading information. 2020.
[43] C. Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Mach. Intell., 155):0662215 May 2019.
[44] A. Sarkar, A. Sarkar, and V. N. Balasubramanian. Enhanced regularizers for attributional robustness. AAAI, 2021.
12

---

[45] A. A. Shrotri, N. Narodytska, A. Igmatiev, J. Sarques-Silva K. S. Meel, and M. Vardi. Coritraint-driven explanations of black-box (ml} models, 2021.
[46] K. Simonyan, A. Vedaldi, and A. Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv:1312.6034, 2013.
[47] M. Sundararajan, A. Taly, and Q. Yan. Axiomatic attribution for deep networks. ICML, 2017.
[48] Vig. S. Gehrmann, Y. Belinkov, S. Qian, D. Nevo, S. Sakenis, Huang, Y. Singer, and S. Shieber. Causal mediation analysis for interpreting neural nlp: The case of gender bias. NeurIPS, 2020.
[49] G. Visani, E. Bagli, Chesani, A. Poluzzi, and D. Capuzzo. Statistical stability indices for lime: obtaining reliable explanations for machine learning models. arXiv:2001.11557 2020.
[50] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms, 2017.
[51] N. Yannella and O. Kagan. Analysis: Article 29 working party guidelines on automated decision making under gdpr. 2018. 29-working- salll-prttttyeee tattt--uiiiiine----ttttoonee -utommatdd-decciioo----eee making under-gdpi gdpr//
[52] C.-K. Ych, C.-Y. Hsich, A. Suggala, D. L. Inouye, and P. K. Ravikumar. On the (in) fidelity and sensitivity of explanations. In Advances in Neural Information Processing Systems, pages 10965-10976, 2019.
[53] H. Zhang, H. Chen, Z. Song, D. Boning, I. S. Dhillon, and C.-J. Hsieh. The limitations of adversarial training and the blind-spot attack. In International Conference on Learning Representations (ICLR), 2019.
[54] Y. Zhang, K. Song, Y. Sun, S. Tan, and M. Udell. Why should you trust my explanation? ICML-AI for Social Good, 2019.
[55] X. Zhao, W. Huang, X. Huang, V. Robu, and D. Flynn. Baylime: Bayesian local interpretable model-agnostic explanations. UAI, 2021.
13

---

Table 3: Datasets, models and neighborhoods used in experiments. RF-> Random Forest, NN Neural Network, ResNet-> Residual Network and NB Naive Bayes.
Dataset
Modality
Black-box model acc/It',
Realistic neighborhood creation methods
IRIS MEPS
tabular
RF classifier, 93%
KDEGen 8
RF
tabular
RF regressor, 0.325
39
FMNIST
image
NN classifier, 87%
VAEGen g
CIFARIO
image
ResNet18, 95%
VAEGen 8
Rotten Tomatoes
text
NB classifier, 75%
Word2VecGen
A Efficiency of LINEX
It is important to note that the query complexity (i.e. number of times we query the black box to obtain an explanation) of LINEX is the same as that of LIME since the union of the environments is the same LIME perturbation neighborhood. This is important in todays cloud-driven world where models may exist on different cloud platforms and posthoe explanations are an independent service where each call to the model has associated cost. In terms of running time for environments, convergence was fast and running time was approximately 2.5 times that of LIME (LINEX took 2.5 seconds on IRIS for 30 examples as opposed to I second by LIME, LINEX took 47 seconds on MEPS for 500 examples as opposed to 18 seconds by LIME), which is very similar to Smoothed LIME (S-LIME) (took 2.3 seconds on IRIS and 40 seconds on MEPS) that we still outperform in majority of the cases.
Realistic neighborhood generation can be time consuming especially for McLIME since generators have to be trained which may take up to an hour using a single GPU for datasets such as FMNIST. After the generator is trained and neighhorhood sampled MeLIME takes the same amount of time as LIME since the model fitting procedure is the same. MAPLE took 1.5 seconds for the IRIS dataset for 30 examples and 27 seconds for 500 MEPS examples.
way to further speed up LINEX would be to implement it through embarrassing parallelism which can easily be done across explanations. This will prevent scaling of the running time in the number of examples when many explanations are needed. The setting with many explanations is anyway where would need efficiency because if only few explanations were desired the slightly higher running time of LINEX would not be an issuc.
B Proof of Theorem 1
Expanding on the proof sketch provided in the main paper we now provide case wise analysis to prove Theorem 1.
wi w³: If the optimal solutions to both environments in the convex set [-% 1 are the same, then in the first iteration itself where we fit to the first environment we would have reached the optimal solution to our problem where wH wi This is because in the second iteration where we fit the second environment to the residual from the previous fit u = 0 and the algorithm would terminate. This would imply the output of algorithm 1 would be ur wi.
wi wa: When the optimal solutions for the two environments are not equal we consider the following two cases:
Opposite sign attributions: If the th component of wt and w have opposite signs, then the 5th components of the ensemble predictor, wT. and thz are both at the boundary ? and -y respectively wn > O. This is because both try to push the ensemble (i.e. their sum) towards the sign they have where eventually they reach the boundary łn and have no incentive to deviate. Any deviation from these values will lead to a higher least squares error in their environment, thus making this NE.
Same sign attributions: If the 7th component of wi and wi have same signs, then the 1th component of ensemble predictor constructed from the NE set to the least squares attribution with smaller absolute value, i.e., w; = where |wi < |wğgl- Without loss of generality assume 0 < wi, < why the attribution of the environments' predictors in NE, then Wi and Wiy have opposite signs, i... Wbzt y and w1, wi. - y where the
14

---

ensemble predictor for the hth component would be w;; = ش1 + ب2ا = wi, - wix since any deviation from this would lead to worse least squares loss for the corresponding environment. This shows that ensemble predictor is conservative and selects the smaller least squares attribution.
C Behavior for More than Two Environments
Given Assumptions and 2 we now discuss the behavior of our method for more than two environ- ments. If the number of environments odd, then using similar logie to that discussed the proof sketch one can see that the feature attribution would be equal to the median of the feature attributions across all the environments. Essentially, all environments with optimal least squares attributions above the median would be at +., while those below it would be at -% The one at the median would remain so with no incentive for any environment to alter its attribution making it a NE. This is a stable choice that is also likely to be faithful as we have no more information to decide otherwise. On the other hand if we have an even number of environments the final attribution in this case depends on the middle two environments in the same manner as the two environment case proved in Theorem I Thus, if the optimal least squares attributions of the middle two environments have opposite sign, then the final attribution is zero, else its the lower of the two attributions in terms of the numerical value. This happens because the NE for the other environments is t depending on if their optimal least squares attributions are above/below those of the middle two environments. This again is stable and likely to be faithful choice, where also unidirectionality is preferred.
D Experimental Details
D.1 Dataset Details and Hyperparameter Specifications
We describe the datasets and the hyperparameters used for each. We set perturbation neighborhood sizes 10 (IRIS), 500 (MEPS), 100 (FMNIST-random), 500 (FMNIST-reallitic)) 100 (CIFAR10- random), 500 (CIFAR0--realistic). 100 (Rotten tomatoes) for generating local explanations. We also use 3, 10, 10, 10, 5 as exemplar neighborhood sizes to compute GI, CI and Y metrics for the five datasets respectively. We also use 5-sparse explanations for all cases except FMNIST and CIFARIO with realistic perturbations where we follow MeLIME and generate dense explanation using ridge penalty with penalty multiplier value of 0.001. The fox bound 7 in Algorithm is set as the maximum absolute value of linear coefficient computed by running LIME/MeLIME in the two individual environments. Please look at IRIS dataset first since it contains some of the common details used across others.
IRIS (Tabular): This dataset has 150 instances with four numerical features representing the sepal and petal width and length in centimeters. The task is to classify instances of Iris flowers into three species: setosa, versicolor, and virginica. A random forest classifier was trained with a train/test split of 0.8/0.2 and yielded test accuracy of 93%. We provide local explanations for the prediction probabilities for class setosa. For both random and realistic perturbations, we use perturbation neighborhood size of n. For random perturbations, we used the same approach followed by LIME and sample from a Gaussian around each data point. Realistic perturbations (with the same number n) were generated using KDEGen 3 a kernel density estimator (KDE) with the Gaussian kernel fitted on the training dataset to sample data around a sample point. For both random and realistic perturbations, we weight the neighborhood using Gaussian kernel of width J vVd, where d is the dimension of the feature vector and T = {0.05, 0.1, 0.25, 0.5, 0.75), and this corresponded to kernel widths {0.1 1, 0.2, 0.5, 1.0, 1.5). We also perform weighted version of realistic selection where we use MAPI PLE 39 to assign weights to all the test examples and pick the top n weighted examples to use as the perturbation neighborhood. For random/realistic perturbations and realistic selection, the corresponding environments (of size n each) for LINEX are created by drawing & bootstrap samples where k= = (,, 3, 4, 5) in our experiments. We test for {10, 20, 30, 40, 50} with this dataset.
Medical Expenditure Panel Survey (Tabular): The Medical Expenditure Panel Survey (MEPS)
dataset is produced by the US Department of Health and Human Services. It is a collection of surveys of families of individuals, medical providers, and employers across the country. We choose Panel 19 of the survey which consists of cohort that started in 2014 and consisted of data collected over 5
15

---

rounds of interviews over 2014 - 2015. The outcome variable was composite utilization feature that quantified the total number of healthcare visits of a patient. The features used included demographic features, perceived health status, various diagnosis, limitations, and socioeconomic factors. We filter out records that had utilization (outcome) of O, and log-transformed the outcome for modeling. These pre-processing steps resulted in a dataset with 11 1133 examples and 32 categorical features. We train a random forest regressor that has a test R² of 0.325 in this dataset. We provide local explanations of the predictions. With MEPS, we do not use realistic perturbations since KDE and VAE generators do not work well with categorical data. Otherwise the setting is similar as IRIS data, except that we {0.28, 0.57, 1.41, 2.83, 4.24].
(50, 100, 200, 300, 400, 5003. The kernel widths in this case were We use k = (2,3, 3, 4. 5 for this dataset.
Fashion MNIST (Images): This dataset has 28 x 28 grayscale images of fashion articles with 60,000 train and 10,000 test samples. The task is to classify these into 10 classes correspond- ing to coat, shoe, and so on. A neural network trained with test accuracy of 87%. Explanations are generated for the prediction probabilities corresponding the predicted class for each ex- ample. We choose 1000 test examples to generate explanations. Realistic perturbations were generated using VAEGen H Variational Auto Encoder (VAE) fitted the training dataset. For random perturbations, we chose n from {50, 100, 200, 300, 400, 500) and kernel sizes were {0.43, 0.85, 2.14, 4.27, 6.41) }. For realistic perturbations we chose n from (250, 500, 750, 1000) and the kernel widths were {1.4, 2.8, 7.0, 14.0, 21.03. We use k = {2, 3, 4, 5} for this dataset.
CIFARIO (Images): This dataset has 32 x 32 colored images belonging to 10 different classes. The dataset has 50,000 train and 10,000 test samples. The task is classify these into 10 classes corresponding to dog, bird, and so on. A residual network with 18 units (ResNet18) was trained with test accuracy of ~ 95%. Explanations are generated for the prediction probabilities corresponding to the predicted class for each example. We choose 1000 test examples to generate explanations. Realistic perturbations were generated using VAEGen 88, a Variational Auto Encoder (VAE) fitted on the training dataset. For random perturbations, we chose from (50, 100, 200, 300, 400, 500] and kernel sizes were {0.43, 0.85, 2.14, 4.27, 6.41). For realistic perturbations we chose n from {250, 500, 750, }000} and the kernel widths were { (1.4, 2.8, 7.0, 14.0, 21.0}. We use k = (2, 4,53 for this dataset.
Rotten Tomatoes (Text): This dataset contains 10662 movie reviews from rotten tomatoes website along with their sentiment polarity, i.c., positive or negative reviews and the task is to classify the sentiment of the reviews into positive or negative. The review sentences were vectorized using Count Vectorizer and Trnffraanfrrmer and sklearn Naive Bayes classifier was fitted on training dataset which yielded a test accuracy of 75%. Explanations are generated for the prediction probabili- ties corresponding to the predicted class for each example. Realistic perturbations were generated using Werd2VeeGen [8), wherein word2vec embeddings are first trained using the training corpus and new sentences are generated by randomly replacing sentence word whose distance in the embedding space lies within the radius of the neighbourhood. For both random and realistic perturbations, was chosen from {25, 50, 75, 100]. The kernel sizes were {0.42, 1.06, 2.12, 3.18} for random perturbations (kernel size 0.21 resulted in numerical issues), and (0.21, 0.42, 1.06, 2.12, 3.18} for realistic perturbations. We use k- {2, 3, 5, for this dataset.
E Results with All Datasets and Hyperparameter Combinations for Random and Realistic Perturbations
We present results with all hyperparameter combinations for random and realistic perturbations. Results for LIME with random perturbations (LIME), smoothed LIME (S-LIME), LINEX with random perturbations (LINEX/rand), MeLIME (MeLIME), LINEX with McLIME-like realistic neighborhoods (LINEX/rea),, MAPLE (MAPLE), LINEX with MAPLE-like realistic neighborhoods The legend for these figures are given in Figure
(LINEX/mpl) are presented in figures 19
For the five datasets, we perform ablations by varying one of perturbation neighborhood size (Figures 5.. number of environments (Figures 14). 14), and kernel width (Figures 15 19 Each point in
these figures are averaged over all possible values for the two parameters that are not ablated. For example, each point in Figure i] averaged over all possible values for kernel widths and number of
16

---

environments for given perturbation neighborhood size. Standard errors of the mean are also plotted in the same color with lesser opacity. Lower values of Infidelity (INFD), Generalized Infidelity (GI), Coefficient Inconsistency (CI) are better whereas for Unidirectionliity (Y) and Class Attribution Consistency (CAC) higher values are better.
Figures 5 show ablations with respect to perturbation neighborhood sizes. Considering all datasets, the stability/rccouree metries (CI, Y, CAC) are clearly better for LINEX compared to its counter- parts. For LINEX methods (LINEX/rand, LINEX/real, LINEX/mpl,, the metrics get better or stays approximately the same generally as perturbation neighborhood size increases keeping with the intuition that larger perturbation neighborhood sizes should produce explanations that are more stable in the exemplar neighborhood. for FMNIST and CIFARIO are already good for small perturbation neighborhood sizes possibly because of the quality of McLIME perturbations.
Turning to the fidelity metrics (INFD and GI) in tabular datasets, see that the results still favor LINEX, but less heavily compared to the stability/recourse metrics. This is in line with what we observe in T in the GI measure (except for LINEX/mpl with MEPS). This gap closes a bit with INFD, but we note that is better measure since it estimates how faithful explanations are in a exemplar neighborhood. With the text dataset, LINEX variants are slightly more favored, whereas with the image dataset, the baselines have an edge.
IRIS and MEPS, LINEX close to or outperforms the corresponding baselines
Considering Figures TO 14 we see that variations are less stark with respect to number of environ- ments overall for LINEX variants. Note that except for S-LIME, other baselines do not use multiple environments, and hence stay constant. The slight variations in MAPLE are due to the effect of random seeds. In the stability/recoorse metrics, again LINEX variants emerge as the clear winner across datssets. With the faithfulness metrics (GI and INFD), in the text dataset, LINEX variants generally perform better, whereas the baselines have better performance in the image dataset.
Finally, we study the variation of the performance measures with respect to kernel width in Figures We that the stability/recourse metrics flatten out in all cases with large kernel widths. This behaviour holds true for faithfulness metrics (GI and INFD) as well except in some cases. GI and INFD measures also increase before they flatten out since the fit becomes poorer at larger kernel widths. The stability/recooure metrics hecome better or remain approximately the same since explanations generally improve or preserve their stability properties kernel widths increase. Note that very small kernel widths can lead to unexpected behavior that does not fit the trend as seen with the tabular datasets since explanations same at different kernel widths since they use a different weighting scheme. As with other ablations, we see that LINEX variants are similar better in stability/recourse metries overall, while with the faithfulness metrics the results are more mixed.
15 19
become hyper-local. MAPLE and LINEX/mpl stay the
Note that do not compute MeLIME perturbations with MEPS since KDE and VAE generators do not work well with categorical data, and do not use compute CAC since the task is regression. Further, the features used in explanations for different test examples are not comparable for random perturbations with FMNIST, CIFARI0 and Rotten Tomatoes, hence we cannot compute CAC for those cases as well. This explains the missing curves/plots.
LIME
S-LIME
LINEX/rand
MeLime
LINEX/real
MAPLE
LINEX/mpl
Figure 4: Legend for figures 5 19
17

---

3.20
2044
(a) Iris
(b) MEPS
(c) FMNIST
(d) Rotten Tomatocs
0.0
(e) CIFAR10
Figure 5: Coefficient inconsistency (CI) vs. Perturbation neighborhood size.
Regnaomaad
sedgh
Iris
(b) FMNIST
(c) Rotten Tomatoes
Figure 6: Class attribution consistency (CAC) vs. Perturbation neighborhood size.
6.-
5.793
335
3769
24
20
232
220
203
350
(a) Tris
(b) MEPS
(c) FMNIST
(d) Rotten Tomatoes
8.47
6.00
Berghterband
(e) CIFARIO
Figure 7: Unidirectionality (Y) vs. Perturbation neighborhood size.
20
130
200 200
402
56E
331
(a) Iris
(b) MEPS
(c) FMNIST
(d) Rotten Tomatocs
(e) CIFAR10
Figure 8: Generalized infidelity (GI) vs. Perturbation neighborhood size.
18

---

2000
3048
3035
3.33
3.14
311
3115
1.59
1025
1023
1033
3002
3001
1892
Segheurbood Siz
Meglacrkead
(a) Iris
MEPS
FMNIST (random)
(d) FMNIST (realistic)
00375
C39
Heigbbrrtodd 804
seggbeeteed site
Hei Reighberhood abs
(e) Rotten Tomatoes
(1) Rotten Tomatoes (realistic)
(g) CIFARIO
(random)
Figure 9: Infidelity (INFD) vs. Perturbation neighborhood size.
Momber centrommentt
35
25 1.1
20
(a) Iris
(b) MEPS
(c) FMNIST
(d) Rotten Tomatocs
(e) CIFARIO
Figure 10: Coefficient inconsistency (CI) Vs. Number of environments.
23455
0.50
Munser anerroweett
Homber ee
(a) Iris
(b) FMNIST
(c) Rotten Tomatoes
Figure 11: Class attribution consistency (CAC) vs. Number of environments.
F
Example Feature Attributions in Text Data: MeLIME vs LINEX
Below sample attributions by the two methods along with the magnitude of the attributions. Attribution magnitudes are printed with a precision of 10 and shown along with the corresponding words in descending order.
F1 Positive Sentiment
enticing and often funny documentary
MeLIME: documentary funny and enticing often
LINEX documentary funny often enticing and
MeLIME: 0.517 0. 446 o. 333 0.317 0.311
19

---

4774
6.76
A774
3051
279
03950)
03061
Manber cww.oooerddd
Rerder
Sueter
(a) Iris
MEPS
FMNIST
Rotten Tomatoes
6.22
650
(c) CIFAR10
Figure 12: Unidirectionality (T) vs. Number of environments.
E312
3.33
12
8.D
11
21
4.0
10
(a) Iris
(b) MEPS
(c) FMNIST
(d) Rotten Tomatocs
2.09
020
526
Hondow
(e) CIFARIO
Figure 13: Generalized infidelity (GI) vs. Number of environments.
322
3025
3008
3005
335
20
25
40
(a) Tris
(b) MEPS
(c) FMNIST (random)
(d) FMNIST (realistic)
0424
0033
123
2325
Namber wnweeereantts
Mumee envirOmenT
Hamber aevtrenunts
Rotten Tomatoes (random)
(f) Rotten Tomatoes
(g) CIFARIO
(realistic)
Figure 14: Infidelity (INFD) vs. Number of environments.
LINEX 0.416 0.377 0.342 0.331 0.330
one-of-a-kind near-masterpiece.
MeLIME: kind near masterpiece LINEX masterpiece kind one
MeLIME: 0.832 695 0. 182 LINEX 0.712 384 381
20

---

339
A794
05850
02
0.6
022 25.
(a) Iris
(b) MEPS
(c) FMNIST
(d) Rotten Tomatocs
6.52
0.0
Srenet wilh
(e) CIFAR1O
Figure 15: Unidirectionality (T) Kernel width.
8000
03 04 86 03
12 24
32.3 22. 35.
(a) Iris
(b) MEPS
(c) FMNIST
(d) Rotten Tomatoes
(e) CIFARIO
Figure 16: Coefficient inconsistency (CI) vs. Kernel width.
2.0
(a) Iris
(b) FMNIST
(c) Rotten Tomatoes
Figure 17: Class attribution consistencv (CAC) vs. Kernel width.
235
Revent
Smadl miRh
Eemee widh
(a) Iris
MEPS
FMNIST
(d) Rotten Tomatoes
620
125
Kornel witt
CIFARIO
Figure 18: Generalized infidelity (GI) vs. Kernel width.
21

---

3.95
64
20 28
23
22
28
26
35
23
280 10 156 225 320
(a) Iris
(b) MEPS
(C) FMNIST (random)
(d) FMNIST (realistic)
0.10
0.0
0.30
4.00
0.00
(e) Rotten Tomatoes
(1) Rotten Tomatoes
(g) CIFARIO
(random)
(realistic)
Figure 19: Infidelity (INFD) vs. Kernel width.
a fast funny highly enjoyable movie MeLIME: enjoyable highly funny fast movie LINEX enjoyable highly fast funny movie
MeLIME: 0.550 0.4 0.412 0.389 0.198
LINEX 0.409 0. 0.9 0.372 0. 350 0.326
ferrara's strongest and most touching movie of recent years. MeLIME: touching years
strongest and LINEX touching most recent strongest and 0. 0.450 0. 443 0.427
MeLIME: 7.7 0.490
LINEX 0.490 0. 488 0. 0.450 0. 044 0.407
saved from being merely way-cool by a basic credible compassion MeLIME: cool basic credible merely from
LINEX: cool credible merely compassion from
MeLIME: 1.514 0.0 0.0 0.0 0.026
LINEX 0.358 308 0.304 099 0.293
really quite funny
MeLIME: funny quite really LINEX funny quite really
MeLIME: 0.559 0.417 0.233 LINEX 0.462 0. 0.275
spare yet audacious
MeLIME: spare yet audacious
LINEX audacious spare yet
MeLIME: 0.626 0.4 0.395 LINEX 0.501 0.4 0.422
an engrossing and infectiously enthusiastic documentary MeLIME: engrossing documentary and enthusiastic an LINEX engrossing documentary an enthusiastic and MeLIME: 0.593 0. 455 0. 358 0. 354 0.333
LINEX 0.461 407 3.374 3.3 0.350
wildly funny prison caper MeLIME: funny caper wildly prison LINEX funny caper prison wildly MeLIME: 0.541 364 214 193
22

---

LINEX 0.403 335 0. 245 039
this charming but slight tale has warmth wit and interesting characters compassionately portrayed
MeLIME: charming compassionately and interesting portrayed
LINEX charming compassionately has tale portrayed
MeLIME: 0.690 0.507 0.456 0. 044 0.424
LINEX 0.464 0.4 0.431 0.430 0.429
thoughtful provocative and entertaining MeLIME: thoughtful entertaining and provocative LINEX thoughtful entertaining and provocative
MeLIME: 0.2 0.517 0.402 0.395
LINEX 0.505 0.461 0.415 0.404
the film is quiet threatening and unforgettable MeLIME: quiet unforgettable and film the LINEX unforgettable quiet film and is MeLIME: 0.597 483 014 0.325 0.303
LINEX 0.421 0.416 388 37878 0.3
moving tale of love and destruction in unexpected places unexamined lives MeLIME: unexpected moving love tale lives LINEX moving unexpected places lives in
MeLIME: 0.692 0.662 0.577 0.538 0.499 LINEX 0.538 0.530 0.521 0.513 0.501
though frodo's quest remains unfulfilled determined new zealanders has proved its creative mettle.
hardy group of
MeLIME: creative group proved has new LINEX creative quest its proved determined
MeLIME: 0.602 0.441 0.424 0.402 0.393 LINEX 010 0.392 0. 390 0. 385 0.381
F22 Negative Sentiment
originality sorely lacking
MeLIME: lacking sorely is originality
LINEX lacking sorely originality is
MeLIME: 0.543 0.381 0.296 0. 0.878 LINEX 430 0.356 0.314 272
an ugly pointless stupid movie MeLIME: stupid pointless ugly movie an LINEX stupid pointless ugly movie an MeLIME: 0.543 0.499 0.385 0.365 0.276
LINEX 0.6 01411 0.373 3.360 0.350
so devoid of pleasure or sensuality that it cannot even be dubbed hedonistic MeLIME: devoid even be dubbed of
LINEX devoid so dubbed be cannot
MeLIME: 0.666 0.416 0.413 0.372 0.344 LINEX 0.400 3.3 0. 387 380 0.368
neither revelatory nor truly edgy- crassly flamboyant and comedically labored
MeLIME: edgy neither nor labored revelatory LINEX edgy neither nor labored truly
MeLIME: 1.256 0. 338 0. 277 204 0.021
23

---

LINEX 0.439 0. 398 398 369 0.349
occasionally funny sometimes inspiring often boring
MeLIME: boring occasionally inspiring sometimes often LINEX boring occasionally sometimes often inspiring
MeLIME: 0.669 042 218 0. 210 0.1
LINEX 0.377 262 0. 262 250 0.236
cumbersome and cliche-ridden movie greased with every emotional device known to man
MeLIME: cliche every device movie with
LINEX cliche every man cumbersome emotional
MeLIME: 0.695 0.449 0.327 0.280 0.268
LINEX 0.385 0 0.361 0 353 0.349 0.309
ponderous plodding soap opera disguised as feature film
MeLIME: plodding soap ponderous opera disguised LINEX plodding soap film ponderous feature
MeLIME: 0.579 0.522 0.421 0.808 0.382
LINEX 0.442 0. 040 0.418 0.406 0.377
kitschy flashy, overlong soap opera MeLIME: soap flashy opera overlong kitschy LINEX soap flashy opera overlong kitschy
MeLIME: 0.499 0.397 0.391 3.358 0.230 LINEX 0.389 0.362 0.360 0. 0.300
[a] poorly executed comedy MeLIME: poorly comedy executed LINEX poorly comedy executed MeLIME: 0.653 0.348 0.257 LINEX 0.502 0.335 0.309
bad movie that happened to good actors MeLIME: bad happened movie to that
LINEX bad happened movie actors
MeLIME: 0. 0.396 0.371 0.367 0. 242 LINEX 0.4 0. 384 0.367 0.361 0.344
complete waste of time MeLIME: waste complete time of LINEX waste complete time
MeLIME: 0.614 0.425 0.313 0.247 LINEX 0.4 0.381 0.348 0.278
don't waste your money
MeLIME: waste money don your
LINEX waste money don your
MeLIME: 0.592 0. 497 0. 408 0. 0.3 LINEX 483 0. 450 0 411 3.3
witless and utterly pointless
MeLIME: pointless witless and utterly
LINEX pointless witless utterly and
MeLIME: 0.652 0.491 0.263 0.245 LINEX 0.506 044 0.311 269
24

---

MrLIME:r= or 0.279
LINEX 0.603
Original
(2a) McLIMEr 0.434 (2b) LINEX: 0.689
(2c) Original
(3a) McLIME: 0,259 (3b) = 0.711
(3c) Original
(4a) MeLIME: 0.292 (4b) LINEX:r = 0.633
(4c) Original
33-
30-
18-
10-
15
15-
15-
15-
15
25
25
:r 0.271 (5b) LINEX 0.701
Original
(6a) McLIME: 0,297 (6b) LINEX:r 0.962
(6c) Original
35-
15
(76) MeLIME:r - 0.482 (7b) - 0.820
(7c) Original
(8a) MeLIME:/ 0.177 (8b) LINEXi/ - 0.788
(8c) Original
19
18
10
15-
15-
15-
15-
15-
15
10
25
25
2>
MrLIME 0.247 LINEX:r
Original
(10a) 0.381(106)
(10c) Original
25
25
Figure 20: Results using individual samples for realistic perturbations for FMNIST dataset for all classes:1-10 (T-shirt/top, Trouser, Pullover, Dress, Coat, Sandal, Shirt, Sneaker, Bag and Ankle boot). (a) McLIME feature attributions for an image. (b) LINEX feature attributions for an image. (c) Original image in the class. The values show Pearson's correlation between feature attributions and the original image from the respective class. We observe that LINEX attributions/expllaaaios exhibit significantly higher correlation with the original image belonging particular class (i.e.
high CAC).
G Example Feature Attributions in Image Data: MeLIME vs LINEX
We show feature attributions for individual example images with MeLIME and LINEX with McLIME perturbations in Figure 20 In Figure 21 we show class-wise mean feature attributions along with mean images. Figure 22] see examples from CIFARIO. LINEX explanations seem provide more meaningful feature attributions.
H Results for All Methods Including SHAP
In Table 4 we provide the results for SHAP along with all methods for easy comparison. Note that SHAP does not have standard errors since is computed only once per test point. The INFD values for SHAP are miniscule since SHAP values add up to the predictions by definition. In order to compute GI, CI, Y, CAC, we convert the SHAP values to SHAP attributions first and follow the same approach used by other explanation methods.
25

---

(1a) McLIME:r=0.200
(1b) LINEX:==0.544
Original
(2a) MeLIME:r=0.4RP LINEX:==08009
(2c) Original
(3a) McLIME:r=0.311 (3b] LINE
[3c) Original
(4a) McL1ME:r=0.418 (4b) LINEX:r=0.80
(4c) Original
39-
10-
30-
18
10-
15
16-
16-
15-
15
26
24
04
25
25
00
(5a) McLIME (5b) LINEX:==0.69) 6.6
Original
(6a) MeLIME:r=0.419 (6b) LINEX:==
(6c) Original
35-
15
(7a) MeLIMEErr0.331 (7b) LINEX://0.788
[7c) Original
(8a) MeLIME:70-432 (8b) LINEX:r= 0.000
(8c) Original
19
18
10
15-
15-
15-
15-
15-
15
10
25
25
25
29
(9a) LELIME:r-D
(9b) LINEX:-00.75
Original
MeLIME:r=O.Am (10b)) LINEXir-
(10c) Original
25
25
25
Figure 21: Results using realistic perturbations for FMNIST dataset with mean feature importances for all classes:1-10 (T-shirt/top, Trouser, Pullover, Dress, Coat, Sandal, Shirt, Sneaker, Bag and Ankle boot). (a) Mcan feature attributions of all images in the class using McLIME. (b) Mean feature attributions of all images in the class using LINEX. Mean all images the class. The values show Pearson's 's correlation between average feature attributions and mean of the original images from the respective classes. We observe that LINEX explanations/atrribttioo exhibit significantly higher correlation with the original images belonging to a particular class (i.e. high CAC).
I Error Analysis of LINEX
We perform eπror analysis for LINEX gain better understanding about the method. We choose FMNIST dataset for doing this since, LINEX/real under performs MeLIME in terms of the INFD measure here (see Table more heavily compared other datasets and wanted investigate the reasons for this. This also happens to be one the higher dimensional datasets that is intuitive to visualize and understand.
We start by observing that even though LINEX/real underperforms in the INFD metric, the gap is not so great in the GI metric, which suggests that MeLIME may be overfitting explanations here. We also note that in terms of CI, T, and CAC metrics, LINEX/real clearly outperforms MeLIME.
We now choose a sample of images from the dataset where LINEX/real has highest instance- level infidelity numbers and display them in Figure 23 Just looking at the explanations and the corresponding original images visually, is evident that LINEX/real highlights the prominent features like sleeves and collar shirt, handles of the bags, outlines the boots/shoes, even though the infidelity values are high. However, McLIME misses out some of these prominent features and
26

---

Original
LINEX
MeLIME
Original
LINEX
MeLIME
1.0
Original
LINEX
MeLIME
Original
LINEX
MeLIME
0.8
Feature Attribution
0.6
0.4
Original
LINEX
MeLIME
Original
LINEX
MeLIME
0.2
0.0
Figure 22: Results using realistic perturbations for CIFAR1O dataset. We see above images of dog. horse, truck, bird, boat and dog again randomly selected from CIFARIO. The original images greyed out here that the (normalized) attributions are clearly visible. As can be seen LINEX attributions seem to consistently focus on salient features as compared to MeLIME. For example for the first dog image we highlight the head, ears and leg, while MeLIME focuses more on the neck and some the background. For horse too LINEX focuses on head and body, while MeLIME focuses on the legs and neck. For truck both seem to focus important features. For bird LINEX hones in on the wings, while McLIME although giving importance to wings also attributes some of the background. The boat image LINEX focuses the center of the boat, while Melime the edges and some of the water around the boat. For the dog face image LINEX focuses on the nose, eyes and ears, while Melime focuses on the ears and neck.
focuses only on optimizing the local fit. The fact that LINEX zeroes in on important features also provides additional evidence for the closeness of GI metrics between the two methods, and the better performance of LINEX/real with CI, Y, and CAC metrics.
This conclusion is also verified when we look at the performance LINEX at class level. In Figure 24 we see two classes where the infidelity of LINEX is low (i.e. Trousers class) and the other where its infidelity is high (i.e Shirt class). As can be seen since the Trousers class has examples with less superftuous features (viz. varied designs) focusing
which might reduce infidelity but critical for determination of the class, LINEX does better in terms of infidelity on the prior. However, although infidelity is higher for the latter Shirt class does much better other metries such GI, CAC, CI and Y indicating that LINEX truly focuses on robust features.
J Ablation Analysis of Important Features for Various Explanation Methods
We wanted to analyze the most challenging case for us the reported experiments which on the FMNIST dataset where we are more worse than McLIME in terms of INFD than any of the other setups. We thus assess if the features deemed important those with the largest coefficients by the explanation methods are indeed important for the black box model to make their predictions. To assess this, we set the we set a fraction of features (pixel values) corresponding to the top coefficients of MeLIME and LINEX/realistic the black box model this is what we mean by ablation here. The baseline value here was chosen to -1 since that is the value of the background pixels. We then used two measures to assess quality of explanations higher values being better for both. The first measure is mean absolute error between the predicted scores before and after ablation, corresponding to the original predicted class. The second measure is the fraction of images that changed their predicted class after ablation. We
baseline value and run the modified images again through
27

---

Table Comparing the different methods (including SHAP) using metrics infidelity (INFD), gen-
eralized infidelity (GI), coefficient inconsistency (CI), class attribution consistency (CAC) and
unidirectionality (Y).
Dataset
Method
INFD 1
GI
C
T1
CAC 1
LIME
0.015 + 0.011
0.132 + 0.012
0.319 0.132
0.646 0.040
0.667 + 0.167
S-LIME
0.077
0.143
0.704
0.878 - 0.034
LINEX/rand
0.013 0.009
0.052 0.008
0.0113
0.802
0.921 0.042
NB/rand
0.040 0.010
0.067 + 0.003
0.319 = 0.132
0.646 0.040
0.667 = 0.167
IRIS
McLIME
0.008 0.000
0.049 + 0.018
0.219=0.11
0.464 0.100
LINEX/real
0.009 + 0.003
0.029 + 0.003
0.024 + 0.002
0.942 + 0.023
NB/real
0.058 0.022
0.034 0.000
0.219 + 0.108
0.629
0.013
0.464 0.100
MAPLE
0.009 0.001
0.038
0.004
0,261 0.033
0.458 0.032
0.586
0.035
LINEX/mpl
0.013 0.000
0.020 1 0.000
0.026 1 0.002
0.694 1 0.008
0.929 0.004
SHAP
0.007
0.197
0.248
0.664
0.524
LIME
0,158 + 0,066
0.214 + 0.041
0.005 = 0.001
0,981 = 0.006
S-LIME
0.158 + 0.066
0.214 + 0.042
0.005 - 0.001
0.974 = 0.008
NA
LINEX/rand
0.130
0.052
0.164 0.021
0.003 + 0.001
0.979 + 0.006
MEPS
NB/rand
0.275 0.062
0.311 + 0.079
0.005 + 0.001
0.981 0.006
MAPLE
0.063 + 0.000
0.067 + 0.000
0.007 = 0.000
0.957
= 0.000
NA
LINEX/mpl
0.098 1 0.001
0.094 T 0.001
0.007 T 0.000
0.950 1 0.000
SHAP
0.000
0.091
0.009
0.940
NA
LIME
0.162 + 0.003
S-LIME
0.142 0.003
FMNIST
NA
NA
NA
NA
LINEX/rand
0.149 0.002
NB/rand
0.207 + 0.000
McLIME
0.001 + 0.000
0.277 = 0.000
0.007 = 0.000
0.769 = 0.000
0.327 = 0.000
LINEX/real
0.100 0.002
0.304
0.001
0.002 + 0.000
0.780
0.000
0.649
0.001
NB/real
0.017 0.000
0.446 0.000
0.007 1 0.000
0.000 0.769
0.327 0.000
SHAP
0.000
1.962
0.589
0.551
0.038
LIME
0.191
0.005
S-LIME
0.185 1 0.002
NA
NA
NA
NA
CIFARIO
LINEX/rand
0.186 1 0.002
NB/rand
0.208 0.001
McLIME
0.100 0.003
0.412 0.007
0.014 = 0.000
0.546 = 0.003
LINEX/real
0.090 + 0.005
0.279 + 0.001
0.006 = 0.000
0.679 = 0 004
NA
NB/real
0.103 + 0.002
0.398 + 0.004
0.014 + 0.000
0.546 + 0.003
SHAP
0.003
1.376
0.398
0.512
NA
LIME
0.079 0.036
Rotten
S-LIME
0.075
0.035
NA
NA
NA
NA
Tomatoes
LINEX/rand
0.069 0.032
NB/rand
0.241 + 0.007
McLIME
0.029 + 0.001
0.391 = 0.000
0.000 = 0.000
0.999 = 0.000
0.909 = 0.000
LINEX/real
0.053 0.000
0.361
0.000
0.000 = 0.000
1.000
0.000
0.953
0.001
NB/real
0.035 0.000
0.535 + 0.000
0.000 + 0.000
0.999
0.000
0.909 + 0.000
SHAP
0.000
0.384
0.008
0.999
0.015
see from Figure 25 that LINEX/realistic substantially outperforms MeLIME in both these measures, clearly demonstrating the relevance of features chosen by our method to the black box.
K Error Analysis of LINEX based on Ablation
Highlighting stable features for examples near non non-lincarities is a key strength of LINEX. However, in some cases for examples near class boundaries it may ignore sensitive features as we show in this demonstration.
In Figure 26 we show 6 examples that are appear to be close to class boundaries. We ablate pixels corresponding to top 15% of important features chosen by MeLIME and LINEX/realistic using the approach discussed in Section | Ablation based on MeLIME importances meaningfully changes classes, whereas ablation by LINEX importances does not. The changes in prediction for MeLIME ablation for the six images are respectively from Dress to Trouser, Sneaker to Sandal, Pullover to Dress, Sneaker to Sandal, Bag to Pullover, and Sneaker to Sandal. The new class assignment looks
28

---

reasonable looking at the ablated images. We also see that the changes in class probabilities for the original class (p) are much higher after McLIME ablation compared to LINEX/realisiic ablation.
MeLIME ablated images for the first example has structures that look like trouser legs, for the second, fourth and sixth examples the area around the heel is more open making the original sneaker look like a sandal, for the third example, there is a hole in the hooded part of the pullover making it resemble a dress. The fifth example is classified as pullover possibly because of the elongated structures on the sides that look like hands.
Note that such cases of LINEX under performing are rare though is confirmed by its superior performance in Figure 25
L Understanding Behavior of LIME and LINEX with Synthetic Data
We consider explaining the behavior of a function of two variables æ and y with Class sandwiched between Class 0 (see Figure[7)) The third (or vertical) axis denotes the probability of being in Class Clearly, x is the only important feature here that determines the class label.
The
From Figure 27 (left), we see that the LIME (here McLIME would be the same as LIME since the space is flat and all points are realistic) feature attributions at points a, b, and will provide importance to x feature for small as well as large kernel width (1 and 2 respectively) neighborhoods. For point c, the interior of the Class O, the attributions are stable across kernel widths. However for points and b close to the boundary of classes, the attributions for small kernel width and large kernel width neighborhoods differ significantly along the direction. This shows the instability of LIME explanations near boundaries of classes for different kernel widths.
In contrast in Figure 27 (right), we see that the LINEX explanation constructed for the two kernel widths provides stable feature attributions for all points a, b, c. For a and 6, LINEX will conservatively pick a smaller feature attribution along the æ direction since the function changes rapidly in its neighborhood. As such though LINEX will still pick the feature in the x direction in this scenario.
M
Variation of feature attributions with Y
Based on the proof of Theorem D if for a feature the optimal attributions have opposite sign for each of the two environments, then 7 can be made arbitrarily small (except 0) large and the output of Algorithm [ should still be the same which is 0 as the Nash Equilibrium is 177, If the optimal attributions are the same sign then we should still get the same output from Algorithm I as long as y 2 min ([w (uzel) ) since the attribution from our algorithm is the minimum of those values. When y < min([wra) (w2()) then the feature attributions will smoothly reduce 7 reduces.
We demonstrate this behavior in Figure 28 using an example from the IRIS dataset with random perturbations using the same setting in Section 5 In the experiments in Section 5 we set 7 0.329 which is the maximum absolute value based on a linear fit to each environment. As increases beyond 0.329, the attributions are unchanged demonstrating robustness. Same holds true while reducing ? up to 0.165 beyond which we see smooth reduction in the attribution values. Qualitatively, similar behavior is seen for other examples too. Because we set y pessimistically (ignoring constraints) to high value, we can expect our reported performances in the paper to be robust across many values of y.
N Convergence of LINEX procedure and comparisons
We demonstrate based synthetic example how Algorithm I and provides unidirectional explanation. We generate synthetic data using a function in R² (Figure leltt). The function gently rises with increasing y values, and along it is flat first, then rises abruptly and then falls gradually. We want to obtain robust attributions of this function at the point x = 1.0, y = 0.0, which is close to the end of the rising edge along direction.
As we can imagine, since the slope changes abruptly along x direction near the point, it should be ideally excluded from an explanation intended towards recourse based on a linear proxy. Otherwise, the explanation will not generalize in the neighborhood of this point. On the other hand, the y direction should be included since the function changes smoothly along y throughout.
29

---

To generate explanations We first create two environments centered at the example to explain with variances 0.5 and 2.0. Now independently fitting these environments leads to feature attributions that are (-0.033, 0.098} and (0.084, 0.102). Appending the two environments the attributions are (0.029, 0.095). whereas with LINEX, the attributions would be {0.0, 0.093). Thus, LINEX effectively eliminates the feature with high variability or abrupt changes. The behavior of the coefficients for each environment as LINEX converges is shown Figure right,,, As such, one can also see the convergence is fast.
O Limitations
Like any other posthoe explainable AT method there is no way to surely say that LINEX exactly reflects the true reasoning behind black box classifier in arbitrary applications. It also is somewhat slower than LIME as shown in section A given the game theoretic nature of the algorithm, where its stability and unidirectionality hopefully offsets the additional time required. On the flip side, given its favorable properties in terms of recovering explanations could be used to violate privacy which may be concerning from social standpoint.
30

---

MeLime: r=0.121. NFD=0.001 UNEX/real: r-0.334, INFD-0.169
Original
MeLime: rw0.093, INFD=0.001 LIEE/real:: r-0.338, INFD=0.216
Original
UNEE/real: r-0.339,
Original
MeLime: r=0.114, NFD=0.001 LIEE/rral:: r-0.412, INFD-0.189
Original
Original
MeLime: r60.162, IND=+0.00 LIEEXreal:: r=0.528, INFD-0.161
Original
Figure 23: Error analysis for chosen set of examples in FMNIST using McLIME and LINEX/real methods. The three columns are the McLIME feature attributions, LINEX/real feature attributions, and the original images. The rows correspond to different examples. We show the Pearson's 's correlation coefficient between feature attributions and mean of the original images from the respective classes (r) and instance- level infidelity (INFD) measures. LINEX seems highlight important features like stripes the t-shirt, handles the bags, outlines of the boots/shoes more prominently, while MeLIME seems overfit to the data while missing out highlighting some key features prominently.
31

---

Trouser class less infidelity (INFD)
Shirt class more infidelity (INFD)
Figure 24: We see above that infidelity is lower for Trousers class for LINEX as compared with the Shirts class. A reason for this that the trousers are more plain with less superfluous features such as the different designs in shirts. Since LINEX focuses on robust features focusing excessively on the designs is not critical for it determine shirt, albeit focusing infidelity. Advantage of it relying on robust features is however apparent when we look at other metries such GI, CAC, CI and T seen in Table where is much closer to superior McLIME.
these designs might reduce
Mean absolute error
ablated probs)
0.5
LINEX/real
MeLIME
Average predicted class changes
0.5
LINEX/real
MeLIME
0.4
(original and
0.3
0.2
0.1
0.1
0.0
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.00
0.05
0.10
0.15
0.20
0.25
0.30
Fraction important features ablated
Fraction important features ablated
Figure 25: Ablation analysis determine the features deemed important by the explanation methods are actually considered important for prediction by the black box model. We see that features chosen by LINEX impact the prediction the black box model much more than those chosen by MeLIME. This is true with respect to both MAE measure (left) between the predicted probabilities before and after ablation for winning (or argmax) class, and the change in predicted classes (right) before and after ablation. Higher values here mean that the features chosen by the explanations are more relevant for the black box to make its predictions. The maximum value of both measures is 1.0.
32

---

peb
VeLime Coofts
IMFXimed Coefss
Origial p-6.9500 da.
NcJME ablato p-0 1-0.004.
UNEsecal ab p=0.5137 d.
UNExireal Coofts
Original pmo 9105,
shaae pnD 5450,
LIMIXtowal pmnl 8:16,
Coefs
9905,
MeJME 4782,
UNEKeea 9862.
Vetime Cooffs
LIMEXmmd Coelis
Originl p-0.9228
NeLME ablite p-0
UNEKeeal ablite p=8 2858. d.
Orighal- p-0
p-n
Figure 26: Error analysis for chosen set of examples in FMNIST using MeL.IME and LINEX/realistic methods, using ablation important features. Each row shows results for a particular image. The columns show the: (a) MeI.IME. coefficients, (b) LINEX/realistic coefficients, (c) the original image along with its predicted class (cls.) and predicted probability for that class (p), (d) the image after MeLIME ablation along with the predicted probability for the original class (p) and the new class prediction (cls.), and (e) the image after LINEX/realistic ablation along with the predicted probability for the original class (p) and the new class prediction (cls.). The changes in prediction for MeLIME ablation for the six images are respectively from Dress to Trouser, Sneaker to Sandal, Pullover Dress, Sneaker Sandal, Bag to Pullover, and Sneaker to Sandal. No changes in classes are seen for LINEX ablation.
33

---

Class
Class
0.8
0.2
0.0
0.0
a
Class
Class
y Class
Class 0
Figure 27: LIME (left) and LINEX (right) feature attributions for three points (a. b, c) for synthetic data where we have Class sandwiched between Class O. For LIME, the different colors pink and blue correspond to feature attributions obtained with the small and large kernel width neighborhoods. Note how explanations for LIME change significantly (in magnitude) by kernel widths near the class boundaries, whereas the LINEX explanation remains stable, where it still picks up the important feature.
0.2
Wo
feature attribution
W1
0.1
W2
W3
0.0
-0.1
-0.
0.1
0.2
0.3
0.4
0.5
0.6
Figure 28: Feature attributions for the four features for an example in the IRIS dataset are shown above when varying 7. We used the same setting in Section 5 this experiment. The attributions increase smoothly as y increases and stay constant after y 2 min(/wid, [W2i))Vi.
34

---

Environment coefficients
0.3
1.5
0.2
W1.1
W2.5
0.5
W2.1
0.0
-0.1
-0.5
-0.2
y
0.3
20
40
60
80
100
120
140
Iterations
Figure 29: Left side: Explaining scalar function in I22 at the point indicated by the triangle. The point is centered at r 1.0, y 0.0. The environments created by sampling multivariate normals with variances 0.5 and 2.0 respectively (samples not shown) centered at this point. Right side: Convergence individual environment attributions. The attributions for first feature (z), $1.0 and W2,0, converge and -y leading to the optimal attribution of 0. For the second feature (y) the optimal attribution (Wi,1 + W2,1) converges positive value.
35

---

0.335
0.045
0.045
0.040
0.035
0.025
0.000
0.025
0.023
0.200
0.020
0.355
0.15
0.015
30
35
Weighborhood size
Neighberhood size
Neighborhood dize
(a) INFD- S-LIME mean smoothing
(b) INFD S-LIME median smoothing
(c) INFD S-LLIEE------ MoM
smoothing
0.250
0.25
0.250
0.225
0.200
0.225
0.775
0.175
0.10
0.25
0.150
0.125
0.100
0.125
0.035
10
25
20
25
30
30
40
45
50
10
20
25
50
Neighborhood size
(e) GI -S--I-- median smoothing
Reighborhood
(d) GI S-LIMEE mean smoothing
(f) GI S-LIME MoM smoothing
0.35
0.30
0.35
0.25
0.35
0.20
0.20
0.20
0.35
0.15
10
15
20
25
45
50
Neighborhood
10
15
20
25
30
35
60
50
10
20
25
30
35
40
45
50
Heighborhood
(h) CI S-LIME median
Neighborhood size
(g) C1 S-LIME mean smoothing
smoothing
(i) CI S-LIME MoM smoothing
0.78
0.76
0.74
0.72
0.70
0.72
0.70
2.85
2.70
3.66
0.64
10
15
20
25
30
40
45
50
Neighborhood size
50
25
30
Neighborhood Bize
(k) S-LLIMEE median
Neighborhood size
(i T- S-LIME mean smoothing
smoothing
(l) Y S-LLIEE MoM smoothing
0.95
0.55
0.50
0.90
0.50
0.75
0.70
0.75
0.65
0.70
0.70
20
30
35
Neighborbood size
Neighborhood size
Neighborhood size
(m) CAC- S-LIME CAC-S-LIME mean smoothing
(n) CAC S--LI--MME... median smoothing
(0) CAC-S-LIME, S-LIME MoM smoothing
Figure 30: Effeet various smoothing schemes on S-LIME's performance based on environments (since median-of-means (MoM) just median for 2) with the same setup described Suppl. D. for the IRIS dataset. As can be seen median and MoM perform worse than the mean on INFD and similar on other metrics. Thus, this does not change the takeaways from the main paper. See Figure in the supplement for legend.
36


Reviews:
[{"review_id": "EIPqvkTAED", "reviewer": "Reviewer_uF3q", "summary": "In this paper, the authors put forward a local, attribution-based explanation method that fits a local, explainable surrogate (a linear model in this case) to perturbation output of the original model.  In essence, this is exact scenario as the immensely popular LIME explanation method; however, this work puts forward LINEX which seeks to improve on the robustness of LIME (where robustness is measured as Fidelity, Stability, Invariance, and a new property put forward as Unidirectionality). LINEX proceeds by learning a collection of linear classifiers, each fitting to a different perturbation “environment” and the authors provide an interpretation of their least-squares fitting approach as a multiplayer game. In addition the authors provide some minor theoretical analysis (Theorem 1) which justifies the modeling choices allowing them to give an intuition for why their method works well.", "questions": "Can the authors further elaborate precisely what they mean by “perform bootstrap sampling to create k different environments.” I would like to understand exactly how is this done step-by-step such that you get such an incredibly meaningful difference between the output of your method and that of S-LIME.\n\nWhy is there a trailing 1 in Equation (2)?", "limitations": "See weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper provides clear motivation for the need for its method, provides a straight forward development of the method, and provides salient theoretical and experimental arguments for the method. \n\nThe experimental evidence in favor of the method is strong, and the method is simple enough that I expect it could be widely adopted into post-hoc explanation tools without too much experimental effort.\n\nThe paragraph “Implications of Theorem 1” is nice as it allows the reader to very easily digest an interpretation of why Algorithm 1 achieves the goal of the method.", "weaknesses": "The method seems to rely on the diversity of the “environments” in a way that is quite unclear to me. Simply picking gaussians with different covariances seems like it will not give rise to the desired benefits of the method (i.e., it is unclear that simply selecting an ensemble of random environments should be enough to improve over using a single superset random environment). I understand that in general we the method picks the lowest magnitude attribution, which can in turn provide greater stability. We observe, indeed, in table 1 that the method provides little benefit in the cases of FNIST, and CIFAR 10, where perhaps these random environments are not enough. However, in IRIS and MEPS, the random environments have significantly better performance than S-LIME, and I am having trouble fully understanding why this is the case. (See questions section). \n\nWhile I understand the authors general point about the desirability of unidirectionality, it seems like it is already generally satisfied in LIME, S-LIME, and MeLIME. The only place LINEX has a considerable advantage in unidirectionality is on IRIS (and to some extent CIFAR). Perhaps to underscore this point, the authors could run experiments on something like Adult or any other financial dataset where their motivating example for using recourse is relevant and see if there is a considerable difference. To be clear, I am not suggesting the authors carry out this experiment during the rebuttal phase, but I am simply stating that having a more clear experimental example demonstrating  the importance of unidirectionality would be good in future versions of the paper.\n\nThere are several works in robustness of explanations (albeit gradient-based and not LIME-based) that are very related to this work but are not included as prior works:\n[1] Dombrowski et. al. - https://arxiv.org/abs/2012.10425\n[2] Wicker et. al. - https://arxiv.org/abs/2212.08507\nThese are just two of the more recent works that cover robustness of grad. Explanations. I think the more seminal work might be a single, sufficient citation to provide readers with more context: \n[3] Dombrowski et. al. - https://proceedings.neurips.cc/paper/2019/file/bb836c01cdc9120a9c984c525e4b1a4a-Paper.pdf\n \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for realizing the potential of our approach. We now address your concerns.\n\n> Reliance of LINEX on the “diversity” of environments\n\nTypically when using IRM environments are given. One of our contributions here is proposing simple alternatives to create them for our problem. In our case, we just want sufficient diversity between environments so that the un-important features for explanations vary significantly across environments. This will let LINEX weed them out and preserve only the stable/persistent features. We found empirically that just setting different environments to random bootstraps from the base environments produced good results. It seems like this simple procedure is sufficient to induce necessary diversity across insignificant features. Note that our method is agnostic to the way environments are created and users can create them in other ways as well if it suits their problem better.\n\n> Performance with IRIS, MEPS, CIFAR10 and FMNIST\n\nWe show benefits in the stability measures - CI, $\\Upsilon$, CAC - which are either same or better for all the datasets. This is true even for CIFAR10 and FMNIST that the reviewer mentions, where LINEX/real is better than MeLIME in 4 out of 5 cases and similar in one case.\n\n> Advantage of LINEX in unidirectionality\n\nTaking your suggestion we ran experiments on a finance dataset. In particular, we trained a rule learning model (Dash et al Boolean Decision Rules via Column Generation, ICML 2019) on the HELOC dataset provided by FICO. This model won the FICO explainability challenge and had 74\\% accuracy. Out of the 24 features the model highlighted three features namely ExternalRiskEstimate, NetFractionRevolvingBurden and MSinceMostRecentDelq. Using the same setup as for IRIS we ran experiments for the rand case (results averaged over a random 20\\% test set) and found the following: For LIME, S-LIME and LINEX respectively, INFD was 0.017, 0.016, **0.012**; GI was 0.087, 0.069, **0.049**; CI was 0.097, 0.086, **0.041**; $\\Upsilon$ was 0.671, 0.719, **0.911** and CAC was 0.632, 0.793, **0.902**. As can be seen we not only outperformed the competitors on unidirectionality but also other metrics in this case. \n\n> Inclusion of prior works\n\nThanks. We will include the two Dombrowski et al. papers and Wicker et al. in the final version. \n\n> Detailed method for bootstrap sampling between to create k different environments \n\nFor both S-LIME and LINEX, we create multiple ($k$) sets of perturbation neighborhoods (environment) using bootstrap sampling of the base perturbation neighborhood (base environment). For S-LIME, we compute multiple LIME explanations (one for each environment) and average them, for LINEX we use Algorithm 1 to obtain a single explanation from the $k$ sets. Thus, both methods have the same starting point.\n\nCreating k environments:\n1. First generate a single base environment of size (number of examples) $= n$.\n2. Repeat the following procedure $k$ times to create $k$ bootstrap samples:\n\n    a. Create an index set of size $n$ which is randomly sampled with replacement from the base index set $\\{1, \\ldots, n\\}$. \n\n    b. The examples in the base environment corresponding to the randomly drawn index set corresponds to a bootstrap sample.\n\n> trailing 1 in Equation (2)?\n\nWe will remove this to improve clarity."}, {"review_id": "jtaaq0UMus", "reviewer": "Reviewer_Rtbi", "summary": "Explanation methods are known to be unstable with flickering attributions on inputs with mild perturbations.\nThis work addresses the explanation instability problem by re-posing it as computing attributions that are invariant across different environments (that are obtained through input perturbations).\nTheir proposed scheme exploits Nash Equilibrium guarantees for convex objectives (of LIME) to obtain an explanation scheme with some desirable properties, which they also demonstrate empirically through multi-modal evaluation.\n\nAlthough I found the idea interesting, I did not like the story and have some critical concerns regarding their evaluation. I elaborate them below.", "questions": "1. Baselines and ablation. The problem resembles robust mean estimation. I would like to comparisons with the following baselines:\n   1. S-LIME but with attributions clipped at $[-\\gamma, \\gamma]$.\n   2. S-LIME but with attributions aggregated using median instead of mean.\n   3. (1) + (2)\n   4. Median-of-Mean estimation instead of mean estimation with S-LIME without increasing the number of function evaluations.\n   5. (1) + (4) \n2. Metrics.\n   1. Has CAC been used before? I cannot understand well why/how the mean vector matching indicates recourse utility.\n   2. What happens if we slightly change the defn. of GI to aggregate $|y_b(x') - y_e^{x'}(x')|$? Although similar to INFD, we would then be able to check if the estimator is simply smoothing the explanations while the underlying model is not that smooth.\n3. Theoretical analysis and explanation. LINEX performed well on CAC and CI metrics, but I do not understand what is contributing to the improvement. We need ablation study to understand the rrelative contribution of different aspects of LINEX: (a) $\\gamma$ clipping, (b) setting non-zero attribution ($w_i$) only when $\\sum_e \\frac{|w_{ji}|}{w_{ji}}>0$ etc., (c) setting attribution value to the smallest among environments. In other words, a crisp intuitive explanation for why NE leads to empirical gains helps.\n4. Figure 3 is hard to follow. LINEX too is highlighting features in the background.", "limitations": "I do not see them mentioned anywhere.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Datasets used for experimental evaluation span various modalities: Image/Text/Tabular.\n- Connection with NE (Nash Equilibrium) is refreshing and the algorithm is simple.\n- Theoretical insight: their theorem is intuitive and I like that their estimator regresses all disagreeing attributions to 0, which is clean.", "weaknesses": "1. Connection to IRM. I do not see any connection to IRM (Inv. Risk Minimization) setting or method except for the fact that they both use \"environments\" of some kind. Neither does their estimator borrow techniques from IRMv1 algorithm nor does it impose \"invariance\" across environments. In that regard, I found their story muddled.\n2. Game theoretic perspective. The paper also did not justify well why we should view the estimation problem from game-theoretic standpoint. More specifically, why does the utility function as defined in L230 lead to an explanation method with desired properties. Why should the environments be viewed as agents in a game with competing objectives (and limited resources) at all? \n3. I have many evaluation concerns that are described in \"questions\".\n4. The paper is not easy to read because the story is cluttered (first two points), contributions and motivation not straight-forward.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that you found our idea to be interesting. Below are our responses to your concerns.\n\n> Connection to IRM\n\nBesides the aspect of environments which you mentioned being similar to IRM, citation [4] mentioned in the paper is a game theoretic algorithm to solve IRM. IRMv1 which was mentioned in the paper that introduced IRM is actually an approximation to the original problem and also much slower than the game theoretic version in [4]. As mentioned in the related works section this work and [3] which also address the OOD problem are inspirations for our current approach and hence quite related to IRM. Our approach which automatically cancels features that have different sign attributions in the 2 environments making the explanation invariant to those features is analogous to canceling out spurious features in IRM.\n\n> Why Game theoretic perspective\n\nThe main motivation for this is possibly answered in our response above. Framing of the explanation problem in this novel way naturally leads to properties that we have mentioned in the paper (viz. unidirectionality, stability), which is not the case (provably) with other methods. Please also see lines 227-231 in the paper.\n\n> Readability: Contributions, motivations\n\nWe address the IRM connection and game theoretic perspective in the previous responses. Our differentiation is discussed in the second paragraph of related work. We will add the above clarifications to the final version.\n\n> The problem resembles robust mean estimation. Baselines and ablations\n\nOur approach is *not* estimating the mean. Even with 2 environments if a feature has same sign attributions it will go towards the lower (absolute value) attribution. While for opposite sign attributions it will tend towards 0. For more environments as discussed in the Supplement C the behavior depends on if there are odd or even number of environments. This type of behavior is very different than robust mean estimation.\n\nNonetheless, we have experimented with the variations of S-LIME you suggested on the IRIS dataset and the **results are in a pdf document uploaded as part of the global response above**. In particular for, \n\n1. *S-LIME but with attributions clipped at $[-\\gamma,\\gamma]$:* We do not report additional results since the behavior is the same as reported in the paper. This is because as mentioned in Supplement D $\\gamma$ is set based on the maximum absolute coefficient found for LIME. So the clipping is trivial for S-LIME (i.e. coefficients do not change).\n\n2. *S-LIME but with attributions aggregated using median instead of mean:* These are reported in the uploaded pdf. In summary, this leads to worse results on INFD and qualitatively similar behavior for the other metrics (when compared with the mean).\n\n3. *(1) + (2):* Since (1) doesn’t affect the coefficients this is the same as (2).\n\n4. *Median-of-Mean estimation:* These are again reported in the uploaded pdf. In summary, here too results are worse for INFD and qualitatively similar for the other metrics (when compared with the mean).\n\n5. *(1) + (4):* Here again since (1) doesn’t affect the coefficients this is the same as (4).\n\n> Metrics: Significance of CAC\n\nCAC is a stability metric and Unidirectionality is the one meant for recourse. CAC checks whether certain important features are highlighted across most of the explanations of a class making it a reasonable stability metric where there is little rotation or shifting of the input.\n\n> Changing definition of GI to aggregate $|y_b(x')-y_e^{x'}(x’)|$ to check if explanations are being incorrectly smoothened?\n\nThe GI definition we have in the paper is a stronger metric to check for incorrect smoothening than the suggested change. If the explanations are incorrectly smooth then explanations of neighboring examples will incur a higher penalty (i.e. high GI) when applied to the input. This will be more pronounced than applying to the example itself on which the explanation methods optimize to find an explanation. In any case, INFD checks for quality of explanations applied to themselves at a global scale, which we have reported. We found your suggested metric to give the same values (up to third decimal) as INFD.\n\n> Theoretical analysis and explanation for good performance of CAC and CI metrics\n\nThe reason why LINEX performs better in CAC and CI metrics is mainly because LINEX can recover stable explanations. Stability falls out of our algorithm which weeds out features that change across the environments. It is reasonable to believe that within a class (CAC) and in the neighborhood of an example (CI), there will be common features that are representative of the model predictions.\n\n> relative contribution of different aspects of LINEX: (a)  $\\gamma$ clipping, (b) setting non-zero attribution only when  sign is $>0$, (c) setting attribution value to the smallest among environments.\n\nThe aspects you mention above are *not* independently applied in LINEX. The $\\ell_{\\infty}$ norm constraint ($|\\tilde{w}|\\le \\gamma$) in Algorithm 1 implicitly leads to the (b) and (c) behaviors mentioned by you above. This is the power of LINEX, where this simple penalty we add leads to such desired behaviors. This is what we prove in Theorem 1.\n\n> More clarity on Figure 3 \n\nThe attributions of LINEX for background pixels are small (yellow/red) as opposed to MeLIME.\n\n> Specification of Limitations\n\nThis is provided as the last section of the supplementary material."}, {"review_id": "H91gbEvGR2", "reviewer": "Reviewer_bruB", "summary": "The paper proposes Locally Invariant Explanations (LINEX) as a variation of the well-known LIME explanation method. While LIME is widely used in interpretability, it has been demonstrated to be dependent on the sampling procedure to create neighbouring points as well as the choice of the explanation model. The manuscript aims to mitigate the dependence on the sampling procedure by combining LIME with invariant risk minimisation. \n\nThe method is evaluated on various datasets, such as IRIS, Fashion MNIST, CIFAR10, Rotten Tomatoes, as well as Medical Expenditure Survey and compared to number of previously proposed neighbourhood selection procedures. Both qualitative and quantitative comparisons using a number of metrics are discussed and it is demonstrated that the proposed method leads to a statistically albeit mild improvement.\n\n", "questions": "- In L 302, it is stated that SHAP is not a \"natural fit\". Why is this so?\n- What was your logic for selecting the particular kernel sizes in L317?", "limitations": "Limitations are addressed briefly but adequately in the conclusions. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The proposed neighbourhood selection mechanism seems reasonable and theoretically grounded. \n- The quantitative experimental analysis is through. I particularly like that t-tests are used to evaluate statistical significance. \n- Experiments cover various datasets and modalities. ", "weaknesses": "- The proposed method modifies the neighbourhood sampling procedure of LIME and is thus rather limited in scope. \n\n- The paper is a very hard read. This is not because the covered material is particularly unaccessible but rather a result of a suboptimally structured and at times rather confusing presentation. I will list a few concrete suggestions of how to improve the structure. I want to encourage the authors to thoroughly revise the presentation. This would make the ms a much more accessible and valuable contribution.\n\nConcrete suggestions for improving structure:\n- Explain IRM in more accessible manner (either in the main text or appendix). For example, an environment is currently not properly defined. Furthermore avoid imprecise mathematical definitions such as \"the expectation \\mathbb{E}_e is defined w.r.t. the distribution over points in the environment\" where it is not obvious what is meant by \"distribution over points in the environment\".\n- I find the brief introduction to the Nash equilibrium very hard to parse (L 134-145). For example, the utility is defined over joint set actions but in L141 it takes a player k as an input. \n- Metrics for evaluation, as outlined in Section 4.1, should be moved to the experimental section. Separate paragraphs with corresponding equations and a brief explanation for each of the metrics used in Table 2 should be added.\n- Assumptions 1 and 2 are hard to parse. Assumption 1 is rather convoluted and should be split up into at least two sentences. Assumption 2 should clearly state that t and \\gamma are thresholds and refer to their definitions. \n- Similarly, refer to the definitions of the environment generation distribution in Definition 2 and explain what is meant by |.| in the indicator functions of equation 2.\n- The proof sketch L264-277 is very hard to follow and adds little to the overall presentation. Consider to not include it. \n\nMinor suggestions for improving writing:\n- L28 reads as if the doctor is given a cancer diagnosis. I think what is meant is that a patient receives a cancer diagnosis and the doctor has to validate it?\n- L57 - L63 is rather convoluted. Splitting this up in separate sentences would help.\n- There are some ill-placed whitespaces such as in L302.\n- Be consistent with abbreviations, e.g. Supplement vs Suppl. \n- Avoid a.k.a. in favour of i.e. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your suggestions in improving the structure of our paper. We are also glad that you liked the approach and our experimental evaluations.\n\n> Scope: modifying the sampling scheme of LIME\n\nLIME is one of the most widely used explanation approaches and being model agnostic is applicable across many settings and domains. Given that our method is also model agnostic and provides simple and practical alternatives to create environments we believe our approach will also be widely adopted especially given the stability and unidirectionality benefits. For instance, recently it has been shown that explanation stability is an important requirement for different stakeholders that perform tasks such as model improvement, domain learning, adapting control and capability assessment (see Figure 2 in Vera et, al. Connecting Algorithmic Research and Usage Contexts: A Perspective of Contextualized Evaluation for Explainable AI, AAAI HCOMP 2022).\n\n> Describing IRM in a more accessible manner\n\nWe will discuss IRM and environments with an example in the final version. We define “distribution of points in the environment” in lines 121-122, so the statement we make regarding expectation with respect to this distribution in lines 126-127 is we believe grounded.\n\n> Nash equilibirum definition in Lines 134-139\n\nThe utility of player $i$ depends on their strategy $\\bf{s_i}$ as well as the strategy of the rest of the players $\\bf{s}_{-i}$. In Definition 1, we define pure strategy Nash Equilibrium, which “identifies a state where each player is using the best possible strategy in response to the rest of the players leaving no incentive for any player to alter their strategy.” (quoted from Line 142-143 of the paper). The $k$ in line 141 is “any other strategy” that will lead to suboptimal utility for the player $i$ if it were used in place of strategy $\\bf{s}_i^{\\dagger}$. We are happy to discuss this more using an example in the Supplement.\n\n> Metrics for evaluation should be moved to experiment section\n\nWe will do this in the final version.\n\n> Other presentation/stylistic/minor suggestions\n\nAssumption 1: We will rephrase this as “The feature values for each of the dimensions in the samples created *while* forming the local environments are independent.”\n\nAssumption 2: We will refer back to the definitions of $t$ and $\\gamma$ in Algorithm 1.\n\n> Minor suggestions\n\nWe will address the other stylistic/minor suggestions in the final version.\n\n> SHAP not a natural fit (line 302)\n\nSHAP is not a natural fit here, since all the other explanation methods we list in Table 2 use some perturbation neighborhood to compute explanations, whereas SHAP does not.\n\n> Choice of kernel sizes in line 317\n\nThe size ($\\tau$) of 0.75 was used in LIME code base as the default value. We chose fractions of it to make the kernel even more local. "}, {"review_id": "LlAVkWulCG", "reviewer": "Reviewer_aw9L", "summary": "This work extends [LIME](https://arxiv.org/abs/1602.04938) to generate stable and unidirectional feature attributions through the [invariant risk minimization framework](https://arxiv.org/abs/1907.02893). Their method, LINEX, ensures that it follows the desiderata of faithfulness, robustness to neighborhood sampling, stability (similar to neighbors), and the proposed unidirectionality (closeby examples have the same sign for its attributions). They design LINEX as a concave game (pure Nash equilibrium always exists), thereby ensuring stability and unidirectionality. In the experiments, they show that they can find feature attributions that stay consistent to its neighbors across various modalities (tabular, image, text) and mostly outperform baselines.", "questions": "- How is t is set during the experiments? Does it violate Assumption 2?\n- Are the results for MeLIME correct for CIFAR results since their attributions often just seem to be flipped from LINEX?", "limitations": "The limitations are adequately addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The (concave) game theoretic design of the feature attribution method is novel and sound.\n- The unidirectionality desideratum is original and very sensible.\n- The theoretical results provide sound support for their design of the proposed feature attribution method.\n- The proposed method empirically improves upon previous query-based methods.\n- Stable & robust feature attributions, such as generated by their proposed method, are important for researchers as well as practitioners to gain better insights into black-box models.\n- The paper is clearly written and easy to follow.\n- Code is provided.", "weaknesses": "- The largest weakness of this work is missing any (novel) qualitative insights into how model work (e.g., similar to Sec. 6.3 and/or 6.4 of [LIME](https://arxiv.org/abs/1602.04938)). The present submission only contains comparisons to previous works and does not show any interesting application of their approach to understand models.\n- While unidirectionality may be a valid property for most cases, there will be edge cases for which minor differences for close by examples may be discriminative (e.g., a person that has paid back previous loans and another has not, while all other features remain the same).\n- The trustworthiness of the proposed feature attribution method is not shown. It would be helpful to conduct a user study similar to Sec. 5.4 of [LIME](https://arxiv.org/abs/1602.04938). \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for highlighting the strengths of our approach. We now address your concerns.\n\n> qualitative insights into how models work\n\nWe provide several qualitative insights in last paragraph of Section 5 and in appendices I, J, . Please also look at Figure 25.\n\n1. Figures 2 and 3 show LINEX explanations are more coherent and highlight more salient features compared to MeLIME, and in Table 1 (text data), where LINEX highlights features that are reasonable for the sentiment.\n\n2. Supp. I (Figure 23) - Using FMNIST data we qualitiatively show that LINEX/real highlights prominent features (such as sleeves and collar in a shirt, handles of the bags, outlines of the boots/shoes) better than MeLIME, even when the infidelity values are high.\n\n3. Supp. J (Figure 25) -  Using ablation with FMNIST data, we show that the features deemed important by LINEX/real (those with the highest coefficients) are indeed important for the model prediction compared to MeLIME. We show that setting the important features to baseline value produces a larger change in predicted classes for LINEX/real compared to MeLIME.\n\n> edge case for unidirectionality: minor differences for close by examples may be discriminative\n\nOur method has better unidirectionality overall, and we agree that there may be corner cases like the reviewer mentions where higher unidirectionality need not necessarily be desirable.\n\n> trustworthiness using a (simulated) user study\n\nThe experiment in Supp. J (Figure 25) demonstrates the trustworthiness of the explanation. Since we claim LINEX to be a better post-hoc explanation compared to the baselines, one of the characteristics we expect is that setting the features deemed important by LINEX to some baseline value must substantially reduce the performance of the model. This is exactly what we show in this experiment using ablation with FMNIST data and comparing LINEX/real to MeLIME.\n\n> How is t is set during the experiments? Does it violate Assumption 2?\n\nAs mentioned in the supplement for the tabular datasets (IRIS and MEPS) we ask for 5-sparse explanations while for the others where MeLIME is relevant we adopt its setup. Thus, $t$ is set accordingly. This leads to Assumption 2 being violated for the tabular datasets, but not for the others. Nonetheless, we mostly perform either better or similar to the competitors on the different metrics even on tabular.\n\n> Are the results for MeLIME correct for CIFAR results since their attributions often just seem to be flipped from LINEX?\n\nWe checked again and the attributions are correct. They are not necessarily flipped but just not that correlated. For instance in Figure 3, i) for the dog image in most cases when LINEX is blue (high significance) MeLIME is yellowish-green (moderate significance) and ii) for the bird image LINEX correctly highlights the most of the birds wings in blue, while MeLIME highlights also the wings in blue but also the much of the background."}]

Author rebuttal:
We thank all the reviewers for their constructive comments. We are glad that you found our work to be an **interesting idea**,  that could be **widely adopted**, having **clear motivation**,  with **straightforward development**, **strong experimental evidence**, **easily adaptable into post-hoc explanation tools**, **reasonable and theoretically grounded** and **clearly written**. We now individually address your concerns.

Meta-review: In this manuscript, the authors introduce a novel approach to address the problem of local explanation, notably by incorporating elements of invariance and game theory into their explanatory models.

Post-rebuttal evaluations have been diverse. After a thorough review of the manuscript, the supplementary materials, and the rebuttal, it is evident that both the reviewers and I find the integration of invariance and game theory into explanatory models to be an innovative contribution. However, I also echo some of Reviewer Rtbi's concerns regarding the paper's lack of clear motivation, especially in its handling of invariance. A subsequent discussion period among the reviewers led to the resolution of some, but not all, concerns.

As such, I recommend accepting the paper and I hope that several critical revisions should be addressed in the camera-ready version. The key issues primarily pertain to the concept of invariance:

1. Clarify the role of invariance as a motivating factor for the proposed method. Given that the method draws inspiration from the Invariant Risk Minimization (IRM) game, rather than IRM, an in-depth explanation of the IRM game's relevance is warranted.
2. Elucidate how the proposed algorithm identifies invariant structures without resorting to a learned representation function. Current literature on IRM and the IRM game often characterizes invariant structures through a learned representation function, a feature notably absent in this manuscript.
Decision: Accept (poster)