Research map / Learning theory and algorithms / Prediction and decision losses
SHAP@k: Efficient and Probably Approximately Correct (PAC) Identification of Top-K Features
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.
Frames top-k SHAP feature identification as an Explore-m bandit problem and adds an overlap-based PAC stopping rule plus greedy per-feature sampling to KernelSHAP and SamplingSHAP, cutting function evaluations about 5x on credit datasets.
Problem
Identifying the k most important features by SHAP value with PAC guarantees is sample-inefficient when existing sampling-based SHAP estimators are run until all feature confidence intervals are narrow.
Approach
Treat top-k SHAP identification as an Explore-m problem: stop when the CI overlap between the weakest top-k feature and the strongest non-top-k feature is within epsilon, and greedily sample only those two features at each step.
Key results
- KernelSHAP@k reduces function evaluations by 8.0x on German Credit (221114 to 27632) and 4.7x on UCI Credit versus KernelSHAP for (epsilon=0.005, delta=1e-6) top-4 identification.
- SamplingSHAP@k reduces function evaluations by 14.2x on German Credit (397607 to 27982) and 10.4x on HELOC versus SamplingSHAP.
- Across datasets the methods offer between 1.2x and 14.2x sample-efficiency improvements and 1.2x to 14.7x runtime improvements, averaging about 5x.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use KernelSHAP@k with overlap-based stopping instead of KernelSHAP | KernelSHAP · German Credit | function evaluations: 221114 -> 27632 | Helped |
| Use SamplingSHAP@k with overlap-based stopping and greedy sampling instead of SamplingSHAP | SamplingSHAP · German Credit | function evaluations: 397607 -> 27982 | Helped |
| Use KernelSHAP@k with overlap-based stopping instead of KernelSHAP | KernelSHAP · Give Me Some Credit | function evaluations: 6883 -> 5593 | Helped |
| Use SamplingSHAP@k with overlap-based stopping and greedy sampling instead of SamplingSHAP | SamplingSHAP · Give Me Some Credit | function evaluations: 10501 -> 3184 | Helped |
| Use KernelSHAP@k with overlap-based stopping instead of KernelSHAP | KernelSHAP · HELOC | function evaluations: 59230 -> 12986 | Helped |
| Use SamplingSHAP@k with overlap-based stopping and greedy sampling instead of SamplingSHAP | SamplingSHAP · HELOC | function evaluations: 95641 -> 9221 | Helped |
| Use KernelSHAP@k with overlap-based stopping instead of KernelSHAP | KernelSHAP · UCI Credit | function evaluations: 34336 -> 7275 | Helped |
| Use SamplingSHAP@k with overlap-based stopping and greedy sampling instead of SamplingSHAP | SamplingSHAP · UCI Credit | function evaluations: 53460 -> 14485 | Helped |
| Use KernelSHAP@k with overlap-based stopping instead of KernelSHAP | KernelSHAP · German Credit | runtime (seconds): 15.95 -> 2.28 | Helped |
| Use SamplingSHAP@k with overlap-based stopping and greedy sampling instead of SamplingSHAP | SamplingSHAP · German Credit | runtime (seconds): 2.2 -> 0.15 | Helped |
| Use KernelSHAP@k with overlap-based stopping instead of KernelSHAP | KernelSHAP · Give Me Some Credit | runtime (seconds): 0.04 -> 0.03 | Helped |
| Use SamplingSHAP@k with overlap-based stopping and greedy sampling instead of SamplingSHAP | SamplingSHAP · Give Me Some Credit | runtime (seconds): 0.05 -> 0.02 | Helped |
Surprising findings
- KernelSHAP@k uses fewer samples than SamplingSHAP@k on UCI Credit, yet SamplingSHAP@k is about 10x faster in runtime because KernelSHAP's weighted regression is costlier per estimate.
- On Give Me Some Credit the improvement from KernelSHAP@k over KernelSHAP is only 1.2x.
Limitations
- Assumes feature independence inherited from SHAP; correlated features not addressed.
- Only identifies the top-k set, not the ordering of the features.
- C2 greedy sampling cannot be applied to KernelSHAP since it estimates all features jointly.
Experimental setup
Datasets: German Credit Risk Give Me Some Credit HELOC UCI Credit Approval
Benchmarks: German Credit Risk Give Me Some Credit HELOC UCI Credit Approval
Metrics: number of function evaluations runtime in seconds
Baselines: KernelSHAP SamplingSHAP
Builds on: KernelSHAP SamplingSHAP Explore-m (Kalyanakrishnan et al.) interventional SHAP
Closest papers by meaning
- Provably Accurate Shapley Value Estimation via Leverage Score Sampling (ICLR 2025 · similarity 0.86)
- A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values (NeurIPS 2025 · similarity 0.85)
- Gaussian Process Bandits for Top-k Recommendations (NeurIPS 2024 · similarity 0.83)
- Shaping Up SHAP: Enhancing Stability through Layer-Wise Neighbor Selection (AAAI 2024 · similarity 0.83)
- KernelSHAP-IQ: Weighted Least Square Optimization for Shapley Interactions (ICML 2024 · similarity 0.82)
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.82)
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.