Unlocking the Game: Estimating Games in Möbius Representation for Explanation and High-Order Interaction Detection

Shapley value-based explanations are widely utilized to demystify predictions made by opaque models. Approaches to estimating Shapley values often approximate explanation games as inessential and estimate the Shapley value directly as feature attribution with a limited capacity to quantify feature interactions. This paper introduces a new approach for calculating Shapley values that relaxes the assumption of inessential games and is proven to provide additive feature attribution. The initial formulation of the proposed approach includes the estimation of game values in their Möbius representation with exponentially many parameters, but we put forward a polynomial-time algorithm designed to manage the game's numerous values and achieve an efficient linear-time computation of the Shapley value. Moreover, this formulation uniquely enables identifying only the significant high-order feature interactions amidst a potentially exponential set. Through experiments, we demonstrate the robust performance of our methodology in game estimation and in providing explanations for multiple black-box models.