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.
Introduction
In the fields of Explainable AI (XAI) and data management, identifying the specific inputs responsible for a particular output is a critical task. Game theory offers a robust framework for this through the Shapley value, which fairly distributes "credit" among players (or database facts) for a given outcome. While extensively studied in deterministic contexts, real-world data is frequently uncertain. This uncertainty is often modeled using Probabilistic Databases, where each fact exists with a certain probability.
The primary challenge addressed in this research is the computation of these scores when the "players" themselves are probabilistic. The authors introduce the concept of the Expected Score—the average Shapley or Banzhaf value across all possible "worlds" of a probabilistic database.
Defining the Expected Score
The core objective is to compute the expected value of a contribution score $c$ (like Shapley or Banzhaf) for a Boolean function $\phi$ over a set of variables $V$, where each variable $x \in V$ has an associated probability $p_x$.
Theoretical Framework and Reductions
A major theoretical contribution of this paper is the proof that computing expected Shapley/Banzhaf values is interreducible with computing the Expected Value (EV) of a Boolean function. This implies that the tractability landscape for both problems is identical: if the probability of a query being true can be calculated efficiently, so can the expected contribution of its constituent facts.
To establish these reductions, the authors employed polynomial interpolation techniques. By using carefully selected probability values, they were able to "extract" the necessary components of the Shapley score from the general probability function of the query.
Algorithms for Tractable Computation
For practical applications, the research focuses on deterministic decomposable circuits (d-D circuits). These are a form of knowledge compilation that allows complex Boolean logic to be represented in a way that facilitates efficient processing. The authors designed a bottom-up induction algorithm that traverses these circuits to compute scores in polynomial time relative to the circuit size.
Interestingly, the complexity varies between different power indices. While both are tractable on d-D circuits, Banzhaf values can be computed in linear time, whereas Shapley values require a more complex implementation with quadratic-to-quintic complexity.
Experimental Evaluation
The proposed algorithms were implemented within ProvSQL, an open-source PostgreSQL extension for handling database provenance. The system was evaluated using the TPC-H 1 GB benchmark, focusing on 8 standard queries modified to isolate core Boolean logic.
Key findings from the experiments include:
- Practical Feasibility: For most TPC-H queries, the combined time for provenance tracking and score computation was only a few seconds.
- Scalability: The system handled complex queries effectively. For instance, Query 5, involving over 1,000 gates, was processed in approximately 41 seconds.
- Efficiency: For many simpler queries, the overhead was negligible, often taking less than a second.
Conclusion
This work bridges the gap between game-theoretic importance measures and probabilistic data. By showing that the tractability of expected scores matches that of probabilistic query evaluation, the authors provide a clear roadmap for implementing explainability in uncertain databases. Future work will explore Fully Polynomial-Time Randomized Approximation Schemes (FPRAS) to handle "hard" queries (such as those with self-joins or complex negation) that cannot be efficiently compiled into small d-D circuits.
Summary updated