Simple Steps to Success: A Method for Step-Based Counterfactual Explanations
Authors: Jenny Hamer
Nicholas Perello
Jason Valladares
Vignesh Viswanathan
Yair Zick
Venue: Accepted by TMLR ()

Abstract: Algorithmic recourse is a process that leverages counterfactual explanations, going beyond understanding why a system produced a given classification, to providing a user with actions they can take to change their predicted outcome. Existing approaches to compute such interventions---known as recourse---identify a set of points that satisfy some desiderata---e.g. an intervention in the underlying causal graph, minimizing a cost function, etc. Satisfying these criteria, however, requires extensive knowledge of the underlying model structure, an often unrealistic amount of information in several domains. We propose a data-driven and model-agnostic framework to compute counterfactual explanations. We introduce StEP, a computationally efficient method that offers incremental steps along the data manifold that directs users towards their desired outcome. We show that StEP uniquely satisfies a desirable set of axioms. Furthermore, via a thorough empirical and theoretical investigation, we show that StEP offers provable robustness and privacy guarantees while outperforming popular methods along important metrics.

Published in Transactions on Machine Learning Research (10/2024)
Simple Steps to Success: A Method for Step-Based Counterfactual Explanations
Jenny Hamer*
hamer@google.com
Google Miep New York
Nicholas Perello'
sperello@humass.com edu
University of Massachusetts, Amherst
Jason Valladares Google
hason.vllladorr33@mmaad.ooo
Vignesh Viswanathan'
wuisuemathan@tmmasss
University of Massachusctts, Amherst
Yair Zick
yeick edu
University of Massachusetts, Amherst
Reviewed on OpenReview: https: openreview. net/ pet//fore forum? id- R6ey5DKaoX
Abstract
Algorithmic recourse is a process that leverages counterfactual explanations, going beyond understanding why system produced a given classification, to providing a user with actions they can take to change their predicted outcome. Existing approaches to compute such interventions known as recourse identify a set of points that satisfy some desiderata e.g. an intervention in the underlying causal graph, minimizing a cost function, etc. Satisfying these criteria, however, requires extensive knowledge of the underlying model structure, often unrcalistic amount of information in several domains. We propose a data-driven and model-agnostic framework to compute counterfactual explanations. We introduce StEP, a computationally efficient method that offers incremental steps along the data manifold that directs users towards their desired outcome. We show that StEP uniquely satisfies a desirable of axioms. Furthermore, via thorough empirical and thcoretical investigation, show that StEP offers provable robustness and privacy guarantees while outperforming popular methods along important metrics.
1 Introduction
An automatic decision maker produces a negative prediction for some user e.g. denies their grad school application, offers them bad loan terms or an overly strict criminal sentence; what can the user do to change this outcome? Counterfactual explanations (Wachter et al., 2017) recommend actions that change algorithmic predictions on given point. This is usually modeled as constrained optimization problem that outputs specific points which satisfy certain desirable properties: actionability, validity, data manifold closeness and causality to name a few (Verma et al., 2020). Achieving these desiderata often requires both significant compute power and user herr/moell information. We propose lightweight algorithm for producing counterfactun explanations; rather than searching for good interventions for users, we search for good directions that users can take. We use these directions to create an iterative recourse mochanism where stakeholders can repeatedly request new directions after carrying out the recommended changes. We
"oqual contribution
work completed during Master's University Massachusetts, Amherst.

---

Published in Transactions on Machine Learning Research (10/2024)
show that by carefully choosing these directions, we satisfy several desirable properties of algorithmic recourse at significantly lower computational cost.
1.1 Our Contributions
We propose a recourse algorithm called Stepwise Explainable Paths (StEP). Our koy theorctical insight is that StEP is the only method for generating recourse directions (counterfactual explanations) which satisfics a set of natural properties. StEP directions are model-agnostic and easy to compute, requiring only the training dataset and the output of the model of interest on points in the training dataset. That is, our method does not require prior knowledge of the underlying model architecture and instead takes strongly data-dependent approach. In addition to introducing StEP, a novel step-based recourse method, we present its provable quality (Section 3.1), diversity (Section 3.2), and privacy (Section 3.3) guarantees. We also provide an extensive experimental evaluation of StEP, including a holistic cross-comparison with three popular recourse methods (DiCE (Mothilal et al., 2020a), FACE (Poyiadzi et al., 2020), and C-CHVAE (Pawelczyk et al., 2020)) on three widely-used financial datasets- Credit Card Default (Yeh & Lien, 2009), Give Me Some Credit (Credit Fusion, 2011) and UCI Adult (Kohavi, 1996) datasets. We also investigate StEP's robustness to noise (Section 4.3).
1.2 Related Work
Counterfactual explanations are fundamental concept in the model explanation literature (Verma et al., 2020). First proposed by Wachter et al. (2017), they are founded in legal interpretations of explainability (Wachter et al., 2018) and are distinct from feature highlighting methods (Barocas et al., 2020), such as Shapley value-based methods (Datta et al., 2016; Lundberg & Lee, 2017), Local Interpretable Model-Agnostic Explanations (Ribciro et al., 2016) and saliency maps (Simonyan et al., 2013). Recent policy efforts describe algorithmic recourse as means for fostering trust in Al systems (Wachter et al., 2018; NTTA, 2023; Biden Jr., 2023). Whereas feature highlighting methods indicate important features (or feature interactions (Patel et al., 2021)), counterfactual explanations identify changes to features that are likely to change the outcome (Karimi et al., 2022; Verma et al., 2020). These changes are usually solutions to an optimization problem, ensuring that the explanations are valid, actionable, sparse and diverse (Mothilal et al., 2020a; Karimi et al., 2020a; Ustun et al., 2019a). These solutions are computed using integer linear programs (Ustun et al., 2019a; Kanamori et al., 2020), SAT solvers (Karimi et al., 2020a), or gradient descent (Mothilal et al., 2020a; Wachter al., 2017). Other works provide sequence of steps from the point of interest to a point with the desirable outcome along the data. manifold (Poyiadzi al., 2020). While these prior methods offer reasonable approaches to recourse generation, none of them axiomatically characterize their approach.
Another approach in the literature is to solve the causal problem of finding the best intervention (Karimi et al., 2021). Karimi et al. (2021) argue that any recourse recommendation must be consistent with the underlying causal relations between variables. However, this requires complete (or, as in Karimi et al. (2020b), imperfect) knowledge of the underlying causal model, which is often practically or computationally infeasible.
We address this issue by providing users with promising directional actions, allowing them more flexibility and agency in enacting recourse recommendations. Our axiomatic characterization is similar to that of Monotone Influence Measures (MIM) (Sliwinski et al., 2019). However, Sliwinski et al.'s approach is not iterative in nature, nor is their recommended direction guaranteed to change the prediction outcome.
2 Preliminaries
We introduce some general notation and definitions used throughout this work. We denote by Z E Rm a point of interest (PoI) corresponding to an individual or their current state, and define a datasct X (Et,,....,, C R with features and n datapoints. We use x; to denote the i-th index of the vector ø.
We focus on binary classification using a model of interest f R + +1 trained on the dataset X; our goal is to produce a counterfactual explanation for ē & X where f(z) = -1 The counterfactual explanation for a point of interest Z is direction (or set of directions) d T that moves the point z towards the positive
2

---

Published in Transactions on Machine Learning Research (10/2024)
Acceptance
Bonk Accomnt Bakkere
Honk Actoonnt Balesse
Donk Accomnt
Baundary
x
Rejeriloa
Pol
Credis
Store
Crecit
(a) The dalaset
(b) Possible Recourse Directions
(c) Possible Stakeholder Path
Figure 1: (Left) The training dataset that the loan approval algorithm uses, (Middle) Plotting possible
recourse directions for Example 2.1 and (Right.) plotting a stakeholder path toward loan acceptance.
class, i.e. [(E d) 1 for some positive value e> 0. We go beyond simply providing an explanation for the the Pol's outcome by framing our output recommended recourse which can be actioned by the user. Upon applying recourse to a Pol E, refer to H + c d as counterfactual (CF) of z denoted by IcF.
Offering single explanation may not be helpful in real-world settings; users may be unable to make single dramatic change to their features or may not exactly follow the suggested recourse. We allow the stakeholder to repeatedly request new recourse directions as they change their values until they are positively classified. We call such an approach direction-lused recourse. To illustrate this approach, consider the following example of algorithmic loan approval.
Example 2.1. Consider loan applicant whose application is rejected by an algorithm utilizing two factors: bank account balance and credit score. The loan applicant, i.e., the Pol, the algorithm, and the training dataset are described Figure la. Several directions can change the Pol's value from (red points with label -1) (blue points with label +1). For example, inercasing the crodit score while Icaving the bank account balance unchanged eventually changes the applicant's label; increasing both bank balance and credit score (Figure 1b) results in positive outcome. Suppose that we provide the applicant with both alternatives; the applicant makes some modifications and reapplies for loan. If the application is rejected, provide them with new directions, based on their current state, and repeat until the application is accepted. This results in a recourse path, rather than a single direction (Figure 1c).
We wish to ensure that our directions robust; thus, even if the stakeholder somewhat deviates from our suggested path, they are still likely to secure positive outcome. This also oflloads some of the computational costs onto the stakeholder, which guarantees certain recourse properties that would otherwise require a significant amount of information and computational cost. Consider Example 2.1: after providing two different directions, the change that the applicant makes to their datapoint will likely be minimum cost change that approximately follows one of the directions we propose in Figure 1b. Even the resulting change does not facilitate change in outcome, or is incorrectly executed, we can still offer additional directions until a desirable outcome is obtained.
2.1 Data-driven Recourse
Whether explanations should be computed based on the underlying model or the observed data highly debated topic (Chen et al., 2020; Barocas et al., 2020; Janzing et al., 2020). While data-driven recourse methods exist (Poyiadzi et al., 2020), most work solely with the model of interest f (Mothilal et al., 2020a; Wachter et al., 2017; Karimi et al., 2020a).
Recent work shows that explanations can perform poorly when they are inconsistent with the data manifold Le. the underlying distribution from which the data drawn (Frye et al., 2021; Aas et al., 2021) and are vulnerable to manipulation (Slack et al., 2020: 2021). Ignoring the data manifold when computing counterfactuals can be even more pernicious, resulting in recourse recommendations that may not improve the outcome in any way, but simply move it outside the data manifold. To see why this is the case, consider
3

---

Published in Transactions on Machine Learning Research (10/2024)
Donk Accoent Bakseee
Bonk Arcount Badaeror
thp
Credit
Credit
(a) The dataset and the model.
(b) Recourse directions
Figure 2: (Left) The training dataset that the loan approval algorithm uses, and (Right) Off manifold (di)
and On manifold (d2) directions.
Algorithm Stepwise Explainable Paths (StEP)
Require: Dataset X' partitioned into & clusters (Ki,..., point of interest H. model f, some non- negatively valued function Rz5 + Rz0
1:
while f(Ø) = do
2:
for every cluster CE [k] do
D Generaza
E (X' +)a(1E=' - end for
5: Offer the dircctions (detoe(M) to the stakcholder
6: Stakeholder returns an updated point of interest F²
7: x--
end while
simplified, two dimensional instance as shown in Example 2.1 but with a different point of interest (given in Figure 2a). The shortest distance perturbation which crosses the decision boundary corresponds to the direction di (as given in Figure 2b). This direction suggests that the stakeholder decrease their credit score and marginally increase their bank account balance, which actively moves the stakeholder away from the positively classified points. An explanation algorithm that recognizes the data manifold will offer a direction similar to d2, arguably making the stakcholder better candidate for loan approval.
3 Stepwise Explainable Paths (StEP)
We now present our approach for computing recourse directions. The overall method is summarized in Algorithm 1. We first partition the dataset X' into clusters ( Xx} (using a standard clustering algorithm). For a point of interest Z, we generate a direction de towards each cluster X, using the expression
d = Σ - - =)
(1)
FEN
where a : R4 + R4 is some non-negative function and ||-|| is rotation invariant distance metric. We select directions using Equation (1) (a similar formula is proposed by Sliwinski et al. (2019)). The intuition behind this equation is as follows: for each point in the cluster X,, if f(²)) 1, we 'move' on the line (ø - x²) a distance a([]=" - æ]I), where a a decreasing function of || - F1 Thus, points closer to have greater effect on de; similarly, positively classified points that are close to each other will have a greater effect on d. We offer these & directions to the stakeholder, who then returns with new point 7' after following the recourse recommendations. The process repeated until we produce positively classified point (i.c. a counterfactual) or reach a user-specified maximum number of iterations. StEP's computational complexity is linear in the size of the dataset and is bounded by the maximum number of iterations.
4

---

Published in Transactions on Machine Learning Research (10/2024)
3.1 An Axiomatically Justified Direction
We axiomatically derive our choice of direction in equation 1: we identify direction that uniquely satisfies set of desirable properties. More specifically, for given point of interest ã & Xe, we believe any reasonable recourse direction, denoted by d(ZT, Ne: f) should satisfy the following axioms:
Shift Invariance (SI) Let Xe+ 6D denote the dataset resulting from adding the vector to each point in X' and let fg be a shifted model of interest such that fz(2) f ( b) for all E. Then, d( Xes f) diE + 6, X. + b, fz).
Rotation /eaeeett/Reecttiin Faithfulness (RRF) Let A be any matrix with det(A) E f-1,++1 and let A. denote the dataset resulting from replacing every point F in X. with AT, Let lA denote a rotated model of interest such that fa(=) =( for all ह. Then, Ad(E, Ne, f) di A(A AXe, fa).
Continuity (C) d is continuous function of the dataset Xe. One can think of the continuity axiom notion of recourse robustness: small changes to the input Pol will not cause significant changes to the resulting recourse.
Data Manifold Symmetry (DMS) Let f and be two functions such that f(²) g(3)) for all points E E X. Then, we must have d(z, Xe, f) = d(ž Nex g).
Negative Classification Indifference (NCI) Let F' No be a datapoint with f(ī") = -1. Then, d(ī, Xe. f) = d( [T)
Positive Classification Monotonicity (PCM) Let F' $ de be a point with f(3') and x > 24, then d(E Xe, f) s (F X. ff). Similarly, if 2 < Fi, then (E, Ne. f) 2 d Xe U {.)).
Our axioms are inspired by Sliwinski el al. (2019), who use a similar approach to characterize a family of direction-based based explanations (Monotone Influence Measures). Unlike the MIM framework, we remove any dependency negatively classified points (the Negative Classification Indifference axiom). Without this change, naive adaptation of MIM may output directions pointing away from all positively classified points. Intuitively, a cluster of negative points near positive points may make it impossible to recommend any recourse, as the MIM framework "shies away" from negative point clusters (see details in Appendix A).
The five remaining axioms are fundamental. Shift Invariance and Rotation Gotation/Refee RReflection Faithfulness ensure the directions depend on the relative locations of the points rather than their absolute values. The RRF axiom also generalizes the feature symmetry axiom: swapping the coordinates of features and j does not change the value assigned to them; this is commonly used in the characterization of other model explanation frameworks (Datta et al., 2015; 2016; Patel et al., 2021; Lundberg & Lee, 2017; Sliwinski et al., 2019). In addition, these properties ensure the units in which we mcasure feature values have no effect on the outcome, e.g., measuring income in dollars rather than cents has no effect on the importance of income. Continuity ensures that the direction we pick is robust to small changes in the cluster X.. Data Manifold Symmetry (DMS) ensures that the direction depends on the model of interest only through points in the dataset. In other words, DMS ensures that the model's output on points outside the data manifold do not affect the output direction Chen et al., 2020). Positive Classification Monotonicity (PCM) ensures that the direction will point towards regions with large number of positively classified points. In other words, if there is a large number of positively classified points with a high value in some feature i E N (e.g. bank balance), PCM ensures that the output direction will ask the stakeholder to increase their bank balance.
desirable property in model explanations (Frye al., 2021; Lundberg & Lee, 2017;
Any direction which satisfies the above axioms is uniquely given by Equation (I): ie. is a weighted combination of the directions from the point of interest to every positively classified point in the dataset. The weight given to every point is function of their distance -II-
Thcorem 3.1. A recourse direction for a point of interest given a dataset Xo, a model of interest f and rotation invariant distance metric ||-||| satisfies SI, RRF, C, DMS, NCI and PCM if and only if it given by equation 1.
5

---

Published in Transactions on Machine Learning Research (10/2024)
Proof. For readability, we replace X. with X. It is easy to see that equation satisfies all five axioms only show uniqueness.
We assume without loss of generality that X' contains no negatively classified points. If X' does contain any negatively classified points, we can simply remove them without changing the recourse direction because of Negative Classification Indifference (NCT). Therefore, our goal is to show that any direction which satisfies (SI), (RRF), (C), (DMS), (NCI) and (PCM) of the form
d(z, > -a( 2)
PEEX
We start off with useful lemma.
Lemma 3.2. If any direction d satisfies Rotation and Reflection Foithfulness (RRF) and Positive Classi- Sictton Monolonicity (PCM), then for any dalaset X, any dalapoinl T, any model of interest J and any positively classified point T $ I, there erists some 2 0 such that
( d( aiū - z)
Proof. Suppose for contradiction that there is some I, X, 7 and f such that
Ya 0: X f) d(z X, f) + alj x)
Let T- such matrix exists since the two vectors either linearly independent or T= bbj F) where E IR+.. Since d satisfies Rotation and Reflection Faithfulness (RRF), we have from (Al); < 0
d(, f). Let A be a rotation matrix such that (Al): 0 and [A(T- - x)}1 > 0;
(AF, ( fa) - dA <
This contradicts the Positive Classification Monotonicity (PCM) property since (Aj)) > (Ar) and fa(AT) ( 1.
Consider a direction d' that satisfies the six desired axioms. We go ahead and show uniqueness via induction on [.]. Let k = 0, X () By Shift Invariance (ST), d(tt, 0..) = d(o, (-/- The vector Ô and an empty X' are invariant under rotation. Therefore, since satisfics Rotation and Reflection Faithfulnoss (RRF) and Data Manifold Symmetry (DMS), we must have d(0, f-) = 0, the only vector invariant under rotation.
Let == 1, 1 where 7 / म. Note that any pair of (Z, can be translated by shift and rotation to any other pair (F",g") with the same distance (117-a0 between them. This is because the distance metric (II-I) is rotation invariant and any distance metric shift invariant when computing the distance between two points; the shifts cancel each other out. Note that after rotation by some matrix A, we have fa = f and similarly, after shift by some vector 6, we have + b) = f(ū). Therefore, the label of the point y does not change after applying Shift Invariance (ST) or Rotation and Reflection Faithfulness (RRF). Therefore, by (SI), (RRF) and Lemma 3.2, we have
- -
where a is a non-negative valued function.
Suppose the hesot holds when | S k. Consider a dataset. y of size k ++1 1. This means y contains at least two distinct points & Z. We prove our hypothesis for the case where ÿ and ă are linearly independent. The case where they are linearly dependent follows from Continuity (C): we can peturb the vectors slightly make them linearly independent. By Lemma 3.2, we have
dEyY E A (d(z,))) - ( aaū-))
and d(zY,f) B- (d(z,)) (2), -((
(2)
6

---

Published in Transactions on Machine Learning Research (10/2024)
Donk Accoent Balsece
Bonk Acceent Balseror
Crodit Score
Credit
(a) No Clustering
(b) With Clustering
Figure 3: Directly applying the direction formula equation 1 without clustering to find recourse directions may result in undesirable behavior, e.g. excluding variety of options and picking an off-manifold direction (Left). Clustering resolves this issue (Right).
By the inductive hypothesis, we have
(1.3), =I) - x)
and d(z y (2) dd -
We can use this and the fact that y I and म are linearly independent to combine the two sets in equation 2 to get
= -D -
T. a(1 - - - -[]====[))(= -r)
This completes the induction.
Reducing stakeholder "travel distance" to reach a positive classification is common objective used in algorithmic recourse (Mothilal et al., 2020a; Karimi et al., 2020a; Mahajan et al., 2019). This distance can be seen as a measure the effort required from the stakeholder to change their outcome. We can incorporate this StEP using the choice of a. Any a function of the form a(z) = 1 with k 2 2 ensures that nearby points are assigned greater weight than far-off points. Different choices of result in different directions.
3.2 Diverse and On-Manifold Recourse via Clustering
Despite its theoretical soundness, utilizing StEP without clustering presents two drawbacks.
Lack of guaranteed diversity In many cases, changing the function does not result in diverse set of directions even when many directions are possible. Consider slight modification to Example 2.1 (given by Figure 3) where the class of positive points is separated into two clusters. A recourse algorithm could reasonably output a direction towards eit cluster as a potential recourse. However, Equation (1) outputs a linear combination of these two clusters. Furthermore, it is easy to see that changing the function a will not significantly change the direction.
Off-manifold directions Since Equation equation aggregates directions, is possible to obtain off- manifold directions (refer to Figure 3a); off- off-manifold regions may have high prediction error.
Without clustering, Equation equation aggregates directions obtained for different parts of the datasct, rather than treating different data regions differently. We resolve both aforementionel concerns by clustering the positively classified data points and compute directions per individual cluster. This ensures that we identify different clusters of points and aggregate each cluster in a theoretically sound manner. The impacts are demonstrated in Figure
3.3
Direction Selection
One potential concern when using the dataset directly compute recourse that StEP could potentially leak sensitive user data. (indeed, other model explanation algorithms have been shown to leak private information
7

---

Published in Transactions on Machine Learning Research (10/2024)
Milli et al. (2019); Shokri et al. (2021)). With clustering, it may not be possible to offer privacy guarantees since the clustering process itself may not be privacy preserving. However, we can show that the StEP distance computation itself is privacy-preserving (see Dwork & Roth (2014) for a formal exposition to differential privacy). Briefly, an algorithm M that takes as input a dataset X' and outputs a value M(X) is said to be (e, -ddffferrrettllllyy private if for all range(M), we have:
Pr(M(X)) E S) Se Pr(M((2))) E S]+
where and X' are any two datasets that differ by at most one datapoint. Differential privacy states that the output of M does not vary much by the removal of any data point. A simple method prove that function is differentially private to upper bound its sensitivily, i.e. the change to the function when adding a datapoint. Dwork & Roth (2014) show that adding finite amount of noise to bounded scnsitivity function guarantees differential privacy. A similar guarantee is offered for Shapley-based (Dalla et al., 2016), and gradient-baser based (Patel et al., 2022) explanations.
StEP (without clustcring) can be made diffcrentially private for a specific family of a functions, when the distance metric used is the l2 norm. More formally, we assume that a<=) s L for all = > 0, then we can bound the sensitivity of StEP.
Lemma 3.3. When the distance metric used is the & norm and (x2) < E for all > 0, the global sensitivity (using the lg norm) of the direction given by equation 1 is upper bounded by C.
Proof. Let the direction output of equation (in the absence of clustering) for a particular dataset X, a model of interest and point of interest 전 be d(E,X, f).
The global scnsitivity of equation 1 using the 2a norm is given by
A2d=
max ZX
|[ X -'
(3)
where X" is X' with one additional (or one less) datapoint. (Dwork & Roth, 2014). We can assume without loss of generality that X' contains one additional positively classified datapoint J.. If the point is not positively classified, then none of the directions change and the sensitivity 0. The global sensitivity defined in equation 3 reduces
C
A2d = max | - - J,."
- #I(2)I(I((> 1)lla
< max 3,3"
(F'
- F)
(by assumptions and f(z")
F
1
< max
-C -1 C
F.F
F
In the first inequality, assume ||| F- 0 so apply ((10===11)
パ If If z'112 0,
then by definition we must have z = F which implics And = 0 and the lemma trivially holds.
Since the direction has bounded sensitivity, classic results from the differential privacy literature tell that. introducing Gaussian noise makes the direction (c, differentially private.
Thcorom 3.4. When the distance metric used is the & norm and a(z) S C. equation 1 can be made (e, diffferrrrllll privale by adding Gaussian noise with O mean and slandard deviation sC where 32 > 2 log( هات to all the features.
x' the directions output by
The proof of Theorem 3.4 direct application Dwork & Roth (2014, Theorem 3.22) and is omitted. Offering multiple recourse dircctions results in an additive increase in privacy cost. More specifically, if we provide directions, and each direction is (c differentially private, then our mechanism is (ke, k6) differentially private (Dwork& & Roth, 2014).
8

---

Published in Transactions on Machine Learning Research (10/2024)
Dataset
Type
Classification task
LogReg
Forest
DNN
Credit Card Default
Financial
payment default
1000
535
559
Give Me Some Credit
Financial financial distress
1000
332
426
UCT Adult
Demographic
income >$50k
1000
1000
1000
Table 1: Dataset descriptions. Values for logistic regression (LogReg), random forest (RandForest) and
2-1ayer DNN (DNN) reflect average number of negatively classified datapoints in the test set across 10 trials. We limit the number of datapoints used for recourse (from the test split) to 1000.
4 Empirical Evaluation & Analysis
We compare the performance of StEP and three popular recourse methods DiCE (Mothilal et al., 2020a), FACE (Poyiadzi et al., 2020) and C-CHVAE (Pawelezyk et al., 2020) on three widely used datasets within counterfactual research using three base models. We also examine StEP's robustness noise or "user- interference" when following recourse directions. We provide an overview of our experimental setup here and include full details to support reproducibility in Appendix C. Recall that counterfactual point for I is a terminal point of recourse path, ËcF, such that f(ăcF) = 1.
Recourse Baselines Given a negatively classified Pol I, DICE solves an optimization problem that outputs a diverse set of counterfactuals. For each of these counterfactual points Ecr, (#cr - Ø) can be interpreted as a direction recommendation for the Z. FACE constructs an undirected graph over the set of datapoints and finds a path from the point of interest & set of positively classified candidate points using Djikstra's algorithm (Dijkstra, 1959). Each edge in the path that connects 7 to Ter can be thought of as direction recommendation from 전 to žcr. The backend of C-CHVAE (Pawelezyk et al., 2020) is variational autoencoder (VAE): distances within the latent space surrounding the Pol is used to identify counterfactual points. We use the author's 's implementation for DiCE and adapt FACE's and C-CHVAE's implementations from Poyiadzi et al. (2020) and Pawelczyk et al. (2021).
.,,,, Given a negatively classified Pol I,, StEP and FACE produce a sequence of points (i", ,..., the original Pol, Æl the point after following the first direction recommendation by the recourse method, and on. DiCE and C-CHVAE, produce two point sequences (7 .7). We refer to this sequence of points recourse path, and each of the directions be referred to "step".
where z²) is
Datasets and Models We employ three real-world datasets in our cross-comparison analysis: Credit Card Default (Yeh & Lien, 2009), Give Me Some Credit (Credit Fusion, 2011), and UCI Adult/Census Income (Kohavi, 1996), described in Table For each dataset, we train and validate logistic regression, random forest, and two-layer DNN model instances following 70/15/15 training, validation, and test (recourse-time) data splits. Based on balanced hyperparaneter tuning across all recourse methods, we specify a confidence threshold of 0.7 at test time for each base model to determine whether Pol is positively classified. Implementation and hyperparameter tuning details are described in Appendix C.2.
Metrics & Properties In alignment with counterfactual and recourse literature, we use the following well-established metrics to evaluate the performance of StEP, DiCE, FACE, and C-CHVAE on each base model and dataset (Verma et al., 2020). In the following definitions, we are given a recourse path (x "e,,",...,, where 70th is the Pol A recourse path successful if f(*) = 1, i.. the recommended path ultimately produced counterfactual _ TcF. Our results report the average of these metrics over all Pols.
Success (or validity (Verma et al., 2020)) measures the proportion of Pols with successful path.
Average Success measures the proportion of successful paths generated for given Pol Æ.
& Distance is the Euclidean distance between the Pol 50 and the final point F ie. ||500 - - Distance is only computed for successful paths. Low distance, or prozimal, recourse, supports actionability.
Diversity the average Euclidean distances between the counterfactuals of each successful recourse path for given Pol Z. Diversity is only computed for Pols with least two successful recourse paths.
9

---

Published in Transactions on Machine Learning Research (10/2024)
Logistic Regression
Random Forest
DNN
Max Error %
Avg Success
Avg Success
Avg Suc Auccess
Sucoess
E Dist.
Diversity
Success
Dist.
Diversitty
Suceess
4 Dist.
Diversity
Dataset Method
StEP
1.00
0.91
7.06
2.58
1.00
0.84
0.95
1.00
1.00
1.29
8.51
Credit
DICE
1.00
1.00
35.28
12.93
1.00
1.00
20.34
8.35
0.99
0.99
32.47
13.02
2.96
Card
Default
FACE
0.54
0.54
4.46
0.78
0.51
0.51
2.75
0.88
0.45
0.45
4.38
0.93
3.16
CCHVAE
1.00
1.00
7.88
1.17
1.00
1.00
3.22
0.29
1.00
1.00
5.11
0.34
5.03
StEP
0.98
0.70
15.32
10.73
1.00
0.74
4.03
9.91
1.00
0.99
5.87
2.15
15.91
Give Me
DICE
0.99
0.99
103.68
38.77
1.00
1.00
73.54
31.16
0.99
0.99
95.45
37.14
3.33
Some
Credit
FACE
0.98
0.98
2.97
0.57
0.96
0.96
0.63
0.93
0.93
0.59
0.98
CCHVAE
0.06
0.06
2.24
0.13
1.00
1.00
1.40
0.02
1.00
1.00
4.18
0.03
15.07
StEP
1.00
0.54
2.39
1.37
0.89
0.47
4.93
2.09
1.00
0.56
2.40
1.38
4.01
UCT
DICE
1.00
1,00
6.75
1.76
1.00
1,00
7.57
1.35
1.00
1.00
7.03
1.60
5.66
Adult
FACE
0.63
0.63
3.02
0.74
0.63
0.63
2.77
0.77
0.64
0.64
3.02
0.76
0.83
CCHVAE
1.00
1.00
2.57
0.46
0.93
0.92
2.59
0.44
0.99
0.99
2.77
0.51
8.48
Max Error %
6.70
7.25
15.94
15.07
1.89
2.95
7.86
6.49
1.50
1.50
7.72
14.83
Table 2: Comparative analysis results all datasets and base models. Metrics computed scaled data and averaged over 10 trials. We include max. standard error bounds for each metric by task and across tasks.
4.1 Categorical Variables and Actionability
We provide rigorous support for categorical variables, including immatable, semi-mutable, ordinal and unordered. Immutable fcatures-ond -ones that cannot be changed, c.g. race-ane ignored during recourse. Semi-nutable features can only be changed in one direction, e.g,, education level can only increase. Ordinal features, e.g. an ordered scale like ratings, are encoded features using a Borda scale (from to k). The remaining categorical features are encoded via one-hot encoding.
For recourse to be practically relevant, methods should offer actionable directions (Ustun et al., 2019b): those which do not suggest infeasible changes changes to immutable features, Lee that the user can actually execute. Constraints are natural way of preventing recommendations that ask a user to perform an infensible action, e.g. becoming younger or less educated to secure loan. StEP encodes such constraints within its distance metric, in a manner similar to DICE (Mothilal et al., 2020a). For each dataset and task, we implement all appropriate encodings and constraints so that the directions producod by StEP satisfy actionability desiderala and requirements. Refer Appendix C.1 for encodings by dataset.
4.2 Comparative Analysis of StEP, DiCE, FACE, and C-CHVAE
For each Pol, we generate = 3 recourse paths, repeat this over 10 trials, and compute metrics and statistics based on the resulting counterfactuals. The comparison of StEP, DiCE, FACE, and C-CHVAE on all base models are presented Table 2. We introduce additional metrics and further discussion in Appendix
StEP For all tasks, StEP offers balance between minimizing distance and maximizing diversity performance. StEP's lower distance recourse supports actionability- more proximal counterfactuals may be more actionable to the user-wile providing variety in the suggested directions. We observe differences between distance and diversity-while maintaining a desirable tradc-off between the two metrics-acres across basc models while consistently performing well on success. On UCI Adult, SLEP exhibits significantly different success compared to average success. Given that StEP produces a recourse path for each of its underlying & clusters, average success may be roduced when one or more of these clusters contains many outliers. However, even in this setting, StEP produces successful counterfactuals for the remaining clusters. This supports StEP's robustness to outliers and generalization to the tail of the underlying data distribution.
10

---

Published in Transactions on Machine Learning Research (10/2024)
StEP is also robust to the choice of base model, providing a consistent balance between proximal and diverse counterfactuals with high success. Even with simple base model (logistic regression), StEP balances desirable metrics, while reducing lg distance under more complex yet lightweight models (Random Forest or DNN).
DiCE Across tasks, DiCE consistently produces successful recourse paths. Since DiCE selects counterfactuals by solving an optimization problem with a diversity objective, we unsurprisingly observe that the method consistently excels on this metric. This performance comes with trade-off of much higher distance from the given Pol. This suggests that DiCE could be useful when highly varied recourse options desirable, but at the cost of potentially inactionable recourse given the very high distance to the Pol (and therefore very significant changes to be made by the user).
When FACE produces successful recourse, it consistently performs well w.r.t. E2 distance in other words, its counterfactuals are close to the original Pol. In aggregate across datasets, however, FACE's sensitivity to distance between datapoints in its underlying graph results in unrcliable success performance. Our results suggest that increasing the nonlinearity of the base model does not assist FACE in this dimension. Additionally, FACE exhibits significant trade-off between low distance between Pol and its counterfactual(s) and diversity. For k > 1, FACE finds the closest counterfactual, objective which is orthogonal to promoting diversity.
FACE
C-CHVAE Across tasks, C-CHVAE performs competitively on l distance, but produces counterfactuals with very low diversity. C-CHVAE's objective relies on similarity via distance in the latent space of its VAE, so each of the successful & recourse paths produces counterfactual which is as close as possible to the original Pol. Across nearly all tasks, C-CHVAR excels in terms of success but exhibits trade-off between proximal successful counterfactuals and diversity.
Despite these strengths, we observe a core weakness of C-CHVAE demonstrated by its surprisingly poor success on Give Me Some Credit under the logistic regression base model. To ensure that generated counterfactuals lic on the data manifold, for a given PoI, C-CHVAE's autoencoder approximates the conditional log likelihood of its nutable features given the immutable features. Therefore, for a given imnutable value (e.g. a protected class like race or gender), if there are few datapoints with high-confidence positive predictions, C-CHVAE will generate counterfactuals based on low-confidence prodictions. In this task using logistic regression, only 8% of positively classified training examples had feature value age S 59. This significant feature imbalance means that C-CHVAF generated fals with a confidence level of < 0.7 for these datapoinis, demonstrating C-CHVAE's sensitivity to feature imbalance and risk in magnifying biased data.
Unlike with StEP, when DICE, FACE, and C-CHVAE are unsuccessful at producing recourse for a given Pol, they fail for all k paths, resulting in equal success and average success.
4.3 Practical Robustness Considerations for StEP
Clustering. We evaluate StEP's sensitivity to the choice of underlying clusters across all tasks and base models. Firstly, using off- the-shelf k-means, we vary k between {1....,6) 66. Appendix B.6 show that StEP is robust to both the number and relative size of clusters when using k-means. We also evaluate StEP under random clustering, by assigning each point to a random cluster value from [l..... k). Our metrics of interest slightly improve as k increases. We hypothesize that this improvement stems from the finer-grained dataset partitioning, which allows StEP to produce a path (within the given maximum number of iterations) from the Pol to at least one cluster. Even under random clustering, StEP performs well on most metries. Given the strict categorical constraints in the UCT Adult task, the center of each random cluster being distributed uniformly across the entire dataset results in some clusters being inherently less reachable for many Pols.
Our empirical results in
User interference. Algorithmic recourse models commonly assume that users exactly follow suggested actions. In Appendix B.7, we relax this assumption by introducing a noise parameter 3 as a proxy for how much a user deviates from the prescribed direction. We construct a noise vector where each dimension that represents continuous feature in the dataset. is independently sampled from the standard normal distribution
11

---

Published in Transactions on Machine Learning Research (10/2024)
Logistic Regression
Random Forest
DNN
Max Error %
Noise (a)
Successs
Avg Suceeses
F2 Dist.
Diveriity
Successs
Arg Successs
fo Dist.
Diversity
Stecess
Avg Successs
E Dist.
Diversity
Dataset
0.0
1.00
0.91
7.06
2.58
1.00
0.84
3:20
0.95
1.00
1.00
5.04
1.29
8.51
Credit
0.1
1.00
0.90
7.09
2.58
1.00
0.87
3.22
0.95
1.00
1.00
5.04
1.29
8,51
Card
Default
0.3
1.00
0.92
7.10
2.57
1.00
0,90
3,20
0.96
1.00
1.00
5.02
1.30
8,54
1.00
7.06
2.57
0.91
3.13
1.00
1.00
5.01
1.31
8.64
0.0
0.98
0.70
15.32
10.73
1.00
0.74
4.03
9.91
1.00
0.99
5.87
2.15
15.94
Give Me
0.99
0.81
13.68
9.98
1.00
3.50
2.14
1.00
5.87
2.15
14.90
Some
Credit
0.3
0.99
0.90
9.95
7.73
1.00
1.00
2.83
1.69
0.96
0.95
3.90
2.15
14.33
0.5
0.99
0.92
8.03
6.37
1.00
1.00
2.42
1,44
0.95
0.95
3.45
2.10
13.09
0.0
1.00
0.54
2.39
1.37
0.89
0.47
4.93
2.09
1.00
0.56
2.40
1.38
4.01
UCI
0.1
1.00
0.53
2.35
1.36
0.89
0.47
4.93
2.07
1.00
0.55
2.35
1.37
3.84
Adult
0.3
1.00
0.53
2.34
1.36
0.89
0.47
4.91
2.07
1.00
0.55
2.34
1.37
3.94
0.5
1.00
2.32
1.35
0.89
0.47
4.86
1.00
0.55
2.31
1.36
3.96
Max Error %
1.06
7.25
15.94
12.41
1.64
2.95
11.14
14.24
0.72
0.80
9.41
14.90
Table 3: User-interference experiment results. Metrics are computed on scaled data and averaged over trials. Maximum standard error bounds for each metric by task and across tasks are included.
and the remaining dimensions zero. We scale this noise vector to magnitude ||d]], where d is the original recourse vector and 3 E Rg0 The noise vector is then added to d as the next suggested action.
The results presented in Table 3 demonstrate StEP's robustness to user-interference and other noise. The improvemends in performance w.r.t. success, avg success, and l distance in many cases can be interpreted as noise providing a benefit similar to small amounts of stochasticity in gradient methods (e.g. SGD, momentum), helping StEP move out of a local minima. We include additional results and discussion on this task in Appendix B.7. This case study provides considerable empirical evidence to StEP's robustness to deviation from the suggested recourse.
5 Discussion and Conclusion
We introduce StEP, data-driven method for direction- based algorithmic recourse that does not depend on the underlying model or knowledge of its underlying causal relations. We show that the directions computod by StEP uniquely satisfy set of desirable properties, which be made differentially private under mild assumptions. We empirically demonstrate StEP's ability to produce actionable and diverse recourse, its robustness to user-interference, and its practical utility.
In Section 3.2, we discuss the limitations of StEP without clustering and highlight the necessity of a clustering- based approach. Modulating h controls the number of clusters (and, in turn, number recourse directions produced); a clustering with too fine of a granularity may result in unsuccessful recourse paths for some of the clusters. While standard clustering methods perform well in practice, thorough analysis of their effects StEP could provide useful insights in practical deployment settings.
An additional limitation of SLEP is its dependence on how we measure distances between datapoints, with DiCE, FACE and Wachter's method. Defining new encoding schemas for categorical variables and investigating different notions of distance in the use of StEP and other recourse methods is an interesting area of future work. Finally, StEP and other recourse methods raise questions regarding group fairness, e.g. whether StEP offers similar performance for users from different. protected groups.
Acknowledgements.
The authors thank Neel Patel for early discussions. Perello and Zick are supported Army Research Lab DEVCOM Data and Analysis Center Contract W911QX23D0009
12

---

Published in Transactions on Machine Learning Research (10/2024)
References
Kjersti Aas, Martin Jullum, and Anders Løland. Explaining individual predictions when features are dependent: More accurate approximations to shapley values. Artificial Intelligence, 298, 2021.
Solon Barocas, Andrew D. Selbst, and Manish Raghavan. The hidden assumptions behind counterfactual explanations and principal reasons. In Proceedings of the 3rd ACM Conference on Fairness, Accountability and Transparency (FAccT),, pp. 80 89, 2020.
Joseph R. Biden Jr. Executive order 14110: Safe, secure, and trustworthy development and use of artificial intelligence. Federal Registrar, 881210))751111-55226 2023.
Hugh Chen, Joseph D. Janizek, Scott Lundberg, and Su-In Lec. True to the model true to the data? In Proceedings of the 5th Annual Workshop on Human Interprelabilily in Machine Learning (WHT), 2020..
Will Cukierski Credit Fusion. Give me some credit, 2011. URL httpss///aggll..co//mmmttttttti GiveMeSomeCredit.
Amit Datla, Anupam Datla, Ariel D. Procaccia, and Yair Zick. Influence in Classification via Cooperative Game Theory. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAT), pp. 511 517, 2015.
Anupam Datta, Shayak Sen, and Yair Zick. Algorithmic Transparency via Quantitative Input Influence: Theory and Experiments with Learning Systems. In Proceedings of the 37th IEFE Conference on Security and Privacy (Oakland), pp. 598 617, 2016.
Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik; 1:269 271, 1959.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy, Foundations and Trends in Theorelical Compuler Science, 9(3 4):211 1):211-407, 2014.
Christopher Frye, Damien de Mijolla, Tom Begley, Laurence Cowton, Megan Stanley, and Ilya Foige. Shapley explainability on the data manifold. In Proceedings of the 9th International Conference on Learning Representations (ICL.R), 2021.
Dominik Janzing, Lenon Minorics, and Patrick Blöbaum. Feature relevance quantification in explainable A1: A causal problem. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2907-2916, 2020.
Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, and Hiroki Arimura. Dace: Distribution-awaare counter- factual explanation by mixed-integer linear optimization. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pp. 2855-2863 2020.
Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Model-agnostic counterfactual expla- nations for consequential decisions. In Proceedings of the 23nd International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 895 955-905, 2020a.
Karimi, Julius von Kügelgen, Bernard Schölkopf, and Isabel Valera. Algorithmic recourse under imperfect causal knowledge: probabilistic approach. In Proceedings of the 33rd Annual Conference Neural Information Processing Systems (NeurIPS), pp. 265 277, 2020b.
Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: From counterfactual explanations to interventions. In Proceedings of the 4th ACM Conference Fairness, Accountability and Transpurency (FAccT), pp. 353 -362, 2021.
Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: Contrastive explanations and consequential recommendations. ACM Computing Surveys, 55(5), dec 2022.
Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD), 1996.
13

---

Published in Transactions on Machine Learning Research (10/2024)
Scott M. Lundberg and Su-In Lee. A Unified Approach to Interpreting Model Predictions. In Proceedings of the 30th Annuul Conference on Neural Information Processing Systems (NewrIPS), pp- 4768 44777, 2017.
Divyat Mahajan, Chenhao Tan, and Amit Sharma. Preserving causal constraints in counterfactual petpiirrfcctallepppaaattiiooo explanations for machine learning classifiers. ArXiv, abs/19122 /tt/1912.03227,, 2019.
Smitha Milli, Ludwig Schmidt, Anca D. Dragan, and Moritz Hardt. Model Reconstruction from Model Explanations. In Proceedings of the 1st ACM Conference on Fairness, Accounlability and Transparency (FAT*), pp. 1-9, 2019.
Ramaravind K. Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 3rd ACM Conference on Fairness, Accountability and Transporency (FAceT), pp. 607-617, 2020a.
Ramaravind K. Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classificrs through diverse counterfactual examples. In Proceedings of the 3rd ACM Conference on Fairness, Accounlability and Transporency (FAceT), 2020b.
NTIA. AI accountability policy request for comment. Federal Register, 88(71):22433 -22411, April 2023.
Neel Patel, Martin Strobel, and Yair Zick. High dimensional model explanations: an axiomatic approach. In Proceedings of the 4th ACM Conference Fairness, Accountability and Transparency (FAccT), pp. 401-411, 2021.
Neel Patel, Reza Shokri, and Yair Zick. Model explanations with differential privacy. In Proceedings of the 2022 ACM Conference on Fairness, Accountability and Transparency (FAceT), pp. 1895-1904, 2022.
Ma Pawelezyk, Klaus Broelemann, and Gjergii Kasneci. Learning model-agnostic counterfactual explana- tions for tabular data. In Proceedings of the 26th International World Wide Web Conference (WWW), pp. 3126-3132, 2020.
Martin Pawelczyk, Sascha Bielawski, Johan Van den Heuvel, Tobias Richter, and Gjergji. Kasneci. Carla: A python library to benchmark algorithmic recourse and counterfactual explanation algorithms. In Proceedings of the 34th Annual Conference on Neural Information. Processing Systems (NeurIPS) Track on Datasets and Benchmarks, 2021.
Rafael Poyiadzi, Kacper Sokol, Raul Santos- Rodiitge, Tijl De Bie, and Peter Flach. FACE: Feasible and actionable counterfactual explanations. In Proceedings of the 3rd AAAT/ACM Conference Artificial Intelligence, Ethics and Society (AIES), pp. 344 350, 2020.
Marco T. Ribeiro, Sameer Singh, and Carlos Guestrin. Why Should I Trust You?: Explaining the Predictions of Any Classifier. In Proceedings of the 22nd International Conference on Knowledge Discovery and Data Mining (KDD), pp. 1135 1144,114,4 2016.
Reza Shokri, Martin Strobel, and Yair Zick. On the privacy risks of model explanations. In Proceedings of the 4th AAAT/ACM Conference on Artificial Intelligence, Ethics and Sociely (AIES), 2021.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint 1xXiu:3312.003/ 2013.
Dylan Slack, Sophic Hilgard, Emily Jia, Samoer Singh, and Himabindu Lakkaraju. Fooling LIME and SHAP: Adversarial attacks on post hoc explanation methods. In Proceedings of the 3rd AAAI/ACM Conference on Artificial Intelligence, Ethics and Society (ATES), pp. 180-186, 2020.
Dylan Slack, Anna Hilgard, Himabindu Lakkaraju, and Sameer Singh. Counterfactual explanations can be manipulated. Proceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 62 75, 2021.
14

---

Published in Transactions on Machine Learning Research (10/2024)
Jakub Sliwinski, Martin Strobel, and Yair Zick. A Characterization of Monotone Inftuence Mcasures for Data Classificatton. In Proceedings of the 33rd AAAT Conference on Arlificial Intelligence (AAAT), pp- 2019.
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the 2nd ACM Conference Fairness, Accountability and Transparency (FAccT), pp. 10-19, 2019a.
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. Proceedings of the 2nd ACM Conference on Fairness, Accountability and Tronsparency (FAT*), pp. 10-19, 2019b.
Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning; A review, 2020.
Sandra Wachter, Brent Mittelstadt, and Luciano Floridi. Why right to explanation of automated decision- making does not exist in the general data protection regulation. International Dala Privucy Law, 7(2):
76 99, 2017.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: automated decisions and the GDPR. Harvard Journal of Low & Technology, 31, 2018.
I-Cheng Yeh and Chehui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2, Part 1):2473 2480, 2009.
15

---

Published in Transactions on Machine Learning Research (10/2024)
Boundary Rejection
Bank Account Balance
POI
Acceptance
X
dMMM
X
X
X
X
Credit Score
Figure 4: An example where the MTM direction points away from all the positively classified points.
A Issue with the Naive Adaptation of MIM
MTM (proposed by Sliwinski et al. (2019)) is a data driven approach to explain the outcome of point ø. Intuitively, it direction that moves towards points of the same outcome and moves away from points of the opposite outcome. It is given by:
d( -)--E) FEX
f())
where a is a non-negative valued function and 1(.) takes the value if the input condition is true and 0 otherwise. We can naively adapt MIM for recourse by flipping the direction, moving towards positively classified points and away from negatively classified points. This would give us the direction:
d(, ΣE' -)o(|E= -1)) # f()))
FEX
This direction, unfortunately, can lead to bad recourse recommendations. To see why, consider Example 2.1 with a different dataset and point of interest (given in Figure 4). When nearby points are given a higher weight than far away points, the direction output by MIM could be poor, pointing away from all the positively classified points. This because when nearby points are given a higher weight than far away points, the push away from negatively classified points can be stronger than the pull towards positively classified points. This is indeed what happens in Figure 4.
B Additional Empirical Investigation
We compare StEP with three methods, DiCE, FACE, and C-CHVAE by generating k = recourse instructions for each negatively classified datapoint in the test set for each dataset.
With StEP, we first partition the positively labeled training data into 3 clusters, and then for each Pol in the test set, we produce a direction for each of the clusters. In these comparative experiments, we use sci-kit learn's default k-means implementation without any tuning, and we assume the the stakeholder follows the provided direction exactly.
B.1 Baseline Recourse Methods
We compare StEP DiCE (Mothilal et al., 2020a), FACE (Poyiadzi et al., 2020), and C-CHVAE Pawelozyk et al. (2020). DiCE outputs diverse set of points, FACE outputs a set of paths that terminate at a positively classified point, and C-CHVAE outputs points in the latent. neighborhood of the PoT using an autoencoder.
16

---

Published in Transactions on Machine Learning Research (10/2024)
Given point E such that f()) -1, DiCE uses determinantal point processes and solves the following optimization problem to output diverse set of m counterfactual explanations {τ) ......,,
m2
arg min 12
loss([(E)),
dist(Cs T))
77
m7
C2.., cm)
Each of the output points ?j can be seen as a recommendation for the direction Ej - E. Due to the structure of the optimization problem, none of these output points are guaranteed to be positively classified. We run DICE with the default hyperparamcter settings.
FACE constructs undirected graph over the set of data points and finds path from the point of interest. to set of positively classified candidate points using Djikstra's algorithm (Dijkstra, 1959). All the results generated in this paper use distance threshold of 3 and the max length of path is capped at 50 data points.
C-CHVAE utilizes a variational autoencoder to construct a low-dimensional neighborhood within a radius around the Pol and scarches for counterfactuals within each iteration the radius to scarch around gets expanded by given step distance hyperparameter. We run C-CHVAE with a step distance of and the max number of iteration to 50. For the remaining hyperparameters, we use the default given by Pawelezyk et al. (2021). We modify Pawelezyk et al.'s implementation for C-CHVAE to support non-binary categorical features and k > counterfactuals.
B.2 Additional Comparative Analysis
We define three appropriate metrics, path length, path steps, and prozimal diversity motivated by direction-based algorithm.
Path length is the sum of Euclidean distances between the steps of a recourse path. A shorter path length requires stakeholders to work less to change their outcome. Formally, the path length given by E- 1122 Path lengths are only computed for successful paths.
Path steps corresponds to the number of steps laken in the path, given by 1- When the number of steps is 1 (as is with DiCE and C-CHVAE), distance and path length are the same.
Proximal Diversity (Prox. Diver.) is the total Euclidean distances between the counterfactual points of each successful recourse path for a given Pol Z normalized by distance from the furthest terminal point to the Pol,
Z 112-
maxiel,.... 1 0
-
Elll2
i=1
j=i
To provide diverse recourse one can simply provide counterfactual points siguificantly distant from each other and the PoL. This makes recourse less actionable and the metric value less interpretable, therefore normalize by max distance (proximity) between the Pol and its counterfactuals to scale this. Proximal diversity is only computed for Pols where at least two recourse paths successful.
The results for these new metrics are presented in Table 4. Proximal diversity reflects our observations on distance and diversity Section 4.2. That is, StEP has diverse and close in distance recourse and DiCE has highly diverse and far in distance recourse. Proximal diversity weighs these two aspects, resulting in similar performance between the two methods. Given that DiCE and C-CHVAR do not output points between the Pol and counterfactual, path steps was always one step.
B.3 Discussion of DiCE
Since DiCE is not direction-basod mothod, we generate i counterfactual points and interpret the difference between the original Pol ă and counterfactual Eer as a proxy for the path take. In our experiments, DiCE almost always generates valid counterfactual explanation but this counterfactual is usually much
17

---

Published in Transactions on Machine Learning Research (10/2024)
Logistic Regression
Random Forest
DNN
Max Error %
Path Length
Path Steps
Prox. Diver.
Path Length
Path Steps
Prox. Diver.
Path Length
Path Steps
Prog. Diver.
Success
Sucerss
Success
Dataset Method
SLEP
7.23
2.49
1.00
3.70
3.75
5.04
5.13
2.09
6.88
Credit
DiCE
1.00
35.28
1.00
2.43
1.00
20.34
1.00
2.23
0.99
32.47
1.00
2.64
2.96
Card
Default
FACE
0.54
5.61
2.18
2.02
0.51
3.68
1.56
2,49
0.45
5.04
2.06
2.16
1.75
CCHVAE
1.00
7.88
1.00
0.96
1.00
3.22
1.00
0.76
1.00
5.11
1.00
0.57
3.53
StEP
0.98
15.86
15.86
2.41
1.00
4.12
4.12
2.09
1.00
5.87
5.87
2.19
15,42
DICE
0.99
103.68
2.34
1.00
73.54
1.00
95.45
1.00
2.38
3.33
Some
Credit
FACE
0.98
2.72
1.07
1.92
0.96
2.80
1.01
2.01
0.93
2.81
1.01
1.91
1.13
CCHVAE
0.06
2.24
1.00
0.13
1.00
1.40
1.00
0.15
1.00
4.18
1.00
0.13
15.07
StEP
1.00
2.70
2.70
2.48
0.89
5.35
5.46
2.46
1.00
2.57
2.65
2.47
3.98
UCI Adult
DICE
1.00
6.75
1.00
1.65
1.00
7.57
1.00
1.20
1.00
7.03
1.00
1.43
3,98
FACE
4.29
2.14
0.63
3.83
1.72
2.41
0.64
2.16
0.83
OCHVAE
1.00
2.57
1.00
1.24
0.93
2.69
1.00
1.24
0.99
1.00
1.35
5.19
Max Error %
6.70
15.42
15.42
15.07
2.21
7.58
7.58
5.13
1.50
7.72
7.72
6.88
Table 4: Comparative analysis results on all datasets and base models. Metrics are computed on scaled data and averaged over 10 trials. The maximum standard error bounds for each metric by task (row) and across tasks (column) are included.
farther from the Pol than StEP on average, which requires the user to make very large changes at each step of recourse. Furthermore, sometimes the counterfactual can be away from the data manifold.
B.4 Discussion of FACE
FACE is a direction-bassd recourse method which finds the shortest path from each Pol to positively classified candidate points that exist within the graph (i.e. counterfactuals) The existence of edges between points in graph are determined using distance threshold parameter. If two points have distance less than the distance threshold, an edge is generated; otherwise, no edge spans the two points. Intuitively, the distance threshold determines the size of the step users are required to take when following FACE's recourse.
Finding an appropriate distance threshold for FACE is a challenging and highly task-dependent requirement. If the distance threshold loo small, the graph becomes sparse and lypically produces few no successful recourse paths. On the other hand, the distance threshold is very large, the graph becomes dense and recourse generates trivial paths between Pols and candidate points consisting of a single edge. In this case, FACE produces brittle recourse.
One possible option for the distance threshold is to set it equal to the step-size of StEP (equal to 1) to ensure a fair comparison of the two methods, which results in very few successful paths being generated (in some tasks, with success rate as low as 0). When increasing the distance threshold between to 3, FACE begins non-trivial paths across our tasks. All the results generated this paper are using the distance threshold 3.
B.5 Discussion of C-CHVAE
C-CHVAE uses both the encoder and decoder from variational autoencoder trained the given dataset. The encoder transforms data points into a low-dimensional representation and the decoder reconstructs latent representations to the original dimension. During it's search, C-CHVAE encodes the Pol and samples points around the hyper-sphere around it. These points are then decoded and tested on the base model to determine if they are counterfactuals. In each iteration, C-CHVAE expands the hyper-sphere samples around by a given step distance hyperparanter. To find counterfactuals, we continue the algorithm until k counterfactuals found via sampling.
18

---

Published in Transactions on Machine Learning Research (10/2024)
Logistic Regression
Random Forest
DNN
Max Error %
Noise (0)
Path Length
Path Steps
Prux. Diver.
Path Length
Path Steps
Prox. Diver.
Poth Length
Path Steps
Prox. Diver.
Suecess
Success
Sucersss
Dataset
0.0
1.00
7.23
7.42
2.49
1.00
3.70
3.75
2.22
1.00
5.04
5.13
2.09
6.88
Credit
0.1
1.00
7.43
7.73
2.49
1.00
4.26
4.31
2.22
1.00
5.15
2.09
6.82
Card
Default
0.3
1.00
7.91
8.34
2.49
1.00
4.75
4.85
2.25
1.00
5.19
5.33
2.09
6.66
0.5
1.00
8.36
8.93
2.48
1.00
4.73
4.92
2.28
1.00
5.44
5.69
2.11
6.41
0.0
0.98
15.86
15.86
2.41
1.00
4.12
4.12
2.09
1.00
5.87
2.19
15.42
Give Me
0.1
0.99
16.26
16.27
2.42
1.00
3.52
3.53
2.77
1.00
5.89
5.89
2.20
11.20
Credit
0.3
0.99
12.59
12.64
2.48
1.00
2.92
2.93
2.86
0.96
4.03
4.05
2.24
9.71
0.5
0.99
10.45
10.57
2.34
1.00
2.60
2.62
2.94
0.95
3.77
3.81
2.29
8.52
0.0
1.00
2.70
2.70
2.48
0.89
5.35
5.46
2.46
1.00
2.37
2.65
2.47
3.98
0.1
1.00
2.64
2.94
2.49
0.89
5.81
6.34
2.47
1.00
2.46
2.82
2.47
4.76
Adult
0.3
1.00
2.63
3.01
2.49
0.89
5.79
6.47
2.46
1.00
2.44
2.88
4.72
0.5
1.00
2.62
3. 16
2.48
0.89
5.70
6.73
2.45
1.00
2.43
3.02
2.47
4.77
Max Error %
1.06
15.42
15.42
5.20
1.64
11.20
11.20
2.35
0.72
9.41
9.41
6.88
Table 5: intefennereeeence analysis results on all datasets and base models. Metrics are computed on scaled data and averaged over 10 trials. The maximum standard error bounds for each metric by task (row) and across tasks (column) included. "Prox. Diver." is shorthand for proximal diversity.
In most tasks, this iterative process of expanding the search radius step-by-step aids C-CHVAR in producing low distance counterfactuals with high success. However, the encoding and decoding steps lead C-CHVAE to be sensitive to strong relationships between mutable and immutable features, leading to failures in certain tasks as described in Section 4.2. The choice of number of iterations, step distance, number of & counterfactuals did not affect the poor success on Give Me Some Credit under logistic regression. We recommend careful dataset selection when using C-CHVAE, as the relation between immutable and mutable features can be and is often discriminatory.
B.6 The Effects of Clustering StEP
StEP supports base clustering methods which allow the user to specify the number of clusters (e.g. k-means) and those which estimate a number clusters (c.g. affinity propagation). With the latter, the clustering method determines k the number of potential recourse paths StEP can produce.
We suggest using clustering approaches where the user can specify the number of clusters (number of recourse paths), aligning with more traditional recourse methods. Methods that empirically determine number of clusters to satisfy some objective function can result in a large k-while having multiple recourse paths is desirable, past a certain threshold loses its marginal utility, can overload users, and become challenging to interpret if one is considering all of those paths without additional post-processing.
The consideration around number of clusters has more to do with how the clusters are distributed in high- dimensional space relative the learned docision boundary of each classifier, rather than as function of "cluster goodness" or quality. From these results, show that SCEP is robust to the nunber of clusters for k-means, and therefore also robust to the relative size of each cluster.
We expect that clustering can negatively impact recourse when the clustering method and base model leverages immutable features. Intuitively, as an example within the Give Me Some Credit, one of the k clusters reflects an older/ree /eder/retired population unlikely to experience financial distress. Additionally, as observed in the C-CHVAE analysis Scction 4.2, only 8% of positively classified training examples had a feature value age < 59 under logistic regression. Therefore, StEP consistently fails find a path to this cluster for Pols younger than 59 years old. This is reflected in StEP 's Avg Success under logistic regression and Give
19

---

Published in Transactions on Machine Learning Research (10/2024)
Logistic Regression
Random Forest.
DNN
Max Error %
Avg Successs
Avg Succoss
Avg Success
Success
E2 Dist.
Diversity
Successs
6 Dist.
Diversity
Success
E Dist.
Diversity
Dataset
k
0.90
0.90
5.03
0.00
1.00
1.00
2.99
0.00
1.00
1.00
4.65
0.00
1.27
Credit
2
0.92
0.87
6.17
2.01
1.00
1.00
3.10
0.77
1.00
1.00
4.95
1.10
1.46
Card
Default
1.00
2.58
1.00
0.84
3.20
1.00
1.00
5.04
1.29
8.51
1.00
0.93
6.96
4.48
1.00
0.86
3.30
1.78
1.00
1.00
5.06
2.38
6.54
1.00
0.95
7.06
4.96
1.00
0.88
3.65
2.52
1.00
1.00
5.19
2.83
11.13
1.00
0.95
7.22
5.50
1.00
0.90
3.44
2,40
1.00
1.00
5.29
3.37
8.56
0.58
0.58
2.37
0.00
1.00
1.00
2.83
0.00
1.00
1.00
0.00
8.67
Give Me
2
0.90
0.70
8.78
6.58
1.00
0.73
4.12
10.28
1.00
1.00
4.17
0.27
31.71
Some
Credit
0.98
0.70
15.32
10.73
1.00
0.74
4.03
9.91
1.00
0.99
5.87
2.15
15.94
4
1.00
0.75
15.27
18.64
1.00
0.79
6.56
16.35
1.00
0.98
6.26
4.42
10.51
1.00
0.73
15.60
19.85
1.00
0.81
7.21
17.57
1.00
0.98
6.11
4.66
11.00
1.00
0.73
14.73
19.11
1.00
0.82
7.58
18.57
1.00
0.98
6.23
5.01
11.24
0.24
0.24
1.89
0.00
0.23
0.23
2.09
0.00
0.35
0.35
1.86
0.00
3.21
UCI Adult
2
1.00
0.62
1.94
0.86
0.89
0.56
4.53
1.98
1.00
0.67
2.06
0.85
4.50
1.00
0.54
2.39
1.37
0.89
0.47
4.93
2.09
1.00
0.56
2.40
1.38
4.01
1.00
0.48
2.35
2.12
0.89
0.39
4.91
3.15
1.00
0.63
2.37
2.11
4.03
1.00
0.58
2.28
2.09
0.90
0.44
4.20
3.05
1.00
0.63
2.33
2.07
5.31
1.00
2.33
2.16
0.44
3.75
2.99
1.00
0,60
2.37
2.15
3.58
Max Error %
6.23
8.28
31.71
31.71
3.21
8.45
12.86
21.53
2.89
2.89
7.72
14.83
Table 6: Number of clusters for k-means clustering results. Metrics are computed on scaled data and averaged over 10 trials. Maximum standard error bounds for each metric by task and across tasks are included.
Me Some Credit in Table 2. However, the other clusters wore reachable for most Pols, mcaning StEP almost always had a successful recourse path for every Pol.
From our empirical results, the consideration around number of clusters has more do with how the clusters are distributed in high-dimensional space relative to the learned decision boundary of each classifier, rather than as a function of "cluster gooduess" or quality. From these results, we show that StEP is robust to the number of clusters for k-means, and therefore also robust to the relative size of each cluster (Table 6).
We also generated results with uniformly random cluster assignments, i.c., each point randomly assigned a cluster value from {1....,k} (Table 7). The & = 1 case for both k-means and random clustering produce the same results (as expected). For random clustering, as increases, we observe small improvements across our metrics of interest and that StEP demonstrates reasonable performance on most tasks. We note that, given the strict categorical constraints in the UCI Adult task, some clusters inherently less reachable for many Pols.
B.7 Additional StEP User Interfenteee Results
In Table 5 present results the path length, path steps, and proximal diversity metrics (defined in Section B.2). The noise 3 we introduce offers insights into StEP's behavior. Interestingly, introducing noise produces improvements in performance on the Give Me Some Credit Dataset (Table 3) by decreasin path length and path steps while providing a small boost proximal diversity. Recall that StEP clusters the positively labeled evaluation data which introduces additional hyperparameters: the number of clusters, k and the clustoring method. We cluster the evaluation data in full without removing any outliers via sci-kit learn's off- tho-shelf k-means algorithm. In particular, one cluster in the Give Me Some Credit dataset contained several outliers.
20

---

Published in Transactions on Machine Learning Research (10/2024)
Logistic Regression
Random Forest
DNN
Max Error %
Avg Success
Avg Success
Avg Success
Success
Do Dist.
Diversity
Success
Eo Dist.
Diversity
Success
82 Dist.
Diversity
Dataset A
1
0.90
0.90
5.03
0.00
1.00
1.00
2.99
0.00
1,00
1,00
4.65
0.00
1.27
Credit
2
0.90
0.89
5.04
0.05
1.00
1.00
2.99
0.03
4.65
0.01
10.48
Card
Default
3
0.91
0.89
5.04
0.09
1.00
1.00
2.99
0.05
1.00
1,00
4.65
0.02
8.33
0.92
0.89
5.04
0.13
1.00
1.00
2.99
0.06
1.00
4.65
0.03
6.03
5
0.93
0.90
5.05
0.15
1.00
1.00
2.99
0.07
1.00
1.00
4.65
0,04
6.10
6
0.94
0.90
5.06
0.18
1.00
1.00
2.99
0.09
1.00
1.00
4.65
0.04
6.53
1
0.58
0.58
2.37
0.00
1.00
1.00
2.83
0.00
1.00
1.00
4.11
0.00
8.67
Give Me
2
0.59
0.58
2.37
0.03
1.00
1.00
2.82
0.04
1.00
1.00
4.11
0.00
32.44
Some
Credit
3
0.60
0.58
2.39
0.05
1.00
1.00
2.81
0.06
1.00
1.00
4.11
0.01
31.38
0.62
0.59
2.39
0.07
1.00
1.00
2.82
0.07
1.00
1.00
4.11
0.01
30.58
5
0.63
0.59
2.40
0.08
1.00
1.00
2.83
0.09
1.00
1.00
4.11
0.01
24.86
6
0.66
0.59
2.40
0.09
1.00
1.00
2.80
0.10
1.00
1.00
4.11
25.59
1
0.24
0.24
1.89
0.00
0.23
0.23
2.09
0.00
0.35
0.35
1.86
0.00
3.21
UCI
2
0.25
0.25
1.90
0.08
0.23
0.22
2.10
0.06
0.36
0.35
1.87
0.08
22.89
Adult
3
0.26
0.25
1.92
0.17
0.25
0.22
2.12
0.11
0.36
0.35
1.87
0.16
9.92
4
0.27
0.25
1.93
0.20
0.25
0.22
2.13
0.16
0.37
0.35
1.89
0.20
11.87
5
0.28
0.25
1.94
0.28
0.26
0.22
2.13
0.19
0.37
0.35
1.90
0.27
9.85
6
0.28
0.25
1.95
0.31
0.26
0.22
2.15
0.23
0.37
0.35
1.90
0,26
7.62
Max Error
2,91
2.52
1.19
15.89
8.99
32.44
3.30
2.95
4.76
22.89 89
Table 7: Number of clusters for random cluster assignment results. Metrics are computed on scaled data and averaged over 10 trials. Maximum standard error bounds for each metric by task and across tasks are included.
When generating recourse for Pol V. StEP produces direction towards the centers of each of the clusters. Any outliers in the evaluation data can cause dramatic shifts in the directions, due to the sparse topology of the outlier clusters.
The Give Me Some Credit dataset exhibits significant variance between the mean path length across the clusters. Beyond removing outliers from the dataset, we suggest the following to correct for the variance influenced by the presence of outliers: (a) increase the number of clusters used and ignore the paths computod for cluster which has an average path length of standard deviations higher than the mean path length between the other clusters; (b) increasing the number of clusters may help disperse the cluster assignments of outliers, and the more clusters StEP uses results in more paths produced, which help support generating greater number of viable suggested recourse options for a given stakeholder.
C Experimental Details for Reproducibility
C.1 Datasets Details
we produce random train, validation, and test sets from the 30, 000 instances using 70/15/15 split, resulting in sets with approximately 21k/4.5k/4. datapoints respectively. This dataset contains 24 features, 3 of which are categorical features. We also convert the columns denoted by "PAY. to continuous values by replacing instances of -1, -2 with O. We set "MARRIAGE". "AGE", and "SEX" as immutable features. For StEP we set "EDUCATION" as an ordinal feature that can only increase.
Credit Card Default:
Give Me Some Credit: we produce randomly assigned train, validation, and test splits from the instances in the same manner with Credit Card Default. Give Me Some Credit consists of 10 features. We remove
21

---

Published in Transactions on Machine Learning Research (10/2024)
points in this dataset with missing values prior to splitting into train, validation and test sets. We set "age" immutable feature.
we produce randomly assigned train, validation, and test splits from the instances the same manner as with Credit Card Default. UCI Adult/Census Income consists 15 features, of which are categorical. We drop the "education" feature as is equivalent the "education-num" feature. For StEP we set "education-num" as feature that can only increase when giving recourse. We set the following features immutable features: "age", "marital-status" "relationship", "race", "sex", "native-couutry".
UCI Adult/ Adult/Census Census Income:
C.2 Base Model Details
Each method relies on base machine learning model; in experiments, we sci-kit learn's implementation of logistic regression and random forest replicating practitioners' preferences for simpler and more explainable models. To evaluate more complex models, we use the PyTTrrh library implement a non-linear neural network model with two hidden layers of 16 and 32 neurons. We use simple holdout set validation to determine the hyperparameters used, outlined C.4.
C.3 StEP Parameters Discussion
We use the simple rotation invariant f2-norm as our distance metric. To ensure the distance function not biased towards any feature, we normalize continuons feature values with respect to their mean and standard deviation (Mothilal et al. (2020b) follow similar methodology). More formally, for a continuous feature i, we transform its value follows:
Choosing a Distance Metric:
x = 0i (x) 14)
where is the mean value of the feature and is the standard deviation.
Choosing the function We propose two different a functions - the volcano function" and the sloped function. The volcano function weighs nearby points higher than faraway points, but all points closer than a specific threshold are weighed equally (a similar function is used by Patel et al. (2022)). We denote this function by ag and define it as follows:
1
2>7
a.
gd
25
dd
The sloped function is shaped like a normal distribution curve with a mean. We denote this function by Os and define as follows
( 2
a=(2; = exp
Both of these functions are continuous and upper bounded. If divide the output of these functions by (the input to the functions), the output will satisfy the conditions of Theorem 3.4, i.e. the StEP algorithm can be made differentially private with slightly modified version of these functions.
In our experiments, we use the volcano function og with and = 0.5.
C.4 Other Hyperparameter Selection
We perform a basic grid search across base models, recourse methods, and datasets using sci-kit learn's GridSearchCV function. To determine appropriate byperparameters to use across the base ML models and recourse methods, we roughly optimize for reasonably high success rate and to minimize distance.
named for shape when drawn whiteboard.
22

---

Published in Transactions on Machine Learning Research (10/2024)
For each base ML model, we sweep over confidence cutoff between {0.50, 0.55, 0.60, 0.65, 0.7} and evaluate the performance of each recourse method. We find that 0.7 provides reasonable results across datasets, base models, and recourse methods while remaining a reasonable value practitioner may use. We vary E [1,2,3 3, 4, 4, the number paths to produce for cach PoI (and for StEP, the number of clusters to produce), and fix k 3 for our comparative analysis and user-interference experiments.
For StEP, we consider step sizes in {0.10, 0.25, 0.50, 0.75, 1.00} and fix value of across all experiments. FACE has two main hyperparametens: graph type in (A-NN, KDE) and distance threshold (a float). In B.4, provide substantial discussion the distance threshold parameter. For all our experiments using FACE, we used the graph following suggestion from the authors of the method. For C-CHVAE we set the step distance hyperparameter to 1. We detail this hyperparameter in B.1. For all applicable recourse methods, we allow maximum of 50 iterations to produce l counterfactua((s).
C.5 Computational Resources Used
We used two machines for our empirical evaluation, including for base model training (i.e. logistic regression, random forest, neural network), for recourse experiments, and post-processing of results to produce metrics. These machines contain:
8 CPU cores, 64GB RAM, NVIDIA 4070 GPU, and 2TB local SSD disk memory.
16 CPU cores 64GB RAM, NVIDIA 4080S GPU, and 4TB local SSD disk memory.
23


Reviews:
[{"review_id": "h4iF9Yh7ZM", "reviewer": "Reviewer_buBt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strenghts**\n- The paper presents a straightforward method for generating recourses, which contributes to its ease of implementation and understanding. The method is principled in the sense that it follows from a set of axioms the authors propose.\n\n- The notion of direction-based recourse is original, and seems interesting given its simplicity. \n\n**Weaknesses**\n- The paper does not (empirically) study changes to fundamentally important hyperparameters on recourse accuracy and recourse costs. In particular, an analysis is missing which studies the sensitivity of recourse accuracy and recourse costs as the underlying clustering method is changed or the number of clusters $k$ is varied.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a data-driven method called StEP for computing recourses. For a specific user, StEP first divides the input dataset into clusters and identifies a 'direction' in the user’s feature space for each cluster. Users can enhance their features by following the suggested direction. StEP iteratively provides new directions based on the user's actions until the desired classification is achieved. These suggested directions are data-driven, can be made to have minimal dependence on the underlying model through adding privacy preserving noise to the input directions, and fulfill certain desirable properties for offering a recourse.\n\n\nThe paper does a good job at presenting a straightforward, model-agnostic algorithm for generating recourse, evaluated across multiple datasets and three popular model classes. However, there are areas for improvement, such as the limited evaluation of the robustness of generated recourse when noise is added to achieve privacy and when different clustering methods are used. Overall, the paper offers a solid foundation for future research in distance-based algorithmic recourse, though further enhancements would increase its comprehensiveness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- [**Required**]: Analysing the impact of clustering methods on recourse accuracy: Since the recourse direction is highly dependent on the clustering algorithm, it would be helpful to see how different clustering methods impact the probability to obtain a recourse.\n- [**Required**]: Analysing the impact of cluster size on recourse accuracy: Given a fixed clustering method, how do different values of the minimum cluster size impact the probability of obtaining a recourse? This experiment would help readers understand the sensitvity of the method to hyperparameters. \n- [**Suggested addition**] *DP Motivation*: The work by [1] is a missing reference that seems highly relevant to this work. [1] has first shown that privacy concerns are relevant to recourse problems, and weaving this observation into this work would strengthen the motivation behind considering DP in recourse problems.\n- [**Optional**] *Analysing the impact of DP on recourse costs*: Does there exist a tradeoff between recourse costs and making recourse DP? I would imagine that the worst case recourse costs might increase due to additional noise being added to the recourse directions. \n\n\n[1] Pawelczyk et al (2023), \"On the Privacy Risks of Algorithmic Recourse\", AISTATS, https://arxiv.org/abs/2211.05427", "broader_impact_concerns": "I do not have concerns regarding the work's broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GH8sWiwNGC", "reviewer": "Reviewer_1UEM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and well-organized. It is possible to understand mostly all the details and assumptions made, and also the proposed method is straightforward. The method is also well-framed in the literature and it provides a novel interpretation of the algorithmic recourse problem. I also praise the addition of examples (e.g., Figures 1, 2 and 3) that help motivate the approach and give an immediate gist of the idea. The experiments are well-executed and back up almost all claims made by the authors. \n\nI have some comments mainly on the justification of some theoretical assumptions, the potential societal impacts of StEP and the efficacy of StEP under certain conditions.   \n\nIn Section 2, the author argues that their approach “[...] offloads some computation costs onto the stakeholder” since they provide only directions rather than full-fledged recourse options. The authors also argue that “Even if the resulting change does not facilitate a change in outcome [...] we can still offer additional directions until a desirable outcome is obtained”. It seems to me that there are two issues here:\n- The burden of implementing recourse is all on the user side. StEP can only offer instructions such as “raise your income”, without specifying how much. Basically, the users do not know the $c$ value in $f(x + c\\cdot d)$. Thus, it might be suboptimal from a user standpoint since the stakeholders lack the full specifications.\n- How many interactions with StEP will the user have before obtaining the desired classification? For example, a user could have a hard time following StEP directions (e.g., because the clustering is poor), thus increasing a lot the interactions.\n\nI would suggest the author add a “Limitations” or a “Broader Impact” statement considering the potential effect on the application of StEP in real-world scenarios\n\nIn Section 1.1, the phrase “StEP is the _only method_ [...] which satisfies a set of _natural properties_” overstates the contribution. I believe the authors do not adequately justify why the properties proposed in Section 3.1 should be considered natural for explanations. What is _natural_ in the first place? Section 3.1 describes properties from a mathematical point of view, which is somewhat justified by citing previous research. However, since the ultimate goal of this work is to provide useful explanations for the user, I do not see how those mathematical properties match properties considered _realistic_ by a human.\n\nIn Section 2.1, the authors state that DiCE can recommend “impossible” actions (e.g., paying a negative amount of money) to obtain recourse. Following the latest DiCE implementation [1], it is possible to specify actionability constraints, which would in principle avoid this situation. Since the authors state in Section 4.1 that StEP encodes constraints in the same way as DiCE does, I wonder if the proposed approach suffers from the same issue, or if the authors picked a specific example where the competitor fails. \n\nAlgorithm 1 described the StEP method, but the authors do not discuss its computation complexity and/or potential pitfalls of running it for large datasets $\\mathcal{X}$. I would expect that, since we consider only positive points, in practice the complexity would be linear on the size of $\\mathcal{X}$. However, other issues might arise. For example, the similar method FACE tends to be very memory-consuming (if we use an adjacency matrix to build the graph we get $O(|\\mathcal{X}|^2)$ space complexity), thus it is usually run with a reduced dataset $\\hat{\\mathcal{X}} \\subset \\mathcal{X}$.\n\nSection 3.2 provides some intuitions if StEP is run without clustering. However, I believe that cluster quality is an important assumption and a prerequisite for StEP to work in practice. I would have liked to see an ablation experiment testing empirically this assumption, even on synthetic data (e.g., more practically, it is easy to create synthetic tasks with varying clustering difficulty, for example, by using utils such as make_classification in scikit-learn [2]). \n\nSection 3.3 provides results for a privacy-preserving StEP method in the case it is run without clustering. Since as Section 3.2 points out, there are pitfalls in running StEP with no clustered $\\mathcal{X}$, I wonder what is the significance of these results, since in practice we would expect to use the clustered StEP anyway. \n\nHere below are some additional minor nitpicking comments:\n- In Section 2, why do you need that the counterfactual explanation $\\mathbf{x} \\notin \\mathcal{X}$? In principle, any instance $\\mathbf{x} \\in \\mathcal{X}$ where $h(\\mathbf{x}) = +1$ would constitute a good recourse suggestion.\n- Section 3.1 feels like you are providing some properties which are conveniently satisfied by your solution a-posteriori, instead of the other way around. I would suggest having Section 3.1 before Equation 1.\n- Table 2 and Table 3 are not very readable. I would suggest the authors highlight the desired property (e.g., StEP provides more diverse/closer solutions) to help match what is written in Section 4.2 with the Tables.\n- Table 2 and Table 3 results might be improved by showing the standard error/standard deviation for each entry. Reporting the max error does not tell us if the results are statistically significant. For example, StEP might provide closer solutions, but if the std is enormous, then StEP might be worse than other competitors. \n\n\n[1] https://interpret.ml/DiCE/readme.html\n\n[2]  https://scikit-learn.org/stable/modules/generated/sklearn.datasets.make_classification.html#sklearn.datasets.make_classification", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents StEP, a new model-agnostic and data-driven method to find counterfactual explanations for algorithmic recourse. StEP provides a set of “directions” instead of proper counterfactuals, to gradually steer the user towards a high-density area of the data manifold achieving the desired classification outcome. The authors show how StEP satisfies some theoretical properties that ensure good explanations. The authors also show how StEP (without clustering) is privacy-preserving. Lastly, the paper presents an experimental section where the efficacy of StEP is compared with other competitors in terms of accuracy, diversity and closeness using real-world datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Could the authors add a “Broader Impact”/“Limitation” statement highlighting the potential societal pitfalls of their approach and/or limitations?\n- Could the authors rephrase or better justify the naturalness assumption of the properties in Section 3.1?\n- Can the authors comment on the computational complexity of Algorithm 1 and/or on its execution with limited data $\\mathcal{X}$?\n- What if the clustering used by StEP is not precise? Can the authors provide some theoretical/experimental results on this (e.g., by considering how StEP recourse success varies compared with some clustering evaluation metrics such as silhouette score/mutual information)? \n- Can the author comment on the privacy-preserving properties of StEP (with clustering) in Section 3.3?", "broader_impact_concerns": "Please see the \"Requested changes\" section above.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZobJMisSa5", "reviewer": "Reviewer_aKSn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Well-organized presentation.\n2. Extensive experimental evaluation.\n\nWeaknesses:\n1. The idea of the stepwise explainable paths and the corresponding proofs are straightfoward. In other word, the contribution of the paper is limited.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper designes a direction-based algorithm for producing counterfactual explanations, named StEP. It is shown that the directions computed by StEP uniquely satisfy a set of desirable properties, as well as differentially privacy under some mild assumptions. Empirical evaluation is demonstrated to show its performance comparing with baselines, and show its robustness to user-interference.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "NA", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is very readable; the contribution is well motivated, overall sensible and sufficiently well supported by empirical evidence. Two reviewers out of three are in favor of accepting the manuscript.  The remaining reviewer is more negative, but I find their opinion is chiefly motivated by issues that do not necessarily align with TMLR's objectives.

This being said, I strongly encourage the authors to implement all clarifications requested by the reviewers for the camera ready.
Decision: Accept (poster)