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.
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:
- 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.
- Knowledge Compilation: They focus on deterministic decomposable (d-D) circuits. These are specialized representations of Boolean logic that allow for efficient probability calculations.
- 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.
- 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.
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