  As modern complex neural networks keep breaking records and solving harder
problems, their predictions also become less and less intelligible. The current
lack of interpretability often undermines the deployment of accurate machine
learning tools in sensitive settings. In this work, we present a model-agnostic
explanation method for image classification based on a hierarchical extension
of Shapley coefficients --Hierarchical Shap (h-Shap)-- that resolves some of
the limitations of current approaches. Unlike other Shapley-based explanation
methods, h-Shap is scalable and can be computed without the need of
approximation. Under certain distributional assumptions, such as those common
in multiple instance learning, h-Shap retrieves the exact Shapley coefficients
with an exponential improvement in computational complexity. We compare our
hierarchical approach with popular Shapley-based and non-Shapley-based methods
on a synthetic dataset, a medical imaging scenario, and a general computer
vision problem, showing that h-Shap outperforms the state of the art in both
accuracy and runtime. Code and experiments are made publicly available.
