Gradient-based Counterfactual Explanations using Tractable Probabilistic Models
Authors: Xiaoting Shao
Kristian Kersting
Venue: ICLR 2022 Submitted (2022)
Keywords: Counterfactual example
Sum product networks
tractable probabilistic models
counterfactual explanation.

Abstract: Counterfactual examples are an appealing class of post-hoc explanations for machine learning models. Given input x of class y, its counterfactual is a contrastive example x' of another class y'. Current approaches primarily solve this task by a complex optimization: define an objective function based on the loss of the counterfactual outcome y' with hard or soft constraints, then optimize this function as a black-box. This “deep learning” approach, however, is rather slow, sometimes tricky, and may result in unrealistic counterfactual examples. In this work, we propose a novel approach to deal with these problems using only two gradient computations based on tractable probabilistic models. First, we compute an unconstrained counterfactual u of x to induce the counterfactual outcome y'. Then, we adapt u to higher density regions, resulting in x'. Empirical evidence demonstrates the dominant advantages of our approach.

Under review as a conference paper at ICLR 2022
GRADIENT-BASED COUNTERFACTUAL EXPLANA- TIONS USING TRACTABLE PROBABILISTIC MODELS
Anonymous authors
Paper under double-blind review
ABSTRACT
Counterfactual examples are appealing class of post-hoc explanations for ma- chine learning models. Given input of class y1, counterfactual is contrastive example x' of another class yo- Current approaches primarily solve this task by a complex optimization: define an objective function based on the loss of the coun- terfactual outcome yo with hard or soft constraints, then optimize this function a black-box. This "deep learning" approach, however, is rather slow, sometimes tricky, and may result in unrealistic counterfactual examples. In this work, we propose a novel approach to deal with these problems using only two gradient computations based tractable probabilistic models. First, compute an constrained counterfactual u of æ to induce the counterfactual outcome yo- Then, we adapt higher density regions, resulting in x'. Empirical evidence demon- strates the dominant ad advantages of our approach.
INTRODUCTION
Explaining decisions made by intelligent systems, especially black-box models, is important. First of all, model that explain their decisions is more likely to gain human trust, especially if there are significant consequences for incorrect results, or the problem has not been sufficiently studied and validated in real-world applications (Simpson) 2007 Hoffman al., 2013 Doshi & Kim 2017]. Secondly, explanations can promote fairness by exposing bias towards protected attributes in the system (Prates al.) 2019 [Buolamwini & Gebrul 2018 Obermeyer al.] (219)). In addition,
explanations are a helpful tool for debugging purpose (Holte 1993 Freitas 2014 Rudin 2019).
Counterfactuals are closely related to classes of explanation, which much of the early work in AI on explaining the decisions made by an expert rule-based systems focused on (Wachter et al.) 2017]. As the name implies, counterfactual is an alternative example counter to the fact which takes the form "If X had not occurred, Y would not have occurred". Explicitly establishing the connec- tion between counterfactuals and explanations, Wachter et al.) (017)) concluded that counterfactual explanations can bridge the gap between the interests of data subjects and data controllers that oth- erwise acts as a barrier to legally binding right to explanation. They further formulate the problem of finding counterfactual explanations as an optimization task that minimizes the loss of desired outcome w.r.t. an alternative input combined with regularization for distance to the query example. In similar vein, the dominant majority of recent counterfactual explanation methods are proposed based on their adapted objective functions for optimization.
Unfortunately, these deep learning approaches have some downsides: First of all, they very time-consuning for generating explanations due to the iterative optimization process, because for every optimization iteration the model needs to be evaluated least once and it may take lot of iterations until a candidate is found. Secondly, the objective function is usually highly non-convex, which makes it more tricky to find a satisfying solution in practice. Thirdly, the optimizer involves additional hyperparameters that need to be carefully selected, such as learning rate. Furthermore, although these methods optimize for the "closest possible world" by constraining the distance the counterfactual to the query instance, they are still not aware of the underlying density and the data manifold. As a direct consequence, the counterfactuals often appear rather unnatural and unrealistic although they as close as possible to the query instance. See figure 3 for example. This imposes difficulties for humans to understand the explanations. As Nickerroo (1998) argues, humans exhibit confirmation bias, meaning that tend to ignore information that is inconsistent with our prior

---

Under review as a conference paper at ICLR 2022
beliefs. In analogy, unrealistic counterfactuals also have very limited effect for communicating explanations to humans.
To improve upon these limitations, propose novel approach to generate counterfactual expla- nations. Unlike the overwhelmingly dominant deep learning approach, we decouple the goal of perturbing the prediction and maintaining additional constraint the perturbation. Specifically, we view the task as a two-step process, whereby the first step is to perturb a sample towards a desired class and the second step is constrain the perturbed sample be close to the data manifold it is realistic and natural. The first goal aligns with adversarial attacks (Goodiellow et al. 2013 [Brown al. 2017; Yuan et al. 2019), where small perturbation is computed to perturb the prediction. In the literature there are gradient- based methods (Kurakin et al. | MMosavi--ezzool et al., 2016) and optimization-basee that gradient corresponds to the direction of steepest ascent, gradient-based perturbation is not only very easy to implement with current deep learning frameworks, but also much faster to compute compared optimization-based perturbation. Therefore we adopt gradient-based approach for the first step. To ensure the quality and effectiveness of the second step, we learn a sum-pm cum-product- network (SPN) (Poon & Domingos 2011). a tractable density model, on the input, and perturb the example further based on the gradient that directs to steepest ascent of likelihood, evaluated on the SPN.
methods (Szegedy et al. | Carlini & Wagner] (017). Exploiting the fact
In summary, we make the following contributions:
We propose the first approach for generating counterfactual examples using probabilistic circuits to ensure density-awareness in tractable way.
2. We experiment with complex and high-dimensional real-world dataset, which was not dealt with using domain-agnostic methods the literature.
3. We give empirical evidence to demonstrate the advantages and effectiveness of our ap- proach: visually appealing examples with high density, fast computation, and high success rate.
We proceed as follows: First, we give an overview of the literature and summarize the shortcomings of the existing approaches. Then introduce RAT-SPNs, preparing for presenting approach. Finally, we evaluate our approach via empirical evidence and conclude our work.
2 RELATED WORK ON COUNTERFACTUAL EXPLANATIONS
Research attention on counterfactual explanations has been increasingly raised since Wachter et al. (2017) presented the concept of unconditional counterfactual explanations as a novel type of ex- planation of automated decisions. Identifying the resemblance between counterfactual explanations and adversarial perturbations, |aachter et al. (2017) proposed to generate counterfactual explanations based the optimisation techniques used the adversarial perturbation literature. Specifically, loss function is minimized w.r.t its input, using standard gradient- based techniques, for a desired output and regularizer penalizing the distance between the counterfactual and the query.
Following Wachter et al. 2017). Mothilal et al. 2020) augmented the loss with diversity constraint to encourage diverse solutions. However, these approaches do not have explicit knowledge of the underlying density or data manifold, which may lead to unrealistic counterfactual explanations. A bunch of methods counteract this issue by learning an auxiliary generative model to impose addi- tional density constraints on the optimization process. As common choice for density approxima- tor, Variational Autoencoder (VAE) (Kingma Welling 2014) and its variants (Klys et al. 2018 Ivanov et al. 2019) are used. For instance, Dhurandhar et al. 2018 proposed contrastive explana- tions method (CEM) for neural networks based on optimization. The objective function consists of a hinge-like loss function and the elastic net regularizer as well as auxiliary VAE to evalu- ate the proximity to the data manifold. [ustnn et al. 2019 defined the term recourse as the ability of person to change the decision of model by altering actionable input variables. Recourse is evaluated by solving an optimization problem. Joshi et al. 2019 provided an algorithm, called RE- VISE, to suggest recourse, based on samples from the latent space of VAE characterizing the data distribution. Pawelezyk et al. 2020 developed a framework. called C-CHVAE, to generate faithful counterfactuals. C-CHVAE trains VAE and returns the closest counterfactual due
2

---

Under review as a conference paper at ICLR 2022
W1
We
-
y c
Figure I: The SPN structure used to estimate distribu- tion as a mixture of class- conditional densities. Each class-conditional density is in turn represented by a sub- SPN. Classification is done via Bayes' rule.
X1
X
X1
X
nearest neighbour style search in the latent space. Downs et al. 2020 proposed another algorith- mic recourse generation method, CRUDS, that generates multiple recourses satisfying underlying structure of the data as well as end-user specified constraints. Based on a VAE-variant, CRUDS uses Conditional Subspace Variational Autoencoder (CSVAE) model (Klys al. 2018) that is capable of extracting latent features that are relevant for prediction. Another method called CLUE Antorán et al. (2020) is proposed for interpreting uncertainty estimates from differentiable proba- bilistic models using counterfactual explanations, by searching in the latent space of VAE with arbitrary conditioning (VAEAC) (Ivanov et al., 2019).
Poyiadzi et al. 2020 proposed FACE, a graph-based algorithm to generate counterfactuals that are coherent with the underlying data distribution by constructing graph over all the candidate targets. Besides, several domain-specific approaches are also emerging Olson et al. (2021); Goyal et al.
2019 Chang et al. 2019).
The aforementioned techniques have the following shortcomings: 1. The deep learning-like ap- proach (Wachter et al.] 2017; Mothilal et al. 2020; Dhurandhar et al., 2018 Ustun et al., 2019 Joshi et al.) (2119) is too slow generate explanations the fly due to the iterative optimization process, which in turn comes with additional tuning parameters. 2. Although highly expressive, neural density estimators such VAEs highly intractable, which makes explicit density
straint on counterfactual explanations infeasible (Dhurandhar et al.) [2018) Ivanov et al.) 2019: Klys al. 2018 Joshi et al. 2019 Pawelezyk et al. 2020). In addition, they come with the overhead of latent representation, which is not necessarily in good quality when maximum likelihood training is used learn them (Alemi et 2018 Dai Wipf 2019).
We improve upon the aforementioned shortcomings by proposing the first counterfactual method using tractable probabilistic circuits, specifically sum-product networks (SPNs) (Darwiche 2003 Poon & Domingos 2011).
GRADIENT-BASED COUNTERFACTUAL EXPLANATIONS USING TRACTABLE PROBABILISTIC MODELS
Before explaining our idea, we first introduce the tractable probabilistic models we use.
An sum-product network (SPN) S over X is tractable probabilistic model for P(X) based directed acyclic graph (DAG). This graph indicates computation for probabilistic inference and con- sists of three types of nodes: univariate leaf nodes, sum nodes, and product nodes. Let ch(-) denote the children of a node. A sum node is weighted sum of its children, i.c. S ENEch(s) WS,N N non-negative and sum to 1, i.c. WS,N 0, Σn Ws,N 1. Sum nodes
where the weights WS.N can be viewed as mixtures of their child distributions. product node P is product of its children, i.e. P IINeck(P) N. The root node represents P(X). Products factorized distributions,
3

---

Under review as a conference paper at ICLR 2022
yo data monifold
Y1
+
accond step
connterfactual
X
log S(xluo)
Iog (xtlat))
first: step
+1x
(.S(m))
Figure 2: Left: Illustration of our gradient-basee approach. Arrow indicates perturbation based gradient step. Right: An example MNIST. The first corresponds the first gradient step for perturbing the prediction irregardless the manifold. This perturbation removes some characteristics of the current class and adds some characteristics of the counterfactual class, The resulting sample u yields the desired class but obviously deviates from the training sets (It looks neither like nor 7). The second row corresponds to the second gradient step for generating in-distribution counterfactual by pushing the intermediate sample to region with higher density.
implying independence assumption among their children. SPNs allow for fast, exact inference on high-treewidth models.
Unlike most of the probabilistic deep learning approaches, SPNs permit exact and efficient inference. Specifically, they are able to compute any marginalization and conditioning query in time linear of model's representation size. By employing SPNs for deep learning, random and tensorized SPNs (RAT-SPNs) (Peharz et al. (2000) are proposed using simple approach to construct random SPN structure and combine with GPU-based optimization. fooled by certain oft-of-domain image detection tests on which VAEs, normalizing flows (NFs), and auto-regressive density estimators (ARDEs) consistently fail (Choi & Jang. 2018 Nalisnick et al., 2018).
worth noting that RAT-SPNs are not
To learn the parameters w of a given RAT-SPN structure S in generative setting to approximate a distribution Pd (X),, we assume i.i.d. samples X' .......>> XN) are given. Then maximum like- lihood estimation is employed, i.e. w = arg max 1 over X represented by the RAT-SPN S.
N DN log S(x,), where S(x) a distribution
Apart from the standard use for density estimation, RAT-SPNs can be used as generative classifier as well. Consider classification problem f Rd + (1.....0 C} with C' labels, C roots are used to represent condiicondii densities (. =: S(X = y). The overall density distribution is then given by S(X) = E, S(Xly) See figure | for illustration. Bayes' rule is used to classify sample x: S(Y P(Y)) In other words, RAT-SPN of this special structure S(x)
has dual use: both a density estimator S(X) and classifier (X) We will use this model to demonstrate our approach because it can be used for classification and yield tractable density evaluation for free at the same time. However, our approach can be easily extended to deep neural classifiers by training auxiliary RAT-SPN for density estimation. For more details RAT-SPN, check out appendix.
Our approach is defined two serial perturbations: In the first step, maximize log S(yix) to
S(y x)
induce desired outcome y/, which is equivalent to maximizing log S(xly)
S(xlp") since
S(x) 8(y'lx) = log ((x('y)) s(xl)) S(y\x)
S(x
log
log
S(x)
S(x
when assuming a uniform class prior. Towards this end, we take a gradient step towards the steepest ascent of the counterfactual outcome. This results in the perturbed example u where
a(log S(xly/) log S(xly))
11 x
* E1.
dx
4

---

Under review as a conference paper at ICLR 2022
This step is similar generating an adversarial perturbation in that the sample u is expected to change the prediction to y from with very slight change.
However, without additional constraints, the perturbed sample is very likely to deviate from the underlying data manifold. In order to generate in-distribution counterfactuals, we maximize the density P*(u (u) of the current sample which is approximated via the SPN S(u). In contrast the density estimators used primarily in the literature, SPNs have the merit that they allow for tractable density evaluation. To maximize the density S(u), we take another gradient step towards its steepest ascent, i.e.
(S(u) Eu
x' = u
* c2.
x' is the final counterfactual explanation for x that yields s/ instead of y. See figure for illustration.
EMPIRICAL EVALUATION
To illustrate the advantages of our approach, we designed experiments to evaluate it both qualita- tively and quantitatively across several benchmark datasets. All the experiments are implemented in Python and Tensorflow, running on Linux machine with two Intel Xeon processors with 56 hyper-threaded cores, 4 NVDIA GeForce GTX 1080 under Ubuntu Linux 14.04.
Datasets: We experiment with three widely cited datasets commonly used in the counterfactual ex- planation literature and one real-world dataset. MNIST (LeCun| 1998). In particular, we evaluate across several contrastive pairs of classes where counterfactual perturbations are intuitive to com- prehend: digit and 4, digit and 7, digit 3 and 8, and digit 7 and 4. German credit dataset (ger) classifies people described by set of attributes good or bad credit risks. Adult-Income (Ronny & Barry 1996) records whether person makes over 50K a year based on census data. Caltech-UCSD Birds (CUB) (Wah et al. 2011). This is real-world dataset for tinengraeedd bird classification. This dataset contains 200 bird species and we evaluate the counterfactuals across three contrastive pairs of bird species: Red Faced Cormorant and Crested Auklet, Myrtle Warbler and Olive sided Flycatcher, Horned Grebe and Eared Grebe. Bird species classification is a difficult problem that pushes the limits of the visual abilities for both humans and computers. Some pairs of bird species are nearly visually indistinguishable and intraclass variance is very high. This is arguably the most complex and high dimensional problem studied so far in the counterfactual explanation literature. To make this problem slightly more approachable, we work with feature representations extracted from the final convolutional layers of VGG-16 (Simonyan & Zisserman 2015) pretrained on ImageNet. That is, we train RAT-SPN generative classifier using the class conditinnai feature maps.
We consider three widely cited model-agnostic approaches in the literature that can be directly applied to our chosen datasets: |Wachter et al. CEM (Dhurandhar et al. 2018) and FACE (Poyiadzi et al. 2 [
Baseline:
To evaluate approach with empirical evidence, trained RAT-SPN for each dataset. Each RAT-SPN is, as in figure] [ a mixture class-conditional densities. This RAT-SPN is used for both classification and density estimation. For each dataset, the counterfactual approaches are evaluated on the same RAT-SPN classifier. We used cross-validation to select hyper- parameters for RAT-SPNs and for all the counterfactual methods. See appendix for more details.
Implementation details:
4.1 OUR COUNTERFACTUAL EXAMPLES ARE VISUALLY APPEALING.
Counterfactual examples can be presented to users as contrastive explanations. The examples that correspond to prior beliefs of the users can be better received by them due to confirmation bias (Nickerson) 1998). That means, the counterfactual examples should appear plausible and not deviate too far from the training samples. Figure 3 demonstrates some examples on MNIST for a variety of test cases across four methods. It is obvious to see that our approach consistently yields the most visually appealing examples as they are smooth, clean and look very plausible. Although being
Since the real-world dataset is quite high sigeh-immnsional compared to those commonly used in the literature. we discarded some baselines with scalability issue after experimenting with it, e.g. DiCE MMothial et al.
2020
5

---

Under review as a conference paper at ICLR 2022
3
3
3
8
8
8
Query
8
8
8
3
3
3
4
4
4
7
3
3
3
3
3
.
Wachter
7
4
7
3
3
3
3
8
8
CEM
/
4
7
8
3
8
8
3
3
FACE
4
4
4
4
4
4
8
8
8
3
3
3
Ours
Figure 3: Counterfactual examples on MNIST across several classes and methods. The top row indicates the original class and the target class.
Query
Red Faced Cormorant + Crested Auklet
Myrtle Warbler + Olive sided Flycatcher
Horned Grebe Eared Grebe
Target
Wachter
CEM
FACE
Ours
Figure 4: Counterfactual examples on Caltech-UCSDD Birds (CUB) across several classes and meth- ods. The top row indicates the original class and the target class.
smooth, our counterfactual examples still show nice variation: For example, in the 7-th and 8- column, the counterfactual tilts to the left when the query image tilts slightly to the left, and likewise to the right. In comparison, Wachter al. and CEM (Dhurandhar et al.) 2018) both yicld quite wiggly and noisy results. Although CEM includes a VAE reconstruction loss its objective function a proxy for constraining the examples to be in-distribution, explicit evaluation of density intractable. FACE (Poyiadzi et al., 2020) also yields very plausible examples because it simply returns training instance of the counterfactual class.
Another visual example can be seen on CUB. As previously said, we trained RAT-SPN as a gen- erative classifier using the class-conditional feature maps generated by VGG-16. In this case, the

---

Under review as a conference paper at ICLR 2022
RAT-SPN gives density model the feature maps and the counterfactual explanations are also computed in this extracted feature space. Since feature maps can not be trivially transformed back to raw features, we strive only for highlighting the salient counterfactual features instead of imputing them. degossaeeesonssrrates some test examples on this dataset. The heatmap overlaid on the exam- ple indicates the salient counterfactual features that should be perturbed to become the counterfactual class, An example from each counterfactual class is shown in the first row. Note that this is not the particular target we strive for but only an example for the readers to have intuitive idea about the contrastive features. It can be seen that our approach consistently yields plausible heatmaps: For the Red Faced Cormoran the beak is highlighted when the image focuses on the head, and the tail is highlighted when the image zooms out. For the Myrtle Warbler the salient features are mostly on the yellow spot of the feather. For the Horned Grebe the salient features are mostly highlighted around the head. Among the baselines, CEM and FACE are implicitly density-aware and often show con- sistent behavior with our approach. However, FACE sometimes yiclds saliency on the background instead of on the bird. |Wachter et al. performs the worst and yields quite random and unintuitive heatmaps. In conclusion, our approach showed very competitive and intuitively plausible heatmaps that highlight the contrastive features this complex dataset.
From visual examples on both datasets we can see our approach yields appealing and intuitive results that are easy comprehend.
4.2 OUR COUNTERFACTUAL EXAMPLES HAVE HIGH LIKELIHOOD.
In contrast to wiggly examples, smooth examples often appear more plausible and realistic, which are in turn often tied with high likelihood. This experiment is to offer a quantitative evaluation on likelihood.
is widely agreed that communicating explanations with humans. Wachter al. (207)) penalizes distance the query instance, which indirectly also prevents the counterfactual examples to deviate too far from the dis- tribution. More recent approaches use VAEs as neural density estimator penalize OOD examples (Dhurandhar et al., (2188 Ivanov et al. 2019: Klys et al. 20188] Joshi et al. 2019 Pawelezyk et al.) 2020). FACE (Poyiadzi et al. 2020) takes a different approach and searches through the training samples directly for counterfactual example instead of constructing it via an optimization process.
(OOD) counterfactual examples have very little use in
However, these approaches are not able constrain density explicitly and directly because den- sity evaluation is simply intractable. The direct consequence is that the proxy constraint does not consistently yield counterfactual examples in high-density region. To confirm this with empirical evidence, we take the advantage of RAT-SPNs on tractable inference to efficiently estimate and evaluate density.
Table summarizes the average density evaluation on all the counterfactual examples across four datasets using four candidate approaches. On three of these datasets, our approach yields the best density among the baselines. FACE is strong competitor in terms of likelihood because it always returns a training instance. But its limitation is obvious: It assumes we have access to the training samples, which is oftentimes not the case, e.g. due privacy reasons.
To have some intuition on tabular data, see table 2 for some randomly selected examples on the German credit dataset. The columns from A10-I to A15-3 all one-hot encoded categorical attributes. For example, A10-1, A10-2 and A10-3 encode feature 10. Due to space constraint, only mutable features are shown. Each feature is perfectly negatively correlated with other features from the same categorical attribute due to the constraint imposed by one-hot encoding. Therefore we expect counterfactual perturbation to obey this feature correlation in order to stay close to the underlying distribution. That means, if one feature has positive perturbation, the rest features from the same attribute should have negative perturbation. That means, their perturbations should sum up to almost zero. Ideally each perturbation should be -1 or +1, but we work with continuous values in practice so this is often not the case. From table one can see that our approach and FACE always respect this relation - the perturbations within each attribute always sum up zero or nearly zero, showing an negative correlation. It is no surprise that FACE always perfectly reflects this constraint because its counterfactual examples directly come from the training set, which perfectly satisfy this constraint by construction. In contrast, Wachter et al. and CEM often violate this constraint: Take Wachter al. example, its perturbation the first query yields 1, 1, -1 (sum up to 1) on
7

---

Under review as a conference paper at ICLR 2022
Table 1:
Density evaluation in log scale averaged the test set (the higher, the better). Best result indicated using runner-ups o,
Wachter
CEM
FACE
Ours
MNIST
-738.51
-735.13
-733.73e
-325.13
Credit
-50.61
-43.55o
-43.83
-41.67
Adult -14.20
-96.99
-96.26e
-96,42o
CUB -4593.85
-4505.00
-4501.99o
-4501.23
Table Counterfactual perturbations for German credit dataset with attributes encoded on a one- hot fashion. Attribute 10: Other debtors guarantors A10-1: none, A10-2 co-applicant, A103 guarantor, Attribute 14: Other installment plans - A14-1 : bank, A A142 stores, A14-3 : none, Attribute 15: Housing A 151 rent, A15-2 own, A15-3 for free. A cell color "green" denotes negative correlation that we expect from the counterfactual perturbation. A cell color "red" denotes
wrong correlation.
Attribute 10
Attribute 14
Attribute 15
A10-1
A10-2
A10-3
A14-1
A14-2
A14-3
A15-1
A15-2
A15-3
query
0.00
0.00
1.00
0.00
0.00
1.00
0.00
1.00
0.00
0
Wachter
0.00
1.00
-1.00
1.00
1.00
-1.00
1.00
-1.00
1.00
CEM
0.03
0.05
-0.09
0.08
0.08
-0.08
0.07
-0.29
0.08
FACE
1.00
0.00
-1.00
0.00
0.00
0.00
0.00
0.00
0.00
Ours
0.90
0.05
-0.95
0.18
0.05
-0.23
0.22
-0.39
0.16
query
1.00
0.00
0.00
0.00
0.00
1.00
1.00
0.00
0.00
0
Wachter
0.00
1.00
0.00
1.00
1.00
-1.00
0.00
0.00
1.00
CEM
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
FACE
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
Ours
-0.10
0.05
0.05
0.18
0.05
-0.23
-0.78
0.61
0.17
query
1.00
0.00
0.00
0.00
0.00
1.00
0.00
1.00
0.00
Wachter
0.00
1.00
0.00
1.00
1.00
-1.00
1.00
-1.00
1.00
CEM
0.00
0.00
0.00
0.00
0.00
0,00
0.00
-0.21
0.00
0
FACE
0.00
0.00
0.00
0.00
0.00
0.00
1.00
-1.00
0.00
Ours
-0.10
0.05
0.05
0.18
0.048
-0.23
0.22
-0.39
0.17
attribute 14. These perturbations are obviously not balanced. This intuitive example is related to their likelihood evaluation (see table Those who respect the constraint better tend to yield higher likelihood because they are more realistic.
In conclusion, our counterfactual examples have dominant advantages on staying close to high- density region.
4.3 OUR APPROACH IS MUCH FASTER COMPUTE.
The baseline methods employ methodology that's widely represented in the literature: Defining complex objective function with additional constraints and use optimization techniques to iteratively find a solution. This is usually too slow yield counterfactual examples on the fly. Especially when users want to interact with machine explanations, fast computation becomes more essential. As empirical evidence, table shows that our method is an order-of-magnitude faster than the baseline approaches. This is no surprise due to the fact that our approach takes only two gradient steps while the baselines can easily take up to thousands of iterations.
4.4 OUR APPROACI IS EFFECTIVE.
The goal of counterfactual explanation is to find contrastive example that changes the class predic- tion. An approach is effective has a higher success rate in perturbing the class prediction to the counterfactual class. This measurement is widely reported in the literature.
8

---

Under review as a conference paper at ICLR 2022
Table 3: Average computation time the test set in seconds (the lower, the better). Best result
shown in bold.
Wachter
CEM
FACE
Ours
MNIST
181
216
281
27
Credit
59
97
757
21
Adult
52
57
1722
10
CUB
65
468
63
16
Table 4: Success rate is measured by the ratio of counterfactual examples that yields the target prediction class (the higher, the better). Note that success for CEM is measured by any prediction perturbation for its own fairness, i.e. the perturbed prediction does not need to be the specified target
class.
Wachter
CEM
FACE
Ours
MNIST
1.00
0.90o
0.54
0.71
Credit
1.00
0.87
0.92
1.00s
Adult
1.00
0.93
0.50
0.99c
CUB
1.00
0.73
0.90
0.98c
Except for CEM, all the success rate are measured by the ratio between examples with the counter- factual prediction and all the test examples. Since CEM encourages a contrastive example belonging to any other class than the original class, measuring its success only by specific class prediction not fair for CEM. Therefore we measure its success rate by the ratio between examples with per- turbed class prediction and all the test examples. This metric is ranged between 0 and where is the best and is the worst.
Table gives summary of success rate. Wachter et al. is very effective perturbing the class prediction, with a success rate of 1.0 across various datasets. CEM and FACE are less effective. Our approach has slightly less success rate than Wachter et al.] but still very effective in general with very reasonable success rate. This result is not surprising: Waachter et al.) has the fewest constraint in its objective function, while CEM and approach face trade-off between prediction success and density constraint.
In conclusion, although being fast compute, approach does not sacrifice the effectiveness of perturbing the class prediction.
5 CONCLUSIONS AND FUTURE WORK
In this work we presented a novel way of generating counterfactual examples using tractable prob- abilistic inference. The core idea is view counterfactual example generation two-step pro- cess: First perturb the class prediction irregardless of the underlying distribution by maximizing the conditional likelihood of the counterfactual class. As this would probably result in an unrealis- tic counterfactual example that is far away from the underlying distribution, we then maximize its likelihood the second step by taking a step towards the direction of the gradient of the likelihood function. This is possible because density evaluation is tractable for the probabilistic models we use. Our approach is not only very effective for generating counterfactual examples, but also very fast to compute. In addition, the counterfactual examples have high likelihood.
One interesting direction to investigate in future work generating counterfactual examples inter- actively based human feedback. Another direction is to enforce more complicated or specific constraints on the counterfactual examples. As highly tractable generative model, SPNs allow for wide variety of tractable probabilistic inferences, which could be used to formulate more complex constraints. It is also interesting to incorporate human supervision on counterfactual explanations to improve the underlying classification model. All of these research directions would not be ap- proachable with the existing approaches.

---

Under review as a conference paper at ICLR 2022
REFERENCES
German credit dataset.
(german+ cermmantcrettttttttt...
Accessed: 2021.
Alexander A Alemi, Ben Poole, Ian Fischer, Joshua V Dillon, Rif A Saurous, and Kevin Murphy. Fixing a broken elbo, 2018. In International Conference on Machine Learning, volume 1, 2018.
Javier Antorán, Umang Bhatt, Tameem Adel, Adrian Weller, and José Miguel Hermández-Lobato. Getting clue: A method for explaining uncertainty estimates. arXiv preprint arXiv:2006.06845. 2020.
Tom B Brown, Dandelion Mané, Aurko Roy, Martín Abadi, and Justin Gilmer. Adversarial patch.
arXiv preprint arXiv:171..000 2017.
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commer-
cial gender classification. Conference on fairness, accountability and transpurency, pp. 77-91. PMLR. 2018.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp), pp. 39-57. IEEE, 2017.
Chun-Hao Chang, Elliot Creager, Anna Goldenberg, and David Duvenaud. Explaining image clas- sifiers by counterfactual generation. In International Conference Learning Representations, 2019.
Hyunsun Choi and Eric Jang. Generative ensembles for robust anomaly detection. 2018.
Bin Dai and David Wipf. Diagnosing and enhancing vae models. arXiv preprint 2019.
Adnan Darwiche. A differential approach to inference in bayesian networks. Journal of the ACM (JACM), 50(3))280-305 2003.
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. arXiv preprint /802.0770 2018.
Finale Doshi Velez and Been Kim. Towards rigorous science of interpretable machine learning. arXiv preprint arXiv: / 770.08608, 2017.
Michael Downs, Jonathan L Chu, Yaniv Yacoby, Finale Poshi-Velezz and Weiwei Pan. Cruds: Coun- terfactual recourse using disentangled subspaces. In ICML Workshop on Human Interpretability in Machine Learning, 2020.
Alex Freitas. Comprehensible classification models: a position paper. ACM SIGKDD explorations newsletter, 15(1):1-10, 2014.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, ICLR, 2015.
Yash Goyal, Ziyan Wu, Jan Ernst, Dhruv Batra, Devi Parikh, and Stefan Lee. Counterfactual visual explanations. In International Conference on Machine Learning, pp. 2376-2384, PMLR, 2019.
Robert R Hoffman, Matthew Johnson, Jeffrey M Bradshaw, and Al Underbrink. Trust in automation. IEEE Intelligent Systems, 28(1):84-8)))) -8, 2013.
Robert C Holte. Very simple classification rules perform well most commonly used datasets.
Machine learning. (11)6633, 1993.
Oleg Ivanov, Michael Figurnov, and Dmitry Vetrov. Variational autoencoder with arbitrary condi- tioning. In Proceedings of the International Conference on Learning Representations, 2019.
Shalmali Joshi, Oluwasanmi Koyejo, Warut Vijitbenjaronk, Been Kim, and Joydeep Ghosh. Towards realistic individual recourse and actionable explanations in black-box decision making systems. arXiv preprint arXiv: arXiv:1907.0e0 1900009070.... 2019.
10

---

Under review as a conference paper at ICLR 2022
D. P. Kingma and M. Welling. Auto-encoding variational bayes. In Proceedings the International Conference on Learning Representations, 2014.
Jack Klys, Jake Snell, and Richard Zemel. Learning latent subspaces in variational autoencoders. 00.00699000000 2018.
arXiv preprint
Alexey Kurakin, Ian Goodfellow, Samy Bengio, et al. Adversarial examples in the physical world, 2016.
Yann LeCun. The mnist database of handwritten digits. http://yann.. lecun. com/exdb/mmist// 1998.
Seyed-Mohsen Moosavi-Dezfoole Alhussein Fawzi, and Pascal Frossard. Deepfool: a simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on com- puter vision and pattern recognition, pp. 2574-2582, 2016.
Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp. 607-617, 2020.
Eric Nalisnick, Akihiro Matsukawa, Yee Whye Tch, Dilan Gorur, and Balaji Lakshminarayanan, Do deep generative models know what they don't 't know? arXiv preprint arXiv: 180000916, 2018.
Raymond S Nickerson. Confirmation bias: A ubiquitous phenomenon in many guises. Review of general psychology, 2(2):175 1998.
Ziad Obermeyer, Brian Powers, Christine Vogeli, and Sendhil Mullainathan. Dissecting racial bias in an algorithm used to manage the health of populations. Science, 366(64644::44-453,, 2019.
Matthew L Olson, Roli Khanna, Lawrence Neal, Fuxin Li, and Weng-Keen Wong. Counterfac- tual state explanations for reinforcement learning agents via generative deep learning. Artificial Intelligence, 103455, 2021.
Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. Learning model- counterfactual explanations for tabular data. In Proceedings of The Web Conference 2020, pp. 2633122, 2020.
Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoting Shao, Martin Trapp, Kristian Kersting, and Zoubin Ghahramani. Random sum-product networks: A simple and effec- tive approach to probabilistic deep learning. In Uncertainty in Artificial Intelligence, pp. 334-344. PMLR, 2020.
Hoifung Poon and Pedro Domingos. Sum-product networks: A new deep architecture. In 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pp. 689-690. IEEE, 2011.
Rafael Poyiadzi, Kacper Sokol, Raul Santos-Rodriguus Tijl De Bie, and Peter Flach. Face: Feasible and actionable counterfactual explanations. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pp. 344-350, 2020.
Marcelo OR Prates, Pedro H Avelar, and Luis C Lamb. Assessing gender bias in machine translation: case study with google translate. Neural Computing and Applications, pp. 1-19, 2019.
Kohavi Ronny and Becker Barry. UCI machine learning repository, 1996. URL. https:
//archive.ics meii.dda htw.:////n//aattttt/aaaaaaa
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-22 215, 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference Learning Representations, ICLR, 2015.
Jeffry A Simpson. Psychological foundations of trust. Current directions in psychological science, 16(5):264 2688, 2007.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: arXiv:1312.6 1312,6/99, 2013.

---

Under review as a conference paper at ICLR 2022
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 10-19, 2019.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harv. JL & Tech., 31:841, 2017.
Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The caltech-ucsd birds-200-201 dataset. 2011.
Xiaoyong Yuan, Pan He, Qile Zhu, and Xiaolin Li. Adversarial examples: Attacks and defenses for deep learning. IEEE transactions on neural networks and learning systems, 3009):2805-2824, 2019.
6 APPENDIX
6.1 IMPLEMENTATION DETAILS
RAT-SPNs (Peharz et al. 2020) is a simple approach to learn an SPN a deep learning fashion: constructing a random SPN structure and learn the parameters via gradient-based techniques. To construct the random SPN structure, Peharz et al. (2020) use the notion of a region graph as an abstract representation of the network structure. Given a set of random variables (RVs) s) X, a region R is defined as any non-empty subset of X. Given any region R, a --pariition P of R is a collection of K non-overlapping sub-regions R1..... ... Rx. whose union is again R, i.e. P { . Rx ), Vk RR * 0, Vk: # R& n R = 0, Rs = R. In practice, only 2-partitions are considered. To construct random regions graphs, we randomly divide the root region into two sub-regions of equal size (possibly breaking ties) and proceed recursively until depth D, resulting in an SPN of depth 2D. This recursive splitting mechanism is repeated R times. Therefore, the size of RAT-SPNs are controlled by the following structural parameters: split-depth D, number of split repetitions R, number of sum nodes in regions S, number of inpul distributions per leaf region
In our experiments, we trained RAT-SPN for each dataset and we set D to 1. This RAT-SPN has dual use: is both a density estimator S(X) and a classifier S(Y[X). The rest tuning- parameters are determined via cross-validation, We cross-validated R E {19, 29, 40), S E (2, 10), E (20, 33)
We divided each dataset into 70%-30% train and test sets where train set was used to train the SPNs and optimize parimtesa via vross-validation. Test set was used test counterfactual examples. The baseline Wachter et al. (207)) and CEM both used gradient-basee based optimization combined with Adam optimizer. Early stopping is implemented to stop early when all the query examples perturbed to the counterfactual class. For FACE, used only the first 1 training examples for searching in order to maintain a reasonable computation time.
We scaled all features to the range between 0 and 1. Since only digit 1, 3, 4, and 8 are used in the experiment, we used only those images to train an SPN, i.e. the SPN has 5 classes. Test accuracy of this SPN on the class prediction task is 98%. The reported results based on the following hyperparameters: R = 19, S = 10, 1 = 20. We also cross-validated hyperparameters for Adam optimizer used in Wachter al. (201)) and CEM: learning rate E {0.5, 0.05). Final results use learning rate=0.5, epochs=5000. For CEM, we set 8 = 1 and cross-validated c E {10, 100} and y E {0.1, 1). The reported results use e 100 and y = 0.1. For FACE, we used mode 'KNN' where k = 5. For our approach, we set 62 = 1 and cross cross- validated c1 E {1,10}, The reported
MNIST Dataset:
results use E = 10.
We scaled all images to 224 x 224 x 3 so it can be used for VGG-16. We report results with the following hyperparameters. The last convolutional layer of VGG-16 has dimension the first 100 feature maps for speedup. That is, the SPN takes input of 7 X 7 x 100 features. We did the same cross-validation as for MNIST and report the results for the following hyperparameters: For RAT-SPN, R = 29, S 10, I 25. For Wachter et al., learning rate = 0.05, epochs- = 1000. For CEM, learning rate = 0.5, epochs = 7000. For FACE, we used mode 'KNN' where k 5. For approach, e 10 and c2 1.
CUB Dataset:
7 x 7 x 512 and
Adult Dataset: We standardized features by removing the mean and scaling to unit variance and transform categorical features by using one-hot-encoding. We report results with the following
12

---

Under review as a conference paper at ICLR 2022
x.y
x,y
logs(Kiya) (og))0))))
log S(X)
a2
Figure 5: Individual illustration of the two gradients used in our approach on two commonly used 2D datasets. From left to right, the figures are: the training data for classification task, SPN's prediction on this set, the contour lines of SPN's decision boundary, i.e. log S(X Uo) log S(X y/ and its gradient, the contour lines of SPN's density on X. The orange data points are class yo and the blue data points are y1- Note that each figure on row are plotted under the same scale, and the gradient in separate figures do not have one-to-one correspondence.
hyperparameters: For RAT-SPN, R 19, 5 10, I 20. This RAT-SPN gives test accuracy of 74%. For Wachter et al., learning rate 0.05, epochs 1000. For CEM, learning rate = 0.5, epochs -000. For FACE, we used mode = 'KNN' where
For our approach, 6 and 62 =
German Credit Dataset: We transformed features by scaling each feature to the range between 0 and and transform categorical features by using one-hot-encoding. We report results with the fol- lowing hyperparameters. We selected the following features to use: 'checking status', "history", "purpose'. "savings', 'employ'. "status', 'others', 'property'. 'other plans'. 'housing', 'foreign', 'age', 'amount', 'duration'. For RAT-SPN, R 40, S 10, I 33. This RAT-SPN gives test accuracy of 69%. For Wachter et al.) learning rate = 0.05, epochs = 1000. For CEM, learning rate 0.5, epochs 1000. For FACH, we used mode 'KNN" where A: 5. For approach, = 10 and 62 1.
6.2 2D INTUITION
In figure we plot the two gradients used in our approach on two commonly used 2D datasets to given intuition. We trained RAT-SPN each dataset,
in the third column that the decision boundary of RAT-SPN given by log S(X (X))))>= - ((X(y)). Therefore, taking gradient of log S(X yb) log S(X(y1) (y1) w.r.t the input induces direction for crossing the decision boundary under first-order approximation around the query example. The gradient vectors are visualized by arrows, and the gradient in the third column
computed randomly chosen test examples of class (from the blue cluster in the training set). In case the dataset is not dense in the input space, like the second dataset, the first gradient step may very likely extrapolate low-density region. Fortunately. the second gradient step of S(X) serves as a first-order approximation of the local density and takes an example in low-density region higher-density region. See the last column, the gradient vectors are computed on randomly chosen nut-of-distributie examples.
13


Reviews:
[{"review_id": "mRxlm3mj5Ly", "reviewer": "Reviewer_LeuZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper seems to clearly improve the SOTA in the field of counterfactual examples identification. This is definitely true in terms of execution times, and the quality of the generated examples seems to be high according to various performance descriptors. The topic has been subject of intense research in the last four years and I believe the paper can be safely accepted at ICLR.\n\nI have found the description of the method in sect. 3 clear and easy to grasp, but adding a detailed description of some \"deep learning\" method could be useful to clearly understand the computational advantages of the current approach. \n\nAs execution times are the most notably advantages, more details should be provided about that part in the experimental section and the different results of the other methods on the different datasets should be commented.\n\nI am not sure I understand the notion of \"success\". In my current understanding, if the value should be always one for any method, otherwise we just don't get what we want for the explanation. More details should be added there.\n\nI also miss some discussion about the choice between methods such that the contrastive sample is lying in the training set (as in Face) and \"virtual\" ones. I would say that such choice might depend on the particular problem under consideration. I see this is not a specific issue of the current method, but a discussion on this point would help.\n\nI should also say that, unlike the MNIST, the CUB experiment was less clear to me.\n", "summary_of_the_paper": "This is a XAI paper presenting a method to find counterfactual examples (i.e., contrastive example leading to a different prediction from the one currently obtained for a given example). The approach is based on tractable generative probabilistic circuits. This makes the procedure considerably faster than the existing SOTA approach. This seems to be very valuable and extensive validations show good performances even in terms of interpretability, smoothness and effectiveness.", "summary_of_the_review": "Good paper on a novel and important topic: a XAI algorithm to return counterfactual examples achieved by a generative approach based on probabilistic circuits. Results are in line with the SOTA and considerably faster in terms of execution times.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jv44AN_cE9D", "reviewer": "Reviewer_Hebe", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "There are a few questions that need further clarifications:\n\n1. In page 5, line 3: the authors state: \"u is very likely to deviate from the underlying data manifold\". I wonder whether this claim is true. The way u is generated already captures the data likelihood via the conditional likelihood S(x|y') and S(x|y'). In my opinion, if u deviates, that basically means either (i) epsilon_1 is too big, or (ii) S is a wrong model. What else can be the root cause of the deviation of u from the data manifold?\n\n2. To generate u, why do we need to minus S(x|y)? Isn't the goal just about maximizing S(x|y'), and there is no need to minimize S(x|y)?\n\n3. It is not clear how only 2 gradient ascent steps (generate u and then x') would suffice. The paper seems to omits the constraint that x and x' should be close (in some distance). Should we minimize epsilon_1, while trying to meet some requirements (effectiveness, etc.)?\n\n4. How should epsilon_1 and epsilon_2 be tuned? The experiment results report for a specific value of epsilons, without a clear intuition and/or guidance on choosing these two parameters. \n\n", "summary_of_the_paper": "This paper consider the counterfactual generation problem; a counterfactual explanation of an input x with label y is a neighborhood point x' which is classified in the target class y'. This paper proposes a two step approach to generate counterfactual:\n\nStep 1: take a gradient step to maximize the likelihood of class y' (conditional)\nStep 2: take a gradient step to maximize the data likelihood (marginal)\n\nThe paper proposes to use sum-product network (SPN) to model the likelihood.\n\nThe numerical experiment shows that the counterfactual generated as such:\n- requires few gradient evaluations,\n- is visually appealing,\n- is easy to compute,\n- is effective.\n\n", "summary_of_the_review": "The paper is an interesting read. I agree with the authors that this approach require few gradient evaluations, however, the paper lacks rigorous justification on (i) why the method is effective, (ii) whether it minimizes some neighborhood criteria, (iii) how to tune its parameters.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1vCMXJDF9mu", "reviewer": "Reviewer_Nam5", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Overall, the idea of using SPNs for trustworthy machine learning models is legitimate, and the algorithm proposed by the authors for inferring counterfactual explanations from SPNs is both theoretically simple and empirically effective. \n\nUnfortunately, it is quite difficult to accept the paper in its current state, due to clarity issues in both the theoretical part (Section 3) and the experimental part (Section 4).\n\nIn the theoretical part of this study, we essentially have a brief presentation of SPNs, together with a two-step gradient-based algorithm for inferring counterfactual explanations. However, what problem is solving this algorithm? Notably, are the counterfactual explanations returned by this algorithm satisfying some desirable properties? Furthermore, what is the convergence rate of this algorithm? \n\nThese questions call for a more formal presentation of the technical part of this study. As we know, counterfactual explanations are not just perturbations of the input data instance that change the output class. The literature on XAI has identified several properties which should be satisfied by counterfactual explanations. Among them are validity, actionability, sparsity, causality, etc. (Verma, Dickerson, and Hines, 2020). Each subset of these properties is associated with a well-defined, formal optimization problem. Thus, in order to clarify the behavior of the two-step gradient algorithm presented on Pages 4-5, the underlying optimization task should be appropriately formulated. Once we have a clear problem formulation with the desired properties of counterfactual explanations, the behavior of the two-step gradient algorithm should be analyzed in order to have some formal guarantees on its convergence rate. \nMy guess is that the judicious choice of SPNs as machine learning models allows for tractable forms of counterfactual explanations satisfying at least the validity property (i.e. L2-distance minimization), and the actionability & causality properties (due to the fact that the returned counterfactual explanations have high likelihood). \n\nIn the experimental part of this study, we are not comparing the same “objects of study”. On the one hand, we have some model-agnostic approaches to counterfactual explanations (Wachter et. al., CEM, FACE). So, these model-agnostic approaches can be applied to many candidate ML models, requiring only a few assumptions about the model (e.g. Wachter et. al. only require access to gradients). On the other hand, we have a model-based approach to counterfactual explanations (this study), which focuses on SPN models. Since the authors are comparing different counterfactual explanations methods on different classes of machine learning models, the prediction performance of the models should also be reported. For example, using the Adult-Income dataset, the classification performance of RAT-SPN is approximately 74% (as reported in the Appendix); but what is the classification performance of the model upon which the Wachter et. al. explanation method has been applied? My point here is related to the evidence that predictive performances should be comparable (in order to compare different counterfactual inference approaches), and a table highlighting these performances would be helpful. For reproducibility reasons, it would be nice to provide a link to some repository, with all source codes and benchmarks used in the experiments.\n\n-- Reference used in this review:\n\nSahil Verma, John P. Dickerson, Keegan Hines: Counterfactual Explanations for Machine Learning: A Review. CoRR abs/2010.10596 (2020)\n", "summary_of_the_paper": "Explaining in a human-understandable way the predictions made by machine learning models is an important research topic for the development of trustworthy systems. In this topic, the present paper focuses on counterfactual explanations, a specific class of explanations that provides a link between what could have happened if the input to a model had been changed. \n\nThe key idea of this paper is to exploit Sum-Product Networks (SPNs), a class of machine learning models capable of providing counterfactual explanations endowed with appealing computational properties. Based on those models, the authors present a conceptually simple two-stage gradient-based algorithm for computing counterfactual explanations. This approach is empirically compared with baseline techniques on several benchmarks.\n", "summary_of_the_review": "As indicated above, the idea of using SPNs for generating counterfactual explanations in an effective way is relevant, and experimental results look promising. So, I encourage the authors in pursuing this avenue of research. However, for the moment, the paper has clarity issues, related to both the technical part and the experimental part. I think that the technical issues are most important.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0VMFQExkWBo", "reviewer": "Reviewer_eBHW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "This paper introduces a counterfactual explanation method that relies on a two-step perturbation. The first perturbation nudges the original data instance towards the counterfactual class. The second perturbation uses sum-product networks to guide the counterfactual instance towards higher density regions and thus produce more realistic examples.\n\nThe approach has a number of attractive aspects including faster computation time than other deep learning counterfactual methods, which would enable it to be used interactively. In addition, the proposed method produces more realistic counterfactual instances relative to the other methods mentioned in the evaluation.\n\nI agree with the authors that the optimization problem for deep learning counterfactual methods is tricky and they can produce unrealistic counterfactuals. The use of a sum product network is a nice idea and a promising direction.\n\nThere are, however, two major issues with this paper. First, the authors are unaware of current counterfactual methods that are closely related (see references at the end of this review). This paper needs a direct comparison to these techniques or a discussion of how the proposed approach improves on these state of the art counterfactual approaches. In light of these uncited papers, several of the claims regarding the novelty of the paper are not true. For instance, in the introduction, the authors state that they \"...experiment with a complex and high-dimensional real-world dataset, which was not dealt with in the literature.\" but Goyal et al. (2019) used the CUB dataset in their evaluation.\n\nSecond, the evaluation section could be stronger. The authors show counterfactual images produced by their method and by other competitors. However, while some algorithms produce very obviously low quality counterfactuals, the images produced by the method in this paper sometimes picks up on regions in the background of the bird (like in FACE). In addition, I found the MNIST counterfactuals produced by the authors' method to be noticeably blurry; is there a reason for this blur? As a result, the proposed method is not a clear improvement over other methods on images and it is also an open question of how it would compare against the recent counterfactual methods that were not cited.\n\nThe authors also show that their method produces higher likelihood images and that the method is fast in terms of compute time. These qualities of their method are good, but the key question that is not answered is whether the counterfactual explanations are good quality explanations to a human and whether they are better explanations than other state of the art counterfactual methods. To answer this question, the authors need to perform a user study to evaluate how humans would respond to the explanations. Such a user study is non-trivial to design and requires careful thought as to how the explanations can be used by a human to perform a task.\n\n\n\n\nReferences\n----------------\nM. Olson, R. Khanna, L. Neal, F. Li  and W-K. Wong. (2021). Counterfactual State Explanations for Reinforcement Learning Agents via Generative Deep Learning. Artificial Intelligence, 295, doi: 10.1016/j.artint.2021.103455\n\nYash Goyal, Ziyan Wu, Jan Ernst, Dhruv Batra, Devi Parikh and Stefan Lee. Counterfactual visual explanations. International Conference on Machine Learning, ICML (2019).\n\nChun-Hao Chang, Elliot Creager, Anna Goldenberg and David Duvenaud. Explaining image classifiers by counterfactual generation\nInternational Conference on Learning Representations (2019).\n", "summary_of_the_paper": "The paper present a new method for counterfactual explanations that relies on a two-step perturbation of the original data instance. The first step moves the original image towards the counterfactual class while the second step uses a sum product network to guide the counterfactual instance towards a higher density region.\n", "summary_of_the_review": "The paper presents a novel counterfactual explanation method based on sum product networks. While the method has some attractive properties, the paper needs to compare against recent counterfactual explanation methods and the evaluation section needs to be more compelling.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The only positive reviewer has not decided to step forward to champion the paper. All others have had a negative first impression which has not sufficiently changed after the answers from authors. My recommendation is based on the data that I have available: unfortunately for the authors the need of more clarity throughout and compelling results cannot be ignore/resolved with the info at hand.
Decision: Reject