Kernel Banzhaf: A Fast and Robust Estimator for Banzhaf Values
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916618674634752 |
|---|---|
| author | Liu, Yurong Witter, R. Teal Korn, Flip Alrashed, Tarfah Paparas, Dimitris Musco, Christopher Freire, Juliana |
| author_facet | Liu, Yurong Witter, R. Teal Korn, Flip Alrashed, Tarfah Paparas, Dimitris Musco, Christopher Freire, Juliana |
| contents | Banzhaf values provide a popular, interpretable alternative to the widely-used Shapley values for quantifying the importance of features in machine learning models. Like Shapley values, computing Banzhaf values exactly requires time exponential in the number of features, necessitating the use of efficient estimators. Existing estimators, however, are limited to Monte Carlo sampling methods. In this work, we introduce Kernel Banzhaf, the first regression-based estimator for Banzhaf values. Our approach leverages a novel regression formulation, whose exact solution corresponds to the exact Banzhaf values. Inspired by the success of Kernel SHAP for Shapley values, Kernel Banzhaf efficiently solves a sampled instance of this regression problem. Through empirical evaluations across eight datasets, we find that Kernel Banzhaf significantly outperforms existing Monte Carlo methods in terms of accuracy, sample efficiency, robustness to noise, and feature ranking recovery. Finally, we complement our experimental evaluation with strong theoretical guarantees on Kernel Banzhaf's performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08336 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Kernel Banzhaf: A Fast and Robust Estimator for Banzhaf Values Liu, Yurong Witter, R. Teal Korn, Flip Alrashed, Tarfah Paparas, Dimitris Musco, Christopher Freire, Juliana Machine Learning Artificial Intelligence Banzhaf values provide a popular, interpretable alternative to the widely-used Shapley values for quantifying the importance of features in machine learning models. Like Shapley values, computing Banzhaf values exactly requires time exponential in the number of features, necessitating the use of efficient estimators. Existing estimators, however, are limited to Monte Carlo sampling methods. In this work, we introduce Kernel Banzhaf, the first regression-based estimator for Banzhaf values. Our approach leverages a novel regression formulation, whose exact solution corresponds to the exact Banzhaf values. Inspired by the success of Kernel SHAP for Shapley values, Kernel Banzhaf efficiently solves a sampled instance of this regression problem. Through empirical evaluations across eight datasets, we find that Kernel Banzhaf significantly outperforms existing Monte Carlo methods in terms of accuracy, sample efficiency, robustness to noise, and feature ranking recovery. Finally, we complement our experimental evaluation with strong theoretical guarantees on Kernel Banzhaf's performance. |
| title | Kernel Banzhaf: A Fast and Robust Estimator for Banzhaf Values |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2410.08336 |