Kavli Affiliate: Ke Wang
| First 5 Authors: Linwei Hu, Ke Wang, , ,
| Summary:
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.
| Search Query: ArXiv Query: search_query=au:”Ke Wang”&id_list=&start=0&max_results=3