Efficient and Accurate Explanation Estimation with Distribution Compression

## Abstract

Abstract Exact computation of various machine learning explanations requires numerous model evaluations and in extreme cases becomes impractical. The computational cost of approximation increases with an ever-increasing size of data and model parameters. Many heuristics have been proposed to approximate post-hoc explanations efficiently. This paper shows that the standard i.i.d. sampling used in a broad spectrum of algorithms for explanation estimation leads to an approximation error worthy of improvement. To this end, we introduce compress then explain ( cte ), a new paradigm for more efficient and accurate explanation estimation. cte uses distribution compression through kernel thinning to obtain a data sample that best approximates the marginal distribution. We show that cte improves the estimation of removal-based local and global explanations with negligible computational overhead. It often achieves an on-par explanation approximation error using 2–3 × \times × less samples, i.e. requiring 2–3 × \times × less model evaluations. cte is a simple, yet powerful, plug-in for any explanation method that now relies on i.i.d. sampling.

## 1 Introduction

Computationally efficient estimation of post-hoc explanations is at the forefront of current research on explainable machine learning (Strumbelj & Kononenko, ; Covert & Lee, ; Slack et al., ; Jethani et al., ; Chen et al., ; Donnelly et al., ; Muschalik et al., ).
The majority of the work focuses on improving efficiency with respect to the dimension of features (Covert et al., ; Jethani et al., ; Chen et al., ; Fumagalli et al., ), specific model classes like neural networks (Erion et al., ) and decision trees (Muschalik et al., ), or approximating the conditional feature distribution (Chen et al., ; Aas et al., ; Olsen et al., , ).

However, in many practical settings, a marginal feature distribution is used instead to estimate explanations, and i.i.d. samples from the data typically form the so-called *background data* samples, also known as *reference points* or *baselines*, which plays a crucial role in the estimation process (Lundberg & Lee, ; Covert et al., ; Scholbeck et al., ; Erion et al., ; Ghalebikesabi et al., ; Lundstrom et al., ).
For example, Covert et al. () mention “*[O]ur sampling approximation for SAGE was run using draws from the marginal distribution.
We used a fixed set of 512 background samples […]*” and we provide more such quotes in Appendix A to motivate our research question: *Can we reliably improve on standard i.i.d. sampling in explanation estimation?*

We make a connection to research on statistical theory, where kernel thinning (kt, Dwivedi & Mackey, , ) was introduced to compress a distribution more effectively than with i.i.d. sampling.
kt has an efficient implementation in the compress++ algorithm (Shetty et al., ) and was applied to improve statistical kernel testing (Domingo-Enrich et al., ).
Building on this line of work, this paper aims to thoroughly quantify the error introduced by the current *sample then explain* paradigm in feature marginalization, which is involved in the estimation of both local and global removal-based explanations (Covert et al., ).
We propose an efficient way to reduce this approximation error based on distribution compression (Figure 1).
We refer the reader to the arguments provided in (Herrmann et al., ) concerning the added value of conducting such empirical research in machine learning.
Namely, the research question is rather open and we aim to gain insight into a previously unexplored area.

Figure: Figure 1: Garbage sample in, garbage explanation out. *Sample then explain* is a conventional approach to decrease the computational cost of explanation estimation. Although fast, sampling is unstable and prone to error, which may even lead to changes in feature importance rankings. We propose *compress then explain* (cte), a new paradigm for accurate, yet efficient, estimation of explanations based on a marginal distribution that is compressed, e.g. with kernel thinning.
Refer to caption: x1.png

#### Contribution.

In summary, our work advances current literature in multiple ways:
(1) Quantifying the error of standard i.i.d. sampling: We bring to attention and measure the approximation error introduced by using i.i.d. sampling of background and foreground data in various explanation methods.
(2) Compress then explain: We introduce a new paradigm for estimating post-hoc explanations based on a marginal distribution compressed more effectively than with i.i.d. sampling.
(3) Kernel thinning for (explainable) machine learning: We show experimentally that kt outperforms i.i.d. sampling in compressing the distribution of popular datasets used in research on explainable machine learning.
In fact, this is the first work to evaluate distribution compression via kt on datasets for supervised learning.
(4) Decreasing the computational cost of explanation estimation: We benchmark *compress then explain* (cte) with popular explanation methods and show it results in more accurate explanations of smaller variance.
cte often achieves on-par error using 2–3$\times$ less samples, i.e. requiring 2–3$\times$ less model evaluations. cte is a simple, yet powerful, plug-in for a broad class of methods that sample from a dataset, e.g. removal-based and global explanations.

#### Related work.

Our work is the first to empirically evaluate kt on datasets for supervised learning, and one of the first to reliably improve on i.i.d. sampling for multiple post-hoc explanation methods at once.
Laberge et al. () propose a biased sampling algorithm to attack the estimation of feature attributions, which further motivates finding robust improvements for i.i.d. sampling.
Our research question is orthogonal to that of *how to sample perturbations around an input* (Petsiuk et al., ; Slack et al., ; Li et al., ; Ghalebikesabi et al., ; Li et al., ), or *how to efficiently sample feature coalitions* (Chen et al., ; Covert & Lee, ; Fumagalli et al., ).
Instead of generating samples from the conditional distribution itself, which is challenging (Olsen et al., ), we explore how to efficiently select an appropriate subset of background data for explanations (Hase et al., ; Lundstrom et al., ).
Specifically for Shapley-based explanations, Jethani et al. () propose to predict them with a learned surrogate model, while Kolpaczki et al. () propose their representation detached from the notion of marginal contribution.
We aim to propose a general paradigm shift that would benefit a broader class of explanation methods including feature effects (Apley & Zhu, ; Moosbauer et al., ) and expected gradients (Erion et al., ).

Concerning distribution compression, the method most related to kt (Dwivedi & Mackey, ) is the inferior standard thinning approach (Owen, ).
Cooper et al. () use insights from kt to accelerate distributed training, while Zimmerman et al. () apply kt in robotics.
In the context of data-centric machine learning, we broadly relate to finding coresets to improve the efficiency of clustering (Agarwal et al., ; Har-Peled & Mazumdar, ) and active learning (Sener & Savarese, ), as well as dataset distillation (Wang et al., ) and dataset condensation (Zhao et al., ; Kim et al., ) that create synthetic samples to improve the efficiency of model training.

## 2 Preliminaries

We aim to explain a prediction model trained on labeled data and denoted by $f:\mathcal{X}\mapsto\mathbb{R}$ where $\mathcal{X}$ is the feature space; it predicts an output using an input feature vector $\mathbf{x}$.
Usually, we assume $\mathcal{X}\subseteq\mathbb{R}^{d}$.
Without loss of generality, in the case of classification, we explain the output of a single class as a posterior probability from $[0,1]$.
We usually also assume a given dataset $\{(\mathbf{x}^{(1)},y^{(1)}),\ldots,(\mathbf{x}^{(n)},y^{(n)})\}$, where every element comes from $\mathcal{X}\times\mathcal{Y}$, the underlying feature and label space, on which the explanation are computed.
Depending on the explanation method, this can be a training or test dataset, and it could also be provided without labels.
We denote the $n\times d$ dimensional data matrix by $\mathbb{X}$ where $\mathbf{x}^{(i)}$ appears in the $i$-th row of $\mathbb{X}$, which is assumed to be sampled in an i.i.d. fashion from an underlying distribution $p(\mathbf{x},y)$ defined on $\mathcal{X}\times\mathcal{Y}$.
We denote a random vector as $\mathbf{X}\in\mathcal{X}$.
Further, let $s\subset\{1,\dots,d\}$ be a feature index set of interest with its complement $\bar{s}=\{1,\dots,d\}\setminus s$.
We index feature vectors $\mathbf{x}$ and random variables $\mathbf{X}$ by index sets $s$ to restrict them to these index sets.
We write $p_{\mathbf{X}}(\mathbf{x})$ and $p_{\mathbf{X}_{s}}(\mathbf{x}_{s})$ for marginal distributions on $\mathbf{X}$ and $\mathbf{X}_{s}$, respectively, and $p_{\mathbf{X}_{s}|\mathbf{X}_{t}}(\mathbf{x}_{s}|\mathbf{x}_{t})$ for conditional distribution on $\mathbf{X}_{s}|\mathbf{X}_{t}$.
We use $q_{\mathbb{X}}$ to denote an empirical distribution approximating $p_{\mathbf{X}}$ based on a data matrix $\mathbb{X}$.

#### Sampling from the data matrix is prevalent in explanation estimation.

Various estimators of post-hoc explanations sample from the data matrix to efficiently approximate the explanation estimate (Appendix A).
For example, many removal-based explanations (Covert et al., ) like shap (Lundberg & Lee, ) and sage (Covert et al., ) rely on marginalizing features out of the model function $f$ using their joint conditional distribution $\mathbb{E}_{\mathbf{X}_{\bar{s}}\sim p_{\mathbf{X}_{\bar{s}}|\mathbf{X}_{s}=
\mathbf{x}_{s}}}\left[f(\mathbf{x}_{s},\mathbf{X}_{\bar{s}})\right]=\int f(
\mathbf{x}_{s},\mathbf{x}_{\bar{s}})p_{\mathbf{X}_{\bar{s}}|\mathbf{X}_{s}=
\mathbf{x}_{s}}(\mathbf{x}_{\bar{s}}|\mathbf{x}_{s})d\mathbf{x}_{\bar{s}}.$

Note that the practical approximation of the conditional distribution $p_{\mathbf{X}_{\bar{s}}|\mathbf{X}_{s}=\mathbf{x}_{s}}(\mathbf{x}_{\bar{s}}|
\mathbf{x}_{s})$ itself is challenging (Chen et al., ; Aas et al., ; Olsen et al., ) and there is no ideal solution to this problem (see a recent benchmark by Olsen et al., ).
In fact, in (Covert et al., , Appendix D), it is mentioned that the default for sage is to assume feature independence and use the marginal distribution $p_{\mathbf{X}_{\bar{s}}|\mathbf{X}_{s}=\mathbf{x}_{s}}(\mathbf{x}_{\bar{s}}|
\mathbf{x}_{s})\coloneq p_{\mathbf{X}_{\bar{s}}}(\mathbf{x}_{\bar{s}})$; so does the kernel-shap estimator (a practical implementation of shap, Lundberg & Lee, ). This trend continues in more recent work (Fumagalli et al., ; Krzyziński et al., ).

###### Definition 2.1 (Feature marginalization) .

Given a set of observed values $\mathbf{x}_{s}$, we define a model function with marginalized features from the set $\bar{s}$ as $f(\mathbf{x}_{s};p_{\mathbf{X}})\coloneq\mathbb{E}_{\mathbf{X}_{\bar{s}}\sim p
_{\mathbf{X}_{\bar{s}}}}\left[f(\mathbf{x}_{s},\mathbf{X}_{\bar{s}})\right]$.

In practice, the expectation $\mathbb{E}_{\mathbf{X}_{\bar{s}}\sim p_{\mathbf{X}_{\bar{s}}}}\left[f(\mathbf{
x}_{s},\mathbf{X}_{\bar{s}})\right]$ is estimated by i.i.d. sampling from the dataset $\mathbb{X}$ that approximates the distribution $p_{\mathbf{X}_{\bar{s}}}(\mathbf{x}_{\bar{s}})$.
This sampled set of points forms the so-called *background data*, aka *reference points*, or *baselines* as specifically in case of the expected-gradients (Erion et al., ) explanation method defined as $\textsc{expected-gradients}(\mathbf{x})\coloneq\mathbb{E}_{\mathbf{X}\sim p_{
\mathbf{X}},\alpha\sim U(0,1)}\left[(\mathbf{x}-\mathbf{X})\cdot\frac{\partial
f
(\mathbf{X}+\alpha\cdot(\mathbf{x}-\mathbf{X}))}{\partial\mathbf{x}}\right].$

Furthermore, i.i.d. sampling is used in global explanation methods, which typically are an *aggregation* of local explanations.
To improve the computational efficiency of these approximations, often only a subset of $\mathbb{X}$ is considered; called *foreground data*. Examples include: feature-effects explanations (Apley & Zhu, ), an aggregation of lime (Ribeiro et al., ) into g-lime (Li et al., ), and again sage (Covert & Lee, ), for which points from $\mathbb{X}$ require to have their corresponding labels $y$.

###### Definition 2.1 (Feature marginalization) .

#### Background on distribution compression.

Standard sampling strategies can be inefficient. For example, the Monte Carlo estimate $\frac{1}{n}\sum^{n}_{i=1}h(\mathbf{x}^{(i)})$ of an unknown expectation $\mathbb{E}_{\mathbf{X}\sim p_{\mathbf{X}}}h(\mathbf{X})$ based on $n$ i.i.d. points has $\Theta(1/\sqrt{n})$ integration error $\big{|}\mathbb{E}_{\mathbf{X}\sim p_{\mathbf{X}}}h(\mathbf{X})-\frac{1}{n}\sum
^{n}_{i=1}h(\mathbf{x}^{(i)})\big{|}$ requiring $10^{2}$ points for 10$\%$ relative error and $10^{4}$ points for 1$\%$ error (Shetty et al., ).
To improve on i.i.d. sampling, given a sequence $\mathbb{X}$ of $n$ input points summarizing a target distribution $p_{\mathbf{X}}$, the goal of distribution compression is to identify a high quality *coreset* $\widetilde{\mathbb{X}}$ of size $\tilde{n}\ll n$.
This quality is measured with the coreset’s integration error $\big{|}\frac{1}{n}\sum^{n}_{i=1}h(\mathbf{x}^{(i)})-\frac{1}{\tilde{n}}\sum^{
\tilde{n}}_{i=1}h(\tilde{\mathbf{x}}^{(i)})\big{|}$ for functions $h$ in the reproducing kernel Hilbert space induced by a given kernel function $\mathbf{k}$ (Muandet et al., ).
The recently introduced kt algorithm (Dwivedi & Mackey, , ) returns such a coreset that minimizes the kernel maximum mean discrepancy ($\mathrm{MMD}_{\mathbf{k}}$, Gretton et al., ).

###### Definition 2.2 (Kernel maximum mean discrepancy (Gretton et al., 2012 ; Dwivedi & Mackey, 2021 ) ) .

Let $\mathbf{k}:\mathbb{R}^{d}\times\mathbb{R}^{d}\mapsto\mathbb{R}$ be a bounded kernel function with $\mathbf{k}(\mathbf{x},\cdot)$ measurable for all $\mathbf{x}\in\mathbb{R}^{d}$, e.g. a Gaussian kernel. Kernel maximum mean discrepancy between probability distributions $p,q$ on $\mathbb{R}^{d}$ is defined as $\mathrm{MMD}_{\mathbf{k}}(p,q)\coloneq\sup_{h\in\mathcal{H}_{\mathbf{k}}:\left
\lVert h\right\rVert_{\mathbf{k}}\leq 1}\big{|}\mathbb{E}_{\mathbf{X}\sim p_{
\mathbf{X}}}h(\mathbf{X})-\mathbb{E}_{\mathbf{X}\sim q_{\mathbf{X}}}h(\mathbf{
X})\big{|},$ where $\mathcal{H}_{\mathbf{k}}$ is a reproducing kernel Hilbert induced by $\mathbf{k}$.

An unbiased empirical estimate of $\mathrm{MMD}_{\mathbf{k}}$ can be relatively easily computed given a kernel function $\mathbf{k}$ (Gretton et al., ).
compress++ (Shetty et al., ) is an efficient algorithm for kt that returns a coreset of size $\sqrt{n}$ in $\mathcal{O}(n\log^{3}{n})$ time and $\mathcal{O}(\sqrt{n}\log^{2}{n})$ space, making kt viable for large datasets.
It was adapted to improve the kernel two-sample test (Domingo-Enrich et al., ).

###### Definition 2.2 (Kernel maximum mean discrepancy (Gretton et al., 2012 ; Dwivedi & Mackey, 2021 ) ) .

## 3 Compress Then Explain ( cte )

We propose using distribution compression instead of i.i.d. sampling for feature marginalization in removal-based explanations and for aggregating global explanations. We now formalize the problem and provide theoretical intuition as to why methods for distribution compression can lead to more accurate explanation estimates.

###### Definition 3.1 (Local explanation based on feature marginalization) .

A local explanation function $g(\mathbf{x};f,p_{\mathbf{X}})$ of model $f$ that relies on a distribution $p_{\mathbf{X}}$ for feature marginalization.
For estimation, it uses an empirical distribution $q_{\mathbb{X}}$ in place of $p_{\mathbf{X}}$.
Examples include shap (Lundberg & Lee, ) and expected-gradients (Erion et al., ).

Local explanations are often aggregated into global explanations based on a representative sample from data resulting in estimates of feature importance and effects.

[ht]
\VerbatimEnvironment\RecustomVerbatimEnvironmentVerbatimBVerbatim{minted}[highlightlines=2-4,highlightcolor=highlightcolor]Python
X, y, model = …
from goodpoints import compress
ids = compress.compresspp_kt(X, kernel_type=b”gaussian”, g=4)
X_compressed = X[ids]
import sage
imputer = sage.MarginalImputer(model.predict, X_compressed)
estimator = sage.KernelEstimator(imputer)
explanation = estimator(X, y)
# or even
y_compressed = y[ids]
explanation = estimator(X_compressed, y_compressed)
Code snippet showing the 3-line plug-in of distribution compression for sage estimation.

###### Definition 3.2 (Global explanation) .

A global explanation function of model $f$ that aggregates local explanations over samples from $p_{\mathbf{X}}$, i.e. $G(p_{\mathbf{X}};f,g)\coloneq\mathbb{E}_{\mathbf{X}\sim p_{\mathbf{X}}}\left[g
(\mathbf{X};f,\cdot)\right]$. Examples include feature-effects like partial dependence plots and accumulated local effects (Apley & Zhu, ), and sage (Covert et al., ), which additionally requires as an input labels $y$ of the samples drawn from $p_{\mathbf{X}}$.

Notably, the local explanation function $g$ in sage itself relies on feature marginalization leading to using $p_{\mathbf{X}}$ twice (see Listing 3). We aim to provide high quality explanations stemming from compressed samples as measured with a given approximation error.

###### Definition 3.1 (Local explanation based on feature marginalization) .

###### Definition 3.2 (Global explanation) .

#### Problem formulation.

The problem formulation in this work is straightforward:

$$ $\displaystyle\min_{\mathbb{X}^{\prime}}$ $\displaystyle\quad\big{\lVert}g(\mathbf{x};f,q_{\mathbb{X}})-g(\mathbf{x};f,q_ {\widetilde{\mathbb{X}}})\big{\rVert}\quad$ (1) $\displaystyle\mathrm{or}$ $\displaystyle\quad\big{\lVert}G(q_{\mathbb{X}};f,g)-G(q_{\widetilde{\mathbb{X} }};f,g)\big{\rVert}$ s.t. $\displaystyle\quad|\widetilde{\mathbb{X}}|=\tilde{n}\ll n$ $$

for a given $\tilde{n}$ where i.i.d. sampling or kt are the two potential algorithms to find $\widetilde{\mathbb{X}}$ in an unsupervised manner.

To formulate Propositions 3.4 & 3.5, we recall the definition of total variation distance.

###### Definition 3.3 (Total variation distance (Sriperumbudur et al., 2009 ) ) .

Total variation distance between probability distributions $p,q$ on $\mathbb{R}^{d}$ is defined as $\mathrm{TV}(p,q)\coloneq|p-q|,$ where $|p|\coloneq\int|p(x)|dx$ is the $l_{1}$ functional distance.

###### Proposition 3.4 (Feature marginalization is bounded by the total variation distance between data samples) .

For two distributions $q_{\mathbb{X}},q_{\widetilde{\mathbb{X}}}$, we have $\big{|}f(\mathbf{x}_{s};q_{\mathbb{X}})-f(\mathbf{x}_{s};q_{\widetilde{\mathbb
{X}}})\big{|}\leq C_{f}\cdot\mathrm{TV}(q_{\mathbb{X}},q_{\widetilde{\mathbb{X
}}})$, where $C_{f}$ denotes a constant that bounds the model function $f$.

Proof. Follows from (Baniecki et al., , Thm. 2). ∎

Proposition 3.4 provides a worst-case bound for feature marginalization, the backbone of local explanations, in terms of distance between the (often compressed) empirical distributions. It complements the results for input and model perturbations obtained in (Lin et al., , Lemmas 1 & 4), which also show how such bound propagates to the local explanation function $g$. Analogously, we can derive Proposition 3.5 for global aggregated explanations.

###### Proposition 3.5 (Global explanation is bounded by total variation distance between data samples) .

For two distributions $q_{\mathbb{X}},q_{\widetilde{\mathbb{X}}}$, we have $\big{\lVert}G(q_{\mathbb{X}};f,g)-G(q_{\widetilde{\mathbb{X}}};f,g)\big{\rVert
}_{1}\leq C_{g}\cdot\mathrm{TV}(q_{\mathbb{X}},q_{\widetilde{\mathbb{X}}}),$
where $C_{g}$ denotes a constant that bounds the local explanation function $g$.

Proof. See Appendix B. ∎

Effectively, Propositions 3.4 & 3.5 state that a distribution compression algorithm minimizing $\mathrm{TV}$ would restrict the approximation error of explanation estimation. Note that the empirical estimator of $\mathrm{TV}$ is not consistent and its practical estimation in high dimensions is challenging (Sriperumbudur et al., ). Thus, other metrics between distributions are often used like $\mathrm{MMD}_{\mathbf{k}}$ minimized by kt. Lemma 3.6 is a known result relating $\mathrm{MMD}_{\mathbf{k}}$ to $\mathrm{TV}$.

###### Lemma 3.6 (Theorem 21 in (Sriperumbudur et al., 2010 ) ) .

For two distributions $p,q$ on $\mathbb{R}^{d}$, we have $\mathrm{MMD}_{\mathbf{k}}(p,q)\leq\sqrt{C_{\mathbf{k}}}\cdot\mathrm{TV}(p,q),$ where $C_{\mathbf{k}}$ denotes a constant that bounds the kernel function $\mathbf{k}$.

In Section 4.2, we show experimentally that, in practical machine learning settings, minimizing $\mathrm{MMD}_{\mathbf{k}}$ leads to decreasing other distribution discrepancies like $\mathrm{TV}$. Therefore, cte has a potential to positively impact explanation estimation (Propositions 3.4 & 3.5). Since in theory it is easy to provide a counterexample for this intuition (Lemma 3.6), future work is needed on distribution compression methods with stronger guarantees.

cte is relatively simple to plug-into the current workflows for explanation estimation as shown in Listing 3 for sage. We provide analogous code listings for shap, expected-gradients and feature-effects in Appendix C.

Figure: Figure 2: compress++ with Gaussian kernel on 5 datasets for the 4 considered distribution metrics, color indicates the applied downsampling. The length of the bar is mean value $\pm$ standard error across statistical repetitions.
Refer to caption: x2.png

###### Definition 3.3 (Total variation distance (Sriperumbudur et al., 2009 ) ) .

###### Proposition 3.4 (Feature marginalization is bounded by the total variation distance between data samples) .

###### Proposition 3.5 (Global explanation is bounded by total variation distance between data samples) .

###### Lemma 3.6 (Theorem 21 in (Sriperumbudur et al., 2010 ) ) .

## 4 Experiments

In experiments, we empirically validate that the cte paradigm improves explanation estimation across 4 methods, 2 model classes, and over 50 datasets.
We compare cte to the widely adopted practice of i.i.d. sampling (see Appendix A for further motivation).
We also report sanity check results for a more deterministic baseline – sampling with k-medoids – where centroids from the clustering define a coreset from the dataset.
We use the default hyperparameters of explanation algorithms (details are provided in Appendix D.1).
For distribution compression, we use compress++ implemented in the goodpoints Python package (Dwivedi & Mackey, ), where we follow (Shetty et al., ) to use a Gaussian kernel $\mathbf{k}$ with $\sigma=\sqrt{2d}$.
For all the compared methods, the subsampled set of points is of size $\sqrt{n}$ as we leave oversampling distribution compression for future work.
We repeat all experiments where we apply some form of downsampling before explanation estimation 33 times and report the mean and standard error (se.) or deviation (sd.) of metric values.

### 4.1 Evaluation metrics

Ground truth. The goal of cte is to improve explanation estimation over the standard i.i.d. sampling. We measure the accuracy and effectiveness of explanation estimation with respect to a “ground truth” explanation that is *estimated using a full validation dataset* $\mathbb{X}$, i.e. without sampling or compression. We consider settings where this is very inefficient to compute in practice ($n\coloneq n_{\text{valid}}$ is between 1000 and 25000 samples).
For large datasets, we truncate the validation dataset to 20$\times$ the size of the compressed dataset. Since some explanation methods include a random component in the algorithm, we repeat their ground truth estimation 3 times and average the resulting explanations.

Accuracy. We are mainly interested in the accuracy of estimating a single explanation, measured by the explanation approximation error. Namely, mean absolute error (MAE), where we have $\frac{1}{n_{\text{valid}}\cdot d}\sum^{n_{\text{valid}}}_{i=1}\big{\lVert}g(
\mathbf{x}^{(i)};f,q_{\mathbb{X}})-g(\mathbf{x}^{(i)};f,q_{\widetilde{\mathbb{
X}}})\big{\rVert}_{1}$ for shap and expected-gradients, and $\frac{1}{d_{G}}\big{\lVert}G(q_{\mathbb{X}};f,g)-G(q_{\widetilde{\mathbb{X}}};
f,g)\big{\rVert}_{1}$ with $d_{G}=d$ for sage. We have $d_{G}=100\cdot(d+d^{2})$ for feature-effects, since we use 100 uniformly distributed grid points for 1-dimensional effects and 10$\times$10 uniformly distributed grid points for 2-dimensional effects (see Appendix D).
For broader context, in Section 4.4, we also measure the precision in correctly indicating the top $k$ features (the percentage a top-$k$ feature identified by the downsampled explanation is a top-$k$ feature in the ground truth).

Efficiency. We measure the efficiency of compression and estimating a single explanation with CPU wall-clock time (in seconds). We assume the time of i.i.d. sampling is 0 0. We rely on popular open-source implementations of the algorithms (see Appendix C) and perform efficiency experiments on a personal computer with an M3 chip. We acknowledge that specific time estimates will vary in more sophisticated settings, but our setup aims to imitate the most standard workflow of explanation estimation.

Distribution change. As a sanity check for cte, we show that compress++ works out-of-the-box on popular datasets for (explainable) machine learning without tuning its hyperparameters.
Measuring the similarity of distributions or datasets is challenging, and many metrics with various properties have been proposed for this task (Gibbs & Su, ). In Section 4.2, we report the following distance metrics between the original and compressed distribution: the optimized $\mathrm{MMD}_{\mathbf{k}}$, TV, Kullback–Leibler divergence (KL, Gibbs & Su, ), and n-dimensional Wasserstein distance (WD, Feydy et al., ; Laberge et al., ). Since approximating n-dimensional TV and KL is infeasible in practice, we report an average of the top-3 largest discrepancies between the 1D distributions of features.

Figure: Figure 3: Comparison between cte and i.i.d. sampling for the two estimators of shap and sage explanations on the adult dataset. We measure mean absolute error (MAE, $\downarrow$) between feature attribution and importance values, as well as the precision in correctly identifying the 5 most important features (Top-k, $\uparrow$). Analogous results for the other 4 datasets are in Appendix E. (mean $\pm$ se.)
Refer to caption: x6.png

### 4.2 Kernel thinning on machine learning datasets

First, we use the preprocessed datasets and pretrained neural network models from the OpenXAI benchmark (Agarwal et al., ). We filter out three datasets with less than 1000 observations in the validation set, where sampling is not crucial, which results in five tasks: gaussian (a synthetic dataset, $n_{\text{valid}}=1250$, $d=20$), compas ($n_{\text{valid}}=1235$, $d=7$), heloc (aka FICO, $n_{\text{valid}}=1975$, $d=23$), adult ($n_{\text{valid}}=9045$, $d=13$), and gmsc (Give Me Some Credit, $n_{\text{valid}}=20442$, $d=10$). Further details on datasets and models are provided in Appendix D.2.
In Figure 2, we observe that compress++ works much better in terms of $\mathrm{MMD}_{\mathbf{k}}$ on all datasets compared to standard i.i.d. sampling or the clustering baseline, which is no surprise as this metric is internally optimized by the former.
It also leads to notable improvements in all other metrics.
Overall, there is no consistent improvement in approximating the distribution using clustering.

### 4.3 cte as an efficient alternative to i.i.d. sampling in explanation estimation

We find cte to be a very efficient alternative to standard i.i.d. sampling in explanation estimation.
For example, compressing a distribution from 1k to 32 samples takes less than 0.1 seconds, and from 20k to 128 samples takes less than 1 second.
The exact runtime will, of course, differ based on the number of features. Figure 4 reports the wall-clock time for datasets of different sizes.
Note that the potential runtimes for distribution compression are of magnitudes smaller than the typical runtime of explanation estimation.
For example, estimating kernel-shap or permutation-sage for 1k samples using 32 background samples takes about 10 seconds, which is about 30$\times$ less than estimating the ground truth explanation (Appendix E).
Moreover, estimating kernel-shap for 9k samples using 128 background samples takes 30 minutes, which is about 60$\times$ less than estimating the ground truth explanation (Figure 3).

Figure: Figure 4: Compressing a distribution from 20k to 128 samples takes less than 1 second to compute on a CPU. (mean $\pm$ se.)
Refer to caption: x10.png

### 4.4 cte improves the accuracy of estimating feature attribution and importance explanations

We have already established that distribution compression is a viable approach to data sampling that regularly entails a better approximation of feature distribution. Moreover, its computational overhead is negligible when used for explanation estimation. We have shown that clustering is less efficient and results in higher distribution error on OpenXAI, so we omit to compare it against cte here, but will include it in further ablations in Sections 4.5 & 4.6.

Figure: Figure 5: Comparison between cte, i.i.d. sampling and clustering for expected-gradients explanations on the 4 image classificaiton datasets. We measure mean absolute error (MAE, $\downarrow$) between feature attribution values. cte is not only more accurate but also more stable as measured with standard deviation. Analogous results for the remaining 14 datasets are in Appendix F. (mean $\pm$ sd.)
Refer to caption: x11.png

We next show that cte improves the estimation of feature attribution and importance explanations, namely for shap and sage. We experiment with two model-agnostic approximators: kernel-based and permutation-based. We report the differences in MAE and Top-k between cte and standard i.i.d. sampling in Figure 3 (adult). Analogous results for the other 4 datasets from OpenXAI are in Appendix E.
On all considered tasks, cte results in a notable decrease in approximation error when compared to i.i.d. sampling and an increase in precision (for top-$k$ feature identification) with neglectable computational overhead.

### 4.5 cte improves gradient-based explanations

Here, we aim to show the broader applicability of cte by evaluating it on gradient-based explanations specific to neural networks, often fitted to larger unstructured datasets.

Sanity check.
We first compress the validation sets of IMDB and ImageNet-1k on a single CPU as a sanity check for the viability of cte in settings considering larger datasets. For the IMDB dataset ($n_{\text{valid}}=25000$, $d=768$), cte takes as an input text embeddings from the pretrained DistilBERT model’s last layer (preceding a classifier) that has a dimension of size 768. Similarly, for ImageNet-1k ($n_{\text{valid}}=50000$, $d=512$), cte operates on the hidden representation extracted from ResNet-18.
Figure 6 shows the optimized $\mathrm{MMD}_{\mathbf{k}}$ metric between the distributions and computation time in seconds.
Note that the other metrics for distribution change considered in Section 4.2 have little applicability to such datasets.
We can see, again, that proper compression results in huge benefits w.r.t. $\mathrm{MMD}_{\mathbf{k}}$ (compared to i.i.d. sampling and clustering) and only negligible computational overhead.

Accuracy and efficiency. We now study cte together with expected-gradients of neural network models trained to 18 datasets ($n_{\text{valid}}>1000$, $d\geq 32$) from the OpenML-CC18 (Bischl et al., ) and OpenML-CTR23 (Fischer et al., ) collections.
Details on datasets and models are provided in Appendix D.2.
Figure 5 shows the explanation approximation error for 4 image classification tasks, while analogous results for the remaining 14 datasets are provided in Appendix F.
Here, we vary the number of data points sampled from i.i.d. to inspect the increase in efficiency of cte.
In all cases, cte achieves on-par approximation error using less samples than i.i.d. sampling, i.e. requiring less model evaluations, resulting in faster computation and saved resources.

Model-agnostic explanation of a language model. In Appendix F, we further experiment with applying cte to improve the estimation of g-lime (Li et al., ) explaining the predictions of a DistilBERT language model trained on the IMDB dataset for sentiment analysis.

Figure: Figure 6: Left: compress++ effectively optimizes $\mathrm{MMD}_{\mathbf{k}}$ on IMDB and Imagenet-1k datasets. Right: Compressing a distribution from 25k–50k to 128 samples in 512–768 dimensions takes about 5–10 second to compute on a CPU. (mean $\pm$ se.)
Refer to caption: x12.png

Figure: Figure 7: cte improves the approximation error of local and global removal-based explanations. sage is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with “fg.”). Analogous results for the remaining estimators and 27 datasets are in Appendix G. (mean $\pm$ sd.)
Refer to caption: x14.png

### 4.6 Ablations

We perform additional experiments to evaluate cte on various datasets, with a different model class, and including another global explanation method.
More specifically, we use cte to improve feature-effects of XGBoost models trained on further 30 datasets ($n_{\text{valid}}>1000$, $d<32$) from OpenML-CC18 and OpenML-CTR23.
Details on datasets and models are provided in Appendix D.2.
Moreover, we include shap and sage in the benchmark similarly to Section 4.4.
As another ablation, sage is evaluated in two variants that consider either compressing only the background data (a rather typical scenario), or using the compressed samples as both background and foreground data (as indicated with “fg.”; refer to Listing 3 for this distinction).

Figure 8 shows the explanation approximation error for 3 predictive tasks, while analogous results for the remaining explanation estimators and 27 datasets are provided in Appendix G.
We observe that cte significantly improves the estimation of feature-effects in all cases.
We further confirm the conclusions from Sections 4.3 & 4.4 that cte improves shap and sage.
Another insight is that, on average, cte provides less improvements over i.i.d. sampling when considering compressing foreground data in sage.

Conclusion form the experiments. In Figure 8, we aggregated results from the benchmark discussed in Sections 4.5 & 4.6 to conclude the main claim that cte offers 2–3$\times$ improvements in efficiency over i.i.d. sampling.

## 5 Conclusion and Limitations

We propose *compress then explain* as a powerful alternative to the conventional *sample then explain* paradigm in explanation estimation.
cte has the potential to improve approximation error across a wide range of explanation methods for various predictive tasks.
Specifically, we show accuracy improvements in popular removal-based explanations that marginalize feature influence, and in general, global explanations that aggregate local explanations over a subset of data.
Moreover, cte leads to more efficient explanation estimation by decreasing the computational resources (time, model evaluations) required to achieve error on par with a larger i.i.d. sample size.

Future work on methods for marginal distribution compression other than kernel thinning and clustering might bring additional improvements in the performance of explanation estimation.
Distribution compression methods, by design, have hyperparameters that may impact the empirical results.
Although we have shown that the default compress++ algorithm is a robust baseline, exploring the tunability of its hyperparameters is a natural future work direction (similarly as in the case of conditional sampling methods, Olsen et al., ).
Especially for tabular datasets, dealing with categorical features can be an issue, which we elaborate on in Appendix D.2.
For supervised learning, a stratified variant of kernel thinning taking into account a distribution of the target feature could further improve loss-based explanations like sage, or even the estimation of group fairness metrics.

#### Broader impact.

In general, improving explanation methods has positive implications for humans interacting with AI systems (Rong et al., ). But, specifically in the context of this work, biased sampling can be exploited to manipulate the explanation results (Slack et al., ; Baniecki & Biecek, ; Laberge et al., ). cte could minimize the risk of such adversaries and prevent “random seed/state hacking” based on the rather unstable i.i.d. sampling from data in empirical research (Herrmann et al., ).

#### Reproducibility.

Code to reproduce all experiments in this paper is available on GitHub at [https://github.com/hbaniecki/compress-then-explain](https://github.com/hbaniecki/compress-then-explain).

#### Acknowledgements.

This work was financially supported by the Polish National Science Centre grant number 2021/43/O/ST6/00347. Hubert Baniecki gratefully acknowledges scholarship funding from the Polish National Agency for Academic Exchange under the Preludium Bis NAWA 3 programme.

[Uncaptioned image]: x19.png

## Appendix for “Efficient and Accurate Explanation Estimation with Distribution Compression”

In Appendix B, we derive a proof for Proposition 3.5. Appendix C provides code listings for shap, expected-gradients and feature-effects, analogous to Listing 3 for sage. Additional details on the experimental setup are provided in Appendix D. Appendices E, F & G report results for the remaining datasets.

## Appendix A Motivation: standard i.i.d. sampling in explanation estimation

We find that i.i.d. sampling from datasets is a heuristic often used (and overlooked) in various estimators of post-hoc explanations. Our work aims to first quantify the approximation error introduced by *sample then explain*, and then propose a method to efficiently reduce it. Below are a few examples from the literature on explainability that motivate the shift to our introduced *compress then explain* paradigm.

In (Laberge et al., ), we read “*For instance, when a dataset is used to represent a background distribution, explainers in the SHAP library such as the ExactExplainer and TreeExplainer will subsample this dataset by selecting 100 instances uniformly at random when the size of the dataset exceeds 100.*”

In (Chen & Sun, ), we read “*[Footnote 1.] We use a random subset of samples for each class in the real implementation, to reduce the computation costs of clustering.*”

In (Ghalebikesabi et al., ), we read “*After training a convolutional neural network on the MNIST dataset, we explain digits with the predicted label 8 given a background dataset of 100 images with labels 3 and 8.*”, as well as “*Feature attributions are sorted by similarity according to a preliminary PCA analysis across a subset of 2000 samples from the Adult Income dataset, using 2000 reference points.*”

In (Erion et al., ), we read “*During training, we let k be the number of samples we draw to compute expected gradients for each mini-batch.* and “*This expectation-based formulation lends itself to a natural, sampling based approximation method: (1) draw samples of $x^{\prime}$ from the training dataset […], (2) compute the value inside the expectation for each sample and (3) average over samples.*”

In (Van Looveren & Klaise, ), we read “*We also need a representative, unlabeled sample of the training dataset.*”, and in Algorithms 1 and 2: “*A sample
$X=\{x_{1},\ldots,x_{n}\}$ from training set.*”

In (Covert et al., ), we read “*When calculating feature importance, our sampling approximation for SAGE (Algorithm 1) was run using draws from the marginal distribution. We used a fixed set of 512 background samples for the bank, bike and credit datasets, 128 for MNIST, and all 334 training examples for BRCA.*”

In the shap Python package (Lundberg & Lee, ), there is a warning saying “*Using 110 background data samples could cause slower run times. Consider using shap.sample(data, K) or shap.kmeans(data, K) to summarize the background as K samples.*”, and the documentation mentions “*For small problems, this background dataset can be the whole training set, but for larger problems consider using a single reference value or using the kmeans function to summarize the dataset.*”

## Appendix B Proof

Below, we derive a proof for Proposition 3.5.

###### Proposition B.1 (Global explanation is bounded by total variation distance between data samples) .

For two distributions $q_{\mathbb{X}},q_{\widetilde{\mathbb{X}}}$, we have $\big{\lVert}G(q_{\mathbb{X}};f,g)-G(q_{\widetilde{\mathbb{X}}};f,g)\big{\rVert
}_{1}\leq C_{g}\cdot\mathrm{TV}(q_{\mathbb{X}},q_{\widetilde{\mathbb{X}}}),$
where $C_{g}$ denotes a constant that bounds the local explanation function $g$.

###### Proof.

For two probability distributions $p_{\mathbf{X}},q_{\mathbf{X}}$, we have

$$ $\displaystyle\big{\lVert}G(p_{\mathbf{X}};f,g)-G(q_{\mathbf{X}};f,g)\big{ \rVert}_{1}$ $\displaystyle=\big{\lVert}\mathbb{E}_{\mathbf{X}\sim p_{\mathbf{X}}}\left[g( \mathbf{X};f,\cdot)\right]-\mathbb{E}_{\mathbf{X}\sim q_{\mathbf{X}}}\left[g( \mathbf{X};f,\cdot)\right]\big{\rVert}_{1}$ (2) $\displaystyle=\left\lVert\int g(\mathbf{x})p_{\mathbf{X}}(\mathbf{x})d\mathbf{ x}-\int g(\mathbf{x})q_{\mathbf{X}}(\mathbf{x})d\mathbf{x}\right\rVert_{1}$ (3) $\displaystyle=\left\lVert\int g(\mathbf{x})\big{(}p_{\mathbf{X}}(\mathbf{x})-q _{\mathbf{X}}(\mathbf{x})\big{)}d\mathbf{x}\right\rVert_{1}$ (4) $\displaystyle\leq\int\big{\lVert}g(\mathbf{x})\big{(}p_{\mathbf{X}}(\mathbf{x} )-q_{\mathbf{X}}(\mathbf{x})\big{)}\big{\rVert}_{1}d\mathbf{x}$ (5) $\displaystyle=\int\big{\lVert}g(\mathbf{x})\big{\rVert}_{1}\cdot\big{|}p_{ \mathbf{X}}(\mathbf{x})-q_{\mathbf{X}}(\mathbf{x})\big{|}d\mathbf{x}$ (6) $\displaystyle\leq\int C_{g}\cdot\big{|}p_{\mathbf{X}}(\mathbf{x})-q_{\mathbf{X }}(\mathbf{x})\big{|}d\mathbf{x}$ (7) $\displaystyle=C_{g}\cdot\int\big{|}p_{\mathbf{X}}(\mathbf{x})-q_{\mathbf{X}}( \mathbf{x})\big{|}d\mathbf{x}$ (8) $\displaystyle=C_{g}\cdot\mathrm{TV}(p_{\mathbf{X}},q_{\mathbf{X}}).$ (9) $$

Substituting with empirical distributions, we have $\big{\lVert}G(q_{\mathbb{X}};f,g)-G(q_{\widetilde{\mathbb{X}}};f,g)\big{\rVert
}_{1}\leq C_{g}\cdot\mathrm{TV}(q_{\mathbb{X}},q_{\widetilde{\mathbb{X}}})$.
∎

###### Proposition B.1 (Global explanation is bounded by total variation distance between data samples) .

###### Proof.

## Appendix C Implementing cte in practice

cte is relatively simple to plug-into the current workflows for explanation estimation as shown in Listing C for shap, Listing C for expected-gradients, and Listing C for feature-effects. We use the goodpoints Python package (Dwivedi & Mackey, , MIT license).

[ht]
\VerbatimEnvironment\RecustomVerbatimEnvironmentVerbatimBVerbatim{minted}[highlightlines=2-4,highlightcolor=highlightcolor]Python
X, model = …
from goodpoints import compress
ids = compress.compresspp_kt(X, kernel_type=b”gaussian”, g=4)
X_compressed = X[ids]
import shap
masker = shap.maskers.Independent(X_compressed)
explainer = shap.PermutationExplainer(model.predict, masker)
explanation = explainer(X)
Code snippet showing the 3-line plug-in of distribution compression for shap estimation.

[ht]
\VerbatimEnvironment\RecustomVerbatimEnvironmentVerbatimBVerbatim{minted}[highlightlines=2-4,highlightcolor=highlightcolor]Python
X, model = …
from goodpoints import compress
ids = compress.compresspp_kt(X, kernel_type=b”gaussian”, g=4)
X_compressed = X[ids]
import captum
explainer = captum.attr.IntegratedGradients(model)
import torch
inputs = torch.as_tensor(X)
baselines = torch.as_tensor(X_compressed)
explanation = torch.mean(torch.stack([
explainer.attribute(inputs, baselines[[i]], target=1)
for i in range(baselines.shape[0])
]), dim=0)
Code snippet showing the plug-in of distribution compression for expected-gradients.

[ht]
\VerbatimEnvironment\RecustomVerbatimEnvironmentVerbatimBVerbatim{minted}[highlightlines=2-4,highlightcolor=highlightcolor]Python
X, model = …
from goodpoints import compress
ids = compress.compresspp_kt(X, kernel_type=b”gaussian”, g=4)
X_compressed = X[ids]
import alibi
explainer = alibi.explainers.PartialDependence(predictor=model.predict)
explanation = explainer.explain(X_compressed)
Code snippet showing the plug-in of distribution compression for feature-effects.

## Appendix D Experimental setup

### D.1 Explanation hyperparameters

In Section 4, we experiment with 4 explanation methods (6 estimators). Without the loss of generality, in case of classification models, we always explain a prediction for the 2nd class. For shap, we use the kernel-shap and permutation-shap implementations from the shap Python package (Lundberg & Lee, , MIT license) with default hyperparameters (notably, npermutations=10 in the latter). For sage, we use the kernel-sage and permutation-sage implementations from the sage Python package (Covert et al., , MIT license). We use default hyperparameters; notably, a cross-entropy loss for classification and mean squared error for regression. For expected-gradients, we aggregate with mean the integrated gradients explanations from the captum Python package (Kokhlikyan et al., , BSD-3 license), for which we use default hyperparameters; notably, n_steps=50 and method="gausslegendre". For feature-effects, we implement the partial dependence algorithm (Apley & Zhu, ; Moosbauer et al., ) ourselves for maximum computational speed in case of 2-dimensional plots, mimicking the popular open-source implementations.(^1^11[https://docs.seldon.io/projects/alibi/en/latest/api/alibi.explainers.html#alibi.explainers.PartialDependence](https://docs.seldon.io/projects/alibi/en/latest/api/alibi.explainers.html#alibi.explainers.PartialDependence); [https://interpret.ml/docs/python/api/PartialDependence](https://interpret.ml/docs/python/api/PartialDependence)) We use 100 uniformly distributed grid points for 1-dimensional plots and 10$\times$10 uniformly distributed grid points for 2-dimensional plots.

### D.2 Details on datasets and models

Table 1 shows details of datasets from the OpenXAI (Agarwal et al., , MIT license) benchmark used in Sections 4.2, 4.3 & 4.4. To each dataset, there is a pretrained neural network with an accuracy of 92% (gaussian), 85% (compas), 74% (heloc), 85% (adult) and 93% (gmsc). We do not further preprocess data; notably, feature values are already scaled to $[0,1]$.

**Table 1: Datasets from OpenXAI with $n_{\text{valid}}>1000$ used in experiments.**
| Dataset | $n_{\text{train}}$ | $n_{\text{valid}}$ | $d$ | No. classes |
| --- | --- | --- | --- | --- |
| gaussian | 3750 | 1250 | 20 | 2 |
| compas | 4937 | 1235 | 7 | 2 |
| heloc | 7896 | 1975 | 23 | 2 |
| adult | 36177 | 9045 | 13 | 2 |
| gmsc | 81767 | 20442 | 10 | 2 |

**Table 2: Datasets from OpenML-CC18 and OpenML-CTR23 with $n_{\text{valid}}>1000$ used in experiments.**
| Dataset | Task ID | $n_{\text{train}}$ | $n_{\text{valid}}$ | $d$ | No. classes |
| --- | --- | --- | --- | --- | --- |
| phoneme | 9952 | 4053 | 1351 | 5 | 2 |
| wilt | 146820 | 3629 | 1210 | 5 | 2 |
| cps88wages | 361261 | 21116 | 7039 | 6 | – |
| jungle_chess | 167119 | 33614 | 11205 | 6 | 3 |
| abalone | 361234 | 3132 | 1045 | 8 | – |
| electricity | 219 | 33984 | 11328 | 8 | 2 |
| kin8nm | 361258 | 6144 | 2048 | 8 | – |
| california_housing | 361255 | 15480 | 5160 | 8 | – |
| brazilian_houses | 361267 | 8019 | 2673 | 9 | – |
| diamonds | 361257 | 40455 | 13485 | 9 | – |
| physiochemical_protein | 361241 | 34297 | 11433 | 9 | – |
| white_wine | 361249 | 3673 | 1225 | 11 | – |
| health_insurance | 361269 | 16704 | 5568 | 11 | – |
| grid_stability | 361251 | 7500 | 2500 | 12 | – |
| adult | 7592 | 36631 | 12211 | 14 | 2 |
| naval_propulsion_plant | 361247 | 8950 | 2984 | 14 | – |
| miami_housing | 361260 | 10449 | 3483 | 15 | – |
| letter | 6 | 15000 | 5000 | 16 | 26 |
| bank-marketing | 14965 | 33908 | 11303 | 16 | 2 |
| pendigits | 32 | 8244 | 2748 | 16 | 10 |
| video_transcoding | 361252 | 51588 | 17196 | 18 | – |
| churn | 167141 | 3750 | 1250 | 20 | 2 |
| kings_county | 361266 | 16209 | 5404 | 21 | – |
| numerai28.6 | 167120 | 72240 | 24080 | 21 | 2 |
| sarcos | 361254 | 36699 | 12234 | 21 | – |
| cpu_activity | 361256 | 6144 | 2048 | 21 | – |
| jm1 | 3904 | 8163 | 2722 | 21 | 2 |
| wall-robot-navigation | 9960 | 4092 | 1364 | 24 | 4 |
| fifa | 361272 | 14383 | 4795 | 28 | – |
| PhishingWebsites | 14952 | 8291 | 2764 | 30 | 2 |
| pumadyn32nh | 361259 | 6144 | 2048 | 32 | – |
| GestureSegmentation | 14969 | 7404 | 2469 | 32 | 5 |
| satimage | 2074 | 4822 | 1608 | 36 | 6 |
| texture | 125922 | 4125 | 1375 | 40 | 11 |
| connect-4 | 146195 | 50667 | 16890 | 42 | 3 |
| fps_benchmark | 361268 | 18468 | 6156 | 43 | – |
| wave_energy | 361253 | 54000 | 18000 | 48 | – |
| theorem-proving | 9985 | 4588 | 1530 | 51 | 6 |
| spambase | 43 | 3450 | 1151 | 57 | 2 |
| optdigits | 28 | 4215 | 1405 | 64 | 10 |
| superconductivity | 361242 | 15947 | 5316 | 81 | – |
| nomao | 9977 | 25848 | 8617 | 118 | 2 |
| har | 14970 | 7724 | 2575 | 561 | 6 |
| isolet | 3481 | 5847 | 1950 | 617 | 26 |
| mnist_784 | 3573 | 52500 | 17500 | 784 | 10 |
| Fashion-MNIST | 146825 | 52500 | 17500 | 784 | 10 |
| Devnagari-Script | 167121 | 69000 | 23000 | 1024 | 46 |
| CIFAR_10 | 167124 | 45000 | 15000 | 3072 | 10 |

Table 2 shows details of datasets from the OpenML-CC18 (Bischl et al., , BSD-3 license) and OpenML-CTR23 (Fischer et al., , BSD-3 license) benchmarks used in Sections 4.5 & 4.6. We first split all datasets in 75:25 (train:validation) ratio and left 48 datasets with $n_{\text{valid}}>1000$ for our experiments. For the 30 smaller ($d<32$) datasets, we train an XGBoost model with default hyperparameters (200 estimators) and explain it with shap, sage, feature-effects. For the 18 bigger ($d\geq 32$) datasets, we train a 3-layer neural network model with (128, 64) neurons in hidden ReLU layers and explain it with expected-gradients. We perform basic preprocessing of data: (1) remove features with a single or $n$ unique values, (2) target encode categorical features, (3) impute missing values with mean, and (4) standardize features.

In general, categorical features can be an issue for clustering and distribution compression algorithms; so are for many explanation algorithms and conditional distribution samplers. Although target encoding worked well in our setup, we envision two additional heuristics to deal with categorical features: (1) perform distribution compression using a dataset restricted to non-categorical features, (2) target encode categorical features only for distribution compression.

### D.3 Compute resources

Results described in Sections 4.2–4.4 and Figure 6 were computed on a personal computer with an M3 chip as justified in Section 4.1. Benchmark described in Sections 4.5 & 4.6 was computed on a cluster with 4 AMD Rome 7742 CPUs (256 cores) and 4 TB of RAM for about 12 days combined.

## Appendix E cte improves the accuracy of estimating removal-based explanations

We report the differences in MAE and Top-k between cte and i.i.d. sampling in
Figure 10 (compas),
Figure 10 (heloc), Figure 12 (gmsc) and Figure 12 (gaussian). On all the considered tasks, cte offers a notable decrease in approximation error of shap and sage with neglectable computational overhead (as measured by time in seconds).

Figure: Figure 9: Extended Figure 3. cte improves shap and sage estimation by using the compressed samples as background data for the compas dataset. We measure mean absolute error (MAE, $\downarrow$) between feature attribution and importance values, as well as the precision in correctly indicating the 3 most important features (Top-k, $\uparrow$). Computational resources required to compress a distribution are neglectable in the context of explanation estimation. (mean $\pm$ se.)
Refer to caption: x20.png

Figure: Figure 11: Extended Figure 3. cte improves shap and sage estimation by using the compressed samples as background data for the gmsc dataset. We measure mean absolute error (MAE, $\downarrow$) between feature attribution and importance values, as well as the precision in correctly indicating the 5 most important features (Top-k, $\uparrow$). Computational resources required to compress a distribution are neglectable in the context of explanation estimation. (mean $\pm$ se.)
Refer to caption: x28.png

## Appendix F cte improves gradient-based explanations specific to neural networks

Figure 13 shows the expected-gradients approximation error for 18 datasets. In all cases, cte achieves on-par approximation error using less samples than i.i.d. sampling, i.e. requiring less model evaluations, resulting in faster computation and saved resources.

Figure: Figure 13: Extended Figure 5. cte improves the approximation error of gradient-based explanations specific to neural networks. It is not only more accurate, but also more stable as measured with standard deviation. (mean $\pm$ sd.)
Refer to caption: x36.png

#### Model-agnostic explanation of a language model.

We further experimented with applying cte to improve the estimation of global aggregated lime (Ribeiro et al., ), aka g-lime (Li et al., ), which is a more complex setup that we leave for future work. We aim to explain the predictions of a DistilBERT language model(^2^22[https://huggingface.co/dfurman/distilbert-base-uncased-imdb](https://huggingface.co/dfurman/distilbert-base-uncased-imdb)) trained on the IMDB dataset(^3^33[https://huggingface.co/datasets/stanfordnlp/imdb](https://huggingface.co/datasets/stanfordnlp/imdb)) for sentiment analysis. We calculate lime with $k=10$ for all samples from the validation set using an A100 GPU and aggregate these local explanations into global token importance with a mean of absolute normalized values (Li et al., ), which is the “ground truth” explanation. We then compress the set with i.i.d. sampling, cte, and clustering based on the inputs’ text embeddings from the model’s last layer (preceding a classifier) that has a dimension of size 768. Figure 14 shows results for explanation approximation error and an exemplary comparison between the explanations relating to Figure 1. To obtain these results, we used $8\times$ more samples than the typical compression scenario (still $25\times$ less than the full sample) so as to overcome the issue of rare tokens skewing the results. It becomes challenging to compute the distance between the ground truth and approximated explanations as the latter contains significantly less tokens (features), as opposed to previous experiments where these two explanations always had equal dimensions. Thus, MAE becomes biased towards sparse explanations and popular tokens, i.e. an explanation with a single token of well approximated importance could have an error close to 0. For context, we measure $\mathrm{TV}$ between the discrete distributions of tokens in local explanations before the global aggregation (lower is better). We report results for different token cutoffs, where we remove the rarely occurring tokens from the ground truth explanation, which saturates at 5% tokens left.

Figure: Figure 14: cte for g-lime of a DistilBERT model classifying IMDB reviews. A) It is not obvious how to measure the distance between global explanations containing different sets of tokens (Token coverage in % w.r.t. ground truth, $\uparrow$). Therefore, we gradually remove rare tokens from the measurement based on their occurrence in the ground truth explanation (Token cutoff in quantiles). B) Measurement of mean absolute error (MAE, $\downarrow$) between aggregated global explanations. C) Measurement of total variation distance ($\mathrm{TV}$, $\downarrow$) between token occurrences in local explanations before global aggregation. D) We show an exemplary “worst-case” explanation, i.e. with the lowest MAE for cutoff 0.95 where token coverage is over 99%, for both cte and i.i.d. sampling. For this visualization, we only show the importance of the 5 most positive/negative tokens, and 5 tokens with the importance closest to zero. Explanation approximation error is indicated with transparent bars. Notably, i.i.d. sampling misses containing any input with an important token “superbly”, while cte misses “disgrace”. Sampling overestimates the global importance of tokens “disappointing”, “into” and “get”, while cte, for example, overestimates “than” and underestimates “tedious” or “delightful”.
Refer to caption: x37.png

## Appendix G Ablations

Figures 15–23 report the explanation approximation error for 30 predictive tasks. We observe that cte significantly improves the estimation of feature-effects in all cases. Another insight is that, on average, cte provides less improvements over i.i.d. sampling when considering compressing foreground data in sage.

Figure: Figure 15: Extended Figure 8 (1/10). cte improves the explanation approximation error of various local and global removal-based explanations. sage is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with “fg.”). (mean $\pm$ sd.)
Refer to caption: x38.png

Figure: Figure 16: Extended Figure 8 (2/10). cte improves the explanation approximation error of various local and global removal-based explanations. sage is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with “fg.”). (mean $\pm$ sd.)
Refer to caption: x41.png

Figure: Figure 17: Extended Figure 8 (3/10). cte improves the explanation approximation error of various local and global removal-based explanations. sage is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with “fg.”). (mean $\pm$ sd.)
Refer to caption: x44.png

Figure: Figure 18: Extended Figure 8 (4/10). cte improves the explanation approximation error of various local and global removal-based explanations. sage is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with “fg.”). (mean $\pm$ sd.)
Refer to caption: x47.png

Figure: Figure 19: Extended Figure 8 (5/10). cte improves the explanation approximation error of various local and global removal-based explanations. sage is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with “fg.”). (mean $\pm$ sd.)
Refer to caption: x50.png

Figure: Figure 20: Extended Figure 8 (6/10). cte improves the explanation approximation error of various local and global removal-based explanations. sage is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with “fg.”). (mean $\pm$ sd.)
Refer to caption: x53.png

Figure: Figure 21: Extended Figure 8 (7/10). cte improves the explanation approximation error of various local and global removal-based explanations. sage is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with “fg.”). (mean $\pm$ sd.)
Refer to caption: x56.png

Figure: Figure 22: Extended Figure 8 (8/10). cte improves the explanation approximation error of various local and global removal-based explanations. sage is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with “fg.”). (mean $\pm$ sd.)
Refer to caption: x59.png

Figure: Figure 23: Extended Figure 8 (9/10). cte improves the explanation approximation error of various local and global removal-based explanations. sage is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with “fg.”). (mean $\pm$ sd.)
Refer to caption: x62.png

Figure: Figure 24: Extended Figure 8 (10/10). cte improves the explanation approximation error of various local and global removal-based explanations. sage is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with “fg.”). (mean $\pm$ sd.)
Refer to caption: x65.png

## Peer Reviews

confidence: 5
contribution: 3
initial_rating: 3
presentation: 2
questions: line 184 - definition 4 - it is not clear what is the output f this function and how do you compare it with for calculation of MAE. how the explanation error is defined and how it is calculated? as far as I understand the mean absolute error is measured based on the difference between the assigned values to  features of explanation from the SHAP  with iid and CTE. but to it is not clear that without iid how do you calculate the feature values. if SHAP + i.i.d sampling is not the baseline, the please clearly explain how you calculated the baseline feature values? what is the baseline for that you compared the iid and cte sampling? (Table 1)
soundness: 3
strengths: This approach significantly reduces the computational complexity of SHAP and SAGE.
summary: the paper introduces CTE uses distribution compression through kernel thinning to obtain a data sample to better and more efficiently approximate the marginal distribution. This method is recommend to significantly reduce the computational complexity of attribution-based methods such as SHAP and SAGE.
weaknesses: line 53 - "We introduce a new paradigm for estimating post-hoc explanations based on a marginal distribution" ---> The main contribution of paper is not clearly described. From the introduction, reader might get the idea that you are proposing a new explanation method that employs KT, but as we go further into the paper, the tone of authors changes and they focus on the effectiveness their approach for Kernel SHAP and SAGE. 


the idea of this paper needs to be more clearly stated. From my understanding the paper attempts to improve the computation time of SHAP and SAGE using Kernel thinning. The Kernel Thinning is proposed to better select the samples for the feature attribution explanation. The idea seems interesting and this can help with the Shapely and Sage method, but this approach is only specific to these explanation method that are based on the selection of subsets of data. 

The experimental evaluation is heavily focused on MAE with  the explanation as "...". I wonder if this approach is the main criteria that paper investigated, what is the main baseline that they compare with to obtain the explanation error. If the explanation error is calculated with the SHAP with the iid sampling, so what does Table 1 mean. because in this table the paper explains that from the iid sampling the MAE of explain improved to something that is achieved with CTE.


Also the paper only explored the Gaussian Kernel. Why that choice? why not exploring other kernels? What is the theoretical aspect of Gaussian that advantages your approach?

also, I wanted to see some examples of how the trained explainer using your method performs for image and examples of IMDB dataset. The paper heavily focuses on the MAE without providing any example to show the qualitative comparison of generated explanation


The main purpose of KT, is reducing the computational complexity and the quality of generated explanation, but since this method is focused on the data attribution concept, I was expecting see a comparison between the KT and Influence Function in extracted explanations.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: -
soundness: 3
strengths: - The proposed method is solid and supported by theoretical bounds on the error.

- This topic is outside my expertise but I was able to follow the paper. So I think the authors did a good job summarizing the related work and providing relevant background information.
summary: The paper proposes distribution compression as an alternative to iid sampling for explanation estimation. The proposed approach is supported by theoretical guarantees. It also improves computation cost while still achieving errors comparable with iid sample empirically.
weaknesses: - I overall enjoyed reading this paper. 

- I am not an expert on this area. But it looks like going from iid sampling (the paper's main comparison point) to this more complicated CTE framework (based on kernel thinning) is a big step. I am wondering if there are any other baselines in between these two extremes. For instance, a sampling strategy but not exactly uniform? If there are such baselines, I think it would be good to see a comparison against them too to understand the tradeoff between how complicated the compression scheme is vs how much we can reduce the data size vs the error.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: I'd be interested in hearing the authors' thoughts on the second "weakness" above.
soundness: 3
strengths: The paper is well written. The biggest strength of the paper is the thoroughness of the experiments. For a paper that is largely an empirical demonstration it is great to see the rigour that clearly went in to the experiment section. The proposal is a neat application of an existing technique in a new domain.
summary: This paper tackles the problem of efficiently approximating the marginal distribution that is often used in post hoc explanation methods. The authors propose using kernel thinning to obtain a compressed sample of the "background" samples that are used to empirically estimate the marginalization. The proposed compress then explain method is then empirically demonstrated to require orders of mangitude fewer samples to achieve on-par explanation approximation error compared to i.i.d sampling which is generally utilized.
weaknesses: While the experiment section is rigorously presented, there's room for improvement in presentation - specifically the figures and figure captions. Most of the figures have multiple plots and a single caption. It'd be better to label the sub-plots in each figure as a, b, c,... and then use the caption to describe each figure succinctly. This allows the reader to look at the figures and understand them, rather than having to jump back and forth between the main text and figures.

The other weakness is the fact that this is largely an application of an existing method for efficient sampling. It *is* still a useful contribution to apply this method to explanations, this could be an even better publication if the sampling method was also improved specifically for post explanation methods.

Meta-review: The paper introduces a compress-and-explain scheme to speedup attribution calculation. The reviewers are largely in agremeent that the proposed method is worthy of publication.

Decision: Accept (Spotlight)