Amicable Perturbations

Thank you for your input. We hope that our comment titled "Clarification Regarding Novelty of Our Framework" can help explain how our set up differs significantly from previous works on counterfactuals especially in our focus on changing true class probability's instead of merely effecting the classifier's decision (as is the case with most works regarding counterfactual explanations).

With regards to your comment regarding robustness against counter measures: in our set up it is assumed that the entity crafting amicable perturbations is also the creator of the classifier and there is no adversary to deploy countermeasures. Instead we are focus on ensuring the creator of an amicable perturbation doesn't inadvertently act as an adversary. If the classifier was made more robust against adversarial attacks, this would increase our confidence in amicable perturbations. Unfortunately the task of creating robust classifiers is very difficult in general and the topic of robust classifiers for tabular data sets specifically is still in its infancy. We instead seek to leverage our knowledge of both the original ($\mathbf{x}$) and modified ($\tilde{\mathbf{x}}$) data points to device a defence that is not available in the regular adversarial setting.

We hope that our comment "Clarification Regarding the Verifier" can help explain the theory behind how the verifier works and ease your concerns.

Thank you again for your time, and the answers to your specific question is found below.

Question: Is there any theoretical analysis that can explain why the proposed verification procedure can ensure that amicable perturbations produce truly different outcomes?

Answer: We elaborate on the theory behind the verification method in the comment titled "Clarification on the Verifier." We also have the numerical justification that it is $100\%$ effective at identifying the adversarial attacks we created for our data set.

Question: How is distance $d_\mathcal{X}(\mathbf{x},\tilde{\mathbf{x}})$ defined in each data set? For example, the authors claim in Page 8 that one example should be perturbed using "a simple increase in education to the masters level." A masters degree is not a small change.

Answer: A brief description of $d_\mathcal{X}(\mathbf{x},\tilde{\mathbf{x}})$ in each data set is found on page 7. The exact function is found on our code. Based off of reviewer interest we intend on adding more detailed descriptions of the cost functions to the appendix of our revised paper.

With regards to the specific example listed. Cost includes the expected number of years to improve ones education ($6$ in this case). Although this may appear like a large change, it is modest in comparison to the options suggested by a counterfactual method (which suggested over $12$ years of education). These large changes are simply a result of the original individual being very unlikely to a high income without a significant amount of effort.

[1] Pawelczyk et al (2022), “Exploring Counterfactual Explanations Through the Lens of Adversarial Examples: A Theoretical and Empirical Analysis”, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (AISTATS)

Thank you for your input. We appreciate that causality is an important concern in the field of counterfactuals which is gaining more attention. We believe, however, that the concern of adversarially vulnerable classifiers is also important and worth exploration (as is the goal of this paper). Although a classifier is accurate in making predictions on naturally occurring data ($M(\mathbf{x})\approx\mathbb{P}_\mathcal{D}(\mathbf{y}|\mathbf{x})$) it might be inaccurate in making classification on artificially modified data ($M(\tilde{\mathbf{x}}) \not\approx \mathbb{P}_D(\tilde{\mathbf{y}}|\tilde{\mathbf{x}})$) even if $\mathcal{X}$ was created only by adjusting causal features (perhaps based off of a structural causal model) because of weaknesses in the classifier. More details are found in our comment titled "Clarification Regarding Trustworthiness." We hope that work in the future will incorporate both the idea of causality and the trustworthiness with respect to adversarial vulnerable models we propose in this paper.

As an aside, statistics about the BAR exam support the suggestion that one should move from the Far West to the Great Lakes in order to improve one's chances of passing the BAR: California has one of the lowest passage rate for the BAR exam at $73.14\%$, whereas states in the Great Lakes Area such as Minnesota or Wisconsin have passage rates of $91.46\%$ and $91.83\%$ respectively (https://lawschooli.com/easiest-bar-exam-to-pass-in-the-us/).

In regards to the novelty of our framework, we acknowledge that our optimization problem (7) is similar to those used by counterfactual and adversarial attack methods (5) and (6) (with a few key differences). We believe, however, that much of the value and novelty of our framework is found in the clear definition of the problem (Definition 1). The focus on changing the true probabilities (as a opposed to only focusing on the classifier output) separates us from most works on counterfactuals and all works on adversarial examples. Although some works on counterfactuals have specified their goal as changing the true class probabilities, we do not believe this problem was well characterized before we introduced the concepts of flexible targets, principled measures of distance to a target and a verification procedure. More details on this may be found in our comment "Clarification Regarding Framework Novelty."

With regards to our verification procedure, although its is true the verifier $V$ is trained on the same data as $M$, we train $V$ for a different classification problem (to determine if pairs of data are in the same class) and presenting the training data in a different manner (always in pairs). We suggest this forces $V$ to learn features differently than $M$ which allows for its use in the verification procedure. More details may be found in our comment "Clarification Regarding the Verifier."

Thank you again for your time, and the answers to your specific questions are found below.

Question: Why did the authors present Equations 5 and 6 as separate equations? They seem to be identical except that the notion of distance or loss is instantiated in one case but kept generic in the other.

Answer: The object of showing Equations 5 and 6 individually was to highlight how the methods used for finding counterfactuals (which evolved from Equation 5) and adversarial examples (which evolved from Equation 6) are extremely similar and can even by identical under certain choices for loss functions and norms. [1] delves deeper into this idea listing exactly which attacks and counterfactual creation methods can be identical or proven to achieve similar outputs.

Question: Why does Adult income data set contain 26000 examples only? It should contain over 48,000 examples.

Answer: We believe this is a result of our data set being cleaned to remove individuals with missing data.

Thank you for your response.

Regarding Causality: While we agree with you that taking causality explicitly into account is desirable, but we believe that this does not undermine the contribution of our framework. In addition to ensuring causality, there are several other challenging issues when attempting to change the true class probabilities of an input which we address in this work; such as the unreliable nature of classifiers on artificially generated data points (please see our detailed comment on Trustworthiness). We should also mention that our framework is flexible enough to incorporate causality constraints as follows: a) the actionable set defined in the paper can be modified to only allow changes to causally related features; b) the verification procedure could also be expanded to include a check for causal relationships. We agree that this is an important and interesting point, and we can certainly add this discussion to the revised version of the paper.

We also note, that following the link regarding rates of passing the BAR (https://lawschooli.com/easiest-bar-exam-to-pass-in-the-us/) leads to an explanation of the results of a law professor's analysis of the relative difficulty of BAR exams after compensating for the different academic backgrounds of students (original analysis here https://witnesseth.typepad.com/blog/2013/04/more-on-the-most-difficult-bar-exams.html). In this analysis California (Far West) was the single most difficult BAR exam and the states in the Great Lakes area tended to rank among the easier exams (Wisconsin being the second easiest nationwide). Although it is true that correlated features without a causal link could lead to some inaccurate results, we feel that this concern does not invalidate the contributions of this paper nor the possibility of useful results through our methods, as illustrated by our method picking up on the same trend found by an independent analysis of law school data.

Regarding the Verifier: We appreciate your legitimate point that $\tilde{**x**}$ may come from a different distribution than the training data, however we hope our detailed comment regarding the classifier explains why we believe our method will be effective at eliminating some ineffective advice. We fully recognize that data on the results of interventions (the distribution of $\tilde{**x**}$) would be very useful. For the scope of this paper, we did not consider longitudinal data and incorporating longitudinal data into the verification procedure would be an interesting avenue of future research. We can certainly include a discussion of this point in the revised paper.

In Summary: We note that exploration into causal relationships is important and should be the subject of future research. However, we believe that there are other concerns related to this topic that are also important and neither our paper (nor the vast majority of other works relating to counterfactuals and algorithmic recourse) should be disqualified solely because they focus on these other concerns.

Thank you again for your time spent in reading and responding to our comments, and please let us know if you have any questions.

Thank you for your input. We are aware that other works have considered the relationship between adversarial examples and counterfactuals, however, we believe that without our framework the task of changing true class probabilities (and avoiding the accidental creation of adversarial examples) has not been well characterized. More explanation may be found in our comment "Clarification Regarding Framework Novelty." In the comment titled "Clarification regarding Trustworthiness" we explain how our goals and techniques differ from those of [4] and [5]. In our revised paper we more clearly compare and contrast our work to previous contributions in the field of counterfactuals.

We avoid incorporating the verifier into the optimization problem (to form an end-to-end optimization problem) Because we believe this would enable the optimizer to find inputs that are adversarial to both the Classifier $M$ and verifier $V$. Please see our comment "Clarification regarding the Verifier" for a more detailed explanation.

Question: In Algorithm 1, have the authors considered adding an early stopping criteria based on $\epsilon$ and $\delta$ to the first for loop?

Answer: An early stopping criterion based on convergence would be useful to decrease computational time. We believe this criterion should be based on convergence, not $\epsilon$ and $\delta$, because we wish to find the optimal cost-reward trade off. A stopping criterion based off of $\epsilon$ and $\delta$ would instead find the first $\tilde{\mathbf{x}}$ on the optimization path that satisfies an $\epsilon,\delta$ requirement.

Thank you for your input. We appreciate your concern about causal relations and acknowledge that this is an interesting avenue for future research involving our framework and techniques. This paper focuses on the separate but equally important concern that modified data points may not produce the anticipated result because ML classifiers are often very inaccurate on modified data point (such as adversarial attacks). Please see our comment titled "Clarification Regarding Trustworthiness" for more details about this distinction. This comment also helps explain how our goal is fundamentally different from the goals of [2] and [3]. We also hope the comment titled "Clarification Regarding Trustworthiness" will address some of your concerns regarding the relationship between our paper an previous works.

Thank you again for your time, and the answers to your specific questions are found below.

Question: Have the authors considered a projected gradient descent based algorithm, instead of the addition of the $b(\mathbf{x})$ and $p(\mathbf{x})$ penalties?

Answer: Yes. We initially tried projected gradient descent, but we found that if we projected after every step of the gradient descent our output never changed. If we projected only after the gradient descent had converged, we found that the results were very far from our target (sometimes even further than the original input). We determined this was because the path of the gradient descent went far outside the actionable set and made highly incoherent inputs (i.e. having multiple values $\gg 1$ in what should be a one-hot encoding). This often meant that the final projection step erased all progress made my the gradient descent.

We determined it would not be feasible to search for the proper number of steps between projections for each individual optimization task, and instead we adopted the use of $b(\tilde{\mathbf{x}})$ and $p(\tilde{\mathbf{x}})$.

Question: For the optimization problem in Eq (7), since the f-divergence is 0 once $M(\tilde{\mathbf{x}})\in T$, it seems like all generated perturbations should be right on the boundary of $T$. However, this is not what happens in practice. Can the authors give some intuition on this?

Answer: That is a very astute observation. We had initially thought it might be necessary to run the optimization on a slightly smaller target set in order push the amicable perturbations inside the border of $T$. In practice, however, we found that even though the $\tilde{\mathbf{x}}$ produced immediately after gradient descent lied on the border of $T$, projecting $\tilde{\mathbf{x}}$ onto the coherent space ($cond(\tilde{\mathbf{x}})$) had a tendency to move the amicable perturbation inside of $T$. It is worth noting that even though the amicable perturbations we produce often lie inside of $T$, we do not produce "overkill" examples that are far inside the border of $T$. The example counterfactual from the Law School Success data set in page 8 illustrates how other methods do exhibit this "overkill" behavior.

Question: For the definition of $\Delta(\mathbf{x},\tilde{\mathbf{x}}))$, it seems to me that the threshold should be dependent on T (i.e. $p$ and $q$ ). Can the authors give some intuition on why they use a fixed threshold $\gamma$?

Answer: We initially considered two options for the verification procedure: the one found in our paper and a procedure were we compared $V(\mathbf{x},\tilde{\mathbf{x}})$ to an adaptive threshold ($\gamma_{\text{adapt}}$) determined by the $\delta$ values of $\mathbf{x}$ and $\tilde{\mathbf{x}}$ (which are dependent on $p$ and $q$). We defined the adaptive threshold as

We came to this formula by interpolating between two point where the expected value of $V$ is known. First, if $d_\mathcal{Y}(M(\tilde{\mathbf{x}}),T) = d_\mathcal{Y}(M({\mathbf{x}}),T)$ (such as when $\mathbf{x}$ = $\tilde{\mathbf{x}}$) we expect no change in the distance to the target set and $\gamma_{\text{adapt}} = 0$. Second, if $d_\mathcal{Y}(M(\tilde{\mathbf{x}}),T) = 0$ (implying $M(\tilde{\mathbf{x}}))\in T$) we expect $V(\mathbf{x},\tilde{\mathbf{x}}) > 0.5$ because we assume $\mathbf{x}\notin T$. We then set $\gamma_{\text{adapt}} = 0.5+c$.

In practice we found that the method presented in our paper was both easier to work with and more effective at eliminating adversarial examples. Running into paper length constraints, we decided to cut the "adaptive threshold method." We can certainly add this additional discussion in the Appendix/Supplementary material. For more explanation of the verification method in our paper please see our comment title "Clarification on the Verifier."

Question: A discussion of limitations and societal impacts of amicable perturbations would be useful. Can include points such as the computational cost of generating amicable perturbations, which may not be so bad in the real world because it is not usually time sensitive. The verification method for detecting inputs could potentially be improved to reduce the false rejection of amicable perturbations as adversarial.

Answer: We will include those ideas in the conclusion of our revised paper.

Question: Is it possible to effectively apply amicable perturbations to domains such as image and text? Could you discuss some potential use cases?

Answer: This is an interesting question for future research. This will be very dependent on the context of the problem and there will have to be a definable actionable set. Perhaps such an actionable set for image data could be: you are allowed to change color saturation and contrast. We also think it would be more useful if the classification task were something like "is the image pleasing or not", as opposed to trying to identify the subject of the image.

[1] Ballet, V., Renard, X., Aigrain, J., Laugel, T., Frossard, P., & Detyniecki, M. (2019). Imperceptible adversarial attacks on tabular data. arXiv preprint arXiv:1911.03274.

Question: For solving step 2 (page 6), it is mentioned that a large random sample of input pairs from the test set which have different labels are used to set the threshold $\gamma$. Is it appropriate to use the labeled test set for deciding the verification threshold without introducing bias?

Answer: We use cross validation testing data which has not been used to train the classifier. We hope limits that amount of biased this could add. It would be preferable to use previously created amicable perturbations that had been tested in the real world (in order to assign labels), but we don't assume we have access to that kind of data.

Question: Regarding Algorithm 1

Would suggest defining the penalty terms $b(\tilde{\mathbf{x}})$, $p(\tilde{\mathbf{x}})$ and the projection function $cond(\tilde{\mathbf{x}})$. Is it possible to provide a general form for different scenarios? It would be good to provide pointers in the main paper to the penalty terms defined in Appendix 5.2.1.

In the step where the gradient $\mathbf{g}$ is calculated, please show that the gradient is over all the terms by including parentheses around the terms.

In practice, is it sufficient to use a fixed learning rate $\alpha$ for the gradient descent? Have the authors explored adaptive learning rate schemes?

Please add comments for some of the lines in the algorithm for clarity. For example, can add a comment like “// Projection to ensure coherency” to the line $\tilde{\mathbf{x}} = cond(\tilde{\mathbf{x}})$.

It would help to provide a precise method (recipe) to adjust and the problem parameters. What is the method used in your implementation?

Answer: Thank you for your feedback. We are attempting to clarify our description of Algorithm 1 based off of your recommendations. In practice we used the ADAM modification of gradient descent. We will mention that fact in the updated version.

Question: It would be interesting to explore non-gradient based optimization methods for finding the amicable perturbations. This would allow us to extend the method to non-differentiable models such as gradient-boosted decision trees.

Answer: We agree that this is an interesting avenue for future research.

Question: In the experimental setup (Section 4), the cost function for each data set should be $d_\mathcal{X}$, not $d_\mathcal{Y}$. Same comment for Figure 3.

Answer: You are correct. We have corrected those errors in our updated version.

Question: In Section 4, the cost functions $d_\mathcal{X}$ defined for the data sets are somewhat vague. Could the authors describe them more precisely in an appendix?

Answer: We are adding a section to the appendix that includes more details on the cost functions. We also note that the exact code for the cost functions is found in the supplementary material.

Question: For the plots in Figure 4, how do we interpret the scale of $\epsilon$ values on the x-axis? In the discussion in the text for the Law School data set, it is mentioned that a short move from the Far West to the Great Lakes region and a mild increase in grades can result in a $11\%$ increase. It is hard to understand how to translate these changes into the $\epsilon$ (effort) values. Similar comment for the other examples.

Answer: We are adding cost values to the x-axis in figure 4 similar to those in bar charts from figure 5.

Question: The following lines under Other Methods in Section 4 is not clear.

The counterfactuals will belong to the same actionable set as the amicable perturbations, but the adversarial examples not be be in the actionable set or even to be coherent. This is significant because our verifier procedure should be able to recognize that these adversarial examples are not effective real world solutions.

Answer: We will clarify those lines in the updated version. They are meant to explain that we have the same actionable set requirements for the counterfactuals as we do for the amicable perturbations. The Carlini-Wagner attack, however, does not allow for the limiting of the set within which the adversarial examples are found. Hence the adversarial examples may lie outside the actionable set and and also break coherency (formatting) rules.

Question: More details on the neural networks used for each data set in the appendix would be useful. How are they made suitable for handling categorical inputs?

Answer: We are adding a section on classifier details to the appendix.

Question: Minor: the quality of math symbols in the figures can be improved.

Answer: We will look into ways to decrease pixelation.

Thank you for your input. We will look into how are method could be applied to non-tabular data sets as this is an avenue we had not considered.

In regards to your comments on expanding our methods to non-differentiable models, we believe this is a promising avenue for future research. Many works in counterfactual explanations have sought to find improved methods for solving the mixed integer programming problem (usually involving genetic algorithms or decision tree specific methods). We hope that these methods may be adapted to our framework.

We are working to improve the explanation of Algorithm 1 in our revised version.

We understand your concerns about the use of the Carlini-Wagner attack for a tabular data set, however, the field of adversarial attacks on tabular data is in its infancy with seminal work [1]. We were unable to find any trusted implementation of an adversarial attack on tabular data, so we decided that Carlini-Wagner was our best option.

We are very grateful for your help and suggestions for improving language and catching typos.

Thank you again for your time, and the answers to your specific questions are found below.

Question: The citation format of references is not correct. There should be a parentheses around citations; e.g. (Leo et al., 2019) instead of Leo et al., 2019.

Answer: You are correct. We are correcting that error in our updated version.

Question: The paper needs some proofreading for language issues and typos. For instance, in the last paragraph of page 2, it should be:

“In Section 2, we define an amicable perturbation as well as contrast it with related work.”

Answer: You are correct. We are currently proof reading our paper to improve readability and catch typos. We have corrected the error you pointed out.

Question: The paper needs to define $k$ as the number of classes and $m$ as the input dimension at the start of Section 2. Sometimes these two symbols are interchanged leading to confusion. A few instances are listed below:

-In Eqn 28, it should be $m$ instead of $k$ denoting the number of features.

-In the proof of theorem 1 (Appendix 5.1), the number of classes is denoted by $m$ instead of $k$.

-On page 6, under Solving Step 1, the projection function should be defined as $cond:\mathbb{R}^m\rightarrow\mathcal{X}$.

Answer: Thank you for catching those errors. We have made those corrections in our updated paper.

Question: Section 2, Problem setting and goals

The notations could be more clear. Rather than saying $(\mathcal{X},\mathcal{Y})\sim \mathcal{D}$, it would be better to say $(\mathbf{x},\mathbf{y})\sim \mathcal{D}$, where $\mathbf{x}\in\mathcal{X}\subset\mathbb{R}^m$ and $\mathbf{y}\in\mathcal{Y}$. Here, $\mathcal{Y}$ is the $k$ probability simplex.

Also, different from conventional notation where $\mathbf{y}$ is an integer, here it is the true (conditional) probability distribution over the set of classes. Therefore, it would be clearer to define a class random variable $C\in\{1,...,k\}$ and $\mathbf{y}:=[\mathbb{P}(C=1|\mathbf{x}),...,\mathbb{P}(C=k|\mathbf{x})]$, i.e. the true class posterior probabilities. Of course, this could specialize to a one-hot coded label.

With this definition, it is clear that an amicable perturbation $\tilde{mathbf{x}}$ aims to change the true class of an input to a desired $\tilde{\mathbf{y}}:=[\mathbb{P}(C=1|\tilde{\mathbf{x}}),...,\mathbb{P}(C=k|\tilde{\mathbf{x}})]$.

In the definition of the difference training data (before Eqn 3), used to train $V(\mathbf{x},\tilde{\mathbf{x}})$, it should not include pairs $(i,j)$ where $i=j$. If the architecture of $V$ does not depend on the order of inputs, then it should only include pairs where $i>j$.

In Eqn (3), it would be simpler to define $z^{(i,j)} = 1[\mathbf{y}^{(i)} = \mathbf{y}^{(j)}]$, i.e. using the indicator function.

Answer: We appreciate your suggestions for improving clarity. We are looking into updating those notations for clarity while still maintaining consistent notations with other papers in this field.

Question: The verification function is actually estimating the conditional probability that the true class corresponding to $\mathbf{x}$ and $\tilde{\mathbf{x}}$ are equal given the inputs. Let $C$ and $\tilde{C}$ denote the true class corresponding to $\mathbf{x}$ and $\tilde{\mathbf{x}}$. The verification function estimates the probability $\mathbb{P}(C,\tilde{C}|\tilde{\mathbf{x}})$. Another way to estimate this probability is using the classifier $M(\mathbf{x})$, assuming conditional independence of $C$ and $\tilde{C}$ given $(\mathbf{x},\tilde{\mathbf{x}})$, as follows: $\hat{\mathbb{P}}(C,\tilde{C}|\tilde{\mathbf{x}},\mathbf{x}) = \sum_{i=1}^k M_i(\mathbf{x})M_i(\tilde{\mathbf{x}})$

Answer: We are trying to make this explanation more clear in our revised version and appreciate your suggestions on how we could do this.