Summary
This paper explores the interplay between two properties of removal based explanations: efficiency and consistency. It established that these two properties cannot coexist when the set of predictive models (requiring explanation), and the set of interpreting models (doing the explaining) are disjoint. It proposes a new property: “truthfulness”, which is a relaxation of efficiency, and measures the information-capture within a functional sub-space (a chosen subset of the interpretable models). It proposes several algorithms for learning truthful interpreting models, grounded in methods from Boolean functional analysis, which allow for different trade-offs between consistency and efficiency. It compares these algorithms to existing methods by looking at the interpretation error on a few practical NLP and Vision tasks.
Strengths
The authors demonstrate a solid understanding of existing removal-based (and other) explainability methods. The paper surveys a large number of these related works.
The paper explains a tension in post-hoc explanations: efficiency vs. consistency in a concise and easy to understand way.
The front half of the paper (sections 1 to 4.1), where most of the concepts are presented, is clearly written and easy to understand.
The paper draws insightful connections between producing interpreting models and work in Boolean functional analysis.
Between the theoretical discussion, the methods introduced, and the subsequent experiments, the paper makes numerous useful contributions.
Weaknesses
The paper defines consistency for explanations (Definition 3.2). It is unclear whether the authors are proposing this particular definition, or if it has been previously defined in this way. This should be clarified. Furthermore, the term consistency has been used differently in the explainability and ML literature previously, albeit more casually. It would be helpful to contrast this definition to other ways the term has been used, and to relate/contrast it to other previously defined properties of explanations, such as fidelity.
The motivation for consistency could be improved. The extent to which consistency is desirable, and the size of the neighborhood in which it would be desired, both seem to be highly dependent on how the explanation is going to be used. As it stands, there is a single (simple) motivating example in the main text. Since the primary reason one would use the methods proposed in the paper is to improve consistency, it seems reasonable to further motivate this property.
I question the choice of the words “truthful” and “truthfulness” for Definition 3.4 .When T_v = 0, g is a sort of best approximation to f within a space of interpretable models. The property is interesting, but it does not intuitively align with “truthfulness” for me. With the number of overloaded terms that already exist in the explainability space (many of which invoke their own “layman” concepts), I caution against introducing another, especially a term as loaded as “truth”. I strongly encourage the use of a more verbose and precise term.
It seems unfair to call Theorem 1 the “Impossible Trinity for Interpretability” when the set of interpretable models is separated from the set of predictive models in order to get the result. Interpretable models are a very important class of predictive models. If the authors wish to name the result, I would suggest something along the lines of “Impossible Trinity for Post-Hoc Explanation”.
There is something of a conceptual gap in the flow of the paper. Section 3, and all definitions consider an arbitrary input space X. While Section 4 onwards deals with Boolean functions. What is missing is any real discussion of the process of binarizing real-valued (or other) inputs and how that affects or relates to consistency. From what I understand, ensuring the consistency of an explanation in a neighborhood of removed features (the binarized input space) is different from ensuring the consistency of that explanation in some ball around the original real-valued input. This is simply because moving to another region of the original input space (for example by changing a word/token in an input sentence or by perturbing the input image) will require a different binarization, because what it means to include/exclude one (or more) of the features is different. This seems like it should be better explored and discussed.
The paper discusses “amounts” of inconsistency, but only defines what it means to be consistent, not how to measure deviation from consistency. This seems like a considerable omission, especially since Algorithm 3 aims to reduce inconsistency.
The second half of the paper (section 4.2 onwards) struggles with clarity.
The paper should include concrete examples of output explanations. Especially for Harmonica-anchor and the constrained variant. As it stands, I do not understand how one is meant to take a set of coefficients for some polynomial bases and produce a heatmap over an image or textual input. I can guess, but this should be made clear.
The algorithm boxes include some notation that is not explained elsewhere in the main text. For instance, C is introduced in the appendix. Algorithm 1 should define input and outputs.
For clarity I would also consider using different symbols when referring to Boolean models vs. models having arbitrary inputs, instead of f(x) for both.
Finally, the paper relies heavily on the Appendix, and in that sense the main text does not truly seem self-contained. For instance, in the opening paragraph of the introduction the authors ask the reader to refer to a figure in the Appendix (Figure 3). I suggest shuffling some content around. For instance, the definition of the Shapley value (which is well-known in the field) and even Figure 1 (which isn’t really discussed), would both seem like more appropriate Appendix content than Figure 3, which helps to motivate consistency. The current introduction could also be compressed somewhat.
Some typos:
Line 72: “the algorithm only retain”
Line 131 “We call A model g is interpretable”
Questions
The paragraph starting on line 218 quantifies inconsistency, but does not explicitly explain how. What is an “amount” of inconsistency? It seems like what is being reported is the number of different explanation functions required in the neighbourhood.
Is Figure 2 correctly labeled? Should the subspace radius for Imagenet not be 1-16 and 1-\inf be for IMDB the
Should the C in Harmonica-anchor be indexed by i?
In Table 1 and Section 6.4, it is not clear to me why we would expect (or even want) any of the other methods (other than Harm. 3rd) to have a small “truthful gap” in C^3. The other methods do not aim to explain with 3rd order polynomials. Why should we assess them in this way?
It would seem to me that Harmonica’s “truthful gap” should be a function of T and \lambda, is this explored somewhere?
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.
Limitations
The paper would benefit from an explicit discussion of its limitations.