Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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:

Step 1: take a gradient step to maximize the likelihood of class y' (conditional)
Step 2: take a gradient step to maximize the data likelihood (marginal)

The paper proposes to use sum-product network (SPN) to model the likelihood.

The numerical experiment shows that the counterfactual generated as such:
- requires few gradient evaluations,
- is visually appealing,
- is easy to compute,
- is effective.


main_review: There are a few questions that need further clarifications:

1. 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?

2. 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)?

3. 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.)?

4. 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. 


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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
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.

I 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. 

As 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.

I 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.

I 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.

I should also say that, unlike the MNIST, the CUB experiment was less clear to me.

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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

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.

The 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.

I 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.

There 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.

Second, 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.

The 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.




References
----------------
M. 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

Yash Goyal, Ziyan Wu, Jan Ernst, Dhruv Batra, Devi Parikh and Stefan Lee. Counterfactual visual explanations. International Conference on Machine Learning, ICML (2019).

Chun-Hao Chang, Elliot Creager, Anna Goldenberg and David Duvenaud. Explaining image classifiers by counterfactual generation
International Conference on Learning Representations (2019).

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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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. 

The 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.

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. 

Unfortunately, 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).

In 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? 

These 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. 
My 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). 

In 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.

-- Reference used in this review:

Sahil Verma, John P. Dickerson, Keegan Hines: Counterfactual Explanations for Machine Learning: A Review. CoRR abs/2010.10596 (2020)

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.
review_title: null

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