When is the Computation of a Feature Attribution Method Tractable?
This work addresses computational bottlenecks for researchers and practitioners using feature attribution in explainable AI, though it is incremental as it builds on known results for SHAP.
The paper tackles the computational complexity of feature attribution methods beyond SHAP, identifying conditions for efficient computation and introducing Bernoulli power indices that simplify to constant expected value evaluations, with results showing polynomial equivalence and complexity mirroring for interaction indices.
Feature attribution methods have become essential for explaining machine learning models. Many popular approaches, such as SHAP and Banzhaf values, are grounded in power indices from cooperative game theory, which measure the contribution of features to model predictions. This work studies the computational complexity of power indices beyond SHAP, addressing the conditions under which they can be computed efficiently. We identify a simple condition on power indices that ensures that computation is polynomially equivalent to evaluating expected values, extending known results for SHAP. We also introduce Bernoulli power indices, showing that their computation can be simplified to a constant number of expected value evaluations. Furthermore, we explore interaction power indices that quantify the importance of feature subsets, proving that their computation complexity mirrors that of individual features.