Counterfactual Plans under Distributional Ambiguity
Authors: Ngoc Bui
Duy Nguyen
Viet Anh Nguyen
Venue: ICLR 2022 Poster (2022)
Keywords: Counterfactual explanations
Robust optimization

Abstract: Counterfactual explanations are attracting significant attention due to the flourishing applications of machine learning models in consequential domains. A counterfactual plan consists of multiple possibilities to modify a given instance so that the model's prediction will be altered. As the predictive model can be updated subject to the future arrival of new data, a counterfactual plan may become ineffective or infeasible, with respect to the future values of the model parameters. In this work, we study the counterfactual plans under model uncertainty, in which the distribution of the model parameters is partially prescribed using only the first- and second-moment information. First, we propose an uncertainty quantification tool to compute the lower and upper bounds of the probability of feasibility for any given counterfactual plan. We then provide corrective methods to adjust the counterfactual plan to improve the feasibility measure. The numerical experiments validate our bounds and demonstrate that our correction increases the robustness of the counterfactual plans in different real-world datasets.

Published as a conference paper at ICLR 2022
COUNTERFACTUAL PLANS UNDER DISTRIBUTIONAL AMBIGUITY
Ngoe Bui, Duy Nguyen, Viet Anh Nguyen
VinAI Research, Vietnam
ABSTRACT
Counterfactual explanations are attracting significant attention due to the flourish- ing applications of machine learning models in consequential domains. A coun- terfactual plan consists of multiple possibilities to modify a given instance so that the model's prediction will be altered. As the predictive model can be updated subject to the future arrival of new data, a counterfactual plan may become inef- fective or infeasible with respect to the future values of the model parameters. this work, we study the counterfactual plans under model uncertainty, in which the distribution of the model parameters is partially prescribed using only the first- and second-momen information. First, we propose an uncertainty quantification tool to compute the lower and upper bounds the probability validity for any given counterfactual plan. We then provide corrective methods to adjust the counter- factual plan to improve the validity measure. The numerical experiments validate our bounds and demonstrate that our correction increases the robustness of the counterfactual plans in different real-world datasets.
INTRODUCTION
Machine learning models, thanks their superior predictive performance, blooming with in- creasing applications in consequential decision- tasks. Along with the potential to help make better decisions, current machine learning models are also raising concerns about their explain- ability and transparency, especially in domains where humans are at stake. These domains span from loan approvals (Siddiqi 2012), university admission (Waters & Miikkulainen 2014) to job hiring (Ajunwa et al.) 2016). In these applications, it is instructive to understand why particular algorithmic decision is made, and counterfactual explanations act as a useful toolkit to compre- hend (black-box) machine learning models (Wachter et al. 2017). Counterfactual explanation is also known the field of interpretable machine learning as contrastive explanation (Miller 2018 Karimi et al.) (202bb) recourse (Ustun al. 2019). counterfactual explanation suggests how an instance should be modified so as to receive an alternate algorithmic outcome. As such, could be used as a suggestion for improvement purposes. For example, a student rejected from graduate study, and the university can provide one or multiple counterfactuals to guide the applicant for ad- mission the following year. A concrete example may be of the form "get GRE score of least 325" or "get a 6-month research experience".
In practice, providing counterfactual plan consisting of multiple examples is highly desirable because single counterfactual to every applicant with the same covariates may be unsatisfac- tory (Wachter al., 2017). Indeed, the covariates can barely capture the intrinsic behaviors, con- straints, and unrevealed preferences of the person they represent so that the users with the same features may have different preferences to modify their input. As a consequence, pre-emptive de- sign choice is to provide a "menu" of possible recourses, and let the applicant choose the recourse that fits them best. Viewed in this way, a counterfactual plan has the potential to increase satisfaction and build trust among the stakeholders of any machine learning application.
Constructing a counterfactual plan, however, not a straightforward task because of the many com- peting criteria in the design process. By definition, the plan should be valid: by committing any counterfactual in the plan, the application should be able to flip his current unfavorable outcome to favorable one. However, each possibility in the plan should be in the proximity of the covariates

---

Published as a conference paper at ICLR 2022
of the applicant so that the modification is actionable. Further, the plan should consist of diverse range of recourses to accommodate the different tastes and preferences of the population.
Russell (2119) propose mixed-integer programming method to generate counterfactual plan for linear classifier, in which the diversity is imposed using a rule-based approach. In et al. (000)) the authors propose model-agnostic approach using multi-objeccivve evolutionary algorithm to construct a diverse counterfactual plan. More recently, |Mthilal et al. (2020) use the determinantal point process measure the diversity of a plan. The authors then formulate optimization problem to find the counterfactual plan that minimizes the weighted sum of three terms representing validity, proximity, and diversity.
A critical drawback of the existing works the assumption of an invariant predic- tive model, which often fails to hold in practical settings. In fact, during a tur- bulent pandemic time, it is difficult to as- sume that the demographic population of students applying for postgraduate studies remain unchanged. And even in the case that the demography remains unchanged, an unfavorable admission outcome. The student im- of the recommended recourse x' cho- sen from the counterfactual plan {æy} and re-applies
2021
2022
Co., (ara)
update model
Cg (z')
Applying 1
Reject
Re-apolying
x' E {m²} 1
Reject
{zy}
Figure 1: A student applies in Year 2021 and receives
special pandemic conditions such as hybrid learning mode or travel bans may affect the applicants' package, which in turn leads to in Year 2022. However, the outcome is again unfavor- fluctuations of the covariate distribution in able because of the change in the model parameters 6. the applicant pool.
plements
These shifts in the data channeled to the shift in the parameters of the predictive model: when the machine learning models are re-trained or re- re-calibrated with new data, their parameters also change accordingly (Venkatasubrammaiian & Alfano| 2020). This raises an emerging concern because the counterfactual plan is usually designed to be valid to only the current model, but that is not enough to guarantee any validity on the future models. Thus, the counterfactual plan carries promise of favorable future outcome, nevertheless, this promise is fragile.
hence reasonable demand the counterfactual plan to robust with respect to the shift of the parameters. [Pawelczyk et al. (2020) study the sparsity of counterfactuals and its non-robustness under different fixed models (predictive multiplicity). |Rwaal al. (2020) consider the counterfac- tual plan problem and describe several types of model shift related to the correction, temporal, and geospatial shift from data. They also study the trade-off between the recourse proximity and its validity regarding the model updates. Most recently, [Uaadhyay et al. (2021) leverage robust opti- mization to generate a counterfactual that is robust to some constrained perturbations the model's parameters. However, both works consider only the single counterfactual settings.
Contributions. We study the many facets of the counterfactual plans with respect to random future model parameters. We focus a linear classification setting and we prescribe the random model parameters only through the first- and second-momen information. We contribute concretely
1. a diagnostic tool to assess the validity of counterfactual plan. provides lower and upper bound on the probability of joint validity of given plan subject to uncertain model parameters.
2. a correction tool to improve the validity a counterfactual plan, while keeping the modifications to each counterfactual at minimal level. The corrections are intuitive and admit closed-form expression.
3. a COunterfactual Plan under Ambiguity (COPA) framework to construct a counterfactual plan which explicitly takes the model uncertainty into consideration. It minimizes the weighted sum of validity, proximity, and diversity terms, and can be solved efficiently using gradient descents.
Each of our above contributions is exposed in Section 2 and respectively. In Section conduct experiments on both synthetic and real-world datasets to demonstrate the efficiency of our conrections and of our COPA framework. All proofs can be found in the appendix.
General setup. Consider a covariate space Rd and a linear binary classification setting. Each linear classifier be parametrized by 0 IRd with decision output Co(x) 1 if 0 x 0, and
2

---

Published as a conference paper at ICLR 2022
O otherwise, where 0 represents an unfavorable outcome. Note that omit the bias term to avoid clutter, taking the bias term into account can be achieved by extending the dimension and by an extra dimension. A counterfactual plan is set of J counterfactual explanations (zz))=1.....) and we denote (.²) } for short. When J = 1, we have single counterfactual explanation problem, which is the subject of recent works (Ustun et. 2019: Karimi al. 2020a Upadhyay al. 2021
Next, we define the joint validity of a counterfactual plan.
Definition 1.1 (Joint validity). A counterfactual plan {æz} is valid with respect to a realization 0 if Ca(zy) for all 1.l....-- l.....,J.
Notations. We use $ ($4) to denote the space of symmetric positive (semi)definite matrices. For any A E Rmxxm, the trace operator is Tr [A] Σ Ag. For any integer J, [J] - [J....,JJ.
VALIDITY BOUNDS OF COUNTERFACTUAL PLANS
In this section, we propose a diagnostic tool to benchmark the validity of a pre-computed counter- factual plan {æz}] J. We model the random model parameters Ó with a nominal distribution IP. Instead of making strong assumption on specific parametric form of PP such Gaussian distribution, only assume that TP is known only up to the second moment. More specifically, assume that under P. 8 has nominal mean vector P and nominal covariance matrix Σ Sd
Definition 2.1 (Gelbrich distance). The Gelbrich distance between two pairs (μ), E1) E Rdd 8 and (12, 22) E Rd x 84 is defined as
G((M) (1), (HZ, Σn))
- 12l1 -11m--
Ir + -
The Gelbrich distance is closely related the optimal transport distance between Gaussian distri- butions. Indeed, G((21 Σ1). (p2, Σ2)) is equal to the type-2 Wasserstein distance between two Gaussian distributions (Mn, , En) and A M(22, Σ2) [Gelbrich] 1990). It is thus trivial that G is a dis- tance on 22 x _ and as a consequence, is symmetric and G( E,), (#2, E2)) = 0 and only (ui, Σ,) = (#2, Σz). Using the Gelbrich distance to design the moment ambiguity set for distri- butionally robust optimization leads to many desirable properties such as computational tractability and performance guarantees (Kuhn et al., 2019. Nguyen et al. 2021a). Motivated by this idea, we first construct the following uncertainty set
u A {p,, Σ) E Rd s4. G((p, Σ), (7, E)) S p).
which is formally p-neighborhood the mean vector-covariance matrix space around the nominal moment (f,, Σ). The ambiguity set for the distributions of 0 is obtained by lifting 2/ to generate family of probability measures that satisfy the moment conditions
B B (Q P: 3(2, Σ) 24 such that Q (1,, E)}
where P is set of all probability measures supported on Rd and Q ~ (n. E) indicates that Q has mean vector μ and covariance matrix
The central question of this section is: the distribution of 0 belongs to B. what the probability that a given plan {I,} is valid? To answer this question. we define the event set e (({x,)) that contains all model parameter values that renders (a,} jointly valid. Under the definition of linear model, (((r)) }) is an intersection of open hyperplanes of the form
(((x,)) e (0 E Rd 1I. 0 Vj e [J]}.
We name O(zx,)) }) the set of favorable parameters. The probability of validity for plan under measure is Q(0 O(fx,))). We are interested in evaluating the lower and the upper bound probability that the plan {-,} is valid uniformly over all distributions Q E B. This is equivalent to quantifying the following quantities
inf Q(0 (((z,))) and sup Q(0 ((2,)))) QER
QEB
3

---

Published as a conference paper at ICLR 2022
In the remainder of this section, we discuss how to evaluate the bounds for these terms.
Lower bound.
We denote by O the interior of the set O that is, ((()))) & {0 E R² x 0 >0 0 Vij. Note that all the inequalities defining (1xx,) are strict incqualities. By definition, we have (2({2;]) ((1;,), and hence infgeB Q(0 (0z })) I iinfee Q(4 ((z;))). Because ({xy)) is an open set, we can leverage the generalized Chebyshev lower bound to evaluate the minimum quantity of Q E ((xx))) over all distributions with given mean and covariance matrix (Vandenberghe et al. 2007). Adding moment uncertainty via the set U is obtained by rejoining two minimization layers. The next theorem presents this result.
Theorem 2.2 (Lower bound). For any P RR,, 12 Rd and E. E 84, let T,* be the optimal value of the following semidefinite program
inf
1 - Ejely X3
S.
H E R. EESt S Ce Faxd
M E 3 Ej [J]
X E RR, 2j E R Z3
E gd
2j
L =
2 2j 0,
X1
E [
(2)
Σ
12
2/
M
11
Σ
C
00,
M E
= 1
[2]
Xg)
CC
SEI
|1 2- 27 T
11 +
Tr [M + S 20|
spp.
Then we have L inf Q(0 E 0 ((2;)))) QEB
S inf Q(0 E O(1x)))) QEB
Upper bound. Because ((1x;)) }) is closed set, we can leverage duality result to evaluate the maximum quantity of Q(0 E (({x,})) over all distributions with given mean and covariance matrix (Isil 1960). Adding moment uncertainty via the set U is obtained by invoking the support function of the moment set. This result presented in the next theorem
Theorem 2.3 (Upper bound). For any E R4,, P E Rd and E E s4, let U* be the optimal value of the following semidefinite program
inf
+ 7pp²
110122 Tr [ + + Tr [Q]
t.
7 E 20 E
RR
EER Z sd
EE R., Q
E
Sd
E
R
U*
71 - 2
A34
I Z
7p
2 0,
Q
[ +2
%
Z
2
1 b
2 20
0,
2
20 -
1
2 Σ jE[J]
[
1
0
Then we have supoes Q(Ō E @(tz,))) U
Thanks to the choice of the Gelbrich distance G, both optimization problems in Theorems 2.2 and 2.3 are linear semidefinite programs, and they can be solved efficiently by standard, off-the-shelf solvers such MOSEK to high dimensions (MOSEK ApS 2019). Other choices of distance (divergence) are also available: for example, one may opt for the Kullback- Leibler (KL) type divergence between Gaussian distribution to prescribe / as in Nguyen et al. (020)) and Taskesen al. (202T). Un- fortunately, the KI. type divergence entails a log log-determinant term, and the resulting optimization problems are no longer linear programs and are no longer solvable using MOSEK. Equipped with L and U* we have the bounds
L' S Q(tat) is valid plan) < U
E
on the validity of the counterfactual plans {æz} under the distributional ambiguity set I.
Complementary information. The previous results show that we can compute the lower bound I. and upper bound U for the probability of validity by solving semidefinite programs. We now show that the two quantities L* and U* are complementary to each other in a specific sense.
Proposition 2.4 (Complementary information). For any instance, either L* = 0 or U* = 1. More specifically, we have: (i) Tf ((xr))) then U = 1, and (ä) If ji O ((x;))) then I O.
4

---

Published as a conference paper at ICLR 2022
Because L and U** are bounds for probability quantity, they are only informative when they different from 0 and 1. Proposition22.4asee
that the upper bound U trivial when ç E {({2)) }), while the lower bound L becomes trival if ğ & @((2))). Next, we leverage these insights to improve the validity a given counterfactual plan.
COUNTERFACTUAL PLAN CORRECTIONS
Given counterfactual plan {ry}: , it may happen that {ay} } have low probability of being valid under random realizations of the future model parameter 0. The diagnostic tools proposed in Section indicate that {æy} } has low validity when the bounds are low, and ing this plan such that the lower bounds L are increased. Indeed, increasing L guarantees higher confidence that the plan valid, should the distribution
here interested in correct-
belongs to the ambiguity set. At this point, one may be tempted to optimize I. directly with {æ,) by first converting problem (2) into maximization problem, and then jointly maximizing with { being decision variables. Unfortu- nately, this approach entails bilinear terms x žÿ in the constraints, and this approach is notoriously challenging solve. We thus resort heuristics for correction. Towards this end, the results from Proposition 2.4 suggest that there are two correction operations that we need to perform to improve the validity of the counterfactual plan:
(i) When 7 & ((xx)), then Proposition 2.4 suggests that we should modify the plan {æz} so that the resulting set of favorable parameters contains ft. We term this type of correction Requirement correction, and we consider one specific Requirement correction in Section 3.1
(ii) When ({I,,)) we can also modify {x,} } to as to increase the lower bound L This type of correction is termed an Improvement correction because its goal is to increase the validity of the counterfactual plans. We consider the Mahalanobis Improvement correction Section 3.2
We emphasize that the corrections of the plan } are designed such that the modifications to each counterfactual z, should be minimal. This is achieved by two main criteria: the correction should modify as few counterfactuals as possible, and the modification to each counterfactual should also be as small as possible.
3.1 REQUIREMENT CORRECTION
We propose a Requirement correction with the goal of obtaining a corrected plan {2/} from the given plan {r,} such that ğ lies inside (or strictly inside) the set O((x))). A simple Requirement correction is to construct the corrected plan {2t) by
if T0'x226 26, z'1 - { arg min [| r,lle xz Tf <c,
Vj E []]
for some e 2 Using this rule, 2/ is the smallest modification of Iy measured in the Euclidean distance such that xa is valid with e-margin with respect to the expected future parameter p. The margin e adds a layer of robustness: if
then ğ lies in the interior of the set (((z()), while c then ji lies on the boundary of the set (( Moreover, it easy see that in the case TT proposed Requirement correction admits thus the analytical form:
æi < e, the resulting z is the Euclidean projection of w, onto the hyperplane f IG e. The
=f= min (0, x
E
P
3.2 MAHALANOBIS IMPROVEMENT CORRECTION
Given a plan {zy} such that e O({x,)) and an integer K between 1 and J, the Mahalanobis Improvement correction aims to modify K out of plans to obtain the corrected plan {zt}- The goal of this correction is to increase the lower bound value L* associated with the plan {a ). while at the same time keeping the amount of modification small possible. To attain this goal, first describe the geometric intuition behind the lower bound L in ( and then leverage this intuition to generate the correction.
5

---

Published as a conference paper at ICLR 2022
Geometric infuition. We first analyze the distribu- tion of the random vector & that attains the validity lower bound L" To simplify the exposition, we assume that X > O and define X = E; X7. Following the same argument in Vandenberghe et al. (2007 $2.2), the dis- tribution of 0 can be constructed as mixture of random vectors 8J satisfying:
10
2f /
-10
Yj 0,......
i B with probability 2j.
2/ PM
-20
where for each j J, we have E[0,] 2 /23 and 0 follows a properly chosen distribution. By the validity of 2", on the hyperplane {0 xz] = 03. Thus, we can think of A as the marginal increase in the lower bound T,* if we slightly perturb zj that the point / lies inside the set of favorable parameters. This observation underlies the Mahalanobis correction which we describe next.
-10
10 20
0
verify that the location 25 />3 lies
Figure 2: Illustaaiion with
and
J = 3. Shaded area is O (,, dashed
ellipsoid represents (0 (x) 50
(1) 1, black dots are the locations of
27 2//
Correction procedure. If we can adjust K out of J counterfactuals to improve the validity, then it reasonable to modify the K counterfactuals associated with the K largest values of Aÿ. where 2 is the optimal value of the variable X in problem (2). Without any loss of generality, assume that X have decreasing values, and in this case, our correction procedure will modify the counterfactuals ry for j 1, ....., K. Further, correct each counterfactual, we find x' in Á-neighborhood of at such that the Mahalanobis distance from já to the hyperplane {0: x = 0} maximized, where the Mahalanobis distance is computed with the nominal covariance matrix E. This is equivalent to solving max-min problem
= arg max ming == V
7
s. L.
E Rdd
|| xz l|2 S A.
The next result indicates that o' can be found by solving a conic optimization problem.
Theorem 3.1 (Mahalanobis Improvement correction). The Mahalanobis correction of æ x'j v" /t",, where (w"(t" is the optimal solution of the following conic optimization problem
min Eo U Rd, tetteR, R4, || woo-tag txllla < At, v TT 1
We have specifically modified zny in (3) with respect the nominal mean vector and covariance matrix (ūz, E) of the random vector 0. Alternatively,
can also use ",,, where (n* Σ is the
optimal solution in the variable (14, Σ) of (2) to form the optimization problem. Theorem 3. holds
with the corresponding parameters (μ²* E²). Similarly, equation (4) recovers the Euclidean jec-
tion if we use an identity matrix for weighting. The conic optimization problem in Theorem 3. can
be solved using standard off-the-shelf solvers such Mosek (MOSEK ApS] 2019)
4 COUNTERFACTUAL PLAN CONSTRUCTION UNDER AMBIGUITY
We propose in this section the COunterfactual Plan under Ambiguity (COPA) framework to devise a counterfactual plan that has high validity under random future model parameters. Given an input instance 2o, COPA builds plan (z,} } of J 2 counterfactuals that balances competing objectives including proximity, diversity, and validity. We next describe each cost component.
Proximity. It is reasonable to ask that each counterfactual æy should be close to the input xo that Ty is actionable. We suppose that the distance between Tg and zj can be measured using a function c: IRd x dd + RR. In general, the cost is used to capture the case of adopting the changes for a specific variable (e.g., could barely change their height or race). The proximity of plan (x.) is

---

Published as a conference paper at ICLR 2022
simply the average distance from 2g to each counterfactual in the plan. More specifically, we have
1 J vo).
Proximity((a3),,0)
(4)
Diversity. We measure the diversity of a plan using the determinant point process (Kulesza 2012)
similar the approach in Mothilal et al. (2020). The diversity is given by: Diversity (( & det(K), where Kij (1 c(z,, v1 S i.j J. Then, a plan with larger value Diversity((2;)) is more diverse.
(5)
Validity. Given the moment information (ū, E), one potential approach to compute the validity of a plan { } is to compute the value L* in (2). However, for large covariate dimension d or high number of counterfactual J, the semidefinite program (2) becomes time-consuming to solve and is not practical. This entails us to derive the a computationally efficient proxy for the validity of {zz]. Towards this goal, we use the volume of the maximum-volume ellipsoid with center J and covariance Σ that can inscribed ((x,)). Following Boyd & Vandenberghe 22004 (8.4.2), an ellipsoid with center R, covariance matrix Σ and radius r can be written in the parametric form as (p..s) (r) ( auu+h Ā f2 2 S r). The validity of the plan { is thus defined as
Validity ). Σ) & maxfr 2 0, (t))))))) S {({x)))}
The next result asserts that the above validity measure can be re-expressed in closed form, which justifies its computational efficiency.
Lemma 4.1 (Validity value). i E @(22)}), then Vali = miny p 2
Lemma 4.1 and the analysis in Proposition a.4 suggest that the counterfactual plan should satisfy h) so as to improve the validity. Similar to Section 3.1| we will impose the constraints that p Ty Vj for some margin 2 for validity purposes.
p O (my))
COPA framework.
Our COPA framework finds the counterfactual plan that minimizes the weighted sum of the proximity, the diversity and the validity measure. More precisely, the COPA counterfactual plan is the minimizer of
min Zi....3
Proximity(Iae) ((xnittty(;;; - A Validity((=;)),.
Diverrsit
(6)
S.
2
Vj
for some non-negative parameters A₁ and A2. The COPA problem 6 can be solved efficiently under mild conditions using a projected
descent algorithm.
A projected gradient descent algorithm can be used to solve the COPA problem (6). The gradient of the objective function of (6) can computed using auto-differentiation. We now discuss further the
projection operator. Let A {a E IRd, p 2 c), then the feasible set of the COPA problem (6) product space X², The projection operator Projxs on the product set X is decomposable into simpler projections onto individual set as Projx (Ha2}) = (Proi ( (zf),..., Projj..,,,P,,ee (z')), where each individual projection is
2 1 min (0. p x'J c///1A Note that the second equality above follows from the analytical formula for the Fuclidean projection onto half-space, which was previously used in Section 3.1
(z)) arg min x1112
5 NUMERICAL EXPERIMENTS
In this section, we evaluate the correctness of our validity bounds and the performance of our correc- tions and our COPA framework on both synthetic and real-world datasets. Our baseline for compari- son is the counterfactual plan constructed from the state-of-the-ar DiCE framework MMothilal al.) 2020). Throughout the experiments, we set the number of counterfactuals to J 5. For DICE, we use the default parameters recommended in the DiCE source code. The Mahalanobis correction will use the counterfactual plan obtained by the DiCE method with K = 3 and the perturbation limit A 0.1. In our COPA framework, we use Adam optimizer to implement Projected Gradient Descent and fz-distance compute perturbation cost between inputs.

---

Published as a conference paper at ICLR 2022
1.0
1.0
0.6
Vilddy
0.2
0.4
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0 0.2
0.4
0.6
0.5
100
(a) & (((x,))
(b) j. ((1x)))
Figure 3: The impact of the Gelbrich radius on the validity of a counterfactual plan. The vertical axis of each green point represents the empirical validity of the plan with respect to which ~ N/ M12 Eg) and the horizontal axis is the Gelbrich distance G( 5) (Pg. -g)))-
1.0
1.0
0.9
0.9
0.9
valddy
Validly
Validy
0.8
0.8
0.8
DICE
DICE
DICE
MahslaanoiisCn
0.7
Mahaianabiscir
0.6
MahslansbisCn
COPA
COPA
COPA
0.5
0.0
02
0.4
0.5
0.8
1.0
0.0
0.5
1.0
1.5
20
0.0
0.5
1.0
1.5
2.0
GLP py. ky)
G01 Hg.. Zg)
GGA.E P... Rg)
(a) Mean shift
(b) Covariance shift
(c) Mean & Covariance shift
Figure 4: The impact of shift magnitudes on the validity the plans obtained by three algorithms.
SYNTHETIC DATASET
We first generate 1000 samples with two-dimensional features from Gaussian distributions Mfo, Σo) and ((n, E() to create a synthetic dataset. Each instance labelled as 0 or cor- responding to the distribution that generated For the Gaussian distributions, we use similar pa- rameters as in Upadhyay et al. (2021), where μ4 = [-2, 22]
[2. _ Σo = Σi = 0.5/ with being the identity matrix. This dataset is then used to train logistic classifier with the present parameter tg. This classifier Co, is fixed for the experiments that follow.
The impact of Gelbrich radius on the validity. Given a counterfactual plan generated by DiCE on the classifier Ca., we consider two scenarios: ğ E (({x,) }) and ğ & ((xz)). We choose ğ = 6 for the case O({z,)) and ğ -0,, otherwise. We also set Σ 0.51. We then compute the lower and upper validity bound of this plan with respect to different Gelbrich bounds E [0, 1]. To evaluate the empirical validity of this plan, we simulate 1000 futures for Ó. For each future, we generate Hg and Ey randomly that G((P, Σ), (My, Eg)) S 1, and then sample 106 values of Ā (g Eg). The empirical validity of the plan for each future is the fraction of parameter samples from the future that the prescribed plan is valid. We plot the 1000 empirical validity of the plan in Figure 3 This result consistent with our guarantees that the validity is between the two bounds. We also observe that increasing p loosens the validity bounds.
The impact of degree of distribution shift on validity of plan. We explore the case fu O({2,) }), where ğ = 0g and Σ = 0.5I, to assess the impact of distribution shift to three algo- rithms DiCE, MahalanobisCrr, and COPA. In this experiment,
COPA framework with A1 = 2.0, A2 = 200.0. To assess the performance three algorithms, we parameterize the ground truth distribution of the future parameters 0 ~ N (Nng, Σn) as follows: Mg = Ý + a0 0] Egg (1 + B. Here, we simulate three types of distributional shift of the parameters 0: (1) mean shift (a E 1]. 0), (2) covariance shift (a = 0, 3 [0, 3)), and (3) mean and covariance shift ((a 8) 00 x 3)). For each shift's type, we generate 100 counterfactual plans corresponding to 100 original inputs Zy and compute the empirical validity as previously described. The aver- age and confidence range of the empirical validity are plotted in Figure 4 This result shows the tendency decreasing validity measure of all algorithms when increasing the Gelbrich distance between estimate and ground truth distribution. However, COPA shows stability and robustness for
8

---

Published as a conference paper at ICLR 2022
all shift types. The validity of DiCE deteriorates when the ground truth distribution is far from 0u- Meanwhile, MahalanobisCrr increases the robustness of the plans obtained by DiCE significantly.
5.2 REAL-WORLD DATASETS
In this experiment, we evaluate the robustness of the counterfactual plans obtained by three frame- works on the real datasets. We use three real-world datasets: German Credit (Dua & Graff) 2017, Groemping, 2019), Small Bussiness Administration (SBA) (Li et al. 2018), and Student performance (Cortez & Silva 2008). Each dataset contains two sets of data (the present data Di and the shifted data D2). The shifted dataset D2 could capture the correction shift (German credit), the temporal shift (SBA), or the geospatial shift (Student). More details for each dataset are provided in Appendix.
Experimental settings. For each present dataset D1, we train logistic classifier Co, with parameter 8 on 80% of instances of the dataset and fix this classifier to construct counterfactual plans in whole experiment. We generate 100 counterfactual plans for 100 original inputs and report the average values of our evaluation metrics. To estimate z and Σ. we train 1000 different classifiers from the present dataset D1 (each is trained on random set containing 50% instances of D1). then use the empirical mean and covariance matrix of the parameter. We set Gelbrich radius p = 0.01.
Metrics. To compute the empirical validity in the shift dataset D2, we sample 50% instances of D2 1000 times to train 1000 different logistic classifiers. We then report the empirical validity of a plan as the fraction of the classifiers with respect to which the plan is valid. We also use the lower validity bound as a metric for evaluating the robustness of a plan. We use the formula in (4p and to measure the proximity and diversity of a counterfactual plan.
Table Performance of competing algorithms on real world datasets. For Proximity, lower better. For Diversity, L and Validity, higher is better. Bold indicate the best performance for each dataset.
Dataset
Method
Proximity
Diversity
L*
Empirical Validity
Correction
DICE MahalanobisCtr
0.986 + 0.324
0.072 0.050
0.649 + 0.073
0,996 0.008
1.002 + 0.323
0.064 0.047
0.750 + 0.064
0.999 0.003
COPA (A1 0.2; 2, 2.0)
0.916 = 0.178
0.017 0.058
0.944 # 0.168
0.997 0.018
COPA (Ar 0.5; d2 5.0)
1.154 1 0.253
0.114
0.946 1 0.040
1.000 0.000
COPA (A1 1.0; A 10.0)
1.351 + 0.166
0.225 0.045
0.911 + 0.022
1.000 + 0.000
Temporal
DiCE
2.037 = 0.470
0.089 0.057
0.946 + 0.014
0.801 0.061
MahalanobisCrr
2.014 1 0.473
0.085 0.055
0.966 1 0.007
0.945 0.062
COPA (A1 = 0.2;; A- 2.0)
1.831 + 0.139
0.253 + 0.026
0.994 + 0.000
1.000 + 0.000
COPA (A1 = 0.5; 5.0)
1.966 = 0.112
0.363 + 0.012
0.995 + 0.000
1.000 + 0.000
COPA (A) = 1.0; = 10.0)
2.010 1 0.124
0,380 1 0.006
0,995 1 0.000
1.000 1 0.000
Geospatial
DiCE
1,486 = 0.325
0.136
0.044
0.549 1 0.307
0.408 0.363
MahalanobisCrr
1.497 + 0.325
0.126 0.044
0.864 + 0.117
0.757 1: 0.284
COPA (Aı = =02;; A2 2.0)
1.779 = 0.352
0.052 + 0.047
0.998 + 0.000
1.000 + 0.000
COPA (A1 - -0.5; 5.0)
1.882 1 0.353
0.089 1 0.032
0.998 1 0.000
1.000 1 0.000
COPA (A1 = 1.0; Ag = 10.0)
1.926 + 0.349
0.1 + 0.024
0.997 + 0.000
1,000 + 0.000
Results. The results in Table [ show that our COPA framework achieves the highest empirical validity, L', and diversity (especially when increasing X2) all evaluated datasets. Comparing DiCE and Mahalanobis correction, we can observe that the trade-off of proximity and diversity of Mahalanobis correction is relatively small as compared to its improvement in terms of validity.
6 CONCLUSION
This paper studies the problem of generating counterfactual plans under the distributional shift of the classifier's 's parameters given the fact that the classification model is usually updated upon the arrival of new data. We propose an uncertainty quantification tool to compute the bounds the probability of validity for given counterfactual plan, subject to uncertain model parameters. Further, we introduce a correction tool to increase the validity of the given plan. We also propose a COPA framework to construct counterfactual plan by taking the model uncertainty into consideration. The experiments demonstrate the efficiency of our methods on both synthetic and real-world datasets. Further extensions, notably incorporate nonlinearities, are presented in the appendix.

---

Published as a conference paper at ICLR 2022
REFERENCES
Ifeoma Ajunwa, Sorelle Friedler, Carlos H Scheidegger, and Suresh Venkatasubramanian. Hiring by algorithm: Predicting and preventing disparate impact. Available SSRN, 2016.
Dimitris Bertsimas and Ioana Popescu. Optimal inequalities in probability theory: A convex opti- mization approach. SIAM Journal on Optimization, 15(3):780- -044 2005.
Boyd and L. Vandenberghe. Corvex Optimization. Cambridge University Press, 2004.
Paulo Cortez and Alice Silva. Using data mining to predict secondary school student performance. Proceedings of 5th FUture BUsiness T'CChology Conference, 2008
Susanne Dandl, Christoph Molnar, Martin Binder, and Bemnd Bischl. Multi-objection counterfactual
explanations. In International Conference Parallel Problem Solving from Nature, pp. 448 469. Springer, 2020.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL BtLthtt:///acciin
ics. uci. edu/meddmml
M. Gelbrich. On formula for the L Wasserstein metric between measures on Euclidean and Hilbert spaces. Mathematische Nachrichten, 147(1):185-2033 1990.
U Groemping. South German credit data: Correcting a widely used data set. Reports in Mathematics, Physics and Chemistry, Department II, Beuth University of Applied Sciences Berlin, 2019.
Wenbo Guo, Dongliang Mu, Jun Xu, Purui Su, Gang Wang, and Xinyu Xing. Lemna: Explaining deep learning based security applications. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 364-379, 2018.
Keiiti Isii. The extrema of probability determined by generalized moments (i) bounded random variables. Annals of the Institute of Statistical Mathematics, 12(2): 19-134, 1960.
Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Mgdel-agnostic counterfactual explanations for consequential decisions. In International Conference Artificial Intelligence and Statistics, pp. 895-905. PMLR, 2020a.
Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: Definitions, formulations, solutions, and prospects. arXiv preprint arXiv:2010.04050, 2020b.
Daniel Kuhn, Peyman Mohajerin Esfahani, Viet Anh Nguyen, and Soroosh Shafierzadch-Abade Wasserstein distributionally robust optimization: Theory and applications in machine learning. INFORMS TutORials in Operations Research, pp. 130-169, 2019.
Alex Kulesza. Determinantal point processes for machine learning. Foundations and Trends in
Machine Learning. 5(2-3):123 226.1862226622 2012.
Min Li, Amy Mickel, and Stanley Taylor. "Should this loan be approved or denied?": A large dataset with class assignment guidelines. Journal of Statistics Education, 26(1):55 66, 2018.
Luigi Malagò, Luigi Montrucchio, and Giovanni Pistone. Wasserstein Riemannian geometry of Gaussian densities. Information Geometry, 1(2):137-179, 2018.
Albert W. Marshall and Ingram Olkin. Multivariate Chebyshev inequalities. The Annals of Mathe- matical Statistics, 1104)1001-1114, 1960.
Tim Miller. Contrastive explanation:
A structural-model approach.
arXiv preprint
arXiv:1811.0316. 2018
MOSEK ApS. MOSEK Optimizer API for Python 9.2. 2019. URL / com/ 9. 2/ http/yttonapp//ii..
html
Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp. 607-617, 2020.
10

---

Published as a conference paper at ICLR 2022
Viet Anh Nguyen, Nian Si, and Jose Blanchet. Robust Bayesian classification using optimistic score ratio. Proceedings of the 37th International Conference on Machine Learning 2020.
Viet Anh Nguyen, Soroosh Shafieezadeh-Abadeh, Damir Filipović, and Daniel Kuhn. Mean- covariance robust risk measurement. arXiv preprint a2X0992112.09959, 2021a.
Viet Anh Nguyen, Soroosh Shafieezadeh-Abatee Daniel Kuhn, and Peyman Mohajerin Esfahani. Bridging Bayesian and minimax mean square error estimation via Wasserstein distributionally robust optimization. Mathematics of Operations Research, 2021b.
Martin Pawelczyk. Klaus Broelemann, and Gjergji Kasneci. On counterfactual explanations under predictive multiplicity. In Conference on Uncertainty in Artificial Intelligence, pp. 809-818. PMLR, 2020.
Imre Pólik and Tamas Terlaky. A survey of the S-lemma. SIAM Review, 49(3):711-418, 2007. doi: 10.1137/500361 445044461444444444.
Kaivalya Rawal and Himabindu Lakkaraju. Beyond individualized recourse: Interpretable and in- teractive summaries actionable recourses. arXiv preprint arXiv:2009.07163 2020.
Kaivalya Rawal, Ece Kamar, and Himabindu Lakkaraju. Can i still trust you?: Understanding the
impact of distribution shifts on algorithmic recourses. arXiv preprint arXiv:201..11788, 2020.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should I trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1135-1144, 2016.
Chris Russell. Efficient search for diverse coherent explanations. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 20-28, 2019.
Naeem Siddiqi. Credit risk scorecards: Developing and implementing intelligent credit scoring. John Wiley & Sons, 2012.
Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171-176, 1958.
Bahar Taskesen, Man-Chung Yue, Jose Blanchet, Daniel Kuhn, and Viet Anh Nguyen. Sequential domain adaptation by synthesizing distributionally robust experts. In Proceedings of the 38th International Conference Machine Learning, 2021.
Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorith- mie recourse. Advances in Neural Information Processing Systems 35, 2021.
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 10-19, 2019.
Lieven Vandenberghe, Stephen Boyd, and Katherine Comanor. Generalized Chebyshev bounds via semidefinite programming. SIAM Review, 49(1):52-64, 2007.
Suresh Venkatasubramaniaan and Mark Alfano. The philosophical basis of algorithmic recourse. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp. 284-293, 2020.
Sandra Wachter, Brent Daniel Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harvard Journal of Law Technol- ogy, 2017.
Austin Waters and Risto Mikkulaanenn. Grade: Machine learning support for graduate admissions. Ai Magazine, 35(1 (664))646444 2014.
Xingyu Zhao, Wei Huang, Xiaowei Huang, Valentin Robu, and David Flynn. Baylime: Bayesian local interpretable model agnossic explanations. arXiv preprint arXiv:2012.0305. 2020.
11

---

Published as a conference paper at ICLR 2022
A PROOFS
A.1 PROOFS OF SECTION
Proof of Theorem 2.2
For any (j, Σ) E IRd $4. let
P(u, Σ) (Q: Eg [0] n, Eg Ba(00']
uu T Σ}
denote the set of probability measures under which the random vector 0 has mean μ and covariance matrix Σ. The infimum probability can be decomposed as
inf Q(+ ((z,))) QER
inf inf (H.))Eu QEP(u,E)
Q(0 ((22)))
inf inf (KEE)M
1 ΣjEt1 Aj
s.t.
A E I,, 2j ERd
Zg E Dd
Vj E [J]
- 2J 2 0,
2
3j
ビ 0
E
Σ
22 2j
3
Σ + u T
1
11
JE(J]
where the second equality follows from Vandenberghe et al. Proposition 2), we have
2007
22). By Malagó et al. 20118
min CeRexa
| 1 + Tr
[ 2c]
(²,, (7, E))
Σ
s.t.
CT
Σ
=0.
min CeRaxa
| 27
#
Tr
Σ + up + -
Σ
C
s.t. t.
CT =0.
Hence, by combing two infimum operators, we have
inf
1- Ejen X # E Rd Ee sd
s.t.
Ce Rdxd
X₂ R, 23 E Rd,
Zj E Sd
vjel
7
2 23 2 0,
0
vje
inf Q(0 ((z,)))) QEB
[
2j
E yu
/
Xg
1
JEM
2p T + Tr [ + pq + + 20] sp:
= 0.
CT
In the last step, we add an auxiliary variable M E s with the constraint M = + p4p Note that this constraint can be replaced by M > Σ + uu without affecting the optimal value of the optimization problem. Using the Schur complement, this constraint is equivalent
M - Σ 4 T 1 2.
This completes the proof.
Proof of Theorem 2.3 Let (0) be the indicator function of the set (({z))), that is,
ee {
if E (({r)), otherwise.
By defining the loss function ((0)= (e( and let Z be the convex feasible set defined by
Z 2 {=0 E R,, e Rd Z sd :00 2z 0 (2,00T) > Le(() v0 Rd).
12

---

Published as a conference paper at ICLR 2022
Notice that Z is closed and convex set because it is an intersection of uncountably many closed and convex sets. Denote the following set V of mean second moment matrices that are induced by Ut by
V - (1,, M) E R x $4 3(4, Σ) u such that (), E pp })-
The support function o3 of the set V is defined as
(1 2) sup(= a + Tr [M]] M) E
Using these notations, now have
sup Q(0 E (({z;))) QEB
sup sup (, QEP(n.
Eg[Le(0)]
(7a)
sup inf 20 2/ + Tr [ 14 )Z]
(7b)
(n.))e (zo:2.Z)Ez
sup inf 20 + 24 2 Tr MZ
(
inf sup 20 + 24 T 2 = Tr M2] (..M)E
(7c)
(x0,2,2)2
inf ² + (22, (Zo.
where equality (7a) from the two layer decomposition of the ambiguity set B. and inequality (76)
is from the Isii's duality result [sii (1960). Equality (7c) follows from the Sion's minimax theo-
rem Sion 1958) which holds because the objective function is linear each variable and because
V is compact by the compactness of U (Nguyen et al. 2021b Lemma A.6). We thus have
inf
2u rpp |AA Tr [}]]
9 Tr [Q]
s.t.
N 20 E R, E ZE S", 9 R4, Q 84
sup s(p e O(fx)))) QEB
I 7 73.1
71 Z
7p 7p+ + 2
Q
0.
1 (e(
T
9
=
20 + 2z
To
+ (2, (0
v0 E
Rd.
where the equality follows by substituting the support function V in Kuhn et al. 2019 Lemma 2). Consider the last constraint of the above optimization problem, it is easy to see that it is equiv- alent to
{
+ 22 0 + (2 T0 2g + Tx 0 (z, 08T
20 0
v0 Rd E (((x)))
1
AA
The first remi-infinite constraint is equivalent to the semidefinite constraints
z
z 0,
Σ 0.
20
sufficient condition for the second semi-infinin constraint is that
Z
DAERI
7
20
JE[J
which holds thanks to the S-lemma Pólik & Terlaky (207)) Adding these above constraints into the
optimization problem leads to the desired upper bound. This completes the proof.
The proof of Proposition 2.4 relies on the following result on the multivariate Chebyshev inequali- ties, which can be found in Marshall & Olkin (1960) and Bertsimas Popescu (2005).
Theorem A.1 (Multivariate Chebyshev inequality). Let S be a convex set, then
Q E
1
k = inf (0 - E (0- 11).
sup (~(()))))
1+
BES
We now ready prove Proposition 2.4
13

---

Published as a conference paper at ICLR 2022
Proof of Proposition 2.4 If E (((r))), }), then is clear that
inf 0
(0 -- =0
thus have U
sup
Q(0 E ((fxy))) by Theorem A.1 This leads U 1.
(~(
Consider the case when ğ & ((z2)). By the hyperplane separation theorem, there exists vector Ie such that æ TTO 2 0 for all 0 E (((x,)) and F j O. Let T & {0 Too 2 0}, then is
trivial that (({x;}) C T and that T is convex set. We now have
inf Q(0 E (({,))))
sup Q(0 & (((x)))) < Gen
1 T) = 0, QE
sup
GEB
where the penultimate equality follows from Theorem A.1 This leads to L = 0.
A.2 PROOFS SECTION 3
Notice that the optimal solution x should satisfy x T > Fix any value of + 0. Consider first the inner minimization problem of B and associate with the equality constraint Lagrangian dual variable ( E R, we have
Proof of Theorem 3.7
min (0-
T p = min max (0 - (0- T5-1(0 (1) 200
0:0 T==
OER CER
max min (0 - ( T- 2ç0
CER BERd
2 Exr +2ÇT
max CER
(x 12)2
Σx
where the second equality follows from convex duality result. The third equality follows from the fact that for every value of Ç, the optimal solution in the variable 0 is
(C) = 7 Σ..
Moreover, the last equality follows from the optimality condition in C which gives Ç* á x=xxxx Ex)). Because the optimal solution in æ should satisfy x Tu > 0, problem 3 is hence equivalent to
I A
max
Ex Ik
s.t. t.
I
AA
Adding now two auxiliary variables / R_ and v E Rdd with the constraints:
tx.
the claim in statement of the theorem now follows by a simple substitution to get
max
t. D VER
tER,, ||0 trxllz S At, v p = 1.
Swapping the maximum operator minimum operator completes the proof.
14

---

Published as a conference paper at ICLR 2022
A.3
PROOFS OF SECTION 4
Proof of Lemma 4.1
From the definition of the set O(fr;}), we have
max
max(r: & (({x))))
s.t.
sup
-(E Z5
vj
l
S. t.
- Bj
sup ||
-07
0 4j
max
s.t.
- p 2, + r 12 5
Vj.
where the last equality follows from the dual norm property. The proof now follows by finding the maximum value of that the problem feasible.
B EXPERIMENTS
B.1 EXPERIMENTAL DETAIL.
Real-world datasets Here, we provide more detail about the three real-world datasets we used. Source code can be found at
i German Credit (Dua & Graffi 2017). The dataset contains the information (e.g. age, gender, financial status....) of 1000 customers who took loan from bank. The classification task is to determine the risk (good or bad) of an individual. There is another version of this dataset regarding corrections of coding error (Groemping, 2019). We use the corrected version of this dataset as shifted data to capture the correction shift. The features we used in this dataset include 'duration', 'amount', 'personal_statuss statusssetx_" and 'age".
Small Bussiness Administration (SBA) (Li et 2018). This data includes 2,102 observations with historical data of small business loan approvals from 1987 to 2014. We divide this dataset
into datasets (one instances from 1989 2006 and one is instances from 2006 2014) to capture temporal shift. We use the following features: selected, "Term', 'NoEmp', 'CreateJob', 'RetainedJob', 'UrbanRural', 'ChgOffPrinGr', 'GrAppv', 'SBA' 'New", 'RealEstate', 'Portion', 'Recession'.
ii Student performance (Cortez & Silva 2008). This data includes the performance records of 649 students two schools: Gabriel Pereira (GP) and Mousinho Silveira (MS). The classification task is to determine if their final score is above average or not. We split this dataset into two sets in two schools capture geospatial shift. The features we used are: 'age', 'Medu', 'Fedu', 'studytime", 'famsup", 'higher', 'internet', 'romantic", 'freetime", 'goout', 'health', 'absences', 'G1', 'G2'.
Classifier Throughout this paper, layer MLP with 20, 50, 20 nodes and ReLU activation in each consecutive layer as the nonlinear classifier. We use one-hot encoding for categorical features in the datasets to convert it to vector of [0, 1]. We use min-max normalization to scale the numerical features to [0, I]. We report the performance of the classifiers in three real-world datasets in Table
Logistic Regression for linear classifier and three-
B.2 ADDITIONAL EXPERIMENTS
The impact of degree of distribution shift on validity of a plan. We provide an additional ex- periment in different covariance shift E.g = (1 + A)A A this experiment, we choose A as:
A 1 -1 0
0
The matrix introduces both positive and negative correlations between the classifier's parameters. Other settings are set the the experiment in Section 5.1
15

---

Published as a conference paper at ICLR 2022
Table 2: Performance of the underlying classifiers.
Logistic Regression Accuracy
Neural Network
AUC
Accuracy
AUC
German
0.71 0.01
0.64 0.02
0.68 + 0.02
0.62 + 0.02
Shifted German
0.71 + 0.01
0.64 + 0.02
0.68 + 0.02
0.62 + 0.02
SBA
0.71 + 0.02
0.86 166+00000 0.02
0.90
0.99 + 0.01
Shifted SBA
0.87 0.01
0.97 0.00
0.98 1.01
Student
0.83 = 0.02
0.91 0.02
0.8
0.00
Shifted Student
0.87 0.03
0.93 0.03
0.90 0.03
0.96
1.0
1.0
0.9
0.9
Validity
Validity
0.8
DICE
0.7
DICE
0.7
MahalanobisQr
0.6
MahalanobisCrr
COPA
COPA
0.5
1.0
1.5
2.0
2.5
1.0
1.5
2.0 o(ū ε, Ug. Eg)
2.5
G(ū, Ê, Ug. Σg)
(a) Covariance shift
(b) Mean & Covariance shift
Figure The impact of shift magnitudes on the validity the plans obtained by three algorithms.
Mahalanobis correction on real-world datasets. In this experiment, we evaluate the Maha- lanobis correction different number of corrections K and different perturbation limit A. We set p 0.01, c 0.1, K E (O...., J), J J A [0.05, 0.35). (7, is estimated using similar manner as in Section 5.2 of the main paper. The results in shown in Figure
Counterfactual explanations for real-world datasets. To illustrate the use case of the counter-
factual explanations, provide examples the German dataset with J 3 (Table 3 in which we consider the "personal status and sex" feature as immutable. Here, we can observe that three algorithms could provide diverse sets of counterfactuals that the users may prefer. However, by providing better empirical validity. the plans generated by MahalanobisCrr and COPA are more robust with distribution shift than DiCE (generated without considering the shift).
C EXTENSION TO NONLINEAR CLASSIFIERS
In the main paper, our analysis is based on the linearity in both features and model parameters. We now discuss two extensions of our COPA framework the nonlinear settings.
C.I NONLINEARITY IN INPUT FEATURES
This section extends to any linear classifier (x) if
if ((x) 2 0, and otherwise, where ø X' " is (possibly nonlinear) feature mapping that maps input features to latent representation in a covariate space gd Note that our bounds in Section (tilll hold in latent space IR for a concrete example, Theorem 2.2 holds with x, being replaced by (xx
16

---

Published as a conference paper at ICLR 2022
Diveristy
Proximity
0.1, varying
3, varying
0.135
1.015
0.130
Coraction
0.3
0.125
Divertoy
1.010
Prosiiity
0.120
0.116
1.005
0.1
0.110
0.951
0.0035
1.94
Temponal
Diveristy
Proxiity
0.980
1.82
0.999
0.0025
1.515
0.14
Divoristy
1.540
Prosimity
Ceospelial
0.4
1.625
1.520
2
3
0.05
0.10
0.15
0.20
0.25
0.30
0.35
K
Figure 6: Evaluation of Mahalanobis correction on the real-world datasets. We fix = 0.1, evaluate the effect of the number of correction the lower validity bound, diversity, and proximity (left column). We fix 3, evaluate the effect of the perturbation limit on the lower validity bound, diversity, and proximity (right column).
The COPA framework is also extendable to incorporate the feature map ø. Assuming that & is differentiable, the COPA framework solves the following optimization problem:
Proximity((z;)).a) + A, Validity((6(x;)).) E) DeDieersity((z.)) ((x)))
min 21on0
8. t.
nT,z2e
Vj.
The proximity and diversity measured in the input space and the validity term is measured in latent space instead. This optimization problem can be solved efficiently by projected gradient descent algorithm similar to Section
C.2 NONLINEARITY MODEL'S PARAMETERS
Similar to the prior works (Ustun al. 2019 Rawal & Lakkaraju 2020 Upadhyay al. 2021 l,,
work can adapt to nonlinear classifiers C,rl using a local surrogate models such as LIME (Ribeiro et al. 2016). LIME (Ribeiro et al. 2016) is popular technique for explaining predictions of black- box machine learning models. The main idea of LIME is to train a local surrogate model C on perturbed samples around given input instance zp approximate the local decision boundary of the black-box models. We thus model the uncertainty of parameters for To instead the parameters of C,t-
the surrogate model (%0
For the experiment, we first generate a local linear model 6 using LIME method with 5000 per- turbed samples. We then choose (7, 5.) (0,0.00 0.05/,), where T is identity matrix, model the
17

---

Published as a conference paper at ICLR 2022
Duration
Credit amount
Personal status
Age
L
Empirical Validity
Instance DiCE
30.0
4249.0
A94
28.0
49.4
596.4
28.0
0.00
0.005
72.0
4330.2
28.0
59.7
13776.4
28.0
MahalanobissIr
42.5
69.8
30.0
0.15
0.802
40.8
1153.9
30.0
27.4
10047.3
30.0
CОРA
4.0
18424.0
28.0
0.11
0.797
72.0
9410.3
28.0
40.3
250.0
28.0
Instance
42.0
7174.0
A92
30.0
DiCE
250.0
30.0
0.38
0.88
4.0
7167.4
30.0
13.4
13386.8
30.0
MahalanobisCrr
7,9
523.7
33.0
0.61
0.968
3.6
5500.1
32.0
9.1
12234.5
32.0
CОРA
4.0
3884.7
30.0
0.88
1.000
16.3
3280.8
30.0
15.5
250.0
30.0
Instance
24.0
4526.0
A93
74.0
DiCE
72.0
2165.7
74.0
0.00
0.080
72.0
9907.4
74.0
72.0
18424.0
74.0
MahalanobisCri
62.1
1766.4
75.0
0.01
0.614
55.6
8881.0
75.0
48.8
16680.9
75.0
CÓPA
4.0
250.0
74.0
6.59
0.997
44.8
3070.5
74.0
4.0
18424.0
74.0
Table Counterfactual examples on German dataset.
distributional uncertainty the parameters. Similar to Section 5.2 we set Gelbrich radius p is to 0.01, J = 5, = 3.
Table Performance of competing algorithms on nonlinear classifiers. The current validity the validity of counterfactual plan with respect to the current nonlinear classifier Cua (i.e., the fraction of instances that the generated counterfactual plan is feasible).
Method
Proximity
Diversity
Empirrcall Validity
Current Validity
Correction
D:CE
0.515
0.204
0.043 1 0.037
0.005
0.041
0.414 : 0.238
0.990
MahalanohisCrr
0.595
0.210
0.035
0.035
0.021
0.058
0.409
0.313
0.670
COPA (A1 A. 1.0)
0.219 0.183
0,001
0.011
0.065
0.088
0.556
0.331
0.560
COPA (A, 0.1:
2.0)
0.432
0.403
0.100
0.1116
0.049
0.093
0.301
0.341
0.270
COPA (A1 0.2; 2.0)
0.673 0.314
0.162 0.084
0.038
0.097
0.125
0.16
0.040
Temporal
DiCE
1.573 + 0.451
0.107 + 0.071
0.637
0.350
n,852 4 0.270
1.MI0
MahalanobisCrr
1,567 0.449
+ 0.118
1,000
COPA (A1 = 0.1; 1.0)
1,88 0,540
0.002 + 0.008
0.981 + 0.014
LIM00
+ 0.000
L,MI0
COPA (A, 0.1: 2.0)
0.408
0.247 0.976 0.043
0.000
COPA (A, 0.2. 2.0)
1.447 0.340
0.990 0.004
1.000 = 0.000
1,000
Goospatial
DiCE
1,576 = 0,349
0.175
0.022 0.046
0.328 = 0.303
1,000
MahalanebisCrr
0.169 0.071
0.689 0.280
1.000
COPA (A, = 0,1, = 1.0)
1.342 = 0.367
0.000 - 0.000
0.011
+ 0.007
0,384 = 0.310
0.710
COPA (),
20)
0.210
0.750
COPA (A, = 0.2; 2.0)
1.637 1 0.284
0.287 1 0.017
0.164 1 0.066
0.679 1 0.274
1.000
We report the performance of three algorithms on the MLP classifier in the real-world datasets
in Table 4 The result is promising since the proposed COPA increase the empirical validity
18

---

Published as a conference paper at ICLR 2022
significantly. However, the infidelity of LIME could lead to invalid counterfactual explanations, represented by a lower current validity value. The low current validity is also observed in the lit- erature, see [Upadhyay et al. (202T). For further investigation, model that provides a better approximation of the decision boundary (e.g.. BayL.MME (Zhao et al, (0200). Another direction is boundary as in Guo et al. (2018). However, advocating for the mixture of linear models requires further analysis.
can another local surrogate
mixture linear regression model approximate the decision
19


Reviews:
[{"review_id": "t6FJcEWI9ly", "reviewer": "Reviewer_A84V", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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).\n\nSporadic (hopefully actionable) feedback and comments below\n* [Sec 1, par 1] \"Contrastive\" explanations were first introduced by Tim Miller [A]\n* [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)\n* [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).\n* [Sec 1, par 5] the two examples seem identical: change in demographic population and covariate distribution\n* [Sec 1, par 6] remove \"easily\", and cite [B]\n* [Sec 1, def 1.1] what is the difference between \"feasibility\" and \"validity?\"\n* [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.\n* [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?\n* [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}$?\n* [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.\n* [Sec 2] under what conditions is $\\Theta$ (not) empty?\n* [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)$\n* [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?\n* [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.\n* [Sec 3] abuse of notation in $\\Theta({x_j})$\n* [Sec 3] $\\lambda_j^\\star$ undefined\n* [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.\n* [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?\n\n\n[A] \"Contrastive Explanation: A Structural-Model Approach\", Miller, 2018\n[B] \"The philosophical basis of algorithmic recourse\", Venkatasubramanian & Alfano, 2020\n[C] \"On Counterfactual Explanations under Predictive Multiplicity\", Pawelczyk et al., 2020", "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.", "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).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "d8zVONQ5rnG", "reviewer": "Reviewer_qAnf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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. \nThe 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.\nThe 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.\nNumerical 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.\n\nNevertheless, a few remarks / questions remain. \n\n1. 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.\n\nIf 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.\n\n2. 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?\n\n3. 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.\n\nMinor comments:\np1,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\n\np2, Gen.setup: counterfactual plan stated as ‘increase relative to current value’ or ‘get at least this absolute value’? \nalso: typo ‘explainaition’\np3,Def1: calling it ‘joint feasibility’ suggests it is more than what it is (simply ‘all plans should be feasible’)\np4,Thm2: discuss how to interpret the role of z_j in Thm 2.2\n-\np5,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.\np6, 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.\np7, eq(6): it seems a ‘diversity’ got mixed up with a ‘validity’ component here\np9, 5.2+closing remark: this is too compact; also it would be good to assess how useful users perceive the resulting output to be\n", "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.\n", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-shqmRZDyCd", "reviewer": "Reviewer_pA7G", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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? \n\nMoreover, 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?\n\nOne more question: How difficult can these results be extended to the nonlinear scenario, since in most cases, the predictive model should be nonlinear?\n\nMinor issue: The conclusion section is missing. It would be better to have it. \n\nPost-rebuttal:\n\nThank 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_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. \n", "summary_of_the_review": "Interesting problem and solid results, but the assumptions (linear classifications) are very strong", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)