Question to Kernel SHAP weights

[mayer79]

Fantastic code.

One question regarding ShapleyRegression() in "shapley.py", which I feel is explaining how iterative Kernel SHAP works.

In your paper "Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression" you are drawing coalition vectors $z$ according to the Kernel Weight distribution.

What I originally have thought:

"Let's draw $z$ such that the count of "1" follows the Kernel Weight distribution."

But when I read your code below (which I think is correct), then my thinking was actually wrong, because the Kernel Weight distribution does not appear at all in your code.

Was my thinking wrong?

   # Weighting kernel (probability of each subset size).
    num_players = game.players
    weights = np.arange(1, num_players)
    weights = 1 / (weights * (num_players - weights))
    weights = weights / np.sum(weights)

    [...]

    num_included = np.random.choice(num_players - 1, size=batch_size,
                                        p=weights) + 1
    for row, num in zip(S, num_included):
        inds = np.random.choice(num_players, size=num, replace=False)
        row[inds] = 1

[iancovert]

Hey, thanks for checking out the code. So yes the goal is to sample from $\mu_{\text{Sh}}(S)$ as defined in the paper (bottom of page 2 on RHS).

The naive way of doing this would be: instantiate a vector of length $2^d$ with one entry corresponding to each subset $S$, get weights according to $\mu_{\text{Sh}}(S)$ (which requires summing and normalizing), then sample $S$. I didn't want to do this because it's a large vector and the very small probabilities could be numerically unstable.

Instead, what the code does is 1) consider how much probability mass is on all subsets of size $k$ for each $k$, 2) sample $k$ accordingly, 3) sample some $|S| = k$ uniformly at random. Let me know if that makes sense.

[mayer79]

It makes perfect sense, thanks so much for clarifying. I have crosschecked with Scott's code in "shap", and he does it exactly like this (when sampling us required).

My project has been fixed accordingly.