Greedy PIG: Adaptive Integrated Gradients

We thank the reviewer for the valuable comments and for bringing some related work to our attention.

The method is designed to perform well when evaluated using the Softmax AUC which is not the most commonly used metric (insertion and deletion scores are). How the Greedy PIG compare with other methods using these metrics?

After reading through the work of Petsiuk et al. 2018, we conclude that the scores we are using are indeed the insertion scores (the x-axis is the number of selected pixel values and not the entropic quantity used in Kapishnikov et al. 2019). As we were not aware of Petsiuk et al. 2018, we implicitly re-defined insertion scores as a variation of the SIC AUC scores of Kapishnikov et al. 2019 (and still called them SIC AUC scores). We thank the reviewer for pointing us to this work, this simplifies our exposition! In the revised version we will clarify that we are using insertion scores and cite Petsiuk et al. 2018.

A recent method IDGI [1] was introduced

Thank you for letting us know about this work, indeed it seems very related and interesting. We will read it carefully and cite it in the next version.

On top of my previous concerns, I would like to ask if the authors could the authors share their code (at least on an example). I am intrigued by the difference in performance with GIG which in my understanding is very similar to the proposed method

Yes, we are preparing to publicly release our code. This requires some time on our side due to approvals, but we hope to be able to finish it by the revision deadline.

Petsiuk, Vitali, Abir Das, and Kate Saenko. "Rise: Randomized input sampling for explanation of black-box models." arXiv preprint arXiv:1806.07421 (2018).

We thank the reviewer for their comments and suggestions.

The stated motivation for greedy PIG is to make the attributions more robust to feature correlations. However this aspect has never been explicitly evaluated in experiments. Lemma 4.4 is an attempt to theoretically justify why integrated gradients would fail when redundant features are present, however no proof is provided in the paper to evaluate the correctness of the statement. Moreover, it is not clear how greedy PIG solves the issue stated in Lemma 4.4. Clarifying this would further strengthen the motivations of this work.

We will add a proof of Lemma 4.4 in the next version (it is very short). How Greedy PIG avoids the redundancy issue in Lemma 4.4 is explained in the paragraph right after Lemma 4.4. In short, because of adaptivity, selecting a feature $X$ in round $i$ will lead to avoiding redundant features in rounds $> i$, since their PIG score will be $0$. More generally on adaptivity, there are theoretical lower bounds (explained in Section 3.4) showing that even for the special case of submodular function maximization, multiple rounds of adaptive function evaluations are necessary for computing an optimal solution (Balkanski et al. 2018).

The Proof of Lemma 4.3 is not clear. Why is the hessian bounded by K? What is the non-correlation property of g? What is \bar{H}. The authors say this is average on a path from w to w_{i}. What is the formulae for computing this average? how is the path computed? what is w_{I}. The details should be clarified to the reader.

We thank the reviewer for noticing an editing mistake. Some leftover text from a previously removed lemma was incorrectly pasted into the proof which did not make sense. As for $w_{\{i\}}$, it is a vector that is equal to $w_i$ at $i$ and $0$ everywhere else, as defined in the preliminaries (Section 2.2). The Hessian averaging is a direct consequence of Taylor’s theorem (see e.g. a stronger version in Theorem 1 here: https://www.cs.princeton.edu/courses/archive/fall18/cos597G/lecnotes/lecture3.pdf). We will clarify this better in the revised version.

More generally, it is not clear to me what g is in the paper. Is it the neural network function f as in equation 1? Section 3.3 says this is a continuous extension that allows optimization of equation 3, however equation 3 is never optimized in their greedyPIG algorithm.

In our work, we seek to solve the subset selection problem (3) by using a continuous relaxation $g$ of $G$, which allows us to compute gradients. In fact it is sometimes easier to directly think in terms of $g$ instead of $G$. $g$ can be any continuous function that matches $G$ on the vertices of the hypercube, but the choice of $g$ is usually natural (e.g., the training loss of a neural network $f(\cdot; \theta)$).

For the experiments, what is the value of z, chosen for the greedy-PIG algorithm in each instance. An ablation study on the effect of z (the number of top-z features selected in each iteration) on the different metrics would be interesting as it would show the robustness of the method on the choice of z. If one would want to break correlations, is the ideal value z=1?

That’s exactly right, the ideal value for breaking correlations is $z=1$. In all our experiments, we choose $z=k/R$, where $R$ is the number of rounds. This means that $z=1$ implies a large number of rounds, which increases the overall running time (since we need to compute $O(RT)$ gradients, where $T$ is the number of PIG steps) but generally improves the solution quality. We observed that even slightly increasing the number of rounds (e.g. from $R=1$ to $R=5$) gives noticeable improvement in the feature attribution metrics. In the experiments of Figure 1 we picked $R=100$ ($z\approx 1500$) because there ~150k features ($224\times 224\times 3$), and in the experiments of Table 1 we picked $R=k$ ($z=1$) because there are only $39$ features.

It is not clear what is the Sequential Gradient, the authors refer to in this paper. Is it eq (1) evaluated at one single point instead of a discretization on N points? If yes, how is this point selected? how accurate is this estimation?

Sequential Gradient is Greedy PIG with $T=1$. Specifically, it approximates the integral $\int_{t=0}^1 \nabla g(t {\bf 1}) dt$ by $\nabla g({\bf 0})$. This is accurate if $g$ is close to linear, but based on our results it is still a reliable approach with lower runtime (e.g. see the first Greedy PIG row in Table 1).

We thank the reviewer for the comments and for identifying some typos that we will fix in the revised version.

The novelty of the proposed method is limited. By simply combining feature attribution and feature selection with a unified discrete optimization framework based on subset selection, the authors introduce limited insight into tackling this problem. Equation 7 is a simple extension of Equation 1.

Our contribution is not replacing a set function by a continuous relaxation. Our contribution is introducing multi-round adaptivity (inspired by subset selection problems) to solve attribution problems more effectively.

The proposed Greedy PIG may introduce a sub-optimal problem. By greedily selecting the top-attribution features computed by integrated gradients in each round, the proposed method cannot guarantee a global optimal solution for the feature attribution problem. Further, if seeking the global optimal solution for the feature attribution problem is not the goal of this submission, it may be better for the authors to demonstrate that a satisfactory solution will be attained by the proposed method.

The subset selection problem is NP-hard in general (there are many hardness results for this type of problem, see e.g. Foster et al. 2015). We do not claim to achieve a globally optimal solution but one with good experimental performance in feature attribution tasks. If the reviewer has a suggestion on an algorithm that might return higher quality solutions for the feature attribution objectives, we would be happy to consider it. Further, the greedy algorithm is provably the best achievable algorithm for certain subset selection problems, e.g., monotone submodular maximization subject to a cardinality constraint, unless P = NP.

Foster, Dean, Howard Karloff, and Justin Thaler. "Variable selection is hard." In Conference on Learning Theory, pp. 696-709. PMLR, 2015.

We thank the reviewer for the very detailed comments. We provide answers to all their questions below.

Why does Greedy PID maximize the objective function? The paper claims that formulating feature attribution as an optimization problem has advantages. But the proposed algorithm seems to be an extension of PIG and has nothing to do with maximizing the real object function.

The main ingredient of our algorithm is a subroutine that selects the maximum entries of $\nabla g(w)$. These are the entries that (locally) increase the value of $g$ the most, and so each iteration of the Greedy PIG algorithm (for $T=1$ discretization steps) is exactly making a (sparse) step towards maximizing the function (this also holds for $T>1$ discretization steps under assumptions, e.g., if we assume $g$ is a quadratic function). Furthermore, as we show in Lemma 4.3, the PIG scores approximate the marginal gains under some conditions, and so the set of top attributed features will have high marginal gains in some approximate sense. Repeating this process adaptively over multiple rounds significantly boosts the quality of the solution for the maximization problem. This is the intuition why this algorithm performs well for the maximization problem, which is confirmed in the experiments.

While we agree that there is room for further analysis in the theoretical results (which is partially attributable to the PIG algorithm not having strong theoretical backing but a large body of experimental work), we believe that the strong experimental improvements presented in this paper will motivate theoretical study into the properties of the PIG algorithm. That said, our approach of introducing adaptivity is independent of PIG and can be used to boost any algorithm that approximates the marginal gains, so it should be of independent interest.

Is the continuous objective function a submodular function? The paper seems to lean a lot on the submodularity of set functions to argue for the approximate optimality of Greedy PIG.

Assuming that $G$ is submodular is indeed too strong and generally not met in practice. This is why we do not assume submodularity in our work and the set functions used in the experiments are generally not submodular. That said, based on the experiments many of these problems do exhibit some weaker form of diminishing returns property (see e.g. Figures 1 and 3). Roughly, to get correct classification, knowing the first few features (or edges) gives incrementally a better classification accuracy than incrementally uncovering more features.

The part of why Greedy eliminates the effect of feature correlation needs clarification. Is there some mathematical evidence to support claims in paragraph "Why Greedy captures correlations"?

Consider features numbered $1,\dots, n$. If the function $G$ is non-decomposable (which is what we mean by correlations between the features), then the total gain of adding all the features, $G(\\{1,\dots,n\\} )-G(\emptyset)$, can be very different from the sum of their marginal gains $G(\\{1\\}) - G(\emptyset) + \dots + G(\\{n\\}) - G(\emptyset)$. Therefore, inserting many of these features simultaneously based on their marginal gains can lead to a suboptimal selection. However, if we add them one at a time, then the sum of the marginal gains of the added features (at the time they were added) are $[G(\\{1\\}) - G(\emptyset)] + [G(\\{1, 2\\}) - G(\\{1\\})] + \dots + [G(\\{1,\dots,n\\}) - G(\\{1,\dots,n-1\\})]$, which is equal to the total gain. This is because upon selecting feature $i$, its correlations with features $>i$ are eliminated, since $i$ is now selected.

Why is it good that attributions correlate with marginal gains at S=0? If marginal gains are what we want, why don't we directly use them?

The feature with the highest marginal gain is the best greedy choice of feature to select to $S$ for maximizing $G$. If the attributions correlate with the marginal gains, then they can be used as proxies for the marginal gains and selecting the feature with the top attribution will be a high-quality choice of a feature to select, in terms of maximizing $G$. We don't directly use marginal gains because it is computationally inefficient. Computing all marginal gains of $G$ for each selection step requires $O(n)$ evaluations of $G$, whereas PIG only requires evaluating $\nabla g$ a constant number of times.

I would like to thank the authors for addressing my questions and concerns. The main issue of this submission is the disconnection between the problem formulation and its proposed solution. Although the solution seems to lead to good results, this issue makes the formulation, which consists of a large part of the paper's content as well as a major claimed contribution, unnecessary. I am not convinced by the authors' rebuttal regarding this point:

• The algorithm computes the integration of $\nabla g$, not $\nabla g$, why does selecting the largest entries in this vector lead to a better value for g? The analysis regarding the relation between PIG scores and marginal gains in Lemme 4.3 only apply when the base set S is empty, this analysis does not hold when some points are already selected. I think proving that the algorithm gradually increases the objective function is critical. The paper and the rebuttal have not provided such proof.
• The paper is greatly inspired and mentions a lot about literature on submodular optimization but its objective function is not a submocular function (or not proven so). This makes the support for the proposed adaptivity weak and the mention of submodular optimization unnecessary.
• The answer for my question on the paragraph "Why Greedy captures correlations" is not clear.
• About marginal gains, the point seems to be that approximating marginal gains is good. Even though, computing them could be inefficient, it should be feasible. In order to demonstrate this point, I think a comparison between Greedy PIG and a baseline that uses marginal gains is important.

With the reasons above, I want to keep my initial rating.