From Decision Trees to Boolean Logic: A Fast and Unified SHAP Algorithm

AI summary

Overview

Research area: Explainable machine learning — specifically the computation of SHAP (SHapley Additive exPlanations) feature attributions for decision tree ensembles, bridging game theory, Boolean logic, and high-performance numerical computing.

Technical level: Advanced. The paper assumes familiarity with Shapley values, cooperative game theory, decision tree internals, and pseudo-Boolean representations, though its central idea can be grasped at an intermediate level.

One-sentence scope: The paper introduces Woodelf, a pure-Python, vectorized algorithm that unifies Path-Dependent and Background SHAP — plus Shapley interaction, Banzhaf, and Banzhaf interaction values — by encoding decision trees and background data as weighted pseudo-Boolean formulas and evaluating them in linear time.

What This Paper Is About

SHAP assigns contribution values to features in a trained model, and it is widely used in finance, advertising, and medicine. Two main variants exist: Path-Dependent SHAP, which exploits the tree structure, and Background SHAP, which uses a background dataset to estimate feature distributions and is described as the more accurate of the two. The two have historically been treated as separate problems requiring separate algorithms. This paper's goal is to show that both — and several other game-theoretic attribution metrics — can be computed by one fast, unified algorithm that runs efficiently on both CPU and GPU hardware.

Key Contributions

1. A unified algorithm (Woodelf) across SHAP variants. The paper demonstrates that a single algorithm can handle both Path-Dependent and Background SHAP, which the authors state were previously thought to require distinct approaches.

2. A metric-generic framework. Woodelf computes Shapley values, Shapley interaction values, Banzhaf values, Banzhaf interaction values, and, per the authors, any other value over the Path-Dependent or Background characteristic functions that satisfies the linearity property. The paper claims it is the first algorithm to support such a broad range of metrics.

3. Linear-time Shapley computation for Weighted Disjunctive Normal Form (WDNF) formulas. Sections 2 and 3 introduce a linear-time algorithm for Shapley values, Shapley interaction values, Banzhaf values, and Banzhaf interaction values over WDNF formulas, with the Shapley case proven correct in Appendix B using the linearity and null-player-out properties.

4. A GPU-friendly, pure-Python implementation. All major algorithmic steps are expressed as standard vectorized operations, implemented in NumPy, SciPy, and CuPy with no custom C++ or CUDA code — in contrast to shap and other state-of-the-art implementations, which the paper says rely heavily on custom C++ and CUDA. The package is available via the Woodelf Python package.

Main Findings

• Large-scale speedups on CPU and GPU: On a dataset with 3,000,000 rows, 5,000,000 background samples, and 127 features, Woodelf computed all Background Shapley values in 162 seconds on CPU and 16 seconds on GPU, compared to 44 minutes required by the best method on any hardware platform — a 16× and 165× speedup, respectively.

• Reported speedups on two industrial datasets: In Section 10, the authors report 24× to 333× speedups on GPU and 16× to 31× speedups on CPU versus the state-of-the-art Background SHAP method on any hardware platform, evaluated on two large industrial datasets. The specific per-dataset benchmark tables are not included in the provided content.

• Complexity reduction for Background SHAP: Prior work (PLTreeShap, Zern et al. 2023) reduced Background SHAP complexity from O(mn) — where n is the number of consumers and m is the background size — to O(m+n). Woodelf derives an O(n+m) formulation that leverages GPU-friendly matrix multiplication and then computes per-consumer values in O(nLD) time, where L is the number of leaves and D the tree depth.

• Path-Dependent SHAP as a special case: Path-Dependent SHAP is obtained by replacing the Background frequency vector with a Path-Dependent frequency vector derived from the node cover property — the number of training samples that reached each node during training — requiring no separate algorithm.

• Generalization beyond Shapley: Because the derivation relies only on the linearity property of Shapley values, the same framework extends to Shapley interaction values, Banzhaf values, and Banzhaf interaction values. Banzhaf values satisfy three of Shapley's four properties (null player, symmetry, and linearity) but not efficiency.

• Ensemble handling through linearity: To compute values for a decision tree ensemble, one runs Woodelf on each tree and sums the results; correctness follows from the linearity property of both Shapley and Banzhaf values.

• Algorithmic optimizations: The implementation uses sparse matrix multiplication (reducing the cost of one step from O(4^D) to O(3^D) and improving overall complexity), a caching mechanism for leaves sharing the same features and path length, the fact that neighboring leaves' decision patterns differ only in the last bit, the symmetry φ_{i,j} = φ_{j,i} (halving interaction computations), and depth-dependent unsigned integer types (uint8, uint16, uint32).

Methodology in Plain English

The authors reframe SHAP as a Boolean logic problem. For each consumer row, they build a pseudo-Boolean formula in Weighted Disjunctive Normal Form: a weighted sum of "cubes," where a cube is a set of literals (a variable or its negation). Each cube corresponds to one root-to-leaf path in the tree, and its weight is that leaf's output value. A variable set to 1 means the feature is present (using the consumer's value); set to 0 means it is missing (using a baseline or background value). Evaluating the formula then reproduces the model's prediction under any subset of available features.

To build these cubes, the algorithm computes a "decision pattern" for each consumer at each leaf — a binary string recording whether the consumer would follow the root-to-leaf path at each node — using a breadth-first traversal called CalcDecisionPatterns, which runs in O(nL) time. When the consumer's pattern and the baseline's pattern disagree at a node, that node's feature becomes a literal in the cube; when both agree the node adds nothing; when both disagree with the path the cube is unsatisfiable. This mapping is precomputed with MapPatternsToCube.

For Background SHAP, the paper avoids the naive loop over every (consumer, background sample) pair. Instead, it counts how many background rows produce each decision pattern (computed in O(mL) using value_counts), then replaces the per-sample sum with a matrix-vector product: for each leaf and feature, a sparse "Shapley matrix" is multiplied by a normalized frequency vector, giving a per-leaf contribution vector independent of any individual background row. Once these vectors are precomputed, answering a consumer only requires looking up the element indexed by that consumer's decision pattern. The same machinery works for Banzhaf and interaction values because the derivation only invokes linearity.

Why This Matters

Impact on research. The paper argues against the assumption that Path-Dependent and Background SHAP need distinct algorithms, offering a single Boolean-logic formulation that also covers Banzhaf values and interaction values. It connects SHAP computation to existing theoretical results on pseudo-Boolean functions and weighted DNF, which the authors note is #P-Hard in general — meaning the structure of WDNF formulas arising from decision trees is what makes linear-time evaluation possible. It also demonstrates that a pure-Python, SIMD-style vectorized design can outperform implementations built on custom C++ and CUDA.

Real-world applications.

• Finance: SHAP is used in finance for interpreting tree-ensemble models; the paper lists finance among the domains where SHAP is widely used.
• Advertising: listed alongside finance as a domain where SHAP attribution is widely deployed.
• Medicine: also listed as a key application domain, where local attribution is described as often crucial for regulatory compliance.
• Fraud detection: one of the two evaluation datasets is the IEEE-CIS fraud detection dataset from Kaggle, alongside the KDD-Cup 99 dataset.

Industry relevance. Regulatory compliance frameworks require explaining individual predictions, and global attribution — often built by aggregating many local attributions — is described as essential for model comprehension and feature selection. The ability to compute Background SHAP on datasets of millions of rows with millions of background samples in minutes rather than the 44 minutes reported for the best alternative makes full-background attribution practical on commodity CPU hardware as well as GPUs. The absence of custom C++ or CUDA code simplifies integration and extensibility into existing Python frameworks.

Future Directions

• Extending beyond linearity-based metrics. Woodelf covers any metric over the Path-Dependent or Background characteristic function that satisfies linearity. Metrics that do not satisfy linearity fall outside the framework, and the paper notes that for models such as neural networks the computation is #P-Hard, with approximation methods used instead.

• Managing the 3^D and 4^D growth with tree depth. The paper's own complexity analysis shows matrices of size 4^D and pattern dictionaries of size 3^D, with sparsity reducing one step to O(3^D). How the approach scales to substantially deeper trees than those tested is a natural open question.

• Broadening the empirical evaluation. The reported experiments cover two industrial datasets (IEEE-CIS and KDD-Cup). Independent evaluation on other ensembles, model libraries, and metric types (particularly interaction values, which are the least covered by existing baselines) would test the generality claim.

• Tighter integration and comparison with GPU-native implementations. The paper positions Woodelf against GPUTreeSHAP and FourierSHAP, noting the latter performs well on models with a small number of features. Head-to-head comparison on those regimes, and packaging Woodelf as a drop-in replacement inside existing pipelines, are logical next steps.

Target Audience

This paper is most valuable to machine learning engineers and researchers working on model interpretability, particularly those deploying SHAP at scale on tree-ensemble models such as XGBoost, Random Forest, and CatBoost. It will also interest practitioners in regulated industries — finance, insurance, advertising, and medicine — who need fast, accurate feature attributions for compliance and model auditing. Researchers in game theory, Boolean satisfiability, and pseudo-Boolean optimization will find the WDNF-based linear-time Shapley derivation relevant, as will performance engineers focused on GPU-accelerated and vectorized numerical algorithms in pure Python.

Authors’ abstract

SHapley Additive exPlanations (SHAP) is a key tool for interpreting decision tree ensembles by assigning contribution values to features. It is widely used in finance, advertising, medicine, and other domains. Two main approaches to SHAP calculation exist: Path-Dependent SHAP, which leverages the tree structure for efficiency, and Background SHAP, which uses a background dataset to estimate feature distributions. We introduce WOODELF, a SHAP algorithm that integrates decision trees, game theory, and Boolean logic into a unified framework. For each consumer, WOODELF constructs a pseudo-Boolean formula that captures their feature values, the structure of the decision tree ensemble, and the entire background dataset. It then leverages this representation to compute Background SHAP in linear time. WOODELF can also compute Path-Dependent SHAP, Shapley interaction values, Banzhaf values, and Banzhaf interaction values. WOODELF is designed to run efficiently on CPU and GPU hardware alike. Available via the WOODELF Python package, it is implemented using NumPy, SciPy, and CuPy without relying on custom C++ or CUDA code. This design enables fast performance and seamless integration into existing frameworks, supporting large-scale computation of SHAP and other game-theoretic values in practice. For example, on a dataset with 3,000,000 rows, 5,000,000 background samples, and 127 features, WOODELF computed all Background Shapley values in 162 seconds on CPU and 16 seconds on GPU - compared to 44 minutes required by the best method on any hardware platform, representing 16x and 165x speedups, respectively.