On the Computational Tractability of the (Many) Shapley Values

• URL: http://arxiv.org/abs/2502.12295v1
• Date: Mon, 17 Feb 2025 20:08:03 GMT
• Title: On the Computational Tractability of the (Many) Shapley Values
• Authors: Reda Marzouk, Shahaf Bassan, Guy Katz, Colin de la Higuera,
• Abstract summary: Recent studies have examined the computational complexity of computing Shapley additive explanations (also known as SHAP) across various models and distributions. These studies primarily focused on a specific variant called Conditional SHAP, though many other variants exist and address different limitations. In this work, we analyze the complexity of computing a much broader range of such variants, including Conditional, Interventional, and Baseline SHAP.
• Score: 1.0035342658750597
• License:
• Abstract: Recent studies have examined the computational complexity of computing Shapley additive explanations (also known as SHAP) across various models and distributions, revealing their tractability or intractability in different settings. However, these studies primarily focused on a specific variant called Conditional SHAP, though many other variants exist and address different limitations. In this work, we analyze the complexity of computing a much broader range of such variants, including Conditional, Interventional, and Baseline SHAP, while exploring both local and global computations. We show that both local and global Interventional and Baseline SHAP can be computed in polynomial time for various ML models under Hidden Markov Model distributions, extending popular algorithms such as TreeSHAP beyond empirical distributions. On the downside, we prove intractability results for these variants over a wide range of neural networks and tree ensembles. We believe that our results emphasize the intricate diversity of computing Shapley values, demonstrating how their complexity is substantially shaped by both the specific SHAP variant, the model type, and the distribution.

Related papers

• Partial-Multivariate Model for Forecasting [28.120094495344453]
  We propose a Transformer-based partial-multivariate model, PMformer, for forecasting problems. We demonstrate that PMformer outperforms various univariate and complete-multivariate models. We also highlight other advantages of PMformer: efficiency and robustness under missing features.
  arXiv  Detail & Related papers  (2024-08-19T05:18:50Z)
• On the Tractability of SHAP Explanations under Markovian Distributions [0.1578515540930834]
  The SHAP framework is one of the most widely utilized frameworks for local explainability of ML models. Despite its popularity, its exact computation is known to be very challenging, proven to be NP-Hard in various configurations. Recent works have unveiled positive complexity results regarding the computation of the SHAP score for specific model families.
  arXiv  Detail & Related papers  (2024-05-05T13:56:12Z)
• 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)
• 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)
• PAC Reinforcement Learning for Predictive State Representations [60.00237613646686]
  We study online Reinforcement Learning (RL) in partially observable dynamical systems. We focus on the Predictive State Representations (PSRs) model, which is an expressive model that captures other well-known models. We develop a novel model-based algorithm for PSRs that can learn a near optimal policy in sample complexity scalingly.
  arXiv  Detail & Related papers  (2022-07-12T17:57:17Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Redefining Neural Architecture Search of Heterogeneous Multi-Network Models by Characterizing Variation Operators and Model Components [71.03032589756434]
  We investigate the effect of different variation operators in a complex domain, that of multi-network heterogeneous neural models. We characterize both the variation operators, according to their effect on the complexity and performance of the model; and the models, relying on diverse metrics which estimate the quality of the different parts composing it.
  arXiv  Detail & Related papers  (2021-06-16T17:12:26Z)
• 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)
• Probabilistic Circuits for Variational Inference in Discrete Graphical Models [101.28528515775842]
  Inference in discrete graphical models with variational methods is difficult. Many sampling-based methods have been proposed for estimating Evidence Lower Bound (ELBO) We propose a new approach that leverages the tractability of probabilistic circuit models, such as Sum Product Networks (SPN) We show that selective-SPNs are suitable as an expressive variational distribution, and prove that when the log-density of the target model is aweighted the corresponding ELBO can be computed analytically.
  arXiv  Detail & Related papers  (2020-10-22T05:04:38Z)
• Stochastic spectral embedding [0.0]
  We propose a novel sequential adaptive surrogate modeling method based on "stochastic spectral embedding" (SSE) We show how the method compares favorably against state-of-the-art sparse chaos expansions on a set of models with different complexity and input dimension.
  arXiv  Detail & Related papers  (2020-04-09T11:00:07Z)

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.