Computing SHAP Efficiently Using Model Structure Information

• URL: http://arxiv.org/abs/2309.02417v1
• Date: Tue, 5 Sep 2023 17:48:09 GMT
• Title: Computing SHAP Efficiently Using Model Structure Information
• Authors: Linwei Hu, Ke Wang
• Abstract summary: We propose methods that compute SHAP exactly in time or even faster for SHAP definitions that satisfy our additivity and dummy assumptions. 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 time. Both methods yield exact SHAP results.
• Score: 3.6626323701161665
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Maximum a Posteriori Estimation for Linear Structural Dynamics Models Using Bayesian Optimization with Rational Polynomial Chaos Expansions [0.01578888899297715]
  We propose an extension to an existing sparse Bayesian learning approach for MAP estimation. We introduce a Bayesian optimization approach, which allows to adaptively enrich the experimental design. By combining the sparsity-inducing learning procedure with the experimental design, we effectively reduce the number of model evaluations.
  arXiv  Detail & Related papers  (2024-08-07T06:11:37Z)
• Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
  Contextual decision processes (CMDPs) describe a class of reinforcement learning problems in which the transition kernels and reward functions can change over time with different MDPs indexed by a context variable. CMDPs serve as an important framework to model many real-world applications with time-varying environments. We study CMDPs under two linear function approximation models: Model I with context-varying representations and common linear weights for all contexts; and Model II with common representations for all contexts and context-varying linear weights.
  arXiv  Detail & Related papers  (2024-02-05T03:25:04Z)
• Towards Efficient Time Stepping for Numerical Shape Correspondence [55.2480439325792]
  Methods based on partial differential equations (PDEs) have been established, encompassing e.g. the classic heat kernel signature. We consider here several time stepping schemes. The goal of this investigation is to assess, if one may identify a useful property of methods for time integration for the shape analysis context.
  arXiv  Detail & Related papers  (2023-12-21T13:40:03Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  We propose a straightforward and efficient Shapley estimator, SimSHAP, by eliminating redundant techniques. In our analysis of existing approaches, we observe that estimators can be unified as a linear transformation of randomly summed values from feature subsets. Our experiments validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.
  arXiv  Detail & Related papers  (2023-11-02T06:09:24Z)
• A Comparative Study of Methods for Estimating Conditional Shapley Values and When to Use Them [4.3012765978447565]
  We develop new methods, extend earlier proposed approaches, and systematize the new methods into different method classes for comparison and evaluation. We conduct extensive simulation studies to evaluate how precisely the different method classes estimate the conditional expectations. We also apply the methods to several real-world data experiments and provide recommendations for when to use the different method classes and approaches.
  arXiv  Detail & Related papers  (2023-05-16T15:27:17Z)
• Gaussian process regression and conditional Karhunen-Lo\'{e}ve models for data assimilation in inverse problems [68.8204255655161]
  We present a model inversion algorithm, CKLEMAP, for data assimilation and parameter estimation in partial differential equation models. The CKLEMAP method provides better scalability compared to the standard MAP method.
  arXiv  Detail & Related papers  (2023-01-26T18:14:12Z)
• PDD-SHAP: Fast Approximations for Shapley Values using Functional Decomposition [2.0559497209595823]
  We propose PDD-SHAP, an algorithm that uses an ANOVA-based functional decomposition model to approximate the black-box model being explained. This allows us to calculate Shapley values orders of magnitude faster than existing methods for large datasets, significantly reducing the amortized cost of computing Shapley values.
  arXiv  Detail & Related papers  (2022-08-26T11:49:54Z)
• Algorithms to estimate Shapley value feature attributions [11.527421282223948]
  Feature attributions based on the Shapley value are popular for explaining machine learning models. We disentangle this complexity into two factors: (1)the approach to removing feature information, and (2)the tractable estimation strategy.
  arXiv  Detail & Related papers  (2022-07-15T17:04:41Z)
• Sampling from Arbitrary Functions via PSD Models [55.41644538483948]
  We take a two-step approach by first modeling the probability distribution and then sampling from that model. We show that these models can approximate a large class of densities concisely using few evaluations, and present a simple algorithm to effectively sample from these models.
  arXiv  Detail & Related papers  (2021-10-20T12:25:22Z)
• Fast Hierarchical Games for Image Explanations [78.16853337149871]
  We present a model-agnostic explanation method for image classification based on a hierarchical extension of Shapley coefficients. Unlike other Shapley-based explanation methods, h-Shap is scalable and can be computed without the need of approximation. 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.
  arXiv  Detail & Related papers  (2021-04-13T13:11:02Z)
• A Multilinear Sampling Algorithm to Estimate Shapley Values [4.771833920251869]
  We propose a new sampling method based on a multilinear extension technique as applied in game theory. Our method is applicable to any machine learning model, in particular for either multi-class classifications or regression problems.
  arXiv  Detail & Related papers  (2020-10-22T21:47:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.