Quantum Algorithms for Shapley Value Calculation
Iain Burge, Michel Barbeau, Joaquín García-Alfaro
Abstract
In the classical context, the cooperative game theory concept of the Shapley value has been adapted for post hoc explanations of Machine Learning (ML) 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.
Topics & Concepts
Shapley valueComputer scienceContext (archaeology)AlgorithmVotingCooperative game theoryQuantumGame theoryPolynomialInterval (graph theory)Value (mathematics)Theoretical computer scienceMathematical economicsMathematicsCombinatoricsMachine learningPolitical sciencePaleontologyMathematical analysisPhysicsPoliticsBiologyQuantum mechanicsLawExplainable Artificial Intelligence (XAI)Quantum Computing Algorithms and ArchitectureBayesian Modeling and Causal Inference