Computing the Shapley Value of Facts in ...
Type de document :
Communication dans un congrès avec actes
Titre :
Computing the Shapley Value of Facts in Query Answering
Auteur(s) :
Deutch, Daniel [Auteur]
School of Computer Science [TAU-CS]
Frost, Nave [Auteur]
School of Computer Science [TAU-CS]
Kimelfeld, Benny [Auteur]
Technion - Israel Institute of Technology [Haifa]
Monet, Mikaël [Auteur]
Linking Dynamic Data [LINKS]
School of Computer Science [TAU-CS]
Frost, Nave [Auteur]
School of Computer Science [TAU-CS]
Kimelfeld, Benny [Auteur]
Technion - Israel Institute of Technology [Haifa]
Monet, Mikaël [Auteur]
Linking Dynamic Data [LINKS]
Titre de la manifestation scientifique :
SIGMOD Conference 2022
Ville :
Philadelphia
Pays :
Etats-Unis d'Amérique
Date de début de la manifestation scientifique :
2022-06-12
Discipline(s) HAL :
Informatique [cs]
Résumé en anglais : [en]
The Shapley value is a game-theoretic notion for wealth distribution that is nowadays extensively used to explain complex data-intensive computation, for instance, in network analysis or machine learning. Recent theoretical ...
Lire la suite >The Shapley value is a game-theoretic notion for wealth distribution that is nowadays extensively used to explain complex data-intensive computation, for instance, in network analysis or machine learning. Recent theoretical works show that query evaluation over relational databases fits well in this explanation paradigm. Yet, these works fall short of providing practical solutions to the computational challenge inherent to the Shapley computation. We present in this paper two practically effective solutions for computing Shapley values in query answering. We start by establishing a tight theoretical connection to the extensively studied problem of query evaluation over probabilistic databases, which allows us to obtain a polynomial-time algorithm for the class of queries for which probability computation is tractable. We then propose a first practical solution for computing Shapley values that adopts tools from probabilistic query evaluation. In particular, we capture the dependence of query answers on input database facts using Boolean expressions (data provenance), and then transform it, via Knowledge Compilation, into a particular circuit form for which we devise an algorithm for computing the Shapley values. Our second practical solution is a faster yet inexact approach that transforms the provenance to a Conjunctive Normal Form and uses a heuristic to compute the Shapley values. Our experiments on TPC-H and IMDB demonstrate the practical effectiveness of our solutions.Lire moins >
Lire la suite >The Shapley value is a game-theoretic notion for wealth distribution that is nowadays extensively used to explain complex data-intensive computation, for instance, in network analysis or machine learning. Recent theoretical works show that query evaluation over relational databases fits well in this explanation paradigm. Yet, these works fall short of providing practical solutions to the computational challenge inherent to the Shapley computation. We present in this paper two practically effective solutions for computing Shapley values in query answering. We start by establishing a tight theoretical connection to the extensively studied problem of query evaluation over probabilistic databases, which allows us to obtain a polynomial-time algorithm for the class of queries for which probability computation is tractable. We then propose a first practical solution for computing Shapley values that adopts tools from probabilistic query evaluation. In particular, we capture the dependence of query answers on input database facts using Boolean expressions (data provenance), and then transform it, via Knowledge Compilation, into a particular circuit form for which we devise an algorithm for computing the Shapley values. Our second practical solution is a faster yet inexact approach that transforms the provenance to a Conjunctive Normal Form and uses a heuristic to compute the Shapley values. Our experiments on TPC-H and IMDB demonstrate the practical effectiveness of our solutions.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-03514297/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-03514297/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-03514297/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-03514297/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- 2112.08874.pdf
- Accès libre
- Accéder au document