Shapley Value Estimation

The foundational approximation method that estimates Shapley values by randomly sampling coalitions from the power set. Instead of evaluating all 2^N possible feature subsets, the algorithm draws random permutations of features and computes the marginal contribution of each feature when added to the preceding subset. The Shapley value is the average marginal contribution across all sampled permutations. Variance reduction techniques like paired sampling and antithetic sampling dramatically improve convergence rates, reducing the number of model evaluations required for stable estimates.

Statistical methods that accelerate convergence in Monte Carlo Shapley estimation by reducing the variance of the estimator without increasing the number of samples. Paired sampling evaluates each coalition with and without the target feature in a single pass, halving the required model evaluations. Antithetic sampling pairs each random permutation with its reverse, exploiting symmetry to cancel estimation noise. These techniques can reduce the number of required samples by an order of magnitude while maintaining the same estimation accuracy.

Two fundamentally different estimation strategies distinguished by how they handle feature correlations. Interventional SHAP breaks correlations by sampling feature values from their marginal distributions, answering 'what would the model predict if we intervened on this feature?' This reflects causal relationships but may evaluate the model on unrealistic data points. Observational SHAP preserves correlations by conditioning on observed feature values, answering 'what does this feature contribute given the natural data distribution?' The choice between them significantly impacts both computational cost and the interpretation of results.

A model-agnostic estimation method that solves a weighted least squares problem to recover Shapley values. It uses a specially designed Shapley kernel to weight coalitions, giving higher importance to small and large coalitions. The algorithm samples coalitions, evaluates the model with features either present or replaced by background values, and fits a linear explanation model. This approach is additive and satisfies local accuracy, but requires careful selection of the background dataset to represent missing features.

A model-specific algorithm that computes exact Shapley values for tree-based models in polynomial time O(TLD²), where T is trees, L is leaves, and D is depth. It tracks the proportion of training samples flowing through each path to calculate conditional expectations directly from the tree structure, avoiding sampling entirely. This eliminates the variance introduced by approximation methods and guarantees the efficiency property holds exactly for every prediction.

A high-speed approximation algorithm for deep learning models that combines DeepLIFT multipliers with Shapley value calculations. It linearizes the network by computing the gradient of the output with respect to a reference input, then propagates SHAP values backward through the layers. DeepSHAP assumes feature independence and uses a single reference value, making it fast but potentially less accurate when features are strongly correlated or when the model is highly non-linear.

Methods to accelerate convergence when estimating Shapley values via Monte Carlo sampling. Antithetic sampling pairs each random coalition with its complement to cancel variance. Paired sampling evaluates the model with and without a target feature on the same background sample. These techniques exploit the structure of the Shapley value formula to reduce the number of model evaluations required for a given estimation error, critical when model inference is expensive.

Two distinct formulations for handling missing features during estimation. Interventional SHAP breaks feature correlations by sampling from the marginal distribution, answering 'what if' causal questions. Observational SHAP conditions on observed feature values to preserve correlations, reflecting the model's behavior on the natural data manifold. The choice between them significantly impacts attributions when features are correlated, with interventional SHAP aligning with causal reasoning and observational SHAP with descriptive analysis.

The choice of reference samples used to represent missing features critically impacts SHAP value estimation. A representative background should capture the feature distribution the model expects. Common strategies include using the training data mean, a random subset of training instances, or k-medoids clustering to select diverse prototypes. A poorly chosen background can produce misleading attributions by evaluating the model on unrealistic feature combinations outside its training distribution.