On Formal Feature Attribution and Its Approximation

The work can potentially be improved from either the theoretical side or the experimental side.

From theory direction: It is not clear about the time complexity of the approximating formal feature attribution and the approximation error compared to the actual FFA.

From the experimental direction: The authors highlighted the advantages of FFA compared to existing algorithms. However, the evidence showing this is the case in this work is limited.

1. The authors mentioned the "unsoundness of explanations" exists in prior work. It would be great to specify what type of unsoundness the authors specifically refer to, and explain why the FFA can increase such "soundness". The same justification is needed for the "out-of-distribution sampling" performance compared to existing works
2. All the experiments on the comparison between FFA and other SOTA XAI algorithms are based on real-life examples. It is hard to evaluate, if two methods disagree with each other, which one is better. Why don't the authors start with clean synthetic data, where the ground truth is known, and show where FFA generates better results than other XAI algorithms? And further show that the proposed approximation FFA algorithm did a better job than other XAI algorithms.

1. While the authors propose a new approach to feature attribution based on formal explanation enumeration, it is not entirely clear how this approach differs from existing methods. The authors briefly mention that their approach is based on the proportion of abductive explanations in which a feature occurs to weigh its importance, but it is not clear how this differs from existing methods such as LIME and SHAP.

2. The authors focus primarily on the theoretical aspects of their approach and do not provide sufficient empirical evaluation. While the authors show that their approach can be used to compute feature attribution exactly for many classification problems, they do not provide sufficient empirical evaluation to demonstrate the practical usefulness of their approach.

3. The authors do not provide sufficient details on the approximations used when exact computation is not possible. While the authors mention that effective approximations can be used, they do not provide sufficient details on the specific approximations used and their accuracy.

• Lack of related work. As there is no dedicated related work section, the relation to prior work can be strengthened. As this paper is dealing with feature attributions, there is a multitude of related approaches that could potentially be mentioned [1, 2, 3, 4]. There should be much more space invested to motivate why FFA are relevant and what practival problems they could potentially solve.
• The propositions don’t have proofs. I cannot follow the argumentation leading up to Proposition 1 and 2. While they may be intuitive to experts, I think the exposition is insufficient for the average reader to follow. I agree that conference papers have limited space, but the proofs certainly need to be amenable to verification also by non-experts. I don’t think is insufficient to make imprecise statements like “this is a direct consequence of a result in Huang et al.”. The exact result should be named, and restated in the appendix together with an explanation for how the proposition can be derived from it. This also helps the reader to assess the novelty of this claims.
• Scope: The scope of the method is limited to Boosted-Trees. While I agree that this is a relevant model for tabular data, it is not the only one. This may limit the paper’s potential impact.
• The evaluation metrics use FFA’s as a ground truth (Table 2) and seem to hypothesize that LIME and SHAP should be approximating FFAs. The disagreement is obvious as SHAP and lime are meant to serve different purposes and are derived from different desiderata
• Some claims are exaggerated. For instance, “In this paper we define the first formal approach to feature attribution” (Conclusion) is too strong and incorrect in its current form. Other attribution methods such as Shapley Values or IG [2] also have formal grounding, and can therefore also be considered formal approaches to feature attribution. I think such overly strong statements should be avoided.

Minor: Clarity of the write-up: Unfortunately, there are many writing/grammar issues in the paper, particularly in the introduction. I encourage the authors to check the writeup again. For instance, already the first sentence of the introduction seems a bit puzzling, as it does not mention what is growing and appears to be overcomplicated. What is meant by “We argue that formal feature attribution is hard for the second level of the polynomial hierarchy.” (Section 1)? Usually, a comma is employed after “e.g.” and “i.e.”.

Summary

A work on formal explainability that proposes a novel feature attribution method grounded in formal explanations (FFA). The algorithm to compute FFAs seems interesting and shows that these attributions can be computed for problems up to MNIST size. Unfortunately, there are many competing notions of attribution, the technical novelty seems limited, and the motivation for this approach is not extensive. Furthermore, following the draft is complicated by some missing explanations for the propositions and minor writing issues. While I don’t think the work has substantial flaws, I still lean towards reject as of now.

References

[1] Lapuschkin, S., Binder, A., Montavon, G., Klauschen, F., Müller, K.-R., and Samek, W. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 10(7):e0130140, 2015.

[2] Sundararajan, M., Taly, A., and Yan, Q. Axiomatic attribution for deep networks. In International Conference on Machine Learning, pp. 3319–3328. PMLR, 2017.

[3] Kasneci, G. and Gottron, T. Licon: A linear weighting scheme for the contribution of input variables in deep artificial neural networks. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pp. 45–54, 2016.

[4] Petsiuk, V., Das, A., and Saenko, K. Rise: Randomized input sampling for explanation of black-box models. In Proceedings of the British Machine Vision Conference (BMVC), 2018.

Significance -- Weak:

• The main drawback of the method is that it depends on the ability to compute Axp's. Although the paper does propose an approximation (algorithm 1) it is still can be quite expensive in practice.

• Most current AI methods use deep neural networks, all experiments done in the paper used boosted tree this is because FFA requires the ML to have some first-order logic, which is not practical so the use of the proposed method in practice will be very limited.

• The results and time comparison between exact FFA, approximate FFA and baselines is done on datasets with very small input space and binary classification problem. These results will probably not generalize for larger input space for example, if LIME takes < 1 second for 10x10 images scaling for larger images like 256×256 lime will still be pretty quick if but FFA_10 will probably not give any useful results.