Global Counterfactual Explanations Are Reliable Or Efficient, But Not Both
Authors: Dan Ley
Saumitra Mishra
Daniele Magazzeni
Venue: Submitted to ICLR 2023 (2023)
Keywords: Global
counterfactual
explanations
recourse
fairness
efficiency
reliability
black box

Abstract: Counterfactual explanations have been widely studied in explainability, with a range of application dependent methods emerging in fairness, recourse and model understanding. The major shortcoming associated with these methods, however, is their inability to provide explanations beyond the local or instance-level. While many works touch upon the notion of a global explanation, typically suggesting to aggregate masses of local explanations in the hope of ascertaining global properties, few provide frameworks that are both reliable and computationally tractable. Meanwhile, practitioners are requesting more efficient and interactive explainability tools. We take this opportunity to investigate existing methods, improving the efficiency of Actionable Recourse Summaries (AReS), one of the only known global recourse frameworks, and proposing Global & Efficient Counterfactual Explanations (GLOBE-CE), a novel and flexible framework that tackles the scalability issues associated with current state-of-the-art, particularly on higher dimensional datasets and in the presence of continuous features. Furthermore, we provide a unique mathematical analysis of categorical feature translations, utilising it in our method. Experimental evaluation with real world datasets and user studies verify the speed, reliability and interpretability improvements of our framework.

Under review as a conference paper at ICLR 2023
GLOBAL COUNTERFACTUAL EXPLANATIONS ARE RELIABLE OR EFFICIENT, BUT NOT BOTH
Anonymous authors Paper under double-blind review
ABSTRACT
Counterfactual explanations have been widely studied in explainability, with a range of application dependent methods emerging in faimess, recourse and model understanding. The major shortcoming associated with these methods, however, is their inability to provide explanations beyond the local or instance-level. While many works touch upon the notion of a global explanation, typically suggesting aggregate masses of local explanations in the hope of ascertaining global proper- ties, few provide frameworks that are both reliable and computationally tractable. Mcanwhile, practitioners are requesting more efficient and interactive explain- ability tools. We take this opportunity to investigate existing methods, improving the efficiency of Actionable Recourse Summaries (AReS), one of the only known global recourse frameworks, and proposing Global & Efficient Counterfactual Ex- planations (GLOBE-CE), novel and flexible framework that tackles the scalabil- ity issues associated with current state-of-the-arr, particularly on higher dimen- sional datasets and in the presence of continuous features. Furthermore, we pro- vide a unique mathematical analysis of categorical feature translations, utilising it in our method. Experimental evaluation with real world datasets and user studies verify the speed, reliability and interpretability improvements of our framework.
INTRODUCTION
Counterfactual explanations (CEs) construct input perturbations that result in desired predictions from machine learning (ML) models (Verma et al. 2020; Karimi et al. 2020: Stepin et al.) 2021) key benefit of these explanations is their ability to offer recourse to affected individuals in cer- tain settings (e.g., automated credit decisioning). Recent years have witnessed surge of subsequent research, identifying desirable properties of CÉs (Wachter et al. 2018 Barocas al., 2020 Venkata- subramanian & Alfano] 2020), developing the methods to model those properties (Poyladzi et al, 2020 Ustun et al.] 2019 Mothilal et al. 2020; Pawelczyk et al. (022]) and understanding the weak- nesses and vulnerabilities of the proposed methods (Dominguez-Olmeet et al.) 2021 Slack et al. 2021 Uadhyay et al. 2021; Pawelczyk et al. 2022). Importantly, however, the research efforts thus far have largely centered around local ysis, generating explanations for individual inputs.
model behaviour the instance-level, though it is seldom obvious that any of the resulting insights would generalise globally. For example, a local CE may suggest that a model is not biased against protected attribute (c.g., race, gender), despite net biases existing. A potential way to gain such insights is to aggregate local explanations (Lundherg et al. 2020 Pedreschi al.) 2019 Gao et al. 2021). but since the generation of CEs is generally computationally expensive, it is not evident that such approach would scale well or lead to reliable conclusions about model's behaviour. Be it during training or post-hoc evaluation, global understanding ought to underpin the development of ML models prior to deployment, and reliability and efficiency play important roles therein. We seek to address this in the context of global counterfactual explanations (GCEs).
Such analyses
1.1 CONTRIBUTIONS: INVESTIGATIONS, IMPLEMENTATIONS & IMPROVEMENTS
Given the current lack of a precise definition, we posit in this work that a GCE should apply to multi- ple inputs simultaneously, while maximising accuracy across such inputs. For clarity, we distinguish counterfactuals (the altered inputs) from counterfactual explanations (the extension of counterfactu- als to any of their possible representations, e.g., translation vectors, rules denoting fixed values, etc.).
Investigations Section 2 summarises GCE research, introducing the recent Actionable Recourse Summaries (AReS) framework in Rawal & Lakkaraju| (2020). We then discuss motivations, defining reliability and justifying our claim that current GCE methods reliable efficient, but not both.

---

Under review as a conference paper at ICLR 2023
Scaled Translations k6
Blas Assessment via Recourse Cost Comparisons between Subgroups
Accuracy-Cost Profiles Per Subgroup
Minimum Costs Per Subgroup
GLOBE-CE, (G coss square lenckets)
100%
10C
Fore grtigriiaa---- Falie Form anitir Thue
250-
fandg Wikeha - fube
Namiing (A12))
tonogrtburkr Tiue Cast 0.5331
NedfocttoBoeeeeggllttte 0.30 (200]
Accuracy
150
[Moss 6.155)
WorkeeeWirrerr
100
Nurning)
20
50-
Nanting Lesteeetts
SndfoettooRooeeigggigi (0.00)
[Meux 6.531]
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.5
1.0
1.5
2.0
Trankation Vectors
Avarage Cost
Minimum Cost
Figure/ 1: Left: GLOBE-CE scaled translations. We argue that, while many translation directions cannot be interpreted, we can optimise GCEs by allowing variable magnitudes per input. Right: Example comparisons with synthetic Foreign Worker subgroups. Left to right: Accuracy-cost trade-off's (covering more inputs requires larger magnitudes), minimum costs per input, and the mean translation direction for each subgroup.
Our Framework Section 3 proceeds to introduce our framework Global & Efficient Counter- factual Explanations (GLOBE-CE). Though not strictly bound to recourse, our framework has the ability, as in AReS, to seek answers to the big picture questions regarding a model's recourses (Figure D. namely the potential disparities between affected subgroups, i.e. Do race or gender biases exist in the recourses of a model? Can we reliably convey these in an interpretable manner?
Our major contribution is shift in paradigm; all research so far assumes GCEs to be fixed. We rep- resent each GCE with a fixed translation vector 8, multiplied by an input-dependent, scalar variable k (Figure D To determine the direction of each translation, our framework deploys a general CE generation scheme, flexible to various desiderata. These include but are not limited to sparsity, di- versity, actionability and model-specific CEs (Section 2.1 However, the novelty of our method lies mainly in a) varying l input-wiss wise and b) proving that arbitrary translations on one-hot encodings can be expressed using If/Then rules. To the best of our knowledge, this is the first work that addresses mathematically the direct addition of translation vectors to one-hot encodings in the context of CEs.
AReS Implementations Section subsequently outlines our AReS and Fast AReS implementa- tions, where in the latter we propose amendments to the algorithm and demonstrate that these lead to significant speed and performance improvements on four benchmarked financial datasets. Both implementations are thereafter utilised as baselines in the experimental evaluation of GLOBE-CE.
Improvements Section 5) evaluuates the efficacy of our Fast AReS and GLOBE-CE frameworks along three fundamental dimensions: accuracy (the percentage of inputs with successfully altered predictions), average cost (the difficulty associated with executing successful GCEs) and speed (the time spent computing GCEs). We argue that GCEs that fail to attain maximum accuracy or minimum cost can be mislcading, raising concerns around the safety of ML models vetted by such explana- tions. We target these metrics, demonstrating significant speedups at concurrently higher accuracies and lower costs. User studies comprising MI. practitioniss additionally demonstrate the ability of the GLOBE-CE framework to more reliably detect recourse biases where previous methods fall short.
2 RELATED WORK: GLOBAL COUNTERFACTUAL EXPLANATIONS
2.1 LOCAL COUNTERFACTUS EXPLANATIONS: INSTANCE- MODEL INSIGHTS
Wachter et (2118) is one of the earliest introductions of CEs in the context of understanding black box ML models, defining CEs as points close to the query input (w.rt. some distance metric) that result in desired prediction. This inspired several follow-up works proposing desirable properties of CEs and presenting approaches to generate them. Mothilal al. (2020) argues the importance of diversity, while other approaches aim to generate plausible CEs by considering proximity to the data manifold (Poyiadzi et al. 2020 Van Looveren & Klaise| 2021 K Kanamori et al. 2020) by account- ing for causal relations among input features (Mahajan et al. 2019). Actionability of recourse an- other important desideratum, suggesting certain features be excluded or limited (Ustun et al.] 2019). In another direction, some works generate CEs for specific model categories, such tree-based (Lu- cic et al.) [022] Tolomei et al.] [217]] (017],.Pama Parmentier & Vidal (202I) or differentiable (Dhurandhar et al. 2018) models. Detailed surveys on CEs naturally follow (Karimi et al.) 2020 Verma et al. 2020)
2

---

Under review as a conference paper at ICLR 2023
2.2 BEYOND LOCAL COUNTERFACTURE EXPLANATIONS: THE CURSE OF GLOBALITY
Despite a growing desire from practitioners for global explanation methods that provide summaries of model behaviour (Lakkaraju et al., 2022), the struggles associated with summarising complex, high-dimensional models globally is yet to be comprehensively solved. Some manner of local explanation aggregation has been suggested (Lundberg et al.) 2020; Pedreschi et al. 2019 Gao et al. 202T), though no compelling results have been shown that are both rehable and computa- tionally tractable for GCEs specifically. Lakkaraju et al. (2022) also indicates a desire for more interactivity with explanation tools, alongside reliable global summaries, but these desiderata can- not be paired until the efficiency issues associated with global methods are addressed in research.
Such works have been few and far between. Both Plumb et al. (2020) and Ley et al. (2022) have sought global translations which transform inputs within one group to another desired target group, though neither accommodate categorical features. Meanwhile, Beeker et al. (021) provides an orig- inal method, yet openly struggles with scalability, Gupta et al. (2019) attempts to equalize recourse across subgroups during model training. but with no explicit framework for global interpretation. Rawal & Lakkaraju (2000) proposes AReS, a comprehensive GCE framework which builds on pre- vious work in (Lakkaraju et al. 2019). AReS adopts an interpretable structure, termed two level recourse sets. We defer details of our AReS implementation, improvements included, to Section 4 To our knowledge, only AReS and recent adaptation CET (Kanamori et al. 2022) pursue GCEs for recourse, yet the latter reports runtimes in excess of three hours for both methods. Since our goal is to provide practitioners with fast and reliable global summaries, potentially at each iteration of model training (Gupta et al. 2019), we must take steps to bridge the gap between reliability and efficiency.
2.3 MOTIVATION: GLOBAL CES ARE RELIABLE OR EFFICIENT, BUT NoT BOTH
Reliability In this work, we define reliable GCEs to be those that can be used to draw accurate conclusions of a model's behaviour. For instance, model with higher recourse costs for subgroup A than subgroup B is said to exhibit a recourse bias against subgroup A, and reliable GCEs would yield the minimum costs of recourse for either subgroup, such that this bias could be identified. are sub-optimal, or GCEs only apply to small number of points (sub-optimal accuracy), the wrong conclusions might be drawn, as in GCEs A, B, of Figure 2 In the absence of minimum cost recourses, biases may be de- tected where not present (Ai, B1) or not detected where present (A2, B2). Similarly, without sufficient accuracy, the same phenomena may occur (Ag, B3 and A1, B4, re- spectively). The further these metrics stray from optimal, the less likely any potential subgroup comparisons being reliable. We argue that maximising reliability thus amounts to maximising accuracy while minimising re- course costs. The wider scope of reliability may encom- pass other desiderata as outlined in Section [.1] though refer their impact on bias assessment to future work.
Sub-Optimal Cost
Sub-Optimal Accuracy
the costs found
Aa
No Bias
Ba
Ag
A4
Dias
B2
B4
of
Figure 2: Common pitfalls with wnreliable bias assessment (&2 distance represents cost) for GCEs A.. B,. Light dotted lines: inputs from subgroups and Dark dotted lines: inputs for which the respective GCEs apply.
Efficiency There exists gap in GCE research between reliability and efficiency. Even the most comprehensive works that target maximum reliability (Rawal & Lakkaraju 2020; Kanamori et al., 2022) suffer computation times in excess of three hours on relatively small datasets such as German Credit (Dua & Graff, 2019). In parallel, there exists a body of research advocating strongly the use of inherently interpretable models for these cases, where performance is not compromised (Rudin) 2019 Rudin Radin, 2019 Chen et al., 2018). The utility in black box explanations thus mainly reserved for higher complexity scenarios, and we must seek global method that both executes efficiently and scales well, criteria by which current works have fallen short. In experiments, define efficiency in relation to the average CPU time taken in computing GCE explanations.
OUR FRAMEWORK: GLOBAL & EFFICIENT CES (GLOBE-CE)
We proceed to detail our proposed GLOBE-CE framework, where discuss below: 1) the repre- sentation of GCEs that we choose, assisted by theoretical results on categorical feature arithmetic, 2) the GLOBE-CE algorithm, and 3) the adaptability of our framework to existing CE desiderata.
3

---

Under review as a conference paper at ICLR 2023
Negatively Predicted Inputs x
Fixed Cost Sampling G
Optimal Accuracy Translation
Scaled Translations kys
Ecarpit Gond dace peonthe
Pouuttee etiens Or gial ingurs
Optinal Translation, 8 Scaled Input, Agt
Nandarrly samp strecson a aod cou
181% Acc
UNosswr Recourse Por vost
54N Accuracy
Occisor
100% Reetag cost Thss vongl
Figure 3: The GLOBE-CE framework (Algorithm for specific G. Cost is E2 distance. Left: Negative predictions, X. Left Center: Fixed cost sampling, G. Right Center: Highest accuracy á selection. Right: Scaling 5 per input. Theorems [ and 2 are essential in bridging the gap between scaling translations and the discontinuous nature of categorical features. Future work may consider scaling translations to a fixed end-point.
3.1 OUR GCE R SCALED TRANSLATION VECTORS
We propose novel, interpretable GCE representation: scaled translation vectors, depicted in Figures [ and 3 Simply put, for inputs that belong to particular subgroup z E Xus., we can apply translation 5 with scalar l such that Tcr round(æ + kō) is successful counterfac- tual. Note that round(z) (z) re-encodes one-hot outputs by selecting the largest feature values post- translation. For each I E Nauh. our framework computes the respective minimum value of k required for recourse. The main appeal of this approach is its improvement with respect to the interpretability- perfoittt--pooooancce trade-off that other methods suffer from. Using too few translations limits the performance of previous methods, yet large numbers of GCEs cannot easily be inter- preted. For instance, Figure 3 demonstrates conceptually how one can achieve maximum accuracy with a single translation at comparably lower average costs to previous methods which do not utilise variable magnitudes (Section 2.3 details why this is absolutely necessary for reliable bias assess- ment). While one can interpret a range of scalars relatively easily (Section (32)) one cannot simply interpret a whole range of separate directions, and therein lies the paradigm shift that we propose.
We posit that our method of a) assigning a single vector direction to entire subgroup of in- puts, b) travelling along this vector, and c) analysing the minimum costs required for success- ful recourses per input of the subgroup, is the natural global extension to one of the simplest forms of local CE: the fixed magnitude translation.
fact, the connection between local and global explanations may be more intimate than current research implies. Works suggesting to learn global summaries from local explanations (Pedreschi et al., 2019 Lundberg et al.) [2200] Gao ct al. 2021) and approaches suggesting to learn global summaries directly (Rawal & Lakkaraju 2020 Kanamori et al. 2022; Plumb et al. 2020 Ley et al.) 2022) tend to approach global ex-
planations from the angle that they are fundamentally different problems. Our framing of GCEs as a local problem is akin to treating groups of inputs as single instances, generating transla- tions for them and subsequently, through scaling, efficiently capturing the true range of prop- erties across the set of local instances and their proximity to the decision boundary (Figure 3
Unlike prior work, this implies that we can tackle a wide range of minimum costs, and potentially complex, non-linear decision boundaries, despite a fixed direction 5. AReS (Rawal & Lakkaraju 2020) and recent similar work Counterfactual Explanation Trees (CET) (Kanamori et al.) 2022 do not propose any such scaling techniques. The latter indicates the accuracy to cost trade-off that occurs when one is limited by fixed translation, yet eventually compromises for one. Other translation works (Plumb al. [2020] Ley et al., (022) do not utilise any form of scaling, nor do they provide steps to handle categorical features, an issue we address below. These approaches can also be prone unreliability since they target training data rather than model's decision boundary.
Categorical Feature Arithmetic We assume one-hot encodings (else, these can be trivially en- coded and decoded to suit) and provide, to the best of our knowledge, the first work in the context of CEs that reports mathematically the interpretation of translation kö on a one-hot encoding, including the effects of scaling, yielding deterministic, interpretable rules from kō. For examples of the interpretable rules sets generated by categorical translations, see Table [ and Appendix B.2
Theorem 1. Regardless of feature value, any translation vector that is added to one-hot categor- ical feature can alternatively be expressed using If/Then rules, with just one unique Then condition.
4

---

Under review as a conference paper at ICLR 2023
Proof (Sketch). Consider any one-hot encoded feature vector with feature labels ranging from 1 to n, denoted f [2,.,.... [m]
E {0, 1 ". where |/I = and = arg max; Ji. Similarly, consider a translation vector of size n, denoted 5 = [61, 62...., 6n] E R", where A = arg max, 6, The final vector post- post-translation is g = f + 5, and the final feature value is G = arg max; 9t. Note F = 6; and OF = 5y + 1. We denote 9G = max; 9; = max(0p + 1, m (o.)). For 1 < F S n. we now prove that if G + F (i.e. a change in feature value occurs), we have the rule "If F, Then A" In the case F = A. 9G = max م사 + 1, max; ( ())+4)) = 5Λ + +1, as مو = max; 65. Hence, G = A (no rule). In the case F * A. 9G max(8p + 1, If 6p +1> d2, then 9G 65 + 1 and G F
(no rule). However, or + < òΛ, then 9G = da and G = A. giving the rule "If F. Then A" O Theorem 2. Regardless of feature value, any translation vector that is scaled by k 2 0 and added to a one-hot categorical feature can alternatively be expressed with the first m rules of a sequence.
Proof (Sketch). Consider the general vectors f and ā defined in Theorem T and scalar k. For i + A and k 0, Theorem that kō, +1 < kōg yields the rule iIf Then " Rearranging gives that if the lower bound k > oس is satisfied, then the translation kō induces such a rule. Consider ad- ditionally the vector of lower bounds k- [K1, -i,,,,...,h kip] E RT. where kizs
-5, and RiS- cc. Lemma 2.1. By inspection, we have that K; S. for any i.m < n. pair with 6, S. dm. As such, lower bounds for i and m are both satisfied if > km- Thus, scaling 5 by k > kim induces not only the rule corresponding to feature value m, but also that of any other feature value with d; S 8m.
For k- = 0, we have no rules (k:6 = 0). Let A now be the index of the 1th smallest value in 5, such that A arg min, 8; and An, = arg max; 8; = A. Thus, by Lemma 2.1 for m < n, we have that scaling 8 by kan. < k S kAm+1 induces rules for each of the first m feature values A Aisism
3.2 THE GLOBE- CE ALGORITHM: LEARNING AND INTERPRETING TRANSLATIONS
Any particular CE may be represented with fixed magnitude translation. The major contribution of the GLOBE-CE framework lies in the notion of scaling the magnitudes of translations. Though per- haps an uninteresting concept in the context of local CEs, when large numbers of inputs are present, scaling a translation 8 with imput-dependent variable ic is an elegant and efficient way of solving for global summaries of a model's ' decision boundary. Figure SquureBdepin deepicts the utility that a single, scaled translation vector can exhibit. One can interpret a range of magnitudes, though cannot interpret a range of directions so easily, and previous approaches relied on using a small number of fixed GCEs.
Learning Translations In our setup, we learn ex- planations by adopting methods from instance- level CE research, generalising for any CE al- gorithm G(B, X, n2) that considers, at mini- mum, the model B being explained, the inputs requiring explanations X, and the number n of returned GCEs 02 62.22.... ..., In = A. This en- ables previous CE research to simply be extended when seeking global explanations; we show in Section 3.3 how previous method (constrained random sampling) can be adapted for our pur- poses. GLOBE-CE then scales the 7th GCE 8, over a range of m scalars k = ki, K2, ... kim turning the counterfactuals X", the predictions y"
Algorithm 1: Flexible GLOBE-CE Framework
Inputs: B, X., G. n, & cost & Generate GCEs (Translations) For all GCEs > For all Scalars Counterfactuals
I: A = G(B,
2: for 1 S < do
3: for I 1 [k] do
4:
X, round(X k2
5:
, = B(X))
& Predictions
6:
C.j (o,
Costs
7: end for
8: end for
Outputs: Counterfactuals X", Predictions V" Costs (For all Inputs X, Translations A and Scalars k))
repeating over all 1 S i < n GCBs and re- E {0, (0, and costs C R220
In practice, one could set an upper limit of for the maximum number of GCEs end users are willing or able to interpret. Algorithm [ could then be terminated when accuracies and costs plateau, or n is reached. Scalars & are chosen in a similar fashion, with an upper limit on the cost of GCEs i.c. such that l simply ranges linearly from 0 to point that yields this limit. This may vary per translation, a property not captured here, though one that is easily imple- mentable. Given the speed of our method (Section 5). we found m 1000 to be appropriate. For categorical features, scalars exhibit certain properties that can be manipulated (Theorem 2)
Interpreting Translations The manner in which explanations are portrayed depends on the nature of the data and/or the desire to compare recourses. We introduce straightforward interpretations of GCEs in continuous and categorical contexts, alongside the corresponding accuracy/cost properties.
5

---

Under review as a conference paper at ICLR 2023
New Inputs
All Inputs
(eature(s)
New Rule Added
Accuracy
Cost
Accuracy
Cost
Account Status
If F2, Then F4
+33.5%
1.00
33.5%
1.00
Account Status
If F3, Then R4
+2.5%
1.00
36.0%
1.00
Account Status
If FI, Then F4
+45.2%
1.00
81.2%
1.00
Telephone
F2, Then Fl
+2.5%
1.80
83.7%
1.02
Employment
If Not F4, Then F4
+10.2%
1.95
93.9%
1.12
Table 1: Example Cumulative Rules Chart (CRC) for categorical features, representing the optimal GLOBE- CE translation at scalars. Rules are cumulatively added, resulting in an increase accuracies and costs.
Our scaling approach induces accwrac--cost profiles as pictured in Figure I Left Centre, providing an interpretable method for the selection of particular accuracy/cost combination, as well as for bias assessment, Intuitively, if the magnitude of translation is O (when & = 0), its accuracy and cost are also 0; as the magnitude grows, more inputs successfully cross the decision boundary, resulting an increase in accuracy and average cost. Accuracy/cost values can then be chosen or compared.
We also adopt standard statistical methods to convey minimum costs, which correspond to the mini- mum scalars required to alter each input's prediction. For continuous data, where costs scale linearly as a particular translation is scaled, we deem interpretable to display solely mean translations alongside the illustration of minimum costs (Figure aadd Appendix B.I). an assertion supported by our user studies, where participants interpreted GLOBE-CE explanations considerably faster than in AReS. Prior to our analysis, translations as raw vectors in input space lacked an immediate and intuitive interpretation
categorical data. Theorem demonstrates that any translation can be in- terpreted as series of If/Then rules, limited to one Then condition per feature, as portrayed by the individual rows in Table [ Theorem 2 consequently proves that as translation is scaled, If conditions are added to the rules for each Teature (e.g.. Account Status in Table Tp. We name the resultant GCE representation a Cumulative Rules Chari (CRC). See Appendix B.2 for further details.
3.3 ADAPTING THE GENERATION ALGORITIIM FOR CE DESIDERATA & BIAS ANALYSIS
Recognising the scope of possible GCE generation algorithms be vast, it should be stated that modifications to G along arbitrary criteria may impact efficiency in ways not investigated herein.
GCE Generation In context of recourse, G(B, n.) should deliver diverse and relatively sparse translations, targeting reliability (maximum accuracy, minimum cost) and taking into account that increasing diversity will likely reduce interpretability. Regarding actionability, we assign costs feature-wise (Section 5 We propose specific generation algorithm G(B, X, n, ns. C, (, p)) for our experiments, which consists of uniform random sampling of n, translations at a fixed cost c. The additional parameters control the number of randomly chosen features n,, and the power p which random samples between 0 and are raised, offering control over sparsity. The n final GCEs are cho- sen to greedily maximise accuracy. There also exist model categories that provide alternative candi- date G: model gradients in Deep Neural Networks (DNNs), feature attributions in XGBoost (XGB) models, and the mathematics of Support Vector Machines (SVMs) are explored in Appendix BB.
Bias Analysis Extending our framework to provide comparisons between affected subgroups of interest, similarly AReS, is trivial matter of separating the inputs and evaluating and scaling translations separately. However, it is recommended to generate the same set of n, random transla- tions for both subgroups as this a) eliminates any possible random bias in translation generation and b) exccutes faster. Alternatively, the translations selected for each subgroup can be exchanged, such that recourses can be directly compared (functionality that previous work does not suggest).
4 IMPROVING ACTIONABLE RECOURSE SUMMARIES: FAST ARES
We preface the evaluation of GLOBE-CE with an introduction to AReS (Rawal & Lakkaraju 2020). before suggesting improvements to the method such that both AReS and our improved version be used as baselines. AReS adopts an interpretable structure, termed two level recourse sets, comprising of triples of the form Outer-If/Inner If/Thn conditions (depicted in Figure Subgroup descriptors SD (Outer-If conditions) and recourse rules R.C (frequent itemsets output by apriori (Agrawal & Srikant ) determine such triples. Iteration over SD x RL2 yields the ground set V. before

---

Under review as a conference paper at ICLR 2023
(Stage I)
(Stage 2) Ground Set Evaluation
(Stage 3) Ground Set Optimisation
Ground Set Generation
Frequent itemsets SD, R.C.
Ground Set V C SD RCL (Varid Triples)
Ciolcate oll imples V c SD x R.C"
Whie there escids delett, aud or exchange operation that increases the value of the soluton set FUKL and sottsfes constraints perform
Forsign-Warker True
initoviee the ectution & as the
Worrg--Wrtter Folee
Bax Male 2D Ago 30,
singleton set with the orgest abjective function value:
C -e Years At-Cumeet--omme 1 de Yeers-l-Curert-tttme x
Then Sex
30 Age
Delets: remove rmpli from R. Add move tisle from Jo 12 Exchange: ewep miple with one from
Bow Malo Ago 32x
Yous aag MSSK (((()))
Male, Age Box Malo, 50 Ago
Years-Al Hument-Homa
Years Alre-A--CCCmmmmeee CumermHomeee
(Veun)
Figure 4: Workflow for our AReS implementation (bar improvements). Iteration over SD x RC computes all valid triples fonter-If/Inner--f// If/hhne conditions) the ground set V (Stage I). V is evaluated itemwise (Stage 2), and the optimisation Lee et al. 2009) is applicd (Stage 3), returning the smaller two level recourse set, R.
submodular maximization algorithm (Lee et al., 2009) computes the final set R C V using objective (R).. One strength of AReS is in assessing fairness via disparate impact of recourses, through user- defined SDD While novel method with an interpretable structure, AReS can fall short on two fronts:
Computational Efficiency Our analyses suggest that AReS highly dependent on the cardinality of the ground set V. resulting in impractically large V to optimise. Our amendments efficiently generate denser, seghhrrperforming V, unlocking the utility practitioners have expressed desire for.
Continuous Features Binning continuous data prior to GCE generation, as in AReS, struggles to trade speed with performance: too few bins results in unrealistic recourses; too many bins results in excessive computation. Our amendments demonstrate significant improvements on continuous data.
The overall search for a two level recourse set can be partitioned into three stages, as de- tailed in Figure 4 and Table 10 We generate V, evaluate V, and optimise V. to return a smaller, interpretable set R C SD x RC².. As in the original work, we set SD R.C and let |RC] = [V| <, n². Our optimisations include: R.C-Reduction and Cieer-Genrrrtion which V faster or generate higher performing V. respectively (Stage 1); V-Reduction, a method which termi- nates evaluation of V after r or r' iterations, (Stage 2); and V-Selection which selects the best s items from the ground set (Stage 3). Please refer to Appendix C for complete details and justifications.
5 EXPERIMENTS
The efficacy of our proposed Fast AReS and GLOBE-CE frameworks are evaluated herein. We analyse in Section 3.. the Fast AReS performance enhancements, before providing in Sections 5.2 and 5.3 an extensive evaluation of our GLOBE-CE framework against the current sfate-of-the-art art, AReS (and Fast AReS), and user study involving 16 ML practitioners tasked with assessing re- course bias in models using either AReS or GLOBE-CE. The study also uncovers some important criteria for bias assessment. For further experimental specifics, please refer to Appendices A and D
Datasets We employ four real world datasets to assess our methods, detailed in Table Top down, these predict recidivism, credit risk, payment defaults, and credit risk. AReS (Rawal & Lakkaraju 2020) utilised COMPAS (Larson et al.] 2016) and German Credit (Dua& & Graff, 2019); we include these in order to verify similar results, and we also introduce the larger Default Credit (Dua & Grafi 2019) and HELOC (FICO, 2018) datasets, which both include a significant number of continuous features.
Dataset
N
D
Neat
necont
COMPAS
6k
15
German
1k
71
17
3
Default
30k
91
9
14
HELOC
10k
23
23
Table Inputs N. Dimensions D, Categorical Neats Continuous Meont-
Models We train 3 types of model: DNN, XGB, and Logistic Regression (LR). Model parameters are not held constant, rather the best combination for each dataset and model is chosen. We elect to train models on 80% of the data, unlike Rawal & Lakkaraju (2020). Given the class label imbalance in German Credit (30:70) and the size of the dataset (N = 1000), training AReS on 50% of the data is likely to yield only 0.5 x 1000 x 0.3 = 150 negative predictions on which to construct recourses.
Set-Up AReS suggests binning continuous features, and specifying the cost of moving between two adjacent bins to be 1. We bin continuous features into 10 equal intervals post-training (see Sec- tion ofrade-offf. We also take the cost of moving from one categorical feature to another to be 1. As in AReS, we take the interpretability constraints é E2, E3 = 20, 7, 10, and set SD = R.C. Impor- tantly, specifying subgroups simplifies the problem significantly, and so in our attempt to stress test
7

---

Under review as a conference paper at ICLR 2023
(Stage 1)
(Stage Evalustion
(Stage
Ground Generation
Ground Optimisation
60-
60
1.5
Becoumee Recuraccy
Recourme Recuuracy
Si of Cround
1.0
HELOC
Graund
0.5
20
20
0.0
100
200
300
100
200
300
50
100
150
2:0
250
300
(eccndss)
Time (secones)
Time (secondss)
Orginal APM
Reduction
Abed. 5200
Geramiten 5300
30-33 aa 5080 300
Then: 100 ara 5000,
Comeration
Faductorn r- 5083
Orgine Ahad:--10 111
122 5000,
100
Figure 5: Fast AReS improvements (HELOC). Left: Size of ground set vs time. Centre: Accuracy of V vs time. Right: Final set acc(H) vs time. For other categorical datasets, R.C-Reduction achieved speedups For Default Credit (predominantl continuous), the latter performed best.
similar to
these explanation methods and fully gauge their scalability, we will avoid this. We also observed that both methods elected to alter a smaller number of features (2 or 3), regardless of any width limits.
5.1 FAST ARES EXPERIMENTAL IMPROVEMENTS
The evaluation of Fast AReS is broken down per workflow stage. For various hyperparameter com- binations (r, r' and s), the final sets returned in Stage 3 achieve significantly higher performance within a time frame of 300 seconds, achieving accuracies for which AReS required over 18 hours on HELOC. Appendix D lists details in full, including the combinations of hyperparameters used.
Reliability & Efficiency In Stage 1, we demonstrate RL-Reduction is capable of generating iden- tical ground sets orders of magnitude faster, and Then Generation constructs (different) ground sets rapidly. Stage 2 shrinking (r = 5000) significantly outperforms full evaluation, and Then Genera- tion erases many continuous data limitations by short-cutting the generation of relevant rules. Fi- nally, Stage 3 demonstrates vast speedups, owing to the generation of very small yet high- perfforiefo ground sets in the previous stage: r' and s restrict the size of V yet retain near-optimal acc(V).
5.2 GLOBE-CE EXPERIMENTAL IMPROVEMENTS
The GLOBE- CE explanations in our experiments are computed by the generation procedure posed in Section and their interpretations are as detailed in Section 3.2 (and Appendix (B.. We test the per- formance of both a single, scaled 6, as well as the diverse solution outlined previously, with n = 3, denoting these GLOBE-CE and dGLOBE-CE, respectively. Translations are uniformally sampled at cost 2 and scaled in the range 0 < k < 5, such that the maximum possible cost of translation is 10 bins (the entire range for any one given feature), which we assume as a feasibility limit for recourse.
Reliability Evaluation over various families of models and four diverse datasets indicates that, across the board, GLOBE-CE consistently exhibits the most reliable performance. Situations in which only moderate accuracy is achieved by GLOBE-CE (e.g., COMPAS, DNN), we attribute to an inability of the model to provide recourses within our fcasibility limit (after having exhaustively trialled solutions). In one rare case where the Fast AReS optimisation achieves superior cost (COM- PAS, DNN), it does so at the expense of significantly larger drop in accuracy (a natural trade-off).
Efficiency Applying AReS for several hours can yield accuracy improvements. though we con- sider such time scales inappropriate given that a) we test relatively simple datasets (Section 2.3 and b) practitioners are requesting higher levels of interactivity in explainability tools (Lakkaraju let al. (2022). We argue too that the concept of sampling random translations at a fixed cost is more intuitive than tuning hyperparameters of terms associated with cost, and that GLOBE-CE thus grants a higher degree of interactivity, given its performance with respect to computation time.
5.3 GLOBE-CE USER STUDIES
We conduct an online user study to analyse and compare the efficacy of GLOBE-CE and AReS in detecting recourse biases. The user study involves 16 participants, all of which have background in ML and some knowledge of post-hoc explainability. We include short tutorial on CEs, GCEs, and the ideas of recourse cost and recourse bias. The study utilises two black box models: the first is a decision tree with model bias against females, though with a recourse bias exhibited against males
8

---

Under review as a conference paper at ICLR 2023
Algorithms
Datasets
COMPAS
German Credit
Default Credit
HELOC
Acc.
Cost
Time
Ace.
Cost
Time
Acc.
Cost
Time
Acc.
Cost
Time
AReS
51%
2.31
101s
73%
1.6
2712s
7.22%
1.0
7984s
5.4%
1.0
9999s
DNN
Fast AReS
64%
1,45
32.0s
72%
1.43
12.8s
99.8%
4.2
37.3s
52%
5.5
109.
GLOBE-CE
66%
1.53
7.08s
85%
1.2
2.28s
98.5%
1.3
3.6s
93%
4.3
4.66s
dGLOBE-CE
70%
1.46
9.15s
90%
1.1
2.63s
100%
1.1
7.86s
95%
3.8
5.46s
AReS
45%
1.9
205s
61%
1.5
2092s
11%
1.0
9999s
1.7%
1.0
9999s
XGB
Fast AReS
83%
1.9
47.68
65%
1.75
34.33s
93%
2.3
29.97s
28%
2.1
93.58s
GLOBE-CE
78%
1.8
9.61s
95%
1.02
5.04s
96%
1.1
2.94s
58%
2.4
4.7s
aGLOBE-CL CE
91%
1.4
12.4s
83%
1.03
5.95s
100%
0.7
6.35s
80 %
2.4
5.6s
AReS
79%
1.5
506s
85%
1.3
3566s
31%
1.2
9999s
4.8%
1.0
9999s
LR
Fast AReS
82%
1.7
43.0s
85%
1.3
9.3s
99%
2.1
17.82s
92%
1.6
127.3s
GLOBBE-C
83%
1.20
8.43s
82%
1.2
3.39s
100%
1.0
3.42s
100 %
0.5
3.11s
dGLOBE-CE
84%
1.18
11.7s
91%
1.3
3.87s
100 %
1.0
7.21s
100 %
0.5
3,85s
Table 3:
Evaluatine the reliability (accuracylcost as per Section 1.1 and efficiency of GLOBE-CE against AReS (Rawal & Lakkaraju (2020). We have highlighted red explanations that a) achieve below 10% accuracy or b) require compulation time in excess of 10,000 seconds (#:3 hours). Best metrics are shown in bold.
due to the nature of the data distribution; the second is an SVM (where theoretical minimum lg costs can be computed as ground truth) with recourse bias against a synthetic Foreign Worker subgroup.
We randomly group the 16 participants into two equal subgroups, whereby each participant is pre- sented with two global explanations generated from either AReS or GLOBE-CE. For each explana- tion, the user study asks two questions: 1) do you think there exists bias in the presented recourse
rules?, and 2) explain the reasoning behind your choice. The first question is multiple choice with three answers, and the second is descriptive. Table
User Studics
AReS
GLOBE-CE
Breakdown
Bias?
Correct?
Bias?
Correct?
the response break- down. Importantly, 7 of the 8 AReS users also found describing the recourse bias to be hard, Details of the models, recourses, and snapshots of the user study can be found in Appendix [D.3 [D3
Black Box 1
0
7
7
Black Box 2
0
5
4
Table 4: Bias detection results from user studies. Bias and correct columns: no. of users that identified a bias and no. of users that described it correctly, respectively.
Takeaway In summary, the study demonstrates: 1) correct bias identification requires an under- standing of the underlying distribution of recourses (the proportion of inputs each rule applies to), 2) sub-optimal cost yields misleading conclusions and 3) GLOBE-CO CE both provides distribution infor- mation (AReS uncovers the biased model, yet misleads users with regards to the biased recourses), and outperforms AReS on cost with minimum recourse costs close to the ground truth SVM.
CONCLUSION
This work studies the current state of GCE methods, and addresses in detail the issues associated within the recently proposed AReS framework in Rawal & Lakkaraju (2020). We investigate works on both global and local counterfactual explanations before implementing and improving AReS. With mounting desire from a practitioner viewpoint for access to fast, interactive explainability tools (Lakkaraju et al. 2022), it is crucial that such methods are not inefficient. We propose im- provements the AReS framework that speed up the generation of GCEs by orders of magnitude, also witnessing significant accuracy improvements on continuous data. We further propose a novel GCE framework, GLOBE-CE, that further improves on the issues faced by AReS. Extensive exper- iments with four public datasets and user studies demonstrate the efficacy of our proposed frame- work in generating accurate global explanations that assist in identifying recourse biases. In future hope to apply the proposed GLOBE-CE approach to other real world use cases, and conceive of further generation algorithms that improve its performance beyond that demonstrated here. Ap- pendix E provides an at length discussion of such work, and the relation of our method to current issues facing local CEs such as robustness (Dominguez- ODomenguez-OOmedo Olmedo al., 202T) and sensitivity (Slack) et al. 2021). as well as a detailed discussion of the limitations of our work. We hope that the work here inspires further research into the particularly under-studied area of GCEs, and proves useful as the development of explainability tools grows in the coming years.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Rakesh Agrawal and Ramakrishnan Srikant. Fast Algorithms for Mining Association Rules in Large Databases. In Proceedings of the International Conference Very Large Data Bases, VLDB '94, pp. 487-499 San Francisco, USA, September 1994. Morgan Kaufmann Publishers Inc. ISBN 1558601538. URL httpt: acm. axg/doi// 10. 5555/ 672836
Solon Barocas, Andrew D. Selbst, and Manish Raghavan. The Hidden Assumptions Behind Coun- terfactual Explanations and Principal Reasons. In Proceedings of the Conference on Fairness, Accountability, and Transparency, Barcelona, Spain, January 2020. doi: 10. 10.1145/3351095. 3372830. URL Sttps://papee 3503019
ssrn. com/ so www.o//o/o/a/eeee//o/eeoooeeeeee http://pprrr.ccmaassasppmamassee
iid
arXiv: 1912.04930.
Maximilian Becker, Nadia Burkart, Pascal Birnstill, and Jürgen Beyerer. Step Towards Global Counterfactual Explanations: Approximating the Feature Space Through Hierarchical Division and Graph Search. In Advances in Artificial Intelligence and Machine Learning, 2021. URL
hittps://pubiit wwi.aaaiiinnnn.. www.onnn..bbbbi. www.bbiibbitt.......e. wit.o
Chaofan Chen, Kangeheng Lin, Cynthia Rudin, Yaron Shaposhnik, Sijia Wang, and Tong Wang. An Interpretable Model with Globally Consistent Explanations for Credit Risk. In NeurlPS Workshop on Challenges and Opportunities for Al in Financial Services: the Impact of Fair- ness, Explainability, Accuracy, and Privacy, Montréal, Canada, December 2018. URL https:
7/arxiv. www. abs /1///18111111 12615
Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shan- mugam, and Payel Das. Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives. In Advances in Neural Information Processing Systems, Montréal, lattps:
Canada, December 2018. #1le/c5ff2543555f4cco (aweaed38813377322 20-
Ricardo Dominguez-Olmeddo, Amir-Hossein Karimi, and Berhhard Schölkopf. On the Adversarial Robustmess of Causal Algorithmic Recourse. 11X11:2112.11313 [cs), December 2021. URL
11313
arXiv: 2112.11313.
Dheeru Dua and Casey Graff. UCT Machine Learning Repository, 2019. URLhhtp:://acchi
ics. www.cccicoo edu/ml
Sanghamitra Dutta, Jason Long. Saumitra Mishra, Cecilia Tilli, and Daniele Magazzeni. Robust counterfactual explanations for tree-based ensembles. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari. Gang Niu, and Sivan Sabato (eds.), International Conference on Ma- chine Leurning, volume 162 of Proceedings of Machine Learning Research, pp. 5742-5756, Bal- timore, USA, 17-23 Jul 2022. PMLR. URL hhtttps:/pproeeeeeee ngs. ml htt.roeeedigggg..r..eess///////o ptw.s/v12s//11
Muntta22aduutta222 pdf
FICO. Explainable Machine Learning Challenge, 2018. URL httmm///exp.aiaaaleeaaacccc www.eeeeeeaaaannneeeeeee llenge
fico.
Jingyue Gao, Xiting Wang. Yasha Wang, Yulan Yan, and Xing Xie. Learning Groupwise Ex-
planations for Black-Box Models. Zhi-Hua Zhou (cd.), Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 2396-2402, Virtual-Only. August
2021. International Joint Conferences on Artificial Intelligence Organization. URL https: //doi. 10..//1...0 24963 21.22342ccaii.. heeiiiaaaaa2111211 /30
Vivek Gupta, Pegah Nokhiz, Chitradeep Dutta Roy, and Suresh Venkatasubbaamanian. Equalizing Recourse across Groups, 2019. URL htttattt org http://ax.....or///////9/// 03166
Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, and Hiroki Arimura. DACE: Distribution-Awace Counterfactual Explanation by Mixed-Integer Linear Optimization. In Pruceedings of the Inter-
national Joint Conference on Artificial Intelligence, pp. 2855 2862, Yokohama. Japan, July 2020. International Joint Conferences Artificial Intelligence Organization. ISBN 978-0-9992411-66
5. doi: 10.24963/ijcai. 2020/395. URL
URL https::: www. www.://ww..ogg/po/eeeeeeeeeeeeee wtw.aa...r/pprcceedigg///0000000
395
10

---

Under review as a conference paper at ICLR 2023
Kentaro Kanamori, Takuya Takagi. Ken Kobayashi, and Yuichi Ike. Counterfactual Explana- tion Trees: Transparent and Consistent Actionable Recourse with Decision Trees. In Gus- tau Camps-Valle Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings of The Interna- tional Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Ma-
chine Learning Research, Pp. 1846-1888 1870, Virtual-Only, March 2022. PMLR. URL https: www..ppresee...... press www.llaaanaaiiieeaeaaa html
//proceedings mmr..
Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A Survey of Al- gorithmic Recourse: Definitions, Formulations, Solutions, and Prospects. In NeurIPS Work- shop on ML Retrospectives, Surveys & Meta-Analyses (ML-RSA), Virtual-Only, December 2020. URL http:s:/mmmmreerrspppeee ready pdf, arXiv: 2010.04050.
github..hh..... io/ wttp//euurrrc/e/e// camera
Himabindu Lakkaraju. Ece Kamar, Rich Caruana, and Jure Leskovee. Faithful and Customizable Explanations of Black Box Models. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, AIES '19, pp. 131-138, Honolulu, USA, Jamuary 2019. Association for Comput- ing Machinery. ISBN 9781450363242. URL https: //tii//iiii//. wtwp1//........oo//o//. 111111..111330000 http:////oo...org/0/001111//////
3314229
Himabindu Lakkaraju, Dylan Slack, Yuxin Chen, Chenhao Tan, and Sameer Singh. Rethinking Explainability as Dialogue: A Practitioner's Perspective, 2022. URLhttps://arxiv
abs/2202.0188 01875
Jeff Larson, Surya Mattu, Lauren Kirchner, and Julia Angwin How We Analyzed the COMPAS Recidivism Algorithm, May 2016. URL /
how-we- ana yeeellyeddeteee wwwpas
Jon Lee, Vahab Mirrokni. Viswanath Nagarjan, and Maxim Sviridenko. Non-Monotone Submodular Maximization under Matroid and Knapsack Constraints. Proceedings of the Annual ACM
Symposium on Theory of Computing. Maryland, USA, May 2009. URL hothhtt:: acm.m..
org/doi/100 00145/1536411 1.04441..33666 1536459 arXiv: 0902.0353.
Dan Ley, Umang Bhatt, and Adrian Weller. Diverse, Global and Amortised Counterfactual Expla- nations for Uncertainty Estimates, In AAAI Conference on Artificial Intelligence, Virtual-Only, February 2022. URL http:://t//aatt.t
Ana Lucic, Harrie Oosterhuis, Hinda Haned, and Maarten de Rijke. FOCUS: Flexible Optimiz- able Counterfactual Explanations for Tree Ensembles. In AAAI Conference Artificial Intelli- gence. Virtual-Only, February 2022. URLhttp: //axxii///xxv....// org/ http//bb/1111....1 1219911999 1911.12199.
arXiv:
Scott M. Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M. Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. Explainable AI for Trees: From Lo- cal Explanations to Global Understanding. Nature Machine Intelligence, January 2020. URL
https: http:://www.aatuuu.
www. wtt.://e..ooaatanlleceeeee 20t.
01225660199-111 019-0138-9
Divyat Mahajan, Chenhao Tan, and Amit Sharma. Preserving Causal Constraints in Counterfactual Explanations for Machine Learning Classifiers. In NeurlPS Workshop on Do the Right Thing: Machine Learning and Causal Inference for Improved Decision Making, Vancouver, Canada, December 2019. UtLhttp:://are
abaaaaas1111 1912. 01111122.777777
arXiv: 1912.03277.
Saumitra Mishra, Sanghamitra Dutta, Jason Long, and Daniele Magazzeni. A survey on the ro- bustness of feature importance and counterfactual explanations, 2021. URL https://apxxi org/abs/ 2111 00358
Ramaravind Kommiya Mothilal, Amit Sharma, and Chenhao Tan. Explaining Machine Learn- ing Classifiers through Diverse Counterfactual Explanations. In Proceedings of the Confer- ence on Fairness, Accountability, and Transparency. pp. 607-617, Barcelona, Spain, Jan- uary 2020. doi: 10. 141/33351195533788888 URL httph: //ll. acm www.acm.crro oct.crr//oi//bbeeeeeeeee/e//s 1145/3351095. 3372850 arXiv: 1905.07697.
Axel Parmentier and Thibaut Vidal. Optimal Counterfactual Explanations in Tree En- sembles. In International Conference on Machine Learning, pp. 8422-8431, Virtual- Only, July 2021. URL http:/ http///ptpceec..ce//e/pp www. www.s/rreesvvv33 http://///33/mmmmmeerra.aaaaa
parment ier fpd arXiv: 2106.06631.

---

Under review as a conference paper at ICLR 2023
Martin Pawelczyk, Sascha Bielawski, Johannes den Heuvel, Tobias Richter, and Gjergji Kasneci. CARLA: Python Library to Benchmark Algorithmic Recourse
and Counterfactual Explanation Algorithms. In Advances in Neural Information Processing Systems (Datasets & Benchmarks Track), August 2021. URL https: wtw.toeeeiinnss.eeeiiee.... www.nnuuri.... cc/ wwtpaper/ppppppppppcppeee.eeeeap 2021/Eile//////// pdr arviv: 2108.00783.
25biaadd6ab90ee222222222
Martin Pawelczyk, Teresa Datta, Johannes van-den Heuvel, Gjergji Kasneci, and Himabindu Lakkaraju. Algorithmic Recourse in the Face of Noisy Human Responses. arXiv:2203. 06768 arXiv: 2203.06768.
[cs], March 2022.
org/ abs 2203.
Dino Pedreschi, Fosca Giannotti, Riccardo Guidotti. Anna Monreale. Salvatore Ruggieri, and Franco Turini. Meaningful Explanations of Black Box AI Decision Systems. In AAA/ Con- ference on Artificial Intelligence, volume 33, pp. 9780-9784, Honolulu, USA, January 2019. doi: 10.1609/aaai 133101.330199800 URL https: aaai wxgg/indes / article/view 5500
Gregory Plumb, Jonathan Terhorst, Sriram Sankararaman, and Ameet Talwalkar. Explaining Groups of Points in Low-Dimensional Representations. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the International Conference on Machine Learning, volume 119 of Proceed- ings of Machine Learning Research, pp. 7762-7771 Virtual-Only. July 2020. PMLR. URL http: http:::/proceeeiiio ngs. mm www.srssvvlll 9/p umb20a /pl umb2 a0 pdf
Rafael Poyiadzi, Kacper Sokol, Raul Santos-Rodriguee Tijl De Bie, and Peter Flach. FACE: Fea- sible and Actionable Counterfactual Explanations. In Proceedings of the AAAI/ACM Confer- ence on AI, Ethics, and Society, pp. 344-350, New York, USA. February 2020. doi: 10.1 wttg/////////oooooooo URL https: //tl///ll/ acm. org doi/ 1121/110.1 11111145355222 3375850
3375627.3375850.
arXiv: 1909.09369.
Kaivalya Rawal and Himabindu Lakkaraju. Beyond Individualized Recourse: Interpretable and Interactive Summaries of Actionable Recourses. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances Neural Information Pro- cessing Systems, volume 33, pp. 12187-12198, Virtual-Only, December 2020. Curran Associates, Inc. URL
newriss............. www.:i.....pppppeeee pcc/pppper/222//Eleee (Be77330e9667777382220C5ff442 Paper.
Cynthia Rudin. Stop Explaining Black Box Machine Learning Models for High Stakes Decisions and Use Interpretable Models Instead. Nature Machine Intelligence, May 2019. hthhtts::
/www. nature..............
com/ wwtaacaeeeeeeeee. s42256/ 0009-0008--1
Cynthia Rudin and Joanna Radin. Why Are We Using Black Box Models in AI When We Don't Need To? A Lesson From an Explainable AI Competition. Harvard Data Science Review, November 2019. doi: 221116699608192.588all eddu/pub// 99kuryi8
URL https: happs://hdas //dar mitpress mit.
Dylan Slack, Anna Hilgard, Himabindu Lakkaraju, and Sameer Singh. Counterfactual Expla- nations Can Be Manipulated. In Advances in Neural Information Processing Systems, vol- 34, Virtual-Only, December 2021. URL https: ptttps://prrceeed.nne haper/2021/E111 wttp///1ee//004444abbb. (
meurrps..... cc/ pdf.
Ilia Stepin, Jose M. Alonso, Alejandro Catala, and Martín Pereira-Fariñu. A Survey of Contrastive and Counterfactual Explanation Generation Methods for Explainable Artificial Intelligence. In
IEEE Access, volume 9, pp. 11974-12001 2021. doi: 10.
2021.35532....15 URL
https://si /ttt::://ieeexpoorc peteexxlooeeeeeeee. ieee org/ http///twwnnn/ee///c /tw.uumnnn//2210000 /9321372
Gabriele Tolomei, Fabrizio Silvestri, Andrew Haines, and Mounia Lalmas. Interpretable Pre- dictions of Tree-based Ensembles via Actionable Feature Tweaking. In Proceedings of the
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 465- 474, Novia Scotia, Canada, August 2017. URL https: http///laaacco acm. org/ htg//doi// 10. 1145/ 01777933.099000
Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards Robust and Reliable Al- aas///bb///000 13620
gorithmic Recourse, July 2021. URL 2102.13620.
arXiv:
12

---

Under review as a conference paper at ICLR 2023
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable Recourse in Linear Classification. In Proceedings of the Conference on Fairness, Accountability, and Trunsparency, pp. 10-19, Atlanta, USA, January 2019. doi: 10. 00.114//287560.227555555
URLhttps: //ll. acm. org/
doi/10 1145/ 3255/3285565 28666666
arXiv: 1809.06514.
Arnaud Van Looveren and Janis Klaise. Interpretable Counterfactual Explanations Guided by Prototypes. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 650-665, Bilbao, Spain, September 2021. Springer. URL https://202/) 352.au____2...0 pdrj
ecml att.ppacc..cttoorooooooooe//e/aa
Suresh Venkatasubbaamnnia and Mark Alfano. The Philosophical Basis of Algorithmic Recourse. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 284-293, Barcelona, Spain, January 2020. ACM. ISBN 978-1-4503--636--1 doi: 10.1 145/3351095. 3372876. hRthsttps:
acm. org /ttp:////1...11/333111111 3372 3372876
Sahil Verma, John Dickerson, and Keegan Hines. axtattrrracttallxpppaaiaaaan for Machine Learn- ing: A Review. October 2020. URL http:://arxiv.orr/aaa////0/0 10596
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual Explanations Without Open- ing the Black Box: Automated Decisions and the GDPR. Harvard Journal of Law & Technol- ogy. 2018 ISSN 1556-5068, doi: 10.2139sssm.3062288 URL https: : /wwww SSIn, com
abst ract 306328
arXiv: 171 171999.
13

---

Under review as a conference paper at ICLR 2023
APPENDIX
This appendix formatted as follows.
1. We discuss the Datasets & Models used in work in Appendix A
2. We discuss Implementation Details and Example Outputs of GLOBE-CE in Appendix
3. We discuss the Implementation Details for AReS and Fast AReS in Appendix C
4. We list the Experimental Details of work and analyse Further Results in Appendix
5. We discuss Limitations and areas of Future Work for GLOBE-CE in Appendix E
Where necessary, we provide discussion for potential limitations of our work and future improve- ments or avenues for exploration.
A DATASETS & MODELS
Four benchmarked datasets are employed in our experiments, all of which describe binary classifi- cation and publicly available. Details provided below and in Table Our experiments utilise three types of models: Deep Neural Networks (DNNs); XGBoost (XGB); and Logistic Regression (LR), described below and in Tables 6 through 8 Our user study also investigates linear kernel Support Vector Machines (SVMs), as these provide mathematical forms for minimum recourse.
A.1 DATASETS
To assess our methods, we utilise the real world datasets detailed below and in Table 2 Where necessary, we augment input dimensions with one-hot encodings over necessary variables (e.g. Sex).
The COMPAS (Correctional Offender Management Profiling for Alternative Sanctions) dataset (Larson et al. 2016) classifies recidivism risk, based off of various factors including race, and can be obtained from and is described at: https: www.ppropb.l.. wttppuulic...ggrrrt.ile. wttp/rttcgle///////ooo.......cet viciimimmmmmmmm settings.
how-we- aawlanaalaaaaaa zed- the- www.-cccpaaaaaoe roci vi am- aww.aatggrthh This dataset tests performance of our method in low-din cow-dimeniional and
The German Credit dataset (Dua & Grafi 2019) classifies credit risk and be obtained from ics uci, wtw.l//e///mmaattttt//////////// http///aaaaettsstta.lecooo
and is described at: latps:://arch: credit+catan The documentation for this dataset also details cost matrix, where false posi- tive predictions induce a higher cost than false negative predictions, but we ignore this in model training. Note that this dataset, which tests mainly categorical settings, is distinct from the common Default Credit dataset, described hereafter.
(german-
The Default Credit dataset (Dua Graff 2019) classifies default risk on customer payments and is obtained from and described at: https:: /arch ve. ics uci .ed.eedunii /ml /adtaataaaees. setaasttsseeeeee.e defau It offereai ttcarrt This dataset stress-tests scalability (increased inputs, dimensions and continuous features).
The HELOC (Home Equity Line of Credit) dataset FFICO 2018) classifies credit risk and can be
obtained from (upon request) and described in detail at:
attps://conmusat fico. com/s/
Name
No. Inputs
Input Dim.
Categorical
Continuous
No. Train
No. Test
COMPAS
6172
15*
4
4937
1235
German Credit
1000
71*
17
800
200
Default Credit
30000
91#
14
24000
6000
HELOC 9871
23
0
23
7896*
1975*
*Denotes values post-pun poot-processing (one-hot encoding inputs. dropping inputs).
Table Summary of the datascts used in our experiments. Although German Credit includes continuous fea- tures, we find that they have limited effect on the model both during training the resulting explanations.
14

---

Under review as a conference paper at ICLR 2023
We drop duplicate inputs, and inputs where all feature values are missing (negative values), and replace remaining missing values in the dataset with median values. Notably, the majority of features are monotonically increasing/decrrasingg
A.2 MODELS
We train models with 80:20 split for each dataset. While each model's parameters differ, the universal aims are to a) achieve sufficient accuracy, b) avoid overfitting. and c) predict a similar class balance to the original data. The true proportion of negative labels in the training data of each dataset are 45 %. 30%. 22% and 53 %. respectively. The 5o. Train column dictates in Tables through [8 and the inputs in | with negative predictions from a particular model are denoted [Aan]-
Deep Neural Networks (DNNs) We the common library PyTorch construct and train DNNs. Widths and depths of such models are outlined in Table 6 Layers include dropout, bias and ReLU activation functions. We map the final layer to the output using softmax, and use Adam optimise cross-entropy loss function. Table 6 details various model parameters/bchavioors.
Name
Width
Depth
Dropout
Train Acc.
Test Ace
Xanl
Kanl/ ||
COMPAS
30
5
0.4
68%
65%
2552
52%
German Credit
50
0.3
84%
78%
243
30% %
Default Credit
80
5
0.3
81%
81 %
5232
22 %
HELOC
50
5
0.5
74%
74%
4334
55%
Table 6: Summary of the DNNs used in our experiments.
XGBoost (XGB)
Implementation from the common xgboost library.
Name
Depth
Estimators
a,a, À
Train Acc.
Test Acc
|atti
Katil / X
COMPAS
100
1,
70%
68%
2008
41 %
German Credit
500
0, 0,
95%
74%
197
%
Default Credit
10
200
2,4,
90%
83%
3744
16%
HELOC
100
4,4,
77%
74%
4323
55%
Table 7: Summary of the XGB models used in experiments.
Logistic Regression (LR)
Implementation from the common s learn library.
Name
Max Iterations
Class Weights (0:1)
Train Acc.
Test Acc
Xant /|/2*
COMPAS
1000
1:1
67%
65%
1940
39%
German Credit
1000
1:1
79%
76%
180
23%
Default Credit
2000
0.65:0.35
81%
83%
3858
16%
HELOC
2000
1:1
73%
75%
4282
54%
Table Summary of the LR models used in our experiments. Class Weights refer the loss function used.
B OUR FRAMEWORK: GLOBAL & EFFICIENT CES
This Appendix discusses several specificities concerning our methodology. Similarly to our AReS implementations, we eeknowledge that there does exist scope to improve upon the efficiency of our method, though encouraged by the superior results GLOBE-CE achieves relative to baselines.
15

---

Under review as a conference paper at ICLR 2023
B.1 EXAMPLE GLOBE- -CCE REPRESENTATIONS FOR CONTINUOUS DATA (HELOC)
This section expands upon the various outputs of our framework (Section 3.2 in the context of continuous data from the HELOC dataset (FICO 2018). We consider the following useful repre- sentations of the information computed in Algorithm accuracy-cost profiles, minimum costs, and mean translations.
Accuracy-Cos Profiles The natural trade-off associated with CEs is that between accuracy and cost; lower cost CEs are likely to cover fewer inputs, and vice versa. The literature typically accounts for this by introducing hyperparameter (e.g. A) to tune the trade-off. This however assumes a linear relationship between the metrics i.c. À is held constant during optimisation. Not only is this unreal- istic, as the relative importance of accuracy normally varies with cost, but it introduces tuning diffi- culties for practitioners, i..,, it must be determined either a priori through hyperparameter search which accuracy-com combination is optimal, and subsequently which À value maps to this particular combination (non-trivial). As stated in Section 3.2 our scaling approach instead induces accuracy- cost profiles as in Figure [ providing far more interpretable method for accuracy/cost selection.
Minimum Costs & Mean Translations Standard statistical methods can be adopted to convey the minimum costs per input (corresponding to the minimum scalar required to alter the prediction). For continuous data, knowing that costs scale linearly as a particular translation is scaled, we deem it interpretable to display solely mean translations alongside the illustration of minimum costs, an assertion supported by user studies, where participants interpreted GLOBE-CE explanations considerably faster than in AReS. These explanation representations are depicted in Figure I
B.2 EXAMPLE GLOBE-CU CE REPRESENTATIONS FOR CATEGORICAL DATA (GERMAN)
We now proceed to examine typical GLOBE-CE outputs for categorical features, using the German Credit (Dua & Graft 2019) dataset. Of particular interest is the representation of scaled categorical translations. The accuracy cost profile and minimum cost histogram naturally follow.
Cumulative Rules Charts for Scaled Translations For the sake of our analysis, consider purely the categorical features from German Credit (see Section 3.2 for the introduction CRCs).
Recall that, under a given translation direction, there ex-
Accuracy- Cost Profiles
ists a minimum cost, or equivalently minimum scalar, at
100
which recourse is achieved (shown in blue in Figure (). if indeed recourse can be achieved at all. However, un-
[Minimmn Costs)
80-
GLOBE-CE
Accuracy (%)
15 Scelars)
Allbb
like continuous features, representing the range of poten-
tial minimum scalars across all inputs in an interpretable manner is not trivial. To generate the CRC in Table we exploit the vector of lower bounds k = 1k1, k2..... knn introduced by Theorem 2 which deñnes the minimum scalars required generate specific feature value rules for a given translation. We select 5 equally spaced scalars from this vector (shown in Table [ and in orange in Fig- ure(6). The constrained selection of n scalars from k, such that minimum costs are achieved over the inputs where re- course is found in Algorithm I can be viewed tonic submodular maximisation. Problems of this type NP-hard, though unlike AReS, our required search spaces have shown empirically to be of significantly re- duced size. Lastly, the accuracy-cor cost and minimum costs properties of AReS are also shown in green for reference.
40
20
0-
0.5
1.0 Average Cost
1.5
Minimum Costs
GLOBE CE (Minimum Costs)
150
Art: 91.41% Mean
CLOSE.CE (S Scalors)
mono-
Frequency
rastt 03 90%,
100
Mean Cost
50
Aceuracy-Cost Profiles and Minimum Costs The nu-
2
3
merical values in such representation trayed via the Accuracy-Cou Cost Profiles and Minimum Histograms (Figure 6 Upper and Lower, respectively). The figures shown demonstrate our frame- work's superiority over AReS (including efficiency being around 400 times higher in this situation), even in the context of categorical features, which AReS is designed for, favouring the use of the categorical translation thcorems. As seen, these representations are particularly useful in comparing recourses between subgroups- optimal translations for one subgroup can also be directly applied to another, and vice versa, to gain insights as to a model's subgroup-level reasoning. Potentially, the
casily por-
Figure 6: GLOBE CE representations.
Minimum Cost
16

---

Under review as a conference paper at ICLR 2023
of a CRC could too be reordered to achieve optimality. We discuss these future avenues for research in Appendix E.1
Notes Regarding Scaled Translations By our defini- tions in Section 5 and Appendix E the cost of scaled translation kō on an imput I, increases monotonically with k as displayed in Figure Theorem 2 for proof w.r.t. categorical features). However, between inputs æi and Σz. a smaller scaled translation λjě may induce a higher cost on input Σn than a larger scaled translation kz induces on input Σn (Figure 7). For a fixed inputs Σ1 and 2g can have different costs. For example, should an 'If" condition be satisfied by Σn that is not satisfied by Σ2. and and Ig are otherwise the same, then I1 will have greater cost than 2n (Figure 7]. These last statements apply and only if categorical Teatures are involved.
Cost vs Scalar (German Credit, XGBoost)
X1
3
k =
2
1
Scalar,
Figure 7:
Display of monotonicity, b) smaller k inducing higher cost, and c) fixed k inducing variable cost.
Scaled Translation Example (Single Categorical Feature) We conclude this section by pro- viding one further example aid understanding of the scaling process. Take a one-hot encoded feature with n = 4 values, translation & = [8,, 82, 03. 64] [0, 10,-1,1, 1/2]. index sequence [2, 1,,44,3, vector of lower bound scalars
of sorted 5 (ascending) A
[A, D2, Ag, Aa] = [ki 1z2, k3, k4] - [1, 1/2, oo, 2]. Recall that all rules will have the form 'If Feature Value X. Then Feature Value = 3', since 6g is the maximum translation (Theorem D. For example, & states intuitively that é must be scaled by minimum factor of l: 2 in order for the translation to result in rule for the fourth feature value, since Ka 2. If k: < 2, inputs belonging to the fourth feature value will not flip value post-translation (take k 1, where the post-translation value for such inputs for the third input and 1.5 for the fourth input, resulting no change after re-encoding values by selecting the maximum). Table 9 illlssratees the rule generation process in this case.
772
2
3
Am
2
kam.
1/2
ki.... x 81
0
0
0
kam. x 82
-1/2
-1
-2
kam. x 83
1/2
kam. x 84
1/4
1/2
Rules for
2, Then
If or Then
If or 4,
kmmm < le < kantt
Then 3
Alternative Rules
Not (1 or or 4), Then
If Not (3 o), Then
If Not 3, Then
Table Example of the vector of lower bound scalars and its relation to translation and resulting rules. Values/indexes with distance >1 from the maximum translation (k6g) are shown in red. < n.
B.3 GENERALITY OF OUR FRAMEWORK
Though it has been mentioned repeatedly, we will reinstate our objective of proposing general CE generation framework, and proceed qualify this goal with in-depth analysis of the potential scope of our framework. This section delves deeper into the flexibility of GLOBBECE to model specifics, over variety of model families (DNNs, XGB, SVMs, results in Appendix D.2
well as
17

---

Under review as a conference paper at ICLR 2023
existing works in the model- agnostic domain of GCE research. We will conclude by considering the expansion of our implementation to current CE methods, and even to subsume the AReS algorithm.
Our motivation lies in demonstrating that our translation scaling techniques possess the requisite flexibility to be overlaid on top of existing criteria or algorithms in the CE space. Ideally, there should also exist specific parameter settings whereby our framework is equivalent to previous works, to guarantee at least equal performance. Analogously, Fast AReS is equívalent to AReS when using RL-Reduction, r = IV and & = |V]. Any such reduction of r or 8 can be discarded if hinders the performance of AReS, although we observe empirically that the opposite occurs. Similarly, the fact that our translation generation algorithm is completely general allows our framework to subsume any local method by simply setting the scalar ko = I and the datapoints of interest to just the local input.
Model Specific - Deep Neural Networks DNNs are widely known for their backpropagation properties, which permit gradient calculations for the output layer w.r.t. the input. Several works thus utilise gradient descent to locate counterfactuals for such models. Since the goal of our general CE generation method G(B, X, n) is to locate suitable GCE translations, we perform gradient descent on the following objective function, which takes both globality and categorical features into account:
(
Σ DEX
(Bo(round x 5)) + Acost(z, z. round r + +0) + cca(f + +)))
|
where Eops arg min L())-
In this context, Bg is the softmax prediction of the undesired class, or equivalently, when moving beyond recourse setting, the negative of such for the desired class. The cost and round terms are as previously described, and the additional cat term represents penalty over categorical features in the resulting counterfactuals (we penalise categorical feature values that do not sum to 1). This naturally conforms to the standard framing of the counterfactual problem, and as previously, once dorr is converged to, can be scaled to represent the final GCEs. For purely continuous datasets, the objective reduces to the minimisation of L()) 지े EgEx (Bol + 6) + xcost(o)).
Model Specific - XGBoost Models These also provide an interesting direction for efficient CE generation, namely through readily accessible feature importance scores. In the case of a single decision tree, each node contributes certain amount to the performance of the tree, and if each such contribution is weighted by the particular numher of inputs that it influences, feature importances can be computed for the tree whole. Averaging the importances across all trees yields the overall importance per feature. We show a second time that model specific information, this case feature importance, can be incorporated easily into our framework, simply by weighting the probability of each feature value in our random sampling framework with its feature importance.
Model Specifie - Support Vector Machines We study here the linear kernel SVM, a model that offers mathematical expressions for the minimum distances or costs to the decision bound- ary. Knowledge of such is useful in assessing the performance of our framework; the minimum costs discovered by GLOBE-CE should be as close as possible to the theoretical minima provided.
In our problem landscape, we require minimum costs rather than minimum distances, and we pro- ceed with two assumptions: costs are computed as the fo-n of the individual feature costs; and features are continuous for the sake of this analysis. The first assumption is influenced by the fact that, in the context of linear kernel SVMs, & costs lead to completely sparse solutions (i.e. solutions where just one feature value changes). Though multiple optimal solutions do exist in this context which are not completely sparse, we wish to test the ability of both AReS and GLOBE- CE in find- ing a single, unique, and optimal GCE, which the minimum & cost translation uniquely provides.
We thus aim to minimise the cost ||C8]|2 of a translation d. The feature costs vector is represented as a diagonal matrix C, scaling each feature independently before applying the fn-nomm Let the original input, counterfactual and translation be Σn I. and 5 = I- Σo- respectively. Given that the decision function of the SVM is y wf I. + b, where y = 0 at the decision boundary, we derive:
w I + O and yo === 2o + b
yo w [æ _o) = w" 5 = w C-5
Recognising this expression an inner-product between w" C-1 and Co, the Law of Cosines gives
-30 = - (12112 cos - ||C5]l2 =
yy
- C-1 |/ cos
18

---

Under review as a conference paper at ICLR 2023
which is minimised when cos f 1, such that the angle between Co and C- is 0. or alternatively, C/ is parallel to C- w. This would imply that, upon normalisation, the two would be equivalent:
C6 C- w
90 x
C²2w -y w
6= = W w='C-12 ||-- 1|--1u]1
|Cá22 wC-2=ul2
Noting that w" C-1 = C- ' w. since the cost matrix C is diagonal with C = CT and C-1 (C-1)² we have thus derived the closed-form expressions for minimum cost ||Că|l2 and translation
|
Yoo w C- and
-B0 2 |C-
This translation on the local input (To- yo) in fact applies globally, and we provide details regarding our user study in Appendix D.2 and Section 5f of the main text, demonstrating that the GLOBE-CE framework recovers minimum cost recourses very close to the theoretical global optima of the SVM
Model Agnostic Other black box GCE methods that adopt translation based approaches, such as those in Plumb et al. (2020) and Ley al. (2022), are easily integrated into our framework. Alternatively, we could view our framework as an extension to those works, filling the previous gaps with regards to minimum costs (by scaling translations) and categorical features (through our interpretation).
In reality, a plethora of issues surround past research on GCE translations. The algorithms in (Plumb) ct al. 2020 Ley et al. 2022) minimise distance between initial inputs ppost-translation) and target inputs, resulting in a heavy reliance on the distribution of training data. If data lies too far from the decision boundary. GCEs learnt will not be well optimised for cost. In fact, any sparsely populated areas of the data manifold risk under--epresentattin, despite possible significance w.r.t. the model's decision boundary. Furthermore, when the metric being optimised (the distance between datapoints) is not the metric used to evaluate the resulting explanations, tuning the learning process become very difficult.
However, such problems can be bypassed with the introduction of our method to scale translations. Typically, the outputs of our random sampling framework are not useful standalone, but embrace their full utility after the scaling process. Of course, our handling of categorical features would too be a great addition to these methods, which currently neglect to address categorical features.
The Role of Simplicity in our Framework The simplicity of our GCE generation process, as compared to earlier approaches (Rawal & Lakkaraju 2020; Kanamori et al., 2022), serves to high- light the power of the consequent scaling and selection operations (outlined in this Appendix). It is particularly encouraging that we can achieve superior levels of reliability (high accuracy, low cost) and efficiency compared to the baselines of AReS and Fast AReS, which holds promise for the scal- ability of GLOBE-CE: as datasets and models increase in complexity. there remains a large scope still for our algorithm to improve and adapt.
A Amending our Framework As examples, genetic, evolutionary, simplex (Nelder-Mead) search algorithms could improve both the reliability and the efficiency of the translation generation process as compared to random sampling. In fact, by framing the global search in an analogous sense to the local problem, as we do in Section 3. we leave the door open for any potential groundbreaking local CE research to be applied immediately in the context of GCEs. Another consideration is that a single translation direction will not always guarantee optimality. In fact, true optimality is only guaranteed by a single translation in contexts where the decision boundary spans a hyperplane (e.g. SVMs). We accommodate the use of multiple translations in our approach through a greedy maximum accuracy search the fixed cost of the search, but the presence of many works in this field outlining methods to achieve diversity should be noted, particularly given that our local framing of the global search directly permits the implementation of diversity techniques such as those in Mothilal et al. (2020).
Subsuming AReS We would further argue that the approach in AReS to produce a relatively large number of GCE explanations is one of the main contributors to its computational complexity, though the form of the two level recourse set generally requires much. Of course, there is no reason that the apriori (Agrawal & Srikant 1994) search could not also be used in our framework to generate translations for categorical features by influencing the probability of particular feature values in the same manner as the XGBoost feature importance method that we discussed earlier this Appendix. On top of this, the ability of our framework to impose any number or combination of subgroup descriptors provides route essentially subsume the two level recourse set representation that
19

---

Under review as a conference paper at ICLR 2023
AReS deploys, which we portray in Figure features do not undergo binning.
I with the exception (and advantage) that continuous
The other notable detail in Figures I [nd is the direct comparison of the same GCE between subgroups. Comparing GCEs with different feature values relative scales can make it difficult to determine what, if any. biases are present in the recourses found. Conversely, by applying the same translation direction to both subgroups, the specific differences between recourses are much more easily identified, avoiding the metaphorical 'apples to oranges' comparison. We sug- gest that translations identified within subgroups are made ffrid, and their reliabilities evaluated on opposing subgroups. Note that all of the representations that propose in this text (accuracy-cost profiles, minimum cost histograms, mean translations, and CRCs) support such translation fluidity.
Comparing Subgroups
C ARES IMPLEMENTATION
We use this Appendix to provide further details regarding the implementation of each stage of the AReS workflow. Our implementation of AReS, without improvements, does in fact differ slightly from that proposed in Rawal & Lakkaraju (2020), and as such we will justify our changes herein. We of course acknowledge that this implementation is far from the most efficient possible, though hope that the patterns and improvements we have identified can aid further development of not only this framework, but others in the global counterfactual explanations space.
Of note is the scalability of AReS, which struggled with Default Credit and HELOC, datasets that contain significantly more points to explain ((Xar)) than German Credit or COMPAS, and signif- icantly more continuous features. Additionally, the proportion of points with positive predictions (roughly 75% for German Credit and 45% for HELOC on average) influences the ease with which AReS finds recourses. For stringent models (those which scarcely predict positively), it would make sense that the vast majority of frequent itemsets generated by apriori are representative of feature value combinations that exist in the inputs with negative predictions, and we might therefore expect to need to generate an enormous number of triples before we can identify successful recourses.
Stage 1 Contribution (R (RL-Redutiion) We remove items with feature combinations that only occur once (c.g., "Sex= = Male, Age < 30" has feature combination "Sex, Age"). yielding [RC] = an (0 S a S 1) in (n) time. This generates an identical ground set V, yet saves (1 (1-ac a² )n² iterations.
q) At each iteration of SD RC, we filter the data by the If conditions and redeploy apriori to generate Then conditions. The ground set generated here differs from that in AReS, and we observe significant improvements continuous features.
Stage Contribution
Stage 2 Contribution (V-Reduction, r,r') At large [Vi evaluation costly, yet this is necessary requirement in find- ing high-performing triples. Fortunately, we can take advan- tage of two empirical observations: 1) the generation of a large ground set V is relatively cheap and 2) acc(V) saturates far be- fore the whole set has been evaluated. We evaluate a fixed num- ber of triples and form a new ground set in one of two ways:
Performance
of Tippls Selected Ground Length 119/09
Recouss sormay (60
42-
20
So ected Tipls
adding each new triple; or adding only triples that increase the recourse accuracy of the new ground set. We denote these and r', respectively. For example, r = None and r' 1000 re- turns 1000 evaluations, and may store fewer than 1000 triples.
Maeimmm Single Selecued Triple
1000
2000
3000
4000
5500
Number of tiipes in V Seleced
Figure German Credit dataset. Re- dundancy in triples of ground set V.
Stage 3 Contribution (V-Selection, s) The bottleneck in the AReS framework, however, lies in the submodular maximisation of Stage (Lee et al., 2009). We achieve speedups by further shrinking V pre-optimisation to a more practical starting point. We propose to sort the (new) ground set by recourse accuracy (pre-computed) and select the highest-performing triples. If r or r', no sorting occurs.
C.1 GROUND SET GENERATION (STAGE 1)
AReS includes interpretability constraints for the total number of triples é1, the maximum width of any Outer-If/Inner--t combination 62 and the number of unique subgroup descriptors e3 in R. As in AReS, we take E,, C2 = 20, 7, 10. Constraints that are independent of the optimisation, such as 62, are applied in this stage in (n²)) and not (nz²) time. In our implementation, this involves expediting the 22 width constraint to the ground set generation process by constraining apriori to
20

---

Under review as a conference paper at ICLR 2023
(Stage 1) Ground Set Generation
(Stage 2) Ground Set Evaluation
(Stage 3)
Ground Set Optimisation
AReS
n Iterations Performed
Evaluates Full Ground Set
Searches Full Ground Set
Fast AReS
nnn or n² max, T. Iterations Performed
Evaluates and Reduces Full or Partial Ground Set
Scarches Reduced and Sorted Ground Set
Table 10: A summary of our AReS enhancements w.r.t cach stage of the search. We define o, n and Ti below.
only return frequent itemsets that have length 62 or less, since those already with width e2 cannot then be further combined with another itemset form Outer-If/Inner conditions. the width constraint is not violated for the If conditions, the resulting triple will automatically satisfy the constraint.
The implication of this is that we can apply the constraint in Stage 1, while we generate the ground
set (in the first two levels of the iteration through RC²). This avoids applying the width constraint mid-optimisation in Stage 3, reducing the time complexity of the operation from O(n") to O(n²), It also reduces the number of constraints used in Lee et al. (2009), speeding up Stage 3. Since it makes sense that triples which violate the maximum width condition should not be generated in Stage 1, we assume that similar approach is deployed (though not stated) in Rawal & Lakkaraju (2020).
Teen-tennotiion The apriori algorithm (Agrawal & Srikant 1994) alluded to in the main text takes a probability threshold as input. This probability of an itemset in the data, or support thresh- old p. determines the size of SD and RC, and consequently the size of V. Our Then-Generation method again utilises application of apriori, requiring a second support threshold q. A lower bound for the threshold is derived here. In fact, there always exists a lower bound when mining fre- quent itemsets, such as in apriori, since no observed itemset can occur less than once. Thus, set- ting < 1/|x| would be redundant. This allows us to analyse (in Appendix D.I the effect of 1/1x < S 1. Appendix further details apriori.
C.2 GROUND SET EVALUATION (STAGE 2)
The submodular maximisation (Lee et al. 2009) first evaluates the objective function f over all triples u E V, before initialising the solution R as the singleton set {u} with the maximum f((x)). For large [V]. this evaluation becomes computationally costly (more-so does the subsequent ground set optimisation), and many triples are also redundant. However, we require large [V] in order to find high-performing triples and achieve an acceptable upper bound" on the final set, R R
Our improvement V-Reduction evaluates the objective function f (see Appendix C.3 over fixed number of triples in V (recall that AReS evaluates the entirety of V\. As we ve demonstrated empirically, albeit on the four datasets tried in this investigation, evaluating the entire ground set is wasteful, given that performance of the first elements of V saturates quickly, and more so if one considers that Stage must then perform submodular maximisation over space potentially hundreds of times as large, and that (Lee et al. 2009) only guarantees polynomial time.
However, there is distinction between evaluating the objective function f and evaluating the acc and cost terms used in evaluation. Fortunately, no extra major computation is required to evaluate the accuracy and cost terms, since the objective function f' returns model predictions and costs, and although the two processes differ, they can be carried out efficiently in tandem. This is promising, as not only does our method allow us to terminate evaluation once saturation has been reached, but it also provides with the upper bound acc(R) (R) acc(V). In many of our experiments, this upper bound is actually reached in Stage 3 far before the algorithm has completed, presenting us with straightforward opportunity for early termination of the algorithm. This could further save time dramatically, and provide ofse-of-use to practitioners, though was not included in our experiments.
C.3 GROUND SET OPTIMISATION (STAGE 3)
We introduce two key modifications to Stage 3 of our implementation. The first is to the objective function, the second is the submodular maximisation in Lee al. (2009).
For instance, if acc(V) 25%, we cannot achieve acc( R) > 25%; conversely, ground with acc(V) 80% requires major evaluation and will also include many low-performing, redundant triples.
21

---

Under review as a conference paper at ICLR 2023
Objective Function The objective function fR) in Rawal & Lakkaraju (2020) is designed to be non-normal, non-negative, non-monotone and submodular, and to have constraints that are matroids. These conditions are required for the submodular maximisation in Lee et al. (2009) to have formal guarantee of convergence. This results in four terms in ((R): incorrectrecourse cover, featurecost, featurechange. Bar the cover term, all of these are subtracted from ( (i.e., maximising correct recourse by maximising the negative of incorrectrecourse). Such objective function with three adjustable hyperparameters can very difficult to tune. For that reason, we also trial in our exper- iments an objective that consists very simply of ace(R) À x cost(R), (R). which we maximise. We argue that the formal guarantees of convergence (polynomial time) largely misdirection of ef- forts in the original method. Polynomial time is not particularly helpful when the size of ground sets required for certain datasets/models is huge, and thus we instead focus reducing the size of the ground set while retaining quality before the submodular maximisation (Lee et al. 2009) is applied.
Submodular Maximisation The algorithm states that, for k constraints, you can exchange up to elements from your solution set R alongside the addition of one element from V. Stated also is that the optimisation should be repeated k+1 1 times, before the best solution for R is then chosen. In reality, both of these induce high computational costs. Trivially, for the latter, ignoring the maximum width constraint (A (Appendix C.J) and taking k + 1 = 3, we will mostly increase the time taken by AReS three-fold. Having observed that both of these steps do not improve the performance of AReS significantly in our experiments, we omit them from the original and improved implementations. Furthermore, since the exchange operation stated is the most costly, our implementation checks for add/delete operations first until such options exhausted. Note that works such as (Kanamori ct al. 2022) instead utilise greedy algorithms, though still require in excess of three hours on simple datasets.
C.4 APRIORI INTERPRETATION
The apriori algorithm Agrawal Srikant 1994) returns groups of itemsets that are frequently found within a dataset according to some support threshold (the probability of finding such an itemset in the data). Figure demonstrates this (itemsets with less than equal to 6 features). Rawal & Lakkaraju 2020) states:
recourse set is made up of triples of the form (d, e, c') denoting an outer if condition (d) and inner if-then conditions (c, c'), respectively (page 3).
"The corresponding features in c and c' should match" (page 3). The optimisation searches for R S SD x RL (eq. 1, page 5).
4. "If the user does not provide any input, both SD and RL are assigned to the same candidate set generated by apriori" (page 5).
We deduce that SD corresponds to the outer if conditions (d), so RL must then correspond to (c, c'). However, from statement 2, apriori cannot provide c, c' because of statement 2, which states that features must match, since a single apriori set is incapable of returning the "Then' part of the recourse rule, yet statements 3 and together imply that apriori generates the full space R C SD R..
support
nomaets
(111)
0.001334
(A112)
0:147558
(618)
O 0.200422
(032)
(435)
2042 0.120000
A132, ABL, A101, A174)
Furthermore, Lakkaraju et al.] (2019) define the search space as R C ND x DL x C. where N'D and DL are analagous with SD and R.C, and the number of classes. The rules then take the intuitive form, with AD,, DC and C representing each part of the triple. Assuming this reasoning, alongside correspondence with the authors, confirms the form of our search space R S SD x RC²
2043 0.117547
(A353, A253 ABL A103, A174)
2014
0.100422
(A122, A201, A132,AA12,AA000 A1c1. A174)
2015 0.202444
(A124,A153, A201, A242,A33,, A174)
20%
0.172369
(ALS), A303,220,,A00 A34,,,44,,AA, A174)
Figure 9: Apriori (p = 0.1).
C.5 FURTHER DISCUSSION
Customising AReS As implicit in (Rawal & Lakkaraju 2020), our implementation gives the user control over which features are dropped, how continuous features are binned, and the particular subgroup deseriptors SD used for fairness analysis. We additionally posit that the particular data used to generate R.L. will potentially affect the final results quite significantly; there should be scope
22

---

Under review as a conference paper at ICLR 2023
to assign the 'Then' conditions to an apriori evaluation on the dataset points with positive predic- tions, as these may be more likely to produce successful recourses. Data searcity should be taken into account, as small datasets may not contain such distribution of feature values that allow for effective searches of this nature. Finally, the constraint that all features in the Inner-If and Then conditions must match could possibly be ignored (the CET Kanamori et al. 2022) and GLOBE-CE frameworks both take this approach).
Critiquing AReS We should preface this section by stating that the framework in (Raaal & Lakkaraju 2020) is an original and major contribution to GCEs, and hope that its limitations can be overcome in consequent research. Save the shortcomings listed in the main text, find potential further three for consideration.
Firstly, AReS evaluates its recourses on the same set from which they are learnt (as do we in the main text). In practice, there are many scenarios in which we desire evaluation on set of unseen test points. We perform such an evaluation, detailed in Appendix [D] finding that performance does not deviate significantly, though the GLOBE-CE framework does generalise slightly better.
Secondly, the baselines used to assess AReS are notably weak (e.g. a naive averaging of instance- level explanations), and the effort exerted in tuning such baselines is unknown. While our work considers AReS to be state-of-the-art, owing to its performance against such baselines, making efforts to improve its performance (Fast AReS), perhaps a larger and more varied group of viable baseline frameworks for GCEs that strike a balance between naivety and sophistication could be conceived of.
Finally, the computational expense of the method has not been documented to a strong degree, and the claims made regarding its formal guarantees and framework generality we find not entirely useful. The former claim, while potentially useful, only applics to the optimisation of the ground set V to produce the two level recourse set R. providing no concurrent guarantee on the upper bound of V. and pertaining also polynomial time convergence, which scales particularly badly given the extremely high cardinality of V required to achieve acceptable performance. The latter claim, on the generality of the framework, neglects again account for the size of the optimisation space required by AReS; in throwing a sufficient amount of compute at a simple dataset (far more than the original model required), one should reasonably expect to fit such exhaustive explanations.
Future Work AReS Regarding the first point on generalisation above, we could extend our evaluation on unseen test data to include the effect of overfitting in models and out-of distriibiiiin test points, given the susceptibility of current explanation methods to such inputs.
An interesting property of our Fast AReS optimisation that there exist variety of different shrunk ground sets, each with high performance. While our optimisation simply picks one, multiplicity AReS might be achieved by shuffling the ground set before the evaluation stage. We suggest the space of possible solutions be explored, tasked with answering the question: where might this fail?
Additionally, one might naturally question if framework such as AReS could be extended beyond recourse, especially to other data forms such as images. While we explain the shortcomings AReS faces on continuous data, we posit that higher level views of image data such as latent spaces or concept embeddings could provide interesting target for extended future AReS framework.
Finally, as stated, we bin continuous features into 10 equally sized intervals. This follows the con- ventions in (Rawal & Lakkaraju 2020), though we find that this approach struggles to trade per- formance with efficiency. Another facet of the framework is the direct interpretation of two bins; supposedly, one can move from any point in the first bin, to any point in the second bin, though this is not theoretically confirmed. The use of evenly spaced bins might also be improved upon in certain cases with quantile based discretisation, or more advanced decision tree structures. Lastly, the determination of costs is still complex and unsolved problem in counterfactual literature- we justify our approach in Appendix
D EXPERIMENTAL RESULTS
This Appendix further details various experiments on AReS, Fast AReS and our GLOBE-CE frame- work. User studies, model specific analyses, and hyperparameters are included.
D.I ARES OPTIMISATIONS
23

---

Under review as a conference paper at ICLR 2023
Stage 1
Stage
Stage 3
OG: 0.169 p 0.390
OG: 5000
OG: 0.39 < 0.305, [
German Credit
RL:: 0.39 5 p S 0.149
RL. 5000
RL: = 0:245
Then: 0.9
0.303
Then: 5000, 0.00125
Then: 0.48,
= 0.00125
OG: 0.316 S S 0.26, r [V]
0.00125
OG: 0.325 S S 0.285
OG: 5000
OG: 0.324 < 0.318, |V|
HELOC
RI: 0.325 S 0.203
RI: 5000
RI: 0.245
Then: 0.75 S Σ 0.563 9 0.000127
Then: 5000, g 0.000127
Then: p 0.48,
OG: 0.325 S 0.3. [
9 0.000127
Table 11: The keys OG (Original AReS), RL (RL-Reduction) and Then
refer to the
generation process of the ground set, per Section + Arrows indicate values carried from one stage to the next. Apriori thresholds and q are listed. Remaining parameters r, r' and are listed in the Figure plots.
As AReS struggles to achieve sufficient accu- racy within reasonable times, we set hyperpa- rameters for featurecost and featurechange, or X, to O, also finding that the average costs were low and did not vary large amount, justifying the decision to target correctness. The remain- ing hyperparameters used in the Figure exppr-
(Stage 2)
Ground Set Evaluation
90
Recourse Accuracy
of Ground Set V (%6)
80-
75
iments (Section (5) are as detailed per stage in
[T] Recall also that we have bounded the range of the apriori threshold y used in Then-
70
65
ic whly 2000)
Generation to 1/|x| S < 1 (Section and Appendix C.I p. Figure 10 demonstrates that for q I we slightly reduce the run- time, at the expense of a much larger drop in performance. Observe that the red and brown lines (where p is held constant and is varied) converge to the green and purple lines (where q 1/| and p varied), respectively. The brown and purple plots also indicate that combining our two improvements R.C-Reduction and Then-Generatie performs sub-optimally, We thus de- cide to evaluate these improvements separately, with fixed 1/|22 threshold. We note that the choice of SD = RC weakens performance, which aids stress-testing scalability.
Io- 0.33, vary 2002
0:20125
20000
55
FL. Fesluction Then Dureratioo
50
100
150
200
250
300
Time (seconds)
Figure 10: Effect of apriori threshold in the proposed Chen-Generaaton method (German Credit).
D.2 GLOBE-CE
Model Specific Analyses
The GLOBB-CE implementations that utilised some sort of model in-
formation (DNN gradients. XGB feature importance scores) are depicted Figures IT and [2]
alongside GLOBB-CE (blue), diverse GLOBE-CE with n = 3 (orange) and Fast AReS (green).
The use of DNN gradient descent to determine appropriate translation prior to scaling, shown in red Figure II demonstrates marginally improved performance over GLOBE-CE on continuous data (HELOC, Right), though the same method for categorical data (German Credit, Left) produces
Accuracy-Cost Profiles (German Credit, DNN)
Accuracy-Cost Profiles (HELOC, DNN)
100
(Nistnum Grst
80
Drvemeti in 31
80
INiiinum Costo
Accuracy 196
Accuracy
60
60
40
CLont-ce
Gradients
40
20
INiiium Cootol
20
CLOBE-CE
(Nimmum Costro
on
Nea. AlMS
GECHE-CE
(NImmmm coots)
BLOBe dE
0-
0.75
1.00
1.50
1.75
Average Cost
Average Cast
Figure 11: Translations generated by gradient descent and scaled (red), compared to the other frameworks.
24

---

Under review as a conference paper at ICLR 2023
Accuracy-Cost Profiles (COMPAS, XGB)
Accurácy-Cost Profiles (Default Credit, XGB)
80-
80-
Accuracy (9)
Accuracy (%)
60
60
40
40
GOSE-CE
mum Costsl
Fast
[Nimimum Costs
GLOBE-GT
Tve
20
20
0-
GLose CE mum Costal
Teature GL000-CE
Coste
0
CLOBE C2
(Minmrm Couts)
GLOEE-CC (Mint Costrl
Teature importance
1.0
1.5
2.5
Average Cost
Average Cast
Figure 12: Translations generated by feature importance and scaled (red), compared to the other frameworks.
similar results to GLOBE-CE, with performance dependent on the particular accuracy-cost trade-off desired (as expected, given that gradient descent can struggle in the presence of categorical features).
The of XGB feature importances to weight the probability of the random translation generated prior to scaling, shown in red in Figure 12, demonstrates improved performance over GLOBE-CE on continuous data (Default Credit, Right) and, marginally, on categorical data (COMPAS, Left).
The results across these two particular model classes illustrate the flexibility of our framework and its ability to accommodate model specific properties, doing so effectively with model gradients (DNNs) and feature importance scores (XGB). The effectiveness of the random sampling framework in the absence of any additional model information other than its predictions also demonstrated.
D.3 USER STUDIES
In our experiments, participants received either explanations from GLOBE-CE or from AReS, and were subsequently asked to provide bias identification, and description if they believed a bias to exist. The aim of the study is two-fold. We first hope to establish the importance of providing the underlying distribution of costs per the GCEs output by framework (i.e., the proportion of inputs that correspond to each GCE, given that the lowest cost GCE that results in a flipped prediction is selected for each input). Secondly, we hoped to reinforce our claim in Section 2.3 that sub-optimal recourse costs/accuracies can resulting in misleading conclusions regarding bias.
In the first question of the study, both frameworks output the exact same explanations, minus the fact that GLOBE-CE also includes costs and the percentage of inputs for which a particular rule was best. Explanations for AReS/GLOBE-CE, are identical (minus [square brackets] for AReS). This is shown below in the Cumulative Rules Chart, where the subgroup Female is discriminated against by the model, though due the data distribution, the subgroup Male is discriminated against with respects to the costs required for recourse. This challenges the assumption made in AReS that recourse biases can be simply gauged without knowledge of the inputs affected.
Cumulative Rules Chart:
If Sex = Male:
Job = No and Property = No, Then Job Yes and Property Yes
Rule M1 [Cost 2, 90% of Inputs]
If Healthcare = No, Then Healthcare Yes
}
Rule M2 [Cost 1, 10% of Inputs]
If Sex Female:
Job No and Property No and Savings = No. Then Job = Yes and Property = Yes and Savings = Yes
Rule Fl [Cost 3, 10% of Inputs]
If Healthcare No,
Rule F2 [Cost 1, 90% of Inputs]
Then Healthcare = Yes
25

---

Under review as a conference paper at ICLR 2023
Study znn Erakattion the Gribal Cousta fastall
lggm satk preens grise couturiiuu oparsioos. masss use than ansue the time sessitess Dustors
henggn warter andite
ote hoaett thee Oter otrppst
deve ball set ratice ferk
phes
50% repua]
Thes muth than cieas aos chrawoo
For saboros 3e mnieeeu monnen dion
Focartoelct Fite: 821
parter
irgain pian tegins. you perric qentee
destraht
Figure 13: User study 2 snapshots (GLOBE-CE (ELOBE-C), Left: Explanation Right: Explanation 2. Successful
recourse bias identification and description occurs when underlying costs distributions are shown.
In the second question of the study, we introduce a synthetic subgroup ForeignWorke Worker to HELOC, and discriminate against it by forcing recourse costs to be higher. We use a linear kernel SVM as our model, in order to compare the recourse costs of AReS and GLOBE-CE against the absolute minimum costs, which we provide theoretical analysis for in B.3] Our results for GLOBE OEEEEEEAO are in Figure I achieving near-optimal costs, and resulting in correct bias description by users.
E DISCUSSION & FUTURE WORK
Having outlined highly flexible framework for GCEs, it is important that we consider now both the possible limitations of the GLOBE-CE framework, as well as avenues for future work or growth.
E. POSSIBLE GLOBE-CE LIMITATIONS AND FUTURE WORK
Determining Costs of Actionable Recourse We do not unrealistically claim to hold the answers regarding the costs associated with actioning particular counterfactuals. In reality, this is an incredi- bly complex problem to solve. Not only could the costs certain actions vary with time, depend on each other and themselves, or be susceptible to unknown degrees of randomness, but they could also depend on a multitude of factors surrounding the specific human being that is ultimately tasked with the action. Disregarding such difficulties, building a model that perfectly reflects a user's 's struggle in executing particular set of actions might easily require an improper breach of said user's privacy.
While Rawal & Lakkaraju 2020) proposes the use the Bradley-Terry model to compute fixed feature costs, and claims that pairwise feature comparisons are "relatively easy for experts to make", neglecting to account for the properties of the end user even the dependencies between costs will ultimately render such comparisons redundant. Notwithstanding this, searching for better cost models remains worthwhile area of research. For instance, despite its unreliability in this context, the use of the Bradley-Tere Terry model would still surpass in performance the use of non-normalised E distance as cost. As such, we do not overly focus on cost estimation in this paper. acknowledging that actionability remains, to all intents and purposes, an unsolved problem, and recognising that this could affect the reliability of bias assessment between subgroups based upon costs. Instead, we settle for the use of unit costs between categorical features per decile of continuous features (L1).
Expanding our Baselines The basclines used in AReS are discussed in greater detail in Ap- pendix C.5 Further possible candidates are the GCE translations proposed in (Plumb et al., 2020)] Ley et al., 2022). and a non-interpretable accumulation of the costs of local CEs, used solely to assess minimum costs per input, and not naively averaged over produce GCEs. While this last
26

---

Under review as a conference paper at ICLR 2023
suggestion doesn't t yield GCEs, it could offer challenging set of minimum costs per input for framework to seek to outperform.
Limitations of Categorical Translations Our form of categorical translations always yield rules of the form "If' A (or B or .... Then X" for any one particular feature (with possible negation on the "If" term). However, it may also be useful to represent other forms, such "If A, Then Not A" or "If A then (B or C)". The minimum costs yielded would not decrease as a result of these new forms, since they can still be represented with the original (e.g. "If A, Then B" would solve simply the first suggestion), though may have interpretability implications which could explored in future work.
Alternative GCE Approaches The common perspective is to discover CEs from a set of inputs, though a user-based approach which does the opposite could also be proposed, whereby a user spec- ifies CE of interest, and the group of inputs most strongly affected by such a change and returned. Such an approach could utilise our proposed scaling operation to better summarise the group of imputs in terms of both accuracy and minimum cost, and could also execute without the need for user-specified CEs, generating, scaling and analysing CEs automatically instead.
identified
Relation between CEs and GCEs We postulate the thought experiment that, for a given dataset, there could always conceivably exist further inputs or dimensions at larger or smaller scales whereby global explanations are reduced to local explanations, and vice-versa. For example, a local CE, where all input dimensions are accounted for, can suddenly become a subgroup explanation if extra dimensions added to the dataset. By the same logic, removing dimensions points can render global explanations local. In the context of fixed models that we find ourselves in here, such modifications possess more theoretical than practical potential, though we pose that such direction for future research could uncover interested properties between local and global CEs.
adding data-
GLOBE-CE: Part We translate N negatively predicted instances to N neutrally predicted in- stances (on the decision boundary). This paves the way for further optimisation of the translation. For example, if the nearest neighbours between the original points and those on the decision bound- ary do not correspond to the translation for a significant number of inputs, further tuning could ensue.
E.2 ROBUSTNESS OF COUNTERFACTUALS
Recent research has demonstrated instabilities w.r.t. CE techniques from state-of-the-art methods:
CEs are non-robust (become invalid) in certain scenarios.
(Dominguez-Olmedo et al. 2021
Mishra et al. 2021 Dutta et al. 2022)
Minor perturbations to input features may result in substantially different recourses from popular CE approaches. (Slack al., (02T))
Minor changes in the underlying ML model, for example, due to retraining with new data, makes
CEs for the old model invalid on the new model. (Upadhyay et al. (021))
Noisy human implementation of the suggested recourse may prevent an individual from achieving the desired response from an ML model. (Pawelezyk et al. 2022)
Related research has also identified positive link between the distance moved past decision boundary and counterfactual robustness, which suggests that GLOBE-CE can easily be modified to account for robustness by simply increasing the scalar k that is applied to a global translations 6.
27


Reviews:
[{"review_id": "nsifvklgwPS", "reviewer": "Reviewer_e9Jt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "summary_of_the_paper": "The authors tackle the problem of \"global counterfactual explanations,\" which extend methods from local counterfactual explanations (of individual data instances) to draw global insights about a model. They propose a new framework, which they call GLOBE-CE, which is based on feature translations of vectors of variable length, and provide a mathematical analysis of the implications of this for categorical features. They also improve the efficiency of an existing one (ARES), and compare the two with real world datasets and user studies.", "summary_of_the_review": "I think there's some strong, interesting, and important work in this paper, but the missing context that seems to have been expected of the reader made it difficult to evaluate. With more pages devoted to the details, I believe this would be a very good paper. But I am not thrilled about its current form.", "strength_and_weaknesses": "Strengths: The key idea behind GLOBE-CE -- that if groups of instances are explained together by a single set of counterfactuals based on a translation in the input space -- is clever, and, to my knowledge, novel. The experiments seem to show that GLOBE-CE provides a good tradeoff between reliability and efficiency. The paper is very clearly written. The insights about categorical features are also interesting.\n\nWeaknesses:\n- There are, in my opinion, too many contributions in this paper for me to fully understand all of them without going through the appendix (and related work) in some detail. Between all the contributions, there appears to have not been room for exposition, definitions, and evidence. For instance, the concept of \"recourse cost\" is never precisely defined, though identifying bias in it appears to be the phenomenon of study that the methods proposed are meant to uncover. Another example is that the explanation of how AReS works is not really sufficient to follow the paper's contributions to it; I'd have to go read the original paper to understand how it works, and without that intuition, the statement that \"analyses suggest that AReS is highly dependent of the ground set V\" isn't very convincing.\n- The takeaway from the small user study is not obvious to me; measuring the effectiveness of the tool deserves a more in-depth evaluation than is provided here. (However, in a paper introducing this method I would not consider such a user study necessary.)\n- I also honestly think the title is somewhat misleading; I thought this paper would quantify reliability and efficiency and either empirically or theoretically examine those tradeoffs. Instead, the paper consists of several contributions vaguely connected by the theme of tackling reliability and efficiency.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "n1JNaZFCNg-", "reviewer": "Reviewer_tDod", "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": "", "summary_of_the_paper": "1. The efficiency of Actionable Recourse Summaries (AReS) is improved, and a method of Global & Efficient Counterfactual Explanations (GLOBE-CE) is designed to address the stability issues flexibly.\n2. The authors provide a mathematical analysis of categorical feature translations and use it in their presented method.\n3. Experiments on real-world datasets and user studies verify the proposed method's speed, reliability, and interpretability improvements.", "summary_of_the_review": "My pre-rebuttal rating is '6: marginally above the acceptance threshold'. I really appreciate the problem that this paper addresses and their effort in balancing reliability and efficiency. My concerns are mainly about the limitations caused by Categorical Translations and reproducibility. Please see the detailed concerns in the 'Weaknesses'. I would be happy to read the responses from the authors and willing to increase the score if my concerns are well-addressed.", "strength_and_weaknesses": "Strengths:\n1. This paper attempts to balance efficiency and reliability for global explanation methods of model behavior, which is a valuable perspective in machine learning practice.\n2. As the authors claim, it is the first to mathematically address the direct addition of translation vectors to one-hot encodings in the context of Counterfactual Explanations.\n3. Overall, the experiments seem well-designed, and the results are promising. Moreover, the improvements of the proposed framework are decent over other methods and consistent in various datasets and under different settings.\n \nWeaknesses:\n1. Since the framework is built on many machine-learning models, it would be too hard to reproduce this work because it misses quite a few details, such as how to adapt to various models via different hyper-settings.\n2. Categorical Translations have their limitation, such as omitting the rules of ’If A then B or C‘. Unavoidably, based on Categorical Translations, the presented framework may fail in similar cases. ", "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": "lT9YKwKRtu5", "reviewer": "Reviewer_NXG7", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "", "summary_of_the_paper": "The paper proposes a framework for global counterfactual explanations while considering the bias that can arise across different subgroups and the need to allow for different translations. The paper also provides an analysis of categorical feature translations. Emprirical results support the theoretical analysis.", "summary_of_the_review": "I vote for accepting this paper considering the proposed framework for global counterfactual explanations.", "strength_and_weaknesses": "Strengths: \n\n1. Well-motivated idea with clear illustration, especially Figure 2.\n\n\nWeakness:\n1. Clarity on how the mean cost for the translation vectors is estimated in Figure 1 (right-most figure) is needed.\n", "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": "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": "7mFNvJieDpF", "reviewer": "Reviewer_T2G1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper analyzes various theoretical and technological aspects related to global counterfactual explanation proposing various methods trying to empirically prove the statement \"Global Counterfactual Explanations Are Reliable Or Efficient, But Not Both\". In particular, it proposes a novel global and efficient counterfactual explainer GLOBE-CE, and improves an existing global counterfactual explainer named Actionable Recourse Summaries (AReS). ", "summary_of_the_review": "The content of the paper might be interesting, but before reaching the qualified level for this conference, the paper should be re-structured and better presented. Experiments should include additional evaluation measures such as those used in Mothilal, R. K., Sharma, A., & Tan, C. (2020, January). Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 conference on fairness, accountability, and transparency (pp. 607-617) or Guidotti, R. (2022). Counterfactual explanations and how to find them: literature review and benchmarking. Data Mining and Knowledge Discovery, 1-55 or Mazzine R, Martens D (2021) A framework and benchmarking study for counterfactual generating methods on tabular data. Appl Sci 11(16):7274. Also, a comparison against a baseline \"dummy\" global counterfactual explainers combining in a naive way local counterfactual explainers should be reported.", "strength_and_weaknesses": "+ A novel counterfactual explanation method is proposed\n+ An existing counterfactual explanation method is improved\n+ An interesting and limitedly addressed research direction is studied\n\n- The content is not organized in the best possible way, and the narrative is difficult to follow and chaotic in various passages.\n- The Fast AReS extension is not clearly explained. \n- The experiments are performed on a limited number of datasets and evaluated with a limited and not updated number of measures.\n", "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": "2x1LZ4jvjDj", "reviewer": "Reviewer_XGq4", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 2, "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": "", "summary_of_the_paper": "I spent an hour struggling to read this and, truthfully, I'm still not sure what it's about. ", "summary_of_the_review": "I was not able to understand this paper well enough to comment on its technical merits. I believe that this is fundamentally an issue of lack of clarity. This paper would need significant improvements to be published.", "strength_and_weaknesses": "A caveat for the rest of this review: I am not an expert in explanation. As such, much of the jargon was unfamiliar to me. It's possible that an expert in this area would have been able to make more sense of the paper than I did. That being said: this paper is very unclear to a reader who is just a general expert in machine learning. Indeed, I actually still can't figure out what, precisely, this paper is about.\n\nSome illustrative examples of clarity problems:\n1. as far as I can tell, \"global counterfactual explanation\" is not defined\n\n2. it's not clear what data setup the authors have in mind. I guess these are explanations for predictive models. In section 3.1, the authors write \"x in X_sub\". In context, I guess this notation is meant to be input features. What space do these features live in? Immediately after, the paper uses x + k*\\delta, where \\delta is a vector. That would seem to imply that x is a vector of real numbers. Does this method then only work for data where the features are vectors of real numbers? \n\nSimilarly: what does subgroup mean in this context? What is a \"successful\" counterfactual? \n\nThese confusions all occur in a single sentence. I believe such things could be clarified pretty easily; the issue is that they are not currently.\n\n3. The takeaway messages from Figures 1 and 3 are totally unclear by looking at the figures. The captions do not explain the purpose of these figures.\n\n4. I can't find any result in the paper that appears to correspond to the claim, \"Global Counterfactual Explanations are reliable or efficient, but not both\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject