A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918208511934464 |
|---|---|
| author | Chen, Tyler Seshadri, Akshay Villani, Mattia J. Niroula, Pradeep Chakrabarti, Shouvanik Ray, Archan Deshpande, Pranav Yalovetzky, Romina Pistoia, Marco Kumar, Niraj |
| author_facet | Chen, Tyler Seshadri, Akshay Villani, Mattia J. Niroula, Pradeep Chakrabarti, Shouvanik Ray, Archan Deshpande, Pranav Yalovetzky, Romina Pistoia, Marco Kumar, Niraj |
| contents | Shapley values have emerged as a critical tool for explaining which features impact the decisions made by machine learning models. However, computing exact Shapley values is difficult, generally requiring an exponential (in the feature dimension) number of model evaluations. To address this, many model-agnostic randomized estimators have been developed, the most influential and widely used being the KernelSHAP method (Lundberg & Lee, 2017). While related estimators such as unbiased KernelSHAP (Covert & Lee, 2021) and LeverageSHAP (Musco & Witter, 2025) are known to satisfy theoretical guarantees, bounds for KernelSHAP have remained elusive. We describe a broad and unified framework that encompasses KernelSHAP and related estimators constructed using both with and without replacement sampling strategies. We then prove strong non-asymptotic theoretical guarantees that apply to all estimators from our framework. This provides, to the best of our knowledge, the first theoretical guarantees for KernelSHAP and sheds further light on tradeoffs between existing estimators. Through comprehensive benchmarking on small and medium dimensional datasets for Decision-Tree models, we validate our approach against exact Shapley values, consistently achieving low mean squared error with modest sample sizes. Furthermore, we make specific implementation improvements to enable scalability of our methods to high-dimensional datasets. Our methods, tested on datasets such MNIST and CIFAR10, provide consistently better results compared to the KernelSHAP library. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_05216 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values Chen, Tyler Seshadri, Akshay Villani, Mattia J. Niroula, Pradeep Chakrabarti, Shouvanik Ray, Archan Deshpande, Pranav Yalovetzky, Romina Pistoia, Marco Kumar, Niraj Machine Learning Data Structures and Algorithms Quantum Physics Shapley values have emerged as a critical tool for explaining which features impact the decisions made by machine learning models. However, computing exact Shapley values is difficult, generally requiring an exponential (in the feature dimension) number of model evaluations. To address this, many model-agnostic randomized estimators have been developed, the most influential and widely used being the KernelSHAP method (Lundberg & Lee, 2017). While related estimators such as unbiased KernelSHAP (Covert & Lee, 2021) and LeverageSHAP (Musco & Witter, 2025) are known to satisfy theoretical guarantees, bounds for KernelSHAP have remained elusive. We describe a broad and unified framework that encompasses KernelSHAP and related estimators constructed using both with and without replacement sampling strategies. We then prove strong non-asymptotic theoretical guarantees that apply to all estimators from our framework. This provides, to the best of our knowledge, the first theoretical guarantees for KernelSHAP and sheds further light on tradeoffs between existing estimators. Through comprehensive benchmarking on small and medium dimensional datasets for Decision-Tree models, we validate our approach against exact Shapley values, consistently achieving low mean squared error with modest sample sizes. Furthermore, we make specific implementation improvements to enable scalability of our methods to high-dimensional datasets. Our methods, tested on datasets such MNIST and CIFAR10, provide consistently better results compared to the KernelSHAP library. |
| title | A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values |
| topic | Machine Learning Data Structures and Algorithms Quantum Physics |
| url | https://arxiv.org/abs/2506.05216 |