Course contentsShow
← Machine Learning and Deep Learning
Lesson 3217 of 3,53870. Interpretability: Feature-Based MethodsFree lesson

Computational Complexity and Sampling Strategies

Learn about the exponential complexity of exact SHAP and practical sampling strategies for approximation.

Computational Complexity and Sampling Strategies

You'll learn why computing exact SHAP values is computationally prohibitive and how sampling strategies make it practical.

The Exponential Wall

Computing exact SHAP values requires evaluating a model across all possible feature coalitions—that is, every subset of features. If you have n features, there are 2^n possible subsets to consider. For just 20 features, that's over 1 million evaluations. For 30 features, it's over 1 billion. This exponential complexity makes exact SHAP computation infeasible for real-world models with many features.

Think of it like planning seating arrangements for a dinner party: with 5 guests, there are 32 possible combinations of who shows up. With 20 guests? Over a million combinations to consider. The problem explodes exponentially.

Practical Sampling Strategies

Since exact computation is impossible for most cases, we use sampling strategies to approximate SHAP values:

Random sampling selects a subset of feature coalitions randomly, computing model predictions only for these samples. The more samples you take, the better your approximation—but the longer it takes.

KernelSHAP (as you learned earlier) uses weighted linear regression on sampled coalitions, cleverly weighting samples to prioritize the most informative feature combinations.

TreeSHAP and DeepSHAP avoid sampling entirely by exploiting model structure, achieving polynomial-time complexity instead of exponential—this is why they're so much faster for tree-based and neural network models.

The tradeoff is always accuracy vs speed: more samples mean better approximations but longer computation times. Typical implementations use hundreds to thousands of samples rather than the exponential number required for exactness.

Key Takeaway: Exact SHAP computation has exponential complexity (2^n), making sampling strategies essential; methods like random sampling approximate values in reasonable time, while structure-aware methods like TreeSHAP achieve polynomial complexity.