- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies edits to Boolean classifiers through adjustments of their prime implicants, interpreted as sufficient reasons. It gives representation theorems relating constraints on adjustment functions to postulates for (positive) unary edits and a designated class of minimal-change operators. A concrete strategy weakens reasons with the fewest literals conflicting with a rejected instance. An SDD-based procedure recovers these reasons through nearest-model enumeration, residual preprocessing, and counterexample-guided minimal hitting sets. Validation consists of runtime comparisons against exhaustive prime-implicant enumeration on random 3CNF formulas with 3-8 variables.
Critical strengths
S1: The paper is well-written and sound. The formalisation is well-structured and well written. The progression from background concepts to theoretical representation theorems is well implemented. Running examples effectively exemplifies the formal definitions.
S2: Linking sufficient-reason explanations to the Schwind et al. edit operators is a reasonable idea. Proposition 3 gives a useful reduction avoiding the enumeration of prime implicants of a decision formula.
Critical weaknesses
W1: Limited novelty: I am not completely sure about the novelty of the paper. Many results are adaptation of notions presented in the AAAI23 paper by Schwind et al. The contribution seems to be the minimal weakening part, but this is not compared with the min-generalisation operator also proposed in the same paper. The algorithm seems also to build on established explanation-generation techniques by Ignatiev et al. in their AAAI19 paper. The paper does not convincingly establish that these advances are significantly novel and seems incremental (see Q1). The interactive / human-in-the-loop aspect, which could represent the most novel part, is neither formalised nor evaluated.
W2: The link with neural classifiers is not well developed. The whole focus of the paper is on the Boolean representation and SDD representation for computation. Whilst it is mentioned that a decision tree can be represented as an SDD, the link to the machine learning part is underdeveloped for a conference as ICLR. I think, from this point of view, the paper would better fit into a KR conference.
W3: The experimental part is, unfortunately, very limited. I understand the main focus of the paper is to introduce formal decisions, representation theorem and the SDD-based procedure, but random 3-CNF is not a proxy for learned classifiers. There are no decision trees or other learned models compiled to SDDs, and no real datasets. The number of variables considered in the experiments (3-8) is very limited. As the authors pointed out, nothing can be concluded about scalability. Several things are not explained or reported at all (see question Q3)
Questions for authors
Q1: How does your minimal weakening approach compare to the one in Schwind et al.? What is the main novelty of your approach?
Q2: The designated procedure for computing the minimal-change operators assumes that the decision formula is in SDD. However, translating a Boolean formula to SDD, I believe, it has exponential complexity in the worst case. This is not properly discussed in paper, why? Am I missing something? What complexity does the limit O(|D|) represent? what is D? number of decision nodes? Perhaps a formal definition of SDD is needed.
Q3: Related to the experiments: they depend on some parameters that are not properly introduced, in particular, the range of density values. What does this parameter control? It is mentioned but not properly explained. The median at n=8 drops, and this is not explained. Several things are not reported at all: the number of nearest models and tie sizes, the SDD size after edits, iterated edits. Also it would be interesting to measure the quality of the edit, e.g., how many instances change label, or accuracy after correction.
Minor comments:
- 'Experiments demonstrate the practical advantage' in the abstract overstates the experiment's size.
- 'which beliefs more entrenched' is ungrammatical
- Figure 1 is generic and adds little. Furthermore, the interactive part is not tackled in the paper.
- Definitions 2-6-7 contain iff formulations. Reformulating these definitions without the iff part would make them sound more like definitions than propositions.
- Style: subsection 4.1 maybe can be joined with Section 4 (having only 1 subsection is not good from a stylistic point of view)