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.

本文提出了多种方法，可以在多项式时间内准确计算 SHAP 值，适用于不同类型的模型结构信息，包括已知功能分解、已知模型顺序和未知模型顺序，其中的方法在实际应用中计算效率高且准确性较高。