Path-Dependent Tree SHAP in C++

July 2026 · 18 min read

The exact coalition implementation is clear but exponential. A practical tree-specific implementation uses the tree path and training covers. This post keeps the implementation intentionally small: it computes expectation changes along the hot path and assigns each change to the split feature. It is not a full optimized Tree SHAP library, but it exposes the structural advantage over black-box sampling.

Expected Value from Covers

double expected_value(Node* n) {
    if (n->leaf) return n->value;
    double wl = (double)n->left->cover / n->cover;
    double wr = (double)n->right->cover / n->cover;
    return wl * expected_value(n->left)
         + wr * expected_value(n->right);
}

Path Contribution Walk

vector<double> path_dependent_contrib(Node* root,
                                      const vector<double>& x,
                                      int m) {
    vector<double> phi(m, 0.0);
    Node* cur = root;
    double before = expected_value(cur);

    while (!cur->leaf) {
        int f = cur->feature;
        Node* next = x[f] < cur->threshold ? cur->left : cur->right;
        double after = expected_value(next);
        phi[f] += after - before;
        before = after;
        cur = next;
    }
    return phi;
}

This compact version attributes each conditional-expectation jump to the feature that caused the branch. Full Tree SHAP is more careful: it averages over all orders in which path features could be revealed. The simplified walk is still useful for understanding why tree structure makes row-level explanations cheap.

Ensemble Additivity

vector<double> ensemble_contrib(const vector<Node*>& trees,
                                const vector<double>& x,
                                int m,
                                double learningRate) {
    vector<double> total(m, 0.0);
    for (Node* t : trees) {
        vector<double> one = path_dependent_contrib(t, x, m);
        for (int j = 0; j < m; ++j)
            total[j] += learningRate * one[j];
    }
    return total;
}