Research map / Learning theory and algorithms / Sample complexity
Efficient and Accurate Explanation Estimation with Distribution Compression
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes compress-then-explain (CTE), which replaces i.i.d. background/foreground sampling in explanation estimation with kernel-thinning distribution compression (COMPRESS++), reducing approximation error and variance and needing 2-3x fewer model evaluations.
Problem
Explanation estimators (SHAP, SAGE, expected gradients, feature effects) approximate marginal feature distributions by i.i.d. sampling from the dataset, which introduces approximation error and instability that can even change feature importance rankings.
Approach
Connects explanation estimation error to MMD between empirical distributions, showing that minimizing MMD (via kernel thinning) bounds feature marginalization and global explanation error; thus a compressed subset chosen by COMPRESS++ is a drop-in replacement for i.i.d. sampling.
Key results
- On OpenXAI tasks, CTE reduces MAE of kernel-shap, permutation-shap, kernel-sage, and permutation-sage by roughly 20-45% and std by about 50% relative to i.i.d. sampling.
- For expected gradients, CTE reduces error by 35% on mnist_784, 40% on Fashion-MNIST, and 21% on CIFAR_10 (p<1e-10), achieving 2-3x sample efficiency.
- Compressing 20k points to 128 samples takes under 1 second on CPU.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace i.i.d. background sampling with CTE for Kernel-SHAP | Kernel-SHAP · Adult | MAE: 73 -> 58 | Helped |
| Replace i.i.d. background sampling with CTE for Permutation-SHAP | Permutation-SHAP · Compas | MAE: 11 -> 6 | Helped |
| Replace i.i.d. background sampling with CTE for Kernel-SAGE | Kernel-SAGE · Gaussian | MAE: 52 -> 30 | Helped |
| Replace i.i.d. background sampling with CTE for Permutation-SAGE | Permutation-SAGE · GMSC | MAE: 28 -> 16 | Helped |
| Replace i.i.d. background sampling with CTE for Kernel-SHAP | Kernel-SHAP · HELOC | MAE: 67 -> 41 | Helped |
| Replace i.i.d. sampling with CTE for expected gradients | Expected Gradients · mnist_784 | MAE: 35% | Helped |
| Replace i.i.d. sampling with CTE for expected gradients | Expected Gradients · Fashion-MNIST | MAE: 40% | Helped |
| Replace i.i.d. sampling with CTE for expected gradients | Expected Gradients · CIFAR_10 | MAE: 21% | Helped |
| Use compressed samples as both background and foreground instead of compressing only background data (ablation) | SAGE · 30 OpenML tasks | MAE | Mixed |
| Use kernel thinning (CTE) instead of k-medoids clustering | Explanation estimation · OpenXAI datasets | MAE | Helped |
Surprising findings
- Clustering (k-medoids) often yields higher explanation error than i.i.d. sampling, since it does not consistently improve distribution approximation.
Limitations
- Fixed subset size sqrt(n) and default Gaussian kernel; hyperparameter tuning and oversampling left for future work
- Categorical features are problematic for distribution compression and explanation methods
- Language model experiment (G-LIME on DistilBERT) uses 8x more samples and MAE is biased toward sparse explanations
Experimental setup
Datasets: OpenXAI (gaussian, compas, heloc, adult, gmsc) OpenML-CC18 OpenML-CTR23 IMDB ImageNet-1k
Benchmarks: OpenXAI datasets OpenML-CC18 OpenML-CTR23 IMDB ImageNet-1k
Metrics: mean absolute error standard deviation of MAE top-k precision MMD total variation KL divergence Wasserstein distance wall-clock time
Baselines: i.i.d. sampling k-medoids clustering kernel-shap permutation-shap kernel-sage permutation-sage
Builds on: kernel thinning COMPRESS++ SHAP SAGE expected gradients
Closest papers by meaning
- Selective Explanations (NeurIPS 2024 · similarity 0.88)
- Provably Better Explanations with Optimized Aggregation of Feature Attributions (ICML 2024 · similarity 0.86)
- Saliency strikes back: How filtering out high frequencies improves white-box explanations (ICML 2024 · similarity 0.85)
- Geometry-Adaptive Explainer for Faithful Dictionary-Based Interpretability under Distribution Shift (NeurIPS 2026 · similarity 0.85)
- Data-centric Prediction Explanation via Kernelized Stein Discrepancy (ICLR 2025 · similarity 0.85)
- Explainable Neural Networks with Guarantee: A Sparse Estimation Approach (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.