A Quantum Algorithm for Shapley Value Estimation

• URL: http://arxiv.org/abs/2301.04727v4
• Date: Sun, 03 Nov 2024 12:11:33 GMT
• Title: A Quantum Algorithm for Shapley Value Estimation
• Authors: Iain Burge, Michel Barbeau, Joaquin Garcia-Alfaro,
• Abstract summary: We propose quantum algorithms which can extract Shapley values within some confidence interval. We demonstrate the validity of each approach under specific examples of voting games.
• Score: 0.8739101659113155
• License:
• Abstract: In the classical context, the cooperative game theory concept of the Shapley value has been adapted for post hoc explanations of machine learning models. However, this approach does not easily translate to eXplainable Quantum ML (XQML). Finding Shapley values can be highly computationally complex. We propose quantum algorithms which can extract Shapley values within some confidence interval. Our results perform in polynomial time. We demonstrate the validity of each approach under specific examples of cooperative voting games.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• 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 Shapley Value Computation for the Naive Bayes Classifier [0.0]
  This article proposes an exact analytic expression of Shapley values in the case of the naive Bayes classifier. Results show that our Shapley proposal for the naive Bayes provides informative results with low algorithmic complexity.
  arXiv  Detail & Related papers  (2023-07-31T14:39:10Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• A didactic approach to quantum machine learning with a single qubit [68.8204255655161]
  We focus on the case of learning with a single qubit, using data re-uploading techniques. We implement the different proposed formulations in toy and real-world datasets using the qiskit quantum computing SDK.
  arXiv  Detail & Related papers  (2022-11-23T18:25:32Z)
• From Shapley Values to Generalized Additive Models and back [16.665883787432858]
  We introduce $n$-Shapley Values, a natural extension of Shapley Values that explain individual predictions with interaction terms up to order $n$. From the Shapley-GAM, we can compute Shapley Values of arbitrary order, which gives precise insights into the limitations of these explanations. At the technical end, we show that there is a one-to-one correspondence between different ways to choose the value function and different functional decompositions of the original function.
  arXiv  Detail & Related papers  (2022-09-08T19:37:06Z)
• 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)
• The Shapley Value in Machine Learning [5.867472712737402]
  We give an overview of the most important applications of the Shapley value in machine learning. We examine the most crucial limitations of the Shapley value and point out directions for future research.
  arXiv  Detail & Related papers  (2022-02-11T13:25:11Z)
• groupShapley: Efficient prediction explanation with Shapley values for feature groups [2.320417845168326]
  Shapley values has established itself as one of the most appropriate and theoretically sound frameworks for explaining predictions from machine learning models. The main drawback with Shapley values is that its computational complexity grows exponentially in the number of input features. The present paper introduces groupShapley: a conceptually simple approach for dealing with the aforementioned bottlenecks.
  arXiv  Detail & Related papers  (2021-06-23T08:16:14Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• 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)

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.