Consistent Counterfactuals for Deep Models
Authors: Emily Black
Zifan Wang
Matt Fredrikson
Venue: ICLR 2022 Poster (2022)
Keywords: deep models
deep networks
explainability
counterfactual explanations
consistency
consistent predictions
model duplicity
random initialization

Abstract: Counterfactual examples are one of the most commonly-cited methods for explaining the predictions of machine learning models in key areas such as finance and medical diagnosis. Counterfactuals are often discussed under the assumption that the model on which they will be used is static, but in deployment models may be periodically retrained or fine-tuned. This paper studies the consistency of model prediction on counterfactual examples in deep networks under small changes to initial training conditions, such as weight initialization and leave-one-out variations in data, as often occurs during model deployment. We demonstrate experimentally that counterfactual examples for deep models are often inconsistent across such small changes, and that increasing the cost of the counterfactual, a stability-enhancing mitigation suggested by prior work in the context of simpler models, is not a reliable heuristic in deep networks. Rather, our analysis shows that a model's Lipschitz continuity around the counterfactual, along with confidence of its prediction, is key to its consistency across related models. To this end, we propose Stable Neighbor Search as a way to generate more consistent counterfactual explanations, and illustrate the effectiveness of this approach on several benchmark datasets.

Published as a conference paper at ICLR 2022
CONSISTENT COUNTERFACTUALS FOR DEEP MODELS
Emily Black; Zifan Wang," Anupam Datta, Matt Fredrikson {emi lybla, zi fan, danupam, mfredrik) @cmu. Carnegie Mellon University
ABSTRACT
Counterfactual examples are one of the most commonly-cited methods for explaining the predictions of machine learning models in key areas such as finance and medical diagnosis. Counterfactuals are often discussed under the assumption that the model on which they will be used is static, but in deployment models may be periodically retrained fine-tuned. This paper studies the consistency of model prediction counterfactual examples in deep networks under small changes to initial training conditions, such as weight initialization and leave-one-out variations in data, as often occurs during model deployment. We demonstrate experimentally that counterfactual examples for deep mod- els are often inconsistent across such small changes, and that increasing the cost of the counterfactual, a -aaiiiit--nhhancing mitigation suggested by prior work in the context of simpler models, is not a reliable heuristic deep networks. Rather, our analysis shows that a model's Lipschitz continuity around the counterfactual, along with confidence of its prediction, is key to its consistency across related models. To this end, we propose Sta- ble Neighbor Searct as way to generate more consistent counterfactual explanations, and illustrate the effectiveness of this approach on several benchmark datasets.
INTRODUCTION
Deep Networks are increasingly being integrated into decision-making processes which require
explanations during model deployment, from medical diagnosis credit risk analysis (Bakator & Radosav
2018 et. al 2017 Liu et al. [2014] Sun et al., (0166] De Fauw et al. [2018 Babaev et al. [019]] Addo
al. 2018 Balasubramaniann et al. 2018] Waan & Xul 2018). Counterfactual examples (Wachter al.
2018 Van Looveren & Klaise 2019 Mahajan et al. 2019: Verma et al. 2020 Laugel et al. 2018
Keane & Smyth| 2020 Ustun et al. [019 (Sharma et al. Poyiadzi et al. [220 Karimi al. 2020
Pawelczyk et al. 2020a) are often put forth as simple and intuitive method of explaining decisions in
such high-stakes contexts (Me Grath et al. 2018 Yang et al. 2020). A counterfactual example for an input is related point z' that produces desired outcome y' from model. Intuitively, these explanations are intended to answer the question, "Why did point æ not receive outcome y/ either to give instructions for recourse, i.e. how individual can change their behavior to get a different model outcome, as a check to ensure a model's decision is well-justified (Ustun et al. 2019). Counterfactual examples are particularly popular in legal and business contexts, they may ofter way to comply with regulations in the United States and Europe requiring explanations on high-stakes decisions (e.g. Fair Credit Reporting Act (FCRA) and General Data Protection Regulation (GDPR 2016)), while revealing little information about the underlying model (Barocas et al. 2020 Mc Grath et al. 20188).
Counterfactual examples are often viewed under the assumption that the decision system on which they will be used is static: that is, the model that creates the explanation will be the same model to which, e.g. a loan applicant soliciting recourse re-applies (Barocas et al., 2020). However, during real model deployments in high-stakes situations, models are not constant through time: there are often retrainings due to small dataset updates, or fine-tunings to ensure consistent good behavior (Merchant 2020 pwc 2020). Thus, in order for counterfactuals to be usable in practice, they must return the same desired outcome not only for the model that generates them, but for similar models created during deployment.
This paper investigates the consistency of model predictions on counterfactual examples between deep mod- els with seemingly inconsequential differences, i.c. random seed and one-point changes in the training set.
"Equal Contribution
Implementation available ht
stency

---

Published as a conference paper at ICLR 2022
We demonstrate that some of the most common methods generating counterfactuals in deep models either are highly inconsistent between models or very costly in terms of distance from the original input. Recent work that has investigated this problem in simpler models (Pawelezyk et al. 2020b) has pointed to increasing counterfactual cost, i.e. the distance between an input point and its counterfactual, as a method of increasing consisteney. We show that while higher than minimal cost is necessary to achieve stable counterfactual, cost alone is not reliable signal to guide the search for stable counterfactuals in deep models (Section 3
Instead, we show that model's Lipschitz continuity and confidence around the counterfactual is more reliable indicator of the counterfactual's stability. Intuitively, this is due to the fact that these factors bound the extent of a models local decision boundaries will change across fine-tunings, which we prove in Section 4 Following this result, we introduce Stable Neighbor Search (SNS), which finds counterfactuals by searching for high-confidence points with small Lipschitz constants in the generating model (Section ! Finally, we empirically demonstrate that SNS generates consistent counterfactuals while maintaining low cost relative to other methods over several tabular datasets, e.g. Seizure and German Credit from UCI database (Dua & Karra Taniskidou 2017). in Section
In summary, our main contributions are: 1) we demonstrate that common counterfactual explanations can have low consistency across nearby deep models, and that cost is insufficient signal to find consistent counterfactuals (Theorem. [ 2) to navigate this costiconsisteney tradeoff, we prove that counterfactual examples in neighborhood where the network has small local Lipschitz constant are more consistent across changes to the last layer of weights, which suggests that such points are more stable across small changes in the training environment (Theorem. 2 :)) leveraging this result, we propose SNS as way to generate consistent counterfactual explanations (Def. [5: 4) we empirically demonstrate the effectiveness of SNS in generating consistent and low-cost counterfactual explanations (Table D. More broadly, this paper further develops a connection between the geometry of deep models and the consistency of counterfactual examples. When considered alongside related findings that focus on attribution methods, our work adds to the perspective that good explanations require good models to begin with (Croce et al. 2019 Wang et al. 2020 Dombrowski et al. 2019 Simonyan al. 2013 Sundararajan et al. 2017).
BACKGROUND
Notation. We begin with notation, preliminaries, and definitions. Let F(x:8) argmax, be deep network where fi denotes the logit output for the i-th class and @ is the vector of trainable parameters. If F(x:0) E [0.1), there is only one logit output we write f. Throughout the paper assume F is piece-wise linear such that all the activation functions are ReLUs, We use ||I||p to denote the l, norm of vector x and B, def [x']lxx' x|Ip S e, E IR4 to denote a norm-bounded ball around x.
Counterfactual Examples. We introduce some general notation unify the definition of counterfac- tual example across various approaches with differing desiderata. In the most general sense, a counterfactual example for input x an example x. that receives the different, often targeted, prediction while min- imizing a user-defined quantity of interest (Qol) (see Def. I] for example, a counterfactual explanation for a rejected loan application is a related hypothetical application that was accepted. We refer to the point x requiring a counterfactual example the origin point or input interchangeably. We note that there is a different definition of "counterfactual" widely used in the causality literature, where a counterfactual is given by an intervention on causal model that is assumed to generate data observations (Pearl) 2009). This is case of overlapping terminology, and is orthogonal to this work. We do not consider causality in this paper. Definition 1 (Counterfactual Example). Given model F(x), an input desired outcome class o* F(x:0). and a user-defined quantity of interest q. a counterfactual example X for x is defined as X. p x) where the cost of x, is defined as -xxelpp-
The majority of counterfactual generation algorithms minimize of (x,x') del X 1xxx'|l Up: potentially along
with some constraints, to encourage low-cost counterfactuals (Wachter et al., 2018). Some common vari- ations include ensuring that counterfactuals are attainable, i.e. not changing features that cannot be changed (e.g. sex, age) due to domain constraints (Ustun et al. 2019 Lash et al.. (2017), ensuring sparsity, so that fewer features are changed (Dandl et al. 22200] Guidotti et al. 2018), or incorporating user preferences into what features can be changed (Mahajan et al. 2219). Altematively, a somewhat distinct line of work (Pawel) czyk et al. 2020a| Van Looveren & Klaise 2019 Joshi et al. (019) also adds constraint to ensure that counterfactuals come from the data manifold. Other works still integrate causal validity into counterfactual
search (Karimi al. 2020), generate multiple counterfactuals at once (Mothilal al. 2020).
2

---

Published as a conference paper at ICLR 2022
We focus analysis on the first two approaches, which denote minimum--cost and data data-support coun- terfactuals. We make this choice as the causal and distributional assumptions used in other counterfactual generation methods referenced are specific to a given application domain, whereas our focus is on the general properties of counterfactualls across domains. Specifically, we evaluate our results on minimum-coss counterfactuals introduced by Waacher al. (2018), and data-support counterfactuals from Pawelczyk al.) (2020a), and Van Looveren & Klaise (2019). We give the full descriptions of these approaches in Sec. 5
Counterfactual Consistency. Given two models F(x:81) and F F(x:02), a counterfactual example x, for F F(x;0; is consistent with respect to F F(x:02) means F F(x::01) = F(x,;02). Following Pawelczyk et al. (2020b), we define the Invalidation Rate for counterfactuals in Def. 2
Definition 2 (Invalidation Rate). Suppose x. is a counterfactual example for found in model F F(x:0), we define the invalidation rate IV( of x. with respect to a distribution & of trainable parameters as (V
del -Eg Re (F(xx())) + F (x
Throughout this paper, we will call the model F(x:0) that creates the counterfactual the generating or base model. Recent work has investigated the consistency of counterfactual examples across similar linear and random forest models (Pawelczyk et al. 2020b). We study the invalidation rate with respect to the distribu- tion θ introduced by arbitrary differences in the training environment, such as random initialization and one- point difference in the training dataset. We also assume F(x:6") uses the same set of hyper- parameters as chosen for Fxx:6)) e.g. the number of epochs, the optimizer, the learning rate scheduling, loss functions, etc.
COUNTERFACTUAN INVALIDATION IN DEEP MODELS
As demonstrate in more detail in Section counterfactual invalidation is problem in deep networks on real data: empirically, we find that counterfactuals produce inconsistent outcomes in duplicitous deep models up to 94% of the time.
Previous work investigating the problem of counterfactual invalidation (Pawelczyk et al. 2020b Rawal ct al. 202T). has pointed increasing counterfactual cost as a potential miligation strategy. In particular, they prove that higher cost counterfactuals will lead to lower invalidation rates in linear models in expectation (Rawal et al. 202T). and demonstrate their relationship a broader class of well-calibrated models (Pawelczyk et al. (020b). While this insight provides interesting challenge to the perspective that low cost counterfactuals should be preferred, we show that cost alone is insufficient to determine which counterfactual has greater chance of being consistent at generation time in deep models.
The intuition that larger distance between input and counterfactual will lead to lower invalidation rests on the assumption that the distance between point and a counterfactual x. is indicative of the distance from Ie to the decision boundary, with a higher distance making xe 's prediction more stable under perturbations to that boundary. This holds well in a linear model, where there is only one boundary (Rawal et al. 2021).
However, in the complex decision boundaries of deep networks, going farther away from a point across the nearest boundary may lead being closer a different boundary. We prove that this holds even for a one-hidden-layer network by Theorem [ This observation shows that a counterfactual example that is farther from its origin point may be equally susceptible to invalidation as one closer to it. In fact, show that the only models where ép cost is universally good heuristic for distance from a decision boundary, and therefore by the reasoning above, consistency, are linear models (Lemma [].
Theorem 1. Suppose that H1, Hz are decision boundaries in a piecewise-lineat network F(x) sign [ww ReLU(W(x); and let x be an arbitrary point in its domain. If the projections of x onto the corresponding halfspace constraints of H., HHH are Hi and H2 then there exists point x' such that:
1) dix, =H))=0
2) d(x' .H2) H2)
3) S
where H(x,H.) denotes the distance between x and the nearest point on a boundary H.. Lemma Let F and x be defined as in Theorem [ If the projections of x onto the corresponding halfspace constraints of H, are Hi and H2, but there does not exist point x' satisfying (2) and (3) from Theorem / then H1 = H2.
Figure T iillustrates the geometric intuition behind these results. The shaded regions of 1b correspond to two decision surfaces trained from different random seeds on the data in (a). The lighter gray region denotes where the models disagree, whereas the black and white regions denote agreement. Observe
3

---

Published as a conference paper at ICLR 2022
X3
C3
(a)
(b)
Figure Illustration of the boundary change deep model (b) and a linear model (c) for 2D dataset (a) when changing the seed for random initialization during the training. Shaded regions correspond to the area when two deep models in (b) (or two linear models in (c)) make different predictions.
that counterfactuals equally far from a decision boundary may have different invalidation behavior, as demonstrated by the counterfactuals far away from one boundary may lead one to cross another one in deep models. However, for two linear models shown in Fig. Ic being far away from the boundary indeed good indicator being consistent.
and for the point T2. Also note that shown with 4i, being
The discussion so far has demonstrated that there not a strong theoretical relationship between cost and invalidation in deep models. In Section [ we test this claim real data, and show that higher-cost counterfactuals can have higher invalidation rates than their lower-cost relatives (c.f. Table D Further, show that the coefficient of determination (R²) between cost and invalidation rate is very small (with all but one around 0.05). Thus, while cost and invalidation are certainly related-for example, it may be necessary for a stable counterfactual to be more costly than the minimum point across the boundary- cost
alone is not enough to determine which one will be the most consistent in deep models.
TOWARDS CONSISTENT COUNTERFACTUALE
In this section, we demonstrate that the Lipschitz continuity (Def. 3 of neighborhood around counterfactual can be leveraged to characterize the consistency of counterfactual explanations under changes to the network's parameters (Section[42 Our main supporting result is given in Theorem which shows that model's Lipschitz constant in neighborhood around I. together with the confidence of its prediction on Sa serve as proxy for the difficulty of invalidating xy. We further discuss insights from these analytical results and introduce an effective approach, Stable Neighbor Search, improve the consistency of counterfactual explanations (Section 4.3). Unless otherwise noted, this section assumes all norms are fz.
Definition 3 (Lipschitz Continuity). A continuous and differentiable,uuncee function h: S + - is K -KLipsschitz continuous iff vx' (,]l/((x') -xx)) < x x|.. We write h is K K-Lipschitz in S.
4.1 RELU DECISION BOUNDARIES AND DISTRIBUTIONAL INFLUENCE
We analyze the differences between models with changes such as random initialization by studying the differences that arise in their decision boundaries. In order capture information about the decision boundaries in analytical form, we introduce distributional influence: method of using a model's gradients gather information its local decision boundaries. We begin motivating this choice by reviewing key aspects of the geometry of ReLU networks.
ReLU networks have piccewise linear boundaries that are defined by the status of each ReLU neuron in the model (Jordan et al. 2019 Hanin & Rolnick 2019). To see this, let ux(x) denote the pre-activation value of the neuron u4 in the network f at x. We can associate half-space A; in the input space with the linear activation constraint u, (x) 2 corresponding to the activation status of neuron u; and an activation puttern for a network at x, (x), as the activation status of every neuron the network. An activation region for given activation pattern denoted R(p), is then subspace of the network's input that yields the activations in p. geometrically, this a polytope given by the convex intersection of all the half spaces described by p, with facets corresponding to each neuron's 's activation constraint.
Note that for points in given activation region R(p), the network f can be expressed as a linear function, Of thus piecewise- linear constraints, f(x) 0 for binary classifiers, or fx(x 2 (x) between classes and j for a categorical classifier, with linear pieces corresponding to the activation region xf x. This leads to the following: ()) if decision boundary crosses (p),, then w, will be orthogonal to that
i.e. Vx (x))-f(x) w, x bp where w, =0 (x)/xx (Jordan et al. 2019 Hanin & Rolnick 2019 Decision boundaries
4

---

Published as a conference paper at ICLR 2022
(
B
A
0 0
== 1
(a)
(b)
Figure 2: (a) A geometric view of the input space in ReLU network. Dashed lines correspond to activation constraints while the colorful solid lines are piece-wise linear decision boundaries. Taking gradient of the model's s output with respect to the input returns vector that orthogonal to nearby boundary (points in the blue and green regions) or an extension of a nearby boundary (the point in the yellow region). (b) Curves of the model's sigmoid output (tx') (y-axis) against interpolation parameter (x-axis).
boundary, and (2) if decision boundary does not cross the region R(p), then wp is orthogonal to exten- sion a nearby boundary (Fromherz et al. 2021 Wang et al. 202T). In either case, the gradient with respect to the input captures information about some nearby decision boundary. Figure 2a summarizes this visually.
This analysis motivates the introduction of distributional influence (Definition which aggregates the gradients of the model at points in given distribution of interest (Dol) around x.
Definition 4 (Distributional Influence (Leino et al. 2018)). Given an input x, network f: + RRm class of interest c, and a distribution of interest Dx which describes reference neighhorhood around define the distributional influence as XDD (x) Ex [0f((x) /xx)) We write S(Dx) to represent
the support of >x When m=1, 1, we write XD_ (x) (0f
In Leino et al. (0118), distributional influence is used to attribute the importance of a model's input and internal features observed outcomes. Following the connection between gradients and decision boundaries ReLUU networks, we leverage it to capture useful information about nearby decision
boundaries detailed in Section 4.2
4.2 CONSISTENCY AND CONTINUITY
Characterizing the precise effect changes such as random initialization have on the outcome of training challenging. We approach this by modeling the differences that arise from small changes such as fine-tuning of the original model, where the top layer of the model is re-trained and the parameters of rest of the layers are frozen.
We now introduce Theorem 2 which bounds the change distributional influence when the model is fine-tuned at its top layer in terms of the model's Lipschitz continuity on the support of Dx. This suggests that finding a cotfhdoonfeeecee counterfactual example in a neighborhood with a lower Lipschitz constant may lead to lower invalidation after fine-tuning, given the relationship between nearby boundaries and influence described in the previous section.
Theorem 2. Let [x) det w -h(xx) +b +h(x)+bbbe ReLU network with a single logit output (i.e., binary classifier), where h(x) the output of the penultimate layer, and denote ow ow=ol (f as the sigmoid output of the model at Let W dh! {w/: : :l[w- - w'll || }} and XD, (x:w) be the distributional influence of f when weights ware used at the top layer. If is K K-Lisschitz in the support S(Dx), the following inequality holds:
Vw' EW, IIxP, (x:w) Xo, (x:w I1| K
where Cj and O2 are constants and dar(x:)) del l0f
Observations. Theorem characterizes the extent to which a model's local decision boundaries, by proxy of influence, may change result of fine-tuning, This intuitively relates to the likelihood of counterfactual's 's invalidation, as a point near a decision boundary undergoing a large shift more likely to experience change in prediction than near stable portion of the boundary. As the two key ingredients in Theorem are are the local Lipschitz constant and the model's confidence at x, this suggests that searching for high-confidence points in neighborhoods with small Lipschitz constants will yield more
5

---

Published as a conference paper at ICLR 2022
consistent counterfactuals. While Theoremm]doe does not provide a direct bound invalidation, and is limited to changes only at the network's 's top layer, we characterize the effectiveness of this heuristic in more general settings empirically in Section[Saftee showing how to efficiently operationalize it in Section 4.3
4.3 FINDING CONSISTENT COUNTERFACTUALS
The results from the previous section suggest that counterfactuals with higher sigmoid output and lower Lipschitz Constants of the penultimate layer's output with respect to the Dol Dx will be more consistent across related models. Stuble Neighbor Search (SNS) leverages this intuition to find consistent counterfactuals by searching for those with a low Lipschitz constant and confident counterfactual. We can find such points with the objective in Equation
[
which assumes given counterfactual point x.
X arg max x'E((x,5)
[xo(x'- Ksr such that F F(x.:1)) F
(1)
In Eq. [ abooe and throughout this section, we assume that a binary classifier with a single-logit output and sigmoid output or (x)())) When is clear from the context, we directly write (x). The results are readily extended to multi-logit outputs by optimizing over the maximal logit at x. K5 is the Lipschitz Constant of the model's s sigmoid output over the support S(Dx). We relax the Lipschitz constant K of the penultimate output in the Theorem 2 to the Lipschitz constant of the entire network, as in practice any parameter in the network, and not just the top layer, may change.
Leveraging a well-known relationship between the dual norm of the gradient and a function's Lipschitz constant (Paulavičius & Zilinskas, 2006). we can rephrase this objective as shown in Equation Note that we assume &g norms throughout, so the dual remains lz-
do (xc) 0x
X arg max x(E)(x
o(x')-
max RES(D
such that F(xx:0))((x)))
Choice of DoL. The choice of Dol determines the neighborhood of points from which we gain an understanding of the local decision boundary (Wang et al.] (022). In this paper, following prior work, choose D as Uniform(O -> x). uniform distribution over linear path between zero vector and the current input (Sundararajan et al. 2017). That is, the set of points in D is S(D) [(x,1+ E [0,1]]- Equation 3 below updates the objective accordingly.
(ox(tx) ((x))
X. arg max ((.
oxx'-
max (E
such that P(x,0)=-((x()
(3)
While Equation provides an objective that uses only primitives that are readily available in most neural network frameworks, solving the inner objective using gradient descent requires second-order derivatives of the network, which is computationally prohibitive. In the following, discuss sequence of relaxations to Eq. (3) that provides sssource-efficien objective function.
Avoiding vacuous second-order derívatives. There exists lower-bound of the term ma ([0oo(tx'//((xx)) by utilizing the following Proposition which allows us to relax Eq. by maximizing a differentiable lower-bound of the gradient norm rather than the gradient norm itself.
Proposition 1. Let q be differentiable, real-valued function in Rd and S be the support set of Uniform(O x Then for x' ES, [|0q(x')/xx1I] 2 (0/(())))/rrrrrm///
Noting that the constant factor ||x|| is irrelevant to the desired optimization problem, Equation 4 below updates the objective by fitting into the place of q in Proposition [ The absolute-value operator is omitted because the derivative of the sigmoid function is always non-negative.
(ott' 0t
X arg max
[x(x)= max =E
such that F(xx:0)=((x00)
(4)
x x(E
The second term in Equation 4 ma (tx')) //tr is interpreted by plotting the output score o (tx') against the interpolation vanable shown in Fig, 26 This term encourages finding counterfactual point X, where the outputs of the model for points between the zero vector (t = 0) and itself (t = 1)
form smooth and flattened curve B in Fig. 2h Therefore, by incorporating the graph interpretation

---

Published as a conference paper at ICLR 2022
of co (tx')))) to find solution of x, that comessonds to curve B, we can instead try to increase the area under the curve of a(xx') against I, which simplifies our objective function with replacing the inner-derivative with an integral shown in Equation
[xx))+ S. (txx ydl such that F(xx:))=((x;))
X arg max x'E((x.5)
(5)
One observation of the objective defined by Equation 5 is that the first term (x') is redundant, as differentiating the second integral term already provides useful gradient information to increase (xx). Equation yields our approach, Stable Neighbor Search.
Definition 5 (Stable Neighbor Search (SNS)), Given a starting counterfactual x for a network F(x),
its stable neighbor x, of radius is the solution to the following objective:
{ (txx)d )dt
arg max B'
We implement the integral in Definition 5 as summation over grid of points of specified resolution, which controls the quality of the approximation. The complexity of SNS linear in the number of points in this grid.
5 EVALUATION
In this section, we evaluate the extent invalidation across five different counterfactual generation methods, including Stable Neighbor Search, over models trained with two sources of randomness in setup: /) initial weights, and 2) leave-one-out differences in training data. Our results show that Stable Neighbor Search con- sistently generates counterfactuals with lower invalidation rates than all other methods, in many cases elim- inating invalidation altogether on tested points. Additionally, despite not explicitly minimizing cost, SNS counterfactuals manage to maintain low cost relative to other methods that aim to minimize invalidation.
5.1
SETUP
Data.
Our experiments encompass several tabular classification datasets from the UCI database including: German Credit, Taiwanese Creait-Default, Seizure, and Cardiotocography (CTG). We also include FICO HELOC (FICO 2018a) and Warfarin Dosing (Consortium) 2009). All datasets have two classes except Warfarin, where we assume that the most favorable outcome (class 0) is the desired counterfactual for the other classes, and vice versa. Further details of these datasets are included in Appendix B.
We compare SNS with the following baselines in terms of the invalidation rate. Further details about how we implement and configure these techniques are found in Appendix [B.3 Min-Cost
Baselines.
fi/lg (Wachter et af. (018): we implement this by setting the appropriate parameters for the elastic-net loss (Chen et al. 2018) ART (Nicolae et al. (018). Min-Cost e-PGD (Wachter al. 2018): We perform Projected Gradient Descent (PGD) for an increasing sequence of e until a counterfactual is found. Pawelczyk et al. (Pawelezyk et al. 2020b): This method attempts to find counterfactual examples on the data manifold, that are therefore more resistant to invalidation, by searching the latent space of a variational
autoencoder, rather than the input space, Looveren al. (Van Looveren & Klaise 2019): This method minimizes an elastic loss combined with term that encourages finding examples on the data manifold.
We note that PGD was originally proposed in the context of adversarial adversarial examples (Szegedy al. 2013). As has been noted in prior work, the problem of finding adversarial examples is mathematically identical to that finding counterfactual examples (Freiesleben) 22200 Browne & Swifi, 20200] (ookol &
Flach 2019 Wachter et al. 2018). While solution sparsity is sometimes noted as a differentiator between the two, we note that techniques from both areas of research can be used with various l, metrics. We measure cost in terms of both l and &g norms, providing lg in the main body and e in Appendix B.6
Implementation of SNS. SNS begins with a given counterfactual example as mentioned in Def. 5 which generate with Min. f//6, and Min. PGD. We use the sum of 10 points to approximate the integral.
7

---

Published as a conference paper at ICLR 2022
Intulicariion Rate
Method
Genman Ciedit
Sezure
Warfarin
HELOC:
Taiwanese
1.00
L.0
RS
|.00
RS
L.00
L.00
RS
1.00
Min.
044
0.56
0.07
0129
0.44
0.35
0.30
0.45
0.30
0.78
+SNS
0.00
0.07
0.00
0.01
0.00
0.00
0.00
0.00
0.00
0.04
Min.
0.36
0.36
0.61
0.77
0.68
0.49
0.35
0.3
0.55
0.61
0.27
0.72
+SNS
0.00
0.06
0,02
0.1
0.00
0
0.00
0.00
0.00
0.00
0
0.04
Min. PGB
0.25
0:4
0.54
004
0U0
0.11
D04
0.00
Toowern et
0.25
0.48
0.54
0.1
0.25
0.34
0.20
Pawelaykke clal.
0.20
0.35
0.16
0.11
0.00
0.06
0.02
0.01
0.05
0.15
0.02
0.20
Counterhemnal Cosr((y)
Method
Genman Credit
Scatue
CTG
Warfatin
HELLCC
Taiwunese Credit
0.34
Ez
0.11
Looveee al.
5.37
8.40
0.11
0,45
Min. PGB
1.02
1.36
0.88
0.51
0.32
0.75
Manu: SSN
0.25
1.71
Min.G SNS
9.60
1.71
PGD SNS
3,0
0.22
0.50
1.79
278
Pawekzyk et al.
7.15
13.66
1.07
2.62
1.38
4.4
Correlation
0.06
0.17
Table I: The consistency of counterfactuals measured by invalidation rates. The average f cost of different methods are also included. Results are aggregated over 100 networks for each experiment (RS and LOO). Lower invalidation rates and cost are more desirable. For lg cost, the best results are highlighted among three methods (separated by a line) with lower invalidation rates. If a method has significantly low success rate in generating counterfactual examples, we report '.' In the last line, we present the R² correlation coefficient from linear regression predicting invalidation percentage from cost. Small values indicate weak correlation.
Retraining Controls. We prepare different models for the same dataset using Tensorflow 2.3.0 and all computations are done using a Titan RTX accelerator on a machine with 64 gigabytes of memory. We control the random seeds used by both numpy and Tensorflow, and enable deterministic GPU operations in Tensorflow -ettemmiww Python package). We evaluate the invalidation rate of counterfactual examples under changes in retraining stemming from the following two sources (see Appendix [B.4] for more details on our training setup). Leave-One-Out (L.O0): We select a random point (without replacement) remove from the training data. Network parameters are initialized with the same values across runs. Random Seed (RS): Network parameters are initialized by incrementing the random seed across runs, while other hyperparameters and the data remain fixed.
We note that these sources of variation do not encompass the full set of sources that we are relevant to counterfactual invalidation, such as fine-tuning and changes in architecture or other hyperparameters. However, they are straightforward to control, produce very similar models that nonetheless tend to invalidate counterfactuals, and they are not dependent on any deployment or data-specific considerations in the way that fine-tuning changes would be. While we hope that our results are indicative of what might be observed across other sources, exploring invalidation more depth particular applications important future work.
Metries. To benchmark the consistency of counterfactuals generated by different algorithms, we compute the mean invalidation rate (Def. ( over the validation split of each dataset. To calculate the extent of correlation between cost and invalidation, discussed in Section we perform linear regression (scipy. inregress) between the costs for each valid counterfactual, across all five methods, with its invalidation rate across both LOO and RS differences. Table reports the resulting R22 for each dataset.
Methodology. For each dataset, we train a "base" model and compute counterfactual examples using the five methods for each point in the validation split. For each set of experiments (LOO or RS), we train 100 additional models, and compute the invalidation rate between the base model and the 100 variants. The results are shown in Table
5.2 RESULTS
Looking at the invalidation results in T the most salient trend is apparent in the low invalidation rates of SNS compared to the other methods. SNS achieves the lowest invalidation rate across all datasets in both LOO and RS experiments, except for the Seizure dataset with RS variations, where there is a two-point difference in the invalidation rate. SNS generates counterfactuals with no invalidation on CTG, Warfarin, and Heloc, and no invalidation over L.0 differences German Credit and Taiwanese Credit.
8

---

Published as a conference paper at ICLR 2022
Notably, this is down from invalidation rates as high 61% from other methods Heloc, and x 10-50% on others. On Seizure, which had IV rates as high as 94% from other methods, SNS achieves just 2% (LOO) invalidation. The closest competitor is the method of Pawelczyk et al. (2020b), which achieves zero invalidation in one case (CTG under IOO), but at significantly greater cost -in five out of six cases, SNS produced less-costly counterfactuals, and in nearly every case the margin between the two is greater than 2x.
As discussed in Section 3, while increasing cost is not a reliable way to generate stable counterfactuals for deep models, our results do show that stable counterfactuals tend be more costly. The data suggests that greater-than-minina cost appears to be necessary for stability. While SNS counterfactuals are much less costly than those generated by Pawelczyk et. al. they are consistently more costly than other methods that aim minimize cost without other constraints. To investigate the relationship between counterfactual cost and invalidation more closely, we report the R² coefficient of determination of linear regression between the cost of each valid counterfactual generated and its invalidation rate in Table 1 Recall that a R² ranges from zero to one, with scores closer to zero indicating no linear relationship. Notably, Table ] shows that the correlation between cost and invalidation is quite weak: the maximum R over all datasets is 0.17 (Heloc), while most of the other datasets report coefficients that are much smaller-at or below 0.05.
6 RELATED WORK
Counterfactual examples enjoy popularity in the research literature (Sokol & Flach 2019; Wachter et al.
2018 Keane& & Smyth [2020] Dandi et al. [2020] Van Looveren& & Klaise| [019 Mahajan et al. |0119] Yang
al. 2020 Verma et al. 20200 Pawelczyk al.) 2020a Dhurandhar et al. [0088] Guidotti al. 2018).
especially in the wake of legislation increasing legal requirements on explanations of machine learning
models (Kaminski 2019 GDPR 2016). However, recent work has pointed to problems with counterfactual
examples that could occur during deployment (Laugel et al. [2019] Pawelczyk et al. 2020b; Barocas et al.
2020 Rawal al. 202T). For example, [Barocas& & Selbst (2016) point to the tenston between the usetulness
Forexampie,Barrcass
of counterfactual and the ability to keep the explained model private. Previous work investigating the
problem of invalidation, has pointed to cost as a heuristic for evaluating counterfactual invalidation at generation time (Pawelczyk et al. 2020b Rawal et al., (22T)) We demonstrate that cost is not reliable metric for predicting invalidation in deep models, and show how the Lipschitz constant and confidence of model around counterfactual can be a more faithful guide to finding stable counterfactual examples.
While in this work, we address the problem of multiplicitious deep models producing varying outputs on counterfactual examples, recent work has shown that there are large differences in model prediction behavior on any input across small changes to the model (Black & Fredrikson) 2021 Marx et al. 2019 D Amour al. 2020p. Instability has also been shown be problem for gradient- based based explanations, although this 18 largely studied in an adversarial context (Dombrowski et al.) 2019 Ghorbani et al. 2019 Heo et al. 2019).
Within the related field of adversarial examples, there is recent interest in adversarial transferability (Dong ct al. 2018 [lyas et al., [019 Xie et al. (019)), where adversarial attacks are induced to transfer between models. In general, adversarial transferability concerns transferring attacks between extremely different models-e.g. trained on disjoint training sets. Meanwhile, in this work, we decrease counterfactual invalidation between very similar models, in order preserve recourse and explanation consistency, Interestingly, Goodffllow Mileedeingyy,GGooddeelllww et al.) (2014) suggest that transferability of adversarial examples is due to local linearity in deep networks. This supports our motivation: we find stable counterfactuals in more Lipschitz regions of the model, i.c. where it behaves (approximately) linearly. We note, however, that as linearity does not imply Lipschitzness, this insight does not provide a clear path to generating stable counterfactuals. We look forward to exploring the potential overlap between these two areas as future work.
7 CONCLUSION
In this paper, we characterize the consistency of counterfactual examples in deep models, and demonstrate that counterfactual cost and consistency are not strongly correlated. To mitigate the problem of counterfactual inconsistency, we introduce Stable Neighbor Search, which finds stable counterfactuals by leveraging the connection between the Lipschitz constant and confidence of the network around counterfactual, and its consistency. At a high level, our work adds to the growing perspective in the field of explainability that creating good explanations requires good models to begin with.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work was developed with the support of NSF grant CNS-1704845, CNS-1943016, as well as by DARPA and the Air Force Research Laboratory under agreement number FA8750-15-22 15-2-0277. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes not with- standing any copyright notation thereon. The views, opinions, and/or findings expressed those of the author(s) and should not be interpreted as representing the official views or policies of DARPA, the Air Force Research Lab- oratory, the National Science Foundation, or the U.S. Government.
ETHICS
This paper demonstrates the problem of counterfactual invalidation in deep networks, and introduces a counterfactual generation method, Stable Neighbor Search (SNS), which creates counterfactual examples which yield consistent outcomes across nearby models. We note that the increased stability in counterfactual examples which SNS provides may eventually factor in to an engineer's. s, lawmaker's, s, or business' decision about what type of model use: with the potential for more stable explanations, deep networks may seem more favorable. This, along with the ever- werrincreasing zeal to incorporate neural networks in more applications, may lead practitioners to choose deep model, when simpler model may be a better fit for orthogonal reasons. However, if used wisely, we believe SNS can lead to positive impacts, by lessening the invalidation of recourse to users who desire a different model outcome.
REFERENCES
Managing the risks of machine learning and artificial intelligence models in the financial services industry, 2020.
Peter Addo, Dominique Guegan, and Bertrand Hassani. Credit risk analysis using machine and deep learning models. Risks, Apr 2018.
Dmitri Babaev et al. Et-mn: Applying deep leaminng credit loan applications. KDD, 2019.
Mihalj Bakator and Dragica Radosav. Deep learning and medical diagnosis: A review of literature. Multimodal Technologies and Interuction, Aug 2018.
Ramnath Balasubramanian et al. Insurance 2030: The impact of ai on the future of insurance. McKinsey & Company, 2018.
Solon Barocas and Andrew D Selbst. Big data's disparate impact. California Law Review, 104:671-732. 2016.
Solon Barocas, Andrew D Selbst, and Manish Raghavan. The hidden assumptions behind counterfactual explanations and principal reasons. In Proceedings of the 2020 Conference on Fairness, Accountability; and Transparency, pp. 80-89, 2020.
Emily Black and Matt Fredrikson. Leave-one-out unfaimess. FAceT '21, 2021.
Kieran Browne and Ben Swift. Semantics and explanation: why counterfactual explanations produce adversarial examples in deep neural networks. arXiv preprint arXiv:20/2, 10076, 2020.
Pu Chen, Yash Sharma, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Ead: elastic-net attacks to deep neural networks via adversarial examples. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
International Warfarin Pharmacogenetics Consortium. Estimation of the warfarin dose with clinical and pharmacogeneticc data. New England Journal of Medicine, 360(8):533-76) 2009.
Francesco Croce, Maksym Andriushchenko, and Mathhis Hein. Provable robustness of relu networks via maximization of linear regions. AISTATS 2019, 2019.
Alexander D' D'mour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi. Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein. Matthew D Hoffman, et al. Underspecificatioo presents challenges for credibility in modem machine learning. arXiv preprint arXiv:201 /. /,03395, 2020.
10

---

Published as a conference paper at ICLR 2022
Susanne Dandl, Christoph Molnar, Martin Binder, and Berdd Bischl. Multi-objective counterfactual explana- tions. In International Conference on Parallel Problem Solving from Nature, pp. 448 4699.466.000 Springer, 2020.
Jeffrey De Fauw, Joseph R Ledsam, Bemardino Romera-Paredee, Stanislav Nikolov, Nenad Tomasev, Sam Blackwell, Harry Askham, Xavier Glorot, Brendan O'Donoghue, Daniel Visentin, et al. Clinically appli- cable deep learning for diagnosis and referral in retinal disease. Nature medicine, 24(9):1342-133 341--3500, 2018.
Amit Dhurandhar, Pin-Yu Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. arXiv preprint arXiv: 000.0002..... 2018.
Ann-Kathrin Dombrowski, Maximilian Alber, Christopher Anders, Marcel Ackermann, Klaus-Robert Müller, and Pan Kessel. Explanations can be manipulated and geometry is to blame. arXiv preprint vrXiv:/906.0798. 2019.
Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boosting adversarial attacks with momentum. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1185-9193, 2018.
Dheeru Dua and Efi Karra Taniskidou. UCI machine learning repository. https//iveiccs.uc.com 2017.
Geert Litjens et. al. A survey on deep leamning in medical image analysis. Medical Image Analysis, 2017.
FCRA. Fair credit reporting act.
Fair-oredit-repottin
FICO. Fico xml challenge. https://commmiityficoocooo
http://wwww......ooooooooooooooa 80
FICO. Dataset usage license, fico xml challenge. hhaeeeaallaee/aastttt...Ss--eeee 2018b.
https//oommuuiiiff.cooo///eeeeat
Timo Freiesleben. Counterfactual explanations & adversarial examples-common grounds, essential differences, and potential transfers. arXiv preprint 0rX14:2009.04487, 2020.
Aymeric Fromherz, Klas Leino, Matt Fredrikson, Bryan Pamo, and Corina Päsäreanu. Fast geometric projections for local robustness certification. In International Conference on Learning Representations (ICLR),202))
GDPR. European parliament and council of european union (2016) regulation (eu) 2016/679.
https://eur-les wew.erro.e.....p.ppaaaaa eu/ http://gglllcoootte///////777771 /ttp:////A////////////////////1 3201 60066666677710
2016.
Amirata Ghorbani, Abubakar Abid, and James Zou. Interpretation of neural networks is fragile. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3681-3688, 2019.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamnessing adversarial examples. arXiv 1412.6572, 12 2014.
Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Dino Pedreschi, Franco Turini, and Fosca Giannotti. Local rule-based explanations of black box decision systems. arXiv preprint arXiv:1805.1080 2018.
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
Juyeon Heo, Sunghwan Joo, and Taesup Moon. Fooling neural network interpretations via adversarial model manipulation. Advances in Neural Information Processing Systems, 32:2925-299 2936, 2019.
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. In Advances in Neural Information Processing Systems 32. 2019.
Matt Jordan, Justin Lewis, and A. Dimakis. Provable certificates for adversarial examples: Fitting a ball in the union of polytopes. In NewrtPS, 2019.
11

---

Published as a conference paper at ICLR 2022
Shalmali Joshi, Oluwasanmi Koyejo, Warut Vijitbenjaronk, Been Kim, and Joydeep Ghosh. Towards realistic individual recourse and actionable explanations in black-box decision making systems. arXiv preprint arXiv:1907.09615. 2019.
Margot E Kaminski. The right explanation, explained. Berkeley Tech. LJ, 34:189, 2019.
Amir-Hossein Karimi, Julius von Küigelgen, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse 2020.
under imperfect causal knowledge: a probabilistic approach. arXiv preprint arXi::2006.000m
Mark T Keane and Barry Smyth. Good counterfactuals and where to find them: A case-based technique for generating counterfactuals for explainable ai (xai). In International Conference on Case-Based Reasoning, pp. 163-178. Springer, 2020.
Michael T Lash, Qihang Lin, Nick Street, Jennifer G Robinson, and Jeffrey Ohlmann. Generalized inverse classification. In Proceedings of the 2017 SIAM International Conference on Data Mining, pp. 162-170.
SIAM, 2017.
Thibault Laugel, Marie-Jeanne Lesot, Christophe Marsala, Xavier Renard, and Marcin Detyniecki. Comparison- based inverse classification for interpretability in machine learning. IPMU, 2018.
Thibault Laugel, Marie-Jeanne Lesot, Christophe Marsala, and Marcin Detyniecki. Issues with post-hoc counterfactual explanations: discussion. arXiv preprint 190600990004774,, 2019.
Klas Leino, Shayak Sen, Anupam Datta, Matt Fredrikson, and Linyi Li. Influenceedirected explanations for deep convolutional networks. In 2018 IEEE International Test Conference (ITC), pp. 1-8, 2018. doi: 10.1099/EST.2211888447777
Siqi Liu, Sidong Liu, Weidong Cai, Sonia Pujol, Ron Kikinis, and Dagan Feng. Early diagnosis of alzheimer's disease with deep learning. In 2014 IEEE 1/th international symposium on biomedical imaging (ISBI), pp. 1015-1018. IEEE, 2014.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018.
Divyat Mahajan, Chenhao Tan, and Amit Sharma. Preserving causal constraints in counterfactual explanations for machine learning classifiers. arXiv preprint arxfn:1912.003277, 2019.
Charles T. Marx, Flávio du Pin Calmon, and Berk Ustun. Predictive multiplicity in classification. CoRR, 0es/1909.066777 2019,
06677
Rory Me Grath, Luca Costabello, Chan Le Van, Paul Sweeney, Farbod Kamiab, Zhao Shen, and Freddy Lecue. Interpretable credit application predictions with counterfactual explanations. In NIPS 2018- Workshop on Challenges and Opportunities for Al in Financial Services: the Impact of Fairness, Explainability. Accuracy, and Privacy, 2018.
Gordon al. Merchant. Model lifecycle transformation: How banks are unlocking efficiencies: Accenture,
Dec 2020.
Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference on Faimess, Accountabilit; and Transparency, pp. 607-617, 2020.
Maria-Irina Nicolae, Mathieu Sinn, Minh Ngoc Tran, Beat Buesser, Ambrish Rawat, Martin Wistuba, Valentina Zantedeschi, Nathalic Baracaldo, Bryant Chen, Heiko Ludwig, Ian Molloy, and Ben Edwards. Adversarial robustness toolbox v1.2.0. CoRR, 1807.01069, 2018. URL
btttps//arxxl..or/pdde
01069
Remigijus Paulavičius and Julius Žilinskas. Analysis of different norms and corresponding lipschitz constants for global optimization. Technological and Economic Development of Economy, 12:301-306. 01 2006. doi: 01118///192269...00 108.1199...06667775557
Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. Learning model-agnostic counterfactual explanations for tabular data. In Proceedings The Web Conference 2020, pp. 3126-3132, 2020a.
12

---

Published as a conference paper at ICLR 2022
Martin Pawelczyk, Klaus Broelemann, and Gjergji. Kasneci. On counterfactual explanations under predictive multiplicityy In Proceedings of the 36th Conference on Uncertainty Artificial Intelligence (UAI), Proceedings of Machine Learning Research, 2020b.
Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, USA, 2nd edition, 2009. ISBN 052189560X.
Rafael Poyiadzi, Kacper Sokol, Raul Santos- Gantos-Rodriguez, Tijl De Bie, and Peter Flach. Face: feasible and actionable counterfactual explanations. In Proceedings of the AAAT/ACM Conference AI, Ethics, and Sociery, pp. 344-350, 2020.
Kaivalya Rawal, Ece Kamar, and Himabindu Lakkaraju. Can still trust you?: Understanding the impact of distribution shifts algorithmic recourses, 2021.
Shubham Sharma, Jette Henderson, and Joydeep Ghosh. Certifai: Counterfactual explanations for robustness, transparency, interpretability, and faimess of artificial intelligence models. arXiv preprint arXtv:1905.07857, 2019.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint arXiv: 2013.
Kacper Sokol and Peter A Flach. Counterfactual explanations of machine learning predictions: opportumities and challenges for ai safety. In SafeAl at AAAI, 2019.
Wenqing Sun, Bin Zheng, and Wei Qian. Computer aided lung cancer diagnosis with deep learning algorithms. Medical imuging 2016: computer-aided diagnosis, volume 9785, pp. 97850Z. International Society for Optics and Photonics, 2016.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International Conference on Machine Learning, pp. 3319-3328. ICML, 2017.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks, 2013.
denserilow-deeermmiism Python package. Available at: http://pwgoogggneeeeeeeaaoteeeer Retrieved on 6/5/2020.
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 10-19, 2019.
Arnaud Van Looveren and Janis Klaise. Interpretable counterfactual explanations guided by prototypes. arXiv preprint arXiv:1907 025844, 2019.
Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning: review. arXiv preprini arXiv:2010. 10596, 2020.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without without the black box: Automated decisions and the gdpr. Harvard Journal of Law & Technology, 31(2):841 -877, 2018.
Yibo Wang and Wei Xu. Leveraging deep learning with Ida-based text analytics to detect automobile insurance fraud. Decision Support Systems, 105:87-95, 2018.
Zifan Wang, Haofan Wang, Shakul Ramkumar, Matt Fredrikson, Piotr Mardziel, and Anupam Datta. Smoothed geometry for robust attribution. Neurips, 2020.
Zifan Wang, Matt Fredrikson, and Anupam Datta. Boundary attributions provide normal (vector) explanations. ArXiv, abs/2103.11257, 2021.
Cihang Xie, Zhishuai Zhang, Yuyin Zhou, Song Bai, Jianyu Wang, Zhou Ren, and Alan L. Yuille. Improving transferability of adversarial examples with input diversity. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
Linyi Yang, Eoin M Kenny, Tin Lok James Ng, Yi Yang, Barry Smyth, and Ruihai Dong. Generating plausible counterfactual explanations for deep transformers in financial text classification. arXiv preprint arXiv:2010. 12512, 2020.
13

---

Published as a conference paper at ICLR 2022
A PROOFS
A.1 THROREM AND LEMMA
Theorem Suppose that H1, H2 are orthognal decision boundaries in piecewise- network =(x)=signlf (eo),, and let x be un arbitrary point is domain. If the projections of x onto the corresponding halfspace constraints of H1,Hi are H1 and H2, then there exists point x' such that:
1) H()
2) d(x H2) H2)
3) d(x
where H.). denotes the distance between x and the nearest point boundary H..
Proof. Let u(x); Wox be the pre-activation of the neuron i-th output in the hidden layer. The status of the neuron therefore will have the following two status: ON if vu(x)>> and OFF otherwise. When neuron is ON, the post-activation is identical to the pre-activation. Therefore, can represent the ReLU function as a linear function of all neurons' activation status. Formally, the logit output of the network F can be written as
((x)=WAAN)
where A is diagonal matrix diag((Ao, ...,AA)) such that A; [xx])((x);;=> > 0). The network is a linear function within neighborhood if all points in such neighborhood have the same activation matrix A. For any two decision boundaries H2 and H2, the normal vectors of these decision boundaries can written nj w A₃ Wo and n. =wm Ag respectively, where Ai and Ag determined by the activation status of internal neurons.
For an input if the projections of onto the corresponding halfspace constraints of H₁, are on H₁ and H2, then the distance H1) and H2) are given by projections as follows:
In x |1|
In x
d(x, d(x,H1)=
H()
|2llz
W.I.O.G.. we assume F(x)= and n1 and na point towards Let point y defined
n y'vnn
n2
y=y-
(8)
[m 2
n
y -
(9)
[n
where is tiny positive scalar such that F(y)=F(xx =1. We firstly show that dly, =0 follows:
m2 y
H2)
(10)
|
|n_ (y"
|n
(11)
|| ||
[n y' 1/n |nTy'll
(12)
||nella
nn y nTy'
(1) tiny so n2 points to y")
(13)
[n /2
=0
(14)
14

---

Published as a conference paper at ICLR 2022
We secondly show that d(y (1y.HH) Hi) follows:
in yl
H(y,H:)
(15)
[m] 1a
|n] (y'
In]y'ln y'
|
(16)
|| l|2
In] (x-t-)
poi mlmg
[n] (x+7" my
(17)
||ma|la
In] (x++1 Toll
In x/*++)|lu |nnl222211
nj m2
13
(18)
||mi|12
n x x [illll
(H1 and H2 are orthogonal)
(19)
[n
In =
-1)
(20)
n le
The proof of Theorem is complete.
Lemma 1 Let H2,F and be defined in Theorem If the projections of onto the corresponding halfspace constraints of H,,Hz are on H1 and H2, but there does not exist point x' satisfying (2) and (3) from Theorem then H1 H2-
Note if we remove the assumption that H1 and H2 are orthogonal, we will show that Theorem I will Ing (x+7 (in la (2"")) )] })
hold by condition. Let mxx) = |n] x+ n. n.inn n22
Assume the angle between the
normal vectors of H1 and H2 is 0 such that n. n m ||m | 3
|20008.
[n (x+1)
m(x)= = |n x+
m
(21)
Ing
n2
m
n,
n
n
= |n| x+
(22)
n2
|22
= =In x - cos m
Xc
(23)
Since d(y.H1) xc m(x) and H1) x |n x and they share they same denominator ||n||2 In order to have m(x) > jnj x|. we just need 711 p11-ooo cas cas²8) ()][n|lll n, xcosf > 0, which means we need to find a 17 such that r cos20)][mn ||a nı xcosO. Moving terms around we have the following inequality:
nj xcos0
x l
(24)
cos
n
cost
cos
The RHS goes to when 0- which corresponds to the situation of Theorem When 0 (H, H2). RHS goes to oo, which means we cannot find a point satisfying the Theorem 1, which completes the proof of Lemma
A.2 THEOREM AND PROPOSITION
Theorem 2
Let f(x) del T -((x) + be a ReLU network with a single logit output (ie., a binary
classiffer), where h(x) is the output of the penultimate layer, and denote ow = =xxxx as the sigmoid output of the model at x. Let W adt {w' :lwlwww'''
A}, Xx=(x) be the distributional influence of
when weights ware used at the top layer, and XD (x) be the distributional influence of I when weights
w' are used at the top layer. If is K K-Lipschitz in the support S(Dx)), the following inequality holds:
Vw EW, llx2, (x:w) Xo, (x:w)) I| S K [[o[xx:)]l]]]-G]]
where C1 and O2 are constants and do (x:w) dul 3t
15

---

Published as a conference paper at ICLR 2022
Proof. Consider a ReLU network as g(h(x)). We first write out the expression of h(z):
(Wax+b)))
(25)
where & are the parameters for the i-th layer and dv(+) the corresponding ReLU activation. By the definition of the distributional influence,
do (0(((h()):w))
XD(x)= Dxx)(x)
(26)
Oz
(g) 0g(l::) 0h(x)
Dxx)(x)
(27)
0g
Oh
dz
N-1
(lz:))(-oozzz)) II (WAA()
Dxx)(
(28)
(29)
where W; is the weight of the layer I; I, is a dense layer or the equivalent weight matrix of a convolutional layer and (z) is an diagonal matrix with each diagonal entry being the neuron activated or 0 other wise when evaluated at the point z.
[xx(x) (x)x
(30)
N-1
-I(EnD(())
o (2::))
II (2)A
(31)
D(x)(
o (2: (2:w)) w/
(WGA(Z))
11
(32)
N-1
II (w)))2))
(1(2:)(1- |1
(33)
N-1 (W
<BewD(x)
(34)
(Jensen's Incquality from (33) to (34))
N-1
<EnDD(x)
II-I|
II (W.)Z)))TI
(35)
(By the definition of matrix operator norm from (34) (35))
To simplify the expression, we denote
a a= ((: -f
(36)
N-1
B II (W)
(37)
and now Equation (35) now becomes
[lxx(x) (roxx)-Xx(x))) Xx) |||||| [|]
(38)
with Cauchy-Shwartz inequality, we find that
Ex- |||||| [BII
(BnD(o))aa)) V Bnn
(39)
Now we will show that these two terms E a 2 and v Ex B are bounded.
(1) Bound for the term / (2a
16

---

Published as a conference paper at ICLR 2022
Consider the relation between the expectation and the variance of random variables
(EX))+Var(>
(40)
which implies that
E B2-D(x)lla) (Ex +
(41)
We simplify the notation by defining
do do oz
and we denote (z;w) do + (z;w) and do (z; - do (x) +z(, Note that ō because do E [0 Therefore, the E can be simplified as
ExxD(x)) |a|| = D(x) ( w(lp:///wwww////wooo//oo 6(z:w') wwll
(42)
- (x: w w dx; Ez ( 6(2:w))))))) ww'l
(Triangle Inequality)
(43)
) (x:
(( 2
(44)
< ldo (es::)-wdo(xxy)0) dx: + - |/ + 1000)/0))lll
(45)
ldo(x:)) do: (////|||w/
(5 4
(46)
ldo(x:))
[1|w|+
_/2
1
(|| =A)
(47)
1
1
< ldo do x: )w'
||+
(l/w ||+
A)
(Triangle Inequality)
(48)
2
2
< (x:w))
w/l
[|w||+
(do (do S
(49)
<xo w/l
|/|
+ +
(50)
To summarize, we find that
3
Be ||||| S (X::)////l++++>>>>
+
(51)
Since both sides of the inequalities are non-negative scalars, we see that
- w/|+
1 72
(EzwD(x)) 2aal)) do (xxx)))]llw)
(52)
2
The derivation of the variance term Vor([lal) may not have a simple analytical form to show that is bounded, but it is easy to find upper bound of |a]l|
||||| (x::)) (x);-d((xw))vv +0( -
(from Equation (43))
(53)
(o (wtp:///////l/////////////////// (|0 (1/2://// ww'll
(Triingle Inequality)
(54)
(do S 1 (1ww
|w|
+
(55)
5 A
|+
(56)
2
which implies that ||a|| |0.5||/||+34 With Popoviciu's inequality, the variance Var([la)) must be bounded such that
1
5 0
5 -
Var([la|]]
w|
(57)
2
17

---

Published as a conference paper at ICLR 2022
Now far we have derived the upper-bounds for (Ex~D(x)|la|))? and Var([la])); put together, show that
Eg Be / ||
(58)
where
C1 [|w/| + 1
(59)
5 C2 =
|w|| w||+| 12
(60)
2
(2) Bound for the term (B | |
B is the operator norm, namely the spectral norm for the matrix B, As we assume h(x) is K -LLipschiiz
we know that
N-
N-
Exx
B - D(xil
II
(WAA(2))
||5
sup z~((()
||
II
(WA((2))
(61)
(62)
and Vz~D(x)
N-11
B < sup
||
WW (z))
-K
(63)
z>D((x 1=1
(64)
Therefore,
|B||2<22
(65)
E Dzx) 2 K2
(66)
which implies | To put together, we finish the proof and show that
llxo(x) / De | [ 2 S [d([x//////////////0
(67)
A.3 PROPOSITION
Proposition Let g be differentiable, real-valued function in Bdd and S be the support set of Uniform(O -x). Vx ES,
0g(x')
0g(rx')
|| ||||
Or 1=
Ox'
Proof. First, we show that Vx ES
Oq(x')
0q(x') Ox
xX|
x115
||-1|/|||
(Cauchy-Schwarz)
(68)
Ox
18

---

Published as a conference paper at ICLR 2022
By the construction of x' we know
||x| || |xx| therefore,
dg(x') T
0g(x²)
||-1|x||
(69)
Ox!
0x'
0y(x')
Oy(x') T
xX|
(70)
Ox
Ox'
Now consider a function p(r:x') rx'. Then we show trick of chain rule.
0q(p) Or
aq(p)
0p(rxx)
dq(p) Ör
x
(71)
p
P
does not change the computation of taking the Jacobian of q's output with respect to the input; therefore, we show that
Replacing the notation p with x' in 0g(x')
8x
0y(x')
Dy(p) x
r= x O4(P)
0u(rxx)
Ör r-
r==1
(72)
Ox'
P
Gr
We therefore complete the proof of Proposition by showing
x
0g(rx')
|| |X|
(73)
Ox
Ör
B EXPERIMENT DETAILS
B.1 META INFORMATION FOR DATASETS
The German Credit Dua Karra Taniskidou 2017) and Taiwanese Credit Dua & Karra Taniskidou 2017 data sets consist of individuals financial data, with binary response indicating their creditworthiness. For the German Credit Dua & Karra Taniskidou (2017) dataset, there are 1000 points, and attributes. We one-hot encode the data to get 61 features, and standardize the data to zero mean and unit variance using SKLearn Standard scaler. We partitioned the data intro a training set of 700 and a test set 200. The Taiwanese Credit Dua & Karra Taniskidou (2017) dataset has 30,000 instances with 24 attributes. We one-hot encode the data to get 32 features and normalize the data to be between zero and one. We partitioned the data intro training set of 22500 and test set of 7500.
The HELOC Mataset|FICOO (0188) contains anonymized information about the Home Equity Line of Credit applications by homeowners in the US, with binary response indicating whether has even been more than 90 days delinquent for payment. The dataset consists of 10459 rows and 23 features, of which we one-hot encode to get dataset of 10459 all features to be between zero and one, and create train split of 7,844 and a validation split of 2,615.
the applicant
and 40 features. We normalize
The Seizure Dua Karra Taniskidou (2077) dataset comprises time-series EEG recordings for 500 individuals, with a binary response indicating the occurrence of a seizure. This is represented as 15000 rows with 178 features each. We split this into 7,950 train points and 3,550 test points. We standardize the numeric features to zero mean and unit variance.
The CTG Dua & Karra Taniskidou (2017) dataset comprises of 2126 fetal cardiotocograms processed and labeled by expert obstetricians into three classes of fetuses, healthy, suspect, and pathological. We have turned this into binary response between healthy and other classes. We split the data into 1,700 train points and validation split of 425. There are 21 features for each instance, which we normalize to be between zero and one.
The Warfain dataset is collected by the International Warfarin Pharmacogenetics Consortium Consortium (2009) about patients who were prescribed warfarin. We removed rows with missing values, 4819 patients remained in the dataset. The inputs to the model are demographic (age. height, weight, race), medical (use amiodarone, use of enzyme inducer), and genetic (VKORC1, CYP2C9) attributes. Age, height, and weight real-valued and were scaled zero and unit variance. The medical attributes take binary
19

---

Published as a conference paper at ICLR 2022
values, and the remaining attributes were one-hot encoded. The output is the weekly dose of warfarin in milligrams, which we encode as "low", "medium", or "high", following Consortium (2009)
The UCI datasets are under an MIT license, and Warfarin datasets are under a Creative Commons License. Dua & Karra Taniskidou (2017); Consortium (2009). The license for the FICO HELOC dataset is available at the dataset challenge website, and allows for research purposes FICO 2018b)
B.2 HYPER-PARAMETER, AND MODEL ARCHITECTURES
The German Credit and Seizure models have three hidden layers, of size 128, 64, and 16. Models on the Taiwanese dataset have two hidden layers of 32 and 16, and models on the HELOC dataset have two deep layers with sizes 100 and 32. The Warfarin models have one hidden layer of 100. The CTG models have three layers, of sizes 100, 32, and 16. German Credit, Adult, Seizure, Taiwanese, CTG and Warfarin models are trained for 100 epochs; HELOC models are trained for 50 epochs. German Credit models are trained with a batch size of 32; Adult, Seizure, and Warfarin models with batch sizes of 128; Taiwanese Credit models with batch sizes of 512, and CTG models with a batch size of 16. All models are trained with keras' Adam optimizer with the default parameters.
B.3 IMPLEMENTATION OF BASELINE METHODS
We describe the parameters specific to each baseline method here. Common choices of hyper-parameters shown in Table
Min-Cost l Wachter et al. (2018) We implement this by setting 3 = 1.0 for L (or 3.0 for Eg) and confidence=0.b for the clastic-net loss Chen et al. (0018) in Nicolae et al. (2018).
Min-c PGD Madry al. 20188: For given e, we use 10 interpolations between and the current e as the norm bound in each PGD attack. The step size is set to 2+ max.steps where 6g is the norm bound used. The maximum allowed norm bound is the median of the &g norm of data points in the training set.
Pawelczyk et al. Pawelezyk et al. (2020b): We train an AutoEncoder (AE) instead of Variational AutoEncoder (VAE) to estimate the data manifold. Given that VAE jointly estimate the mean and the standard deviation of the latent distribution, it creates non-deterministic latent representation for the same input. In the contact with Pawelczyk et al., we are informed that we can only use the mean as the latent representation for an input; therefore, by taking out the standard deviation from a VAE, we instead train a AE that produces deterministic latent representation for each input. When searching for the latent representation of a counterfactual, we use random search as proposed by Pawelczyk et al. PPawelzyk et al. (2020b): we randomly sample 1280 points around the latet representation of an input within norm bound of 1.0 in the latent space. When generating random points, we use fixed random seed 2021. If there are multiple counterfactuals, we return the one that is closest to the input. For all datasets, we use the following architecture for the hidden layers: 1024-128-3) 128- 1024.
Looveren et al. Van Looveren & Klaise 2019): We use the public implementation of this method We use k-d trees with & = 20 to estimate the data manifold as the curre implementation only supports an AE where the input features must be between and 1, while our dataset are not normalized into this range. The rest of the hyper-parameters are default values from the implementation: theta=100, max wwt.etttiinnn000 only supports for non-eager mode so we tur off the eager execution in TF2 by running tf. compat. v1. www.diiall....g...ee.et.t.eeeeea
This implementation
() for this baseline.
SNS : We run SNS for 200 steps for all datasets and project the counterfactual back to a lz ball. The size of the ball is set to be 0.8 multiplied by the largest size of the ball used for the baseline Min-c PGD. For Max f/l82 without a norm bound, we use the norm bound from Min-e PGD. Similarly, the step size set to 2+0.8+e/200,
httpa://docs.... sel don. http://ooooooooaaaaaaaa////aaaaa
20

---

Published as a conference paper at ICLR 2022
Hyper-parameters and Success Rate
Min 4
German Credit
Seizure
CTG
Warfarin
HELOC
Taiwanese Credit
step size
0.05 0.35
0.05
0.05
0.5
0.01
0.05
success rate
0.14
1.00
1.00
1.00
1.00
Min lg
German Credit
Seizure
CTG
Warfarin
HELOC
Taiwanese Credit
step size
0.01
0.01
0.01
0.01
0.01
0.01
success rate
0.84
0.71
1.00
1.00
1.00
1.00
Min e PGD
German Credit
Seizure
CTG
Warfarin
HELOC
Taiwanese Credit
Max.
3,00
3.00
0.20
0.50
2.10
5.00
step size
adp. 0.90
adp.
adp. 0.51
adp.
adp.
adp.
success rate
0.86
0.85
1.00
1.00
Looveren et al.
German Credit
Seizure
CTG
Warfarin
HELOC
Taiwanese Credit
step size
success rate
1.0
1.0
1.0
1.0
1.0
Pawelczyk et al.
German Credit
Seizure
CTG
Warfarin
HELOC
Taiwanese Credit
0.3
1.0
1.0
1.0
1.0
1.0
step size
success rate
0.38
1.00
0.87
0.72
0.76
0.14
Table Syper-parameters and Success Rate for each baseline methods. adp. denotes that the step size for each iteration is 2*e/max steps.
B.4 DETAILS OF RETRAINING
We evaluate counterfactual invalidation over models with one-point differences in their training set, or different random initialization. For each dataset, we train a base model F(0) with a specified random seed determine initialization, and specified vaainvalidationn split. We use this generate all counterfactuals. We then train 100 models with one-point differences in the training set from base model, as well as 100 models trained with different random initialization parameters. To do this, we randomly derive: training set S, a set O S of size 100 that consists of points drawn randomly from test data (i.e. with which to create 100 different training sets with one point removed, 5(W)), and a test set. Then, For each 2; E O, we train F(0y' on S(V)) by removing from S. To train the 100 models with different initialization parameters, simply change the numpy random seed directly before initializing model.
B.5 FULL RESULTS OF IV WITH STANDARD DEVIATIONS
The full results of invalidation rates with standard deviations are shown in Table 3
B.6 4 AND l2 RESULTS
The full results of & and lg costs with standard deviations are shown in Table
21

---

Published as a conference paper at ICLR 2022
Invalidation Rate (LOO)
Method
German Credit
Seizure
CTG
Warfarin
HELOC
Taiwanese Credit
Min. &
0.41--0.04
0.07-1:0099
0.44+00.22
0.30+10.03
0.30+10.03
+SNS
0.00++0.00
0.00++0.00
0.00+-0.00
0.00=+0.00
0.00+00.00
Min. E2
0.36++0.05
0.64+-0.06
0,48+-0.17
0.35++0.22
0.55++0.05
0,27+0005
+SNS
0.00++0.00
0.02++0.02
0.00++0.00
0.00++0.00
0.00++0.00
0.00+0.00
Min. PGD
0,28++0003
0,94+00011
0.04++0.03
0.10+0.01
0.04++00001
0.04+00.00
+SNS
0.00++0.00
0.04+-0.02
0.00++0.00
0.01+0000
0.00++0.00
0,00+0000
Lowvrrn et al.
0.25++0033
0,48+00.44
0.1 0.1188
0,26+0002
0.25++0.33
0,29+0006
Pawelezyk et al.
0.20++0.13
0.16+00.14
0.00++000
0.02++0.00
0.05++0.06
0.02+00011
Invalidation Rate (RS)
Min. &
0,56#0.05
0.29::0.09
0.35+0008
0.43+0007
0.78+00006
+SNS
0.07+0.02
0.01+0000
0.00=0.00
0.00
0.04
Min. Ez
0.56+0.06
0.77+0.12
0.49#0.15
0.30
0.61
0.72
+SNS
0.0620.04
0.13+:0.88
0.0010000
0.00=0.00
0.00
0.0410.04
Min. cPGD
0.61
0,94:0112
0.0910.04
0.1210.03
0.11:0002
0.24110.07
+SNS
0.12::0.03
0.1620008
0.00100000
0.02
0.00
0.11+0.05
Looveren et al.
0.4010.03
0.5410005
0.1810008
0.25
0.34
0.53
Pawelczyk et al.
0.35:10.16
0.11+0.17
0.0610004
0.01
0.15
0.2010.09
Table 3: Invalidation Rates with standard deviations for each datasets and each re-training situations. Results are aggregated over 100 models.
Counterfuctual Cost (Eg)
Method
German Credit
Seizure
CTG
Warfarin
HELOC
Taiwanese Credit
Min. &
1.33
0.17:0.11
0.50-0.33
0,2410.18
1.5610.94
Min. f2
4.49+11.00
8.23+-2.27
0.06++0.04
0.54+0.57
0.11+0008
1.65++1008
Looveren
5.37++2.53
8,40+16.96
0.11=:0.06
1.03:+0.46
0.45:0045
1.82
Min. PGD
1.02-10.57
1.36:10.38
0.08:10.03
0.31
0.32-1012
0.75+0022
Min.6, + SNS
3.00-0.82
0.25++0.08
0.80
1.71+0.12
3.50+00.1
Min.f + SNS
6.23-11.65
9.60:12.31
0.2110004
0.90
1.7110.11
4.68
PGD+ + SNS
3.03-10,38
3.60+:0.59
0.22++0.44
0.50=E0.11
1.79=0.15
2,78+00.9
Pawelczyk et al.
7.15-42.12
13.66:17.46
1.07-10.20
2.62
1.35-0093
4.24412.33
Counterfactual Cost (6,)
Method
German Credit
Scizure
CTG
Warfarin
HELOC
Taiwanese Credit
Min. f
2.09+2.00
0.16+0.19
0.48
0.35+0.30
2,40++2.84
Min. &
13.10
77.89-128.38
0.18:10.1
1.1710.91
0.4310031
9.76.L3,93
Louveren
15.93-18.93
76.99-169.93
0.16:10.12
1.75-10.9
0,97+11.05
6.1145..1
Min. PGD
6.311:3.56
14.55:1:.15
0.30:10.12
1.07-10.22
1.55:0.54
3.19+11.09
Min.f + SNS
13.81+22.96
0.5810.14
1.6110..2
7.1110.72
I1.04=3.17
Min.f, + SNS
11.54
96.08-+-7.80
0.57+0.10
2.17:00.5
7.18=0.75
16.63++3.76
PGD + SNS
14.21122.1
38.55:16.36
0.63
14140.36
7.64
10.19422.5
Pawelczyk et al.
38.48-+12.11
145.36+477.67
3.03++0.63
+6.48+266
4.51+33.22
12.22++7.49
Table 4: l and & costs of counterfactuals with standard deviations.
22


Reviews:
[{"review_id": "SJ1OxQl6XS", "reviewer": "Reviewer_gXiV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Pro:\n - Interesting and relevant topic\n - Well written (good structure and easy to follow)\n - \"Sound\" evaluation\n\nCons:\n - Relevance of counterfactuals could be made more prominent (in the introduction). Why are they so popular? etc.\n - Sec. 4.2 limited to changes in the top layer. I understand that some simplifications are necessary but this particular simplification seems very strong to me.\n - Implementation of SNS: The authors use 10 points to approximate the integral. Why exactly 10? How does the method behave for different number of points? This specific number looks like a magic number that needs further explanations.\n - I miss some comments on the computational complexity of the proposed method (SNS)", "summary_of_the_paper": "The authors study how counterfactual explanations of a Deep Neural Network change if the initial training settings are slightly changed. They find that even small changes in the initial training settings lead to huge differences in the counterfactual explanations. They propose a method for computing more robust (i.e. consistent) counterfactual explanations.", "summary_of_the_review": "Overall an okay paper with only minor (not too critical) issues as pointed out in the main review.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Lky1hdkvnaZ", "reviewer": "Reviewer_fWXE", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper presents a nicely thought out method on providing points on a manifold that are robust to small sometimes imperceivable  changes on the training parameters. \nHowever, the reviewer believes that the claims relating to counterfactual are based upon a not so accurate interpretation of causality. \nFirstly I would invite the authors to substitute definition 1 with the appropriate counterfactual definition from the textbook by J. Pearl, 2009, chapter 7. \nMoreover, I am under the impression that the problem of producing non robust counterfactuals is rooted to the fact that the methods explored by the authors do not impose any identifiability constraints that would guarantee the models learning the intended DAGs and producing accurate counterfactuals. As such I fail to understand the expectation that the models should produce correct and robust counterfactuals when there is no explicit constrain on the models to do so. The method proposed in this paper does not refer not attempt to solve any of the aforementioned points\nCounterfactual stability in categorical variables , effectively a similar outcome to this paper, was already already explored in [1].\n\nI would invite the authors to look into the field of identifiability and robustness when the appropriate causal inference methods are used and constraints enforced \n\n\n[1] Counterfactual Off-Policy Evaluation with Gumbel-Max Structural Causal Models; Oberst and Sontag ; ICML 2019", "summary_of_the_paper": "The authors propose a regularisation method that offers increased stability on counterfactual predictions when models are affected by small changes during deployment . The method is based upon a K-Lipschitz constant.", "summary_of_the_review": "Overall the paper has merit in terms of identifying examples that are robust upon small changes in the training procedure. The claims regarding to counterfactuals, explainability and causality I believe are a stretch. As such I recommend that the paper is changed such that it is in the proper context", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Bj1z64TClhh", "reviewer": "Reviewer_ZP6K", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "## Detailed summary\nWhile previous work finds a little higher counterfactual loss leads to lower invalidation rates in linear and well calibrated models. This paper focuses on deep NNs and show that with deep models, this may not hold as higher counterfactual loss does not mean CFE is further from the decision boundary, which invalids the conclusion in linear/well calibrated models. Theorem 1 shows that there exist data points x and x', and decision boundaries H1 and H2 s.t. x' is on H2 but is further to H1 than x, due to the complex decision boundary of DNNs. Lemma 1 further verifies this by showing if x' does not exist, then H1=H2.\n\nIt proposes distributional influence (DI), which uses gradient information to explain local decision boundaries (around a sample). Distributional influence is defined as the expected gradient of the output against the input in the local neighbor region of x ($\\mathcal{D}_x$).\n\nThey find a bound on the change of DI in terms of the model's Lipschitz continuity on the support of $\\mathcal{D}_x$. This means finding a high confidence CFE with low Lipschitz constant would likely to have lower invalidation rate. Based on this, they propose to maximize the confidence while minimize the Lipschitz constant under the constraint that the CFE x' and x share the same predicted label. This is transformed into eq.(4) by Proposition 1, where the second term is the maximal slope in Figure 2b. This is further simplified to eq.(5).\n\nIn experiments, they use UCI datasets, FICO HELOC and Warfarin Dosing. Note that only binary labels can be used. Results show SNS can lead to much lower invalidation rate. And SNS would lead to a higher counterfactual loss in general, as expected.\n\n## From the above, the strength includes\n1. Clear theoretical justification of the proposed method, although there are some imperfections.\n2. Good presentation and visualization (e.g., Fig. 2).\n3. Relative comprehensive results, considering various datasets, baselines and metrics.\n\n## Weakness includes\n1. Only relatively small tabular datasets are used, which is not the most widely used case for DNNs.\n2. Some details may need to be further clarified.\n\n# Questions and detailed comments:\n\nHow to compute the integral of SNS, what would be the complexity?\n\nThere is no causal model built and therefore, why the CFE in this paper is a counterfactual. If it is, which counterfactual distribution is it sampled from?\n\nWhat is a the x-axis and y-axis of Fig 2? I guess they are two input features but it is better to show them in the figure.\n\nIt is not very clear to me which terms are related to confidence in the equation of Theorem 2.\n\nI did not fully get why small change in DI always means low invalidation. I guess this has to be shown formally.\n\nWe know DNNs tend to be over-confident for unseen x. Would this result in any issue if we aim to find CFE with high confidence?\n\nWhat is the effect of relaxing the Lipschitz constant K from the penultimate output to the entire network? Would it increase or decrease, why?\n\nIt is better to clarify what is $t$ in Fig 2 since it is only defined in the later pages.\n\nTypo in page 6. zero vector (t=1) --> (t=0)\n\n", "summary_of_the_paper": "This paper aims to generate valid counterfactual examples (CFE) in a dynamic setting where the model can be retrained in the test time. The goal is to minimize the invalidation rate. Different from previous work, they focus on DNNs. Through a series of theoretical analysis, they propose to maximize the confidence and minimize the Lipschitz constant under the constraint that the CFE x' and x share the same predicted label.  Experiments on tabular datasets show the proposed method reduces the invalidation rate a lot.\n", "summary_of_the_review": "Copied from above.\n\n## Strength\n1. Clear theoretical justification of the proposed method, although there are some imperfections.\n2. Good presentation and visualization (e.g., Fig. 2).\n3. Relative comprehensive results, considering various datasets, baselines and metrics.\n\n## Weakness\n1. Only relatively small tabular datasets are used, which is not the most widely used case for DNNs.\n2. Some details may need to be further clarified.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0jL78_P3PKQ", "reviewer": "Reviewer_76Ar", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Novelty/Contribution**:\nTo the best of my knowledge, the consistency of counterfactuals has not been extensively studied. In my opinion, the main novelty is proposing Stable Neighbor Search (SNS), which finds counterfactuals in more locally Lipschitz regions. The results for SNS are promising -- it outperforms the benchmark methods (Van Looveren and Pawelczyk). \n\nA second contribution is the discussion of the relationship between Lipschitzness and counterfactual consistency. This contribution is less significant, in my opinion, as it is similar to discussions in the field of adversarial examples. In adversarial example literature, it is well-established that improving the Lipschitzness of a network will improve its adversarial robustness. \n\n**Correctness**:\nGenerally, I believe that the central argument of the paper is correct: generating counterfactuals in areas where the network has a smaller Lipschitz constant improves the consistency of counterfactual explanations. However, I am not sure whether the proof of theorem 2 is correct. There are some steps that require further clarification.\n\nSpecifically:  \n-  what property are you using in the step from lines 35-36 to 37-38? $E(ab)=E(a)E(b)$ requires $a$ and $b$ to be independent, but it's not clear to me why that holds in this case. \n- line 46: $d\\sigma (x,w)$ can be both positive and negative, right? As such, I think there should be an absolute value sign around $d\\sigma (x,w)$. \n- some unclear notation: $g$ is not defined in the main text -- is it the same as $f$?\n\n\n**Writing**:\nOverall, very well written and easy to follow. However, I do think the authors over-state some contributions in the introduction. For example,\n\"we prove that counterfactual examples in a neighbourhood where the network has a small local Lipschitz constant are more consistent against changes in the training environment (Theorem 2)\". Theorem 2 assumes (1) only a change in the final layer weights and (2) a relu network with a final sigmoid activation. The authors are explicit about this later on, however, I think the introduction should be written more carefully.\n\n\n**Minor language/formatting suggestions**: \n- Section 3: \" ... counterfactuals produce inconsistent outcomes in duplicitous models up to 94% of the time\"  This sentence reads as a fact, however it's shown empirically for a specific set of hyperparameters/datasets. There are likely cases when it holds for 100% of the time. As such, perhaps rephrase it as \"counterfactuals often produce inconsistent outcomes. Empirically, we've found that it occurs up to 94% of the time.\"\n- Section 4.2, sentence 1: \"characterizing the precise effect such as random initialization have on\" -> \"characterizing the precise effect of hyperparameters, such as random initialization, have on\"\n- Theorem 2: space missing between w and are in the statement, and a \".\" instead of a \",\" after forall $w' \\in W$. Perhaps define $h$ as a ReLU network, rather than $f$. The latter makes it easier to read (I was a bit confused about the sigmoid activation/ relu network for a moment).\n- Appendix, Proof Theorem 2. Page 16: for the equation numbering, (34), (36) and (38) should not be there. This can be remedied by using * or align in latex.\n- the definition of distributional influence should contain w in the main text (to be consistent with the appendix) \n\n----- \nPost-rebuttal update: I have increased my score as the authors have corrected their proof for Theorem 2. ", "summary_of_the_paper": "The paper focuses on the consistency of counterfactual explanations (i.e., the rate at which counterfactual explanations transfer across different models). The authors show that the consistency of counterfactuals does not necessarily relate to cost (i.e., the distance between input and the counterfactual). They propose an alternative theory: they investigate the relationship between local Lipschitzness and consistent counterfactuals. Based on this idea, they propose a new method (SNS) for generating counterfactual examples. Empirically, they show that SNS creates more consistent counterfactuals than van Looveren et al. and Pawelczyk et al.", "summary_of_the_review": "\nOverall, I like the paper and enjoyed reading it. However, I am currently recommending a 5 as I am not convinced by the correctness of the claims in the paper. Specifically, I have some concerns about the validity of Theorem 2 (elaborated upon in my main review). If the authors are able to clear up this aspect, I'm happy to reconsider my score. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Most of the discussion centered around whether the underlying question in the literature is setup correctly in terms of its relationship to causality as the question being asked is one of an intervention. The underlying literature makes an attempt at not including things that can't be intervened on like age, but the setup of a "counterfactual" could benefit from a causal take.

Holding that aside, the paper makes progress on an established question though analysis that reveals that the Lipschitz continuity and confidence are important for causality and Stable Neighbor Search for generating counterfactuals.

The most negative reviewer in discussion writes that they're okay with the paper being accepted if the rest of the reviewers are positive. The rest of the reviewers are positive with one mentioning that the paper is well written and interesting in the discussion and that the author replies cleared up the issues about counterfactuals.
Decision: Accept (Poster)