Amortized SHAP values via sparse Fourier function approximation

We appreciate your thoughtful and insightful comments. Please find our responses below.

My biggest concern with this submission is that the fact that it's only applicable to pseudoboolean functions is far too restrictive. I don't think that limitation can be overcome simply by "discretizing continuous features into quantiles" to transform them into categorical features. Post-hoc explanations like SHAP values are largely a useful area of research because they enable interpretation of real-world deployments of machine learning methods. I have trouble thinking of how many real-world problems out there can be easily tackled with boolean inputs. What are the main challenges towards extending this work to continuous valued problems? is it possible at all? at the very least a discussion is warranted. I'm afraid without that this paper, while theoretically neat would just end up without a significant impact.

In summary, the paper is lacking: a) Concrete examples of real-world problems where the boolean limitation is and isn't problematic. b) Discussion of potential challenges and ways of extending this method to continuous-valued cases. c) impact of discretization on model and SHAP performance when applied to otherwise continuous-valued datasets.

This is indeed a valid point that you have brought up and a point that we also care about very much. There is certainly ways that one could think of extending this framework to generalize to continuous features that we will discuss now. But before that we would like to clarify that all the datasets we used for the experiments of this paper were inherently discrete and consisted of purely categorical features (not just binary). Therefore, these were examples of real-world problems where the boolean limitation isn’t problematic. We explain in more detail later in answer to your question 3.

Back to the topic of continuous features, we already have ideas of how one can potentially generalize our results and we present them now.

Case of trees: Our paper shows order of magnitude speedups for the case of trees. When one thinks about trees it can be seen that they are inherently discrete structures even though they perfectly work for continuous features. By setting a threshold, i.e. a continuous number to define a split of the node, all trees are inherently in fact binary. This way of thinking gives one very simple but crude extension of the current framework: To assign to each node of the tree a binary feature specifying whether a certain continuous feature is bigger or smaller than a certain threshold (and assigning a zero or one). This would increase the feature dimension of the problem to the number of nodes in the tree in the worst case scenario. This idea does not perfectly work since some combination of zeros and ones are not allowed but we have found mechanisms of smarter encodings that would make this transformation work. They are not mentioned in this paper and we think the current work can lay a foundation and ground of this further extension.

A second and more principled and less crude way to think about the case of trees is to not use a Fourier transform that we are using now which is over $Z_2 \times Z_2 \times ... Z_2$ (n times where n is the number of features). But rather use a transform over $Z_{K_1}, \times, Z_{K_n}$ where $K_i$ is the number of distinct thresholds feature $i$ has in the tree. Coming up with a closed form solution for the SHAP values in this Fourier basis is an interesting question that we also plan to look at. It is not too far-fetched to think that we can also find a closed form solution to this discrete Fourier basis. This would perfectly handle the case of any tree. Note that by a recursive formula one can readily compute the Fourier transform of trees as well.

MLPs: Regarding the case of MLPs with continuous input features, one can not simply resort to the discrete Fourier transform of type $Z_k \times \dots Z_k$ to perfectly capture this structure as it is no longer inherently discrete (like trees). This is slightly tricky scenario because it requires us to characterize the relationship of continuous and discrete Fourier transforms of neural networks functions. In classical signal processing there are results which characterize what level of granularity in discretization is required to reconstruct continuous transform with the discrete one for a given level of error. These results depend on the Spectrum of the continuous transform. For example the case of super imposition of sinusoids, where the spectrum has a bounded domain give rise to the Nyquist rate etc.

(Continued in the next comment)

We thank the author for clarifying and reorganizing the paper following the comments. Most of the questions and problems mentioned were addressed.

The only remaining limitation in my mind is the theoretical results being on the simpler side. While it is possible that the writing could be more concise, the eagerness of the authors to respond to the comments made me believe that future corrections/improvement suggestions would be addressed.

Due to the last point, I am more leaning toward acceptance, and while not sufficiently to bump my rating of the paper to 8 (accept) if there were more fine-tuned rating options I would have bumped my rating of the paper to 7 (weak-accept).

We are happy that we could address your concerns. Thank you for reconsidering your score, it’s greatly appreciated!

Thank you for your thorough review and your great attention to the details. It is delightful to see you found the text fully contained and highlighted the originality of the direction of our workWe are happy to discuss the weaknesses you mentioned and go through the questions.

The theoretical results are on the simpler side, specifically the proofs span around 2.5 pages and seem to be on the simpler side. While there is absolutely no need to overcomplicate the proofs and short proofs have merit, I believe that it should be noted.

We agree and also believe there is no need to complicate proofs for the sake of lengthening them.

The writing seems to require some improvement. Specifically, I felt that the abstract, introduction, and background were on the cumbersome side and should be shortened. As a consequence, the introduction only "moved me over the fence" on the significance of the problem and did not truly excite me. It also seemed to me that the abstract is rather long and is somewhat repeated in the introduction.

We understand your concern. Since the paper requires quite some background explanation especially on the Fourier approximations, which are not typical in papers in this field, the abstract and introduction has become longer than the typical paper. If accepted we will go over these sections again and try to decrease redundancies. We are very much open to suggestions from you about parts that you felt like were unnecessary and/or pedantic/boring.

Nonetheless, regarding the approximation of neural networks, I am intrigued by the exact values (as a function of the approximation) of the representation for common networks (say AlexNet). It seems that this is an active research area in itself, thus perhaps there are yet exact values for such networks. If there are such results consider including them since it could give a good picture of the complexity of approximating (with theoretical guarantees) the SHAP value via the proposed method.

We thank the reviewer for this suggestion and we think that indeed that this is indeed an interesting and impactful direction to take. One can think of CNNs, as roughly speaking, MLPs that slide along the data channels spatial positions. Therefore, one could apply the same methodology and spectral bias results that we presented here. However the extension requires more careful thinking and a more work. We are not aware of any results that try to carefully extend Spectral bias results (in the spirit mentioned above) to the case of CNNs. Perhaps the reason could be that, there was not much practical value to do so. We believe our paper provides at least some incentive, that these spectral bias results can be concretely used for some important down stream task, i.e. estimating SHAP values.

Regarding your question about other results in the literature for how well deep shap methods approximate the true SHAP values. Again to the best of our knowledge the goto method for this is DeepLift and FastSHAP. Which we have included as a baseline. We have also documented the $R^2$ scores we get for the faithfulness of their SHAP values to ground truth values. As mentioned in the paper, unlike FourierSHAP, for these methods one can not reliably have a fine-grained control over the level of approximation and trade it off with computation. In Fourier SHAP there is at least a proxy for the level of accuracy of the SHAP values namely the Fourier approximation error. Moreover DeepLift is not model agnostic and assumed full access to the model architecture.

When mentioning the "exponential sum" in the second paragraph of page two consider giving a reference to the full expression on page 3. I am unsure if this is due to me being unfamiliar with the matter, but noting the sum over the exponential number of combinations simply as "exponential sum" rather confused me initially.

That is indeed a valid point, and the whole line can be written clearer. We updated the first line of that paragraph and it is reflected in the updated pdf.

The first line of Section 2.2 seems to require rewriting.

Thanks for the catch. We rewrote the first sentences as follows: Here we review the notions of the Fourier basis and what we mean by sparsity. We will later use sparse Fourier representation of functions to compute SHAP values. In this work, ...

Hope it is more clear now.

I would prefer the machine properties in the experimental section, and for you to include more details such as CPU and RAM.

All experiments are ran on servers with Intel(R) Xeon(R) CPU E3-1284L v4 @ 2.90GHz, restricting the memory/RAM to 20 GB, which was managed with Slurm. We will add this detail to Appendix F, Experiment Details. We will make sure to add more details about the setup in the main text as well.

Thank you very much for your thorough comment and the subtle questions you asked. We are delighted that you find our work important and beneficial for explainable ML community. We are happy to address some of the points mentioned and answer your questions.

1- The proposed method is limited to binary features or categorical data that can be presented using one-hot encoding.

We have addressed this concern quite extensively in our answer to reviewer g97w Q1. We ask you to kindly read this section and tell us what you think. There we mentioned our ideas for extending this work to continuous domain, as well as highlighting the scope of binary / categorical data.

2- FourierSHAP is not a model-agnostic explanation method, e.g., KernelSHAP, i.e., does not explain any black-box model but is limited to either tree-based models or neural networks (or any sparse and low-degree functions).

We believe there has been a misunderstanding regarding the model-agnostic nature of FourierSHAP. The only requirement for applying FourierSHAP is query access to the model. There are no assumptions that we know anything more about the model's internal structure (such as structure of the MLP or the tree), and the method can be used with any black-box model as long as you can give input x and query the value i.e. get $f(x)$

The reason we specifically mentioned tree-based models and MLPs in our paper was to highlight the expressive class of functions namely the Fourier sparse functions. Both of these models are representative examples of functions that have sparse Fourier representations. This was not intended to imply that FourierSHAP is limited to these models. In fact, FourierSHAP can be applied to any black-box model, regardless of its type or structure.

For example, in our black-box experiments with GB1 and avGFP, we applied FourierSHAP without relying on any structural knowledge of the MLPs. For these MLPs, we make queries to the model without accessing its weights or architecture. Similarly, while we utilized the tree structure for extracting the sparse Fourier transform from tree-based models, we could have treated the tree as a black box and still applied the Fourier methodology. This would have taken longer, but it would have worked. These experiments show that FourierSHAP is truly model-agnostic.

It is also important to note that many model-agnostic explanation methods, such as LIME, inherently assume some form of regularity in the model to make the method effective. For instance, LIME assumes that the model can be locally approximated by a linear function. Similarly, FourierSHAP relies on the assumption that a model can be well-approximated by a sparse Fourier representation.

3- The experiments are limited, including only four datasets.

We appreciate the reviewer’s concern regarding the number of datasets used in our experiments. While we only included four datasets in the current study, these datasets were carefully selected to showcase the versatility and effectiveness of FourierSHAP across different types of models (trees and MLPs) and domains (biology and discrete GPU hyperparamer performance). We believe that this initial set provides evidence of the method's applicability.

4- The metric used to evaluate the accuracy of the SHAP approximations does not adequately capture how closely the approximated values align with the ground truth, nor does it assess the agreement in feature ranking based on their relative importance.

Given the fact that on our 4 datasets are all linear regression datasets we think that the magnitude of the SHAP importance value is also of importance (in addition to the rank). Therefore the metric should capture that as well. If the datasets were classification, perhaps the ranking would have been a better metric as there the magnitude is less meaningful.

1- Line 105 says, ``This was not formerly possible with these two black box methods." which two black-box methods is the line referring to?

DeepLift and FastSHAP mentioned in line 102. We will try to rewrite line 105 to avoid the confusion.

2- In the experiments, why were not all the algorithms trained and explained on all the datasets for evaluation?

There was no specific reason here other than us not wanting to run too many experiments. We randomly assigned one prediction model (tree, MLP etc. ) to each dataset. We could have done what you said as well. Not sure if we could fit 12 sets of result (as opposed to the current 4) in the main body of the paper though and most would go to the appendix

Thank you for providing clarifications and answers to the raised questions. After going through the authors' answers, I remain concerned that the empirical investigation is very limited and does not provide sufficient evidence for the claims on the performance of FourierSHAP. For example, in response to Weakness #1 (that FourierSHAP is limited to binary features or categorical data), the authors proposed potential ways to generalize the approach to continuous features. However, such "ways" should be evaluated first and listed in the experiments to be considered as possible solutions. Additionally, the authors clarified that FourierSHAP is model-agnostic and can be applied to any black-box model, but this was not obvious in the paper. For instance, I could not find experiments involving black-box models other than tree-based models and feedforward neural networks, which raises more questions on the quality and time complexity of FourierSHAP on models beyond tree-based models and feedforward neural networks. I tend to think the paper should be rejected until it provides a more extensive empirical investigation.

Thank your for taking the time to read our response. We are disappointed that our rebuttal has caused more confusion. Please allow us to make another attempt at addressing your concerns to hopefully clear up any points that we mis-communicated. You have raised a lot of points so let us dissect your response into different parts. There is quite a lot to unpack here so let's go step by step.

For example, in response to Weakness #1 (that FourierSHAP is limited to binary features or categorical data), the authors proposed potential ways to generalize the approach to continuous features. However, such "ways" should be evaluated first and listed in the experiments to be considered as possible solutions

First of all, let us discuss "ways". Regarding "ways", we believe you are referring to our response to reviewer "g97w", who has by the way raised their score after reading the response. As you and the other reviewer have kindly pointed out, our algorithm does not natively support continuous features. However we have made no such claims anywhere in the paper that we are addressing the continuous case and we, do not want to deny that the work at its current state has this limitation. At the proposal of reviewer "g97w" and "trxy" we have now added a limitations sections emphasizing the fact that we do not support continuous features (Appendix G). Nevertheless, as you and reviewer g79w were quite rightfully concerned about extension paper to continuous we have written a potential future direction in response to this reviewer. And given the positive response of reviewer "g97w" we have now added this as a future direction section in Appendix G as well. That being said, if you read our response there, these potential future directions require extensive justification involving theoretical and empirical on the spectral biases of neural network with continuous inputs that would pave the way for us to also extend this algorithm. This would be the subject of not just one but a few research papers and is not trivial, but as we have mentioned, as potential future work, it is not too far-fetched either.

Now the remaining concern here is that without handling continuous features, is the contribution of our paper worthy. And we will address this after discussing two of you other concerns first.

Additionally, the authors clarified that FourierSHAP is model-agnostic and can be applied to any black-box model, but this was not obvious in the paper

We politely disagree here. There are 2 sub-cases: A- If you are saying that we have not been clear in the presentation of the paper that we are claiming to present a model-agnostic (a.k.a black box) algorithm. These claims appear as early as line 3 in the abstract: Quote: "We cover both the model-agnostic (black-box) setting, where one only has query access to the model.. " Other places include but are not limited to lines 72, 93, 94, or the whole experiment section titled black-box staring on line 421.

B- If you are saying that it is not obvious that our algorithm is a black-box method we also politely disagree. Let us explain more clearly: The only requirement for applying FourierSHAP is query access to the model i.e. that you can give an input x and see the value of the predictor f(x). The fact that FourierShap is a black-box does not even require us to present experiments. You can see that by understanding the algorithm itself. The first stage of our algorithm, which is extracting a Fourier transform only assumes query access (as clarified numerous times see for example line 72). So unless the reviewer somehow thinks we cheated in our experiments and did something that we did not claim to do in the paper, there should be no doubt we are only querying the black box. If accepted the code release would also help alleviate the reviewers concerns.

Going on to the next concern:

For instance, I could not find experiments involving black-box models other than tree-based models and feed forward neural networks, which raises more questions on the quality and time complexity of FourierSHAP on models beyond tree-based models and feed forward neural networks

After reading this sentence and connecting it with the last quote, we think that the reviewer, when saying our algorithm is not model-agnostic, means that it can not be applied to black boxes other than trees and neural networks. We would like to politely disagree here too. In order to get our point across we need some background. First of all let us consider the most widely used and well-known model-agnostic algorithm kernel shap with over 10000 citations. At the heart of of this model-agnostic method, there is an approximation and this approximation can come with guarantees. In the case of kernel shap this appears as asymptotic statistical guarantees. Basically for a large enough number of sampled subsets kernel shap recovers the ground truth shap values (by ground truth shap values we mean ones that can be computed by the exponential summation equation 4.1). In the worst case scenario though, when we have $n$ features, one has to sample all possible $2^n$ subsets. It is the same for our case: one can get better and better approximations of the black box by increasing the sparsity parameter. In the worst case one can get a perfect approximation using $2^n$ queries to the black box i.e. computing the whole Fourier spectrum.

But there is hope. The authors of kernel shap, proved that for simple models such as linear predictors in the form of $f(x_1, \dots, x_n)=a_1 x_1+ \dots + a_n x_n$, kernel shap exactly recovers ground truth shap values without taking exponentially many samples $n$. Please see section 4.2 of [1] for a list of specific models kernel shap is guaranteed to produce ground truth values for. This might sounds like a very weak guarantee, but please note without regularity constraints on the prediction function $f$ one can not hope to overcome the exponential summation of Equation 4.1.

Now what we have done for our model-agnostic algorithm is shown that for a class of significantly more complex predictor models than linear models, namely trees and MLPs our algorithm is able to compute the ground-truth shap values (exponential summation Eq4.1) precisely. This is possible due to the fact that both these predictors show regularity and structure when you take their Fourier transform, namely they are sparse. We have shown how to exploit this regularity to overcome the exponential summation of shap value computation. We would like the reviewer to contemplate the fact that this is the main contribution of our work. Even though it only applies to discrete features, and has not yet been extended to continuous features, it provides a big leap in the realm of model-agnostic algorithms. Note that trees capture linear predictors as a very special case (Any linear predictor over $n$ variables is a summation of $n$, depth=1 trees)

Now lets go to our experiments. Since our algorithm is more suited to discrete data, we have chosen datasets that only contain categorical features. We have trained neural networks and trees on these datasets. If the reviewer has an ML predictor model that they think works well on these datasets we are happy to oblige, but we think that for these types of datasets trees and MLPs are probably the two most widely used models.

Our choice of experiments are also justified because they show that our claims about guarantees to produce ground truth SHAP values are true.

Thanks for the response. We are happy that you find our work novel and beneficial for the XAI community. We are happy to have addressed most of the concerns you have raised during the rebuttal phase. We can see that your only main remaining concern is that we have not evaluated our model on enough datasets. The datasets that you mentioned in the gaming area are definitely interesting ones for the application of FourierSHAP. We did not intentionally prioritize experiments/datasets of one area over another.

Before getting into datasets, we would like to emphasize the fact that we have presented a completely new and novel way of computing SHAP values that did not exist before. Therefore a lot of the writing of the paper has gone to presenting the soundness of this method and justifying why it makes sense with guarantees. And significant work in the experiments is in lines with those explanations and just solidifying that this new algorithm is doing what it claims to be doing. The fact that no reviewer is questioning whether the algorithm is correct shows that the experiment section is doing its job well in our humble opinion. We were only asked by reviewers to run an experiment to show we are recovering ground truth SHAP values, which we happily provided for them. That being said, not only have we successfully shown that the new algorithm is sound and correct we have showcased its performance on 4 different datasets, with order of magnitude improvements in runtime compared to other methods.

We very much appreciate, agree, and sympathize with the reviewer's concern for empirical evaluation. We think the number of datasets we have provided is reasonable though, when compared to other SHAP methods presented in top ML conferences. In order to alleviate the reviewers concern that this is a standard number of datasets to experiment on and that this is in line with other similar works proposing a SHAP value computation methods, we have conducted a list of other papers that are similar to ours and published in top ML conferences.

We hope we are able to portray to the reviewer that the current set of experiments is justified. We would like to ask the reviewer to again consider the work as a complete package of a proposed, theoretically-backed method with clarified domains of application and guarantees that is backed up by a set of experiments that convey the proposed method in a concise but sound manner.

References

[1] RKHS-SHAP: https://openreview.net/pdf?id=gnc2VJHXmsG

[2] GP-SHAP: https://openreview.net/forum?id=LAGxc2ybuH

[3] Linear TreeSHAP: https://openreview.net/forum?id=OzbkiUo24g

[4] Interventional TreeSHAP: https://ojs.aaai.org/index.php/AAAI/article/view/26322

[5] TreeSHAP: https://www.nature.com/articles/s42256-019-0138-9

[6] A Unified Approach to Interpreting Model Predictions: https://papers.nips.cc/paper_files/paper/2017/hash/8a20a8621978632d76c43dfd28b67767-Abstract.html

[7] FastSHAP: https://openreview.net/forum?id=Zq2G_VTV53T

[8] Linear Regression SHAP: https://proceedings.mlr.press/v130/covert21a.html

We would first like to thank you for your comprehensive, thoughtful and detailed feedback on the work. Below, we provide our detailed responses to your comments.

Restrictive Application Settings: First, FourierSHAP can only applied when input spaces are binary. This means numerical features cannot be represented. This is a big limitation of the method, which obvious competitors like [1-4] do not have, which reduces the applicability of FourierSHAP in settings with numerical data. I am sure workarounds and fixes exist (binning and binarization), however this is left unexplored by the paper.

We have addressed the binary assumption concern quite extensively in our answer to reviewer g97w. We ask you to kindly read this section and tell us what you think.

Regarding competitors [1-4]; thank you for shedding light on these very interesting methods, which we will now discuss.

Please correct us if we are wrong, but after going through [1] it seems this is a method that only applies to predictor models within the RKHS paradigm as Kernel regression, Kernel classification etc. The models we have tested in our paper namely trees and neural networks do not fall under this category. [1] paper has no such experiments on these class of functions either and have a few experiments on synthetic data. We understand you are asking us to fit a an RKHS model to a MLP or a tree and then run these methods and compare to ours. Even though that sounds like an interesting thing to do, it lacks the thorough theoretical and empirical foundations we have presented for the case of Fourier representations. There are a few open questions here: 1- What kernel do we use for the case of trees and MLPS 2-Why is that kernel a useful function approximation for these classes of models

While, we have provably and empirically shown that Fourier transform capture a compact representation for trees. And we have built upon previous thorough and justified empirical and theoretical results of why using Fourier transforms for MLPs make sense.

The same reasoning applies for [2] which computes SHAP values efficiently when the predictor model is a (potentially multi-output) GP. Again trees and MLPs do not fall under this category. The paper has no experiments whatsoever trying to approximate MLPs or trees with GPs. And again the difference of our presentation with this paper is that we have justified the use of a Fourier representation for trees and MLPs thoroughly using our own derivations and also citing empirical and theoretical evidence from others on why this actually makes sense.

[3] does not compute interventional SHAP values, but rather conditional SHAP values. In our paper we have not presented an algorithm for conditional SHAP values for trees and as mentioned explicitly in section 2.1 exclusively focused on the interventional setting.

[4] however is a compelling relevant work that computes interventional SHAP values for piecewise linear regression trees. As normal decision trees are instances of piecewise linear regression trees, this work is an appropriate method to compare ours with. The paper also provides two new algorithms for computing interventional SHAP values for trees and show significant speedups over classic interventional TreeSHAP [*1]. We regret missing this work and are grateful to you for highlighting it. We took the time to include it into our baselines for the tree setting experiments and rerun all the experiments. We updated our Figure 3 in the paper and it now includes the fastest version of PLTreeSHAP introduced in [1].

[5] we have included this as as baseline already (TreeShap) and we have orders of magnitude speedup over this method

It was great going through these works, and adding the only direct competitor as a baseline into our tree setting experiments. We will definitely include all [1-4] in our related work. Again, thanks for mentioning them in your review.

Second, FourierSHAP seems to work only with very shallow neural networks (i.e. 3 layers with 300 neurons), which definitely is not realistic given modern architecture sizes.

While we understand modern CNNs and Transformer architectures can be tens of layers, here in this paper we have only made claims about MLPs. Please again correct us if we are wrong, but practically speaking MLPs, rarely go beyond more than say 4,5 layers. Furthermore, our work relies on results from Spectral biases of such networks which still hold even as MLPs get deeper. The work of Yang and Salman shows the effects empirically and theoretically up to MLPs of 10 layers.

Usually, for XAI use cases testing with smaller networks is ok for model-agnostic methods, as the focus lies in showing that such methods can work with all sorts of models. However, given that FourierSHAP relies on finding a sparse Fourier representation of the underlying model, the aforementioned argument is invalid.

We are not sure we understand why you are classifying Fourier SHAP as not being model agnostic. The only assumption that needs to be made in order to extract a Sparse Fourier approximation is query access to the model and nothing more. And given the Fourier representation we can compute SHAP values.

The reason we have introduced trees and MLPs, is that these two classes of functions indeed have sparse Fourier approximations. This substantiates that fact that the class of Fourier sparse functions indeed can be quite expressive as it capture two widely used classes of predictor models as a subset. Please note again our method will apply to any black box method since it only assumes query access and no access to the structure of the MLP or the tree. Indeed for the MLP we only do queries to the MLP and using no other information whatsoever about its weight or its structure. Even though for the case of trees we have used the tree structure to extract the spare Fourier trasnsform we could have very well treated it like a black box and used the Fourier methodology to extract its representation. It would have taken longer but this would still work, and we did this in our black box experiments on two of our datasets, GB1 and avGFP.

We think that inherent in any model agnostic method is some regularity assumption about the black box in order to show that the method works. For example LIME assumes the model is well approximated but a locally linear function. We think we have done an extensive work to show why Fourier SHAP is a very useful approximation method for model agnostic settings.

This Fourier representation will most definitely be drastically different from smaller sized networks. This needs to be theoretically or at least empirically explored. Otherwise, I am doubtful the results generalize to large scale networks

The spectral bias theorem results still hold for deeper MLPs. This is proven by Yang and Salman and also shown empirically for networks of up to depth 10. I think the main intuition here is that the network learns a low degree function no matter the depth.

Lastly, computing ground-truth SVs with an approximation based method like KernelSHAP is an okay proxy, but in smaller feature settings like the Entacmea (13 features) dataset used in this paper or potentially synthetic settings, real ground truth values can be obtained through brute force or clever tricks with knowledge about the underlying data generating process / black box function.

Regarding your concern about using KernelSHAP as ground truth; in our answer to reviewer g97w's Q3, we discussed this extensively, mentioning our toy tests with multiple predefined Fourier functions to make sure our formula for computing SHAP values off a sparse Fourier function works.

In any case, as a proof of concept to help readers grasp the idea easier, we would be happy to compute SHAP values using the original SHAP formula and contrast it to KernelSHAP and ours, for Entacmaea.

Presentation can be Refined: The papers could be presented better. The work is more verbose than it needs to be. This starts in the abstract which is overly detailed and too long. The paper looses itself in discussing aspects that are in my opinion secondary and can be postponed to the appendix, like the parallelization and GPU acceleration. The paper contains multiple typos.

Judging the breadth and depth of your knowledge showcased by your comments, we think that you are probably a more seasoned and experienced researcher in this field. The other 4 reviewers have all given a score of 3 for presentation and three of them have mentioned the presentation to be a strength. They seem to like the presentation and seem to appreciate the slower pace and verboseness of the topic. We think that it might be safer to keep it this way to make sure the work is accessible to a wider audience.

Missing Limitations Section: The paper does not contain a limitation section discussing FourierSHAP's drawbacks and avenues for interesting future work.

We agree with you that a dedicated limitations and future works section will solidify the manuscript. We already discussed some of our ideas for extending this work in our response to reviewer g97w. We make sure to add this section to the paper if we get accepted.

The point being made here is that just because the model agnostic method comes with guarantees for a certain class of prediction models (like linear models in kernel-shap) does not imply it can not be used for other classes. Kernel-Shap is still a model agnostic method because it only assumes query access to the black box. Going back to FourierShap, the fact that we have provided some form of guarantees for MLPs and trees does not make the method model-based. We have presented a model-agnostic, query access, black box method that is guaranteed to produce ground truth shap values for two classes of widely used models namely MLPs and trees. In our opinion, our contribution is important since for the case of MLPs, it is something that to our knowledge, no model-agnostic method has been able to do before. More precisely, Except for FourierSHAP, there is no SHAP computation method that assumes only query access to the model i.e. is model agnostic, and is guaranteed to compute ground truth SHAP values for MLPs.

Just to drive the point home, we think the application of Fourier-Shap is just as justified as is kernelShap to the NLP datasets of [3] if not more, since it is guaranteed to work on a much more complicated class of prediction models than KernelSHAP has guarantees for. We will try but not promise to run FourierSHAP on a language dataset before the end of the rebuttal period. Please note, since FourierShap comes with guarantees for MLPs and trees we have focused a lot of effort in the paper portraying these guarantees to hold and we have focused the experiments on showing results in these classes of prediction models and chosen datasets that are relevant to these models.

[1]: Lundberg, Scott M., and Su-In Lee. "A Unified Approach to Interpreting Model Predictions."

Question 2: As mentioned before in Section 2.1 lines 137-144 we have clearly stated we only cover the interventional setting. Quoting those lines:

..., in this work, we focus on the SHAP values as defined in \textsc{KernelShap} introduced by [..] also known as Interventional [..] or Baseline [..] SHAP, where the missing features are integrated out from the marginal distribution $p(x_{[n] \setminus S})$, as opposed to the conditional distribution $p(x_{[n] \setminus S} | x_S)$.

The reason why it only covers this is because we do not have a way to tractably approximate the conditional distribution of a dataset. Capturing conditional distribution of a dataset is in general tricky and is even harder when one only has query access to the black box.

In model-based methods like tree-shap, life is easier, as one can use the tree itself to approximate conditional distributions. We don't know if our method can cover this precise setting where the conditional is assumed to arise from the tree as we have not thought about it. If the paper is accepted we will add this as a potential future work.

Q3: We are glad you were convinced by our explanations here. As mentioned before, if the paper is accepted we will make sure to mention all of papers [1]-[4] and explain why they differ with our setting in the other work section of the paper in the appendix. [4] was the only directly comparable paper and we have added it as a baseline as you suggested.

Q4: Thank you for taking the time to read. As mentioned before, if accepted we will add a future work/limitation section including all the points mentioned there and the potential extension for the conditional tree setting (that we promised here in question 2).

We thank you again for taking the time to review this work and adding your valuable comments.

Thanks for your response. While we appreciate the reviewer's intent to expand our work to other sub-fields of Machine Learning such as Reinforcement learning and NLP, we think this is not adding to the presentation of the paper. In the previous response we have clarified how the current algorithm can be applied to query access black-box models of any sort including those that the reviewer wants.

We believe the scope of the paper is quite clear and we do not plan to expand it any further. We believe the paper has a substantial amount of non-trivial material theoretically and empirically linking spectral biases of MLPs and trees to the task of computing SHAP values. Adding further fields of importance serves to distract the reader from the content that is meant to be presented.

In short, we have presented a new and novel algorithm for computing amortized SHAP values for the setting of Tabular/Discrete data. Our algorithm is mathematically and empirically justified and is guaranteed to work for trees and MLPs in the query a.k.a black-box setting. We believe, the paper already has areas where it shines as showcased by our experiments where we have provided order of magnitude speedups on a variety of datasets and settings.

We do not think it is required for us to include experiments from RL and LLMs as part of our work to introduce FourierSHAP. As a matter of fact, none of the similar methods proposed by the reviewer, go beyond classic tasks and datasets to introduce their methods and shining points. They definitely did not provide any such experiments on language data, LLMs or Reinforcement learning.

Since the reviewer thinks our work, with empirical studies on 4 datasets, lacks sufficient empirical evaluation to be published and should be clearly rejected, we have conducted a list of the baseline methods the reviewer suggested in his initial review and their empirical scope. These are all from top ML conferences as the reviewer has required. In addition to the reviewers suggested baselines, we have also included a few other well known methods in the XAI community that we have used as baselines. The following table shows what datasets were included in these works.

We hope this shows the paper is on par with other published work at top ML conferences in terms of empirical evaluation.

References

[1] RKHS-SHAP: https://openreview.net/pdf?id=gnc2VJHXmsG

[2] GP-SHAP: https://openreview.net/forum?id=LAGxc2ybuH

[3] Linear TreeSHAP: https://openreview.net/forum?id=OzbkiUo24g

[4] Interventional TreeSHAP: https://ojs.aaai.org/index.php/AAAI/article/view/26322

[5] TreeSHAP: https://www.nature.com/articles/s42256-019-0138-9

[6] A Unified Approach to Interpreting Model Predictions: https://papers.nips.cc/paper_files/paper/2017/hash/8a20a8621978632d76c43dfd28b67767-Abstract.html

[7] FastSHAP: https://openreview.net/forum?id=Zq2G_VTV53T

[8] Linear Regression SHAP: https://proceedings.mlr.press/v130/covert21a.html

We thank you for your thoughtful review and are delighted to hear that you found the script easy to follow and the literature review sufficient and helpful. We apologize for publishing of response to your review later than the others. Hope we can still make sure we could cover your points.

It is not clear how the SHAP estimate degrades with the approximation error in sparse Fourier approximation.

General picture: This is a hard question to answer. The Fourier approximation error is global measure of how accurate the approximation is. Whereas for any query to be explained we are doing more local perturbations around that certain instance to be explained. Perhaps one can try to derive a bound by averaging all $2^n$ possible input instances to be explained and assuming a uniformly random background dataset. But we think a bound like that would not be of practical use as in practice one use background data-points and query points from the data distribution. So generally speaking without making very heavy assumptions about the data distribution (namely uniform) we do not see how one can practically derive a bound here.

The initial step for Fourier approximation can be computationally expensive.

Yes, but as we have pointed out ourselves as well on lines 396-401 the sparse Fourier approximation is performed just once per model, and allows extremely cheap computation of SHAP values for any query inputs in an amortized fashion. We developed a JAX-based implementation of [1] that enables fast GPU-accelerated sparse Fourier approximation. As also mentioned in the Appendix F.1, using our implementation, we achieved high Fourier approximation accuracies in less than few minutes in all of our black-box experiments (Figure 1).

On the other hand, training FastSHAP on multiple background datasets to run our experiments took up to multiple hours for some of our larger datasets. To give an example, it took us more than 8 hours to train FastSHAP on four background datasets to run our GB1 black-box experiments. This is while the approximated Fourier spectrum we achieved in 3 minutes already resulted in higher accuracies of SHAP values generated. Our method also does not need any such re-training with the change in the background dataset. This is orders of magnitude speedup in the first "pre-computation" step by comparison. We will include the extensive list of training times of all different versions of FastSHAP we trained for our experiments in Appendix F.1.3. This will highlight how cheaper overall our method is compared to similar methods that enable cheap amortized SHAP values computation.

Furthermore, as it can also be seen in our Figure 1, sparse Fourier approximation is guaranteed to result in more and more accurate representations of the black-box function with the time spent. That is not necessarily the case when training a larger model for FastSHAP (this can be seen in our Figure 2). One can also take into account all the hyperparameter tuning and architecture engineering required to properly train a FastSHAP model (as can be seen in Appendix F.1.3), which is not needed in approximating sparse Fourier spectrum of a predictor.

Past work has shown several optimizations are possible for Kernel SHAP making it faster. Are they applicable to your approach?

The optimizations in KenrelSHAP are mostly regarding smart ways of sampling coalition subsets. These results can not directly be used here as our method is inherently different. We believe the most promising optimizations for our method would likely lie in the initial sparse Fourier approximation step or in the parallel implementation of the second step.

[1] Efficiently Learning Fourier Sparse Set Functions: https://papers.nips.cc/paper/9648-efficiently-learning-fourier-sparse-set-functions