Is this the Right Neighborhood? Accurate and Query Efficient Model Agnostic Explanations
Authors: Amit Dhurandhar
Karthikeyan Natesan Ramamurthy
Karthikeyan Shanmugam
Venue: NeurIPS 2022 Accept (2022)
Keywords: explainable AI
adaptive sampling

Abstract: There have been multiple works that try to ascertain explanations for decisions of black box models on particular inputs by perturbing the input or by sampling around it, creating a neighborhood and then fitting a sparse (linear) model (e.g. LIME). Many of these methods are unstable and so more recent work tries to find stable or robust alternatives. However, stable solutions may not accurately represent the behavior of the model around the input. Thus, the question we ask in this paper is are we approximating the local boundary around the input accurately? In particular, are we sampling the right neighborhood so that a linear approximation of the black box is faithful to its true behavior around that input given that the black box can be highly non-linear (viz. deep relu network with many linear pieces). It is difficult to know the correct neighborhood width (or radius) as too small a width can lead to a bad condition number of the inverse covariance matrix of function fitting procedures resulting in unstable predictions, while too large a width may lead to accounting for multiple linear pieces and consequently a poor local approximation. We in this paper propose a simple approach that is robust across neighborhood widths in recovering faithful local explanations. In addition to a naive implementation of our approach which can still be accurate, we propose a novel adaptive neighborhood sampling scheme (ANS) that we formally show can be much more sample and query efficient. We then empirically evaluate our approach on  real data where our explanations are significantly more sample and query efficient than the competitors, while also being faithful and stable across different widths.

Is this the Right Neighborhood? Accurate and Query Efficient Model Agnostic Explanations
Amit Dhurandhar IBM Research
Karthikeyan Natesan Ramamurthy IBM Research
Yorktown Heights, NY, USA
Yorktown Heights, NY, USA
adhuran@us imm. com
knatesa@us imm. com
Karthikeyan Shanmugam'
IBM Research
Yorktown Heights, NY, USA
kart harthaleyyassuuumuug@@@@@1g11... com
Abstract
There have been multiple works that try to ascertain explanations for decisions black box models on particular inputs by perturbing the input or by sampling around it, creating a neighborhood and then fitting a sparse (linear) model (e.g. LIME). Many of these methods are unstable and so more recent work tries find stable or robust alternatives. However, stable solutions may not accurately represent the behavior the model around the input. Thus, the question we this paper is are approximating the local boundary around the input accurately? In particular, are we sampling the right neighborhood so that a linear approximation of the black box is faithful to its true behavior around that input given that the black box can be highly non-linear (viz. deep relu network with many linear pieces). It is difficult to know the correct neighborhood width (or radius) as too small a width can lead to a bad condition number of the inverse covariance matrix function fitting procedures resulting in unstable predictions, while too large width may lead to accounting for multiple linear pieces and consequently a poor local approximation. In this paper, propose simple approach that is robust across neighborhood widths in recovering faithful local explanations. In addition to a propose naive implementation of our approach which still be accurate, a novel adaptive neighborhood sampling scheme (ANS) that we formally show can be much more sample and query efficient. We then empirically evaluate our approach on real data where our explanations are significantly more sample and query efficient than the competitors, while also being faithful and stable across different widths.
Introduction
Explainable artificial intelligence (XAI) has come to prominence in recent years with the proliferation of deep learning technologies, which are inherently black box, across various facets of society [13]. Regulations such as the General Data Protection Regulation (GDPR) [31] in Europe demand explana- tions to be provided for automatic decision making systems that affect humans. The explanations demanded are typically local in the sense that we want explanations for individual decisions rather than for the entire system, which could also be much more challenging. Given this need many local
Author's 's current affiliation is Google Research India. Work was done while at IBM Research.
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

explanation methods have been developed [26, 21, 6, 24, 33] that can be used to explain arbitrary models, i.e. are model agnostic. Even though plethora of these methods exist it not clear if they are truly faithful to the underlying black box model. Most of these methods employ some type of sampling or perturbation scheme to estimate a simple interpretable model (viz. a sparse linear model), which can then be read off to ascertain explanations. Because of the inherent randomness of such procedures the most important question is are we learning the right (local) interpretable model? This essentially boils down to are we using the right samples for the estimation?
In this paper, we argue that sampling neighbor- hood just based on the input values and using it for estimation can lead to a poor local approximation of the black box function. This also applies when samples are generated from an underlying data man- ifold [2]. which is oblivious to the black box's be- havior. As such, we propose a novel neighborhood sampling scheme called Adaptive Neighborhood Sam- pling (ANS) which generates ncighborhood taking into account the local bchavior of the black box. Our main idea is to estimate the region where the black box model is (approximately) linear around the input we want to explain followed by adaptively sampling in this region still respecting the original sampling process/distribution The estimate of the relevant lin- ear region will be done using much fewer black box queries than say a total budget of N. As it will turn out our sampling process will result in many more samples in the desired region hence minimizing query wastage compared with simply querying the black box N times, finding the relevant region and then fitting a sparse linear model. Query efficiency is im- portant as it has been argued in recent works [5, 18] that in todays multi-cloud environments each query can have an associated monetary cost not to mention factors such as inference time, power consumption and network latency in a distributed system need to be taken into account.
0.22
0.20
0.18
0.16
0.14
0.12
0.10
0.08
0.00
0.25 0.50
1.00 1.25 1.50 1.75 2.00 kernel_width muitiplier
0.75
ANS-Basic
S-LIME
ANS
MeLIME
LIME
Figure 1: We show the variation of Infidelity (INFD) measure over various kernel width multiplier values for the proposed methods (ANS and ANS-Basic) with CIFARIO dataset. Lower values of this measure are better. At very small kernel widths, INFD actually goes up indicating instability. Hence in lieu of choosing arbitrarily low kernel widths, we need explanations that are accurate over many kernel widths, which is provided by our meth- ods. More details are in the experiments sec- tion.
An illustration of our approach is shown in Figure 1. While it can be argued that very small kernel widths. which corresponds to considering only extremely close samples in the sparse linear estimation, can be chosen to circumvent the problem of choosing the right neighborhood, we show that this can lead to instability (high infidelity). Hence it is important to find methods that work well across multiple kernel widths. This achieved by our methods (ANS, ANS- -NS-Ba addition, choosing the right neighborhood also leads to high sample and query efficiency for ANS.
In the rest of the paper, we repeatedly use the terms faithful and stable with respect to the explanations. What we mean by faithful is that simple models (viz. sparse lincar) built using these explanations should closely replicate the behavior of the black box model on the corresponding examples. This corresponds to low infidelity (INFD). By stability (unless mentioned otherwise) we mean for different kernel widths we should recover similar quality explanations. This corresponds to lesser variation in INFD and coefficient inconsistency (CI), both of which are defined in Section 4, across kernel widths.
2 Related Work
There have been many works trying to uncover local explanations in model agnostic settings [26, 33, 6, 21, 25]. Local explanations also do not have to be feature based and could also be exemplar based [14]. There are also methods that provide both forms of explanations [24]. Some methods in a sense stitch together local explanations and create global ones [25, 23J. Although there are many methods there is still a need to design explanation methods that are faithful and stable [12]. This is

---

particularly true for LIME like neighborhood sampling methods where stability and faithfulness w.r.t. neighborhood width is highly desired [32] as it is difficult to predefine an optimal width.
Some recent works try to accomplish improved stability for certain modalities such as tabular [15] through adversarial training. This notion of stability however is across examples sampled from linear shifts in the distribution. Others assume access to partial causal graph [10, 17] and build on top of SHAP to create stable feature attributions. Stability here is achieved by trying to obtain attributions that are as consistent as possible with respect to the provided partial graph. Another popular strategy to learn the data manifold and then sample from it [2, 29] or project onto [1] creating more faithful explanations. The premise here is that the realistic sampled neighbors will give rise to better explanations. There are other works that aim for stability and unidirectionality [6] the explanations, by proposing new algorithm for fitting rather than modifying the sampling scheme. Hence the methodology in [6] is complimentary a sense to our contribution and could potentially benefit from the neighborhood sampling scheme proposed in our current work.
The conceptual contribution of our work to realize that manifold or not, examples sampled in a neighborhood could belong to different linear parts in non-lincar function such as deep relu network and hence using them obtain a local explanation through sparse linear or some other simple model fitting can be misleading.
Algorithm 1: Adaptive neighborhood sampling (ANS). Estimation of and b can also be performed not just once but multiple times and the latest estimates can be used for future sampling. For realistic perturbations sampling can be done in the latent space. More details in section 3.1.
Input: Example to explain μe, black-box predictor f(.), maximum number of neighbors generated N, standard deviation and number top features output l:
Set # Examples to query
Sample n <<< N) examples from (11, and query f())
Find region [a,, b,.] that corresponds to f using MPLSR methods [9, 7] on the samples Add to Q samples that lic in [an, bn]
Estimate uncertainty a # Could be set 1 or based on stability of the region (i.e. p) vn
Sample N n examples from N (ap + (1 - a) anttbm,0?
Add to Q samples that lie in (an; bn)
Query f-) on these additional samples added to Q Fit interpretable model (viz. sparse linear) ((.) to (ær, f (x)) where
Output: Top k coefficients of ((.)
3 Method
We now describe our approach. In terms of notation vectors are bolded. Matrices are also bolded and in capital letters. Inequalities and assignments indicated for vectors and matrices are element wise.
3.1 Description
As mentioned before, if you consider the black box function to be piecewise linear (viz. deep relu network) our main idea is to sample neighborhood around input μ such that the neighbors belong to the linear piece corresponding to it. Since any continuous black box function can be arbitrarily well-approximated by piecewise linear function [20] and hence our setup is quite general.
Typical neighborhood sampling schemes such as those for LIME and its variants [2, 33, 6] (i.e. ambient or latent space) can be seen to sample from independent Gaussian distribution M(u, o² where a the standard deviation for each feature (or kernel width) and μI is d dimensional example want to explain. It is difficult to find the correct a as too small can lead to numeric instabilities during function fitting because of a bad condition number of the inverse covariance matrix, while too large a will not accurately capture the local information [32]. So pertinent question is, can
3

---

devise neighborhood sampling procedure that captures local information and is (largely) robust across different values of a??
Main Idea: Our idea is to leverage multidimensional piecewise linear segmented regression (MPLSR) schemes [9, 7] assist in this endeavor. These methods will learn a piecewise linear function identifying boundaries of each linear piece, One simple (or naive) solution for our problem using these methods would be to i) sample N neighbors using N (n,, o² I2) ii) run MPLSR on these samples to find the boundaries of the linear piece corresponding to μa, iii) sclect only samples that belong to this region and iv) train sparse linear or some other interpretable model only on the selected samples followed by outputting the important features. Although this approach captures our general idea, it has two sources of inefficiency; i) Low sample efficiency: If la close to the boundary of the range (a, bj in which it lies, then the naive sampling scheme will have many samples lying outside the range leaving much fewer valid samples to train an interpretable model. ii) Low query efficiency: The naive scheme requires us to query the black box N times, but only small fraction of these samples may lie within the desired range, as previously mentioned.
Given this, in algorithm we propose an adaptive neighborhood sampling (ANS) scheme which aims to enhance both these efficiencies. 3.2. Our idea is to sample small set of examples n similar to the naive scheme. However, we then run MPLSR and find an estimate of the true range [a, b) given by (an. bn). Depending on our uncertainty in the estimate denoted by a E [0, we sample from an updated distribution N (au + (1 a) Satba r²I). The intuition behind the updated distribution is that if we are highly uncertain (i.e. a i) about the range then we want to be conservative and sample close to μ. However, if we are confident x O, then we want to sample close to the middle of the range so that we get (many) valid samples belonging to the correct linear piece that corresponds to μ..
Algorithm| 1:
detailed analysis is given in Scction
For realistic perturbations using autocncoders one can sample in the latent space, find the (lincar) region in the input space by decoding the current neighboring samples followed by updating the mean of the sampling distribution as indicated in algorithm and then passing it through the autoencoder to find its corresponding latent to sample around.
Estimating a: a could be estimated in at least a couple of ways: i) Since the error of MPLSR [7] schemes in terms of n scales v we could set α Vi ii) One could also perform subsampling or bootstrap sampling on the n samples?, run MPLSR on each such sample and compute a (normalized) metric indicative of the variability in estimating the range (a, bj. For instance, one could use the overlap coefficient [30] p as an indicator of the stability of the range. Given bootstrap samples
with corresponding estimated ranges using MPSLR being [a b,('),,... aan (mm) b((²)] and their
corresponding volumes being 01, Dj...., 12 respectively. if ih denotes the volume of the intersection of
these ranges (i.e. volume of [a b(22 b Jn...
(m² ((m)))) then the overlap coefficient would be (m)
In
P min ..., 3
(I)
The coefficient would be indicative of how stably we can estimate the range, where if we get the exact same ranges for the m bootstraps, P will be 1, while if the ranges had little overlap, p would be close to O. Our uncertainty a can then be set to p.
3.2 Analysis
We now analyze our approach in terms of sampling efficiency, query efficiency and time complexity.
3.2.1
Sampling Inefficiency
The sampling inefficiency or the expected number of iterations to get a valid sample in the range (a, b] based on a naive implementation of our idea which is described in the previous subsection (lets call it (NN--Baii) that involves sampling from the original distribution A ((,, (2, I) would be Pize[a,6] If we sample n examples based on the original distribution then the sample efficiency will be the
e Note this will not require additional queries to the black box.

---

same for these examples. However, for N - n examples if we sample using the proposed distribution
N (au + (1 a) anttbn o² I) the sampling inefficiency will be (.
P. (me b,,])
(a where (.) denotes the (cumulative) probability w.r.t. the proposed distribution. Thus, the relative sampling inefficiency 81 will be as follows:
Inefficiency of ANS
$1 Inefficiency of ANS- Basic
N-n N Po (mE N P(æc a. b]]
P(
N P(x E (a, bl)
N N (a E [a, bl)
When (i.e. high uncertainty of range) (a E b)) P(æ E [a, bl) and hence our efficiency is the same as sampling from the original distribution. However, for smaller a, (.).) should significantly increase making our procedure much more sample efficient especially when the range is large and μ is far away from the center of the range. Hence,
P(x E la, bl) In
a
b
(3)
Pa ea,
2
Ideally, we would want to choose an n where equation 2 minimized. Finding the optimal n in closed form is difficult. Note that there is tradcoff for different values of n. Too large will lead us to sample very few points from our proposed distribution thus mitigating its benefit. Too small a n might lead to high uncertainty (i.e. close to 1) in estimation of the range (a, bj which will again increase $1. However one could in practice choose a reasonable n depending on the dimension the data. One could also evaluate the quality by looking at (random) subsets or bootstrapped samples of the queried n instances, fitting the linear piecewise methods and evaluating the stability of the obtained partitions, which is similar one of the methods proposed to estimate a.
Further, one does not only have to perform the estimation of the ranges once but can do so periodically updating the estimates for and b. The relative inefficiency analysis in this case also should naturally extend. For instance, if we estimate the ranges r times producing the corresponding a during the gih estimation at intervals of n4 respectively with fr+1 = N 1== n4 and Pa, (x: E [a, b)) P(x E (a, b)), then the relative inefficiency 87 would be,
(r)
1 N
P(x E ()) n4 Pa (x b))
where, (1)) can be denoted as simply 8I. We expect that we would get better estimates of the range for
later iterations i.c aj S a; Vj > and hence Pa, (a E [a, b)) 2 Pa. (x E [a, b)) leading to higher efficiency for examples sampled later stages. Óf course the larger the more the computational complexity, as we have to run the piecewise linear routine r times.
3.2.2 Query Efficiency
What up until now the efficiency in sampling examples within the range. Interestingly however, the (relative) black box query efficiency likely to be much higher. The reason for this is that with ANS we need only query those examples that are accepted by our sampling scheme as opposed to querying all the examples as in the naive sampling case. The efficiency of naive sampling thus still P(æ (a, bl), while for us the accepted examples after sampling N times which in expectation will be (N - Pa E [an, bn]) will definitely lie within [on, bn]] and hence the
probability they will lic in [a, b] is given by (a, - Note that the region [a, b] will not be underestimated based on finite samples i.c. [a, b) C (an, bn] given a good piecewise linear method, and hence the ratio of probabilities mcaningfully represents the probability of accepted samples lying
(xE(abb)
5

---

in (a, b). The reason for this is that our sampling can never add not existent non-linearities as this is just function of the black box model, but may miss regions where the linear piece corresponding to ends. Hence, the total relative query efficiency EE of ANS is,
P(x E E b)) + N-n (e(eba).)) N TL
N Pa Pa(aElan bn))
q
P(æ E b))
N n1 N Pa(x E (an: bn P(( E b)
Pa(x (a, b))
(5)
The gain can thus be large when we are quite certain of the range (i.e. small a) for not too large a n and Pa (aae[a.bb)) the black box model is highly non-lincar since, P. (#rE (mE [a]] will be close to 1 and P(x E [a, bj) will
in all likelihood be small. Similar to equation 4, here too the above analysis can be straightforwardly extended to multiple estimations of the range where the a would be replaced by the corresponding on for the 7h estimate.
3.2.3 Time Complexity
The additional time complexity for ANS over LIME comes from having to run MPLSR methods [9, 7] which have complexities such as Onnd log n) or (ndd). However, this time could be reduced across examples through embarrassing parallelism [16]. Moreover, efficient heuristics maybe used to speed up such partitioning schemes I]. Interestingly though, with deeper models where inference time is not insignificant the lower query complexity of ANS can more than compensate for the additional time it requires running the MPLSR schemes. We see evidence of this in the experiments.
If we use p to estimate a we may not have to estimate it per example, but we could estimate it for a few examples and then the maximum of those values (if we want to be conservative) could be used for other examples we want to explain for given n. This will save on time as the amortized complexity over many examples will be similar to running MPSLR schemes just once per example to find the range (an bn]. rather than multiple times.
4 Experiments
We now empirically evaluate approach. We compare ANS with ANS-Basic, LIME and Smoothed- Lime (S-Lime) on two commonly used labular datasets IRIS [4] and HELOC [8], where the latter was the dataset used in the FICO explainability challenge. We also experiment on CIFARIO 10 [19] where an additional baseline Melime [2] is compared with. The black box models for the tabular datasets random forest classifiers consisting of 100 trees that have accuracy of ~ 100% and 78% on IRIS and HELOC respectively, which is state-of-the-an The black box model for CIFARIO is ResNet- 18 which has accuracy of ~ 95%. Except CIFAR10 10 which comes with its own test we randomly split the other two datasets into 80% train and 20% test. For 10 randomly selected examples in each test set we performed bootstrap sampling 20 times for the respective n, estimated (an, bn] and calculated a based on the overlap coefficient p as defined in equation 1. The maximum of those values was the a used for all the examples.
Given our goal of showcasing that the ANS (and ANS-Basic) neighborhood generation procedures elevate given proxy model explanation scheme with generated neighborhoods we believe LIME, S-LIME and Melime to be good basclines which validate our idea on random as well as realistic neighborhoods. Methods such as SHAP [21] and MAPLE [24] do not really fit in here as they do not perform proxy model fitting on generated neighborhoods. Moreover, saliency based methods such as gradcam, saliency maps, layerwise relevance propagation also do not fit in our framework since they are white-box explanation methods.
Metrics: We now define evaluation metrics that we use to evaluate methods in this paper. The five metrics we use are Infidelity (INFD) [26), Generalized Infidelity (GI) [25), Coefficient Inconsistency (CI) [15], accepted sampling complexity (ASC) and query complexity (QC). INFD and GI evaluate fidelity of the explanations. CI evaluates stability. ASC and QC evaluate the sample and query efficiency respectively.

---

0.25
5,12
0.20
0.20
0.11
0.10
INP
0.10
0.02
0.12
0.05
0.07
0.10
3.25
6,50
0.75
1,50
1.25
1.75
2.00
0.2
0.6
0.6
0,8
3.0
1.2
14
3.00
0.25
0.50
0.75
3.00
1:25
1,50
1.75
2.00
kornelwwdth, hinnt_.wtnmmuuttlller muutippiirr
kernel_wiäth, multiplier
kornel_width, muttiplier
0.50
0.2725
0.45
0.2675
0.2650
0,2600
0.2915
0.30
0.38
0.2915
1.00
1.25
1.75
0.2
0.4
0.5
1.0
0.25
1.25
Wemee__wdthhmmmllee multillee
korno__withhmmuttiiii
Mernel_wlthh_mmittpeee
1.150
0.021
0.125-
0.020
0 012
1000
010
0.75
0.00
0.036
0.25
0.50
5.75
1:00
1,25
1,30
L.75
2,00
0.2
0.6
0.5
0,5
1.0
1.4
0.00
0.25
0.30 5,73
1.00 1.5
1.75 2.00
kemee wiith widdiiiimmmimpppiee
multiplior
kemel width multiplier
5000
5000
5200
4500
4500
4000
4000
3500
3100
3500
3000
2003
2507-
1500
0.25 0.50
0.75
3,02
1.25 3.50
1.75 2.02
0.
0.4
1.8
0.25
0.50
0,75
1.00 1.25
1.75
2.00
Kamel width multipller
kemee width multipler
kamel wwt.:wiiditttpppeee multiplier
4500
4500
4000
4000
3500
3500
3300
3000
2500
kerte__widt_mman multiplier
ANS-Basic
ANS
LIME
S-LIME
MeLIME
Figure 2: Various metrics kernel width multiplier (kwm) for Iris (left), HELOC (middle), and CIFAR (right) datasets. The metrics are (from top to bottom each row): Infidelity (INFD), Generalized Infidelity (GI), Coefficient Inconsistency (CI), Accepted Sample Complexity (ASC), and Query Complexity (QC). For all metrics lower values are better. The method legend is at the bottom.
If (ær, y) denote examples in test set D.. Let ys (b())) be the black box models prediction input and y. (x)) be the prediction denote the feature attributions and the test/real neighborhood of æ with |-leard denoting cardinality. With have the following definitions.
applying the explanation model æ'. Also let of and Nr
Infidelity (INFD): We define infidelity as the mean absolute error (MAE) between the explanation and black box model over the test set. INFD Dilers E(ny)),, 1Va (x))
v. (z)].
Generalized Infidelity (Gl): Based on previous works we define GI as: GI
Dellon E(RMDED Walen ExreN, (bs(x) v (æ))

---

Horse
ANS
ANS-Basic
1.0
0.8
Feature Attribution
Melime
0.6
0.4
0.2
Lime
0.0
S-Lime
kwm=0.1
kwm=1
kwm=2
Figure 3: Qualitative explanations for image from the CIFAR dataset for three different kernel width multiplier (kwm) values. The feature attributions of our proposed method ANS (and even ANS-Basic) are much more stable and accurate over different kwm values compared other methods as the face of the horse is highlighted for different kwms. This is not the case for the other methods. More examples in the supplement.
Coefficient Inconsistency (CI): CI can be defined the MAE between the attributions of the test points and their neighbors: CI DDlton E(E,)ED, [. lam Ex'EN,
J0E c 11-
ASC: This just the total number of samples used train the local sparse linear models. For ANS and ANS-Basic they are the accepted samples. While for other baselines is just N.
QC: This is the total number of queries made by the methods to the black box model.
We report the results in Figure The results show the behavior of the different metrics for dif- ferent kernel width multiplier (kwm) used to weight the random or real neighbors i.e. kum (0.05, 0.1, 0.25, 0.5, 0.75, 1, 1.5, 2}. n 0.2N, where N 5000 which is the typical neighborhood size for LIME. a was found for 10 random examples and the maximum of those values was used across other examples in the dataset. Real test neighborhoods are not natural to find random perturbation based neighborhoods for CIFAR10 as superpixels may vary between neighbors. Hence, GI and for CIFARIO are only reported for realistic neighborhoods generated by Melime. In this case procedures are also run these real neighborhoods. More details about explanation generation are in the supplement. We used 56 core and 242 GB RAM LINUX machines to run the experiments.

---

LIME
S-JIME
1-5
A.
0,01
LINE
S-UIE
ARS-Beoic
AR5
0.334
6,2
640
642
602
Cosf
-033
-038
Peoture cames
Pooture
Peatern
kwm=0.1
kwm=0.75
kwm=
Figure 4: For two examples in the Iris test corresponding to the provide feature attributions for sepal length (sl), sepal width (sw), petal length and petal width (pw) for three different kernel widths (0.1, 0.75, 2.0). Each row is separate example and each column corresponds to the method indicated in the title of the subfigure. We can see that across different kernel widths ANS-Basic and ANS feature attributions much more similar than those seen for LIME or S-LIME. As such, LIME and S-LIME feature attributions even seem to change signs in some cases, while ours do not.
of figures above,
Observations:
We from Figure that ANS and ANS-Basic in general are significantly more accurate than the competitors across kernel widths. ANS while being similar in accuracy and even sample efficiency to ANS-Basic is significantly better in query complexity. The sample efficiency can possibly be improved by considering larger n. The only places where we seem to be worse than the competitors are on GI and CI for the HELOC dataset. We believe the reason for this is that the classification task is much harder for this dataset 95%) possibly resulting in a highly non-linear decision boundary. This makes the explanations even for neighbors different than the original example, resulting in higher GI and CI values even if the explanation for the particular example is correct. The correctness of the local explanation reflected by us having lower INFD value, although GI and CI maybe higher.
ofttte--ftthearr accuracy only 78%) as compared with the others (>
The average time taken by LIME for each explanation is about 0.5 seconds, while our methods take about second for the tabular datasets which use random forests. However, for CIFAR 10, LIME using ResNet-18 takes about minute while ANS takes around 50 scconds showcasing the benefit of reduced query complexity. With deeper models this is slated to improve even further. In any case, additional time for our methods in some cases is probably worth it given the higher accuracy and the fact that local explanations are independent and hence can be parallelized.
Qualitatively too in Figures 3 and 4 observe that ANS produces much more stable and intuitive explanations compared with other methods. ANS- is slightly less stable than ANS but still better than the competitors.
Discussion
Rather than piccewise linear regression one could also perform piecewise polynomial regression for decision boundaries with high curvature, which will be more computationally expensive, but rejection sampling method and analysis should be applicable in that context too.
Our proposed approach is distinct from typical rejection sampling schemes [3] where proposal distribution is rilted and used to sample from the desired distribution. The reason we do not subscribe to these standard schemes in our case is that these schemes are mainly used in two settings: i) when we are not able to sample from the original distribution or ii) when we want to sample from tails of the original distribution. Both of these conditions are not met in our case since sample in regions which include the mean (i.c. highest probability density) while having access to these distributions.

---

There are also motivations for our approach based on causality and practical behavior of neural networks.
Causal motivation: It is known that given a structural causal model (SCM) [22], the best sparse model captures the Markov blanket i.e. parents and children in a causal graph of the variable to be estimated. In the post-hoc explanation setting the target variable Y has no children as the black box model is of the form y = f(x). Hence, if the black box i.c. f() is linear lasso it could recover the causal parents for some regularization parameter. However, in the non-linear sctting, one could have a case where multiple linear pieces explain the causal relationship in different parts of the domain. If one tries to fit a linear model, gradient for one piece with respect to one feature might (approximately) cancel the gradient with respect to another piece for the same feature because the weights are of opposite signs. This could lead the linear model missing some (causal) parents when explaining the variance in y. However, if we are able to identify the correct (linear) regions, then a simple lasso-like fit in each such region should be able to uncover the correct causal parents overall. This work may also motivate a notion of locally causal, which may be useful in practice, beyond the standard formalisms of causality [22, 27] which are predominantly global.
Simplicity bias motivation: In a recent paper [28]. investigating the reasons for neural networks fitting to spurious correlations in the in-domain data resulting in poor generalization, the authors argue that this because of the simplicity bias of neural networks. That is, the networks pick the simplest boundary to separate classes which could simply be linear separator on one feature. However, in the test data, the optimal separator could based on a more complex decision boundary. Hence, one would ideally want to capture the true complexity of the decision boundary. The definition of complexity they use to analyze arbitrarily complex decision boundaries is closely related to the number of linear pieces that would make up different decision boundaries. This formalization thus further motivates our ANS and ANS-Basic approaches, which identify the appropriate linear component based on piccewise linear decision boundary.
The explanations that we obtain are more accurate in many measures with lower sample and query complexity than standard baselines as we discuss in the experiments. However, like other black box posthoc explainability methods is difficult to say with certainty that the provided explanations are in fact the "true" explanations. Additionally, the performance gains of our approach are contingent on the quality of the MPLSR schemes. case the ranges are incorrect the estimation may reduce to standard LIME quality explanations. Luckily, this is likely to only happen when the ranges are overestimated and we include neighbors belonging to different linear pieces, since in the opposite case of underestimation we should still have neighbors belonging to the correct linear piece. In general though, the MPLSR implementations seem to be reasonably mature which is reassuring.
In summary, we have proposed a novel neighborhood generation approach that is adaptive and is robust across different kernel widths, much more so than other methods. We have theoretically shown the benefit of this scheme compared with naive implementation of our idea where our main proposal likely to be sample but more so query efficient. This is further validated through real data experiments where our approach is more accurate quantitatively as well as qualitatively.
Acknowledgement
We would like to thank Sara Magliacane and Kartik Ahuja for helpful discussions at the beginning of this project.
References
[1] C. J. Anders, P. Pasliev, A.-K. Dombrowski, K.-R. Muller, and P. Kessel. Fairwashing ex- planations with off off-manifold detergent. In Intl. Conference on Machine Learning (ICML), 2020.
[2] T. Botari, F. Hvilshøj, R. Izbicki, and A. C. P. L. F. de Carvalho. Melime: Meaningful local explanation for machine learning models, 2020.
[3] G. Casella, C. P. Robert, and M. T. Wells. Generalized accept-reject sampling schemes. Institute of Mathematical Statistics, 2004.
[4] D. Dheeru and E. Karra Taniskidou. UCI machine learning repository, 2017.
10

---

[5] A. Dhurandhar, T. Pedapati, A. Balakrishnan, K. A. Pin- Yu Chen, Karthikeyan Shan- mugam, and Puri. Model agnostic contrastive explanations for structured data. http://aaaiv.orr/ass//96..00
2019.
[6] A. Dhurandhar, K. Ramamurthy, K. Ahuja, and V. Arya. Locally invariant explanations: Towards stable and unidirectional explanations through local invariant learning. arXiv:2201.12143, 2022.
[7] I. Diakonikolas, J. Li, and A. Voloshinov. Efficient algorithms for multidimensional segmented regression. arXiv:2003. 1086, 2020.
[8] FICO. Explainable machine learning challenge. www.--ac-n---eaaaannaaaaaalleeea
https://communityy: com/s/ /
2018. Accessed: 2018-
10-25.
[9] E. Frank, Y. Wang, S. Inglis, G. Holmes, and H. Witten. Using model trees for classification. Machine Learning, 1998.
[10] C. Frye, C. Rowat, and I. Feige, Asymmetric shapley values: incorporating causal knowledge into model-agnostic explainability. NeurlPS, 2020.
[11] M. Garofalakis, D. Hyun, R. Rastogi, and K. Shim. Efficient algorithms for constructing decision trees with constraints. In Proceedings of the Sixth ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '00, page 335-339. Association for Computing Machinery, 2000.
[12] A. Ghorbani, A. Abid, and Zou. Interpretation of neural networks is fragile, 2019.
[13] D. Gunning. Explainable artificial intelligence (xai). In Defense Advanced Research Projects Agency, 2017.
[14] 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 Data Mining, 2019.
[15] L. Hancox-Li. Robustness in machine learning explanations: does it matter? In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency. ACM, 2020.
[16] M. Herlihy and N. Shavit. The art multiprocessor programming. Elsevier, 2012.
[17] T. Heskes, E. Sijben, 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.
[18] A. Ilyas, L. Engstrom, A. Athalye, and J. Lin. Black-box adversarial attacks with limited queries and information. Intl Conference on Machine Learning. 2018.
[19] A. Krizhevsky. Learning multiple layers of features from tiny images, 2009.
[20] Z. Lu, H. Pu, F. Wang, Hu, and L. Wang. The expressive power of neural networks: view from the width. Advances in Neural Inf. Proc. Systems, 2017.
[21] S. M. Lundberg and S.-I. Lee. A unified approach interpreting model predictions. In Advances in Neural Information Processing Systems, pages 4765 4774, 2017.
[22] J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2000.
[23] T. Pedapati, A. Balakrishnan, K. Shanmugam, and A. Dhurandhar. Learning global transparent models consistent with local contrastive explanations. Advances in Neural Inf. Proc. Systems, 2020.
[24] G. Plumb, D. Molitor, and A. Talwalkar. Model agnostic supervised local explanations. In Advances Neural Information Processing Systems, page 2520-2529, 2018.
[25] K. N. Ramamurthy, B. Vinzamuri, Y. Zhang, and A. Dhurandhar. Model agnostic multilevel explanations, 2020.

---

[26] 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, 2016.
[27] D. Rubin. Causal inference using potential outcomes. J. Amer. Statist. Assoc,, 2005.
[28] H. Shah, K. Tamuly, A. Raghunathan, Jain, and Netrapalli. The pitfalls simplicity bias in neural networks. Advances in Neural Information Processing Systems, 33:9573-9585, 2020.
[29] A. A. Shrotri, N. Narodytska, A. Ignatiev, J. Marques-Silvee K. S. Meel, and M. Vardi. Constraint-driven explanations of black-box (ml) models, 2021.
[30] M. K. Vijaymeena and K. Kavitha. A survey on similarity measures in text mining. Machine Learning and Applications, 2016.
[31] P. N. Yannella and O. Kagan. Analysis: Article 29 working party guidelines on automated decision making under gdpr. 2018. htpp://www.cbberadvisrrbbl wwtpblllg..oooo// com/201 29-working-por wwworking-partt-aoe partt- suidelines-on-automaeedd www.ddeiiiiioiooinneeeoeoeeeeeee wawakiingunder--ee /anlsss-aasss--riccceee
[32] Y. Zhang, K. Song, Y. Sun, S. Tan, and M. Udell. Why should you trust my explanation? ICML-AI for Social Good, 2019.
[33] X. Zhao, W. Huang, X. Huang, V. Robu, and D. Flynn. Baylime: Bayesian local interpretable model-agnostee explanations. UAI, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
12

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "dv-84d3z5PC", "reviewer": "Reviewer_8rcz", "summary": "Many local explanation methods have been developed for explaining black box models in a post hoc fashion. These methods first sample around the example to be explained and build a linear model using the samples to form an explanation. However, the challenge in these schemes is that we do not know if we are sampling the right neighborhood around the example. If the neighbourhood is too small, the linear fitting can be unstable due to a bad condition number and if the neighborhood is too large, the function that these methods approximate may not be linear. This work provides an adaptive sampling procedure where they first estimate the linear region around the example using a few samples and then sample within that region only taking into account the uncertainty of the estimate. This work then shows using experiments on a few tabular datasets, that their procedure is much more query efficient and sample efficient and leads to stable predictions across multiple widths of sampling.  ", "questions": "The related work section does not mention any previous work which also does adaptive sampling of the neighborhood, I wanted to clarify if this is the first work which does the adaptive sampling of the neighborhood. \n\nThe stability with respect to kernel widths is shown in the figures in the appendix. I see that Melime is also quite stable across different widths. Can the authors please comment a little more on the Melime method?\n\nI also want to clarify if the metrics shown in the graphs are averaged over all test examples.", "limitations": "The authors have adequately discussed the limitations of their work. They have showed that their explanations are much more stable across different sampling widths but as pointed out by the them, there is no way to check if the explanations are more accurate. Moreover, the correctness of their method depends on MPLSR schemes and if the range of the linear segment is found to be incorrect in these schemes, the quality of explanations may degrade. They have also pointed out that their methods is slower as compared to the vanilla methods and have also given a dataset example where their performance is weaker than the vanilla methods.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The method proposed in this work seems like a very natural and simple idea which gives improvement over the existing methods. The explanations are stable over different widths which is what was desired. \n\nOne weakness is that this method is slower because the method involves running MPSLR schemes and the accuracy of the method depends a lot on the correctness of MPSLR methods. The method is also somewhat complicated to implement and involves choosing multiple hyper parameters like n, \\alpha. \n\nThe paper is generally well written and clear. \n\nThere could be more discussion on the related work. It would be nice if there were more details on how different methods achieve stability in their methods. Also, stability and faithfulness have been mentioned multiple times but it is not clearly defined anywhere what do the authors mean by that. I am guessing stability is defined as the change in explanations as the sampling width increases. But, in any case, these terms should be clearly explained in the beginning.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dmuUikECKPg", "reviewer": "Reviewer_15VB", "summary": "This paper proposes a technique called adaptive neighborhood sampling scheme (ANS) to make local explanations more faithful, stable, and sample query efficient. ANS is built on multidimensional piecewise linear segmented regression (MPLSR) to indentify boundaries of each linear piece.", "questions": "(1) for Cifar10, how do you sample neighbors? in input image space or feature space?", "limitations": "(1) It would be better if the author can provide some qualitative examples on the Tabular datasets.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n(1) The motivation is clear and the method to use MPLSR is solid to identify linear pieces. \n\n(2) Experimental results show the better fidelity and sample efficiency of the proposed methods.\n\nCons:\n\n(1) I think this paper needs to give a formal definition of \"stability\" and \"faithfulness\".\n\n(2) It would be easier for readers to understand the metrics if the author can explicitly indicate for each metric whether it is higher the better or lower the better.\n\n(3) According to figure 2, for HELOC dataset, it seems that ANS-Basic and ANS are worse than the baselines wrt GI and CI. Also for CIFAR-10, a comparison to LIME is missing. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "NPYMtJUPLxW", "reviewer": "Reviewer_hHAF", "summary": "This paper is on improving explainability techniques for machine learning models. A popular technique is based on local linear models that make a locally linear approximation of the ML model around a provided input example for which an explanation is sought. Local linear approximations make use of random samples from around the provided input example to estimate the linear model. However, having samples too close to the input can affect the condition number of the covariance matrix, while on the other hand having the samples spread out too much can lead to an unfaithful model. \n\nThis paper proposes a strategy that chooses the samples in an adaptive manner to ensure that the samples span the locally linear region of the model, leading to a more reliable model. Experimental evaluation shows better performance compared to other locally related baselines. ", "questions": "NA", "limitations": "NA", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n\nThe proposed method samples points adaptively thus not requiring to set a sampling variance.\nThe method also takes into account the uncertainty of the estimated values a_n, b_n for improved robustness. Experimental evaluation shows that it leads to a better performance w.r.t. to a variety of performance metrics.\n\n**Weaknesses**:\nI do not work in explainability for ML, however it seems that the contribution is a minor improvement (the sampling strategy) over existing approaches. As such, the approach is not so novel, in my opinion, even though experimentally it is beneficial.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8SHaeoRw0D3", "reviewer": "Reviewer_6LhD", "summary": "The paper proposes a rejection sampling method for neighborhood-based explanation methods including LIME. It argues that existing neighborhood-based explanation models are quite unstable in terms of the the neighborhood width, which is the boundary range for the local neighborhood and the mean value of a Gaussian distribution where the local neighborhood follows. In order to make the choice of neighborhood width insensitive, it first samples several data points (n) to compute the range $[a_n, b_n]$ and an uncertainty score $\\alpha$ to adaptively learn the neighborhood distribution from $N(\\mu, \\sigma I)$ to $N(\\alpha \\mu + (1-\\alpha)\\frac{a_n + b_n}{2}, \\sigma I)$. Then the LIME algorithm is applied for fitting an interpretable explainable model. It also analyses the sample efficiency and query efficiency compared to a naive version, showing that the method is query/sample-efficient.  ", "questions": "- It would be nice if the variance can be provided in Figure 2 to show the performance of the proposed method is stably outperforming other methods.\n", "limitations": "The limitation is not discussed in the paper.  ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths\n    - The proposed method is intuitive and relatively clearly explained.\n    - The experiment shows that the method is simple and effective.\n    - Efficiency analysis is covered in terms of sampling, query and training MPLSR.\n- Weakness\n    - The experiments are limited to small-scale datasets.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept