The shapley values are calculated independently for each test data point and then averaged to the overall shapley values.
Our implementation
In our implementation, there is a dependence between the shapley values of each test data point:
values: NDArray[np.float_] = np.zeros_like(u.data.indices, dtype=np.float_)
n = len(u.data)
yt = u.data.y_train
iterator = enumerate(zip(u.data.y_test, indices), start=1)
for j, (y, ii) in tqdm(iterator, disable=not progress):
value_at_x = int(yt[ii[-1]] == y) / n
values[ii[-1]] += (value_at_x - values[ii[-1]]) / j
for i in range(n - 2, n_neighbors, -1): # farthest to closest
value_at_x = (
values[ii[i + 1]] + (int(yt[ii[i]] == y) - int(yt[ii[i + 1]] == y)) / i
)
values[ii[i]] += (value_at_x - values[ii[i]]) / j
for i in range(n_neighbors, -1, -1): # farthest to closest
value_at_x = (
values[ii[i + 1]]
+ (int(yt[ii[i]] == y) - int(yt[ii[i + 1]] == y)) / n_neighbors
)
values[ii[i]] += (value_at_x - values[ii[i]]) / j
The relevant part is that values is initialized outside the loop over data points but then used to initialize the recursive calculation of shapley values inside the loop in each iteration. Starting with the second iteration, this produces different results.
Test results
The differences in implementation seem to matter for the results. I tested a new implementation that is very close to the paper against montecarlo estimates and the old implementation. The new implementation agrees with the montecarlo estimates but the old one does not. Here are the result:
Description of the algorithm
The KNN Shapley method is based on this paper
The basic algorithm is:
The shapley values are calculated independently for each test data point and then averaged to the overall shapley values.
Our implementation
In our implementation, there is a dependence between the shapley values of each test data point:
The relevant part is that
valuesis initialized outside the loop over data points but then used to initialize the recursive calculation of shapley values inside the loop in each iteration. Starting with the second iteration, this produces different results.Test results
The differences in implementation seem to matter for the results. I tested a new implementation that is very close to the paper against montecarlo estimates and the old implementation. The new implementation agrees with the montecarlo estimates but the old one does not. Here are the result: