Approximation of group explainers with coalition structure using Monte Carlo sampling on the product space of coalitions and features
This work addresses the computational bottleneck in explainable AI for practitioners, offering a faster and model-agnostic solution, though it is incremental as it builds on existing game-theoretic frameworks.
The paper tackles the high computational complexity of game-theoretic explainers for machine learning models by designing a Monte Carlo sampling algorithm that estimates these explainers with linear complexity relative to the background dataset size, achieving similar statistical accuracy to more complex methods.
In recent years, many Machine Learning (ML) explanation techniques have been designed using ideas from cooperative game theory. These game-theoretic explainers suffer from high complexity, hindering their exact computation in practical settings. In our work, we focus on a wide class of linear game values, as well as coalitional values, for the marginal game based on a given ML model and predictor vector. By viewing these explainers as expectations over appropriate sample spaces, we design a novel Monte Carlo sampling algorithm that estimates them at a reduced complexity that depends linearly on the size of the background dataset. We set up a rigorous framework for the statistical analysis and obtain error bounds for our sampling methods. The advantage of this approach is that it is fast, easily implementable, and model-agnostic. Furthermore, it has similar statistical accuracy as other known estimation techniques that are more complex and model-specific. We provide rigorous proofs of statistical convergence, as well as numerical experiments whose results agree with our theoretical findings.