# Computing SHAP Efficiently Using Model Structure Information

arXiv: https://arxiv.org/abs/2309.02417 · HTML: https://mlsanity.com/paper/2309.02417/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 13 references that are in the map.
- First posted on arXiv 5 Sep 2023.

## Builds on (most cited first, 6 of 6)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [True to the Model or True to the Data?](https://mlsanity.com/paper/2006.16234/) (2020)
- [GAMI-Net: An Explainable Neural Network based on Generalized Additive Models with Structured Interactions](https://mlsanity.com/paper/2003.07132/) (2020)
- [Explaining Adverse Actions in Credit Decisions Using Shapley Decomposition](https://mlsanity.com/paper/2204.12365/) (2022)
- [Using Model-Based Trees with Boosting to Fit Low-Order Functional ANOVA Models](https://mlsanity.com/paper/2207.06950/) (2022)

## Abstract (arXiv)

SHAP (SHapley Additive exPlanations) has become a popular method to attribute the prediction of a machine learning model on an input to its features. One main challenge of SHAP is the computation time. An exact computation of Shapley values requires exponential time complexity. Therefore, many approximation methods are proposed in the literature. In this paper, we propose methods that can compute SHAP exactly in polynomial time or even faster for SHAP definitions that satisfy our additivity and dummy assumptions (eg, kernal SHAP and baseline SHAP). We develop different strategies for models with different levels of model structure information: known functional decomposition, known order of model (defined as highest order of interaction in the model), or unknown order. For the first case, we demonstrate an additive property and a way to compute SHAP from the lower-order functional components. For the second case, we derive formulas that can compute SHAP in polynomial time. Both methods yield exact SHAP results. Finally, if even the order of model is unknown, we propose an iterative way to approximate Shapley values. The three methods we propose are computationally efficient when the order of model is not high which is typically the case in practice. We compare with sampling approach proposed in Castor & Gomez (2008) using simulation studies to demonstrate the efficacy of our proposed methods.