Fast TreeSHAP: Accelerating SHAP Value Computation for Trees
SHAP (SHapley Additive exPlanation) values are one of the leading tools for interpreting machine learning models, with strong theoretical guarantees (consistency, local accuracy) and a wide availability of implementations and use cases. Even though computing SHAP values takes exponential time in general, TreeSHAP takes polynomial time on tree-based models. While the speedup is significant, TreeSHAP can still dominate the computation time of industry-level machine learning solutions on datasets with millions or more entries, causing delays in post-hoc model diagnosis and interpretation service. In this paper we present two new algorithms, Fast TreeSHAP v1 and v2, designed to improve the computational efficiency of TreeSHAP for large datasets. We empirically find that Fast TreeSHAP v1 is 1.5x faster than TreeSHAP while keeping the memory cost unchanged. Similarly, Fast TreeSHAP v2 is 2.5x faster than TreeSHAP, at the cost of a slightly higher memory usage, thanks to the pre-computation of expensive TreeSHAP steps. We also show that Fast TreeSHAP v2 is well-suited for multi-time model interpretations, resulting in as high as 3x faster explanation of newly incoming samples.
Code (1)
Tasks
BIG-bench Machine LearningComputational EfficiencyMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions
Shapley values are a standard tool for explaining predictions of tree ensembles, with Path-Dependent SHAP being the most widely used variant. Despite substantial progress, existing methods still exhibit trade-offs betwee…
GPUTreeShap: Massively Parallel Exact Calculation of SHAP Scores for Tree Ensembles
SHAP (SHapley Additive exPlanation) values provide a game theoretic interpretation of the predictions of machine learning models based on Shapley values. While exact calculation of SHAP values is computationally intracta…
BIG-bench Machine LearningCPUGPUBeyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles
While shallow decision trees may be interpretable, larger ensemble models like gradient-boosted trees, which often set the state of the art in machine learning problems involving tabular data, still remain black box mode…
Explainable artificial intelligenceExplainable Artificial Intelligence (XAI)Linear TreeShap
Decision trees are well-known due to their ease of interpretability. To improve accuracy, we need to grow deep trees or ensembles of trees. These are hard to interpret, offsetting their original benefits. Shapley values …
Understanding Interventional TreeSHAP : How and Why it Works
Shapley values are ubiquitous in interpretable Machine Learning due to their strong theoretical background and efficient implementation in the SHAP library. Computing these values previously induced an exponential cost w…
Interpretable Machine Learning