SHAP-IQ: Unified Approximation of any-order Shapley Interactions

Summary

This paper provided an unified perspective to several existing Shapley-based interaction attribution methods as Cardinal Interaction Index (CII), in addition provide a more efficient sampling based approximation method. Connection between their formulation with unbiased KernelSHAP is established and they showed that their formulation can also improve the standard SHAP algorithm.

Strengths

The unified formulation of several interaction attribution methods as CII is novel to the best of my knowledge in the X-AI literature. The authors made their claims and novelty very clear as well.

Weaknesses

I think the content of the paper is very well written so not much weakness to comment. One thing that tricked me a bit is in line 33-34 when first mentioned CII it would be nice to have a citation to show that this is not your original contribution. Also in line 129 the \mathcal{S}_{s_0} notation is not defined properly so that stopped my flow a bit too.

Questions

Not really from my side.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Not really from my side. Potential improvements are stated in the weakness section.

Summary

This paper presents a unified approximation technique for Shapley interaction indices. It reformulates the general form of various Shapley interaction methods (Shapley interaction index, Shapley-Taylor, Faith-Shap) from a sum involving the set in question to a sum not involving the set, but instead a computation involving the method weights. This allows one call of the function to be a Monte Carlo integration sample of every set of inputs the method is calculating a value for. Theoretical guarantees of unbiasedness and efficiency are provided, as well as probabilistic error bounds.

Strengths

Clear writing, very easy to follow and presented plainly. Interesting and practical results which apply to multiple methods. improvements over baseline is apparent in experiments. The results are general enough that they are likely to apply to future methods.

Weaknesses

Faith-Shap not fully addressed. But this seems to be in part to the inherent differences of that method.

Questions

-Could you clarify, is this method an application of a technique used to approximate Shaley Values, but applied to interaction indices? If so, would you point out where this is is stated. If not, could you elaborate on the novel contributions? Minor issues: (153) Please define $\mathcal{G}_D$. (130-132)_ Please clarify, this secion is dificult to follow. (174) - the commas and grammar are off in this sentence.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Application to Faith-Shap as mentioned above. The method applies to to a type of interaction form that is fairly general.

Summary

This paper presents a novel method, SHAPley Interaction Quantification (SHAP-IQ), for efficiently computing Shapley interaction indices in the context of explainable artificial intelligence (XAI). Shapley interaction indices extend the concept of Shapley values, a method from cooperative game theory, to measure the contribution of interactions between features in a model. The authors propose SHAP-IQ as a unified sampling-based approximation method that can be applied to any Cardinal Interaction Index (CII). They provide theoretical guarantees for SHAP-IQ, showing that it is unbiased and consistent, and provide a general approximation bound. They also discuss the computational complexity of SHAP-IQ and how it compares to other methods. The paper also presents a new representation for the Shapley value (SV) and shows that in the special case of single feature subsets, SHAP-IQ provides novel insights into the SV and greatly simplifies the calculation of Unbiased KernelSHAP (U-KSH). The authors conducted multiple experiments to illustrate the approximation quality of SHAP-IQ compared to current baseline approaches. They compare the baseline methods with SHAP-IQ using different evaluation metrics. The paper concludes with an appendix that provides further theoretical and experimental results for SHAP-IQ, including additional results for specific CIIs such as SII, n-SII, STI, and FSI. The appendix also includes all proofs of theoretical results from the main paper, further insights into the implementation of SHAP-IQ, and additional experimental results. In summary, this paper presents a novel method for computing Shapley interactions, provides theoretical guarantees for this method, and demonstrates its effectiveness through a series of experiments.

Strengths

**Originality**: The authors propose a novel method, SHAPley Interaction Quantification (SHAP-IQ), for computing Shapley interactions for arbitrary cardinal interaction indices (CII). This is a unique contribution to the field of explainable artificial intelligence (XAI), particularly in the context of black box models. The paper not only presents the new method but also includes a detailed comparison with existing methods, an exploration of its theoretical properties, and a demonstration of its practical application. This comprehensive approach strengthens the authors' claims about the effectiveness of SHAP-IQ. **Quality**: The paper provides a rigorous theoretical foundation for SHAP-IQ, including proofs of its properties such as being unbiased and consistent. The authors also provide a general approximation bound for SHAP-IQ. **Clarity**: The paper is well-structured and clearly written. The authors provide a clear explanation of their method and its theoretical underpinnings, making it accessible to readers with a background in the field. The appendix provides additional theoretical and experimental results, further supporting the claims made in the main paper. It also includes all proofs of theoretical results, providing transparency and allowing readers to fully understand the theoretical foundation of SHAP-IQ. **Significance**: The authors demonstrate the practical application of SHAP-IQ through a series of experiments. They show that it can be applied to different machine learning models and datasets, and that it outperforms existing methods in terms of approximation quality and computational efficiency. This suggests that SHAP-IQ could have a significant impact on the practice of XAI.

Weaknesses

This paper has no obvious weakness. The main concern from me is the reproducibility of the experiments, which seems like requiring too many computational resources.

Questions

Could the authors discuss some future works about the SHAP-IQ?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes, the authors have discussed limitations well.

Summary

The paper proposes a new sampling-based approximation method called Shapley interaction quantification(SHAP-IQ) for the cardinal interaction index(CII), which is a generalization of the Shapley interaction index. To this end, the authors give a novel representation, and showed that SHAP-IQ is an unbiased and provide a general approximation bound for the quality and variances of the point estimates. Finally, they demonstrated that SHAP-IQ provides the effectiveness and nice explanations for language model and image classification models.

Strengths

- Provide a unified approach for CII, which is a generalization of unbiased KernelSHAP, and so on. - SHAP-IQ is an unbiased and its quality and variance are guaranteed to bound theoretically. - SHAP-IQ empirically provides lowest mean square error compared with other baseline algorithms.

Weaknesses

- The results are solid, but they are not particularly surprising. The contributions are somewhat limited to achieve an unbiased method and theoretically bounding the accuracy. - Shapley interaction index implies that the number of features to be observed exponentially increases, which in turn may make interpretation more difficult. In some cases, multiple sets of features may have similar importance scores. In such situations, selecting specific sets of features may not be done in a naive way. It would be better to provide a measure to choose them or an approach to reduce the number of feature subsets to be observed.

Questions

- In Figure 2, how are the top-k interactions determined? Are they based on the largest absolute value or some other criterion? - How should the illustration on the left of Figure 3 be understood? Each word is assigned both positive and negative values. What does this mean?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Yes. Below are the comments for improvements. - SOUM is known as the induced subgraph game[1]. The interaction subsets correspond to hyperedges of a graph G and a is its weight. The value of a subset T is given by the summation of edge weights of a subgraph induced by T. - In Definition 4.2, K -> k_0? or K seems not be defined. [1] Deng, Xiaotie, and Christos H. Papadimitriou. 1994. “On the Complexity of Cooperative Solution Concepts.” Mathematics of Operations Research 19 (2): 257–66.

Summary

**Context.** This paper aims at quantifying the contribution of a set of features to the prediction of a machine learning model by leveraging the Shapley value (SV), a principled tool coming from cooperative game theory. Previous works either focused on (i) estimating the contribution of a single feature (via feature importance scores) or on (i) estimating the contribution of a group of features (via feature interaction scores) through different extensions of the SV to features interaction (e.g. SII, STI or FSI). As of today, no unified framework or methodology to compute feature interaction scores has been proposed. This paper tries to fill this gap. **Contributions.** The authors made the following set of contributions. * They propose a novel perspective and representation of the cardinal interaction index, agnostic to the size of the features' group to be valued. This representation leads to the SHAP-IQ function unifying previously proposed feature interaction scores. * They propose a theoretical analysis of SHAP-IQ with both statistic properties (bias, consistency) and non-asymptotic theoretical guarantees in the form of high-probability deviation bounds. * They illustrate the benefits of their approach on several experiments.

Strengths

* The paper and contributions are timely and of interest for the ML community. * The paper is clear and well-written. * I did not fully check in details the Appendix but the first derivations (first 5 pages) in the Appendix are correct and well detailed. * The related work part spanning both the Introduction and Section 3 is clear and relevant. I appreciated the links made between SHAP-IQ and previous works. * SHAP-IQ (based on Monte Carlo integration) allows to re-use the same sample for all groups of features. * Experiments are convincing and well-chosen.

Weaknesses

* Theorem 4.3 is quite classical since SHAP-IQ stands for a Monte Carlo approximation and proofs techniques to obtain high-probability deviation bounds via Chebyshev inequalities have been commonly used in works on Shapley value. Could the authors go beyond this simple theoretical analysis and provide more insights on the impact of key quantities of the problem (e.g. $\nu_0$ and $S$)? * Full computational complexity and benchmark with competitors: The computational complexity of SHAP-IQ depends on several things: number of Monte Carlo draws, finding the right sampling order $k_0$, pre-computing of the weights $\gamma_s^m$,... Could the authors clarify the full cost and compare it to previous approaches competing with SHAP-IQ?

Questions

See previous section.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes, done at the end of the paper.

Response to Authors

I am thankful to the authors' response about the future works and I will keep my original score. I suggest authors add these to the camera-ready version if this paper can be accepted.

Response to Author

We have read the rebuttal and thank the author for the response. We will not change our score.

Thanks for your answer

I thank the authors for their response and the additional figure provided in the attached .pdf file. I suggest the authors to add these responses in a relevant paragraph in the manuscript to enhance clarity if the latter is accepted. I will keep my score unchanged though since the theoretical analysis is quite classical.