Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the effect of uncertainly in the parameters of an ML model used for consequential decision making on the validity, proximity, and diversity of sets of counterfactual explanations (CFE), namely counterfactual plans. In particular, the paper assumes the model parameters are sampled from a distribution would known mean and covariance, and studies the aforementioned metrics of counterfactual plans when the parameter distribution changes in a bounded manner (according to the Gelbrich distance). Beyond a diagnostic tool (providing bounds on how much the parametere distribution can change), the paper presents a method for counterfactual plan correction after having generated a plan (ex-post), and an approach to generate robust counterfactual plans before the fact (ex-ante). Experiments are presented for the proposed methods.
main_review: Overall I found the paper interesting and relevant. Some related literature is missing which I've highlighted below. The experimental results mostly correctly demonstrate the methodological contributions. In my opinion, the definitions and notation would need another pass of re-writing as in the current version it was quite difficult to follow with multiple read-throughs. I would be interested to read more justification of the assumed setting (in particular, on the distributional parameters, and how the method can be extended to nonlinear settings).

Sporadic (hopefully actionable) feedback and comments below
* [Sec 1, par 1] "Contrastive" explanations were first introduced by Tim Miller [A]
* [Sec 1, par 1] CFEs cannot be directly used as "directive actions" due to absence of causal understanding of actions and consequences (see Karimi et al., 2020b, [B] and others)
* [Sec 1, par 3] On "Counterfactual Plans", perhaps the authors would refrain from introducing yet another terminology to prevent confusion. Perhaps it better to simply call them collections of CFEs? This vagueness presents itself throughout the paper, e.g., in paragraph 3: "the plan should be valid: by committing to any action ...". If I've understood correctly (a page later, in the General Setup), plans are collections of actions, and each action is a simultaneous change over multiple features. In this case, one could consider each action as "plan" itself, no? Also, CFEs aren't actions because of lack of causality (see earlier point).
* [Sec 1, par 5] the two examples seem identical: change in demographic population and covariate distribution
* [Sec 1, par 6] remove "easily", and cite [B]
* [Sec 1, def 1.1] what is the difference between "feasibility" and "validity?"
* [Sec 1, notation] perhaps consider the more common notation of bold letters for vectors, e.g., $\mathbf{x}_j \in \mathbb{R}^d$ for a specific CFE, becuase $x_j$ can be interpreted as one element of a CFE.
* [Sec 2] why is the Gelbrich distance considered, as opposed to other distances? Also, can the authors please add intuition as to what it means for the distance in distribution (mean, covariance) of model parameters to be bounded up to a distance of $\rho$? Besides technical convenience, perhaps some intuitive or methodological justification can be provided?
* [Sec 2; nit] if $\tilde{\theta}$ has a nominal distribution $\hat{\mathbb{P}}$ with first and second moments $\hat{\mu}, \hat{\Sigma}$, wouldn't it be more consistent (and easier to read) if the model parameters were instead $\hat{\theta}$?
* [Sec 2] $\mathcal{P}$ is undefined and lacks explanations. It is also not used later, at least not directly ($\mathbb{B}$ is used). Generally, the notation is difficult to follow, as was the definition of CFE vs CF plans, etc.
* [Sec 2] under what conditions is $\Theta$ (not) empty?
* [Sec 2] abuse of notation in $\mathbb{Q}$ should be addressed, e.g., $\mathbb{Q}, \mathbb{Q} \sim (\cdot, \cdot), \mathbb{Q}(\cdot \in \cdot)$
* [Sec 2] evaluating the lower/upper bound of the probabilities of validity is reduced to solving a (rather complex) semi-definite program; is this easily solvable and are tradeoffs to be made here?
* [Sec 2] perhaps the authors want to clarify how $L^\star, U^\star$ act as a diagnostic tool, even with simple examples to aid readability.
* [Sec 3] abuse of notation in $\Theta({x_j})$
* [Sec 3] $\lambda_j^\star$ undefined
* [Sec 5] besides $\Sigma_g = (1 + \beta)I$, what other types of shifts in covariance could/should one consider? This seems like a rather restricted setting.
* [Sec 5, closing remarks] are there any comments on how the presented framework would extent to support nonlinear decision boundaries or other types of shifts in parameter distribution?


[A] "Contrastive Explanation: A Structural-Model Approach", Miller, 2018
[B] "The philosophical basis of algorithmic recourse", Venkatasubramanian & Alfano, 2020
[C] "On Counterfactual Explanations under Predictive Multiplicity", Pawelczyk et al., 2020
summary_of_the_review: Overall I found the paper interesting and relevant. Some related literature is missing which I've highlighted below. The experimental results mostly correctly demonstrate the methodological contributions. In my opinion, the definitions and notation would need another pass of re-writing as in the current version it was quite difficult to follow with multiple read-throughs. I would be interested to read more justification of the assumed setting (in particular, on the distributional parameters, and how the method can be extended to nonlinear settings).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies counterfactual plans under model uncertainty, that is, the parameters of the predictive model shift when the new data come. In particular, the authors focus on a linear classification setting, based on which, they provide a lower and upper bound on the probability of joint feasibility of a given counterfactual plan, a correction method to improve the lower bound, and a framework to construct a counterfactual plan that satisfies certain optimality. 

main_review: Overall, the studied problem is interesting, the writing is clear, and the results seem sound (but I did not check the proofs). I have a question about originality. What are the differences of the proposed method, compared to the previous work, such as Rawal et al. (2020), Upadhyay et al. (2021), Ustun et al., (2019), and Karimi et al. (2020), except that the previous ones consider a single counterfactual setting? 

Moreover, in this paper, the authors only study the joint feasibility. In my view, it is also very important to study the feasibility of each element in the plan, because it can help us understand the usefulness of each element and thus make changes in a principled way. Can the authors explain a bit about it?

One more question: How difficult can these results be extended to the nonlinear scenario, since in most cases, the predictive model should be nonlinear?

Minor issue: The conclusion section is missing. It would be better to have it. 

Post-rebuttal:

Thank you for the feedback. Your responses well addressed my concerns. Please add them in the revised version. I have increased the score. 
summary_of_the_review: Interesting problem and solid results, but the assumptions (linear classifications) are very strong
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper considers the problem of how to provide a collection of counterfactual explanations for a binary linear classifier such that an informed choice can be made on how best to actualise a new input based on individual preferences such that a different classification is likely to be made, even under potentially changing model parameters. It introduces the Counterfactual Plan under Ambiguity (COPA) framework, consisting of a probabilistic validity assessment of a predetermined plan under a given parameter distribution of the classifier, followed by a correction of the predetermined plan to improve validity under that distribution. These are combined in the COPA framework to produce a plan that optimises a weighted combination of the desiderata ‘proximity’, ‘diversity’ and ‘validity’. Experiments show the resulting output satisfies the derived upper and lower bounds on the validity, with good performance on the desiderata.

main_review: Very interesting paper on a highly relevant subject that rightfully draws a lot of attention these days. It is an application of explainable AI in terms of how a user should change their ‘features’ in order for them to be classified differently by a complex system. Typical examples include loan/student/job applications, where a user may want to know why they got rejected and what they would need to change in order to be successful next time, which is known as the ‘counterfactual plan’. Crucial in this problem is that different users may have different preferences/possibilities to change, and therefore a single advice / explanation to all users (even with the same covariates) may not be the best strategy, which is why it makes sense to aim for a collection of plans, allowing a user to decide for themselves which course of action they may prefer. This problem is compounded by the fact that at a later point in time certain parameters in the classification model may have changed, which may invalidate the original counterfactual plan.

The approach to tackle this problem in the paper is solid and well described. The rationale to model parameter uncertainty by a distribution characterised by the first two moments leads to meaningful and useful bounds on the probability of success (validity) of a given plan (Thm2.2+3), although in practice it will be rather difficult to assess this for real. Also it may not capture realistic changes like exclusion of certain (politically sensitive) features from the model, or inclusion of new features. 
The solution. to stat from an optimal plan under fixed parameters and then to modify/correct this based on the aforementioned distribution to improve the probability of validty is also intuitive and effective.
The desiderata for the collection of counterfactual plans also makes intuitive sense: proximity as smaller changes are likely to be more doable, diversity to give users true alternatives that suit their needs/options, and validity because it is nice the plan is actually likely to be effective.
Numerical experiments in section 5 support the claims on the bounds and show the COPA framework as a whole is effective in finding plans that satisfy the target criteria, although the real-world experiments in 5.2 are on the overly short/compressed side. As a result it is difficult to truly asses the usefulness of the final output in practice.

Nevertheless, a few remarks / questions remain. 

1. The general setup is that of a linear classifier, however the characterisation at the bottom of p2 is much more restrictive. Usually a classifier is considered linear if it is linear in terms of the parameters, and the input variables are typically transformed into a feature vector \phi(x) consisting of a collection of basis functions based on the input. But these feature vectors themselves can then be highly nonlinear in x, and are almost always also highly dependent. It allows for complex decision boundaries in a classifier that reduce to a linear decision hyperplane in some high dimensional space. This way for example a classifier can take into account that a certain age group is likely to be more successful rather than ‘the older the better’. But that also means that it is not possible for a user to directly or independently to intervene on each of these features in the classifier: they can only interact with the input x_i … each of which can be present in many features per parameter of the classifier.This is why it is often so difficult to give good advice.

If I understand correctly the current approach effectively assumes the classifier is linear in *both* variables and parameters … which is not realistic in most real-world classifiers, apart from some overly simplistic systems. This would greatly limit the applicability of the proposed approach in practice.

2. The ‘diversity’ metric in eq.(5) is a useful target in itself, but I am not sure the det(K) factor does what is needed by a user to make an optimal choice. I think it eliminates plans that are linearly dependent (as then det(K) will be zero), but it is possible that a user may need to modify either x_1 or x_2 by a significant margin to ensure 95% probability of success (depending on the parameter shift distribution), but only by a relatively small amount if x_1 and x_2 can be modified simultaneously. Conversely a user may prefer to only alter one aspect rather than try to modify two at the same time  So then there are 3 reasonable plans involving two input variables for a user to choose from, but this would not be an output solution as it would imply a lack of diversity, right?

3. The paper would benefit from an actual example of a collection of counterfactual plans as generated by the COPA framework for a given case, both without and with parameter shift, as well as how two users with the same features but different preferences would use this to choose for different actions.

Minor comments:
p1,mid “in practice …’ => explain this corresponds to an individual/personal loss function / cost matrix that can differ per user … and later show how the output of your algorithm can be used differently by two users in with the same initial features but different preferences

p2, Gen.setup: counterfactual plan stated as ‘increase relative to current value’ or ‘get at least this absolute value’? 
also: typo ‘explainaition’
p3,Def1: calling it ‘joint feasibility’ suggests it is more than what it is (simply ‘all plans should be feasible’)
p4,Thm2: discuss how to interpret the role of z_j in Thm 2.2
-
p5,3.2 ‘Correction procedure’, ‘if we can adjust K out of J actions’ => why would there be a restriction on the number of adjustments? You simply give an updated advice / plan, and each of the suggestions in there should take the adjustment into account, so there is no reason to take K < J.
p6, Proximity, eq(4): it would be good to discuss the role of the cost function c and explain it can be used to capture ‘general indication of the ease of change’ of a specific variable, in order to avoid suggesting people change gender or height.
p7, eq(6): it seems a ‘diversity’ got mixed up with a ‘validity’ component here
p9, 5.2+closing remark: this is too compact; also it would be good to assess how useful users perceive the resulting output to be

summary_of_the_review: Solid paper, important problem, interesting solution. Some caveats (in particular the assumption the classifier is linear in the input variables seems unrealistic for most real-world classifiers, potentially severely limiting the applicability of the COPA framework in practice), but overall clear accept.
review_title: null

Meta-review: The paper provides a neat idea about explaining (linear) predictors based on designing ways of perturbing parameters. It is focused on linear models (which can still lead to non-linear classifiers), but it is a relevant case, particularly for explainability.
Decision: Accept (Poster)