Expected Shapley-Like Scores of Boolean functions: Complexity and Applications to Probabilistic Databases

Pratik Karmakar, Mikaël Monet, Pierre Senellart, Stéphane Bressan

In the world of data science and AI, we often ask: "Which piece of data is responsible for this result?" Whether it's a machine learning model's prediction or a complex database query, we want to attribute "credit" or "blame" to specific inputs. This is where the Shapley value—a Nobel-prize-winning concept from cooperative game theory—has become a cornerstone of Explainable AI (XAI).

However, standard Shapley values assume that your data is certain. In reality, data is often messy, noisy, or probabilistic. A recent paper by Karmakar et al., presented at PODS 2024, addresses this gap by introducing Expected Shapley-Like Scores for probabilistic settings.

The Challenge of Uncertainty

Imagine running a query on a database where records are only "probably" true—perhaps sourced from OCR, sensors, or noisy web crawls. If the query returns a result, how much did a specific, uncertain record contribute to that outcome?

Existing methods for calculating Shapley values (and similar metrics like Banzhaf values) work well for "certain" data. However, in a Probabilistic Database, every "player" (data record) has a probability of existing. The core challenge is complexity: calculating Shapley values is notoriously difficult (#P-hard). Researchers feared that adding a layer of probability would make an already hard problem impossible.

The formal definition of the Expected Score (EScore) problem addressed in the paper.

Bridging Game Theory and Database Theory

The authors prove that calculating the "expected" contribution of a data point in an uncertain environment is computationally equivalent to simply calculating the probability of the result itself. They achieve this through several key techniques:

  1. Theoretical Reductions: Using polynomial interpolation, they prove that computing expected scores is "interreducible" with computing the expected value (the probability) of the underlying Boolean function. If one is tractable, the other is too.
  2. Knowledge Compilation: They focus on deterministic decomposable (d-D) circuits. These are specialized representations of Boolean logic that allow for efficient probability calculations.
  3. Algorithmic Innovation: They designed a bottom-up induction algorithm for d-D circuits. While the theoretical worst-case complexity is $O(|C| \cdot |V|^5)$, it is optimized for practical performance.
  4. System Integration: The algorithm was implemented in ProvSQL, an open-source PostgreSQL extension for database provenance, and tested against the industry-standard TPC-H benchmark.

Key Insights: Why Probability Matters

The most significant finding is that uncertainty doesn't fundamentally change the problem's difficulty. The tractability of expected scores perfectly mirrors the tractability of probability evaluation.

Furthermore, the "Expected" version of these scores provides a much more nuanced view of contribution. As shown in the table below, variables with the same standard Shapley score can have different Expected Scores when their probabilities of existence are factored in.

Comparison of standard Shapley scores vs. Expected Shapley scores. Note how the EScore differs from the base Score when probabilities are introduced.

Results and Practical Feasibility

In experiments on TPC-H queries, the system computed expected scores for thousands of output tuples in seconds. For most queries, the time to compute the expected Shapley value was comparable to the time taken to evaluate the query itself. Even a complex query (Query 5) was processed in approximately 41 seconds, demonstrating that exact computation of these scores is feasible for real-world XAI applications.

While the $O(V^5)$ theoretical bound suggests potential slowdowns for extremely large datasets, the current work opens the door for future exploration into approximation algorithms (like Monte Carlo sampling) and broader query support involving complex aggregations like SUM or AVG.

Reference: Karmakar, P., Monet, M., Senellart, P., & Bressan, S. (2024). Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases. Proceedings of the ACM on Management of Data (PODS).

Summary updated

Abstract

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.
BibTeX
@inproceedings{karmakar2024expected,
  author = {Pratik Karmakar and Mikaël Monet and Pierre Senellart and Stéphane Bressan},
  title = {{Expected Shapley-Like Scores of Boolean functions: Complexity and Applications to Probabilistic Databases}},
  booktitle = {Proceedings of the ACM on Management of Data},
  year = {2024},
  doi = {10.1145/3651593},
}
Figure