# A PSO Based Method to Generate Actionable Counterfactuals for High
Dimensional Data

Shashank Shekhar  Head - Global AI Practice
Subex Ltd,
Bengaluru, India
<EMAIL_ADDRESS>Asif Salim  Research Scientist
Subex Ltd,
Bengaluru, India
<EMAIL_ADDRESS>Vivaswan Jinturkar  Senior Data Scientist
Subex Ltd,
Bengaluru, India
<EMAIL_ADDRESS>Anirudha Nayak  Senior Data Scientist
Subex Ltd,
Bengaluru, India
<EMAIL_ADDRESS>Adesh Bansode  Senior Data Scientist
Subex Ltd,
Bengaluru, India
<EMAIL_ADDRESS>
###### Abstract

Counterfactual explanations (CFE) are methods that explain a machine learning
model by giving an alternate class prediction of a data point with some
minimal changes in its features. It helps the users to identify their data
attributes that caused an undesirable prediction like a loan or credit card
rejection. We describe an efficient, and an actionable counterfactual (CF)
generation method based on particle swarm optimization (PSO). We propose a
simple objective function for the optimization of instance-centric CF
generation problem. The PSO brings in a lot of flexibility in terms of
carrying out multi-objective optimization in large dimensions, capability for
multiple CF generation, and setting box constraints or immutability of data
attributes. An algorithm is proposed that incorporates these features and it
enables greater control over the proximity and sparsity properties over the
generated CFs. The proposed algorithm is evaluated with a set of action-
ability metrics in real-world datasets, and the results were superior compared
to that of the state-of-the-arts.

###### Index Terms:

Expainable AI (XAI), Counterfactual Explanations, Particle Swarm Optimization

##  I Introduction

The explainable artificial intelligence (XAI) is an important area considering
the wide adoption of industrial applications related to AI. This is especially
important in the context of data regulations like GDPR [1]. The commonly
adopted tools for XAI are feature attribution (FA) methods and counterfactual
explanations. The FA methods [2], [3] correspond to those techniques that
explain the model decision in terms of the input features.

But there are some sensitive applications where the users prefer to further
investigate when a model decision turns unfavourable. In these situations, the
users prefer to find the change in their input attributes for a favourable
prediction. This is equivalent to the concept of counterfactual thinking (CFT)
[4] studied by psychologists in which human beings deduce the counter effects
of an event.

Counter effects of a prediction can be critical in many data driven
applications. A typical use case is when a black box machine learning model
rejects the credit card application for a user. In this case, rather than
knowing the feature attribution values, the users prefer for an actionable
alternatives in the values of those features so that the model makes desired
prediction. So CFE can be deployed in these cases where it is required to
provide the changes to be made to the data point where its original prediction
may be changed to a desired class.

In general, CF explanations can be used to increase the trust of an automated
decision-making system. Apart from this, CFs are used in classical statistics
to make causal inference [5]. Along this direction, CFs are also used to
assess the fairness of a prediction model [6]. But this is out of scope of the
work we are proposing and hence we limit our discussion to generating changes
in attributes of a data point to change its model prediction to a desired
class. In the next section, we discuss these concepts in detail and the
significance of our proposal.

##  II Counterfactual Explanations

As per the definition provided by Molnar [7], a counterfactual explanation of
a prediction describes the smallest change to the feature values that changes
the prediction to a predefined output. It is an intuitive and user-friendly
way of understanding a black-box machine learning model. The seminal work that
introduces the importance of CFE in the case of machine learning models was
proposed by Wachter et.al [8]. The authors have listed three objectives of CFE
that helps in interpreting a model prediction.

  1. 1.

To help the user to understand why a particular decision was made by the
model.

  2. 2.

To provide the inputs to the user in the case they want to challenge the model
decision.

  3. 3.

To understand the changes to be made in the feature values so that the current
prediction can be changed to a desired one.

These are particularly useful to explain the black box machine learning model
predictions. In terms of the inner components or working principles of the
learning algorithm, it may be difficult to give an explanation in the layman
perspective. This problem is further escalated when the decision function is
non-linear and the data dimension is large. Hence to provide model
explanations for a layman, an efficient way is to show the changes in their
data point and its effect in model prediction. This can also be characterized
in multiple ways, for example, it is possible to give multiple numbers of CFE
in which each of them has a different set of feature changes and it also
possible to simulate ”what-if” sort of situations. Hence the CFE is a great
utility in the XAI landscape that interacts with the users in a simple way
without getting to know about the inner working of algorithms and it also
helps in generating trust between humans and automated decision systems. Apart
from this, it helps the data scientists to keep their proprietary model
details safe from public access.

For a robust CF generation there are several conditions to be satisfied. Some
of these conditions have inter-dependencies while others are completely
independent. Hence the underlying optimization process comes with a lot of
challenges. To understand this, first we describe the desired properties a CF
generation algorithm is expected to have - interpretable and human friendly
explanations, focusing on a small number of feature changes, avoiding
contradictions, giving the predefined prediction as close as possible, feature
values should be in the same range as the original distribution, and
capability to generate multiple CFs that are diverse. To satisfy these
properties, a CF generation technique shall ideally optimize the following
quantities.

  1. 1.

Validity \- this quantity is defined to check whether the CFs are valid or if
the class of the CF is the desired one.

  2. 2.

Proximity \- measures how close the CFs are to the data point queried.

  3. 3.

Sparsity \- this quantity refers to the number of feature changes in the CFs.

  4. 4.

Diversity \- this quantity is applicable in the case of multiple CF
generation. In this situation, if the CFs are generated by the change in same
set of features and the change in feature values are in same range, the CFs
may not be actionable in real-world.

  5. 5.

Feasibility \- checks whether the CFs belong to the same distribution as of
the dataset.

The state-of-the-art methods are proposed to optimize a combination of these
measures and they are discussed in Section III.

###  II-A Our motivation

There are two observations we found with state-of-the-arts that motivated our
research. They are discussed below.

####  II-A1 To enable a simple multi-objective optimization using PSO

The existing methods are formulated as a mutli-objective optimization problem
with terms that have trade-offs and inter-dependencies. It is difficult to
formulate the problem as a well-defined convex function optimization. Hence
for practical use cases, the state-of-the-art methods use either random
changes to the feature values or a simple search around the neighborhood of
the queried data point. For example, in the practical DiCE [9] implementation
that optimizes - validity, proximity and diversity \- the authors choose
random feature change to generate CFs [9]. Growing spheres (GS) [10] method
searches the CFs in the hyper-sphere around the data point. Similarly, other
state-of-the-arts probe into some specific property of CF generation with
certain approaches. For example, FACE [11] proposes a method in which the CFs
are ensured to follow the underlying data distribution. For this purpose, they
generate counterfactual from a ”feasible path” with respect to the query
point. The path is followed in the regions of significant density of data.

We propose that a simple optimization procedure is the most practical way for
real-world CF generation. As this problem cannot be formulated as a convex
optimization problem and there are inter-dependencies between the properties
to be optimized, a complex optimization strategy with additional procedures
may not serve the purpose. Also, in large dimensional data these complex
procedures can create computation issues. Hence we put forward a simple PSO
based optimization algorithm to generate CFs. There are many advantages in
using PSO that help in easy CF generation as listed below.

  1. 1.

Option to generate multiple CFs \- some state-of-the-art methods generate only
one CF at a time. With PSO, we can have the subset of best performing
particles to support multiple generation.

  2. 2.

Setting box constraints for the attributes \- Since PSO uses particle position
update at each iteration, we can easily incorporate the range an attribute
value can vary. This helps in enabling explicit control over proximity.

  3. 3.

Setting immutable attributes \- For actionable CFs in the real world case, the
users should have the option to set some attributes static. The PSO gives the
option to avoid updates for such attributes and it also helps in controlling
sparsity property.

  4. 4.

Handling categorical variables \- The common method of encoding of categorical
variables is through one-hot encoding. With an advanced variant of PSO, we can
have particle update that adhere to one-hot encoding. A detailed discussion is
given in Section IV-B.

####  II-A2 Analysis on high dimensional data

The state-of-the-arts are always discussed on standard datasets on account of
the convenience to interpret CFs. But those datasets are low dimensional.
Examples are COMPAS, Adult-income, German-credit and LendingClub. The studies
on CF generation on high dimensional data are scarce. Hence we choose high
dimensional datasets for our study with COMPAS included as a standard.

The PSO provides default settings to make faster optimization in terms of
runtime. This can be achieved by parallel updation of particle positions.
Hence the proposed approach based on PSO is suitable for high dimensional
data.

##  III Related Works

Following the taxonomy described by Chou et.al [12], our work is more
interested in instance centric methods. These methods are the ones that seek
CF based on feature changes to propose an instance that is close to the
queried point. They are briefly discussed below.

The seminal work on CFE is done by Wachter et.al [8]. They proposed a base
method in which CFs are generated considering only the optimization of
proximity. DiCE is a popular method proposed by Mothilal et.al [9] . They
devised a method to generate diverse CFs by formulating a mutli-objective
optimization that takes into account the properties of proximity, sparsity and
diversity. Dandl et.al [13] devised CF generation via a multi-objective
optimization that optimizes the previous three along with feasibility.
Looveren et.al [14] used the prototypes of data points using autoencoder or
class specific k-d trees. The prototypes are used in optimizing an objective
function to ensure the generated CFs are feasible. Along with this, the
proximity and sparsity components are also optimized.

Poyiadzi et.al [11] proposed a method for feasible and actionable CF
generation (FACE). Those properties are enabled by ensuring the CFs to lie in
a high density region of data points. They claim that with this feature, the
generated CFs are close to the data manifold and hence feasible. Growing
spheres proposed by Laugel et.al [10] is an intuitive search algorithm to find
a CF in the hypersphere centered around the queried data point. The CF can be
an actual data point in the dataset or a sampled point in the sphere.

The methods so far discussed are model agnostic. Apart from this, Artelt et.al
[15] proposed model-specific CF generation techniques for a collection of
algorithms such as linear models, Gaussian naive Bayes, quadratic discriminant
analysis etc.

Another class of CF generation methods are named as probabilistic methods.
They use the techniques based on probabilistic graphical models or generative
models such as variational auto-encoder. The examples are CRUDS [16], CEM
[17], CLUE [18], and REVISE [19].

##  IV Proposed Method

In this section, we describe the PSO variant that is used for our modeling,
the objective function optimized for CF generation, the evaluation metrics for
checking the efficacy of the generated counterfactuals and the CF generation
algorithm.

###  IV-A The PSO variant

We have used a mixed discrete particle swarm optimization algorithm (MD-PSO)
[20] in our experiments. The velocity updation equation in MD-PSO can be
written as follows.

$V_{i}^{t+1}=c_{0}V_{i}^{t}+c_{1}r_{1}(P_{i}-X_{i}^{t})+c_{2}r_{2}(P_{g}-X_{i}^{t})+c_{3}r_{3}\hat{V}_{i}^{t}$
(1)

Particle update equation is,

$X_{i}^{t+1}=X_{i}^{t}+V_{i}^{t+1}$ (2)

where,

  * •

$i$ denotes the particle:$i$, $t$ denotes the iteration:$t$,

  * •

$X_{i}^{t}/X_{i}^{t+1}$ denotes the particle position at iteration $t$ and
$t+1$ respectively,

  * •

$V_{i}^{t}/V_{i}^{t+1}$ denotes the velocity of the particle at iteration $t$
and $t+1$ respectively,

  * •

$P_{i}$ is the local best position of particle:$i$ till iteration $t$,

  * •

$P_{g}$ is the global best position among all particles till iteration $t$,

  * •

$c_{0}$, $c_{1}$, and $c_{2}$ are hyper-parameters that determine the
properties of inertia, exploitation, and exploration properties of the
particles,

  * •

$r_{1}$, $r_{2}$, and $r_{3}$ are real random numbers between [0, $c_{1}$],
[0, $c_{2}$], and [$c_{1}$, $c_{2}$] respectively,

  * •

$c_{3}$ is the diversity preservation coefficient proposed by the authors for
continuous variables,

  * •

The term $c_{3}r_{3}\hat{V}_{i}^{t}$ is explicitly introduced by the authors
to ensure diversity among the particles. $\hat{V}_{i}^{t}$ is characterized as
a vector with a divergence property. An example is the vector connecting the
mean of the population of particles (or its best performing subset) to the
particle of interest.The purpose of introduction of this component is to avoid
the stagnation of the particles at local minima.

###  IV-B Motivation to choose MD-PSO for CF generation

As explained in section II-A, PSO gives some default advantages that are
required for a CF generation. Adding to this, PSO provides default parallel
computing capabilities for optimization in large dimensions. Apart from giving
the options to generate multiple CFs and setting box constraints, MD-PSO
brings in two features that are critical in CF generation process as explained
below.

  1. 1.

Support for generating diverse CFs.

In an ideal PSO convergence scenario, all the particles are supposed to share
the position around a small region. Hence if we take the subset of best
performing particles in terms of minimizing the objective function, they may
be close points to each other. Hence from a CF generation perspective, the
fourth term introduced in MDPSO provides an option to enhance diversity.

The straight forward way to pick CFs from the PSO output is to choose a subset
of best performing particles. To further ensure diversity, we will do a
clustering on the particles and pick those ones from the cluster that have a
predefined support for the action-ability metrics as explained in Section
V-B2. We assume that the fourth term in MD-PSO helps in creating meaningful
clusters.

  2. 2.

Easy integration of discrete variables in the optimization process.

In analogous to the continuous variable updations in basic variant of PSO, MD-
PSO maps the discrete variables to a hypercube [20]. Similar to the variables
in continuous domain, the discrete variables are allowed to take real values
confined to the hypercube. During updation process, they are mapped to the
nearest corner of the hypercube to restore their discrete property.

In real-world scenarios, the discrete variables, for example - gender, race,
nationality, etc can turn crucial for a CF analysis. Hence it is important to
integrate these discrete variables with the continuous ones and MD-PSO
facilitates this.

###  IV-C Objective function

Inspired from [13], we use the following objective function for the CF
generation,

$l_{1}\left(f(x_{cf}),y_{cf}\right)+l_{2}\left(x_{0},x_{cf}\right)+l_{3}\left(x_{0},x_{cf}\right)$
(3)

where $x_{cf}$ is the counterfactual instance of a data point of interest
denoted by $x_{0}$, $y_{cf}$ is the desired class as against that of $x_{0}$,
and $f(.)$ is a classifier. The individual components $l_{1}$, $l_{2}$, and
$l_{3}$ are defined as follows.

$l_{1}\left(f(x_{cf}),y_{cf}\right)=\begin{cases}0&\text{if $f(x_{cf})\in
y_{cf}$}\\\
\underset{y_{cf}}{\text{inf}}|f(x_{cf})-y_{cf}|&\text{else}\end{cases}$ (4)

The function $l_{1}$ is introduced to make the prediction of CF as close as
possible to the desired prediction.

$l_{2}\left(x_{0},x_{cf}\right)=\frac{1}{p}\sum_{j=1}^{p}\delta_{G}(x_{0}^{j},x_{cf}^{j})$
(5)

where $p$ is the data dimension and $\delta_{G}$ is the Gower distance which
is defined as,

$\delta_{G}(x_{0}^{j},x_{cf}^{j})=\begin{cases}\frac{1}{R_{j}}|x_{0}^{j}-x_{cf}^{j}|&\text{if
$x_{0}^{j}$ is numeral}\\\ \textbf{1}_{x_{0}^{j}\neq x_{cf}^{j}}&\text{if
$x_{0}^{j}$ is categorical}\end{cases}$ (6)

Here $R_{j}$ is a normalizer to scale the feature values. This term ensures
that the counterfactual instance should be as close as possible to the data
point of interest as this property is crucial for its action-ability.

$l_{3}\left(x_{0},x_{cf}\right)=\|x_{0}-x_{cf}\|_{0}=\sum_{j=1}^{p}\textbf{1}_{x_{0}^{j}\neq
x_{cf}^{j}}$ (7)

where 1 denotes the instance when the sub-scripted inequality is satisfied.
The purpose of this term is to bring in minimal feature changes to generate
actionable CF. The objective function is minimized using MD-PSO to generate a
diverse set of CFs.

The mathematical form of $l_{2}$ and $l_{3}$ may look same but they serve
entirely different purposes. The CF is expected to be similar to the query
point for its action-ability and hence $l_{2}$ tries to minimize the proximity
property. On the other hand, it is also desired to keep the number of features
changes in the generated CF to be minimum with respect to the query point.
Hence adding $l_{3}$ to the objective function minimize the sparsity property
that has to be satisfied by a CF. Suppose if a CF is generated with low
sparsity but with a large number of features changes, such a case may be not
actionable in the real world. Hence we use $l_{2}$ and $l_{3}$ in the
objective function optimization to ensure optimal proximity with minimal
sparsity.

The remaining properties that has to be satisfied for faithful CF generation
are validity, diversity, and feasibility. Validity can be easily ensured as it
is a necessary requirement for a data point to be qualified as a CF. Our
proposed algorithm supports multiple CF generation by default. The diversity
property among those are ensured by adding a new term to the velocity update
of the particle in the MD-PSO as explained in Section IV-B. Among instance
centric methods, only FACE ensures feasibility while the probabilistic methods
can ensure this. But this is enabled by costly methods that involve model
training of generative algorithms. Since the scope of our study is only
limited to instance centric methods, any specific component for feasibility is
not added. However, we propose that the MD-PSO objective formulation along
with the control over proximity and sparsity (as explained in Section II-A)
ensures CF generations that are feasible.

###  IV-D Quality evaluation of conterfactuals

The counterfactuals need to be evaluated to check if it is effective. Towards
this direction, there are multiple quality checks that can be done in terms of
their validity, proximity, sparsity, and diversity. These measures are also
closely related to the individual terms we are trying to optimize in the
objective function given by (3).

It has to be noted that there are no standardized way to evaluate the CFs in
the research community and hence we use these metrics inspired from Mothilal
et.al [9]. The quality evaluation metrics used in our study are explained as
follows.

  1. 1.

Proximity: This quantity measures how close the generated CFs are to the data
point of interest. For the real-world users, it is important to get the CFs
that are close to their original data instance. The measure is defined
separately for continuous and categorical variable as follows.

$\text{proximity}_{cont}:=\frac{1}{k}\sum_{i=1}^{k}d_{cont}(x_{cf}^{i},x_{0})$
(8)

where $d_{cont}$ is defined as,

$d_{cont}(x_{cf},x_{0})=\frac{1}{n_{cont}}\sum_{j=1}^{n_{cont}}\frac{\left|x_{cf}^{[j]}-x_{0}^{[j]}\right|}{MAD_{j}}$
(9)

Here, $k$ denotes number of CFs generated, superscript $[j]$ denotes the
$j^{th}$ component of $x_{cf}$ and $x_{0}$, $n_{cont}$ denotes the number of
continuous variables and $MAD_{j}$ stands for the median absolute deviation of
the $j^{th}$ component.

The proximity measure for categorical variables can be defined as,

$\text{proximity}_{cat}:=\frac{1}{k}\sum_{i=1}^{k}d_{cat}(x_{cf}^{i},x_{0})$
(10)

where $d_{cat}$ is defined as,

$d_{cat}(x_{cf},x_{0})=\frac{1}{n_{cat}}\sum_{j=1}^{n_{cat}}\textbf{1}(x_{cf}^{[j]}\neq
x_{0}^{[j]})$ (11)

and $n_{cat}$ denotes the number of categorical variables. The optimal CF
generation requires this metric to be low.

Note that (8) and (10) can be used in the place of $l_{2}$ in the PSO
objective function given in (3). However, $l_{2}$ is used as it is
computationally efficient.

  2. 2.

Sparsity: measures the number of attributes that are changed with respect to
$x_{0}$. For actionable CFs, the users expect minimal action and hence minimal
changes to the number of features. The measure is defined as follows,

$\text{sparsity}:=\frac{1}{p}\sum_{i=1}^{p}d_{spa}(x_{cf}^{i},x_{0})$ (12)

where $d_{spa}$ is defined as,

$d_{spa}(x_{cf},x_{0})=\frac{1}{p}\sum_{j=1}^{p}\textbf{1}(x_{cf}^{[j]}\neq
x_{0}^{[j]})$ (13)

where $p$ is the total number of features or attributes. This quantity is
expected to be low for actionable CFs.

  3. 3.

Normalized Diversity: as the name suggests it is a measure to check how
different the generated CFs are compared to each other. For actionable CFs, we
need to generate the ones that would not contradict with each other and at the
same time keeps the close proximity to the data point of interest. Here the
contradiction means that two CFs should not have opposite feature
attributions, that is, they shall not recommend a feature to be increased and
decreased for the same query point. They shall also focus on minimal changes
to the features and at the same time shall be diverse enough to give the users
multiple options for their actions. These is a requirement with trade-offs and
considering this we define the metric diversity as a distance metric between
each pair of CF examples as shown in (14).

$\text{diversity}:=\frac{1}{kC2}\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}d(x_{cf}^{i},x_{cf}^{j})$
(14)

where we assume $k$ number of CFs are generated, $x_{cf}^{i}$ denotes the
$i^{th}$ CF and $d()$ is a distance metric that can be defined separately for
continuous (as in (9)) and categorical variables (as in (11)).

The expected range of this term for actionable CFs is relative in nature. A
low value indicates that CFs are similar to each other, and high value
indicates that CFs are different from each other. This situation may also
affects the action-ability of generated CFs. This quantity is also influenced
by sparsity as its high value indicates that a large number of features may be
changed and hence it may trigger a larger diversity value which is not
desirable. For this reason, as shown in (15), we use normalized diversity
score in which normalization is done by the dividing (14) by sparsity value.

$\text{diversity${}_{nrm}$}:=\frac{1}{kC2}\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}\frac{d(x_{cf}^{i},x_{cf}^{j})}{\text{prox}(x_{cf}^{i})+\text{prox}(x_{cf}^{j})}$
(15)

where $\text{prox}(x_{cf}^{i}),\;\text{prox}(x_{cf}^{j})$ indicates the
proximity of the CFs $x_{cf}^{i},\;x_{cf}^{j}$ with respect to the query
point, $x_{0}$.

  4. 4.

Coverage: this quantity stands for the fraction of valid CFs. In our
experiments, we generate multiple CFs and this measure counts how many
instances the CF is a valid one. We consider a CF generation output invalid if
it generates CF belonging to the same class as the query point or if the
generation method was not able to generate any output at all. This measure is
expected to be maximum for a CF generation method.

###  IV-E MD-PSO algorithm for counterfactual generation

In this section, we describe our algorithm and how we incorporated the
advantages mentioned in Section II-A1.

For actionable CF generation, we have formulated an algorithm that gives a
control over the proximity and sparsity evaluation metrics. The idea is to
limit the number of features that can change and this feature subset given the
name active set ($\mathcal{A}$), is selected based on the information value
(IV) statistic. The number of features that can be changed or cardinality of
active set is set as a hyper-parameter, $h$. In other words, the top $h$
features are selected after arranging them in descending order of IV. This
helps in controlling the sparsity metric. A description of this statistic is
provided in Appendix.

As the next step, box constraints are set to the features in $\mathcal{A}$. We
scale the dataset in the interval [0,1] for the experiments. The constraints
are enabled in the form of a hyper-parameter, $\epsilon$, that characterizes
the range features can vary and it enables control over proximity. Note that
the box constraint is enabled in the form of $[z(1-\epsilon),z(1+\epsilon)]$
if $z$ is the feature value. If the interval bounds falls outside [0,1] they
will be capped to the extremes of 0 or 1. The processes are summarized in
Algorithm 1.

Input : decision function $f(.)$, query data point $x_{0}$, training dataset
$D$, box constraint parameter $\epsilon$, number of mutable features $h$

Output : A set of counterfactuals

1

2for  _each feature in $D$_ do

3 Find the information value

4

5 end for

6

7Arrange the features in the decreasing order of $IV$

8 Select the top $h$ features to form $\mathcal{A}$

9

10Initialize the particle values satisfying $\epsilon$-criterion with respect
to $x_{0}$

11

12Run MDPSO algorithm with the features defined in $\mathcal{A}$

13

14Apply CF selection criteria on particles

15

16Return selected CFs

Algorithm 1 MDPSO algorithm for counterfactual generation

Note that in our experiments, the parameter $\epsilon$ is common for all
features. However, based on the domain knowledge custom parameters can be used
for different features. The CF selection criteria in line-8 of Algorithm 1 is
explained in Section V-B2.

##  V Experiments

In this section, we describe the experiment settings, datasets used, results
and related observations.

###  V-A Datasets

To check the effectiveness of the proposed approach, we used three high
dimensional datasets namely [21], Arrhythmia [22], hill-valley [23], and LSVT
[24] along with the standard, COMPAS dataset.

COMPAS dataset is the details of 10,000 persons with criminal charges in the
state of Florida. The dataset was used to grant parole by checking into the
likelihood of re-offending the crimes. The Hill-valley dataset consists of a
collection 100 points in a 2D graph that takes the form of a hill or a valley.
The Arrhythmia dataset is a collection of patient records to detect the
presence and absence of cardiac arrhythmia. The original dataset is of 16
classes. In our experiments, we converted them into a binary classification
problem by taking the ’normal’ class and rest of the classes combined as the
other class. The LSVT is a dataset that assess whether voice rehabilitation
treatment lead to phonations considered ’acceptable’ or ’unacceptable’ in
patients suffering from Parkinson’s disease. The data points consist of a set
of features from voice processing algorithms.

TABLE I: Dataset details. Size indicates the number of data points, Cont.feat
- number of continous features and Cat.feat - number of categorical features.

Dataset | Classes | Size | Cont.feat. | Cat.feat.
---|---|---|---|---
COMPAS | 2 | 5238 | 13 | 0
Hill-Valley | 2 | 1212 | 100 | 0
Arrhythmia | 2 | 452 | 177 | 85
LSVT | 2 | 126 | 304 | 3

###  V-B Experimental setup

In this section, we describe the parameters related to the models we have used
for the experiments and other design parameters.

####  V-B1 General settings

For PSO, we have used 50 number of particles and the total number of
iterations or generations are set to 100. The parameters
$c_{i},i=\\{0,1,2,3\\}$ and $r_{i},i=\\{1,2,3\\}$ are fixed by cross-
validation.

The number of data points whose CFs need to be determined are taken as 5 and
they are chosen at random from the testing set. We generate 5 number of CFs
for each of these data points. The metrics used to evaluate the quality of CFs
are the ones explained in Section IV-D. The results reported are averaged
across each instance of the CF generation.

The model chosen for classification is selected as the best performing one
among logistic regression, artificial neural networks and random forest. Once
the model for a dataset is fixed, it is saved and consumed by the CF
generation methods. Note that in our experiments, random forest was the best
performing model for all datasets. Note that in this study, the selection of
classifier is merely an enabler to supply the decision function $f(.)$.

TABLE II: Results of CF generation experiments. Dataset | Method | Proximity | Sparsity | Diversity | Norm. Div | Coverage
---|---|---|---|---|---|---
| DiCE-Random | 1.3992 | 0.1999 | 1.7163 | 1.2266 | 1.00
| DiCE-Genetic | 1.5537 | 0.3571 | 0.0437 | 0.0281 | 1.00
| GS | 1.1109 | 0.4464 | 1.9586 | 1.7630 | 0.80
| Face-KNN | 1.5928 | 0.3714 | 1.8357 | 1.1525 | 1.00
| Face-Epsilon | 1.6795 | 0.3828 | 1.8725 | 1.1149 | 1.00
COMPAS | MD-PSO | 0.2629 | 0.1230 | 0.2959 | 1.1257 | 1.00
| DiCE-Random | 0.9079 | 0.0633 | 1.0800 | 1.1895 | 1.00
| DiCE-Genetic | 0.5047 | 0.7227 | 0.6890 | 1.3651 | 0.80
| GS | 1.0040 | 1.0000 | 0.9864 | 0.9824 | 0.60
| Face-KNN | 1.1806 | 0.7980 | 0.9885 | 0.8372 | 1.00
| Face-Epsilon | 1.0022 | 0.7976 | 0.8417 | 0.8398 | 1.00
Hill-valley | MD-PSO | 0.0700 | 0.6440 | 0.0571 | 0.8172 | 1.00
| DiCE-Random | 1.6771 | 0.2159 | 2.9967 | 1.7868 | 1.00
| DiCE-Genetic | 2.3337 | 0.5269 | 2.3836 | 1.0213 | 1.00
| GS | 1.1168 | 0.9962 | 2.1829 | 1.9546 | 0.60
| Face-KNN | 2.0494 | 0.4188 | 2.6015 | 1.2693 | 1.00
| Face-Epsilon | 2.6416 | 0.5075 | 2.4496 | 0.9273 | 1.00
Arrhythmia | MD-PSO | 0.9989 | 0.0865 | 1.0452 | 1.0464 | 0.60
| DiCE-Random | 1.4819 | 0.1639 | 2.7050 | 1.8253 | 0.80
| DiCE-Genetic | 2.1654 | 0.8665 | 2.3250 | 1.0737 | 0.80
| GS | 1.0056 | 0.9967 | 1.6997 | 1.6902 | 0.60
| Face-KNN | 1.7700 | 0.7759 | 2.1967 | 1.2410 | 1.00
| Face-Epsilon | 2.3219 | 0.9713 | 2.1201 | 0.9130 | 1.00
LSVT | MD-PSO | 1.7859 | 0.3933 | 0.9527 | 0.5334 | 0.80

####  V-B2 Counterfactual selection criteria

After the PSO convergence, we have multiple options to select the $k$ number
of CFs. The basic method is to choose the top $k$ best particles in terms of
minimizing the objective function. But if the PSO convergence is proper, there
is a high probability that the best $k$ particles are close to each other.
Hence it can adversely affect the diversity metric.

Another option is to keep track of the individual best positions of each
particle across all iterations. The problem with this approach is that it can
create additional computation overhead and mostly these individual bests might
have occurred at the last set of iterations.

To ensure a balance between the evaluation metrics, we have done a k-means
clustering over the converged particle positions and a CF is randomly chosen
from each cluster. The number of clusters is taken as the number of CFs
intended to be created which is 5 in our experiments. We have found that this
third approach was giving optimal results compared to the first two.

####  V-B3 Settings of state-of-the-arts

The scope of our study is limited to only instance-centric methods and hence
the proposed method is compared with the following state-of-the-arts - growing
spheres (GS) [10], DiCE [9] with random and genetic algorithm variants and
FACE [11] with EPS and KNN variants. Among these methods only DiCE supports
multiple CF generation. For other cases, we run them 5 times with different
initializations to get multiple CFs.

The GS and FACE methods are implemented with the CARLA library [25] and DiCE
with the library published by authors [9]. For GS, the step size value for
growing the sphere is chosen as 0.02. In the case of FACE, hyperparameters for
the graph size is tuned by a grid search [26]. The value of radius for the
epsilon graph is chosen as 0.25 after cross-validation.

###  V-C Results and Observations

The results obtained in our experiments are tabulated in Table II. The best
results are bolded. Note that the desired values of proximity and sparsity is
to be minimum and that of coverage is maximum. However, it is difficult to set
the desired range for both the diversity metrics as explained in Section IV-D.
In this case, for the sake of checking the quality of a method, we can check
whether the scores of the method lies between the minimum and maximum scores
among all methods. If it is so, that particular method would not be generating
CFs that have too low or high values of diversity.

From the results, it can be seen that proposed MD-PSO method has the best
proximity score in all datasets except LSVT. In the case of LSVT, the best
result is with GS but its sparsity and normalized diversity score is very
high.

In terms of sparsity, MD-PSO has the best results in COMPAS and Arrhythmia. In
the case of Hill-valley and LSVT datasets, MD-PSO has the second best result
following DiCE random. However, in Hill-valley, DiCE Random has a high
proximity score (0.9079) compared to MD-PSO (0.07).

The coverage results of MD-PSO is maximum in the case of COMPAS and Hill-
valley datasets and the second best in other datasets. The FACE variants are
the only models that managed to cover the complete requirement of 5 number of
CF generations for all the query points. However, these models have the
highest proximity score which affects the action-ability of CFs.

It can be seen that none of the models are able to give the best results
across all datasets. However, MD-PSO is having consistent performance in the
metrics relative to the state-of-the-arts. The results also validate the
effectiveness of the control mechanism over the proximity and sparsity scores
in the proposed algorithm as explained in Section IV-E.

Note that both the diversity and normalized diversity is provided in the
results. This is given to understand the inter-dependence between proximity
and diversity. This dependency is more evident in the following example - in
the case of MD-PSO result in Hill-valley, the diversity score (0.0571) is the
lowest among all methods due to a low proximity score. However, the normalized
diversity score (0.8172) is in par with the rest of the methods. Hence
normalized diversity score helps in making meaningful comparison of the
diversity of the generated CFs among the methods whose proximity score varies
in a large range.

It can be noted that the normalized diversity score of MD-PSO lies between the
maximum and minimum in the case of COMPAS, Hill-valley and Arrhythmia
datasets. Hence the divergence levels among the CFs lie between the extremes
and indicate the effectiveness of the proposed approach.

##  VI Conclusions

We designed an algorithm for counterfactual generation in high dimensional
datasets based on particle swarm optimization. The objective function is
formulated as a multi-objective function comprising the properties that
influence actionable generation, namely, validity, proximity, and sparsity. We
adopted the MD-PSO in which an explicit control is enabled over proximity, and
sparsity properties and suitable to optimize categorical attributes in the
one-hot encoded format. With this features, we proposed an algorithm that
helps in CF generations that are actionable in the real-world. The method was
tested on real-world datasets and the results are found to be superior
compared to that of the state-of-the-arts. As future work, we consider the
optimization problem of CF generation in the context of Bayesian optimization.

Information value (IV) is a measure that helps to identify how a predictor
affects in the prediction of target variable. To calculate this value, we
divide each feature into a finite number of bins and find out how many number
of data points falls in the bins for each class. The quantity is measured as
given in (16).

$\text{IV}=\sum_{i}\left(\frac{n_{p}^{i}}{n_{p}}-\frac{n_{n}^{i}}{n_{n}}\right)\times\frac{n_{p}^{i}/n_{p}}{n_{n}^{i}/n_{n}}$
(16)

The summation in (16) is over the bins, $n_{p}^{i}$ and $n_{n}^{i}$ is the
number of data points in positive and negative class respectively in the
bin:$i$, and $n_{p}$ and $n_{n}$ are the total number of data points in
positive and negative class respectively. An IV value $>$ 0.5 indicates that
the corresponding feature is an extremely strong predictor and values in the
interval [0.3, 0.5] indicates strong predictor [27]. In the experiments, the
number of bins was chosen as 10 after removal of data points that are
outliers.

## References

  * [1] P. Voigt and A. Von dem Bussche, “The eu general data protection regulation (gdpr),” _A Practical Guide, 1st Ed., Cham: Springer International Publishing_ , vol. 10, p. 3152676, 2017.
  * [2] S. M. Lundberg and S.-I. Lee, “A unified approach to interpreting model predictions,” in _Proceedings of the 31st international conference on neural information processing systems_ , 2017, pp. 4768–4777.
  * [3] M. T. Ribeiro, S. Singh, and C. Guestrin, “” 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_ , 2016, pp. 1135–1144.
  * [4] N. J. Roese, “Counterfactual thinking.” _Psychological bulletin_ , vol. 121, no. 1, p. 133, 1997.
  * [5] S. L. Morgan and C. Winship, _Counterfactuals and causal inference_. Cambridge University Press, 2015.
  * [6] M. J. Kusner, J. Loftus, C. Russell, and R. Silva, “Counterfactual fairness,” in _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., vol. 30. Curran Associates, Inc., 2017.
  * [7] C. Molnar, _Interpretable Machine Learning_ , 2019.
  * [8] S. Wachter, B. Mittelstadt, and C. Russell, “Counterfactual explanations without opening the black box: Automated decisions and the gdpr,” _Harv. JL & Tech._, vol. 31, p. 841, 2017.
  * [9] R. K. Mothilal, A. Sharma, and C. Tan, “Explaining machine learning classifiers through diverse counterfactual explanations,” in _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , 2020, pp. 607–617.
  * [10] T. Laugel, M.-J. Lesot, C. Marsala, X. Renard, and M. Detyniecki, “Inverse classification for comparison-based interpretability in machine learning,” _arXiv preprint arXiv:1712.08443_ , 2017.
  * [11] R. Poyiadzi, K. Sokol, R. Santos-Rodriguez, T. De Bie, and P. Flach, “Face: Feasible and actionable counterfactual explanations,” in _Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society_ , 2020, pp. 344–350.
  * [12] Y.-L. Chou, C. Moreira, P. Bruza, C. Ouyang, and J. Jorge, “Counterfactuals and causability in explainable artificial intelligence: Theory, algorithms, and applications,” _Information Fusion_ , vol. 81, pp. 59–83, 2022.
  * [13] S. Dandl, C. Molnar, M. Binder, and B. Bischl, “Multi-objective counterfactual explanations,” in _International Conference on Parallel Problem Solving from Nature_. Springer, 2020, pp. 448–469.
  * [14] A. V. Looveren and J. Klaise, “Interpretable counterfactual explanations guided by prototypes,” in _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_. Springer, 2021, pp. 650–665.
  * [15] A. Artelt and B. Hammer, “On the computation of counterfactual explanations–a survey,” _arXiv preprint arXiv:1911.07749_ , 2019.
  * [16] M. Downs, J. L. Chu, Y. Yacoby, F. Doshi-Velez, and W. Pan, “Cruds: Counterfactual recourse using disentangled subspaces,” in _ICML Workshop on Human Interpretability in Machine Learning_ , 2020.
  * [17] A. Dhurandhar, P.-Y. Chen, R. Luss, C.-C. Tu, P. Ting, K. Shanmugam, and P. Das, “Explanations based on the missing: Towards contrastive explanations with pertinent negatives,” _arXiv preprint arXiv:1802.07623_ , 2018.
  * [18] J. Antorán, U. Bhatt, T. Adel, A. Weller, and J. M. Hernández-Lobato, “Getting a clue: A method for explaining uncertainty estimates,” 2021.
  * [19] S. Joshi, O. Koyejo, W. Vijitbenjaronk, B. Kim, and J. Ghosh, “Towards realistic individual recourse and actionable explanations in black-box decision making systems,” _arXiv preprint arXiv:1907.09615_ , 2019.
  * [20] S. Chowdhury, W. Tong, A. Messac, and J. Zhang, “A mixed-discrete particle swarm optimization algorithm with explicit diversity-preservation,” _Structural and Multidisciplinary Optimization_ , vol. 47, no. 3, pp. 367–388, 2013.
  * [21] J. Dressel and H. Farid, “The accuracy, fairness, and limits of predicting recidivism,” _Science advances_ , vol. 4, no. 1, p. eaao5580, 2018.
  * [22] H. A. Guvenir, B. Acar, G. Demiroz, and A. Cekin, “A supervised machine learning algorithm for arrhythmia analysis,” in _Computers in Cardiology 1997_. IEEE, 1997, pp. 433–436. [Online]. Available: https://archive.ics.uci.edu/ml/datasets/arrhythmia
  * [23] Hill-valley data set. [Online]. Available: https://https://archive.ics.uci.edu/ml/datasets/hill-valley
  * [24] A. Tsanas, M. A. Little, C. Fox, and L. O. Ramig, “Objective automatic assessment of rehabilitative speech treatment in parkinson’s disease,” _IEEE Transactions on Neural Systems and Rehabilitation Engineering_ , vol. 22, no. 1, pp. 181–190, 2013. [Online]. Available: https://www.openml.org/d/1484
  * [25] M. Pawelczyk, S. Bielawski, J. Van den Heuvel, T. Richter, and G. Kasneci, “Carla: A python library to benchmark algorithmic recourse and counterfactual explanation algorithms,” 2021.
  * [26] S. Shekhar, A. Bansode, and A. Salim, “A comparative study of hyper-parameter optimization tools,” in _2021 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)_ , 2021, pp. 1–6.
  * [27] Q. Shi, Y.-L. Zhang, L. Li, X. Yang, M. Li, and J. Zhou, “Safe: Scalable automatic feature engineering framework for industrial tasks,” in _2020 IEEE 36th International Conference on Data Engineering (ICDE)_. IEEE, 2020, pp. 1645–1656.