Introduction
As machine learning models grow in complexity, the demand for Explainable AI (XAI) has surged. One of the most prominent tools for interpretability is the SHAP (SHapley Additive exPlanations) score, derived from cooperative game theory. SHAP scores provide a rigorous way to attribute a model's output to its input features. However, calculating exact SHAP scores is generally a #P-hard problem, as it typically requires evaluating an exponential number of feature combinations.
This research identifies a significant class of models where exact SHAP scores can be computed efficiently: tractable Boolean circuits. Specifically, the authors prove that for circuits satisfying the properties of determinism and decomposability, SHAP scores can be calculated in polynomial time.
Tractable Boolean Circuits
The study focuses on Boolean classifiers—models that map binary inputs to a binary output. These are often represented as circuits composed of logic gates.
To achieve tractability, the authors focus on two structural properties:
- Decomposability: An AND-gate is decomposable if the sets of variables in the sub-circuits rooted at its children are disjoint.
- Determinism: An OR-gate is deterministic if, for any given input, at most one of its children evaluates to true.
Circuits possessing both properties (such as d-DNNFs) are known to be efficient for tasks like model counting. This paper extends that efficiency to SHAP score computation.
The Bottom-Up Algorithm
The core contribution of the paper is a bottom-up dynamic programming algorithm. Instead of iterating through exponential feature subsets, the algorithm traverses the circuit from the leaves (inputs) to the root (output). At each gate, it computes and stores specific combinatorial values (denoted as $\alpha$ values in the research) that represent the contribution of that sub-circuit to the final SHAP score.
This approach ensures that the total computation time remains polynomial relative to the size of the circuit. The algorithm is versatile enough to handle product distributions, where each input feature has an independent probability of being true, rather than assuming a simple uniform distribution.
The Boundaries of Tractability
A key theoretical insight of the paper is the "hardness boundary." The authors demonstrate that both determinism and decomposability are strictly necessary for efficiency. They provide formal proofs showing that if either property is removed, the problem of computing SHAP scores immediately reverts to being #P-hard. This establishes a "Goldilocks zone" for XAI: circuits that are succinct enough to represent complex logic but structured enough to remain explainable.
Key Results and Implications
- Broad Applicability: The polynomial-time guarantee for deterministic and decomposable circuits automatically extends to other common model classes, including Binary Decision Trees, Ordered Binary Decision Diagrams (OBDDs), and Free Binary Decision Diagrams (FBDDs).
- Theoretical Foundation: By mapping the computational limits of SHAP, the research provides a clear guide for developers choosing model architectures that require rigorous interpretability.
- Efficiency: The proposed algorithm allows for exact explanations in scenarios where researchers previously had to rely on potentially inaccurate heuristic approximations.
Limitations and Future Directions
While this work marks a significant step forward, it is currently limited to Boolean features and outputs. Real-world datasets often involve continuous variables and regression tasks. Additionally, the assumption of feature independence (product distributions) does not account for correlations between features (e.g., age and income). Extending this framework to handle continuous data and dependent feature distributions remains a primary goal for future research in the field of tractable XAI.
Summary updated