Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the explainability of decision trees.  By conventional wisdom, decision trees are considered interpretable, although this paper explores this notion much more deeply.  Namely, they show that "good" explanations (in some specific sense) are not necessarily tractable with decision trees, and that explaining the behavior of a decision can still be a non-trivial problem.  The authors further provide another novel way of assigning weight to the importance of a feature in a classifier's decision.

main_review: I generally have a favorable opinion on this paper, since it highlights how explaining decision trees is not a solved problem per se, even though almost all people dismiss the explanation of decision trees as uninteresting up front (see, e.g., funding agencies but also including me).

If expressed purely in terms of logic, then the given results are probably not too surprising.  When one considers the results in the context of explaining decision trees, then they become more interesting.  For example, some of the (negative) results emphasize to me that one should not limit oneself to subsets of the instances being explained (i.e., not just terms as used in prime-implicant explanations and Anchor explanations).

limitations_and_societal_impact: addressed
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper states a number of results about computing abductive and
contrastive explanations for decision trees. The paper includes some
experiments on computing explanations about decision trees.

main_review: The paper states a number of results about abductive explanations and
contrastive explanations of decision tres. 

Main claims:

Proposition 1 states a lower bound on the worst-case number of
sufficient reasons for a prediction.

Proposition 2 states a similar results but for the number of minimal 
sufficient reasons.

Proposition 3 states that some specific sets of features can be
computed in polynomial time.

Proposition 4 states the NP-hardness of computing a minimal sufficient
reason.

Proposition 5 states the correctness of a partial MaxSAT encoding for
computing a minimal sufficient reason.

Proposition 6 states that contrastive explanations can be computed in
polynomial time.

Additional Comments:

Starting on page 2, the paper delves into 'abductive explanations'.
However, 'abductive explanations' were introduced in [16], but the
paper never relates with this earlier work. My understanding is that
the 'abductive explanations' proposed in [16] are related with
'sufficient reasons' proposed in later work [7] and with
'PI-explanations' proposed in earlier work [29]. The main difference 
is that 'PI-explanations' and 'sufficient reasons' are studied in the
context of boolean classifiers and this is not the case with
'abductive explanations'. The paper refers to 'abductive explanations'
as something different, without relating with [16], and does not state
the relationship. This should be corrected.

A similar comment applies to the relationship between abductive and
contrastive explanations and "Why?" and "Why Not?" explanations. This
is discussed in detail in [15]. Granted that the paper cites [15], but
not when introducing contrastive explanations.

The definitions of sufficient reason and contrastive explanations
are much more complicated that other treatments, e.g. [15], or even
more recent papers on the same subject.

It would be important to relate Definition 6 with recent work on
explainability, concretely reference [1].

The paper discusses decision trees with boolean features, but this is
too restrictive. For example, there are situations where features are
real-valued. Also, the encodings of decision trees to DNF and CNF
assume one want to analyze a prediction of 1. This should be
clarified, as this impacts the later results.

The decision not to include the proofs in the paper means that
important information is being left out of the paper. The proofs or at
least the most relevant ones should be included in the paper.

Regarding the results stated in the paper, a few observations can be
made.

Proposition 4 has been proved in earlier work:

[R1] P. Barcelo, M. Monet, J. Perez, B. Subercaseaux: Model 
Interpretability through the lens of Computational Complexity. NeurIPS
2020

which the paper does not reference. Concretely, Proposition 4 is one
of the results included in the proof Proposition 6 of the paper
above.

The issue of the encoding described above becomes problematic when
discussing Propositions 5 and 6. It seems to me the paper is focusing
on a prediction of 1. Is that the case? If so, why? It seems to me
there is no need for that, as long as one does not reason in terms of
the encoding.

Regarding Proposition 6 in the paper, the proof exploits the CNF
encoding proposed earlier in the paper. This is unnecessary and makes
the result depend on the value of the prediction. A simpler proof of
the same result is available in the following work:

[R2] X. Huang, Y. Izza, A. Ignatiev, J. Marques-Silva: On Efficiently 
Explaining Graph-Based Classifiers. CoRR abs/2106.01350 (2021)

With respect to the experiments, the decision to binarize features
should be explained in detail. Binarization requires the explanation
algorithms to be aware that binarization took place. This is discussed
for example in [R2] above.

Also, although the paper makes a good point that the number of minimal
sufficient explanations is in general much smaller than the number of
sufficient explanations, it offers no evidence that the size of
minimal sufficient explanations is significantly smaller than the size
of sufficient explanations.

Overall, I believe some of the stated results provide interesting
insights about explanations in decision trees. However, the writing is
unnecessarily complicated. Also, the should do a much better job of
relating with earlier work. In addition, some of the results stated in
the paper are already known. 
limitations_and_societal_impact: None.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: The paper argues that information other than what is presented explicitly in a decision tree can be extracted, in some cases efficiently, that is better at explaining the decisions taken according to the decision tree. The paper proceeds to show some statistics about the type of information that is argued for, when considering various datasets.

main_review: Ultimately, this is a paper about properties of classical logic and prime implicants. It has nothing to do with a conference on machine learning. Also, just by reading the introduction one can see that the claims made are not surprising, follow from very basic proof techniques, and are probably established in some form or another in any textbook on classical logic for undergraduate students. 

To complicate matters further, the terminology used in the paper is non-standard. E.g., using "sufficient reason" for a prime implicant, and then using "minimal sufficient reason" to talk about the size of the implicant (not its set-theoretic minimality) is against the intuitive meaning of the concepts "sufficiency" and "minimal sufficiency", which naturally correspond to implicants and prime implicants.

The motivation of the paper is also awkward. It first discusses explainability and decision trees to motivate the use of prime implicants, but then shows a mnist dataset and talks about explanations in terms of pixels. Do the authors suggest that one would learn a decision tree with the the pixels being the features? This confounding of decision trees and pixel-based examples seems to run throughout the paper. Perhaps the discussion of decision trees should be dropped altogether (and also the results about computing prime implicants, which is not a novel contribution), and the paper should focus on the introduction of the metric on explanatory power and its empirical evaluation?

In line with the above, I was expecting the empirical study to give some evidence in support of an otherwise ad hoc definition of explanatory power, but unfortunately the empirical study was an (unneeded) confirmation that formulas can have numerous prime implicants, but few size-minimal prime implicants.

I also found that the paper might be presenting false dilemmas in attempting to motivate things; e.g., the intractability of computing all sufficient reasons, or the intractability of computing even a single minimal sufficient reason. If one wishes to compute all the sufficient reasons, why not simply make do with the path of the decision tree? Is there any evidence that humans find the former more appropriate than the latter as a reasonable explanation? As for the minimal sufficient reason, what evidence is there that minimality (which is in the size of the reason, not in the set theoretic sense) is warranted? I was under the impression, but I could be wrong, that from the early days of AI people realized that size-minimality is a bad compass when judging abductive proofs.

Even if there is something interesting from page 6 onwards, the first half of the paper is sufficiently trivial to diminish the value of the paper.

--- after reading the author response ---

I would like to thank the authors for their response. I am still not clear on certain aspects of the paper.

Clearly, using logic for explainability of ML is relevant to the conference. I didn't mean to suggest otherwise. But this paper is about properties of classical logic. The connection to explainability is not that evident. In particular, regarding the point on whether minimality of prime implicants is a reasonable requirement to impose on the explanations, I wonder: if A by itself explains the label of a data point, and B&C together explain the label of that same data point, does minimality suggest that the first explanation is better than the second? 

What if the label to predict is whether someone can repay their loan, and feature A is "they live in the suburbs", whereas features B&C are "they have low income & they have other loans". Is it still the case that A is a better explanation than B&C (assuming that both are indeed prime implicants)? As I said in my review, size-minimality is not necessarily what one might be looking for. Maybe it makes sense for the particular application domain (with features being pixels), but the theory developed in this paper is not specific to such features (on the contrary, given the use of DTs I would say it is more geared towards domains amenable to traditional learning and feature-engineering).

I quickly scanned the two papers cited by the authors in their response. Indeed, at least one of the papers discusses minimum-cardinality as a criterion, but does so as part of a comprehensive look at various minimality criteria that have been considered in the literature. That paper mentions conditions under which every minimality criterion is applicable, and their goal is not to take sides. In the submitted paper, on the other hand, the authors do take a side, and they need to argue why minimal-cardinality is the right approach. Just claiming that past works did not disqualify size-minimal abductive proofs is quite different from disqualifying all non-size-minimal proofs.

Just because the use of the results in this paper are for the purposes of XAI, this does not make them novel. Establishing bounds on the number of prime implicants, the complexity of computing them, etc., are questions in logic, and even if classical logic textbooks do not talk about XAI, they do talk about bounds on prime implicants and their complexity (including in the papers cited by the authors).

The response of the authors that minimality is good for explainability because "a sufficient reason that includes hundreds of features can hardly be considered as intelligible" seems to present yet another false dilemma: is minimality the opposite of hundreds of features? What if a minimal sufficient reason did indeed have hundred of features? Would the minimality still make it okay? Or what if a non-minimal sufficient reason had just 3 features? Would its non-minimality make it a bad choice (e.g., the B&C example above)?

I feel that all the above need to be clarified, perhaps by rethinking how to position this work: Does this work really have to do with decision-trees and their explanatory power, or with computing minimal sufficient reasons irrespective of what the original model is? What are the implied assumptions on the use of the theory? Are you assuming traditional engineered features for which DTs have been used, or unstructured data and images? Perhaps narrowing down a bit the scope of this work would give it more traction. 

limitations_and_societal_impact: Seems fine.
review_title: null

Meta-review: This is a borderline paper.
While decision tree is a fundamental classifier in machine learning, the paper addresses a more philosophical problem using tools from logic that may be not so relevant for most of the audience.
Another issue is the novelty: The authors confirmed that they missed the fact that Proposition 4 was already proved, and I suspect other results are also known. A much simpler proof for Proposition 6 is available online. While it was published after NeurIPS deadline, it is another indicator that some of the results in the paper are known, or at least can be explained in a more trivial way. 
Decision: Reject