# Vertex-based Networks to Accelerate Path Planning Algorithms

###### Abstract

Path planning plays a crucial role in various autonomy applications, and RRT*
is one of the leading solutions in this field. In this paper, we propose the
utilization of vertex-based networks to enhance the sampling process of RRT*,
leading to more efficient path planning.

Our approach focuses on critical vertices along the optimal paths, which
provide essential yet sparser abstractions of the paths. We employ focal loss
to address the associated data imbalance issue, and explore different masking
configurations to determine practical tradeoffs in system performance. Through
experiments conducted on randomly generated floor maps, our solutions
demonstrate significant speed improvements, achieving over a 400% enhancement
compared to the baseline model.

Index Terms—  Path Planning, RRT*, Vertex, FCN

##  1 Introduction

Path planning aims to determine a feasible route for an autonomous agent to
travel from a starting point to a target location within an environment while
avoiding obstacles. This process has a wide range of applications across
various domains. The common goal of path planning is to discover a route that
is safe, efficient, and smooth.

Traditional path planning algorithms can be grouped into two primary
categories: grid search-based and sampling-based. Among grid-search
algorithms, the A* algorithm [1] is one of the most prominent solutions,
capable of guaranteeing the finding of an optimal path if one exists; however,
it may encounter difficulties in high-dimensional state spaces. Sampling-based
algorithms, such as Rapid Random-exploring Trees (RRT) [2] and Optimal Rapid
Random-exploring Trees (RRT*) [3], operate through randomly selecting states
from the state space, rather than investigating all possible states, therefore
speeding up the exploration process. RRT uniformly sample states within the
state space while gradually building a tree structure of these states. RRT*
enhances RRT by reorganizing the tree, granting it probabilistic completeness
and asymptotic optimality.

Recently, machine learning-based approaches have been proposed to address the
intricate challenges associated with path planning. These approaches can
generally be categorized into supervised learning (SL) and reinforcement
learning (RL) methods. SL-based solutions perform perception and decision-
making simultaneously, predicting control policies directly from raw input
images [4]. RL-based methods, on the other hand, rely on human-designed reward
functions, allowing learning agents to explore policies through trial and
error [5]. While promising, learning-based path planning solutions often lack
theoretical guarantees on performance. Moreover, SL requires annotated data,
which can be difficult or expensive to acquire.

The latest RRT-based solutions, including informed RRT* [6] and connect RRT
[7], while using traditional strategies, are regarded as the state-of-the-art
solutions in the field. This can be attributed to their flexibility in
handling changes in the environment and their capability of to navigate high-
dimensional state spaces. Moreover, RRT* has the guarantee of asymptotic
optimality and probabilistic completeness, which ensures that the solution
achieves optimality under specific conditions.

However, RRT* solutions suffer sensitivity to the initial solution and slow
convergence to the optimal solution. To overcome these limitations, several
network-based solutions have been proposed to speech up the sampling process.
Trained on optimal paths, Neural RRT* [8] and Motion Planning Networks [9]
predict the probability distribution of the path to achieving faster
samplings. Neural Informed RRT* [10] guides RRT* tree expansion using an
offline-trained neural network during online planning.

Although considerable speed-ups have been demonstrated in comparison to the
original RRT* algorithm, the aforementioned acceleration networks commonly
take the entire A* search space as the target area and estimate probabilities
based on the proximity to optimal paths. Moreover, they may struggle with
highly dynamic environments or those with rapidly changing obstacles, as the
planning may become quickly outdated.

In this paper, we propose to enhance the speed-up of the sampling process by
shifting the target areas from the neighborhood of optimal paths to that of
vertices (corners or turning points). Our design is based on the rationale
that critical vertex points in the optimal paths provide an insightful and
adequate abstraction of the paths, while requiring much less space. Focusing
on vertices, however, results in a side effect that the training data would be
highly imbalanced. We address this issue using focal loss [11] in this work.
We also explore different thresholding setups for the network outputs to
examine the system tradeoffs in performance.

##  2 Background

Rapidly-Exploring Random Trees (RRTs) comprise a family of path planning
algorithms that depend on incremental sampling. The RRT algorithm [2] starts
with a single-vertex tree that represents the initial state and has no edges.
Over each iteration, the algorithm generates a state $x_{\textrm{rand}}$ from
a uniform sampling of the search space and tries to link it to the nearest
vertex $x_{\textrm{nearest}}$ in the tree. If this linkage is feasible, the
Steering function manipulates $x_{\textrm{rand}}$ to produce
$x_{\textrm{new}}$. The new state $x_{\textrm{new}}$ and new edge
$(x_{\textrm{nearest}},x_{\textrm{new}})$ are then added to the growing tree.

The RRT* algorithm [3] introduces two additional procedures: ${\rm
Extend}(G,x_{\rm new})$ function and the ${\rm Rewire}(G)$ process. During the
${\rm Extend}$ procedure, RRT* searches for optimal parent vertices around
$x_{\textrm{new}}$ within a certain radius. After integrating
$x_{\textrm{new}}$ into the tree, RRT* rewires neighbor vertices to assess
whether a path through $x_{\textrm{new}}$ can provide a lower cost than the
current path. The procedure of the RRT* algorithm is illustrated in Algorithm
1. $\textrm{ObstacleFree}(x_{\textrm{nearest}},x_{\textrm{new}})$ function
determines if the line segment connecting $x_{\textrm{nearest}}$ and
$x_{\textrm{new}}$ is obstacle-free. RRT* is asymptotically optimal, which
means that as the sampling iterations approach infinity, the path converges to
the optimal path.

Input: $x_{\rm init},x_{\rm goal},Map$

Output: $G=(V,E)$

1$V\leftarrow\\{x_{\rm init}\\};E\leftarrow\emptyset$ ;

2 for  _$i=1,\cdots,n$_ do

3 $x_{\rm rand}\leftarrow$ UniformSample() ;

4 $x_{\rm nearest}\leftarrow$ Nearest($G=(V,E),x_{\rm rand})$ ;

5 $x_{\rm new}\leftarrow$ Steer($x_{\rm nearest},x_{\rm rand})$ ;

6 if  _ ${\rm ObstacleFree}(x_{\rm nearest},x_{\rm new})$ _ then

7 Extend($G,x_{\rm new}$) ;

8 Rewire($G$) ;

9

10

11return _$G=(V,E)$_ ;

12

Algorithm 1 RRT*

The Neural RRT* algorithm [8] trains a CNN model on successful path planning
cases to generate a nonuniform sampling distribution. For a given task, the
trained network can predict the probability distribution of the optimal path
for on the map, which can guide and speed up the sampling process.

##  3 Method

In this work, we propose a method to improve the Neural RRT* category by
redirecting the sampling guidance from the neighborhoods of optimal paths to
key vertices. To achieve this, we train a neural network called VertexNet, and
subsequently integrate it with the RRT* algorithm.

###  3.1 VertexNet

Our VertexNet is designed to predict the likelihood of each pixel being a
vertex on the optimal path, which we refer to as vertex-ness. We approach this
task as an image mapping problem and address it using a fully convolutional
network, as depicted in Fig. 1. The input to VertexNet consists of an RGB
image representing a floor map, where obstacles, source, and target points are
differentiated by distinct colors. The ground-truth is a corresponding vertex
map extracted from the A* optimal path. The output of VertexNet is a vertex-
ness map, which will subsequently be integrated into the RRT* algorithm to
guide the sampling process.

Fig. 1: Illustration of the proposed VertexNet. Best view on screen.

VertexNet is modified from the U-Net [12], primarily by adopting ResNet34, a
residual network [13] as the backbone for the encoder. This modification aims
to enhance the network’s ability to capture important features from the input
images and facilitate effective training. The updated encoder consists of
basic blocks as described in [13], each of which contains two 2-dimensional
convolutional layers, two batch normalization layers, and one Rectified Linear
Unit (ReLU) activation. In total, our network has 54 weighted layers and
41,221,168 parameters, among which, 19,953,520 are trainable. The network
takes floor map images of size $200\times 200$ as inputs.

####  3.1.1 Ground Truth and Training Objective

The ground-truth images in our work are generated following a three-step
process. In the first step, we employ the A* algorithm to determine the
optimal path for a floor map. Next, we extract a number of vertex points on
the optimal path based their vertex-ness (being corners or turning points).
Finally, we create the ground-truth images by setting the pixels of the
selected vertices to 0s, while the remaining pixels are set to 1s.

Vertices are chosen among the pixels on the path based on specific criteria.
Specifically, only the end-points of line segments are considered as vertices,
while intermediate points are excluded. Since the paths are generated within
discrete image domains, the identification of straight lines becomes crucial.
Straight lines can consist of line segments with consistent directions, as in
Fig. 2(a). The red dash-lines in Fig. 2(b) could also be straight under a
continuous domain, as their directions are not changed. Fig. 2(c) shows a
similar case where we look ahead for three steps. It should be noted that the
points $x_{i}$ in all three cases should not be classified as turning points.

(a) 0-degree and 90-degree lines.

(b) 45-degree straight lines.

(c) 22.5-degree straight lines.

Fig. 2: Three cases of straight lines within the pixel domain.

Let $X_{\textrm{path}}=\\{x_{0},x_{1},\cdots,x_{T}\\}$ be a path going through
a sequence of positions within an image domain. To determine whether a point
$x\in X_{\textrm{path}}$ should be considered as a turning point, we examine
if there is a change in direction for any of the three step sizes in Fig. 2.
In essence, we define a vertex as follows:

$\displaystyle X_{\textrm{vertex}}=\\{x\in X_{\textrm{path}}\mid$
$\displaystyle\Delta(x_{i}-x_{i-1})\land\Delta(x_{i}-x_{i-2})$
$\displaystyle\land\Delta(x_{i}-x_{i-3})\\}$

where $\Delta$ denotes the presence of a change in direction with a certain
step size.

####  3.1.2 Loss Function

As very few pixels in each ground-truth image are selected as vertices, the
ground-truth images tend to be predominately blank as vast majority (over 99%)
of the pixels have intensity of 1s. This intensity imbalance would create a
challenge for image mapping problems. To tackle this issue, we adopt the focal
loss [11] as the objective function for our VertexNet.

${\rm FL}(p_{\rm t})=-(1-p_{\rm t})^{\gamma}\log(p_{\rm t})$

Compared to the cross-entropy loss, the focal loss adds a modulating factor
$(1-p_{\rm t})^{\gamma}$. This factor assigns varying weights to samples based
on their difficulty of classification. Easy samples, which are more likely to
be correctly classified, receive reduced weights, while harder samples are
assigned higher weights. In our dataset, as the non-vertex pixels constitute
the majority, they are categorized as easy samples, resulting in reduced
contributions through the modulating factor. The focusing hyperparameter
$\gamma$ is adjustable, and based on empirical observations, we set it to $2$
in our experiments.

###  3.2 VertexNet RRT*

After VertexNet is trained, it is integrated into the RRT* algorithm to
enhance the sampling process. The integration process follows a similar design
to that of Neural RRT* [8]. Taking a floor map as the input, the non-uniform
sampler generated by VertexNet works together with the uniform sampler from
RRT* to make informed sampling decisions. VertexNet plays a crucial role by
providing probabilistic guidance for selecting the next sampling point, thus
improving the overall sampling efficiency. Meanwhile, the uniform sampler
ensures that the integrated algorithm retains its original properties of
probabilistic completeness and asymptotic optimality.

The resulting algorithm is referred to as VertexNet RRT*, as outlined in
Algorithm 2. Each sampler is assigned a $50\%$ probability of being invoked,
which is determined by the Rand() function. The Nearest function, Extend,
Rewire and Steer function are all the same as in the original RRT* algorithm.

Input: $x_{\rm init},x_{\rm goal},Map,{\rm VetexNet}$

Output: $G=(V,E)$

1$\mathcal{O}={\rm VertexNet}(Map,x_{\rm init},x_{\rm goal})$ ;

2 $V\leftarrow\\{x_{\rm init}\\};E\leftarrow\emptyset$ ;

3 for  _$i=1,\cdots,n$_ do

4 if  _${\rm Rand}() >0.5$_ then

5 $x_{\rm rand}\leftarrow$ VertexNetSample($\mathcal{O}$) ;

6

7 else

8 $x_{\rm rand}\leftarrow$ UniformSample() ;

9

10 $x_{\rm nearest}\leftarrow$ Nearest($G=(V,E),x_{\rm rand})$ ;

11 $x_{\rm new}\leftarrow$ Steer($x_{\rm nearest},x_{\rm rand})$ ;

12 if  _ ${\rm ObstacleFree}(x_{\rm nearest},x_{\rm new})$ _ then

13 Extend($G,x_{\rm new}$) ;

14 Rewire($G$) ;

15

16

17return _$G=(V,E)$_ ;

Algorithm 2 VertexNet RRT*

####  3.2.1 Masked VertexNet RRT*

To explore different configurations, we develop a masked version of the
VertexNet RRT* algorithm. In this variant, a mask is applied to the sampling
probability distribution generated by VertexNet. The mask functions by setting
probabilities below a specific threshold value, denoted as $\tau$, to zero. In
the original VertexNet RRT* algorithm, even pixels with low probabilities have
a chance of being chosen as vertex points. However, with the applied mask,
probabilities below the threshold value are disregarded, leading a higher
likelihood of sampling actual vertex points.

##  4 Experiments

Data We generated a total of 10,000 maps for our experiments. Each map
consists of 12 randomly chosen start points and 12 randomly chosen goal
points, resulting in a dataset of 1,440,000 maps in total. Fig. 3 shows five
maps with different levels of complexity. In our experiments, $70\%$ of the
maps were used for training, and $30\%$ for testing.

To ensure the simulation of diverse map scenarios, our map generator randomly
selects a variable number of obstacles, including shapes like triangles,
circles, squares, bars, and U-shaped obstacles. The orientation of each
obstacle is also chosen randomly. Each map has a dimension of 200x200 pixels,
and integer values are assigned to each pixel based on their respective
classes. Traversable space is denoted by 0, obstacles are represented by 1,
start points are labeled as 2, and goal points are labeled as 3.

(a) Map 1

(b) Map 2

(c) Map 3

(d) Map 4

(e) Map 5

Fig. 3: Five floor maps with different complexities. In each map, green star
denotes the start state and the red cross is the destination.

###  4.1 Sampling Probability Comparisons

The key design of our VertexNet RRT* lies in the modification of the training
objective to focus on the turning points of the optimal paths. This
modification is aimed to reduce the sampling space required for the RRT*
algorithm. By comparing the resulting probability distribution predictions
from models trained with distribution predictions from models trained with the
vertex-based objective versus the path-based objective, we can assess the
effectiveness of our approach.

Fig. 4 illustrates a representative example, where the optimal path and the
extracted vertices are displayed in Fig. 4(a) and (b), respectively. Fig. 4(c)
shows the probability distributions trained using the optimal paths in Neural
RRT*, while Fig. 4(d) show the probability distributions trained using our
VertexNet. As evident, the latter has much fewer bright areas, indicating that
the sampling space of VertexNet RRT* is greatly reduced compared to the Neural
RRT*.

(a) Optimal path

(b) Vertices in optimal path

(c) Neural RRT*

(d) VertexNet RRT*

Fig. 4: Sampling distributions of Neural RRT* and VertexNet RRT*. Dark area
depicts high probabilities, light area shows low probabilities. (a) Blue line
is the optimal path. (b) Blue dots are the vertices in the optimal path. (c)
Sampling probability distribution from Neural RRT*. (d) Sampling distribution
from our VertexNet RRT*.

###  4.2 Path Planning Results and Analysis

We performed experiments on four different algorithms, namely RRT*, Neural
RRT*, our VertexNet RRT* and Masked VertexNet RRT*. We use the abbreviations
RRT*, NRRT*, VNRRT* and M-VNRRT* in the upcoming presentation. The evaluations
were conducted for both initial solutions, where each algorithm terminates
upon reaching the destination, and optimal solutions, where each algorithm
terminates after finding the optimal path.

We conducted experiments to find initial solutions on the five individual maps
in Fig. 3, as well as 1,000 random maps selected from the test set. Each
individual map underwent 1,000 trials for each algorithm to find an initial
solution. The results for the random maps were averaged across the 1,000 maps.
The performance of the algorithms was evaluated based on Path Length and Time
Cost, as summarized in Table 1 and Table 2. Among the models, our VNRRT*
algorithm demonstrated the fastest performance in finding the initial solution
in the Random Maps settings, as indicated in Table 2. Moreover, the path
length achieved by VNRRT* was comparable to that of the baseline Neural RRT*.

Table 1: Path Length comparisons of the initial solutions

| Map 1 | Map 2 | Map 3 | Map 4 | Map 5 | Random Maps
---|---|---|---|---|---|---
RRT* | 250.93$\pm$46.98 | 322.02$\pm$24.06 | 284.38$\pm$19.93 | 222.33$\pm$26.05 | 373.03$\pm$28.89 | 153.07$\pm$83.77
NRRT* | 214.49$\pm$47.46 | 316.9$\pm$26.02 | 282.62$\pm$18.39 | 210.23$\pm$18.8 | 364.38$\pm$30.6 | 142.71$\pm$80.65
VNRRT* | 215.85$\pm$47.96 | 312.17$\pm$23.2 | 283.94$\pm$18.57 | 212.53$\pm$19.55 | 361.57$\pm$30.98 | 145.75$\pm$81.38
M-VNRRT* $\tau$=0.5 | 164.18$\pm$35.44 | 304.33$\pm$23.00 | 293.17$\pm$21.17 | 205.7$\pm$17.52 | 351.48$\pm$32.01 | 134.25$\pm$79.92
M-VNRRT* $\tau$=0.9 | 154.02$\pm$24.01 | 313.67$\pm$25.77 | 296.76$\pm$22.96 | 202.30$\pm$16.42 | 344.03$\pm$29.34 | 133.98$\pm$80.73
M-VNRRT* $\tau$=0.99 | 163.62$\pm$32.51 | 302.72$\pm$23.08 | 306.46$\pm$29.52 | 198.09$\pm$18.85 | 346.61$\pm$24.52 | 136.55$\pm$82.49
Optimal | 135.14 | 255.68 | 264.71 | 190.20 | 319.58 | 119.35

  * Optimal: Optimal path length

Table 2: Time Cost of finding initial solutions

| Map 1 | Map 2 | Map 3 | Map 4 | Map 5 | Random Maps
---|---|---|---|---|---|---
RRT* | 0.19$\pm$0.20 | 0.7$\pm$0.52 | 33.42$\pm$46.82 | 6.76$\pm$13.47 | 8.06$\pm$11.09 | 1.84$\pm$14.72
NRRT* | 0.23$\pm$0.24 | 0.53$\pm$0.38 | 23.24$\pm$28.81 | 4.57$\pm$9.54 | 6.93$\pm$8.9 | 0.77$\pm$6.07
VNRRT* | 0.18$\pm$0.19 | 0.64$\pm$0.44 | 11.15$\pm$14.83 | 2.29$\pm$3.57 | 5.69$\pm$7.23 | 0.45$\pm$2.17
M-VNRRT* $\tau$=0.5 | 0.15$\pm$0.17 | 0.62$\pm$0.43 | 5.56$\pm$5.83 | 1.20$\pm$1.63 | 6.22$\pm$8.36 | 0.85$\pm$5.09
M-VNRRT* $\tau$=0.9 | 0.10$\pm$0.08 | 0.76$\pm$0.53 | 5.22$\pm$6.82 | 1.83$\pm$2.49 | 8.81$\pm$11.89 | 0.62$\pm$3.60
M-VNRRT* $\tau$=0.99 | 0.20$\pm$0.19 | 0.88$\pm$0.83 | 10.36$\pm$32.27 | 3.56$\pm$4.77 | 4.58$\pm$4.38 | 1.44$\pm$12.27

  * Time cost to find the initial solution in seconds.

Table 3: Time Cost of finding optimal solutions

| Map 1 | Map 2 | Map 3 | Map 4 | Map 5 | Random Maps
---|---|---|---|---|---|---
RRT* | 1034.98$\pm$1055.17 | 50.97$\pm$35.56 | 47.20$\pm$57.36 | 28.55$\pm$17.03 | 36.19$\pm$23.21 | 29.62$\pm$102.66
NRRT* | 36.48$\pm$37.57 | 16.45$\pm$8.27 | 35.28$\pm$30.45 | 9.62$\pm$10.92 | 19.63$\pm$14.10 | 19.38$\pm$62.62
VNRRT* | 34.57$\pm$33.43 | 17.34$\pm$8.36 | 18.24$\pm$15.00 | 5.99$\pm$3.67 | 15.09$\pm$10.51 | 10.96$\pm$62.67
M-VNRRT* $\tau$=0.5 | 2.46$\pm$2.21 | 13.41$\pm$7.39 | 16.14$\pm$9.63 | 2.88$\pm$3.12 | 16.12$\pm$12.02 | 3.71$\pm$11.58
M-VNRRT* $\tau$=0.9 | 4.86$\pm$7.95 | 19.09$\pm$12.30 | 21.97$\pm$13.28 | 2.89$\pm$2.13 | 15.37$\pm$14.86 | 18.40$\pm$96.41
M-VNRRT* $\tau$=0.99 | 29.4$\pm$65.28 | 46.14$\pm$46.16 | 36.77$\pm$40.06 | 4.95$\pm$4.48 | 19.68$\pm$26.66 | 85.40$\pm$400.62

  * Time cost to find the optimal solution in seconds.

Fig. 5: Time improvements over RRT* on finding optimal solutions. Data are
Maps 2-5 and Random Maps and the improvements are shown in percentage.

We further evaluated the performance of the algorithms in finding optimal
solutions. Due to the time-consuming nature of finding optimal solutions, we
reduced the number of experimental trials to 100\. Among the algorithms
tested, the M-VNRRT* $\tau$=0.5 algorithm consistently delivered the best
results in experiments conducted on Map 1-4 and Random Maps. On the other
hand, our VNRRT* algorithm achieved the best performance on Map 5, as
summarized in Table 3.

Fig 5 shows the speed improvements of the algorithms over RRT* on finding
optimal solutions. Our VNRRT* outperformed NRRT* in almost all the
experiments, except for Map 2, where its performance was 5% worse. However,
the M-VNRRT* demonstrated relative improvements compared to NRRT* in all
experiments, particularly in Map 3, Map 4, and Random Maps, where the
improvements were 118.59%, 234.03%, and 422.37%, respectively.

As models’ performance vary on individual maps, the Random Maps experiment
provides a more objective evaluation by averaging results of 100 maps. The
results are summarized in the rightmost column of Table 3. On average, the
proposed VNRRT* algorithm shows an acceleration of 76.82% over the baseline
NRRT* algorithm when converging to optimal paths. The M-VNRRT* with $\tau$=0.5
demonstrates an impressive improvement of 422.37% when compared to NRRT*.

In summary, our VNRRT* algorithm demonstrates a significant improvement of
over 70% compared to NRRT* when converging to both the optimal and initial
solutions. On the other hand, our M-VNRRT* $\tau$=0.5 exhibits superior
performance in finding the optimal solution, being over 400% faster than
NRRT*. However, it is 9.41% slower than NRRT* when finding initial solutions.

Our VNRRT* algorithm demonstrates superior speed in finding initial solutions
(Table 2), possibly because it does not incorporate a mask that restricts the
sampling points to optimal vertices. In contrast, the inclusion of a mask in
the M-VNRRT* algorithm imposes more constraints on the sampling probability,
therefore speed up convergence to the optimal solution. This is evident from
the performance of M-VNRRT* $\tau$=0.5 in the optimal solution experiments
(Table 3). Points with a probability prediction below 50% are less likely to
be vertex points but still have a chance of being sampled. The masking process
may have excluded these points, resulting in faster convergence to the optimal
solutions.

##  5 Conclusion

In this work, we present a novel approach to improve the learned heuristic for
path planning algorithms. Rather than using the entire optimal path line
segment as the objective, we focus solely on the turning points of the optimal
paths in our proposed VertexNet. This modification significantly enhances the
speed of the path planning algorithms. We also introduce a mask to the sampler
of VertexNet RRT*, which boosts the sampling probability of the actual
vertices in the optimal path. This further accelerates the convergence speed
to the optimal path. Overall, our approach provides a more efficient method
for learning heuristics, which is important for future machine learning
applications in path planning problems.

## References

  * [1] Peter E Hart, Nils J Nilsson, and Bertram Raphael,  “A formal basis for the heuristic determination of minimum cost paths,”  IEEE transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968.
  * [2] Steven M LaValle et al.,  “Rapidly-exploring random trees: A new tool for path planning,”  1998\.
  * [3] Sertac Karaman and Emilio Frazzoli,  “Sampling-based algorithms for optimal motion planning,”  The international journal of robotics research, vol. 30, no. 7, pp. 846–894, 2011.
  * [4] Ahmed H Qureshi, Anthony Simeonov, Mayur J Bency, and Michael C Yip,  “Motion planning networks,”  in 2019 International Conference on Robotics and Automation (ICRA). IEEE, 2019, pp. 2118–2124.
  * [5] Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel,  “Value iteration networks,”  Advances in neural information processing systems, vol. 29, 2016\.
  * [6] Jonathan D Gammell, Siddhartha S Srinivasa, and Timothy D Barfoot,  “Informed rrt*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic,”  in 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2014, pp. 2997–3004.
  * [7] Jonathan D Gammell, Siddhartha S Srinivasa, and Timothy D Barfoot,  “Batch informed trees (bit): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs,”  in 2015 IEEE international conference on robotics and automation (ICRA). IEEE, 2015, pp. 3067–3074.
  * [8] Jiankun Wang, Wenzheng Chi, Chenming Li, Chaoqun Wang, and Max Q-H Meng,  “Neural rrt*: Learning-based optimal path planning,”  IEEE Transactions on Automation Science and Engineering, vol. 17, no. 4, pp. 1748–1758, 2020.
  * [9] Tingguang Chen, Tingxiang Huang, Xiao Xu, Gilbert Laporte, and Yang Liu,  “Motion planning networks,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, pp. 8537–8546.
  * [10] Xinyu Xie and Danyang Yang,  “Neural informed rrt*: A learning-based approach to motion planning,”  in 2019 International Conference on Robotics and Automation (ICRA). IEEE, 2019, pp. 2845–2851.
  * [11] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár,  “Focal loss for dense object detection,”  in Proceedings of the IEEE international conference on computer vision, 2017, pp. 2980–2988.
  * [12] Olaf Ronneberger, Philipp Fischer, and Thomas Brox,  “U-net: Convolutional networks for biomedical image segmentation,”  in International Conference on Medical image computing and computer-assisted intervention. Springer, 2015, pp. 234–241.
  * [13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.


# Can I Still Trust You?
Understanding the Impact of Distribution Shifts on Algorithmic Recourses

Kaivalya Rawal  Ece Kamar  Himabindu Lakkaraju

###### Abstract

As predictive models are being increasingly deployed to make a variety of
consequential decisions ranging from hiring decisions to loan approvals, there
is growing emphasis on designing algorithms that can provide reliable
recourses to affected individuals. In this work, we assess the reliability of
algorithmic recourses through the lens of distribution shifts i.e., we study
if the recourses generated by state-of-the-art algorithms are robust to
distribution shifts. To the best of our knowledge, this work makes the first
attempt at addressing this critical question. We experiment with multiple
synthetic and real world datasets capturing different kinds of distribution
shifts including temporal shifts, geospatial shifts, and shifts due to data
corrections. Our results demonstrate that all the aforementioned distribution
shifts could potentially invalidate the recourses generated by state-of-the-
art algorithms. Our theoretical results establish a lower bound on the
probability of recourse invalidation due to distribution shifts, and show the
existence of a tradeoff between this invalidation probability and typical
notions of “cost” minimized by modern recourse generation algorithms. Our
findings not only expose fundamental flaws in recourse finding strategies but
also pave new way for rethinking the design and development of recourse
generation algorithms.

Machine Learning, ICML

##  1 Introduction

Over the past decade, machine learning (ML) models are being increasingly
deployed in diverse applications across a variety of domains ranging from
finance and recruitment to criminal justice and healthcare. Consequently,
there is growing emphasis on designing tools and techniques which can explain
the decisions of these models to the affected individuals and provide a means
for _recourse_ (Voigt & Von dem Bussche, ). For example, when an individual is
denied loan by a credit scoring model, he/she should be informed about the
reasons for this decision and what can be done to reverse it. Several
approaches in recent literature tackled the problem of providing recourses to
affected individuals by generating _local_ (instance level) counterfactual
explanations. For instance, (Wachter et al., 2018) proposed a model-agnostic,
gradient based approach to find a closest modification (counterfactual) to any
data point which can result in the desired prediction. (Ustun et al., 2019)
proposed an efficient integer programming approach to obtain _actionable_
recourses for linear classifiers.

While prior research on algorithmic recourses has mostly focused on providing
counterfactual explanations (recourses) for affected individuals, it has left
a critical problem unaddressed. It is not only important to provide recourses
to affected individuals but to also ensure that they are robust and reliable.
It is absolutely critical to ensure that once a recourse is issued, the
corresponding decision making entity is able to honor that recourse and
approve any reapplication that fully implements all the recommendations
outlined in the prescribed recourse (Wachter et al., 2018). If the decision
making entity cannot keep its promise of honoring the prescribed recourses
(i.e., recourses become invalid), not only would the lives of the affected
individuals be adversely impacted, but the decision making entity would also
lose its credibility.

One of the key reasons for recourses to become invalid in real world settings
is the fact that several decision making entities (e.g., banks and financial
institutions) periodically retrain and update their models and/or use online
learning frameworks to continually adapt to new patterns in the data.
Furthermore, the data used to train these models is often subject to different
kinds of distribution shifts (e.g, temporal shifts) (Rabanser et al., 2019).
Despite the aforementioned critical challenges, there is little to no research
that systematically evaluates the reliability of recourses and assesses if the
recourses generated by state-of-the-art algorithms are robust to distribution
shifts. While there has been some recent research that sheds light on the
spuriousness of the recourses generated by state-of-the-art counterfactual
explanation techniques and advocates for approaches grounded in causality
(Barocas et al., 2020; Karimi et al., 2020b, a), these works do not explicitly
consider the challenges posed by distribution shifts.

In this work, we study if the recourses generated by state-of-the-art
counterfactual explanation techniques are robust to distribution shifts. To
the best of our knowledge, this paper makes the first attempt to understand
and quantify the impact of data distribution shifts on the validity of
algorithmic recourses. We theoretically analyze under what conditions do
recourses are get invalidated. We prove that there is a tradeoff between
recourse cost and the potential chance of invalidation due to model updates,
and find a non-zero lower bound on the probability of invalidation of
recourses due to distribution shifts. These key findings motivate our
experiments identifying recourse invalidation in real world datasets.

We consider various classes of distribution shifts in our experimental
analysis, namely: temporal shifts, geospatial shifts, and shifts due to data
corrections. We deliberately select datasets from disparate domains such as
criminal justice, education, and credit scoring, in order to stress the broad
applicability and serious practical impacts of recourse invalidation. Our
experimental results demostrate that all the aforementioned distribution
shifts could potentially invalidate the recourses generated by state-of-the-
art algorithms, including causal recourse generation algorithms. We thus
expose previously unknown problems with recourse generation that are broadly
applicable to all currently known algorithms for generating recourses. This
further emphasizes the need for rethinking the design and development of
recourse finding algorithms and counterfactual explanations as it stands
today.

##  2 Related Work

A variety of post hoc techniques have been proposed to explain complex models
(Doshi-Velez & Kim, 2017; Ribeiro et al., 2018; Koh & Liang, 2017). These may
be model-agnostic, local explanation approaches (Ribeiro et al., 2016;
Lundberg & Lee, 2017) or methods to capture feature importances (Simonyan et
al., 2013; Sundararajan et al., 2017; Selvaraju et al., 2017; Smilkov et al.,
2017). A different class of post-hoc local explainability techniques proposed
in the literature is counterfactual explanations, which can be used to provide
algorithmic recourse. Separately, there has also been research theoretically
and empirically analysing distribution shifts (Rabanser et al., 2019;
Subbaswamy et al., 2020) and adversarial perturbation attacks, and their
consequent impacts on machine learning classifier accuracies and uncertainty
(Ovadia et al., 2019), and interpretability and fairness (Thiagarajan et al.,
2020). While there has been a lot of work on distribution shifts and on
recourses individually, these have remained largely separate pursuits and we
wish to fill this gap in the literature by studying the behaviour of
algorithmic recourses under distribution shifts.

A counterfactual explanation helps users understand the local model decision
boundary by providing example points $\mathcal{S^{\prime}}$ classified as
positive ($+1$) by a binary black-box classifier $\mathcal{M}$, given a sample
data-point $\mathcal{S}$ that has been classified as negative ($-1$). Thus,
for a user $\mathcal{S}$ adversely classified by a model $\mathcal{M}$ as
belonging to class $-1$, the feature vector represented by
$\mathcal{S^{\prime}}$ can be provided as recourse (Pawelczyk et al., 2020b)
to change the prediction to $+1$. All recourse generation methods essentially
perform a search starting from a given data point $\mathcal{S}$, going towards
$\mathcal{S^{\prime}}$, by repeatedly polling the input-space of the black box
model $\mathcal{M}$ along the path
$\mathcal{S}\rightarrow\cdots\mathcal{S"}\cdots\rightarrow\mathcal{S^{\prime}}$.

There are many ways in which to guide this path when searching for
counterfactual explanations. Techniques have been developed for tree based
ensembles (Tolomei et al., 2017; Lucic et al., 2019), using feature-importance
measures (Rathi, 2019), perturbations in latent spaces defined via
autoencoders (Pawelczyk et al., 2020a; Joshi et al., 2019), SAT solvers
(Karimi et al., 2019), genetic algorithms (Sharma et al., 2020; Schleich et
al., 2021), determinantal point processes (Mothilal et al., 2020), and the
growing spheres method (Laugel et al., 2018), among others. Two methods are
particularly noteworthy for their generic formulations, enabling their
application in diverse contexts. (Wachter et al., 2018) first proposed
counterfactual explanations, using gradients to directly optimize the L1 or L2
normed distance between $\mathcal{S}$ and $\mathcal{S^{\prime}}$. (Ustun et
al., 2019) used integer programming tools to minimize the log absolute
difference between $\mathcal{S}$ and $\mathcal{S^{\prime}}$, but only consider
those feature values for $\mathcal{S^{\prime}}$ that already exist in the
data. This is one way of ensuring that the recourses generated are
“actionable”.

In our analysis we broadly adopt the classification taxonomy proposed by
(Pawelczyk et al., 2020b); which classifies recourse generation techniques
into two types: those that promote greater sparsity (sparse counterfactuals)
(Wachter et al., 2018; Laugel et al., 2018; Looveren & Klaise, 2019; Poyiadzi
et al., 2020; Tolomei et al., 2017)), and those that promote greater support
from the given data distribution (data support counterfactuals) (Ustun et al.,
2019; Looveren & Klaise, 2019; Pawelczyk et al., 2020a; Joshi et al., 2019;
Poyiadzi et al., 2020)). For a given set of counterfactual explanations
$\mathcal{S^{\prime}}:\mathcal{S^{\prime}}\in\mathcal{M}(\mathcal{S^{\prime}})=+1$
and arbitrary cost function $d(\mathcal{S},\mathcal{S^{\prime}})$ (usually set
to
$d(\mathcal{S},\mathcal{S^{\prime}})=||\mathcal{S}-\mathcal{S^{\prime}}||_{p}$,
$p\in\\{1,2\\}$) these correspond to counterfactual explanations defined as
$\arg\min_{\mathcal{S^{\prime}}}\,{d(\mathcal{S},\mathcal{S^{\prime}})}$ and
$\arg\min_{\mathcal{S^{\prime}}:P_{data}(\mathcal{S^{\prime}})>0}\,{d(\mathcal{S},\mathcal{S^{\prime}})}$
respectively. We can further qualify additional recourse generation techniques
that use a causal notion of data support probabilities to form an important
subcategory termed (Causal Counterfactuals) (Karimi et al., 2020b, a). There
is a known _upper_ bound on recourse cost under predictive multiplicity
(Pawelczyk et al., 2020b). However, none of the works referenced above
explicitly focus on analyzing if the recourses generated by state-of-the-art
algorithms are robust to distribution shifts.

##  3 Theoretical Analysis

We consider a standardized setup to compare distribution shifts in different
scenarios. This is designed to be similar to real-world machine learning
deployments, where models deployed in production are often updated by
retraining periodically on new data. Our experimental setup to analyze and
examine distribution shifts consists of 6 steps:

  1. 1.

Draw a sample of data $\mathcal{D}1$ from the real world.

  2. 2.

Train a binary classification model $\mathcal{M}_{1}$ on data $\mathcal{D}1$.

  3. 3.

Use a counterfactual explanation based recourse finding algorithm to generate
recourses $\mathcal{CF}_{1}$. Recourses are found for users that are adversely
classified as $-1$ by model $\mathcal{M}_{1}$.

  4. 4.

Draw a new sample of the data $\mathcal{D}2$, that could suffer from potential
distribution shifts that have occured naturally.

  5. 5.

Train a new binary classification model $\mathcal{M}_{2}$ on data
$\mathcal{D}2$, using the exact same model class and hyperparameter settings
as before.

  6. 6.

Verify the predictions of model $\mathcal{M}_{2}$ on the recourses
$\mathcal{CF}_{1}$. By definition, the prediction of $\mathcal{M}_{1}$ on
these points is always $+1$, and we wish to verify that $\mathcal{M}_{2}$
produces the same predictions. However, if this turns out not to be the case
recourses would become invalidated.

The notation and steps above are summarised in figure 1.

Figure 1: Problem setup denoting $\mathcal{D}_{1}$, $\mathcal{M}_{1}$,
$\mathcal{CF}_{1}$, $\mathcal{D}_{2}$, and $\mathcal{M}_{2}$.

Not changing the training setup between models $\mathcal{M}_{1}$ and
$\mathcal{M}_{2}$ allows us to ensure the differences in the models are
entirely due to shifts in the data distribution, and not caused by
hyperparameter variations or changes in the training procedures. Further, the
fraction of $\mathcal{CF}_{1}$ predicted as $-1$ by $\mathcal{M}_{2}$ in step
6 above represents the “invalidation” of recourses that we report and wish to
empirically and theoretically analyze in this paper. We refer to this
phenomenon as “recourse invalidation”, and quantify the fraction using the
terms “invalidation probability” and “invalidation percentage”.

We can now establish the main theoretical results of this paper. We wish to
show:

  * •

Cost definitions for sparse recourses are such that there exists a tradeoff
between the costs and the invalidation percentages of recourses. Thus, to
reduce the chances of invalidation upon updating the model, decision makers
need to deliberately produce higher cost recourses than necessary.

  * •

There exists a model agnostic, non-zero lower bound on the probability of
invalidation of recourses produced by sparse counterfactual based recourse
generation algorithms. Thus, decision makers can never guarantee that the
recourses they provide are completely invulnerable to distribution shifts.

###  3.1 The Cost vs Invalidation Trade-off

To show that there is a trade-off between cost and invalidation percentage, we
need to determine that recourses with lower costs are at high risk of
invalidation, and vice-versa. Our analysis considers sparse counterfactual
style recourses (Pawelczyk et al., 2020a), presuming cost to be represented by
the common Euclidean notion of distance. Our notation is illustrated in figure
2 below, defining $x$ as the data point, and $x^{\prime}_{1}$ and
$x^{\prime}_{2}$ as two potential recourses. We consider the model
$\mathcal{M}_{2}$ to be defined as a perturbation of model $\mathcal{M}_{1}$
by some arbitrary magnitude $\delta_{m}$. Distances (measured according to the
generic cost metric $d$) are measured along the vectors $x\rightarrow
x^{\prime}_{1}$ and $x\rightarrow x^{\prime}_{2}$: $q_{1}$ and $q_{2}$ from
$x$ to $\mathcal{M}_{1}$, and $l_{1}$ and $l_{2}$ from $\mathcal{M}_{1}$ to
$x^{\prime}_{1}$ and $x^{\prime}_{2}$ respectively. We similarly have
$q^{\prime}_{1}$ and $q^{\prime}_{2}$ from $x$ to $\mathcal{M}_{2}$, and
$l^{\prime}_{1}$ and $l^{\prime}_{2}$ from $\mathcal{M}_{2}$ to
$x^{\prime}_{1}$ and $x^{\prime}_{2}$ respectively. The cost function with L2
norm is very common in sparse counterfactuals, defined as
$d(x,x^{\prime})=||x-x^{\prime}||_{2}$(Wachter et al., 2018). Lastly, we
denote the probability of invalidation for an arbitrary recourse $x^{\prime}$
under model $\mathcal{M}_{2}$ as
$Q_{x^{\prime}}=\frac{1-\mathcal{M}_{2}(x^{\prime})}{2}$. Note that by the
definition of recourse, $\mathcal{M}_{1}(x^{\prime})=+1$ and
$\mathcal{M}_{2}(x^{\prime})=+1$ for valid recourses but
$\mathcal{M}_{2}(x^{\prime})=-1$ for invalid recourses.

Figure 2: Abstract Diagramatic Representation of $\mathcal{M}_{1}$ and
$\mathcal{M}_{2}$, with a data point $\mathcal{S}$ represented by feature-
vector $x$ and two potential feature vectors $x^{\prime}_{1}$ and
$x^{\prime}_{2}$ denoting possible recourse $\mathcal{S^{\prime}}$.

######  Theorem 3.1.

If we have recourses $x^{\prime}_{1}$ and $x^{\prime}_{2}$ for a data point
$x$ and model $\mathcal{M}_{1}$, such that $d(x,x^{\prime}_{1})\leq
d(x,x^{\prime}_{1})$ then the respective expected probabilities of
invalidation under model $\mathcal{M}_{2}$,
$Q_{\mathbb{E}\left[x^{\prime}_{1}\right]}$ and
$Q_{\mathbb{E}\left[x^{\prime}_{2}\right]}$, follow
$Q_{\mathbb{E}\left[x^{\prime}_{1}\right]}\geq
Q_{\mathbb{E}\left[x^{\prime}_{2}\right]}$.

###### Proof (Sketch).

We know from our construction that $d(x,x^{\prime}_{1})=q_{1}+l_{1}$ and
$d(x,x^{\prime}_{2})=q_{2}+l_{2}$, and also that
$l^{\prime}_{1}=l_{1}\pm\delta_{m}$ and $l^{\prime}_{2}=l_{2}\pm\delta_{m}$.
We assume that the small random perturbation $\delta_{m}$ between
$\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ has expected value
$\mathbb{E}[\delta_{m}]=0$. Further, we also assume that both $q_{1}$ and
$q_{2}$ are random variables drawn from the same unknown distribution, with
some arbitrary expected value
$\bar{q}=\mathbb{E}\left[q_{1}\right]=\mathbb{E}\left[q_{2}\right]$.

$\displaystyle d(x,x^{\prime}_{1})$ $\displaystyle\leq d(x,x^{\prime}_{2})$
(1) $\displaystyle q_{1}+l_{1}$ $\displaystyle\leq q_{2}+l_{2}$ (2)
$\displaystyle\mathbb{E}\left[q_{1}+l_{1}\right]$
$\displaystyle\leq\mathbb{E}\left[q_{2}+l_{2}\right]$ (3)
$\displaystyle\mathbb{E}\left[q_{1}\right]+\mathbb{E}\left[l_{1}\right]$
$\displaystyle\leq\mathbb{E}\left[q_{2}\right]+\mathbb{E}\left[l_{2}\right]$
(4) $\displaystyle\bar{q}+\mathbb{E}\left[l_{1}\right]$
$\displaystyle\leq\bar{q}+\mathbb{E}\left[l_{2}\right]$ (5)
$\displaystyle\mathbb{E}\left[l_{1}\right]$
$\displaystyle\leq\mathbb{E}\left[l_{2}\right]$ (6)
$\displaystyle\mathbb{E}\left[l_{1}\right]\pm 0$
$\displaystyle\leq\mathbb{E}\left[l_{2}\right]\pm 0$ (7)
$\displaystyle\mathbb{E}\left[l_{1}\right]\pm\mathbb{E}\left[\delta_{m}\right]$
$\displaystyle\leq\mathbb{E}\left[l_{2}\right]\pm\mathbb{E}\left[\delta_{m}\right]$
(8) $\displaystyle\mathbb{E}\left[l_{1}\pm\delta_{m}\right]$
$\displaystyle\leq\mathbb{E}\left[l_{2}\pm\delta_{m}\right]$ (9)
$\displaystyle\mathbb{E}\left[l^{\prime}_{1}\right]$
$\displaystyle\leq\mathbb{E}\left[l^{\prime}_{2}\right]$ (10)

To capture the notion that models are less confident in their predictions on
points close to their decision boundaries, we construct a function
$g(l^{\prime})=P\left[\mathcal{M}_{2}(x^{\prime})=+1\right]$, using the
bijective relationship between $x^{\prime}$ and $l^{\prime}$. Therefore, $g$
is a monotonically increasing function, with $g(l^{\prime})=-Q_{x^{\prime}}$.

We now equate the probability of invalidation $Q$ to an arbitrary function
$g(l^{\prime})$. The bijection between $x^{\prime}$ and $l^{\prime}$ allows us
to define $g(l^{\prime})=-Q(x^{\prime})$ as a monotonic increasing function,
with $g(-\infty)=0$, $g(-\delta_{m})<=0.5$, $g(\delta_{m})>=0.5$, and
$g(\infty)=1$. Lastly, we can now apply this monotonic increasing function and
continue our derivation as follows:

$\displaystyle g(\mathbb{E}\left[l^{\prime}_{1}\right])$ $\displaystyle\leq
g(\mathbb{E}\left[l^{\prime}_{2}\right])$ $\displaystyle-
Q_{\mathbb{E}\left[x^{\prime}_{1}\right]}$ $\displaystyle\leq-
Q_{\mathbb{E}\left[x^{\prime}_{2}\right]}$ $\displaystyle
Q_{\mathbb{E}\left[x^{\prime}_{1}\right]}$ $\displaystyle\geq
Q_{\mathbb{E}\left[x^{\prime}_{2}\right]}$

which gives us the intended result. ∎

######  Proposition 3.2.

The above theorem implies there is a tradeoff between recourse costs with
respect to model $\mathcal{M}_{1}$ and recourse invalidation percentages with
respect to the updated model $\mathcal{M}_{2}$.

###### Proof (Sketch).

The proof for theorem 3.1 above shows two things: (1) from the $L.H.S$ we see
that cheaper costs $d(x,x^{\prime}_{1})$ imply higher invalidation chances
$Q_{\mathbb{E}\left[x^{\prime}_{1}\right]}$, and also (2) from the $R.H.S$ we
see that more expensive costs $d(x,x^{\prime}_{2})$ imply lower invalidation
chances $Q_{\mathbb{E}\left[x^{\prime}_{2}\right]}$. We can also take
contrapositives of these first two statements, giving us the third and fourth
statement:

  1. 1.

cheaper costs $\implies$ higher invalidation

  2. 2.

more expensive costs $\implies$ lower invalidation

  3. 3.

lower invalidation $\implies$ more expensive costs

  4. 4.

higher invalidation $\implies$ cheaper costs

Taken together, these statements complete our proof and show that an increase
or decrease in recourse cost must necessarily be accompanied by a decrease or
increase in the probability of invalidation respectively, and vice versa.
Therefore, we can say that there exists a tradeoff between recourse costs and
invalidation probabilities. ∎

These results establish that recourses that have lower costs are more likely
to get invalidated by the updated model $\mathcal{M}_{2}$. This is a critical
result that demonstrates a fundamental flaw in the design of state-of-the-art
recourse finding algorithms since the objective formulations in these
algorithms explicitly try to minimize these costs. By doing so, these
algorithms are essentially generating recourses that are more likely to be
invalidated upon model updation.

###  3.2 Lower Bounds on Recourse Invalidation Probabilities

In order to find general lower bounds on the probability of invalidation for
recourses $\mathcal{CF}_{1}$ under $\mathcal{M}_{2}$, we first cast the
couunterfactual search procedure as a Markov Decision Process, and then use
this observation to hypothesize about the distributions of the recourses
$\mathcal{CF}_{1}$. We then use these distributions to derive the lower bounds
on the invalidation probability.

######  Proposition 3.3.

The search process employed by state-of-the-art counterfactual explanation
based recourse generation algorithms (Wachter et al., 2018) is a Markov
Decision Process.

###### Proof (Sketch).

We know that the search for counterfactual explanations consists of solving
the optimization problem given by
$\arg\min_{\mathcal{S^{\prime}}}{d(\mathcal{S^{\prime}},\mathcal{S})}$, where
sparse counterfactuals are _unrestricted_ , and data support counterfactuals
are _restricted_ to the set
${\mathcal{S^{\prime}}:P_{data}(\mathcal{S^{\prime}})>0}$. The search
procedure moves through the path
$\mathcal{S}\rightarrow\cdots\mathcal{S"}\cdots\rightarrow\mathcal{S^{\prime}}$,
looping through different possible values of $\mathcal{S"}$ until
$\mathcal{M}_{1}(\mathcal{S"})=+1$ and cost $d(\mathcal{S},\mathcal{S"})$ is
minimized - at which point the recourse $\mathcal{S^{\prime}}=\mathcal{S"}$ is
returned. For sparse counterfactuals, each step in this search depends only on
the previous iteration, and not on the entire search path so far, that is:
$P(\mathcal{S"}_{t+1}|\mathcal{S"}_{t},\mathcal{S"}_{t-1}\dots\mathcal{S})=\mathcal{S"}_{t+1}|\mathcal{S"}_{t}$.
Thus, by satisfying this condition, the recourse generation technique is a
Markov Decision Process. ∎

######  Lemma 3.4.

If the model $\mathcal{M}_{1}$ is linear, then the above proposition implies
that the distribution of recourses $\mathcal{CF}_{1}$ is either exponential or
geometric, along the normal to the classifier hyperplane, for continuous or
categorical data respectively.

###### Proof (Sketch).

By Proposition 3.3 above, we know that the recourse search process follows the
Markov Property, and thus the distribution of the recourses must have the
memoryless property. Further, since the classifier is linear, we know that an
_unrestricted_ recourse search, such as that of sparse counterfactual based
recourses, will proceed exactly along the normal to the classifier hyperplane,
in the direction of increasingly positive $\mathcal{M}_{1}$ classification
probabilities. Lastly, we assume that the probability of the counterfactual
explanation search ending at any given iteration $t$ with
$\mathcal{S^{\prime}}=\mathcal{S"}_{t}$ is always constant $\rho$. Thus, for
continuous data, the distribution of recourses is exponential with
$\lambda=\rho$, and for ordinal data the distribution is geometric with
parameter $p=\rho$. ∎

Figure 3: Parallel model perturbation of arbitrary magnitude $\delta_{m}$
between linear models $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$. The range of
the data is represented by manifold $\Psi$.

######  Theorem 3.5.

For a given linear model $\mathcal{M}_{1}$ with recourses $\mathcal{CF}_{1}$,
and a parallel linear model $\mathcal{M}_{2}$ with known constant perturbation
$\delta_{m}$, we can find the exact invalidation probabilities as a function
of the distribution of the recourses $\mathcal{CF}_{1}$.

###### Proof (Sketch).

Let the recourses be distributed according to some unknown arbitrary
distribution with density $f(l)$, where $l\in(0,\infty)$ is the normal
distance between $\mathcal{M}_{1}$ and $\mathcal{S^{\prime}}$. Then, as is
clear from the invalid region between the models $\mathcal{M}_{1}$ and
$\mathcal{M}_{2}$ illustrated in figure 3, the probability of invalidation of
the recourses $\mathcal{S^{\prime}}$ is
$Q_{\mathcal{S^{\prime}}}=\frac{1}{\Psi}\int_{\Psi}\left[\int_{0}^{\delta_{m}}f(l)\,dl\right]\,d\psi$.
Here $\psi$ is an arbitrary element of the decision boundary, within the data
manifold $\Psi$.

We can now combine this result with known distributions from Lemma 3.4 to get:

$\displaystyle Q_{\mathcal{S^{\prime}}}$
$\displaystyle=\frac{1}{\Psi}\int_{\Psi}\left[\int_{0}^{\delta_{m}}f(l)\,dl\right]\,d\psi$
(11) $\displaystyle=\frac{1}{\Psi}\int_{\Psi}\left[\int_{0}^{\delta_{m}}\rho
e^{-\rho l}\,dl\right]\,d\psi$ (12)
$\displaystyle=\frac{1}{\Psi}\int_{\Psi}\left[1-e^{-\rho\delta_{m}}\right]\,d\psi$
(13)
$\displaystyle=\frac{1}{\Psi}\int_{\Psi}\,d\psi\cdot\left[1-e^{-\rho\delta_{m}}\right]$
(14) $\displaystyle=1-e^{-\rho\delta_{m}}$ (15)

Similarly, for ordinal data this would be
$Q_{\mathcal{S^{\prime}}}=\frac{1}{\Psi}\int_{\Psi}\left[\sum_{l=1}^{\delta_{m}}(1-\rho)^{l-1}\cdot\rho\right]\,d\psi=1-(1-\rho)^{\delta_{m}}$.
Thus, we have characterised the exact invalidation probabilities for parallel
linear models $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$, with known distance
$\delta_{m}$. ∎

We now tend to the case of classifiers with non-linear decision boundaries.

######  Theorem 3.6.

For a given nonlinear model $\mathcal{M}_{1}$ with recourses
$\mathcal{CF}_{1}$, and a parallel nonlinear model $\mathcal{M}_{2}$ with
known constant perturbation $\delta_{m}$, the lower bound on the invalidation
probabilities is achieved exactly when both models $\mathcal{M}_{1}$ and
$\mathcal{M}_{2}$ are linear.

###### Proof (Sketch).

We consider a piecewise linear approximation of the nonlinear models, with an
arbitrary degree of precision. At each point in the classifier decsion
boundary, we consider the piecewise linear approximation to make an angle
$\theta$ with a hypothetical hyperplane in the data manifold $\Psi$. We then
proceed identically as in the proof for theorem 3.5 above, with
$Q_{\mathcal{S^{\prime}}}=\frac{1}{\Psi\cos\theta}\int_{\Psi}\left[\int_{0}^{\delta_{m}}f(l)\,dl\right]\,d\psi$,
where the extra $\cos\theta$ term reflects that the models are locally
inclined at an angle $\theta$ from the hyperplane $\psi$.

It is easy to see that $Q_{\mathcal{S^{\prime}}}$ will be maximized when
$\theta=0,\forall\theta$, because
$\frac{dQ_{\mathcal{S^{\prime}}}}{d\theta}\propto\tan\theta=0\implies\theta=0$.
If each element of the piecewise linear approximation makes a constant angle
of $0$ with the models, then the models themselves must be linear. Thus, the
lower bound on invalidation probability for non-linear models must exactly be
the invalidation probability for linear models, given the same data
(manifold). ∎

Combining the last two results, for any arbitrary model $\mathcal{M}_{1}$, we
know that another model $\mathcal{M}_{2}$ perturbed parallelly with magnitude
would cause invalidation with the following lower bounds:
$Q_{\mathcal{S^{\prime}}}\geq 1-e^{-\rho\delta_{m}}$, for continuous data and
$Q_{\mathcal{S^{\prime}}}\geq 1-(1-\rho)^{\delta_{m}}$ for ordinal data.

##  4 Experimental Analysis

The main focus of our paper is to show that in real-world use cases, recourses
generated by modern state-of-the-art recourse generation algorithms are not
trustworthy and can be invalidated by model updation due to naturally
occurring distribution shifts. We investigate three different real world
distribution shifts: temporal data drifts, geospatial data drifts, and
reported data correction related distribution shifts. We select these datasets
from three disparate domains of criminal justice, education, and credit-
lending to show the broad real world impact of our findings.

We generate recourses using two popular state-of-the-art algorithms - sparse
recourse based counterfactual explanations (hencefore CFE), proposed by
(Wachter et al., 2018); and data support based actionable recourse (henceforth
AR), proposed by (Ustun et al., 2019), details of which are included in
section 2. To adapt CFE to non-differentiable models we use numeric
differentiation and approximate gradients, and to adapt AR to non-linear
models we use a local linear model approximation using LIME (Ribeiro et al.,
2016). We find significant recourse invalidation with either algorithm, and
also show that using causal recourse generation algorithms, although proposed
as a solution to many other problems with recourse invalidation (Karimi et
al., 2020a; Venkatasubramanian & Alfano, 2020; Barocas et al., 2020), does not
solve this particular issue of invalidation due to data drifts. We will be
releasing the code used to produce these results, including hyperparameter
settings, as open-source via GitHub.

###  4.1 Temporal Shifts

To examine the effects of temporal data distribution shifts on recourse
validity we perform experiments in the domain of criminal justice. We have
access to two datasets, collected in 1978 ($\mathcal{D}_{1}$) and 1980
($\mathcal{D}_{2}$) respectively (Lakkaraju et al., 2016). These datasets
contain demographic features such as race, sex, age, time-served, and
employment, and a target attribute corresponding to bail decisions. We reserve
10% of both $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ just for validation, to
perform sanity checks on our model $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$
accuracies. We then follow the experimental setup described in figure 1, for
various model types: Logistic Regression (LR), Random Forests (RF), Gradient
Boosted Trees (XGB), Linear Support Vector Machines (SVM), a small Neural
Network with hidden layers = [10, 10, 5] (DNN (s)), and a larger Neural
Network with hidden layers = [20, 10, 10, 10, 5] (DNN (l)). The models are all
treated as binary classification black-boxes used to predict whether or not a
person would be granted bail. For those people that are denied bails
$\mathcal{M}_{1}(\mathcal{D}_{1})=-1$, we provide counterfactual explanation
based recourses $\mathcal{CF}_{1}$ and test whether these bails are granted
bail by the updated prediction model $\mathcal{M}2$. Our results are
summarised in table 1 below.

Algorithm | Model | M1 acc | M2 acc | CF1 Size | Invalidation %
---|---|---|---|---|---
AR | LR | 94 | 95.4 | 5592 | 96.6
RF | 99 | 99.5 | 4435 | 0.05
XGB | 100 | 99.7 | 1459 | 0
SVM | 81 | 78.9 | 6108 | 3.05
DNN (s) | 99 | 99.4 | 1521 | 19.26
DNN (l) | 99 | 99.6 | 1817 | 0
CFE | LR | 94 | 95.4 | 5601 | 98.29
RF | 99 | 99.5 | 5196 | 0.71
XGB | 100 | 99.7 | 5187 | 0.46
SVM | 81 | 78.9 | 6108 | 100
DNN (s) | 99 | 99.4 | 4955 | 91.38
DNN (l) | 99 | 99.6 | 763 | 0.13
Table 1: Temporal Distribution Shifts: Recourse invalidation in
$\mathcal{CF}_{1}$ by model $\mathcal{M}_{2}$, due to temporal data drift.
$\mathcal{D}_{1}$ had 8395 total points, with 5203 in class $-1$, and
$\mathcal{D}_{2}$ had 8595 total points, with 5430 in class $-1$. The model
accuracies are reported as 10-fold cross validation accuracy percentages, and
$\mathcal{CF}_{1}$ Size represents the number of points for which recourses
exist.

###  4.2 Geospatial Shifts

Next, we replicate our process above to study the impact of geospatial data
distribution shifts on recourse validity. We consider a problem of predicting
grades, modelled as a binary classification between pass ($+1$) and fail
($-1$), using input predictors such as grade, nationality, holidays-taken, and
class-participation. Our dataset consists of schools spread out across Jordan
and Kuwait. We presume that the decision maker initially trained a model using
data $\mathcal{D}_{1}$ collected in Jordan. When this model is deployed,
students at risk of failing are provided with recourses to improve their
predicted grades. Eventually, we postulate that the decision maker trains a
new model $\mathcal{M}_{2}$ on more relevant data $\mathcal{D}_{2}$ collected
in Kuwait. We would ideally want the grade improvement recommendation
recourses already made to continue to remain valid for every student. We use
the same settings for models and recourse generation methods as before, and
our results are presented below in table 2. Note that for some models, AR was
not able to generate any valid recourses ($\mathcal{CF}_{1}$ has size $0$),
and consequently the invalidation percentage is reported NAN.

Recourse | Model | M1 acc | M2 acc | CF1 | Invalidation %
---|---|---|---|---|---
AR | LR | 88 | 93 | 47 | 76.6
RF | 89 | 92 | 0 | NAN
XGB | 85 | 93 | 0 | NAN
SVM | 80 | 91 | 40 | 90
DNN (s) | 83 | 87 | 0 | NAN
DNN (l) | 82 | 93 | 0 | NAN
CFE | LR | 88 | 93 | 47 | 65.96
RF | 89 | 92 | 17 | 76.47
XGB | 85 | 93 | 14 | 57.14
SVM | 80 | 91 | 54 | 100
DNN (s) | 83 | 87 | 2 | 50
DNN (l) | 82 | 93 | 33 | 30.3
Table 2: Geospatial Distribution Shifts: Recourse invalidation in
$\mathcal{CF}_{1}$ by model $\mathcal{M}_{2}$, due to geospatial data drift.
$\mathcal{D}_{1}$ had 129 total points, with 46 in class $-1$, and
$\mathcal{D}_{2}$ had 122 total points, with 27 in class $-1$. The model
accuracies are reported as 10-fold cross validation accuracy percentages, and
$\mathcal{CF}_{1}$ Size represents the number of points for which recourses
exist.

###  4.3 Dataset Correction Related Shifts

Data collection in the real world often suffers from selection bias. These
typically take some time to identify, and correcting the dataset bias can be
necessary to make models fairer and more interpretable, even if there is no
change in accuracy. In addition to selection bias, real world datasets are
often messy and require significant preprocessing before being used to build
machine learning models. One such dataset is the German credit dataset (Dua &
Graff, 2017), commonly used to build and evaluate credit worthiness models.
Here we wish to predict whether or not a given customer should be considered
credit worthy using features such as their credit history, loan amount,
employment history, and age as predictors. The first release (and English
translation) of this dataset, however, contains multiple errors. A corrected
dataset also exists, which can be thought of as the same data with minor
changes to revert previous mistakes (Grömping, ). Thus, to model data
correction based distribution shifts, we train an initial binary
classification model $\mathcal{M}_{1}$ on the first release of the German
credit data, $\mathcal{D}_{1}$, and we consider $\mathcal{M}_{2}$ to be a
model trained on the recently corrected dataset $\mathcal{D}_{2}$. The rest of
our setup is unchanged from before, and results from this experiment can be
seen in table 3. Again, here we see models for which no recourses could be
found, and we report the invalidation percentage for these cases to be NAN.

###  4.4 Causal Recourse Generation

There have been a multitude of recent works showing the inadequacies of non-
causal recourses (Karimi et al., 2020b; Barocas et al., 2020;
Venkatasubramanian & Alfano, 2020). Even though not specific to distribution
shifts, these works posit that causal recourse generation is more robust than
sparse counterfactual explanation based recourse generation. In general, it is
hard to generate causal recourses because of lack of access to a generative
causal model of the data. For the German credit dataset described in section
4.3 however, we are able to directly adopt the exact causal data distribution
from (Karimi et al., 2020a), replicating their simulation of generating causal
recourses on the German credit dataset.

Our experiments show that even with causally generated recourses, distribution
shifts can invalidate recourses. These results are included in table 3, with a
recourse generation algorithm labelled Causal, in addition to the AR and CFE
algorithm results.

Algorithm | Model | M1 acc | M2 acc | CF1 Size | Invalidation %
---|---|---|---|---|---
AR | LR | 71 | 75 | 154 | 7.79
RF | 73 | 73 | 20 | 35
XGB | 74 | 75 | 25 | 8
SVM | 63 | 69 | 1 | 100
DNN (s) | 68 | 69 | 0 | NAN
DNN (l) | 66 | 67 | 1 | 0
CFE | LR | 71 | 75 | 154 | 3.9
RF | 73 | 73 | 258 | 36.82
XGB | 74 | 75 | 253 | 23.72
SVM | 63 | 69 | 1 | 0
DNN (s) | 68 | 69 | 0 | NAN
DNN (l) | 66 | 67 | 57 | 0
Causal | LR | 69 | 71 | 61 | 0
RF | 65 | 64 | 256 | 96.09
XGB | 64 | 68 | 8 | 12.5
DNN (s) | 69 | 70 | 0 | NAN
DNN (l) | 69 | 70 | 0 | NAN
Table 3: Data Correction Distribution Shifts: Recourse invalidation in
$\mathcal{CF}_{1}$ by model $\mathcal{M}_{2}$, due data drift caused by
correcting data reporting errors. $\mathcal{D}_{1}$ had 900 total points, with
275 in class $-1$, and $\mathcal{D}_{2}$ had 900 total points, with 271 in
class $-1$. The model accuracies are reported as 10-fold cross validation
accuracy percentages, and $\mathcal{CF}_{1}$ Size represents the number of
points for which recourses exist.

###  4.5 Sensitivity Analysis

We have demonstrated empirically that distribution shifts cause recourse
invalidation. In this section we wish to demonstrate that increasing the
magnitude of distribution shifts increases recourse invalidation percentages.
To do this we construct synthetic datasets and precisely control the type of
distribution shift. We start with a fixed distribution $\mathcal{D}_{1}$,
which has two independent predictors $X0$ and $X1$, both drawn from a standard
normal distribution, with the binary target attribute defined linearly as
$Y=(X0+X1\geq 0)$. We then train a logistic regression model $\mathcal{M}_{1}$
and generate recourses $\mathcal{CF}_{1}$ from either AR or CFE. Finally, we
shift the distribution $\mathcal{D}_{2}$ according to some shift parameter
$\alpha$ and construct logistic regression model $\mathcal{M}_{2}$, and
analyse the relation between recourse invalidation percentage and $\alpha$.

Figure 4: [AR] Recourse Invalidation with Drift in Target

Figure 5: [CFE] Recourse Invalidation with Drift Target

Figure 6: [AR] Recourse Invalidation with Drift in Predictors

Figure 7: [CFE] Recourse Invalidation with Drift in Predictors

We consider the following two scenarios, with shift parameter $\alpha$
defining the shift between $\mathcal{D}_{2}$ and $\mathcal{D}_{1}$.

  1. 1.

Shifting target: where the predictor distribution ($X0$ and $X1$) stays
constant, but the $\mathcal{D}_{2}$ target attribute is defined as
$Y=(X0+\alpha X1\geq 0)$, for a % shift of $\alpha\in(-60\%,60\%)$.

  2. 2.

Shifting predictors: where the definition of the target stays constant
($Y=(X0+X1\geq 0)$), but we shift the mean of the predictor distribution in
$\mathcal{D}_{2}$ from $(X0,X1)=(0,0)$ to $(X0,X1)=(\alpha,\alpha)$.

As figures 4 through 7 demonstrate, recourse invalidation increases with
increasing distribution shift, but this is not universal. There may be some
distribution shifts that the recourses generated are robust to, and others
that result in upto 100% of generated recourses getting invalidated.
Particularly, when $\alpha$ is negative while shifting predictors (with this
particular target distribution), recourses generated are robust. In all other
cases there is significant invalidation that increases with increasing
$\alpha$. It is also noteworthy that even with data support based
counterfactual recourse AR, we do not uniformly see less invalidation, as
postulated by (Ustun et al., 2019). Sometimes the recourses generated are
indeed more robust, but they also often fail miserably with up to 100%
invalidation. This would suggest that data support counterfactual based
recourses are actually less predictable than sparse counterfactual based
recourses, while still being vulnerable to invalidation, and could thus
potentially be more risky for real world decision makers.

##  5 Conclusion

In this paper, we analyse the impact of distribution shifts on recourses
generated by state-of-the-art algorithms. We conduct multiple real world
experiments and show that distribution shifts can cause significant
invalidation of generated recourses, jeopardizing trust in decision makers.
This is contrary to the goals of a decision maker providing recourse to their
users. We show theoretically that there is a trade-off between minimising cost
and providing robust, hard-to-invalidate recourses when using sparse
counterfactual generation techniques. We also find the lower bounds on the
probability of invalidation of recourses when model updates are of known
perturbation magnitude. While our theory pertains only to sparse
counterfactual based recourses, we demonstrate experimentally that
invalidation problems due to distribution shift persist in practice not only
with data support based counterfactual recourse, but also with causally
generated recourses. Theoretical examination of recourse invalidation when
using these recourse generation methods remains as future work.

This work paves the way for several other interesting future directions too.
It would be interesting to develop novel recourse finding strategies that do
not suffer from the drawbacks of existing techniques and are robust to
distribution shifts. This could involve iteratively finding and examining
recourses as part of the model training phase, in order to ensure that
recourses with high likelihood of invalidation are never prescribed after
model deployment.

## References

  * Barocas et al. (2020) Barocas, S., Selbst, A. D., and Raghavan, M.  The hidden assumptions behind counterfactual explanations and principal reasons.  _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , Jan 2020.  doi: 10.1145/3351095.3372830.  URL http://dx.doi.org/10.1145/3351095.3372830.

  * Doshi-Velez & Kim (2017) Doshi-Velez, F. and Kim, B.  Towards a rigorous science of interpretable machine learning.  _arXiv preprint arXiv:1702.08608_ , 2017.
  * Dua & Graff (2017) Dua, D. and Graff, C.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * (4) Grömping, U.  South german credit data: Correcting a widely used data set.  In _Report 4/2019, Reports in Mathematics, Physics and Chemistry, Department II_. University of Applied Sciences, Beuth.
  * Joshi et al. (2019) Joshi, S., Koyejo, O., Vijitbenjaronk, W., Kim, B., and Ghosh, J.  Towards realistic individual recourse and actionable explanations in black-box decision making systems, 2019.
  * Karimi et al. (2019) Karimi, A.-H., Barthe, G., Balle, B., and Valera, I.  Model-agnostic counterfactual explanations for consequential decisions, 2019.
  * Karimi et al. (2020a) Karimi, A.-H., Schölkopf, B., and Valera, I.  Algorithmic recourse: from counterfactual explanations to interventions, 2020a.
  * Karimi et al. (2020b) Karimi, A.-H., von Kügelgen, J., Schölkopf, B., and Valera, I.  Algorithmic recourse under imperfect causal knowledge: a probabilistic approach, 2020b.
  * Koh & Liang (2017) Koh, P. W. and Liang, P.  Understanding black-box predictions via influence functions.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pp. 1885–1894. JMLR. org, 2017.
  * Lakkaraju et al. (2016) Lakkaraju, H., Bach, S. H., and Leskovec, J.  Interpretable decision sets: A joint framework for description and prediction.  In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_ , pp. 1675–1684, 2016.
  * Laugel et al. (2018) Laugel, T., Lesot, M.-J., Marsala, C., Renard, X., and Detyniecki, M.  Comparison-based inverse classification for interpretability in machine learning.  In Medina, J., Ojeda-Aciego, M., Verdegay, J. L., Pelta, D. A., Cabrera, I. P., Bouchon-Meunier, B., and Yager, R. R. (eds.), _Information Processing and Management of Uncertainty in Knowledge-Based Systems. Theory and Foundations_ , pp. 100–111, Cham, 2018. Springer International Publishing.  ISBN 978-3-319-91473-2.
  * Looveren & Klaise (2019) Looveren, A. V. and Klaise, J.  Interpretable counterfactual explanations guided by prototypes, 2019.
  * Lucic et al. (2019) Lucic, A., Oosterhuis, H., Haned, H., and de Rijke, M.  Actionable interpretability through optimizable counterfactual explanations for tree ensembles, 2019.
  * Lundberg & Lee (2017) Lundberg, S. M. and Lee, S.-I.  A unified approach to interpreting model predictions.  In _Advances in Neural Information Processing Systems_ , pp. 4765–4774, 2017.
  * Mothilal et al. (2020) Mothilal, R. K., Sharma, A., and Tan, C.  Explaining machine learning classifiers through diverse counterfactual explanations.  _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , Jan 2020.  doi: 10.1145/3351095.3372850.  URL http://dx.doi.org/10.1145/3351095.3372850.
  * Ovadia et al. (2019) Ovadia, Y., Fertig, E., Ren, J., Nado, Z., Sculley, D., Nowozin, S., Dillon, J. V., Lakshminarayanan, B., and Snoek, J.  Can you trust your model’s uncertainty? evaluating predictive uncertainty under dataset shift, 2019.
  * Pawelczyk et al. (2020a) Pawelczyk, M., Broelemann, K., and Kasneci, G.  Learning model-agnostic counterfactual explanations for tabular data.  _Proceedings of The Web Conference 2020_ , Apr 2020a.  doi: 10.1145/3366423.3380087.  URL http://dx.doi.org/10.1145/3366423.3380087.
  * Pawelczyk et al. (2020b) Pawelczyk, M., Broelemann, K., and Kasneci, G.  On counterfactual explanations under predictive multiplicity.  In Peters, J. and Sontag, D. (eds.), _Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)_ , volume 124 of _Proceedings of Machine Learning Research_ , pp. 809–818. PMLR, 03–06 Aug 2020b.  URL http://proceedings.mlr.press/v124/pawelczyk20a.html.
  * Poyiadzi et al. (2020) Poyiadzi, R., Sokol, K., Santos-Rodriguez, R., De Bie, T., and Flach, P.  Face: Feasible and actionable counterfactual explanations.  In _Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society_ , AIES ’20, pp. 344–350, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450371100.  doi: 10.1145/3375627.3375850.  URL https://doi.org/10.1145/3375627.3375850.
  * Rabanser et al. (2019) Rabanser, S., Günnemann, S., and Lipton, Z.  Failing loudly: An empirical study of methods for detecting dataset shift.  In _Advances in Neural Information Processing Systems_ , pp. 1396–1408, 2019.
  * Rathi (2019) Rathi, S.  Generating counterfactual and contrastive explanations using shap, 2019\.
  * Ribeiro et al. (2016) Ribeiro, M. T., Singh, S., and Guestrin, C.  ” why should i trust you?” explaining the predictions of any classifier.  In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_ , pp. 1135–1144, 2016.
  * Ribeiro et al. (2018) Ribeiro, M. T., Singh, S., and Guestrin, C.  Anchors: High-precision model-agnostic explanations.  In _Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018\.
  * Schleich et al. (2021) Schleich, M., Geng, Z., Zhang, Y., and Suciu, D.  Geco: Quality counterfactual explanations in real time, 2021.
  * Selvaraju et al. (2017) Selvaraju, R. R., Cogswell, M., Das, A., Vedantam, R., Parikh, D., and Batra, D.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In _Proceedings of the IEEE international conference on computer vision_ , pp. 618–626, 2017.
  * Sharma et al. (2020) Sharma, S., Henderson, J., and Ghosh, J.  Certifai.  _Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society_ , Feb 2020.  doi: 10.1145/3375627.3375812.  URL http://dx.doi.org/10.1145/3375627.3375812.
  * Simonyan et al. (2013) Simonyan, K., Vedaldi, A., and Zisserman, A.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  _arXiv preprint arXiv:1312.6034_ , 2013.
  * Smilkov et al. (2017) Smilkov, D., Thorat, N., Kim, B., Viégas, F., and Wattenberg, M.  Smoothgrad: removing noise by adding noise.  _arXiv preprint arXiv:1706.03825_ , 2017.
  * Subbaswamy et al. (2020) Subbaswamy, A., Adams, R., and Saria, S.  Evaluating model robustness to dataset shift, 2020.
  * Sundararajan et al. (2017) Sundararajan, M., Taly, A., and Yan, Q.  Axiomatic attribution for deep networks.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pp. 3319–3328. JMLR. org, 2017.
  * Thiagarajan et al. (2020) Thiagarajan, J. J., Narayanaswamy, V., Anirudh, R., Bremer, P.-T., and Spanias, A.  Accurate and robust feature importance estimation under distribution shifts, 2020.
  * Tolomei et al. (2017) Tolomei, G., Silvestri, F., Haines, A., and Lalmas, M.  Interpretable predictions of tree-based ensembles via actionable feature tweaking.  _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , Aug 2017.  doi: 10.1145/3097983.3098039.  URL http://dx.doi.org/10.1145/3097983.3098039.
  * Ustun et al. (2019) Ustun, B., Spangher, A., and Liu, Y.  Actionable recourse in linear classification.  _Proceedings of the Conference on Fairness, Accountability, and Transparency - FAT* ’19_ , 2019.  doi: 10.1145/3287560.3287566.  URL http://dx.doi.org/10.1145/3287560.3287566.
  * Venkatasubramanian & Alfano (2020) Venkatasubramanian, S. and Alfano, M.  The philosophical basis of algorithmic recourse.  In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , FAT* ’20, pp. 284–293, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450369367.  doi: 10.1145/3351095.3372876.  URL https://doi.org/10.1145/3351095.3372876.
  * (35) Voigt, P. and Von dem Bussche, A.  The eu general data protection regulation (gdpr).
  * Wachter et al. (2018) Wachter, S., Mittelstadt, B., and Russell, C.  Counterfactual explanations without opening the black box: automated decisions and the gdpr.  _Harvard Journal of Law and Technology_ , 31(2):841–887, 2018.