Efficient and Accurate Explanation Estimation with Distribution Compression

Authors: Hubert Baniecki, Giuseppe Casalicchio, Bernd Bischl, Przemyslaw Biecek
Primary area: interpretability and explainable AI
Keywords: explainable ai, feature attributions, feature importance, sampling, kernel thinning

Abstract:
We discover a theoretical connection between explanation estimation and distribution compression that significantly improves the approximation of feature attributions, importance, and effects. While the exact computation of various machine learning explanations requires numerous model inferences and becomes impractical, the computational cost of approximation increases with an ever-increasing size of data and model parameters. We show that the standard i.i.d. sampling used in a broad spectrum of algorithms for post-hoc explanation leads to an approximation error worthy of improvement. To this end, we introduce Compress Then Explain (CTE), a new paradigm of sample-efficient explainability. It relies on distribution compression through kernel thinning to obtain a data sample that best approximates its marginal distribution. CTE significantly improves the accuracy and stability of explanation estimation with negligible computational overhead. It often achieves an on-par explanation approximation error 2-3x faster by using fewer samples, i.e. requiring 2-3x fewer model evaluations. CTE is a simple, yet powerful, plug-in for any explanation method that now relies on i.i.d. sampling.

Decision: accept (spotlight)
Reviewer scores: 6, 8, 8

Reviews and discussion:
<thread>
creation date:
1729705618113

thread_type:
official_review

<thread_object>
creator: reviewer_db4i

<content>
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.

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.

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.

questions:
I'd be interested in hearing the authors' thoughts on the second "weakness" above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730505308790

thread_type:
official_review

<thread_object>
creator: reviewer_ry7y

<content>
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.

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.

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.

questions:
-
</content>
</thread_object>

</thread>
<thread>
creation date:
1730649855104

thread_type:
official_review

<thread_object>
creator: reviewer_fa33

<content>
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.

strengths:
This approach significantly reduces the computational complexity of 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.

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)
</content>
</thread_object>

</thread>
<thread>
creation date:
1731704584209

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response by Authors

comment:
**We gratefully thank the anonymous reviewers for their time and effort in reviewing our paper.** We are excited about the appreciation of our work and the valuable feedback to improve it. In separate comments, we provide point-by-point responses to each of the reviews. 

Here, we additionally list all the changes made in the edited version of the manuscript, **denoted in green text**.

As suggested by **Reviewer fa33**:

1. We rephrased the original sentence in **lines 53 & 74** from "We introduce a new paradigm for estimating post-hoc explanations based on a marginal distribution compressed more effectively than with i.i.d. sampling." to "We introduce a new paradigm of sample-efficient explainability where post-hoc explanations, like feature attributions and effects, are estimated based on a marginal distribution compressed more efficiently than with i.i.d. sampling."
2. We added a comment on alternative kernel functions in **lines 522–526**: "We used the Gaussian kernel because it is the standard in the field of distribution compression (Dwivedi & Mackey, 2022; Shetty et al., 2022; Domingo-Enrich et al., 2023), especially in experimental analysis, and is generally adopted within machine learning applications. Although our empirical validation shows that the Gaussian kernel works well for over 50 datasets, exploring other kernels for which theoretical thinning error bounds exist, like Matern or B-spline (Dwivedi & Mackey, 2021), is a viable future work direction."

As suggested by **Reviewer dB4i**:

3. We labeled sub-plots as “A), B), C), …” and extended the captions in **Figures 2, 4, 6 & 8** to improve the presentation.
</content>
</thread_object>

</thread>


Metareview:
metareview:
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.