From Scratch · C++ · ML · Explainability
· Tree SHAP
Tree SHAP from Scratch in C++
This implementation sub-series builds the mechanics behind Tree SHAP in plain C++. It starts with exact coalition enumeration for a tiny tree so the Shapley definition is visible, then moves to a path-dependent implementation that uses tree sample counts to compute row-level explanations without treating the model as a black box.
Implementation Roadmap
Exact Tree SHAP for a Small Tree
Enumerate feature coalitions, evaluate a tiny tree with missing features, and average marginal contributions exactly.
Path-Dependent Tree SHAP
Use training counts along hot and cold branches to compute row-level attributions from tree structure.
Why not reuse Kernel SHAP? Kernel SHAP works for any callable model, but it samples masks and fits a regression. Tree SHAP uses the trained tree's structure directly, so it is the right implementation path when the model is a decision tree or tree ensemble.