[a,b,c]Giacomo Principe

# Hunting the gamma-ray emission from Fast Radio Burst with Fermi-LAT

, Nicola Omodei  , Niccolò Di Lalla  , Leonardo Di Venere  , Francesco Longo
, on behalf of the Fermi Large Area Telescope Collaboration

###### Abstract

Fast radio bursts (FRBs) are one of the most exciting new mysteries of
astrophysics. Their origin is still unknown, but recent observations seems to
link them to Soft Gamma Repeaters and, in particular, to magnetar giant flares
(MGFs). The recent detection of a MGF at GeV energies by the Fermi Large Area
Telescope (LAT) motivated the search for GeV counterparts to the $>$100
currently known FRBs. Taking advantage of more than 12 years of Fermi-LAT
data, we perform a search for gamma-ray emission from all the reported
repeating and non-repeating FRBs. We analyse on different-time scales the
Fermi-LAT data of each individual source separately, including a cumulative
analysis on the repeating ones. In addition, we perform the first stacking
analysis at GeV energies of this class of sources in order to constrain the
gamma-ray properties of the FRBs that are undetected at high energies. The
stacking analysis is a powerful method that allow a possible detection from
below-threshold FRBs providing important information on these objects. In this
talk we present the preliminary results of our study and we discuss their
implications for the predictions of gamma-ray emission from this class of
sources.

##  1 Introduction

Discovered just over a decade ago [1], fast radio bursts (FRBs) are one of the
newest astrophysical enigmas. FRBs are bright (typical fluences of few Jy) and
short-duration (few ms or less) pulses at frequencies of about 1 GHz, having
usually large dispersion measures (DM; the free electron density along the
line of sight at a certain distance) in excess of Galactic values [2].

Since their discovery in 2007, several hundreds, as of 2021, June 15, of FRBs
have been reported so far [e.g.; see FRB catalogs 3, 4]. In particular, an
increasing number of FRBs exhibit repeating bursts random in time, and two of
them show a periodic pattern in their activity cycle, as in the case of FRB
180916 [5] and FRB 121102 [6] for which however there is only an indication of
periodicity ($\sim 3\sigma$ significance). No clear indications for physically
different populations distinguishing repeating and non-repeating sources has
been obtained so far.

Despite being a recent discovery, a great interest have been attracted by the
study of FRBs. In particular, FRBs may be used as powerful probes of the
intergalactic medium, and emission mechanism powering these bursts may help
clarify some long-standing issues in astrophysics, including the missing
baryon problem and the nature of coherent emission[7].

Many attempts have recently been made for understanding their progenitors. The
short duration of FRBs favours models involving compact objects such as
strongly magnetized neutron stars (magnetars) and massive black holes [8].
Last year, for the first time, an FRB-like event was associated with a Soft
Gamma Repeater (SGR 1935+2154) and, in particular, to a Galactic magnetar
giant flare (MGF) [FRB 200428, 9].

The recent detection of high-energy emission, at GeV energies, from a magnetar
giant flare in the Sculptor galaxy by [10] motivated the search for gamma-ray
counterparts to the known FRBs. In the last years, some high-energy
counterpart searches for FRBs have been performed without any significant
detection [see e.g, 11, 12, 14, 13], however they were based on a few dozens
of FRBs.

Thanks to over 12 years of data collected by the Fermi Large Area Telescope
(LAT), and to more than 1000 published FRBs, we aim to perform the largest and
deepest systematic search for gamma-ray emission from all the reported
repeating and non-repeating bursts. We make use of different analysis
techniques to search for time coincidences between exposed FRBs and events at
different timescales, ranging from few seconds to days/weeks and up to several
years, with Fermi-LAT. In addition to the study of each individual FRB source,
we perform also a stacking analysis for searching the cumulative emission from
the repeating FRBs.

##  2 Sample of FRBs

For our analysis we selected published FRBs from the following resources:

  * •

118 events from the FRBCAT111https://frbcat.org [3];

  * •

535 repeating and non-repeating FRBs reported in the first CHIME/FRB catalog
[4];

  * •

230 bursts from the 20 repeating FRBs reported by the CHIME/FRB collaboration
(http://www.chime-frb.ca/repeaters) as of June 15, 2021, including 73 bursts
from the periodic FRB 180916;

  * •

235 bursts from FRB 121102 collected by Rajwade et al. [6].

Since several sources are present in more than one of the above-listed
samples, we removed all the repetitions. In addition to these samples, we
included the first FRB from the Galactic MGF located in SGR 1935+2154. Our
sample consists of 1025 FRBs events, including 560 non repeating FRBs and 465
bursts from 22 repeating FRBs. Figure 1 shows the sky map of the selected
FRBs, compared with the gamma-ray sources in the 4FGL-DR2 catalog [15]. The
observed asymmetric distribution between the northern and southern
hemispheres, as well as the fact that all the repeating bursts are located in
the northern hemisphere, is related to the large number of bursts detected by
the CHIME/FRB telescope [16].

Figure 1:  Sky map, in Galactic coordinates and Mollweide projection, showing
the 1025 FRBs in our sample. Repeating FRBs are labelled in the plot. All the
4FGL-DR2 sources [15] are also plotted, with grey points, for a comparison.

Figure 2 shows the dispersion measure (DM) distribution of the selected FRBs.

Figure 2:  Dispersion measure (DM) distribution of all the FRBs contained in
our sample.

The large dispersion measure of the observed bursts suggests their possible
extragalactic origin. To date the detection of FRBs with associated small
(arcsec) error boxes has allowed the detection of fifteen putative host
galaxies222http://frbhosts.org/, accessed on June 15, 2021 with a luminosity
distances range from 149 Mpc to 4 Gpc, giving solid bases to their
cosmological origin. Last year, for the first time, an FRB-like event
(DM=332.7206) was associated to a Galactic magnetar giant flares (MGFs), SGR
1935+2154, located at a distance of 12.5 kpc [FRB 200428, 9, 17].

Among the repeating bursts, the FRB 180916 presents a significant periodicity
of 16.35-day period, with all events observed in a window of 5.4 days (active
phase). While a possible (3.2$\sigma$ significance) periodic activity from FRB
121102 have been recently reported [6]. In this proceeding we focus on the
preliminary results on the search of high-energy emission from the periodic
FRB 180916, while further results on all the selected FRBs will be provided in
a forthcoming publication [18].

##  3 Fermi-LAT analysis

The LAT is a gamma-ray telescope that detects photons by conversion into
electron-positron pairs and has an operational energy range from 20 MeV to
$\sim$ TeV. It comprises a high-resolution converter tracker (for direction
measurement of the incident gamma rays), a CsI(Tl) crystal calorimeter (for
energy measurement) and an anti-coincidence detector to identify the
background of charged particles [19]. Thanks to its wide-field of view, it is
able to cover the entire sky in $\sim 3$ hours, making it a very suitable
$\gamma$-ray detector for investigating the high-energy counterpart of FRBs.

The search for gamma-ray emission from FRBs was performed using various
analysis techniques on different time scales ranging from few seconds up to
several years. Subsequently we performed a stacking analysis of the events
which were not significantly detected in the individual study, in order to
investigate the general properties of the population of the FRB sources. A
similar method was applied in Principe et al. [20] to study another class of
celestial objects.

First, we applied a photon counting analysis to study the coincidence of
single or multiple events with the time and position of the FRBs in our
sample.

Then, we analysed the Fermi-LAT data of each individual source in our sample
using a standard likelihood analysis in order to determine whether it is
detected or not (using a Test Statistic TS333The test statistic (TS) is the
logarithmic ratio of the likelihood $\mathcal{L}$ of a model with the source
being at a given position in a grid to the likelihood of the model without the
source,
TS=$2\log\frac{\mathcal{L}_{\mathrm{src}}}{\mathcal{L}_{\mathrm{null}}}$ [21].
$>25$ as a threshold).

We analysed each individual burst using time intervals ranging from few
seconds to days/months centred on the arrival time of the FRB. We also
analysed the 12.7 years (August 5, 2008 - April 5, 2021) of Fermi-LAT data.
This latest time-interval is motivated by the search of possible new steady
sources (not present in the latest publish LAT catalog [15]) from which the
FRBs may be originated.

In addition to the study of each individual burst contained in our sample, we
performed an ’ad-hoc’ analysis for the repeating FRBs searching for cumulative
signal from all the intervals when bursts have been reported. We used
therefore a ’folding’ analysis procedure, combining together 1000-seconds time
intervals of all the events from a FRB source.

Furthermore, a special attention has been given to the periodic FRB 180916, on
which a folding analysis have been performed considering both the 0.6-day and
5.4-day phase windows. These time-intervals correspond to the windows on which
50% and 100% of the events have been detected [5], We analysed both the active
phases after the FRB discovery as well as all the periods for the 12.7 years
of Fermi-LAT available. A similar approach has been applied also to FRB
121102, for which a possible periodicity of $\sim$157 days period have been
recently reported [6].

The binned likelihood analysis (which consists of model optimisation, and
localisation, spectrum and variability analyses) was performed with
Fermipy444http://fermipy.readthedocs.io/en/latest/ [22], a python package that
facilitates the analysis of LAT data with the Fermi Science Tools, of which
the version 11-07-00 was used. For this analysis we selected events which have
been reprocessed with the P8R3_Source_V2 instrument response functions (IRFs)
[IRFs, 23], in the energy range between 100 MeV and 1 TeV. The low energy
threshold is motivated by the large uncertainties in the arrival directions of
the photons below 100 MeV, leading to a possible confusion between point-like
sources and the Galactic diffuse component. For a different analysis
implementation to solve this and other issues at low energies with Fermi-LAT
see [24].

The analysis consists of model optimisation, source localisation and spectrum
study. The counts maps were created with a pixel size of $0.1^{\circ}$. We
selected $\gamma$-rays with zenith angle smaller than 90∘. The model used to
describe the ROI includes all point-like and extended LAT sources, located at
a distance $<25^{\circ}$ from each target position, listed in 4FGL catalog
[15], as well as the Galactic diffuse and isotropic emission
555https://fermi.gsfc.nasa.gov/ssc/data/access/lat/BackgroundModels.html. For
the analysis we first optimised the model for the ROI, then we searched for
the possible presence of new sources and finally we re-localised the source.
During the model optimisation, we left free to vary the diffuse background
and, only for the analysis on long (i.e., more than a day) time-scales, also
all the spectral parameters of the sources within 5∘ of our targets, while
only the normalisation for those at a distance between 5∘ and 10∘.

In addition to study each individual FRB source, we perform a stacking
analysis for searching the cumulative emission from the repeating FRBs, as
well as on the entire population of FRB sources.

##  4 Preliminary Fermi-LAT results on FRB 180916

In this part we present our preliminary results on the search for high-energy
emission from the periodic FRB 180916 (z=0.0337) with Fermi-LAT. We analysed
LAT data from 10-seconds and 1000-seconds time intervals centred on the first
observed burst (MJD=58377.42972096) without finding any significant emission.
In addition, we performed a folding analysis on the cumulative gamma-ray
emission from the 73 detected bursts, using time intervals of 1000 s centred
on each event, as well as on the 5.4-day active phase windows of the periodic
FRB, using the 12.7 years of available LAT data. Similarly to the analysis on
short time scales, we did not find any significant gamma-ray emission also on
this cumulative analysis of the periodic FRB 180916.

We report on Table 1 the 95% upper limits on the FRB energy flux, obtained for
a power-law spectral model of spectral photon index of 2.

Table 1:  The 95% upper limits on the energy flux of the periodic FRB 180916 from 10-seconds (1) and 1000-seconds (2) time intervals centred on the first observed burst (MJD=58377.42972096), from the folding analysis of the cumulative gamma-ray emission from 1000s time intervals of the 73 detected bursts (3), as well as on the 5.4-day active phase windows (4). Upper limits were obtained for a power-law spectral model of spectral photon index of 2. Analysis | Upper limit on energy flux
---|---
|  (erg cm-2 s-1)
10 s | $7.8\times 10^{-8}$
1000 s | $1.4\times 10^{-9}$
folding 1000 s of all bursts | $1.7\times 10^{-10}$
5.4-days active phase (12.7 years) | $2.3\times 10^{-12}$

Figure 3 shows the spectral upper limits obtained on the periodic FRB 180916
for the different time-scales used in our analysis.

Figure 3:  Fermi-LAT spectrum of the periodic FRB 180916. We plot the upper-
limits for the 10 s and 1000 s time intervals centred on the first FRB event,
as well as for the folding analysis on the 73 detected burst using a 1000 s
time intervals, and for the 5.2-day active phase windows obtained for the 12.7
years of LAT data.

Although in our analysis we did not find any detection, we provide the so-far
most stringent upper limits on the gamma-ray emission from the FRB 180916
source during its 5-day active-phase window [see review 25].

##  5 Conclusion

FRBs are one of the most intriguing topics in astronomy of the last decade. We
presently know of more than 1000 burst from 560 non-repeating FRBs and 22
repeating ones. Despite their origin is still unclear, recent observations
seem to associate them to Soft Gamma Repeaters and, in particular, to MGFs.
Furthermore, the recent detection by the Fermi-LAT of gamma-ray emission from
a MGF located in the Sculpture galaxy (z=0.000811) [10] galvanises the search
of high-energy emission from FRBs. We aim to perform the largest and deepest
systematic search for gamma-ray counterpart to FRBs.

We report here the preliminary results of search for high-energy emission from
the periodic FRB 180916 (z=0.0337). Although in our analysis we did not find
any detection, we provide the so-far most stringent upper limits on the gamma-
ray emission from the FRB 180916 source during its 5-day active-phase window
($L_{\gamma-ray}<7.5\times 10^{42}$ erg s-1). Our results provide crucial
information on constraining the origin of FRBs and modelling their emission
mechanisms.

Further results on the search for the high-energy emission from the $\sim$1000
selected FRBs will be provided in a forthcoming paper [18].

### ACKNOWLEDGMENTS

We acknowledge use of the CHIME/FRB Public Database, provided at
https://www.chime-frb.ca/ by the CHIME/FRB Collaboration.

The Fermi-LAT Collaboration acknowledges support from NASA and DOE (United
States), CEA/Irfu, IN2P3/CNRS, and CNES (France), ASI, INFN, and INAF (Italy),
MEXT, KEK, and JAXA (Japan), and the K.A. Wallenberg Foundation, the Swedish
Research Council, and the National Space Board (Sweden).

## References

  * Lorimer et al. [2007] Lorimer, D. R., Bailes, M., McLaughlin, M. A., et al. 2007, Science, 318, 777.
  * Petroff et al. [2019] Petroff, E., Hessels, J. W. T., & Lorimer, D. R. 2019, Astronomy and Astrophysics Reviews, 27, 4.
  * Petroff et al. [2016] Petroff, E., Barr, E. D., Jameson, A., et al. 2016, Publications of the Astron. Soc. of Australia, 33, e045.
  * The CHIME/FRB Collaboration et al. [2021] The CHIME/FRB Collaboration, :, Amiri, M., et al. 2021, arXiv:2106.04352
  * Chime/Frb Collaboration et al. [2020] Chime/Frb Collaboration, Amiri, M., Andersen, B. C., et al. 2020, Nature, 582, 351.
  * Rajwade et al. [2020] Rajwade, K. M., Mickaliger, M. B., Stappers, B. W., et al. 2020, Monthly Notices of the RAS, 495, 3551.
  * McQuinn [2014] McQuinn, M. 2014, Astrophysical Journal Letters, 780, L33.
  * Cordes & Chatterjee [2019] Cordes, J. M. & Chatterjee, S. 2019, Annual Review of Astron and Astrophys, 57, 417.
  * Bochenek et al. [2020] Bochenek, C. D., Ravi, V., Belov, K. V., et al. 2020, Nature, 587, 59.
  * Fermi-LAT Collaboration et al. [2021] Fermi-LAT Collaboration, Ajello, M., Atwood, W. B., et al. 2021, Nature Astronomy.
  * Cunningham et al. [2019] Cunningham, V., Cenko, S. B., Burns, E., et al. 2019, Astrophysical Journal, 879, 40.
  * Guidorzi et al. [2020] Guidorzi, C., Marongiu, M., Martone, R., et al. 2020, Astronomy and Astrophysics, 637, A69.
  * Verrecchia et al. [2021] Verrecchia, F., Casentini, C., Tavani, M., et al. 2021, arXiv:2105.00685
  * Tavani et al. [2020] Tavani, M., Verrecchia, F., Casentini, C., et al. 2020, Astrophysical Journal Letters, 893, L42.
  * Abdollahi et al. [2020] Abdollahi, S., Acero, F., Ackermann, M., et al. 2020, Astrophysical Journal Supplement, 247, 33.
  * CHIME/FRB Collaboration et al. [2018] CHIME/FRB Collaboration, Amiri, M., Bandura, K., et al. 2018, Astrophysical Journal, 863, 48.
  * CHIME/FRB Collaboration et al. [2020] CHIME/FRB Collaboration, Andersen, B. C., Bandura, K. M., et al. 2020, Nature, 587, 54.
  * Principe et al. [submitted] Principe, G., Omodei N., Di Venere L., et al. in preparation.
  * Atwood et al. [2009] Atwood, W. B., Abdo, A. A., Ackermann, M., et al. 2009, Astrophysical Journal, 697, 1071.
  * Principe et al. [2021] Principe, G., Di Venere, L., Orienti, M., et al. 2021, Monthly Notices of the RAS, 507, 4564. doi:10.1093/mnras/stab2357
  * Mattox et al. [1996] Mattox, J. R., Bertsch, D. L., Chiang, J., et al. 1996, Astrophysical Journal, 461, 396.
  * Wood et al. [2017] Wood, M., Caputo, R., Charles, E., et al. 2017, 35th International Cosmic Ray Conference (ICRC2017), 301, 824
  * Bruel et al. [2018] Bruel, P., Burnett, T. H., Digel, S. W., et al. 2018, arXiv:1810.11394
  * Principe et al. [2018] Principe, G., Malyshev, D., Ballet, J., et al. 2018, Astronomy and Astrophysics, 618, A22.
  * Nicastro et al. [2021] Nicastro, L., Guidorzi, C., Palazzi, E., et al. 2021, Universe, 7, 76.


# Uncertainty in Additive Feature Attribution methods

Abhishek Madaan 1, Tanya Chowdhury 2, Neha Rana 1, James Allan 2, Tanmoy
Chakraborty 3

###### Abstract

In this work, we explore various topics that fall under the umbrella of
Uncertainty in post-hoc Explainable AI (XAI) methods. We in particular focus
on the class of additive feature attribution explanation methods. We first
describe our specifications of uncertainty and compare various statistical and
recent methods to quantify the same. Next, for a particular instance, we study
the relationship between a feature’s attribution and its uncertainty and
observe little correlation. As a result, we propose a modification in the
distribution from which perturbations are sampled in LIME-based algorithms
such that the important features have minimal uncertainty without an increase
in computational cost. Next, while studying how the uncertainty in
explanations varies across the feature space of a classifier, we observe that
a fraction of instances show near-zero uncertainty. We coin the term “stable
instances” for such instances and diagnose factors that make an instance
stable. Next, we study how an XAI algorithm’s uncertainty varies with the size
and complexity of the underlying model. We observe that the more complex the
model, the more inherent uncertainty is exhibited by it. As a result, we
propose a measure to quantify the relative complexity of a blackbox
classifier. This could be incorporated, for example, in LIME-based algorithms’
sampling densities, to help different explanation algorithms achieve tighter
confidence levels. Together, the above measures would have a strong impact on
making XAI models relatively trustworthy for the end-user as well as aiding
scientific discovery.

(a)

(b)

Figure 1: Feature-wise distribution of variation in importance scores obtained
by executing the LIME explanation algorithm (left) 100, and (right) 1000
times, respectively to explain a binary classifier on a chosen instance of the
UCI Diabetes dataset.

## Introduction

The last couple of years have witnessed the advent of a large number of
feature attribution methods (Ribeiro, Singh, and Guestrin 2016; Lundberg and
Lee 2017; Shrikumar, Greenside, and Kundaje 2017). While some of them are
motivated by generating explanations of deep neural models for end users
(model-based explanations), others are built in order to gain an understanding
of unknown properties and mechanisms of the underlying data-generating process
(system-based explanations). Many feature attribution algorithms have been
independently evaluated for stability/robustness/uncertainty, and
unfortunately, most of them fare poorly (Schulz, Poyiadzi, and Santos-
Rodriguez 2021). There is a pressing need to quantify and reduce uncertainty
of these explanation algorithms. For end users, upper bounding the uncertainty
estimate is necessary for garnering trust on the use of Explainable-AI models.
It is especially important to do so before they are used in critical decision-
making scenarios such as deciding jail terms, making medical diagnoses, etc.
System-based explanation methods consider the explanation algorithm to be
genuine insights, so even small errors in the algorithm’s results can lead to
false discoveries and incorrect scientific understanding. Uncertainty
quantification is critical to address that issue.

Only a handful of works have attempted to address problems related to
uncertainty in feature attribution methods. Certain XAI algorithms report the
uncertainty associated with a feature attribution. For example: BayesLIME
(Slack et al. 2021) computes instance-wise uncertainty at various confidence
levels; CXPlain (Schwab and Karlen 2019) reports global uncertainty for the
explanation algorithm. Ghorbani, Abid, and Zou (2019) point out how
explanation algorithms are stochastic processes, highly susceptible to hyper-
parameter changes and adversarial feature perturbations. Zhang et al. (2019)
focus on the LIME algorithm and diagnose the three different root causes of
uncertainty in the same while Schulz, Poyiadzi, and Santos-Rodriguez (2021)
attempt to assign an uncertainty estimate to LIME feature attributions using
bootstrapping and ordinal consensus methods. Krishna et al. (2022) study the
disagreement problem among feature attributions and propose interesting
metrics such as Feature agreement and Rank agreement that can be used to
quantify uncertainty among feature attribution methods. However the problem
space of feature attribution algorithms and uncertainties is huge and the
research done so far is in its early stages. Owing to the limited work in this
domain and the sheer importance of the research problem, we conduct a
behavioral exploration on various research questions under the umbrella of
Uncertainty in XAI. Based on our findings, we also suggest interventions which
would make existing algorithms considerably more robust through the lens of
uncertainty.

In this work, we analyse the uncertainty presented by post-hoc additive
feature attribution based XAI methods for generating local explanations. We
first describe our definition and set of assumptions regarding XAI uncertainty
and enumerate statistical and recent measures to quantify the same (Confidence
Interval w/o Bootstrapping, Standard Deviation, Kendall’s Coefficient of
Concordance, Fleiss’s Kappa, Feature Agreement, and Rank Agreement). We
tabulate and compare the uncertainty reported by each metric on four popular
feature attribution methods (LIME, KernelSHAP, BayesLIME, and CXPlain) over
two datasets. Because of its balance between stability and sensitivity, we
choose the Kendall’s coefficient of concordance to quantify uncertainty in our
experiments. We next study the relationship between a feature’s attribution
and its uncertainty, and observe the absence of any strong correlation. We
propose a modification in the multivariate Gaussian distribution from which
perturbations are sampled in the LIME algorithm such that the important
features have $11.42\%$ reduced uncertainty as compared to the original
algorithm without an increase in computational cost. While studying how
uncertainty varies across the feature space of a dataset, we witness that a
fraction of instances show near-zero uncertainty; we coin the term “stable
instances” for such instances. We diagnose which factors lead to an instance
being stable, and propose an algorithm that determines if an instance is
stable with a precision of $89.2\%$ and recall of $95.1\%$. Next, we study how
uncertainties of XAI algorithms vary with the size and complexity of the
underlying models. We observe that the more complex the model, the more the
inherent uncertainty exhibited by it. As a result, we propose an important
measure to quantify the complexity of a blackbox model. This could be
incorporated in numerous applications, for example, in LIME-based algorithms
to decide sampling densities, to aid different models achieve given confidence
levels.

Our major contributions are as follows:
$\bullet$ We benchmark the performance of 4 different XAI algorithms on 5
uncertainty quantification metrics for a small-scale diabetes and a larger-
scale synthetic dataset. $\bullet$ We propose a modification to the
multivariate sampling function of LIME to achieve $11.42\%$ and $9.06\%$
reduction in top attributes over the PIMA Diabetes and synthetic datasets,
respectively. $\bullet$ We coin the term “stable instances” for instances
whose uncertainty remains low across executions and propose an algorithm to
mine “stable instances”. $\bullet$ We find a strong correlation between the
“complexity” of the underlying model and its average uncertainty and propose a
cardinality-based metric to approximate the complexity of a model for
explanation computation.

To the best of our knowledge, we are the first to study the aforementioned
research questions for XAI. In the spirit of reproducability, we share all the
scripts and datasets required as supplementary material.

Table 1: Measures (Confidence Interval (CI), Confidence Interval Bootstrapping (CI-bootstrap), Standard Deviation (Std. dev.), Kendall’s Coefficient of Concordance ($W$), Fleiss’ Kappa ($\kappa$), Top-K Feature Agreement (TopK-FA) and Top-K Rank Agreement (TopK-RA) with k=8) to quantify uncertainty in explanations generated using popular local linear explanation methods (LIME, KernelShap, BayesLIME and CXPlain) using the PIMA Indian diabetes and our synthetic dataset.  Metric | CI | CI-bootstrap | Std. dev. | W | $\kappa$ | TopK-FA | TopK-RA
---|---|---|---|---|---|---|---
Diabetes
Random | 2.546 | 2.156 | 4.120 | 0.987 | 0.999 | 0 | 0.875
LIME | 0.005 | 0.005 | 0.014 | 0.160 | 0.661 | 0 | 0.5
KernelShap | 0.0043 | 0.0042 | 0.0108 | 0.058 | 0.326 | 0 | 0.375
BayesLIME | 0.012 | 0.0121 | 0.031 | 0.862 | 0.473 | 0 | 0.75
CXPlain | 0.0402 | 0.0327 | 0.0482 | 0.546 | 0.433 | 0 | 0
Synthetic
Random | 2.783 | 2.929 | 3.997 | 1 | 0.990 | 0.892 | 0.979
LIME | $1.64\times 10^{-3}$ | $1.62\times 10^{-3}$ | $4.11\times 10^{-3}$ | 0.569 | 0.953 | 0.465 | 0.894
KernelShap | $1.11\times 10^{44}$ | $8.38\times 10^{43}$ | $2.99\times 10^{45}$ | 0.991 | 0.9995 | 0.35 | 0.875
BayesLIME | 0.035 | 0.034 | 0.088 | 0.971 | 0.906 | 0.234 | 0.76
CXPlain | 0.0123 | 0.0009 | 0.0012 | 0.0685 | 0.939 | 0 | 0.155

## Dataset Descriptions

We use two datasets for our experiments: the UCI Pima Indians Diabetes
dataset111https://raw.githubusercontent.com/jbrownlee/Datasets/master/pima-
indians-diabetes.csv and a larger scale synthetic dataset.

Given certain features from patient medical records, the Pima Indians Diabetes
dataset is a binary classification dataset that predicts the onset of diabetes
within 5 years. It has 768 observations, containing 8 input features (Glucose,
Blood Pressure, Insulin, BMI, Age, etc.) and a binary output where 1 indicates
eventual disease onset. The train-test split for this dataset is $80:20$. This
dataset choice was motivated by the large use case of XAI tools in medical
diagnostic settings and the urgent need to curb uncertainty in such scenarios.

To better understand underlying phenomena of XAI methods, we validate our
experiments on a synthetic dataset. We build a dataset with $100$ features and
$200,000$ instances for our experiments. To build our dataset, we focus on
generating two independent parts: instances $x$ and their ground-truth labels
$y$. We sample our instances $x$ from a mixture of multivariate Gaussians as
described by Liu et al. (2021) starting with arbitrary values of $\mu_{D}$ and
$\Sigma_{D\times D}$ (here $D=100$). For generating ground-truth labels, we
implement a set of linear functions, piece-wise constant functions, non linear
additive functions (e.g., absolute, sine, cosine, exponent, etc.) and piece-
wise linear functions. We then compute intermediate labels
$y_{raw}=\sum_{n=1}^{100}\Psi_{n}(x_{n})$, where $\Psi_{n}$ refers to one of
the functions described above. The labels obtained in this manner are
normalized to have zero mean and unit variance. To build the binary
classification dataset, instances whose $y_{raw}$ values lie above the mean
are assigned label $1$, while those below are assigned label $0$. We set the
train-test split for this dataset at $75:25$ (Liu et al. 2021). This synthetic
dataset allows us to perform targeted experiments by providing control of each
attribute and enables the simulation of various scenarios like low and high
density regions, low and high correlation between features, as well as
incorporating anomalous behaviour within a dataset.

## Quantifying Uncertainty in XAI

While there can be multiple underlying causes that lead to uncertainty in
feature attributions, like classifier uncertainty, in this work we focus on
uncertainty produced solely due to multiple runs of the same explanation
algorithm. A large number of explanation algorithms are perturbation-based and
as a result stochastic processes, whose uncertainty we wish to quantify. Next,
we briefly enumerate methods that can be used to measure the uncertainty of
feature attributions. We include statistical uncertainty quantification
methods as well as variants proposed in recent literature specific to XAI.

$\bullet$ Confidence Interval: Used by Schwab and Karlen (2019) for XAI
uncertainty quantification with the width of the confidence interval being the
uncertainty measure.
$\bullet$ Confidence Interval + Bootstrapping: The attribution algorithm is
run $M$ times before a median feature attribution is chosen from the ensemble
on which Schwab and Karlen (2019) compute uncertainty as above.
$\bullet$ Standard Deviation: The attribution algorithm is run $M$ times and
the standard deviation (stdev) of each feature’s attribution is calculated and
averaged to compute an aggregated uncertainty score.
$\bullet$ Kendall’s Coefficient of Concordance ($w$): Used by Schulz,
Poyiadzi, and Santos-Rodriguez (2021) in XAI, to find correlation between
orderings of features. This is a bounded metric and returns values in $[0,1]$.
Since this is a concordance metric, $W=1-w$ is used to quantify uncertainty.
$\bullet$ Fleiss’ Kappa ($\kappa$): Introduced by Fleiss and Cohen (1973) and
also used by Schulz, Poyiadzi, and Santos-Rodriguez (2021) in XAI, Kappa is
also a rank correlation metric which returns a bounded value in $[0,1]$.
$\bullet$ Feature Agreement: Introduced by Krishna et al. (2022), this metric
measures the relative agreement two attributions face on the top $k$ features.
This score is pairwise aggregated over all attributions over which uncertainty
is being evaluated. Since this is a similarity score, we report the score
subtracted from 1 as uncertainty.
$\bullet$ Rank Agreement: Also introduced by Krishna et al. (2022), this
metric computes the fraction of features that have the same position in
respective rank orders in two feature attributions. This is a stricter metric
than feature agreement.

Table 2: Comparing the uncertainty of the original LIME and KernelSHAP (KS) algorithms and the Multivariate Gaussian Sampled LIME (MVG-LIME) and MVG-KS modification we propose, over Top-1 feature, Top-2 feature and Top-5 feature and for the entire instance with k=2. While the first three uncertainties are computed using standard deviation, the instance uncertainty is computed using Kendall’s coefficient of concordance. Results are averaged over $100$ instances from the Diabetes and synthetic dataset.  Metric | LIME | MVG-LIME | KS | MVG-KS | LIME | MVG-LIME | KS | MVG-KS
---|---|---|---|---|---|---|---|---
Dataset | Diabetes | Synthetic
Top-1 Unc (std) | 0.011 | 0.0092 | 0.012 | 0.0095 | 0.023 | 0.0181 | 0.036 | 0.0067
Top-2 Unc (std) | 0.0117 | 0.013 | 0.014 | 0.0092 | 0.026 | 0.02 | 0.039 | 0.026
Top-5 Unc (std) | 0.014 | 0.0136 | 0.021 | 0.0198 | 0.032 | 0.023 | 0.043 | 0.031
All Unc | 0.176 | 0.087 | 0.035 | 0.0232 | 0.065 | 0.045 | 0.072 | 0.059

We perform experiments to quantify the uncertainty of four different
explanation algorithms, namely LIME (Ribeiro, Singh, and Guestrin 2016),
KernelSHAP (Lundberg and Lee 2017), BayesLIME (Slack et al. 2021) and CXPlain
(Schwab and Karlen 2019), on the synthetic and the PIMA Indian diabetes
dataset using the seven metrics to compute uncertainty described above. The
experimental settings for this comparision along with details of each metric
can be found in the Appendix. We report the comparision results in Table 1. We
first observe that all of the studied explanation algorithms show significant
uncertainty, making the amortization of such uncertainty an important task. We
also find that, among the discussed metrics, the Kendall’s coefficient of
concordance is bounded, assumes a range of values in the interval, as well as
shows strong correlations to the other metrics. Based on that, we use the
Kendall’s Coefficient ($W$) to measure uncertainty in our remaining
experiments.

## Feature Uncertainty vs Feature Importance

In this section, we focus on the uncertainty shown by individual features in a
feature attribution. We witness significant uncertainty in each feature’s
attribution score (its “importance”) when running any of the above mentioned
explanation algorithms multiple times with the same set of hyper-parameters
(see Figure 1). It is of interest to us to study the correlation between a
feature’s importance and the uncertainty of its attribution. A negative
correlation between them is desirable as most applications focus on the top K
most important features (Lipton 2018), for which we would like to minimize
uncertainty.

As a result, we bootstrap and compute the uncertainty for each feature
individually over 100 runs (Figure 1). We then study the correlation between a
feature’s attribution ($w$) and its uncertainty ($u$) for a particular
instance (Figure 8 in Appendix). To do so, we compute the Pearson’s
correlation coefficient between $w_{i}$ and $u_{i}$:
$r=\frac{\sum_{i}(w_{i}-\overline{w})(u_{i}-\overline{u})}{\sum(w_{i}-\overline{w})^{2}(u_{i}-\overline{u})^{2}}$.
We sample 100 instances from both datasets and compute the average Pearson
correlation to demarcate the relationship between the feature’s attribution
and uncertainty in each feature. We find the mean correlation to be $0.128$
and $0.0104$ with a standard deviation of $0.015$ and $0.0006$ for the PIMA
Diabetes and Synthetic datasets respectively. The Pearson’s coeeficient has a
range of $[-1,1]$, and our numbers show very weak positive correlation, which
is not ideal. As a result, we propose a generic modification to perturbation-
based explanation algorithms in order to reduce uncertainty of the important
features.

We suggest a framework that allows important features to have stronger
uncertainty bounds as compared to the less significant ones at the same
sampling density. At present, when generating tabular perturbations, the LIME
algorithm222https://github.com/marcotcr/lime/blob/master/lime/lime˙tabular.py
accepts as input hyper-parameter _num-samples_ and samples a univariate
isotropic Gaussian distribution to choose _num-samples_ instances in the
neighborhood of the instance. This implied that perturbations are chosen
around the instance $x$ being explained following the distribution
$f_{\mathcal{N}}(x)=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{(x-\mu)^{2}}{2\sigma^{2}}}$.
The algorithm sets $\mu$ to $0$ and $\sigma$ to $1$ by default.

We know from Laugel et al. (2018a) that an accurate approximation for the LIME
explanation of an instance is the LIME explanation computed at its nearest
Decision Boundary Point (DBP). A DBP for an instance is the instance on the
classifier decision boundary with nearest Euclidean distance to the instance
being explained. We first compute the tangent to the instance at its nearest
DBP and obtain feature attributions $w_{DBP}$ (Appendix : Algorithm 2). We
also measure the distance $l$ between the instance being explained and its
DBP. We then use the weights of $w_{DBP}$ and the distance to the nearest DBP
$l$ to sample perturbations in LIME in an updated covariance matrix such that,
$\mu_{new}=0_{D}$, and $\Sigma_{new}=\frac{k\times w_{DBP}}{l}$, where $k$ is
a constant, and $\Sigma_{new}$’s non-diagonal elements are zero.

We hypothesize that sampling from this multivariate Gaussian distribution with
mean $\mu_{new}$ and covariance $\Sigma_{new}$ would lead to reduced
uncertainty as compared to the original algorithm. We name this modified
algorithm – Multivariate Gaussian Sampled LIME (MVG-LIME).

We experiment by generating LIME based explanations for 100 instances using
both the classic method and our modification on both the datasets. We set the
value of constant $k$ in MVG-LIME to $2$ on the diabetes dataset and $18$ on
the synthetic dataset based on hyper-parameter tuning. All other hyper-
parameters are fixed to the same values (default LIME parameters) across the
experiments. The results are shown in Table 2. We witness a $27.27\%$
reduction in the uncertainty of the top feature, $14.53\%$ in the top two
features, and $7.386\%$ on the entire instance in the modified approach as
compared to the base algorithm.

This new sampling distribution enables features with higher attributions in
the DBP to be sampled more densely as they are assigned a wider range. In a
similar manner, features with low attributions are assigned a lower range for
sampling and would not be as thoroughly sampled. Employing this modification
would decrease the average uncertainty of important attributes in
perturbation-based algorithms at the same computational cost.

(a)

(b)

Figure 2: Uncertainty (Kendall Coefficient of concordance) vs Frequency of
Instances with corresponding uncertainty for (left) a 3-layer MLP on the PIMA
Indian Diabetes dataset, (right) a 16-layer MLP on the synthetic dataset.

## Uncertainty Across the Classifier’s Feature Space

Table 3: Confusion Matrix depicting instances marked ”Stable” and ”Not Stable” by our algorithm and their corresponding truth labels low (near-zero)/high uncertainty on the Diabetes and Synthetic dataset for LIME and KernelSHAP feature attributions.  Algorithm |  | LIME | KernelSHAP
---|---|---|---
Dataset |  | Low Uncertainty | High Uncertainty | Low Uncertainty | High Uncertainty
Diabetes | Stable | 0.672 | 0.02 | 0.528 | 0.098
Diabetes | Not-Stable | 0.019 | 0.289 | 0.045 | 0.329
Synthetic | Stable | 0.264 | 0.022 | 0.205 | 0.01
Synthetic | Not-Stable | 0.011 | 0.703 | 0.06 | 0.725

Although there has recently been a lot of interest in quantifying uncertainty
of explanation algorithms, studies attempting to do so largely sample a few
instances from the classifier’s feature space and report aggregrated
uncertainty. We, however, think that there might be underlying trends and
insights on how the uncertainty of an instance varies across the feature space
for a binary classification model. Our aim in this section is to study how the
uncertainty of instances varies across the feature space of a classifier.

As a first step towards this, we sample a 1000 instances arbitrarily from the
feature space of both the Diabetes and synthetic datasets and compute their
uncertainty for LIME explanations using Kendall’s coefficient of concordance.
We plot a density graph for both the datasets in Figure 2. For both datasets,
we observe an interesting phenomenon. We essentially witness two peaks in the
Uncertainty density curves for both datasets, one near zero and another at a
positive uncertainty value. Instances with feature attribution having near
zero uncertainty can be of interest to both earn the trust of end users as
well as for use in scientific discovery. As a result, we coin the term stable
instances for such instances. Stable instances can be used as representative
instances for global explanations over their more uncertain counterparts. They
might also help us mine interesting insights about the dataset, the binary
classifier, as well as the explanation algorithm’s behaviour while explaining
it. As a result it is of interest to diagnose what underlying phenomena makes
an instance stable and to come up with an algorithm to generate stable
instances.

Here, we focus on diagnosing what makes an instance a stable instance in
perturbation-based explanation algorithms. As discussed in the previous
section, we find that the nearest decision boundary point ($DBP_{x}$) has the
most influence on the LIME explanation attribution. We find that for most
instances, the uncertainty of the instance was significantly less than the
uncertainty of its nearest DBP (with $94\%$ accuracy) (Figures 4,5,6 in
Appendix). We also empirically observe that having multiple DBPs in equal
proximity of an instance is a leading cause of high instance uncertainty. As a
result, we introduce the term $l_{DBP_{k}}$ for an instance $x$, which
signifies the Euclidean distance between the instance and its $k^{th}$ nearest
DBP in the feature space. We hypothesize that for an instance if $l_{DBP_{2}}$
is larger than $l_{DBP_{1}}$ by at least $5\%$, the instance is a stable
instance. This is motivated by the fact that if the second nearest DBP is at
least a threshold distance away from the nearest, it would not influence
decision making as much and the explanation would be stable.

To verify our hypothesis, we select 1000 instances sampled uniformly from the
feature space of both datasets. We first compute the uncertainty of each
instance using Kendall’s coefficient of concordance. Following the uncertainty
density graphs (Figure 2), we term any instance with uncertainty less than
$0.02$ in the Diabetes dataset and any instance with uncertainty less than
$0.2$ in the synthetic dataset to be stable instances. We then test our
hypothesis to compute whether an instance is stable. We sample heavily in the
growing spheres algorithm ($n=100,000$) used to compute DBPs. We find that
although the growing spheres algorithm is a randomized algorithm, it is
deterministic enough to show trends. We report the confusion matrix of our
Stable Instance determination algorithm in Table 3 for LIME and KernelSHAP on
both datasets. Overall, our algorithm has a precision of $89.2\%$ and a recall
of $95.1\%$ average over both datasets and algorithms.

The presence of multiple DBPs in close proximity leads to different subsets of
them being sampled by perturbation based algorithms at each execution. Since
each decision boundary point usually has its own distinct tangent, the
incorporation of multiple instances brings in high levels of uncertainty to
the LIME algorithm. Following the above, we end up with an algorithm to mine
stable instances for a dataset and binary classifier. This can be incorporated
within various global explanation methods that look for representative
instances to explain the model’s behavior in different regions of the dataset
(e.g., SP-LIME (Ribeiro, Singh, and Guestrin 2016), Guided-LIME (Sangroya et
al. 2020), etc). We also observe that the fraction of stable instances
decreases as the underlying binary classifier’s complexity increases.

(a)

(b)

Figure 3: Relative uncertainty amongst various classifiers trained on (a) PIMA
diabetes (b) synthetic dataset. Algorithm 1 ModelComplexityFinder

1:Classifier $f$, explainer $g$, dataset $\mathcal{D}$, number of samples $n$,
threshold $m$

2:procedure ModelComplexityFinder($f,g,\mathcal{D},n$)

3: $p\leftarrow\textsc{RandomSample}(\mathcal{D},n)$ $\triangleright$ Sample
$n$ points from $\mathcal{D}$

4: $CardinalityArray\leftarrow[]$

5: for all $x\in p$ do

6: $DBP,l_{DBP}\leftarrow\textsc{NearestDBPs}(f,g,x)$ $\triangleright$ Returns
DBPs in increasing order of distance to $x$

7: $c\leftarrow\underset{i}{\text{argmax }}l_{DBP}[i]$ s.t.
$l_{DBP}[i]<(1+m/100)\cdot l_{DBP}[0]$

8: $CardinalityArray.\textsc{Append}(c)$

9: return $\frac{1}{n}\Sigma_{i}CardinalityArray[i]$

## Uncertainty vs Underlying model complexity

Most work in quantifying uncertainty involve experiments on a single
underlying classifier. These classifiers are usually available as an API to
query and are thus blackbox to the person performing experiments. It is of
interest to infer about the complexity of the blackbox classifier, in order to
make informed decisions. In this section, our goal is to study the change in
uncertainty of explanation algorithms while computing feature attributions for
underlying models of different complexities.

We experiment by generating feature attributions for a host of underlying
models (Logistic regression, SVM linear kernel, SVM rbf kernel, different MLP
setting, etc.) on both the datasets. We use the scikit-learn implementations
of each of the above algorithms to learn binary classifiers on the Diabetes
and synthetic datasets. We follow by randomly sampling 100 instances from the
feature space of each dataset and generating perturbation-based explanations
for each of these instances explaining underlying models. We then bootstrap
and compute the uncertainty of each of these classifiers using the Kendall’s
coefficient of concordance. The distribution of uncertainty in feature
attributions as a function of the underlying model is visualized in Figure 3.
We witness a significant variation (Standard deviation of $0.3524$ and
$0.0789$ in PIMA Diabetes and Synthetic datasets respectively) of uncertainty
in explanations generated by the same Explanation algorithm (LIME) when
explaining different underlying models. We observe that uncertainty increases
considerably with the increase in complexity of the underlying model, with
small MLP models having least uncertainty and the SVM model with an rbf kernel
showing the highest uncertainty.

In this light, we propose ModelComplexityFinder, an algorithm to quantify the
relative “complexity” of a blackbox classifier. This “complexity” value
obtained from ModelComplexityFinder can be incorporated in XAI algorithms to
infer more about the blackbox being explained and as a result generate more
trustworthy explanations. For example, we can scale the number of
perturbations to be sampled in perturbation-based algorithms according to the
underlying model’s complexity, sampling more densely for complex models to
obtain tighter bounds on uncertainty.

The ModelComplexityFinder algorithm is detailed in Algorithm 1. We tweak the
growing spheres algorithm (Algorithm 2 in the Appendix) to return all nearest
decision boundary points within a certain threshold distance from the
instance. We then assign a complexity cardinality to each instance based on
the number of decision boundary points which lie within $5\%$ of
$l_{DBP_{1}}$. For each classifier, we sample 100 instances uniformly from the
feature space and compute the cardinality of each instance using the tweaked
growing spheres algorithm. We average the cardinality of the 100 instances to
report the average cardinality complexity of the blackbox model. In this
manner, ModelComplexityFinder allows us to compute the average complexity of a
blackbox model before we use standard explanation algorithms to generate
explanations for it.

We employ ModelComplexityFinder to estimate the complexity of 5 different
underlying models – Logistic Regression, SVM with a linear Kernel, SVM with an
rbf kernel, MLP with 1 hidden layer, and MLP with 3 hidden layers on the Pima
Indian Diabetes dataset. All hyper-parameters are kept fixed across the
experiments. For the growing spheres algorithm, we set the sampling parameter
$n$ to 100,000. We report the results of our ModelComplexityFinder algorithm
in Table 4. We observe that according to our algorithm, SVM-rbf has the
highest complexity with an average cardinality of $29.8$ while Logistic
regression has the lowest with an average cardinality of $3.67$ for the PIMA
Diabetes dataset. We evaluate the performance of our proposed algorithm to
compute a binary classifier’s complexity by calculating the correlation
between the ground truth uncertainty (obtained by averaging Kendall’s
Concordance for those instances) and its calculated complexity. The Pearson
correlation coefficient between the model complexity and true model
uncertainty is $0.836$, showing that ModelComplexityFinder is a good way to
estimate the relative uncertainty of a classifier when all other parameters
are fixed.

Table 4: Underlying model’s complexity estimated by the ModelComplexityFinder algorithm for various binary classifiers (Logistic Regression (LR), SVM with a linear kernel (SVM-lin) , SVM with an RBF kernel (SVM-rbf), 1 layer MLP, 3 layer MLP) on the Pima India Diabetes and the synthetic dataset.  Dataset | LR | SVM-lin | SVM-rbf | 1-MLP | 3-MLP
---|---|---|---|---|---
Diabetes | 3.67 | 4.2 | 29.8 | 7.2 | 21.6
Dataset | LR | SVM-lin | SVM-rbf | 5-MLP | 20-MLP
Synthetic | 1.11 | 1.03 | 1.4 | 1.16 | 1.21

## Related Work

Certain XAI algorithms report uncertainty by default, along with their feature
attribution. Schwab and Karlen (2019) propose CXPlain, which is trained using
a causal objective. After training, the model can be used to compute
explanations quickly and to estimate uncertainty through bootstrap ensembling.
Slack et al. (2021) propose BayesLIME and BayesSHAP, which are Bayesian
versions of LIME and KernelSHAP that output credible intervals for the feature
importance, capturing the associated uncertainty through confidence intervals.
Throughout this study, we treat uncertainty as an emergent behaviour of
explainable-AI systems. However, some other works like that of Zhang et al.
(2019), focus on the root cause of uncertainty and identify three different
sources in LIME-like algorithms, i.e., the randomness of the sampling
procedure, variation in the sampling proximity (the kernel function) and
variation in explained model credibility across data instances. Schulz,
Poyiadzi, and Santos-Rodriguez (2021) quantify uncertainty by measuring the
ordinal consensus among a set of diverse bootstrapped surrogate explainers.
Others like Hill et al. (2022) focus on generating an uncertainty estimate
combining the decision boundary uncertainty and explanation function
uncertainty. A few studies do not focus on uncertainty directly, but throw
light on related proxy metrics. Krishna et al. (2022) study the disagreement
problem, where they work on computing the uncertainty between feature
attributions generated by different attribution algorithms for the same
classifier and instance. Alvarez-Melis and Jaakkola (2018) verify the
robustness of perturbation-based and saliency-based explanation methods using
a local Lipschitz estimate to check how output varies according to a given
input. On similar lines, Ghorbani, Abid, and Zou (2019) observe that the
interpretations by neural networks are fragile and show that two perceptively
indistinguishable inputs with the same predicted label can be assigned very
different interpretations, via experiments on the MNIST dataset. It is of
future interest to study the relation between uncertainty and fragility
metrics for XAI algorithms.

## Conclusion and Future Work

In this work, we addressed a number of important problems under the umbrella
of uncertainty in Explainable-AI. We first described our assumptions for
uncertainty and enumerated methods to compute uncertainty in XAI. We evaluated
the uncertainty of popular explanation methods LIME, Kernel-SHAP, Bayes-LIME,
and CXPlain using the described metrics. We next analysed the uncertainty
shown by different features within an attribution and proposed an algorithm to
achieve negative correlation between a feature attribution and its
uncertainty. Next we studied how the uncertainty of explanation vectors varied
across the feature space of a model. We highlighted the existence of stable
points, diagnosed the reason for their existence and proposed an algorithm to
mine a stable instance. Lastly we analysed the impact that the underlying
model’s complexity had on the uncertainty of explanations and observed that
the more complex the underlying model, the higher the resulting explanation
uncertainty is. Following this we suggested a proxy metric to estimate an
underlying model’s complexity in order to set better hyper-parameters in the
explanation algorithm.

Uncertainty of XAI algorithms is a major deterrent in their use in critical
real life scenarios. Especially, uncertainty of these explanation algorithms
need to be at near zero levels for them to be used to build hypothesis in
scientific understanding. Our work summarizes a few issues regarding
uncertainty and suggests approaches to solve them for the class of LIME based
explanation methods. However the problem of uncertainty in XAI is far from
solved. Future work would involve looking into methods to reduce uncertainty
in non-perturbation explanation algorithms. The ultimate goal would be to
propose explanation algorithms that perform highly with respect to both
faithfulness as well as certainty.

## References

  * Aas, Jullum, and Løland (2021) Aas, K.; Jullum, M.; and Løland, A. 2021.  Explaining individual predictions when features are dependent: More accurate approximations to Shapley values.  _Artificial Intelligence_ , 298: 103502.
  * Abdar et al. (2021) Abdar, M.; Pourpanah, F.; Hussain, S.; Rezazadegan, D.; Liu, L.; Ghavamzadeh, M.; Fieguth, P.; Cao, X.; Khosravi, A.; Acharya, U. R.; et al. 2021.  A review of uncertainty quantification in deep learning: Techniques, applications and challenges.  _Information Fusion_ , 76: 243–297.
  * Alvarez-Melis and Jaakkola (2018) Alvarez-Melis, D.; and Jaakkola, T. S. 2018.  On the Robustness of Interpretability Methods.  arxiv:1806.08049.
  * Bentley, Preparata, and Faust (1982) Bentley, J. L.; Preparata, F. P.; and Faust, M. G. 1982.  Approximation algorithms for convex hulls.  _Communications of the ACM_ , 25(1): 64–68.
  * Burkart and Huber (2021) Burkart, N.; and Huber, M. F. 2021.  A survey on the explainability of supervised machine learning.  _Journal of Artificial Intelligence Research_ , 70: 245–317.
  * Dhurandhar et al. (2018) Dhurandhar, A.; Chen, P.-Y.; Luss, R.; Tu, C.-C.; Ting, P.; Shanmugam, K.; and Das, P. 2018.  Explanations based on the missing: Towards contrastive explanations with pertinent negatives.  _arXiv preprint arXiv:1802.07623_.
  * Fleiss and Cohen (1973) Fleiss, J. L.; and Cohen, J. 1973.  The equivalence of weighted kappa and the intraclass correlation coefficient as measures of reliability.  _Educational and psychological measurement_ , 33(3): 613–619.
  * Gal and Ghahramani (2016) Gal, Y.; and Ghahramani, Z. 2016.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning.  In _international conference on machine learning_ , 1050–1059. PMLR.
  * Garreau and Luxburg (2020) Garreau, D.; and Luxburg, U. 2020.  Explaining the explainer: A first theoretical analysis of LIME.  In _International Conference on Artificial Intelligence and Statistics_ , 1287–1296. PMLR.
  * Ghorbani, Abid, and Zou (2019) Ghorbani, A.; Abid, A.; and Zou, J. 2019.  Interpretation of neural networks is fragile.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, 3681–3688.
  * Goyal et al. (2019) Goyal, Y.; Wu, Z.; Ernst, J.; Batra, D.; Parikh, D.; and Lee, S. 2019.  Counterfactual visual explanations.  In _ICML_ , 2376–2384. PMLR.
  * Herzog and Ostwald (2013) Herzog, S.; and Ostwald, D. 2013.  Sometimes Bayesian statistics are better.  _Nature_ , 494(7435): 35–35.
  * Hill et al. (2022) Hill, D.; Masoomi, A.; Ghimire, S.; Torop, M.; and Dy, J. 2022.  Explanation Uncertainty with Decision Boundary Awareness.  _arXiv preprint arXiv:2210.02419_.
  * Hooker et al. (2019) Hooker, S.; Erhan, D.; Kindermans, P.-J.; and Kim, B. 2019.  A benchmark for interpretability methods in deep neural networks.  _Advances in neural information processing systems_ , 32.
  * Huang et al. (2004) Huang, K.; Yang, H.; King, I.; Lyu, M. R.; and Chan, L. 2004.  Biased Minimax Probability Machine for Medical Diagnosis.  In _ISAIM_.
  * Kendall and Smith (1939) Kendall, M. G.; and Smith, B. B. 1939.  The problem of m rankings.  _The annals of mathematical statistics_ , 10(3): 275–287.
  * Krishna et al. (2022) Krishna, S.; Han, T.; Gu, A.; Pombra, J.; Jabbari, S.; Wu, S.; and Lakkaraju, H. 2022.  The disagreement problem in explainable machine learning: A practitioner’s perspective.  _arXiv preprint arXiv:2202.01602_.
  * Lakkaraju, Bach, and Leskovec (2016) Lakkaraju, H.; Bach, S. H.; and Leskovec, J. 2016.  Interpretable decision sets: A joint framework for description and prediction.  In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_ , 1675–1684.
  * Lakkaraju et al. (2019) Lakkaraju, H.; Kamar, E.; Caruana, R.; and Leskovec, J. 2019.  Faithful and customizable explanations of black box models.  In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_ , 131–138.
  * Laugel et al. (2018a) Laugel, T.; Lesot, M.-J.; Marsala, C.; Renard, X.; and Detyniecki, M. 2018a.  Comparison-based inverse classification for interpretability in machine learning.  In _International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems_ , 100–111. Springer.
  * Laugel et al. (2018b) Laugel, T.; Renard, X.; Lesot, M.-J.; Marsala, C.; and Detyniecki, M. 2018b.  Defining locality for surrogates in post-hoc interpretablity.  _ICML’18 Workshop on Health_.
  * Letham et al. (2015) Letham, B.; Rudin, C.; McCormick, T. H.; Madigan, D.; et al. 2015.  Interpretable classifiers using rules and bayesian analysis: Building a better stroke prediction model.  _Annals of Applied Statistics_ , 9(3): 1350–1371.
  * Li and Wong (2003) Li, J.; and Wong, L. 2003.  Using rules to analyse bio-medical data: a comparison between C4.5 and PCL.  In _International Conference on Web-Age Information Management_ , 254–265. Springer.
  * Lipton (2018) Lipton, Z. C. 2018.  The Mythos of Model Interpretability: In machine learning, the concept of interpretability is both important and slippery.  _Queue_ , 16(3): 31–57.
  * Liu et al. (2021) Liu, Y.; Khandagale, S.; White, C.; and Neiswanger, W. 2021.  Synthetic Benchmarks for Scientific Research in Explainable Machine Learning.  arXiv:2106.12543.
  * Lundberg et al. (2020) Lundberg, S. M.; Erion, G.; Chen, H.; DeGrave, A.; Prutkin, J. M.; Nair, B.; Katz, R.; Himmelfarb, J.; Bansal, N.; and Lee, S.-I. 2020.  From local explanations to global understanding with explainable AI for trees.  _Nature machine intelligence_ , 2(1): 2522–5839.
  * Lundberg and Lee (2017) Lundberg, S. M.; and Lee, S.-I. 2017.  A unified approach to interpreting model predictions.  In _Advances in neural information processing systems_ , 4765–4774.
  * Luss et al. (2019) Luss, R.; Chen, P.-Y.; Dhurandhar, A.; Sattigeri, P.; Zhang, Y.; Shanmugam, K.; and Tu, C.-C. 2019.  Generating contrastive explanations with monotonic attribute functions.  _arXiv e-prints_ , arXiv–1905.
  * Plumb, Molitor, and Talwalkar (2018) Plumb, G.; Molitor, D.; and Talwalkar, A. S. 2018.  Model agnostic supervised local explanations.  _Advances in neural information processing systems_ , 31.
  * Ribeiro, Singh, and Guestrin (2016) Ribeiro, M. T.; Singh, S.; and Guestrin, C. 2016.  “Why should I trust you?” Explaining the predictions of any classifier.  In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_ , 1135–1144.
  * Rieger and Hansen (2019) Rieger, L.; and Hansen, L. K. 2019.  Aggregating explanation methods for stable and robust explainability.  _arXiv preprint arXiv:1903.00519_.
  * Ruggieri (2013) Ruggieri, S. 2013.  Learning from polyhedral sets.  In _Twenty-Third International Joint Conference on Artificial Intelligence_.
  * Sangroya et al. (2020) Sangroya, A.; Rastogi, M.; Anantaram, C.; and Vig, L. 2020.  Guided-LIME: Structured Sampling based Hybrid Approach towards Explaining Blackbox Machine Learning Models.  In _Proceedings CEUR Workshop_.  CIKM workshops.
  * Schulz, Poyiadzi, and Santos-Rodriguez (2021) Schulz, J.; Poyiadzi, R.; and Santos-Rodriguez, R. 2021.  Uncertainty Quantification of Surrogate Explanations: an Ordinal Consensus Approach.  arXiv:2111.09121.
  * Schwab and Karlen (2019) Schwab, P.; and Karlen, W. 2019.  Cxplain: Causal explanations for model interpretation under uncertainty.  _arXiv preprint arXiv:1910.12336_.
  * Selvaraju et al. (2017) Selvaraju, R. R.; Cogswell, M.; Das, A.; Vedantam, R.; Parikh, D.; and Batra, D. 2017.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In _Proceedings of the IEEE international conference on computer vision_ , 618–626.
  * Setzu et al. (2021) Setzu, M.; Guidotti, R.; Monreale, A.; Turini, F.; Pedreschi, D.; and Giannotti, F. 2021.  GLocalX-From Local to Global Explanations of Black Box AI Models.  _Artificial Intelligence_ , 294: 103457.
  * Shrikumar, Greenside, and Kundaje (2017) Shrikumar, A.; Greenside, P.; and Kundaje, A. 2017.  Learning Important Features through Propagating Activation Differences.  ICML’17, 3145–3153. JMLR.org.
  * ShubhankarRawat (2016) ShubhankarRawat. 2016.  ShubhankarRawat/Heart-Disease-Prediction.  [Online; accessed 11-June-2021].
  * Slack et al. (2021) Slack, D.; Hilgard, S.; Singh, S.; and Lakkaraju, H. 2021.  Reliable Post hoc Explanations: Modeling Uncertainty in Explainability.  arXiv:2008.05030.
  * Staniak and Biecek (2018) Staniak, M.; and Biecek, P. 2018.  Explanations of model predictions with live and breakDown packages.  _arXiv preprint arXiv:1804.01955_.
  * Van Looveren and Klaise (2019) Van Looveren, A.; and Klaise, J. 2019.  Interpretable counterfactual explanations guided by prototypes.  _arXiv preprint arXiv:1907.02584_.
  * Watson (2021) Watson, D. 2021.  Interpretable Machine Learning for Genomics.
  * Yeh et al. (2019) Yeh, C.-K.; Hsieh, C.-Y.; Suggala, A.; Inouye, D. I.; and Ravikumar, P. K. 2019\.  On the (in) fidelity and sensitivity of explanations.  _Advances in Neural Information Processing Systems_ , 32.
  * Zhang et al. (2019) Zhang, Y.; Song, K.; Sun, Y.; Tan, S.; and Udell, M. 2019.  Why Should You Trust My Explanation? Understanding Uncertainty in LIME Explanations.  arXiv:1904.12991.

##  Appendix A Appendix

Figure 4: This figure depicts Uncertainty of instances vs Uncertainty of their
closest decision boundary points. The underlying model is Logistic Regression
and explanation model is LIME. The points in the plot depicts distance between
the instances and their respective DBPs.

Figure 5: This figure depicts Uncertainty of instances vs Uncertainty of their
closest decision boundary points. The underlying model is MLP with 1 layer and
explanation model is LIME. The points in the plot depicts distance between the
instances and their respective DBPs.

Figure 6: This figure depicts Uncertainty of instances vs Uncertainty of their
closest decision boundary points. The underlying model is MLP with 3 layer and
explanation model is LIME. The points in the plot depicts distance between the
instances and their respective DBPs. Figure 7: LIME explanation of a
prediction made by 16-MLP on an instance of the synthetic dataset.

Figure 4,5 and 6 depict the Uncertainty of instances (x-axis) vs Uncertainty
of their nearest DBPs (y-axis) for three different binary classification
architectures : Logistic Regression, 1 layer MLP and 3 layer MLP respectively.

Figure 7 depicts the LIME explanation for an instance of the synthetic datset.
We see that only the top 3 out of 100 features have significant feature
attribution and it would be of advantage to make the uncertainty of primary
features minimal at the cost of the uncertainty of less important features.

Confidence Interval (CI): This method was used by Schwab and Karlen (2019) to
compute the confidence interval of an explanation
$CI_{i,\gamma}=[c_{i,\frac{\alpha}{2}},c_{i,1-\frac{\alpha}{2}}]$ at
confidence level $\gamma=1-\alpha$ for each assigned feature importance
estimate $a_{i}$. The width of this confidence interval
$u_{i}=c_{i,1-\frac{\alpha}{2}}-c_{i,\frac{\alpha}{2}}$ is used as a metric to
quantify the uncertainty of $a_{i}$.

Confidence Interval + Bootstrapping (CI-bootstrap): This method was employed
by Schwab and Karlen (2019) to quantify uncertainty of the CXPlain algorithm
based on bootstrap resampling. The explanation algorithm is executed $M$
times, and the median of the feature attributions in the ensemble members is
assigned as the feature importance of the bootstrap ensemble. This new feature
attribution is used to compute confidence intervals using the CI method
described above.

Standard Deviation: The explanation algorithm is executed $M$ times to compute
the standard deviation of each feature’s importance values. The values of the
features’ uncertainty are averaged to compute the uncertainty of an instance’s
explanation.

Kendall’s Coefficient of Concordance ($W$): The method introduced by Kendall
and Smith (1939) to quantify the correlation between rankings, was first used
by Schulz, Poyiadzi, and Santos-Rodriguez (2021) to quantify uncertainty in
XAI. Each explanation algorithm’s output feature is first assigned a rank
based on the relative feature importance in the explanation (1 being the most
important). The algorithm is executed $M$ times and a $D$-dimensional
cumulative sum of ranks vector (CR) is computed. The final concordance metric
$W^{\prime}$ is computed as
$\frac{12\sum_{i=1}^{D}\sum_{d=1}^{D}CR_{d}-CR_{i}}{M^{2}(D^{3}-D)}$. Since
this is a concordance metric, $(1-W^{\prime})$ denotes uncertainty. This is a
bounded metric with a range of $[0,1]$.

Fleiss’ Kappa ($\kappa$): This is another measure of rank correlation (Fleiss
and Cohen 1973). The explanation algorithm is executed $M$ times, and a rank
based on feature importance is assigned to each feature in every run. A vector
$T$ is computed such that $T_{i,j}$ is the count of the number of times
feature $i$ obtains rank $j$. Using this, we compute
$\overline{P}=\frac{1}{D}\sum_{i=1}^{D}\frac{1}{M^{2}-M}[\sum_{j=1}^{D}T_{ij}^{2}-M]$
and
$\overline{P}_{e}=\sum_{i=1}^{m}(\frac{\sum_{i=1}^{D}T_{ij}}{\sum_{i=1}^{D}\sum_{j=1}^{D}T_{ij}})^{2}$.
Then, Kappa $(\kappa)$ score can be calculated as:
$\kappa=\frac{\overline{P}-\overline{P}_{e}}{1-\overline{P}_{e}}$ . This is
also a bounded metric with range $[0,1]$.

We also include comparison with a Random Explanation algorithm as a baseline
for control. We random uniformly sample $100$ instances from both of our
datasets and generate explanations using the XAI algorithms mentioned above to
report the average uncertainty computed by each metric. Explanations are
generated to describe the same 3-layer MLP binary classifier for all
experiments in this section. Figure 1 presents the uncertainty of LIME
explanations, averaged over $100$ and $1000$ runs for an instance of the
Diabetes dataset.

For the confidence interval experiments, we set the confidence level to
$95\%$. The number of executions ($M$) is set to 100. The number of features
($D$) in the Diabetes dataset is $8$, and that in the synthetic dataset is
$100$.

(a)

(b)

Figure 8: Feature Importance vs Feature Uncertainty for an instance of the (a)
Diabetes dataset (b) Synthetic dataset

Decision Boundary Point ($DBP_{x}$) : LIME-based algorithms employ a falling
exponential kernel (Equation 2) based distance metric to compute each
perturbation’s contribution (Equation 1) towards the loss function being
optimized.

$\displaystyle\mathcal{L}(f,g,\pi_{x})$ $\displaystyle=\sum_{z,z^{\prime}\in
Z}\pi_{x}(z)(f(z)-g(z^{\prime}))^{2}$ (1) $\displaystyle\pi_{x}(z)$
$\displaystyle=\exp(-D(x,z)^{2}/\sigma^{2}),$ (2)

where $z$ represents the class of perturbed instances, $\pi_{x}$ describes the
locality around $x$, and $\mathcal{L}(f,g,\pi_{x})$ is a model of how
unfaithful the explanation model $g$ is in neighbourhood of $x$.

This makes finding the nearest Decision Boundary Point (DBP) for an instance
of utmost importance as within a set of perturbed instances ($Z$), $DBP_{x}$
is the perturbed instance ($z^{\prime}$) that will have highest value for
$\pi_{x}(z)(f(z)-g(z^{\prime}))^{2}$. Since $\pi_{x}(z)$ is an exponentially
falling kernel, other perturbed instances on the other side of the decision
boundary will have little impact on $\mathcal{L}$, as compared to $DBP_{x}$.
In order to compute the decision boundary instance nearest to an instance $x$,
Laugel et al. (Laugel et al. 2018a) propose the Growing Spheres algorithm.
They uniformly sample $n$ points in the hyper-dimensional sphere centred at
$x$ of radius $\eta$. They initialize $\eta$ with a large value and compute
the classification label for each sampled instance as per $f$. The presence of
instances with a different classification label than that of $x$ indicates the
presence of a decision boundary within the sphere. To find the nearest
decision boundary point, they redo the above steps with radius $\eta$ halved
and repeat until all sampled points have the same classification label. Next
they sample in spherical layers of linearly increasing radii, namely the
region between spheres of radius $\eta$ and $2\eta$, then $2\eta$ and $3\eta$,
and so on until they encounter a sample instance with classification label
difference from $x$. They term this instance $DBP_{x}$. The pseudo-code of
this process (Laugel et al. 2018a) is provided in Algorithm 2. This is an
approximate and randomized algorithm due to the high-dimensional sampling
involved. We make use of the growing sphere algorithm to compute $DBP_{x}$ in
order to analyze the uncertainty displayed by LIME-based algorithms.

We employ concepts from all of the works described above to answer pressing
questions and propose interventions regarding the uncertainty of XAI
algorithms at the feature level, at the instance level across the feature
space as well as at the variation of the underlying model level.

Algorithm 2 Growing spheres algorithm for computing the Decision Boundary
Point nearest to $x$ (Laugel et al. 2018a)

1:$f:\mathbf{x}\rightarrow\\{0,1\\}$: a binary classifier , $x\in\mathbf{x}$:
an observation to be explained, $\eta,n$: Hyperparameters

2:Nearest Decision Boundary Point $e$

3:Generate $(z_{i})_{i\leq n}$ uniformly in $\mathrm{SL}(x,0,\eta)$

4:while $\exists k\in(z_{i})_{i\leq n}:f(k)\neq f(x)$ do

5: $\eta=\eta/2$

6: Generate $(z_{i})_{i\leq n}$ uniformly in $\mathrm{SL}(x,0,\eta)$

7:$a_{0}=\eta,a_{1}=2\eta$

8:Generate $(z_{i})_{i\leq n}$ uniformly in $\mathrm{SL}(x,a_{0},a_{1})$

9:while $\textbf{not }\exists k\in(z_{i})_{i\leq n}:f(k)\neq f(x)$ do

10: $a_{0}=a_{1}$

11: $a_{1}=a_{1}+\eta$

12: Generate $(z_{i})_{i\leq n}$ uniformly in $SL(x,a_{0},a_{1})$

13:return $k$, the $l_{2}$-closest decision boundary point from $x$