# Motion-Based Handwriting Recognition

Junshen Kevin Chen
Stanford University
<EMAIL_ADDRESS>
Wanze Xie
Stanford University
<EMAIL_ADDRESS>
Yutong (Kelly) He
Stanford University
<EMAIL_ADDRESS>

##  1 Introduction

It is prevalent in today’s world for people to write on a touch screen with a
smart pen, as there is a strong need to digitize hand-written content, to make
the review and indexing easier. However, despite the success of character
recognition on digital devices [1, 2, 3], requiring a digitizer as the writing
surface poses a possibly unnecessary restriction to overcome. In addition, in
VR and AR applications, it is also hard to recognize the texts written with
the motion sensors [4, 5].

We define the problem for identifying handwriting texts given the motion data
collected by a sensor as a motion-based handwriting recognition problem. Such
problem is different from other approaches such as Optical Character
Recognition (OCR)[6] problem as it requires our model to not utilize any
visual features of the written text. In this project, we focus on classifying
individual characters with motion data. We propose a solution by using a pen
equipped with motion sensor to predict the English letters written by the
user. Instead of using image data or on-screen stroke data, we analyze the
acceleration and gyroscopic data of the pen using machine learning techniques
to classify the characters the user is writing.

To tackle this problem, we first collected our own dataset by building the
hardware and inviting 20 different users to write lowercase English alphabet
with the equipment. The input to our algorithm is the yaw, pitch and roll
rotation values of the sensor collected when the user is writing with the pen.
After preprocessing the data using feature interpolation, data augmentation,
and denoising using an autoencoder, we use the processed data to experiment
with 4 different classifers: KNN, SVM, CNN and RNN to predict the labels that
indicate which letters the user was writing when the sensor data was
collected.

Our contribution are as the following:

  1. -

We define a new problem for recognizing handwriting text using only motion
data.

  2. -

We built a hardware to collect a new dataset with 20 different subject writing
lowercase English alphabet 20 times.

  3. -

We designed and implemented a pipeline that solves the defined problem with
feature interpolation, data augmentation, denosing autoencoding and 4
different classifers.

  4. -

We conduct experiments for pipeline with two different settings and our best
model achieves $86.6\%$ accuracy in the random split experiment and $53.6\%$
in the subject split experiment.

All codes and dataset are available at our GitHub repository
https://github.com/RussellXie7/motion-based-hand writing-recognition and
demonstrations are available at https://youtu.be/SGBSVo2U12s.

##  2 Related Work

##### Sensor-Based Gesture Recognition

Recently, there have been lots of researches for various ways of leveraging
inertial motion unit (IMU) data to predict the gesture or the activity of
users [7, 8, 9, 10, 11], but few studies make use of the IMU data to predict
the handwriting letter due to the lack of relevant dataset. Oh et al. analyzed
using inertial sensor based data to recognize handwritten arabic numbers
handwritten in the 3D space [12]. However, one major problem with the system
described in the study is that it requires user to wave hand in the space to
outline the trajectory of the intended number to write, which contradicts the
writing habits of people in daily activity (e,g., write on the table, or write
in space with pen-tip pointing down). Zhou et al. [13] performed a similar
study for sensor-based capital letter classification using a single layer
unsupervised network. Our study shares the same spirit, but instead we have a
more practical set-up of the handwriting sensing device and explore modern
machine learning techniques to address both data pre-processing and
classification tasks.

##### Vision-Based Handwriting Recognition

It has been very successful in using vision-based approaches to tackle the
handwriting recognition problem, with OCR [6] being one of the most prominent
research field, which has been prosperous in applications like translating
manuscript into digitized texts. Other vision based researches propose
tracking the motion of human finger [14] or forearms [15] using RGB or depth
camera. Nevertheless, without a digital screen, an OCR based approach often
require an image of the handwritten manuscript, which is asynchronous between
the writing and recognition event. Camera based approaches often require an
extra layer of set-up in order to recognize and convert handwriting into
digital texts in real time, and occlusions can often be a challenge as well
[16]. Our system aims to approach the problem with a simpler framework by only
requiring a pen.

##  3 Dataset and Features

For this project, we built the hardware with a MPU9250 9-axis motion sensor,
an Arduino Uno R3, and a 3D printed mount to connect stylus and the sensor. We
also constructed a writing grid to help subjects write data in a consistent
size.

Figure 1: Hardware (left) and writing grid (right)

We formalize our data collection strategy by recording 20 writings of each
lowercase letter from the alphabet from numerous subjects, and collected our
own original data set. From the start of subject pressing down the record
button, move the stylus to write one single letter, to the release of the
button constitutes a writing event, producing data known as a sequence,
consisting of as many rows (one row per frame) as the sequence takes. Then,
some frames a sample of a writing sequence is in the following format:

td | yaw | pitch | roll | ax | ay | az
---|---|---|---|---|---|---
7 | 90.10 | -10.34 | -20.02 | 206.9 | -374.1 | 1052.9
25 | 90.27 | -9.86 | -20.29 | 193.0 | -401.7 | 1046.2
Table 1: Frames from a sample of writing sequence

Where td is the time delta between the last frame and current frame sampled by
the sensor in $ms$, yaw, pitch, roll are rotation values in $degrees$, and ax,
ay, az are acceleration on each Cartesian axis in $mm/s^{2}$.

We have collected 20 sequences per letter from 20 subjects, resulting in a
dataset of $10,400$ sequences.

###  3.1 Visualization

We build a visualizer to gain insight to the data before developing several
techniques to process and use the data to train various models.

Figure 2: Letter ’a’ written by two subjects

The above diagram plots the same letter ’a’ written by two different subjects,
visualized by rotating a unit vector anchored to the origin, and plotting the
tail of the vector.

Observing the above, even though the traces of rotation values do not resemble
the letter itself, mainly due to the sensor records the tail of the stylus, we
notice that writing of the same letter share characteristics across subjects,
and distinct letters have identifiable traces against each other.

###  3.2 Data Augmentation

Due to the difficulty to collect a large a mount of data within the time scope
of this project, we implement a data augmentation pipeline to generate new
samples by:

  1. 1.

Add a Gaussian noise centered at 0 and with customized small variance to each
entry;

  2. 2.

Rotate the object by a small random quaternion vector;

  3. 3.

Stretch each sequence by three random scalar constants corresponding to yaw,
pitch, roll.

###  3.3 Calibration and Normalization

The sensor is not by default calibrated before each subject begin writing
sequences. To solve this problem, we ask each subject to hold the stylus
upright for 10 seconds, and use the mean of that sensor recording to subtract
from all frames recorded from this subject.

For rotation values, we want data to be invariant to different subjects’
holding the stylus differently, and therefore we also subtract frame 0 of each
sequence from all frames in this sequence, to get a delta rotation value.

###  3.4 Data Interpolation and Re-sampling

For some models that do not have the inherent structure for time series data,
such as a CNN, we need to transform the input sequence to a flat vector before
the network can be trained. There are two problems in merging and flattening
all frames in each sequence directly: (1) subjects write in different speeds,
and therefore some writing of the same letter may produce a longer sequence
than others and hence produce vectors with different length; (2) the sensor
samples in a variable rate, and therefore the time delta between each
timestamp varies.

To solve this problem, we design a procedure that normalizes sequences so that
they have the same number of features. To obtain the desired fixed number of
features $N$, where $N$ is ideally the average number of frames in each
sequence, do:

  1. 1.

Extract the td, yaw, pitch, roll values from each data sequence and create a
$3\times 1$ array for them, exclude td;

  2. 2.

Map each yaw, pitch, roll to corresponding time stamps;

  3. 3.

Create a 1D linear interpolation model for each sequence;

  4. 4.

Generate linearly spaced time stamps based on the lower and upper bound of the
original timestamps;

  5. 5.

Calculate the interpolated yaw, pitch, roll value for each timestamp generated
in step 4;

  6. 6.

Pair up corresponding yaw, pitch, roll values and merge them into a single
vector of length $3N$ if flatten, or of shape $N\times 3$ if not flatten;

We formalize such feature extractor as: $f(x):\mathbf{R}^{M\times
4}\to\mathbf{R}^{3N}\cup\mathbf{R}^{N\times 3}$, $M$ is number of frames in
each sequence that varies, and each frame contain $\\{td,y,p,r\\}$. Output is
in either $\mathbf{R}^{3N}$ or $\mathbf{R}^{N\times 3}$ depending on if we
choose to flatten the data.

###  3.5 Denoising Autoencoder

One of the limitations of our system is that it collects data at an unstable
sample rate, and also because of the small vibration of the pen when people
move their hands, the data we collected are noisy by nature. We explore a
neural network based approach using autoencoder to deal with this problem.

An autoencoder is an architecture composed of both an encoder and a decoder
and it is trained to minimize the reconstruction error between the encoded-
then-decoded output and the input. Before training our classifiers, we can
choose to apply autoencoder respectively to the raw yaw, pitch and roll data,
and we analyze the results in Section 5.

The input and output of the autoencoder are both a vector in $\mathbf{R}^{N}$,
where $N$ is the number of features. In all our experiments $N=100$. The
hidden encoding and decoding layer both have 128 features and the encoded
feature size is 64. All layers are fully connected, and we use mean-squared
error defined as below to train the model.

$J(x,\hat{x})=\frac{1}{N}\sum_{i=1}^{N}(x^{(i)}-\hat{x}^{(i)})^{2}$

$x^{(i)}\in\mathbf{R}$, which is the rotation value in degrees from one of the
yaw, pitch and roll data and $\hat{x}^{(i)}$ is the reconstructed input.

As a result, with a encoded feature size smaller than the number of features
of the input, the autoencoder can learn the most efficient way to represent
the data and therefore produce a result with most noises excluded.

##  4 Methods

###  4.1 K Nearest Neighbors (KNN)

Intuitively, even though motion data does not construct a pattern similar to
the letter itself, it should still be distinguishable, i.e. the nearest
neighbors to an unseen “a” should be predominantly “a”s.

Therefore we choose KNN [17] as a baseline classifier. For any unseen sample,
choosing $K$ seen samples that are similar to it, then taking the most popular
label to be the prediction. The algorithm is simple as there is no “training”
involved.

Input : $\hat{x}$, an unseen sample; $K$, number of neighbors

Output : $\hat{y}$, the prediction

Data: $\forall i,(x^{(i)},y^{(i)})$, seen samples and their labels

$D^{(i)}\leftarrow\|x^{(i)}-\hat{x}\|$ for all $x^{(i)}$

$\hat{S}\leftarrow$ $K$ samples $(x^{(i)},y^{(i)})$ for the smallest value of
$D^{(i)}$

yield $\arg\max_{y}\sum_{(x^{(i)},y^{(i)})\in\hat{S}}\mathbf{1}[y^{(i)}=y]$

Algorithm 1 Predicting with K nearest neighbors

###  4.2 Support Vector Machine (SVM)

We use a “one-vs-all” strategy to implement the multi-class SVM [18] since our
data set is balanced (there are roughly equal number of samples for each
label). For each of the 26 letters, train an SVM with polynomial kernel with
positive samples are the ones of the corresponding letter, and negative
samples are samples of all other letters.

Input : $(x^{(i)},y^{(i)})\in(X,Y)$

Output : $svm$, a set of 26 SVMs

for  _$y\leftarrow 0,...,26$_ do

$X_{pos}\leftarrow x^{(i)},\forall y^{(i)}=y$

$X_{neg}\leftarrow x^{(i)},\forall y^{(i)}\neq y$

$svm_{y}\leftarrow TrainSVM(X_{pos},X_{neg})$

end for

yield $svm$

Algorithm 2 Training one-vs-all SVMs

At prediction time, produce a score from each SVM, select the one that
generates the most positive score as the prediction.

Input : $svm$, a set of 26 SVMs; $\hat{x}$, an unseen sample

Output : $\hat{y}$, a predicted label

yield $\arg\max_{i}SVMPredict(svm_{i},\hat{x})$

Algorithm 3 Predicting with one-vs-all SVMs

###  4.3 Convolutional Neural Network (CNN)

The format of our interpolated, re-sampled data consists of three independent
components, yaw, pitch, and roll, where each has identical shape of
$(NumFeatures,)$. We may use a CNN[19] to learn from this data by considering
each component to be in its individual channel, and construct layers of 1-D
convolution, with activation and pooling to construct a network. After
experimentation, our best performing network has the following structure:

  1. -

Input: 3 channels of $100\times 1$ vectors

  2. -

3 Convolution $\to$ max-pool $\to$ ReLU: number of channel increases $3\to
32\to 64$, kernel size 3 stride 1 with padding, size $100\times 1$ unchanged

  3. -

3 Fully connected layers of width $6400\to 3200\to 1600\to 500$ with ReLU
activation

  4. -

Output: vector of $26\times 1$ of one-hot encoding for each letter.

The training label (and subsequently prediction output) is a one-hot encoding
of each of the 26 letters. We train the CNN by gradient descent, minimizing
cross entropy:

$J(x,y)=-\sum_{i=1}^{n}\sum_{c=1}^{C}y_{c}^{(i)}\log\hat{y}_{c}^{(i)}$

From observing the training result of the two baseline models (KNN and SVM),
we realize that they result in very low test accuracy using subject split,
meaning that with a more powerful model, we need to be careful to not overfit
to the training set. Therefore, in training the CNN, we use aggressive L2
regularization with $\lambda=0.1$ when calculating gloss.

###  4.4 Recurrent Neural Network (RNN)

One of the state-of-the-art models for representing sequential data is
Recurrent Neural Network (RNN). Unlike feedforward networks such as CNNs, RNNs
consider inputs in a sequential data at each time step as an individual node
and build connections among the nodes to form a directed graph in the temporal
manner. Such structure has the inherent benefits for computing sequential data
as it is able to utilize its intermediate hidden states as "memories" to store
information about inputs in the previous time stamps.

Long Short-Term Memory (LSTM)[20] is a specific type of RNN consisting of
three components: input gates, output gates, forget gates. Input gates handle
the new data fed into the network, output gates determine the values stores in
the cells to be used to calculate the output activation, and forget gates
control the values to be kept in the cells.

In this project, we designed a 5-layer LSTM cell as our RNN model to tackle
this problem. For each node in the input sequence, each layer computes the
following:

$\begin{array}[]{ll}i_{t}=\sigma(W_{ii}x_{t}+b_{ii}+W_{hi}h_{(t-1)}+b_{hi})\\\
f_{t}=\sigma(W_{if}x_{t}+b_{if}+W_{hf}h_{(t-1)}+b_{hf})\\\
g_{t}=\tanh(W_{ig}x_{t}+b_{ig}+W_{hg}h_{(t-1)}+b_{hg})\\\
o_{t}=\sigma(W_{io}x_{t}+b_{io}+W_{ho}h_{(t-1)}+b_{ho})\\\
c_{t}=f_{t}*c_{(t-1)}+i_{t}*g_{t}\\\ h_{t}=o_{t}*\tanh(c_{t})\\\ \end{array}$

where $i_{t}$ is the input gate at time $t$, $f_{t}$ is the forget gate at
time $t$ and $o_{t}$ is the output gate at time $t$. $g_{t}$ is an
intermediate state that filters and activates the long term memory. $h_{t}$ is
the hidden state, or short term memory, at time $t$, $c_{t}$ is the cell state
at time $t$ and $x_{t}$ is the input at time $t$. $\sigma$ is the sigmoid
function, and $*$ is the Hadamard product. $W_{jk}$ and $b_{jk}$ are weights
and bias for the filter connecting gate $j$ and gate $k$.

For our 5-layer LSTM, the input for the $i$th layer is the product hidden
states of the $i-1$th layer for all layers except the first layer. We randomly
initialize the hidden states and the cell state with a standard normal
distribution. Cross-entropy loss is also used to train the RNN model.

##  5 Experiments

###  5.1 Splitting Data for Training and Testing

We propose two ways to split the data set for training.

Classic random split: randomly split the data set with proportion to 80:10:10
for train set, dev set, and test set respectively. We expect this would train
the model to learn writing pattern from each subject then make a prediction on
the seen subjects.

Individual subject split: randomly choose two subjects for dev, two subjects
for test, and use all other subjects’ data for training. We expect this would
lead to lower performance, but indicate how well each model generalizes to the
overall population.

Because we have a small amount of data, ideally it is more appropriate to use
cross-validation as the method to assess the generality and accuracy of the
models. However, due to the time consuming nature of RNN training, we were not
able to complete cross-validation for a large enough number of folds. As a
result, the accuracy reported below were calculated using the splitting
strategies described above, and we plan on experiment with cross-validation in
the future.

###  5.2 Data Preprocessing

####  5.2.1 Interpolation and Re-sampling

Figure 3: Compare before and after re-sampling

Due to the different writing habits among subjects, the data sequence we
collected do not have a consistent length by nature. By setting our fixed
feature number to be 100, we downsample data from those who write at a slower
pace, and upsample data from people who write faster, using the interpolation
technique introduced in section 3.4, and an example visualization of the
result is shown as above.

####  5.2.2 Data Augmentation

(a) A data sequence for letter "a" without augmentation.

(b) A data sequence for letter "a" with augmentation.

Figure 4: Data Augmentation Demonstration

Observe that after augmenting the sequence, the pattern is similar to the
original and distinct from sequences of other labels.

####  5.2.3 Denoising Autoencoder

Figure 5: A data sequence for letter "a" without augmentation.

The autoencoder network appears to learn to encode the descriptive features of
the raw input, while discarding noise from the raw sequence, to produce a
smooth curve that still very much resembles the original.

###  5.3 Baseline Models

K | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---
Rand. split | .721 | .718 | .718 | .707 | .697 | .693
Subj. split | .126 | .127 | .128 | .126 | .129 | .131
Table 2: KNN Test Accuracy | Random split | Subject Split
---|---|---
Train | 0.753125 | 0.9998
Test | 0.590778 | 0.15562
Table 3: SVM Accuracy

We observe that neither KNN nor SVM achieve decent accuracy with subject
split, but is able to generalize relatively well with classic random split,
with KNN achieving 0.721 test accuracy at $K=2$.

###  5.4 CNN

The model is given a computation budget of 20 epochs, trained with a mini-
batch gradient descent with batch size 500. We use Adam optimization[21] to
train the model. The model shows the following convergence behavior.

Figure 6: CNN Training and Validation Accuracy

We observe that for both splits, the model is able to fit well to the training
set, but only generalizes well to the validation set with random split, even
with aggressive L2 regularization.

###  5.5 RNN

Figure 7: RNN Training and Validation Accuracy

We use the same mini-batch gradient descent strategy with feature
interpolation and without data flatten to train the RNN model. In comparison
to CNN, RNN takes many more epochs before it converges, and therefore we give
it a computation budget of 250. We observe that validation accuracy shows
improvement over its CNN counterpart in both random split and subject split.
However, it still suffers from severe overfitting problem with subject pslit
experiment given the large gap between the training and validation curve.

###  5.6 Ablation Study

####  5.6.1 Data Augmentation

|  | CNN | RNN
---|---|---|---
|  | Train | Test | Train | Test
Random Split | w/o aug | 0.985 | 0.710 | 1.000 | 0.766
w/ aug | 0.919 | 0.774 | 0.999 | 0.843
Subject Split | w/o aug | 0.977 | 0.358 | 1.000 | 0.406
w/ aug | 0.988 | 0.396 | 1.000 | 0.510
Table 4: Accuracy with and without Data Augmentation

Table 4 highlights the difference between deep models trained with and without
data augmentation. As we can observe, the data augmentation method is very
effective to improve the test accuracy while all models converge at high
training accuracy. Such observation proves our statement about model
overfitting problem that we concluded in the previous sections, since data
augmentation increases the diversity of the training dataset to help
generalization.

####  5.6.2 Data Denoising

|  | CNN | RNN
---|---|---|---
|  | Train | Test | Train | Test
Random Split | w/o AE | 0.919 | 0.774 | 0.999 | 0.843
w/ AE | 0.996 | 0.784 | 0.999 | 0.866
Subject Split | w/o AE | 0.988 | 0.396 | 1.000 | 0.510
w/ AE | 0.996 | 0.402 | 0.999 | 0.536
Table 5: Accuracy with and without Denoising Autoencoder

The above result shows that denoising the data with a trained autoencoder
results in higher accuracy with both network across both splits of the
dataset. This affirms our hypothesis that small fluctuations in raw sensor
data are indeed noise that are independent from the writing pattern, and that
removing them allows the classifier to better learn the descriptive features
of each class against others.

###  5.7 Overall Performance and Discussion

| Random split | Subject split
---|---|---
| Train | Test | Train | Test
KNN(K=4) | - | 0.718 | - | 0.128
SVM | 0.753 | 0.591 | 0.999 | 0.156
CNN | 0.985 | 0.710 | 0.977 | 0.358
CNN(aug) | 0.919 | 0.774 | 0.988 | 0.396
CNN(aug+AE) | 0.996 | 0.784 | 0.996 | 0.402
RNN | 1.000 | 0.776 | 1.000 | 0.406
RNN(aug) | 0.999 | 0.843 | 1.000 | 0.510
RNN(aug+AE) | 0.999 | 0.866 | 0.999 | 0.536
Table 6: Overall Accuracy

With many samples and complex patterns, our baseline model, SVM, failed to
converge within the computation budget of 40000 iterations. This is evidence
that an SVM with a polynomial kernel is not descriptive enough to learn the
complex pattern. KNN, on the other hand, performs well with a classic random
split, meaning that it is able to find a number of neighbors that are similar,
but fail to generalize to the population, leading to low accuracy with subject
split.

Our RNN with data augmentation and autoencoder denoising perform the best,
both because having more, less noisy data samples result in better learning of
features, but also because RNN is able to learn features from a time series,
resulting in an advantage over CNNs.

We observe that all models suffer from overfitting to the training data. We
hypothesize that this is not over-parameterization, as the networks are simple
with few parameters in comparison to input features. By observing accuracy in
subject split, we notice test accuracy fluctuates substantially as different
runs select different test subjects, and accuracy decreases as the writing
habits of test subjects deviate from ones of train subjects. From this we
interject that there are a few reasons for the low accuracy:

  1. -

Writing habit differs greatly across the population

  2. -

Rotation sensor data alone may not be distinctive enough

  3. -

The lowercase English alphabet has many similar letters that obfuscate the
classifier

##  6 Conclusion, Future Work

We reach the conclusion based on our technique and experiments that, albeit
having a noisy small dataset, it is possible to achieve high accuracy in
handwriting recognition based on rotation sensor data, given the user
calibrates the model with its handwriting habits before it makes predictions.

For future work, we plan to explore additional way to approach motion-based
recognition that are either more plausible to achieve high accuracy, or better
generalize to the population with limited amount of data:

  1. -

Categorize on uppercase English alphabet, as they are far more distinct than
lowercase letters;

  2. -

Gesture recognition, as users are free to define their own gestures, and that
they are by definition more distinct among each other;

  3. -

Remove the pen limitation and use other more intuitive / more accurate
sensors, such as a ring, or a VR controller;

  4. -

Use cross-validation to obtain more accurate representation of the model
performance;

  5. -

Report confusion matrix for the entire alphabet.

## References

  * [1] Maximilian Schrapel, Max-Ludwig Stadler, and Michael Rohs.  Pentelligence: Combining pen tip motion and writing sounds for handwritten digit recognition.  In Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems, CHI ’18, pages 131:1–131:11, New York, NY, USA, 2018. ACM.
  * [2] Jacob O. Wobbrock, Brad A. Myers, and John A. Kembel.  Edgewrite: A stylus-based text entry method designed for high accuracy and stability of motion.  In Proceedings of the 16th Annual ACM Symposium on User Interface Software and Technology, UIST ’03, pages 61–70, New York, NY, USA, 2003. ACM.
  * [3] Multiple pen stroke character set and handwriting recognition system with immediate response.
  * [4] I. Poupyrev, N. Tomokazu, and S. Weghorst.  Virtual notepad: Handwriting in immersive vr.  In Proceedings of the Virtual Reality Annual International Symposium, VRAIS ’98, pages 126–, Washington, DC, USA, 1998. IEEE Computer Society.
  * [5] Augmented reality writing system and method thereof.
  * [6] Sargur N. Srihari, Ajay Shekhawat, and Stephen W. Lam.  Optical character recognition (ocr).  In Encyclopedia of Computer Science, pages 1326–1333. John Wiley and Sons Ltd., Chichester, UK.
  * [7] Minwoo Kim, Jaechan Cho, Seongjoo Lee, and Yunho Jung.  Imu sensor-based hand gesture recognition for human-machine interfaces.  Sensors, 19(18):3827, Sep 2019.
  * [8] Biswarup Ganguly and Amit Konar.  Kinect sensor based gesture recognition for surveillance application, 2018\.
  * [9] F. Grützmacher, J. Wolff, and C. Haubelt.  Sensor-based online hand gesture recognition on multi-core dsps.  In 2015 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 898–902, Dec 2015.
  * [10] Z. Ren, J. Yuan, J. Meng, and Z. Zhang.  Robust part-based hand gesture recognition using kinect sensor.  IEEE Transactions on Multimedia, 15(5):1110–1120, Aug 2013.
  * [11] L. Chen, J. Hoey, C. D. Nugent, D. J. Cook, and Z. Yu.  Sensor-based activity recognition.  IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(6):790–808, Nov 2012.
  * [12] J. K. Oh, Sung-Jung Cho, Won-Chul Bang, Wook Chang, Eunseok Choi, Jing Yang, Joonkee Cho, and Dong Yoon Kim.  Inertial sensor based recognition of 3-d character gestures with an ensemble classifiers.  In Ninth International Workshop on Frontiers in Handwriting Recognition, pages 112–117, Oct 2004.
  * [13] Shengli Zhou, Zhuxin Dong, W. J. Li, and Chung Ping Kwong.  Hand-written character recognition using mems motion sensing technology.  In 2008 IEEE/ASME International Conference on Advanced Intelligent Mechatronics, pages 1418–1423, July 2008.
  * [14] LIANWEN JIN, DUANDUAN YANG, LI-XIN ZHEN, and JIAN-CHENG HUANG.  A novel vision-based finger-writing character recognition system.  Journal of Circuits, Systems and Computers, 16(03):421–436, 2007\.
  * [15] O. F. Ozer, O. Ozun, C. O. Tuzel, V. Atalay, and A. E. Cetin.  Vision-based single-stroke character recognition for wearable computing.  IEEE Intelligent Systems, 16(3):33–37, May 2001.
  * [16] Xing Chen and James Davis.  An occlusion metric for selecting robust camera configurations.  Machine Vision and Applications, 19(4):217–222, Jul 2008.
  * [17] T. Cover and P. Hart.  Nearest neighbor pattern classification.  IEEE Trans. Inf. Theor., 13(1):21–27, September 2006.
  * [18] Marti A. Hearst.  Support vector machines.  IEEE Intelligent Systems, 13(4):18–28, July 1998.
  * [19] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, Nov 1998.
  * [20] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural Comput., 9(8):1735–1780, November 1997.
  * [21] Diederik Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  International Conference on Learning Representations, 12 2014.


# Multi-criteria approach for selecting an explanation from the set of
counterfactuals produced by an ensemble of explainers

Ignacy Stępka1 Mateusz Lango1,2 Jerzy Stefanowski1
1Poznan University of Technology, Poznan, Poland
2Charles University, Prague, Czech Republic
<EMAIL_ADDRESS>
###### Abstract

Counterfactuals are widely used to explain ML model predictions by providing
alternative scenarios for obtaining the more desired predictions. They can be
generated by a variety of methods that optimize different, sometimes
conflicting, quality measures and produce quite different solutions. However,
choosing the most appropriate explanation method and one of the generated
counterfactuals is not an easy task. Instead of forcing the user to test many
different explanation methods and analysing conflicting solutions, in this
paper, we propose to use a multi-stage ensemble approach that will select
single counterfactual based on the multiple-criteria analysis. It offers a
compromise solution that scores well on several popular quality measures. This
approach exploits the dominance relation and the ideal point decision aid
method, which selects one counterfactual from the Pareto front. The conducted
experiments demonstrated that the proposed approach generates fully actionable
counterfactuals with attractive compromise values of the considered quality
measures.

9cm(2.6cm,17cm) This is an extended version of the paper that has been
published in the International Journal of Applied Mathematics and Computer
Science.

##  1 Introduction

Despite incredible progress in machine learning (ML), the wide adoption of its
algorithms, especially in critical domains such as finance or medicine, often
encounters obstacles related to the lack of their interpretability. This is
due to the fact that the majority of currently used machine learning methods
are black-box models that do not provide information about the reasons behind
taking a certain decision, nor do they explain the logic of an algorithm
leading to it. Therefore, there is a growing research interest in explainable
artificial intelligence methods Bodria et al. (2021) offering explanations for
the predictions of black-box models.

Counterfactual explanations (briefly counterfactuals) are one particular type
of such explanations that provide information about how feature values of an
example should be changed to obtain a desired prediction of the model (change
its decision). On the one hand, by interacting with the model using
counterfactuals, the user can better understand how the system works by
exploring the "what would have happened if…" questions. This approach to
building human understanding of machine learning models has some psychological
justifications Miller (2019). On the other hand, a good counterfactual
provides a clear recommendation to the user about what changes are needed in
order to achieve the desired outcome.

There are many practical applications for counterfactual explanations,
including loan decisions Wachter et al. (2017), recruitment processes Pearl et
al. (2016), the discovery of chemical compounds with similar structures but
different properties Wellawatte et al. (2022), analysis of medical diagnosis
results Mertes et al. (2022), and many others, see e.g. the recent survey
Guidotti (2022). For example, consider a scenario where an individual submits
a purchase offer for a property, initially rejected by a model assessing such
proposals. A counterfactual explanation for this situation reveals the minimal
adjustments or enhancements the offeror could implement to ensure the
acceptance of their offer (e.g., increase the offered price, relax
contingencies). Another practical scenario involves a company training a
neural network to assist in the recruitment process for a specific job
position, automating the shortlisting of resumes. In this context,
counterfactual explanations can be employed to verify that the black-box model
does not discriminate against candidates who only differ in terms of a
sensitive and non-actionable feature. Furthermore, for a candidate facing
rejection, a counterfactual explanation can provide valuable insights into the
specific qualifications that were lacking compared to the most similar
candidates who were shortlisted.

A counterfactual explanation is expected to be similar to the example that the
ML model was queried with, but it should change a class prediction. It leads
to a situation where one instance can be explained by many different
counterfactuals. This has led to the introduction of several desired
properties, optimization strategies and quality measures, that a
counterfactual explanation should possess. Such properties include111See Sec.
2 for more details and precise definitions: proximity (counterfactual should
be as similar as possible to a given instance), sparsity (the number of
modified features should be low), actionability (the counterfactual should not
modify immutable features, such as race, or violate monotonic constraints,
e.g. decrease one’s age) and discriminative power (the generated
counterfactual examples should be in the region of the feature space dominated
by the expected class), and others. Even though some of these measures are at
least related to each other (e.g., such as proximity and sparsity), many of
them are not aligned and even contradictory. For example, proximity encourages
the generation of a counterfactual that is as close to the decision boundary
as possible, whereas the discriminative power favours explanations in dense
areas dominated by the other class, which are most likely to be far from the
decision boundary. Related user studies Spreitzer et al. (2022); Förster et
al. (2021) show that human users prefer counterfactuals which, on average,
score well on various criteria.

Generating an appropriate counterfactual explanation is, therefore, a quite
challenging task that involves finding a trade-off between divergent aspects
of explanation quality. Nevertheless, the vast majority of counterfactual
generation methods optimize only one or two measures, usually aggregated by a
weighted sum in the optimized loss function, where the weight is a
hyperparameter of the method, see e.g. Wachter et al. (2017); Chapman-Rounds
et al. (2021); Mothilal et al. (2020); Van Looveren and Klaise (2021). The
choice of a satisfactory weight value, which controls the trade-off between
different aspects of explanation quality, is a not trivial task. The only few
methods Rasouli and Chieh Yu (2022); Dandl et al. (2020) that consider
multiple quality criteria in the process of obtaining counterfactual
explanations, generate a large set of explanations, but leave the task of
selecting a final one to the user. We argue, that it is not enough to present
numerous explanations to the final user due to the choice overload phenomenon
Iyengar and Lepper (2000); Stefanowski (2023). Studies Iyengar and Lepper
(2000); Inbar et al. (2011) show that presenting a limited number of
alternatives is superior to presenting too many options, when it comes to
human ability to analyze these options and make optimal choices. In order to
mitigate these issues, we postulate the need for developing approaches that
would reduce the number of proposed counterfactuals and support the user in
selecting the most attractive solution.

In this paper, instead of proposing yet another method for generating
counterfactuals, we claim that the already existing methods should be
sufficient to provide a diversified set of explanations. However, the more
challenging problem of selecting a suitable, compromise counterfactual while
taking multiple quality criteria into account is still open. Inspired by the
research on classifier ensembles, which achieve better classification
performance by exploiting the predictions from a diversified set of base
classifiers Kuncheva (2004), we propose to use an ensemble of multiple base
explainers to provide a richer set of counterfactuals, each of which
establishes a certain trade-off between values of different quality measures
(often referred to as criteria). We also put forward an approach to
significantly reduce the number of considered explanations to a smaller and
concise set by constructing a Pareto front, i.e., a subset of explanations
that are not worse than others on at least one criterion. Then we propose to
select a final counterfactual from this front by applying the multiple
criteria Ideal Point Method Steuer (1986); Skulimowski (1990) which does not
require additional preference elicitation from the user, and is
computationally efficient. To sum up, the main contributions of this paper are
as follows:

  1. 1.

Proposal of a new approach, integrating an ensemble of explainers algorithm
with the multiple criteria analysis to select a counterfactual representing a
suitable trade-off between the quality measures.

  2. 2.

Experimental evaluation of the proposed approach, demonstrating that it
provides the best trade-off between different quality measures for a wide
range of user preferences for these criteria.

  3. 3.

Multi-criteria analysis of counterfactuals generated by various methods, which
provides insights into the dominance relationship between them.

##  2 Related Works

Following Wachter et al. (2017), a counterfactual explanation is defined as a
perturbation of the instance $x$, denoted as $x^{\prime}$, that results in a
different prediction from the same black box model $b$, i.e., $b(x)\neq
b(x^{\prime})$.

###  2.1 Counterfactual Explanation Methods

Numerous methods for generating counterfactual explanations have been already
introduced. According to Guidotti (2022), they can be divided into four
categories based on their methodological paradigms. Instance-based explainers
select the most similar examples with a desired class from the dataset (e.g.,
FACE Poyiadzi et al. (2020)). Decision tree approaches approximate the
behaviour of a black box model with a decision tree and exploit its structure
to generate counterfactual explanations (e.g., Tolomei et al. (2017)). The
next approaches optimize a certain loss function by adopting specific
optimization algorithms (e.g., Wachter Wachter et al. (2017), CEM Dhurandhar
et al. (2018), Dice Mothilal et al. (2020), Fimap Chapman-Rounds et al.
(2021), CFProto Van Looveren and Klaise (2021), ActionableRecourse Ustun et
al. (2019)). Heuristic search strategies find counterfactuals through
iterative heuristic choices minimizing the chosen cost function (e.g., Cadex
Moore et al. (2019), GrowingSpheres Laugel et al. (2018)). This taxonomy is
only one of many, however it exhibits different approaches to the process of
obtaining counterfactual explanations. Another thorough review with an
alternative categorization can be found in Verma et al. (2020).

Most of the papers introducing counterfactual generation methods do not report
experiments that compare them to previous methods on data benchmarks. In
general, the field of counterfactual explanations suffers from a lack of
comparative studies examining multiple methods, and the paper Guidotti (2022)
is the rare exception.

Table 1: Quality measures of counterfactual explanations. $x^{\prime}$ is the counterfactual for instance $x\in X$. $neigh_{k}$ is the $k$-th nearest neighbour of $x^{\prime}$ in $X$.  Measure |  Definition
---|---
$Proximity(x,x^{\prime})$ |  $distance(x,x^{\prime})$
$Feasibility(x^{\prime})$ |  $\frac{1}{k}\sum_{i=1}^{k}distance(x^{\prime},neigh_{i})$
$Sparsity(x,x^{\prime})$ |  number of features changed in $x$ to get $x^{\prime}$
$Discriminative\\_$ $Power(x^{\prime})$ |  $\frac{1}{k}\sum_{i=1}^{k}\mathbf{1}[[b(x^{\prime})=b(neigh_{i})]]$
$Instability(x^{\prime})$ |  $dist(x^{\prime},x_{1}^{\prime})$ where $x_{1}^{\prime}$ is a counterfactual obtained for example $x_{1}\in X$ being the closest neighbour of $x$

###  2.2 Most related methods for generating several counterfactual
explanations

So far, only one paper has considered combining multiple methods for the same
data Guidotti and Ruggieri (2021), where the authors studied the committee of
counterfactual explainers. In their proposal base explainers may produce
several explanations which are, then, combined (selected up to the required
number) by optimizing a simple two criteria distance-driven aggregation
function.

The multi-criteria approach to generating a set of counterfactuals has only
been explored in a few papers Dandl et al. (2020); Rasouli and Chieh Yu
(2022). They utilize genetic algorithms to generate a large (tens to hundreds
of explanations) set of non-dominated counterfactual explanations based on
multiple criteria. However, these approaches do not tackle the problem of
reducing the choice overload, and the selection of the best counterfactual
explanation is left to the final user or decision-maker. The needs for
adapting the multi-criteria decision analysis to support such users is also
postulated in Stefanowski (2023).

###  2.3 Quality Measures for Counterfactuals

The research on counterfactual explanations and their psychological analysis
show that they should fulfil some expectations that a human decison-maker
might have. Here we list the most frequently mentioned properties in
literature Guidotti (2022); Wachter et al. (2017): (1) validity \- a
counterfactual $x\textquoteright$ has to change the prediction, i.e. $b(x)\neq
b(x\textquoteright)$; (2) sparsity \- a valid counterfactual should change as
few features as possible; (3) proximity \- a counterfactual should be a result
of the smallest perturbation, i.e. $x\textquoteright$ should be as similar to
original $x$ as possible. It is also postulated that counterfactuals need to
be (4) distributional faithful, i.e. they should be located in feature space
regions that ensure their feasibility / plausibility (as some generation
methods may produce examples out-of-data distribution or with unrealistic
feature values). In order to take into account fairness and real world
utility, many works also introduce (5) actionability \- a counterfactual
should not alter any attributes from $x$ that are sensitive and immutable in
certain scenarios (e.g., changing race in a loan application setting). Other
proposed properties are discussed in Guidotti (2022).

The above-mentioned properties led to defining different quality measures
evaluating either a single counterfactual or a set of counterfactuals. For our
further experiments, we chose the most commonly used measures in the
literature, see their specific definitions in Tab. 1.

In the rest of the paper we use the following notation: $x$ is the original
instance, classified by the black box model $b$; $x\textquoteright$ is the
generated counterfactual that corresponds to $x$; distance \- a distance
between two examples calculated with a chosen metric; neighk \- the $k^{th}$
closest neighbour to the instance $x$ in the training data $X$.

##  3 The proposed multi-criteria approach

We propose a new multi-stage approach that integrates an ensemble of different
methods for generating counterfactuals with a multi-criteria approach for
selecting the counterfactual that provides a compromise solution with respect
to conflicting criteria. It consists of four consecutive steps illustrated in
Fig. 1. Firstly, each explainer included in the ensemble is queried to
generate counterfactuals for a given instance $x$ (Sec. 3.1). Next, all
explanations are combined to form a set of candidate solutions. This resulting
set is filtered to remove invalid and non-actionable instances (Sec. 3.2). In
the third step (Sec. 3.3), we employ the dominance relation to reduce the set
of remaining explanations without loss of quality on any considered criterion.
As the final step, we use the Ideal Point Method to select the best solution
(Sec. 3.4). The pseudocode of the proposed approach can be found in Alg. 1. To
ease the comprehension of the proposed approach, we present an illustrative
example in Sec. 3.5.

Algorithm 1 Pseudocode for the proposed approach

$b\leftarrow$ black-box classifier

$X\leftarrow$ training data

$x\leftarrow$ query instance s.t. $x\in X$

$E\leftarrow$ set of base explainers STEP 1 (Ensemble of Explainers):

$C\leftarrow$ $\emptyset$

for $explainer\in E$ do

$c\leftarrow explainer(x,X,b)$ {run the base explainer}

$C\leftarrow C\cup\\{c\\}$

end for STEP 2 (Enforcement of Validity and Actionability):

for $c$ in $C$ do

if $\neg is\\_valid(c)\lor\neg is\\_actionable(c)$ then

$C\leftarrow C\setminus\\{c\\}$

end if

end for STEP 3 (Filtering dominated solution):

$D\leftarrow\emptyset${empty set of dominated solutions}

for $c$ in $C$ do

for $d\in(C\setminus\\{c\\})$ do

if $d$ is better than $c$ on one criterion and better or equal on all criteria
then

$D\leftarrow D\cup c$

end if

end for

end for

$ND\leftarrow C\setminus D$ {set of non-dominated solutions} STEP 4 (Selection
with Ideal Point)

$p\leftarrow vector()$

for each criterion $i$ do

$p_{i}\leftarrow\max_{c\in ND}c_{i}$

end for

$s\leftarrow\operatorname*{arg\,min}_{c\in ND}distance(c,p)$

return $s$

Figure 1: Visualization of the algorithm steps in our proposed approach.

###  3.1 Constructing an ensemble of explainers

In order to obtain a set of diversified counterfactuals we construct an
ensemble of different methods chosen under the following premises: they are
based on different paradigms and thus generate quite diverse explanations,
they have positive literature recommendations, and their stable open source
implementations are available.

In Sec. 4.1, we list the specific methods used in our ensemble, however we
argue, that our approach is general enough to employ different sets of base
explainers. While some methods may generate few solutions and others produce a
single counterfactual, experiments have shown that none of the examined
methods is superior to others with respect to any of the considered criteria,
see Stepka et al. (2023). This supports our hypothesis that a set of solutions
obtained by using different explanation methods provides a broader and richer
set of possible counterfactuals than searching for a single best method.

###  3.2 Enforcement of validity and actionability constraints

Some of the chosen base explainers may generate counterfactuals which do not
change the black-box prediction to the desired value, and also some generated
solutions may violate actionability constraints. Therefore, in this step we
perform an additional filtering of counterfactuals generated by the ensemble,
i.e. we discard explanations which are not valid or non-actionable.
Actionability is examined with respect to restricted attributes that have to
be distinctly pre-defined for any given dataset.

###  3.3 Filtering of dominated solutions

The ensemble of base explainers produces a large number of counterfactuals
characterized by different and sometimes conflicting quality criteria (see the
discussion of proximity and discriminative power in Sec. 1). The problem of
selecting the best solution is challenging, since the objective comparison of
two explanations that excel on different criteria is impossible and largely
depends on the preferences of the user/decision-maker. Such problems are of
interest to the field of multi-criteria decision-aid (MCDA) Ehrgott (2005),
which deals with sets of alternative solutions/decisions $x$ evaluated by many
criteria $g_{i}(x)$. In brief, for each criterion, the direction of the user’s
preference is defined as increasing (gain criteria) or decreasing (cost
criteria). The values of criteria for considered alternatives may be
contradictory, but some of them are more preferred than others because of the
preference directions. MCDA methods can solve trade-off between them.

This leads us to exploiting the dominance relation Ehrgott (2005) which is
defined as follows. Let’s assume the gain direction of preferences for all
criteria $g(x)$ and consider two alternatives - counterfactuals $x^{\prime}$
and $y^{\prime}$. We say that $x^{\prime}$ dominates $y^{\prime}$, if for each
criterion $i$ holds $g_{i}(x^{\prime})\geq g_{i}(y^{\prime})$, and exists at
least one $i$ for which $g_{i}(x^{\prime})>g_{i}(y^{\prime})$. In other words,
criteria values of $x^{\prime}$ are better or equal than the corresponding
values of $y^{\prime}$. The dominated counterfactuals can be removed from the
set of solutions as they are objectively worse than the non-dominated
alternatives.

Then, our approach constructs Pareto front i.e. it builds a set of all non-
dominated counterfactuals obtained by applying the dominance relation on all
explanations in a given set. In other words, each counterfactual explanation
is examined on whether there exists any other counterfactual that has better
or equal scores on all considered criteria. Only if such examples do not
exist, the counterfactual is non-dominated and therefore included in the
Pareto front. Our experiments show that thanks to exploiting this relation,
the size of the candidate solution set can be significantly reduced, on
average by approx. 80% (see experiments in Sec. 4.2).

###  3.4 Selection of a counterfactual with Ideal Point method

As the final set of non-dominated alternatives on the Pareto front may still
be too large for a user to analyse manually, it necessary to support the
choice of the counterfactual that represents the trade-off best suited to the
user. There exist many MCDA methods that allow this by acquiring the global
model of user preferences for these criteria by interacting with them Ehrgott
(2005). However, we will follow a simpler approach which is, in our opinion,
more suited for our problem and better for carrying out our automatic
experiments.

Note that the criteria that characterize different counterfactuals are quality
measures (e.g., proximity). A typical decision situation considered in MCDA
assumes that the user/decision maker is able to compare the alternatives
basing on the criteria values (i.e. in the feature space). However, in our
case quality measures of counterfactuals are not so intuitive for non-expert
humans to interpret and compare. This also limits the possibility of using
typical interactive MCDA methods to elicit the decision maker’s preferences,
which require accurate assessments about the relative importance of criteria
or comparing different variants usually in the original features.

Therefore, we propose to use the Ideal Point Method, which is a simple and
compute-efficient approach recommended in the literature for the case of
equally important criteria Branke et al. (2008); Skulimowski (1990). We
briefly explain this method below.

  * •

Let $D$ be a set of non-dominated counterfactuals in the Pareto front with $c$
criteria. The ideal solution is artificially created in the criteria space by
selecting the best possible value for every criterion. Assuming that all
criteria $g_{i}(x)$ have an increasing direction of preference (gain), the
ideal point $z=[z_{1},z_{2},..,z_{c}]$ can be formally defined as having
$z_{i}=\max\\{g_{i}(x):x\in D\\}$ for all $i=1,...,c$. Usually $z$ is an
abstract point which do not belong to $D$.

  * •

Then, for each counterfactual $x\in D$, its distance measure to the ideal
point $z$ is computed.

  * •

The closest counterfactual to $z$ is selected as the final best solution.

The Ideal Point method originates from the works on multi-objective
mathematical programming, proposed in the previous century Steuer (1986)222It
can be easily extended to use other ways of calculating distances with the
hyper-plane connecting the ideal point with the anti-ideal / nadir point
Ehrgott and Tenfelde-Podehl (2003) (which we will consider in Sect. 4.4). It
has been further extended for different scalarized distances with criteria
weights or to so-called reference points, see discussions in Ehrgott (2005);
Skulimowski (1990). Nevertheless, in our paper we want to show that even the
simplest version is sufficient to demonstrate the usefulness of MCDA approach
in the proposal of the ensemble of explainers.

###  3.5 Approach walkthrough with a toy example

In order to facilitate the understanding of the proposed method, we will go
step by step through the computations for the following instance taken from
the Adult333see Sec. 4.1 for dataset details dataset: x = {age: 24,
education.num: 10, capital.gain: 0, capital.loss: 0, hours.per.week: 30,
workclass: Self-emp-not-inc, marital.status: Never-married, occupation: Prof-
specialty, race: Asian-Pac-Islander, sex: Male, native.country: United-States,
income $>$50K }.

First, we run all the explainers from the ensemble to construct
counterfactuals. Assuming the set of methods used in our experiments (see
experimental setup in section 4.1), 82 counterfactuals are returned. We
provide the full list of returned counterfactuals and further details in the
online appendix444https://www.cs.put.poznan.pl/mlango/publications/amcs24.pdf.

We then feed these counterfactuals into the next step of our approach, which
focuses on enforcing validity and actionability. The validity filter
eliminates counterfactuals that do not change the predicted class from $>50K$
to $\leq 50K$, reducing the candidate set by 5. Subsequently, actionability
enforcement excludes all the alternatives that alter the values of non-mutable
features, in this case: race, sex, and native.country. This actionability test
removes 18 additional counterfactuals, reducing the total number of candidates
to 59. Nine of the removed counterfactuals suggested changing the person’s
native country from the United States to other countries such as France, the
Philippines, or China. All but one of the non-actionable counterfactuals
suggested changing the person’s race, and eight of them suggested changing
both race and country of birth. This demonstrates the need for actionability
and validity testing.

Figure 2: An example demonstrating the application of dominance relations and
the Ideal Point method. Note the optimization directions for Proximity and
Feasibility are min, and for DiscriminativePower \- max.

In the next step, the multi-criteria analysis of the remaining 59
counterfactuals is already in progress. Initially, we apply the dominance
relation to reduce the candidate set to the Pareto front, which consists of 13
alternatives, discarding 46 dominated alternatives. This means that we remove
all counterfactuals with criteria values objectively worse on all criteria
than a set of other counterfactuals. We visualize this process in Fig. 2,
where dominated alternatives are denoted with blue squares, and alternatives
forming the Pareto front are marked with orange dots.

Subsequently, we calculate the coordinates of the Ideal Point (marked with a
red ’x’ in the figure) from the Pareto front. The coordinates of the Ideal
Point corresponds to the best criteria values obtained by any of the
considered alternatives. In this case, these values are 0.04 for Proximity,
0.11 for Feasibility, and 1 for Discriminative Power.

The final step involves calculating the distance between the alternatives from
the Pareto front and the Ideal Point, and selecting the closest one (indicated
by the dotted red line) as the final counterfactual. The distance is
calculated using the Euclidean metric, preceded by feature min-max
normalization. In analysed example, the selected counterfactual is: c = {age:
24.0, education.num: 10.0, capital.gain: 17327.0, capital.loss: 0.0,
hours.per.week: 30.0, workclass: Self-emp-not-inc, marital.status: Never-
married, occupation: Prof-specialty, race: Asian-Pac-Islander, sex: Male,
native.country: United-States}, and it has scores of 0.173 for Proximity,
0.962 for Feasibility, and 0.11 for Discriminative Power.

Table 2: Characteristics of datasets. From left: size \- total number of instances, test size \- the size of holdout test set, continuous/categorical \- number of continuous/categorical features, immutable \- names of features which were designated as non-actionable. Dataset | size | test size | continuous | categorical | immutable
---|---|---|---|---|---
Adult | 32561 | 250 | 5 | 6 | race, sex, native-country
German | 1000 | 100 | 7 | 13 | foreign-worker
Compas | 7214 | 250 | 7 | 3 | age, sex, race, charge-degree
Fico | 10459 | 250 | 23 | 0 | external-risk-estimate

##  4 Experimental evaluation

The aims of experiments are to assess the utility of the proposed approach and
to compare the quality of counterfactuals obtained by different methods.

Firstly, we analyse Pareto front and utility of different steps in our
approach. To investigate if constructing an ensemble is justified, we examine
the impact, that each step has on the size of a set of candidate
counterfactual explanations, as well as the contribution of each of the
methods incorporated into the ensemble (Sec. 4.2).

Then, we analyse the results obtained by different explanation methods and our
ensemble, by comparing them on different quality metrics (Sec. 4.3).

We also study the impact of individual components of our approach on the final
result (Sec 4.4).

Finally, using a utility function model of user preferences, we verify whether
returned counterfactuals represent useful trade-offs between considered
quality criteria (Sec. 4.5).

In order to ensure reproducibility and allow future benchmarking we publicly
release the code used for experiments555https://github.com/istepka/MCSECE.

###  4.1 Experimental setup

Table 3: Comparison of the explainers used in the ensemble according to their
average number of generated counterfactuals per instance per dataset. The
columns, listed from left to right, indicate the number of counterfactuals
left after applying consecutive steps from our approach: all (no filters
applied), val (after applying the validity requirement), act (after applying
both the validity and actionability requirements), front (after exploiting the
dominance relation), and ideal (after using the Ideal Point method for
selection). The best results are bolded, the second best are underlined and
the third best are in italics

Dataset | Adult | German
---|---|---
| all | val | act | front | ideal | all | val | act | front | ideal
Dice | 20.00 | 20.00 | 20.00 | 0.52 | 0.16 | 20.00 | 20.00 | 20.00 | 0.94 | 0.33
FACE | 10.00 | 9.68 | 8.16 | 3.48 | 0.69 | 10.00 | 9.94 | 0.37 | 4.30 | 0.01
Cadex | 6.62 | 6.47 | 6.47 | 1.18 | 0.34 | 13.99 | 11.50 | 11.50 | 2.64 | 0.28
Fimap | 6.00 | 4.70 | 4.70 | 0.37 | 0.07 | 6.00 | 5.02 | 3.04 | 0.57 | 0.09
Wachter | 9.60 | 5.03 | 5.03 | 1.54 | 0.02 | 10.00 | 7.15 | 7.15 | 1.40 | 0.14
CEM | 1.00 | 0.66 | 0.66 | 0.26 | 0.00 | 1.00 | 1.00 | 1.00 | 0.09 | 0.43
CFProto | 7.63 | 7.57 | 0.78 | 0.06 | 0.01 | 5.63 | 3.98 | 2.25 | 1.48 | 0.08
GrowingSpheres | 20.00 | 15.54 | 15.54 | 0.14 | 0.01 | 20.00 | 10.54 | 10.54 | 1.00 | 0.02
ActionableRecourse | 0.40 | 0.10 | 0.10 | 0.20 | 0.01 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00

Dataset | Compas | Fico
---|---|---
| all | val | act | front | ideal | all | val | act | front | ideal
Dice | 20.00 | 20.00 | 20.00 | 1.83 | 0.35 | 20.00 | 20.00 | 20.00 | 2.77 | 0.33
FACE | 10.00 | 9.93 | 0.45 | 0.42 | 0.14 | 10.00 | 9.94 | 0.37 | 0.37 | 0.01
Cadex | 6.00 | 4.78 | 4.74 | 1.08 | 0.19 | 13.99 | 11.50 | 11.50 | 3.72 | 0.28
Fimap | 6.00 | 5.58 | 3.30 | 1.26 | 0.33 | 6.00 | 5.02 | 3.04 | 1.13 | 0.09
Wachter | 10.00 | 6.07 | 6.07 | 1.03 | 0.03 | 10.00 | 7.15 | 7.15 | 1.65 | 0.14
CEM | 1.00 | 1.00 | 1.00 | 0.33 | 0.07 | 1.00 | 1.00 | 1.00 | 0.30 | 0.04
CFProto | 5.75 | 3.65 | 0.73 | 0.13 | 0.00 | 5.63 | 3.98 | 2.25 | 0.95 | 0.08
GrowingSpheres | 20.00 | 8.80 | 8.80 | 1.73 | 0.06 | 20.00 | 10.54 | 10.54 | 0.71 | 0.02
ActionableRecourse | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00

Experiments were conducted on four widely adopted datasets in the related
literature, namely: Adult, German, Compas and Fico, which characteristics can
be found in Tab. 2. For every dataset, we defined a set of immutable
attributes which were later used to evaluate the actionability of provided
explanations. The information about immutability of certain attributes was
passed as an additional input to all methods capable of handling it. Note that
these subsets could be different depending on the perspective of a particular
stakeholder.

As a black-box classification method, we employed an artificial neural network
consisting of two hidden layers with 16-128 neurons in each layer. The number
of neurons was optimized for each dataset separately to maximize accuracy on
the validation set. We used ReLU activation and dropout between layers. More
details of its topology and hyperparameters are provided in the electronic
appendix.

To compute the measures described in Sec. 2.3, it is necessary to select a
distance function. We chose the HEOM distance Wilson and Martinez (1997) due
to its ability to handle both nominal and continuous variables than other
measures.

The evaluated ensemble uses the collection of 9 popular and diversified
counterfactual generation algorithms as base explainers, namely Wachter
Wachter et al. (2017), CEM Dhurandhar et al. (2018), Dice Mothilal et al.
(2020), Fimap Chapman-Rounds et al. (2021), Cadex Moore et al. (2019), FACE
Poyiadzi et al. (2020), CFProto Van Looveren and Klaise (2021),
ActionableRecourse Ustun et al. (2019) and GrowingSpheres Laugel et al.
(2018). In addition to diversity, we were also guided by their popularity in
related works and the availability of their implementations. We used the
following open source libraries: CARLA Pawelczyk et al. (2021), ALIBI Klaise
et al. (2021), CFEC Falbogowski et al. (2022). The methods were mostly used
with default parameters in their implementations, however, to construct a more
extensive set of possible explanations, we exploited the possibilities of
generating multiple counterfactuals from these methods.

To obtain several counterfactuals from some of the methods, we apply different
strategies, because only Dice natively supports generating a set of
explanations (in our case $k=20$).

The first adopted strategy involves random sampling of counterfactuals
discovered during the optimization process, but not selected as the final
solution by the method. Therefore, it not only gathers the explanation that
the method ultimately selects, but also incorporates randomly sampled
counterfactuals discovered during optimization that may perform better on some
criteria that the method does not directly optimize. We apply this strategy to
CFProto ($k=10$) and Wachter ($k=10$).

The second strategy is to restart the method with different set of
hyperparameters to slightly change the optimization process and obtain
different explanation. We use this strategy for GrowingSpheres ($k=20$
restarts with different random seeds), FACE ($k=10$ restarts with different
random seeds), Cadex ($k=15$ different numbers of features to change ranging
from 1 to 14), Fimap ($k=7$ different combinations of parameters for the
objective function666 The following combinations of (Gumbel-softmax
temperature $\tau$, L1 regularization, L2 regularization) were applied: (0.1,
0.001, 0.01),(0.1, 0.05, 0.5),(0.2, 0.01, 0.1),(0.2, 0.08, 0.8),(0.5, 0.001,
0.01),(0.5, 0.01, 0.5)).

While selecting the final counterfactual with our approach, we analysed three
criteria: proximity, feasibility and discriminative power. Recall that in MCDA
criteria must form a coherent family of diverse views on the problem. Indeed,
these three criteria were relatively poorly correlated in our preliminary
experiments Stepka et al. (2023). As a distance function for the Ideal Point
method, we considered Manhattan distance ($L_{1}$), Euclidean distance
($L_{2}$) and Chebyshev distance($L_{\infty}$) (following literature such as
Branke et al. (2008); Skulimowski (1990)).

Table 4: The results obtained for German dataset. The best results are bolded, the second best are underlined and the third best are in italics. Method | prox $\downarrow$ | feas $\downarrow$ | dpow $\uparrow$ | spars $\downarrow$ | instab $\downarrow$ | cover $\uparrow$ | act $\uparrow$ | rank $\downarrow$
---|---|---|---|---|---|---|---|---
Dice | 1.69 | 3.92 | 0.44 | 1.93 | 4.15 | 1.00 | 1.00 | 3.14
FACE | 5.05 | 1.91 | 0.60 | 8.12 | 3.82 | 1.00 | 0.98 | 3.14
Cadex | 1.38 | 3.74 | 0.41 | 2.64 | 3.87 | 0.97 | 0.97 | 5.43
Fimap | 6.85 | 3.01 | 0.60 | 9.91 | 3.71 | 0.97 | 0.97 | 4.57
Wachter | 11.67 | 7.29 | 0.64 | 14.65 | 5.91 | 0.37 | 0.37 | 5.14
CEM | 0.62 | 4.18 | 0.31 | 2.15 | 3.99 | 0.13 | 0.13 | 7.00
CFProto | 3.56 | 4.40 | 0.48 | 4.79 | 4.53 | 0.99 | 0.91 | 5.29
GrowingSpheres | 7.65 | 5.79 | 0.60 | 10.73 | 5.42 | 1.00 | 1.00 | 2.71
ActionableRecourse | 1.01 | 3.55 | 0.44 | 1.39 | 3.60 | 0.23 | 0.23 | 6.29
random selection | 4.39 | 3.95 | 0.50 | 6.28 | 4.61 | 1.00 | 0.98 | 6.86
our approach (Manhattan) | 3.83 | 2.15 | 0.85 | 6.06 | 3.50 | 1.00 | 1.00 | 1.86
our approach (Euclidean) | 3.21 | 2.46 | 0.80 | 4.99 | 3.68 | 1.00 | 1.00 | 2.00
our approach (Chebyshev) | 2.90 | 2.70 | 0.74 | 4.38 | 3.71 | 1.00 | 1.00 | 2.14
Table 5: The results obtained for Adult dataset. Method | prox $\downarrow$ | feas $\downarrow$ | dpow $\uparrow$ | spars $\downarrow$ | instab $\downarrow$ | cover $\uparrow$ | act $\uparrow$ | rank $\downarrow$
---|---|---|---|---|---|---|---|---
Dice | 1.03 | 0.77 | 0.37 | 1.65 | 1.13 | 1.00 | 1.00 | 3.00
FACE | 0.98 | 0.90 | 0.36 | 1.92 | 1.10 | 0.10 | 0.10 | 3.43
Cadex | 0.20 | 0.30 | 0.17 | 2.27 | 0.65 | 0.99 | 0.99 | 4.86
Fimap | 2.12 | 0.35 | 0.59 | 5.75 | 1.17 | 0.99 | 0.99 | 4.00
Wachter | 4.36 | 1.23 | 0.84 | 7.76 | 3.07 | 0.52 | 0.20 | 5.29
CEM | 0.13 | 0.32 | 0.17 | 1.16 | 0.67 | 0.66 | 0.66 | 6.14
CFProto | 1.45 | 1.13 | 0.25 | 7.00 | 2.97 | 0.98 | 0.06 | 6.14
GrowingSpheres | 2.87 | 1.39 | 0.47 | 6.17 | 1.70 | 0.99 | 0.99 | 4.14
ActionableRecourse | 1.14 | 0.10 | 0.70 | 3.72 | 0.56 | 1.00 | 0.84 | 6.57
random selection | 1.55 | 0.81 | 0.38 | 3.56 | 1.17 | 1.00 | 0.88 | 3.86
our approach (Manhattan) | 1.02 | 0.17 | 0.94 | 3.34 | 0.63 | 1.00 | 1.00 | 1.86
our approach (Euclidean) | 0.99 | 0.21 | 0.93 | 3.22 | 0.63 | 1.00 | 1.00 | 2.00
our approach (Chebyshev) | 0.96 | 0.26 | 0.89 | 2.97 | 0.66 | 1.00 | 1.00 | 2.14
Table 6: The results obtained for Compas dataset. Method | prox $\downarrow$ | feas $\downarrow$ | dpow $\uparrow$ | spars $\downarrow$ | instab $\downarrow$ | cover $\uparrow$ | act $\uparrow$ | rank $\downarrow$
---|---|---|---|---|---|---|---|---
Dice | 0.93 | 0.80 | 0.34 | 1.71 | 1.33 | 1.00 | 1.00 | 3.00
FACE | 0.53 | 0.04 | 0.69 | 3.55 | 0.15 | 1.00 | 0.07 | 4.14
Cadex | 0.29 | 0.23 | 0.15 | 2.72 | 0.36 | 0.98 | 0.97 | 5.43
Fimap | 0.52 | 0.11 | 0.69 | 3.53 | 0.17 | 0.99 | 0.58 | 5.00
Wachter | 0.69 | 0.12 | 0.73 | 2.92 | 0.36 | 0.67 | 0.67 | 5.00
CEM | 0.33 | 0.32 | 0.29 | 1.57 | 0.38 | 1.00 | 1.00 | 3.14
CFProto | 0.91 | 0.21 | 0.28 | 3.17 | 0.41 | 0.54 | 0.13 | 6.29
GrowingSpheres | 0.29 | 0.19 | 0.18 | 3.09 | 0.32 | 0.80 | 0.80 | 5.57
ActionableRecourse | 0.07 | 0.32 | 0.89 | 1.00 | 0.66 | 0.00 | 0.00 | 5.29
random selection | 0.63 | 0.37 | 0.40 | 2.74 | 0.61 | 1.00 | 0.70 | 3.86
our approach (Manhattan) | 0.54 | 0.12 | 0.87 | 2.40 | 0.28 | 1.00 | 1.00 | 2.00
our approach (Euclidean) | 0.55 | 0.14 | 0.86 | 2.45 | 0.28 | 1.00 | 1.00 | 2.14
our approach (Chebyshev) | 0.55 | 0.17 | 0.84 | 2.44 | 0.30 | 1.00 | 1.00 | 2.29
Table 7: The results obtained for Fico dataset. Note that ActionableRecourse method is missing, as it failed to provide any valid counterfactual. Method | prox $\downarrow$ | feas $\downarrow$ | dpow $\uparrow$ | spars $\downarrow$ | instab $\downarrow$ | cover $\uparrow$ | act $\uparrow$ | rank $\downarrow$
---|---|---|---|---|---|---|---|---
Dice | 1.11 | 2.15 | 0.38 | 1.88 | 2.53 | 1.00 | 1.00 | 3.00
FACE | 2.34 | 0.82 | 0.70 | 17.88 | 1.78 | 1.00 | 0.03 | 3.57
Cadex | 0.92 | 1.72 | 0.38 | 7.66 | 2.04 | 1.00 | 1.00 | 3.14
Fimap | 1.55 | 1.78 | 0.62 | 16.01 | 1.87 | 0.98 | 0.62 | 4.71
Wachter | 6.66 | 3.50 | 0.81 | 18.39 | 6.45 | 0.49 | 0.49 | 4.71
CEM | 1.12 | 2.08 | 0.50 | 5.80 | 2.47 | 1.00 | 1.00 | 2.71
CFProto | 0.82 | 1.53 | 0.35 | 10.82 | 1.76 | 0.58 | 0.39 | 6.29
GrowingSpheres | 1.44 | 1.90 | 0.35 | 16.48 | 2.39 | 0.97 | 0.97 | 5.29
random selection | 1.30 | 1.84 | 0.40 | 9.67 | 2.21 | 1.00 | 0.84 | 3.86
our approach (Manhattan) | 0.87 | 1.51 | 0.60 | 7.33 | 1.89 | 1.00 | 1.00 | 2.57
our approach (Euclidean) | 0.90 | 1.59 | 0.63 | 7.48 | 1.93 | 1.00 | 1.00 | 2.14
our approach (Chebyshev) | 0.99 | 1.66 | 0.63 | 7.11 | 2.03 | 1.00 | 1.00 | 2.14

###  4.2 Analysis of the Pareto front of counterfactuals generated by the base
explainers in the ensemble

In the first experiment, we take a closer look at the degree of base
explainers’ contribution to the Pareto front. For each dataset and base
explainer method, we computed the average number of counterfactuals generated
for an instance (all), the number of valid counterfactuals, i.e. those that
change the model’s prediction (val), the number of actionable and valid
counterfactuals (act), the number of non-dominated, valid, actionable
counterfactuals on the Pareto front (front) and finally the percentage of
cases for which the counterfactual generated by a given method was selected as
the final answer (ideal). The results are reported in Tab. 3 and some
additional data visualizations are provided in the appendix.

Results show, that there is no single method that is superior to others
considered in the experiments. Some of the methods clearly contribute much
more frequently to the Pareto front, but there is no method which contribution
is negligible on all examined datasets. Contribution to the Pareto front can
be treated as a good indicator of the performance of the method across
different measures, as it shows that counterfactuals generated from some
methods dominate others on all quality measures. Building on that we justify
the utility of incorporating all these methods into the ensemble, as all of
them produce best explanations, but with differing frequencies.

The further analysis indicates, that all steps of our approach eliminate many
counterfactuals. First, enforcing validity constraints reduces the number of
considered candidates by 17%. Second, examining actionability eliminates 16%
of examples from previous step. Third, the use of dominance relation reduces
the remaining set by another 83%. Finally, the Ideal Point Method selects one
compromise counterfactual from the remaining set of explanations. By employing
consecutive steps of or approach, with an exclusion of the last one, it
shrinks the original set of explanations, without the loss of quality, by on
average 88%.

###  4.3 Evaluating counterfactuals with different quality measures

In the second experiment, we compare the performance of the proposed approach
with other methods for generating counterfactuals. The quality of the
generated counterfactual explanations is evaluated using a wide spectrum of
measures used in the related works: proximity (prox), feasibility (feas),
discriminative power (dpow), sparsity (spars), instability (instab), and
actionability (act) – all of them were discussed in Sec. 2.3. Additionally, to
further assess the reliability of the methods in finding counterfactuals, we
report the coverage (cov) metric, which represents the ratio of instances for
which a counterfactual is found. The results of experiments for German, Adult,
Compas, Fico datasets can be found in Tables 4, 5, 6 and 7, respectively.

Among the methods under consideration, the proposed approach was the only one
that was always able to generate an actionable counterfactual for all
instances of tested datasets. Looking at the remaining five quality aspects
(other than actionability and coverage), the proposed approach rarely obtains
the highest score, however, for the vast majority of cases it obtains one of
the top three results. This was expected since our method looks for a trade-
off between multiple quality measures, therefore it is not surprising that in
the individual ranking for each measure it may not obtain superior results.

We also ranked the data for each quality measure and computed the average rank
for each method (the lower, the better) – the results can be observed in the
last column of Tables 4\- 7. Taking all the metrics into account, the proposed
approach always achieves the best (lowest) rank for all datasets under study.
The lowest rank for Adult, German and Compas datasets is achieved by the
variant of our approach employing Manhattan distance. Only for the Fico
dataset the order of three best methods is different. Nevertheless, for all
datasets included in the experiments, variants of our approach take
consistently best three ranks, meaning that they offer the best compromise
between all seven considered quality measures.

As a form of ensemble baseline, we also report the results of the ensemble
that includes all the base explainers of the proposed method, but chooses the
final counterfactual at random (random selection) without employing our
algorithm. This ensemble was never better than any of the three tested
variants of our approach for any dataset and any quality measure,
demonstrating that the performance of our ensemble is a result of choosing an
appropriate final counterfactual with multi-criteria analysis (i.e. applying
dominance relation and Ideal Point Method selection) rather than just using an
ensemble of different methods.

Regarding the comparison of different variants of our method employing
different distance measures, the differences between the obtained scores are
usually very small (except for the Sparsity on the German dataset, where the
difference between the extreme scores is 1.68). The variant employing
Manhattan distance obtains slightly lower average rank for most datasets,
therefore we choose this variant to represent our method in the next
experiment.

###  4.4 Analyzing the impact of the elements in our approach

In this section, we provide a concise analysis of how the components of our
approach influence the selection of final counterfactuals and their
corresponding evaluation measures. The experimental data used for this
analysis is available in the appendix.

The first element in our approach emphasizes validation and actionability
enforcement. Our experiments demonstrate the critical role this element plays
in achieving fully actionable and valid counterfactuals. Without it, the
scores for the Validity and Actionability criteria range from 24% to 54% and
78% to 98%, respectively (varies by dataset). Such performance falls short of
suitability for most real-world scenarios, proving the usefulness of this
operation.

The second element in our approach involves applying the dominance relation to
filter out dominated alternatives. Omitting this component does not lead to a
decrease in the values of various quality measures. This is because, in our
approach, the Ideal Point selects the counterfactual closest to the (0,0,0)
point in the Proximity-Feasibility-(1-DiscriminativePower)777For simplicity,
we invert the DiscriminativePower criterion to have min optimization
direction. min-max normalized criteria space, which is attained through min-
max normalization performed on the dataset. Consequently, the dominance
relation do not enhance the performance of the Ideal Point method.
Nevertheless, removing dominated, i.e. worse, solutions is necessary for
considering other multi-criteria methods. Moreover, as we have already shown
in experiments (see Table 3), this step significantly reduced the number of
solutions.

The final component of our approach involves selecting the counterfactual by
means of the Ideal Point method. On average, this method yields significantly
better-scoring counterfactuals compared to random selection from the Pareto
front. An interesting comparison lies in contrasting the Ideal Point method
with the simple unweighted sum
($s=\text{Proximity}+\text{Feasibility}+(1-\text{Discriminative Power})$) of
the criteria scores. Our experiments (see the appendix) reveal that the
variant employing Manhattan distance achieves the best average scores across
the examined datasets. This variant is equivalent to the unweighted sum
($s=c_{\text{Manhattan}}$), as, in the previously mentioned min-max normalized
criteria space, the Ideal Point coordinates are $p=(0,0,0)$. Therefore, the
distance to the Ideal Point
$c_{\text{Manhattan}}=|p_{0}-\text{Proximity}+p_{1}-\text{Feasibility}+p_{2}-(1-\text{Discriminative
Power})|$ is just a summation of scores on all criteria, equivalent to the
unweighted sum: $s=c_{\text{Manhattan}}$. It is worth noting that other
variants of our approach using Euclidean or Chebyshev distance are not
equivalent and select different alternatives.

While this paper primarily utilizes the simplest multi-criteria selection
method, we also conducted preliminary experiments (included in the appendix)
with a slightly more advanced selection method based on distance to the nadir-
ideal plane Ehrgott and Tenfelde-Podehl (2003), showing slightly superior
results compared to the unweighted sum selection. This underscores the value
of employing multi-criteria selection methods. Even this simple distance
methods are also useful for possible further extensions of the methods towards
interactive dialogue with the decision-maker.

Figure 3:  The barycentric plots depicting the best method for a given dataset
according to the utility functions with different weights assigned to quality
criteria. The datasets are: German (upper-left), Adult (upper-right), Compas
(lower-left), Fico (lower-right).

###  4.5 Using user preference models to evaluate selected trade-offs between
different quality measures

The main aim of our work is to generate a counterfactual for a given instance,
which represents a suitable trade-off between various aspects of explanation
quality. Let us recall that in our approach we do not use criterion weights
due to their difficulty in estimating by humans. However, for the purpose of
examining possible trade-off criteria in potential models of decision-makers’
preferences, we decided to experimentally simulate a simple utility function
model, where we analyzed the impact of all possible weight configurations.
Since an objective comparison of different non-dominated trade-offs is
impossible without additional information about user preferences towards
optimizing particular quality criteria, we employ a simple mathematical model
of user preference to verify the utility of counterfactuals under all possible
configuration of preferences. More concretely, we model the utility of an
explanation as a weighted sum of three selected quality criteria:

$\begin{split}U(x^{\prime})=w_{p}\cdot&\textrm{Proximity}(x^{\prime})\\\
&+w_{d}\cdot\textrm{DiscriminativePower}(x^{\prime})\\\
&+w_{f}\cdot\textrm{Feasibility}(x^{\prime})\end{split}$ (1)

where $w_{p},w_{d},w_{f}\geq 0$, $w_{p}+w_{d}+w_{f}=1$ are parameters which
control the importance of individual quality measures for a potential user. It
is assumed that the user should select the solution which maximizes the
utility function.

Since the space of all possible utility functions has only three parameters
($w_{p},w_{d},w_{f}$) which sum up to 1, it can be easily visualized on a
2-dimensional plot (see Fig. 3) with the Barycentric coordinate system. The
barycentric plot takes the form of an equilateral triangle with each vertex
associated with one weight of the utility function. Each point inside the
triangle represents one possible user utility function, i.e. one possible
setup of $w_{p},w_{d},w_{f}$ weights. For instance, a point at the vertex
corresponding to proximity ($w_{p}$) represents the utility function with
$w_{p}=1$ and $w_{d}=w_{f}=0$. A point in the middle of the edge connecting
the vertices corresponding to proximity ($w_{p}$) and fidelity ($w_{f}$)
represents the utility function with $w_{p}=w_{f}=0.5$ and $w_{d}=0$. Finally,
the central point in the middle of the triangle corresponds to a user having
equal preferences for all quality criteria ($w_{p}=w_{d}=w_{f}=\frac{1}{3}$).

We computed the utilities of the counterfactuals returned by all the methods
under study using utility functions for all888More precisely, we evaluated a
grid of 136 weight combinations, evaluating weight values from 0 to 1 with a
step of $\frac{1}{16}$. possible combinations of weights values. Later, we
verified which counterfactual method would be selected as the preferred one by
a potential user with such preferences. The results of this experiment are
visualized on the Fig. 3.

For the Adult dataset, despite being uninformed about user preferences and
always selecting the same counterfactual with the Ideal Point method, our
proposed approach would be selected as the best one according to approximately
85% of all possible utility functions. Only when the user has a strong
preference towards one criterion, the proposed approach loses to CADEX on
proximity and to FACE on feasibility. For the user solely interested in
discriminative power the counterfactuals produced by Fimap would be the most
appropriate. Similar observations can be made for the German and Compas
datasets, where the results of our method constitute the best trade-off for
all users who are not too strongly biased towards one particular criterion.

Only for the Fico dataset, the counterfactuals produced by FACE seem to
represent a good trade-off between Feasibility and Discriminative Power for
many cases. However, it is important to note that for this dataset FACE
generates actionable explanations only for 3% of examples (see Tab. 7).
Therefore, this result does not demonstrate inefficiency of our selection
procedure since we automatically discard all non-actionable explanations
beforehand. Nevertheless, our proposed method achieve good trade-offs for
users who are more inclined towards obtaining explanations similar to the
instance being explained (proximity) but who are also interested in reasonable
feasibility and discriminative power. In other words, unless decision-maker is
interested solely in counterfactual explanations that score high only on one
criterion, our proposed method provides more preferred counterfactuals.

##  5 Conclusions and Future Works

The main message of our work is to promote the use of multi-criteria decision
analysis (MCDA) to select contractual explanations for predictions made by
black-box machine learning models. The proposed approach has at least two
original contributions to current research. Firstly, we propose to construct
an ensemble of various explanatory methods that are effective in generating a
fairly large (in our experiments, about 80-90) set of diverse solutions.
Secondly, we employ further multi-criteria analysis to first, reduce the
number of considered counterfactuals to only non-dominated explanations, and
thirdly, to support the selection of a solution that offers a compromise
between the values of the considered evaluation measures.

In this work, we have consciously chosen relatively simple and well-known MCDA
proposals: (1) the use of the dominance relation - which is the only approach
that is fully objective to filter out the worse evaluated solutions; (2) the
Ideal Point method - which is also a no preference approach (i.e., it does not
require any acquisition of user preferences on the relative importance of
criteria – weights or comparisons of alternatives). It is also computationally
simple to run automated experiments.

Additional experiments (Sec 4.4) also showed that all steps of our approach
are essential. Moreover, even a relatively simple multi-criteria ideal point
method leads to good choices of counterfactuals and can be easily further
extended, e.g. to the ideal-nadir version.

Despite the simplicity of these multi-criteria methods, we believe that the
presented experiments demonstrated the utility of our approach. Indeed, the
selected counterfactuals are competitive with the solutions offered by the
best of the single methods used, which often optimize only one criterion.
Furthermore, our additional experiments simulating the utility model of a
potential decision maker show that when they do not have a strong preference
for a single criterion, the proposed multi-criteria approach is highly
beneficial and provides a good trade-off between criteria.

Furthermore, our comparative study reveals that no method is superior to
others in all criteria. Therefore, we conclude that more attention should be
given to comparing different counterfactual generation methods using multi-
criteria analysis to highlight the various trade-offs made by these methods.

We also argue, that looking at explanations from different perspectives should
be studied more extensively, and we believe that multi-criteria analysis is
the natural choice for this type of investigation. As a next step, we suggest
that research should focus on whether the proposed framework aligns with the
human perspective, and whether humans make trade-offs between criteria when
selecting the best explanations or whether they prefer only one of them.
Moreover, it is worth considering adaptations of interactive, dialogue multi-
criteria selection methods, which will be the subject of further research.

## Acknowledgments and Disclosure of Funding

The research has been partially supported by 0311/SBAD/0743, 0311/SBAD/0740
PUT University grants and TAILOR, a project funded by EU Horizon 2020 research
and innovation programme under GA no. 952215.

## References

  * Bodria et al. [2021] Francesco Bodria, Fosca Giannotti, Riccardo Guidotti, Francesca Naretto, Dino Pedreschi, and Salvatore Rinzivillo.  Benchmarking and Survey of Explanation Methods for Black Box Models.  _arXiv e-prints_ , 2021.
  * Branke et al. [2008] Kalyanmoy Branke, Jurgen snd Deb, Kaisa Miettinen, and Roman Slowiński.  _Multiobjective optimization: Interactive and evolutionary approaches_ , volume 5252.  Springer Science & Business Media, 2008.
  * Chapman-Rounds et al. [2021] Matt Chapman-Rounds, Umang Bhatt, Erik Pazos, Marc-Andre Schulz, and Konstantinos Georgatzis.  Fimap: Feature importance by minimal adversarial perturbation.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 11433–11441, May 2021.
  * Dandl et al. [2020] Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl.  Multi-objective counterfactual explanations.  In _Parallel Problem Solving from Nature – PPSN XVI_ , pages 448–469. Springer International Publishing, 2020.
  * Dhurandhar et al. [2018] Amit Dhurandhar, Pin-Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das.  Explanations based on the missing: Towards contrastive explanations with pertinent negatives.  31, 2018.
  * Ehrgott [2005] Matthias Ehrgott.  _Multicriteria Optimization_.  Springer-Verlag, 2005.
  * Ehrgott and Tenfelde-Podehl [2003] Matthias Ehrgott and Dagmar Tenfelde-Podehl.  Computation of ideal and nadir values and implications for their use in mcdm methods.  _European Journal of Operational Research_ , 151(1):119–139, 2003.  ISSN 0377-2217.
  * Falbogowski et al. [2022] Maciej Falbogowski, Jerzy Stefanowski, Zuzanna Trafas, and Adam Wojciechowski.  The impact of using constraints on counterfactual explanations.  _Proceedings of the 3rd Polish Conference on Artificial Intelligence, PP-RAI 2022_ , pages 81–84, 2022.
  * Förster et al. [2021] Maximilian Förster, Philipp Hühn, Mathias Klier, and Kilian Kluge.  Capturing users’ reality: A novel approach to generate coherent counterfactual explanations.  In _Proceedings of the 54th Hawaii International Conference on System Sciences_ , 2021.
  * Guidotti [2022] Ricardo Guidotti.  Counterfactual explanations and how to find them: literature review and benchmarking.  _Data Mining and Knowledge Discovery_ , 2022.
  * Guidotti and Ruggieri [2021] Riccardo Guidotti and Salvatore Ruggieri.  Ensemble of counterfactual explainers.  In _International Conference on Discovery Science_ , pages 358–368. Springer, 2021.
  * Inbar et al. [2011] Yoel Inbar, Simona Botti, and Karlene Hanko.  Decision speed and choice regret: When haste feels like waste.  _Journal of Experimental Social Psychology_ , 2011.
  * Iyengar and Lepper [2000] S.S. Iyengar and M. R. Lepper.  When choice is demotivating: Can one desire too much of a good thing?  _Journal of Personality and Social Psychology_ , 2000.
  * Klaise et al. [2021] Janis Klaise, Arnaud Van Looveren, Giovanni Vacanti, and Alexandru Coca.  Alibi explain: Algorithms for explaining machine learning models.  _Journal of Machine Learning Research_ , pages 1–7, 2021.
  * Kuncheva [2004] Ludmila I Kuncheva.  _Combining Pattern Classifiers: Methods and Algorithms_.  Wiley-Interscience, 2004.
  * Laugel et al. [2018] Thibault Laugel, Marie-Jeanne Lesot, Christophe Marsala, Xavier Renard, and Marcin Detyniecki.  Comparison-based inverse classification for interpretability in machine learning.  In _Information Processing and Management of Uncertainty in Knowledge-Based Systems. Theory and Foundations_ , pages 100–111. Springer International Publishing, 2018.  ISBN 978-3-319-91473-2.
  * Mertes et al. [2022] Silvan Mertes, Tobias Huber, Katharina Weitz, Alexander Heimerl, and Elisabeth André.  Ganterfactual—counterfactual explanations for medical non-experts using generative adversarial learning.  _Frontiers in Artificial Intelligence_ , 2022.
  * Miller [2019] Tim Miller.  Explanation in artificial intelligence: Insights from the social sciences.  _Artificial Intelligence_ , pages 1–38, 2019.
  * Moore et al. [2019] Jonathan Moore, Nils Hammerla, and Chris Watkins.  Explaining deep learning models with constrained adversarial examples.  pages 43–56, 2019.
  * Mothilal et al. [2020] Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan.  Explaining machine learning classifiers through diverse counterfactual explanations.  In _Proceedings of the 2020 conference on fairness, accountability, and transparency_ , pages 607–617, 2020.
  * Pawelczyk et al. [2021] Martin Pawelczyk, Sascha Bielawski, Johannes van den Heuvel, Tobias Richter, and Gjergji Kasneci.  Carla: A python library to benchmark algorithmic recourse and counterfactual explanation algorithms.  2021\.
  * Pearl et al. [2016] J. Pearl, M. Glymour, and N.P. Jewell.  _Causal Inference in Statistics: A Primer_.  Wiley, 2016.  ISBN 9781119186847.
  * Poyiadzi et al. [2020] Rafael Poyiadzi, Kacper Sokol, Raul Santos-Rodriguez, Tijl De Bie, and Peter Flach.  FACE: Feasible and actionable counterfactual explanations.  page 344–350, 2020.
  * Rasouli and Chieh Yu [2022] Peyman Rasouli and Ingrid Chieh Yu.  Care: Coherent actionable recourse based on sound counterfactual explanations.  _International Journal of Data Science and Analytics_ , pages 1–26, 2022.
  * Skulimowski [1990] Andrzej Skulimowski.  Applicability of ideal points in multicriteria decision-making.  In _Multiple Criteria Decision-Making, Proceedings of the Ninth International Conference_ , pages 5–8, 1990.
  * Spreitzer et al. [2022] Nina Spreitzer, Hinda Haned, and Ilse van der Linden.  Evaluating the practicality of counterfactual explanations.  In _Workshop on Trustworthy and Socially Responsible Machine Learning, NeurIPS 2022_ , 2022.
  * Stefanowski [2023] Jerzy Stefanowski.  Multi-criteria approaches to explaining black box machine learning models.  In _Asian Conference on Intelligent Information and Database Systems ACIIDS 2023_ , pages 195–208. Springer, 2023.
  * Stepka et al. [2023] Ignacy Stepka, Mateusz Lango, and Jerzy Stefanowski.  On usefulness of dominance relation for selecting counterfactuals from the ensemble of explainers.  In _In: Proceedings of the 4rd Polish Conference on Artificial Intelligence, PP-RAI 2023_ , pages 125–130. Wydawnictwo Politechniki Łódzkiej, 2023.
  * Steuer [1986] R.E. Steuer.  _Multiple Criteria Optimization: Theory, Computation, and Application_.  Wiley Series in probability and mathematical statistics. Wiley, 1986.
  * Tolomei et al. [2017] Gabriele Tolomei, Fabrizio Silvestri, Andrew Haines, and Mounia Lalmas.  Interpretable predictions of tree-based ensembles via actionable feature tweaking.  In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM, 2017.
  * Ustun et al. [2019] Berk Ustun, Alexander Spangher, and Yang Liu.  Actionable recourse in linear classification.  In _Proceedings of the Conference on Fairness, Accountability, and Transparency_. ACM, jan 2019.
  * Van Looveren and Klaise [2021] Arnaud Van Looveren and Janis Klaise.  Interpretable counterfactual explanations guided by prototypes.  In _Machine Learning and Knowledge Discovery in Databases. Research Track_ , pages 650–665. Springer International Publishing, 2021.
  * Verma et al. [2020] Sahil Verma, Varich Boonsanong, Minh Hoang, Keegan E Hines, John P Dickerson, and Chirag Shah.  Counterfactual explanations and algorithmic recourses for machine learning: A review.  _arXiv preprint arXiv:2010.10596_ , 2020.
  * Wachter et al. [2017] Sandra Wachter, Brent Mittelstadt, and Chris Russell.  Counterfactual explanations without opening the black box: Automated decisions and the gdpr.  _Harv. JL & Tech._, 2017.
  * Wellawatte et al. [2022] Geemi P. Wellawatte, Aditi Seshadri, and Andrew D. White.  Model agnostic generation of counterfactual explanations for molecules.  _Chem. Sci._ , 2022.
  * Wilson and Martinez [1997] D. Randall Wilson and Tony R. Martinez.  Improved heterogeneous distance functions.  _Journal of artificial intelligence research_ , pages 1–34, 1997.