Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911841510227968 |
|---|---|
| author | Karmakar, Pratik Monet, Mikaël Senellart, Pierre Bressan, Stéphane |
| author_facet | Karmakar, Pratik Monet, Mikaël Senellart, Pierre Bressan, Stéphane |
| contents | Shapley values, originating in game theory and increasingly prominent in explainable AI, have been proposed to assess the contribution of facts in query answering over databases, along with other similar power indices such as Banzhaf values. In this work we adapt these Shapley-like scores to probabilistic settings, the objective being to compute their expected value. We show that the computations of expected Shapley values and of the expected values of Boolean functions are interreducible in polynomial time, thus obtaining the same tractability landscape. We investigate the specific tractable case where Boolean functions are represented as deterministic decomposable circuits, designing a polynomial-time algorithm for this setting. We present applications to probabilistic databases through database provenance, and an effective implementation of this algorithm within the ProvSQL system, which experimentally validates its feasibility over a standard benchmark. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_06493 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases Karmakar, Pratik Monet, Mikaël Senellart, Pierre Bressan, Stéphane Databases Artificial Intelligence Computational Complexity Shapley values, originating in game theory and increasingly prominent in explainable AI, have been proposed to assess the contribution of facts in query answering over databases, along with other similar power indices such as Banzhaf values. In this work we adapt these Shapley-like scores to probabilistic settings, the objective being to compute their expected value. We show that the computations of expected Shapley values and of the expected values of Boolean functions are interreducible in polynomial time, thus obtaining the same tractability landscape. We investigate the specific tractable case where Boolean functions are represented as deterministic decomposable circuits, designing a polynomial-time algorithm for this setting. We present applications to probabilistic databases through database provenance, and an effective implementation of this algorithm within the ProvSQL system, which experimentally validates its feasibility over a standard benchmark. |
| title | Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases |
| topic | Databases Artificial Intelligence Computational Complexity |
| url | https://arxiv.org/abs/2401.06493 |