Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

• URL: http://arxiv.org/abs/2606.25103v1
• Date: Tue, 23 Jun 2026 19:19:11 GMT
• Title: Beyond Shapley: Efficient Computation of Asymmetric Shapley Values
• Abstract summary: We consider a variant of Shapley values known as Asymmetric Shapley Values (ASV)<n>We show that in certain contexts in which the incorporation of SHAP is $#P$-hard, the exact of ASV can be done in time.<n>We develop an algorithm for approximating ASV in arbitrary causal DAGs which relies on a procedure to sample topological orderings uniformly at random.
• Score: 1.376408511310322
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We address the problem of explainability in machine learning models through feature attribution methods. In particular, we consider a variant of Shapley values known as Asymmetric Shapley Values (ASV), which enables the incorporation of causal knowledge into model-agnostic explanations through the use of a causal graph. We show that in certain contexts in which the computation of SHAP is $\#P$-hard, the exact computation of ASV can be done in polynomial time. To extend this algorithmic result, we introduce a notion of equivalence classes over the topological orderings of the underlying causal graph, which is useful to reduce the time to compute ASV. In particular, we present a polynomial-time algorithm (in the number of equivalence classes) to compute it whenever the causal graph is a rooted directed tree. Finally, we develop an algorithm for approximating ASV in arbitrary causal DAGs which relies on a procedure to sample topological orderings uniformly at random. To implement this sampling mechanism we leverage known algorithms as well as simpler alternatives. Our experimental results demonstrate the practical viability of the proposed approach in realistic causal structures.

Related papers

• Variables Ordering Optimization in Boolean Characteristic Set Method Using Simulated Annealing and Machine Learning-based Time Prediction [1.654967376694554]
  This paper introduces a novel framework that integrates machine learning (ML)-based time prediction with simulated annealing (SA)<n>We train an accurate ML predictor ft(X) to estimate solving time for any given variables ordering.<n>Experiments demonstrate that our method substantially outperforms the standard BCS algorithm.
  arXiv  Detail & Related papers  (2025-09-18T09:02:32Z)
• Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes [12.496136169054541]
  Shapley values are widely recognized as a principled method for attributing importance to input features in machine learning.<n>We show that the exact computation of Shapley values scales exponentially with the number of features.<n>Our work provides more scalable, axiomatically sound, and uncertainty-aware explanations for predictions generated by structured probabilistic models.
  arXiv  Detail & Related papers  (2025-08-20T07:39:14Z)
• Fast Calculation of Feature Contributions in Boosting Trees [10.968795392216606]
  We propose an efficient algorithm that reduces the computational complexity of calculating Shapley values for quadratic losses to time.<n>Our simulations show that Q-SHAP not only improves computational efficiency but also enhances the accuracy of feature-specific $R2$ estimates.
  arXiv  Detail & Related papers  (2024-07-03T21:27:29Z)
• 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)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
  We present a novel distributed computing framework that is robust to slow compute nodes, and is capable of both approximate and exact computation of linear operations. We propose a sequential decoding algorithm designed to handle real valued data while maintaining low computational complexity for recovery. We demonstrate the potential applications of this framework in various contexts, such as large-scale matrix multiplication and black-box optimization.
  arXiv  Detail & Related papers  (2023-09-01T18:02:04Z)
• Learning distributed representations with efficient SoftMax normalization [3.8673630752805437]
  We propose a linear-time approximation to compute the normalization constants of $rm SoftMax(XYT)$ for embedding vectors with bounded norms.<n>We show on some pre-trained embedding datasets that the proposed estimation method achieves higher or comparable accuracy with competing methods.<n>The proposed algorithm is interpretable and easily adapted to arbitrary embedding problems.
  arXiv  Detail & Related papers  (2023-03-30T15:48:26Z)
• 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)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Accurate Shapley Values for explaining tree-based models [0.0]
  We introduce two estimators of Shapley Values that exploit the tree structure efficiently and are more accurate than state-of-the-art methods. These methods are available as a Python package.
  arXiv  Detail & Related papers  (2021-06-07T17:35:54Z)
• 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)
• Theory and Algorithms for Shapelet-based Multiple-Instance Learning [5.08418565337126]
  We propose a new formulation of Multiple-Instance Learning (MIL), in which a unit of data consists of instances called a bag. The goal is to find a good classifier of bags based on the similarity with a "shapelet" (or pattern) In our formulation, we use all possible, and thus infinitely many shapelets, resulting in a richer class of classifiers.
  arXiv  Detail & Related papers  (2020-05-31T17:10:59Z)

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.