Approximating Shapley Interactions with Marginal Contributions

Abstract The Shapley value constitutes a widely recognized tool to assess individual contributions of cooperating entities from a game-theoretic perspective. Within the field of machine learning it is frequently applied to conduct feature attribution or data valuation. Aiming to overcome its deficiencies in capturing intricate interplay between entities, the Shapley interaction index represents a natural extension of the Shapley value, maintaining axiomatic uniqueness. As their complexity renders the exact computation of both quantities impractical, recent work transfers approximation approaches from the Shapley value to Shapley interactions. We propose Permutation-IQ , a domain-independent approximation method based on a novel representation that traces Shapley interactions back to the Shapley value’s fine-grained building blocks of marginal contributions. Sampling these instead of the coarser discrete derivatives of which Shapley interactions are composed, allows to utilize the collected information more efficiently.