acceptodds
Under review as a conference paper at ICLR 2027

From Reasons to Revisions: A Tractable Theory of Belief Change for Boolean Classifiers

Abstract

Explanations of learned classifiers are typically one-directional: a model justifies a prediction, but disagreement with that explanation does not provide a principled way to revise the model. We propose a human-in-the-loop framework in which explanations can be contested and used to correct classifier behavior. Grounded in sufficient reasons for Boolean classifiers, correction is formulated as a minimal adjustment of the reasons supporting a prediction, connecting explainable machine learning with belief change. The main challenge is computational, since a prediction may admit exponentially many sufficient reasons, making explicit enumeration impractical. We show how, for a classifier compiled into an SDD, the compiled structure can be exploited to enumerate reasons directly according to the degree of change they induce. The procedure first identifies the minimum disagreement level and recovers all sufficient reasons obtaining it, while pruning candidates that exceed the current level; less conservative alternatives can then be generated on demand by progressively relaxing this bound. This avoids materialising the full set of sufficient reasons before identifying the most conservative corrections. Experiments on random and structured worst-case classifiers demonstrate the practical advantage of obtaining minimal corrections without first performing exhaustive prime-implicant enumeration. Since learned models such as decision trees can be compiled into these representations, our approach provides a symbolic correction layer for learned predictors and supports an interactive neuro-symbolic explanation-revision loop

Primary area:
interpretability and explainable AI
Keywords:
explainable ai, logic, formal reasoning, neurosymbolic, hybrid AI

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_w5WwOpenReview ↗
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)
Reviewer_MQAGOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper attempts to investigate a setting in formal explainability where a prediction is wrong, and a user seeks to use a formal explanation in order to fix the model, with a human-in-the-loop process and specifically using sufficient reason based explanations (subsets of input features that when fixed determine the prediction which are popular in formal XAI). The idea is that instead of fixing only the prediction of one wrong prediction, to use the notion of a sufficient reason to fix a set of inputs that are (hopefully) all wrong. They do this by defining over a Boolean classifier, a process where one finds sufficient reasons for an opposite prediction that are closest in the Hamming distance to some given wrong prediction. The user picks out of these sufficient reasons the desired ones and instead of fixing only the wrong prediction fixes all of the completions of the subset containing the features where the wrong input and the sufficient reason agree. The authors show theoretically that this definition aligns with the postulates for editing boolean classifiers that was suggested by [1], as well as additional postulates that they add. They show that in sentential decision diagrams (SDDs), a more restricted and structured model family, they can perform an enumeration process over these minimal edits from the wrong prediction in a more efficient manner. Empirically, they show that their enumeration method over a random 3CNF that is compiled into a SDD outperforms in efficiency brute force enumeration.

[1] Editing Boolean Classifiers: A Belief Change Perspective (Schwind et al., AAAI 2023)

Critical strengths
  1. Using formal explanations found using ideas from formal explainability (or even more generally any form of explanation) to improve or “fix” models in an automated way, or with some human-in-the-loop process is an important and potentially useful direction for research.

  2. The paper is overall written well and is clear.

  3. Any work that provides formal guarantees related to explainability may be welcome in a field which is crowded mainly with heuristic approaches.

Critical weaknesses
  1. The paper has an implicit assumption that if a prediction x is wrong, then that finding a sufficient reason for a different and correct prediction that is close in Hamming distance to x improves the model in a better way. There is no justification for that, no proof showing any guarantee related to that, and even the experiments do not show this explicitly. There is no experiment showing that fixing the desired sufficient reasons improve the accuracy of the corresponding model in a better way than just simply fixing the wrong input x. The entire motivation of the paper is based on this unjustified assumption.

  2. The paper focuses only on Boolean classifiers and SDDs that are a niche in the ML community and do not align well with the more general interest of ICLR in more popular ML models, like neural networks. The paper would do better if it would connect, discuss and evaluate its results on more popular ML models that are used in practice by the interpretability community first and foremost to neural networks, and more common interpretable models like linear models, additive models, and decision trees.

  3. Experiments are very limited - they only show that the proposed enumeration approach outperforms brute force enumeration on SDDs that are compiled from random CNFs. There is no discussion of how the proposed approach fixes or affects the accuracy of the model which seems to be one of the main motivations here (“fixing” the model), no results on additional model families, no ablation results, and no supplementary results provided in the appendix. In general, the experimental evidence is currently far from what one would expect for an ICLR paper.

  4. There is no analysis of the computational complexity of the problem (hardness?) or the algorithm’s. Also no discussion, proofs or experiments on how this would extend to other ML models.

  5. The paper overlooks many papers on formal explainability that were published in recent years, particularly in the main ML venues (ICML, ICLR, NeurIPS, etc.), as well as papers that connect formal XAI with classifier rectification.

  6. Minor: The citation format is broken: please use \citep and not \cite on latex, which is what is needed for ICLR.

Questions for authors
  1. Would you expect that the proposed approach improves the accuracy of the model? Could you show this experimentally on the SDD setting you examined, as well as on other models?

  2. Could the proposed algorithm be extended to neural networks? What about other common ML models or ML model types that are popular within interpretability?

Reviewer_ZVqVOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes a theoretical framework for modifying Boolean classifiers by allowing users to correct the explanations. In particular, the authors build on the concepts of sufficient reasons and belief revision to define how changes to explanations can be translated into changes to the classifier. They also propose an algorithm to efficiently identify the candidate explanations that can be modified, avoiding the enumeration of all possible sufficient reasons.

Critical strengths
  • The paper addresses an interesting and relevant problem (and to me also quite a new perspective). I particularly appreciate the idea of moving from explanations that simply justify predictions to explanations that can be used to interactively correct a classifier.
  • The authors provide a solid theoretical framework, connecting concepts from explainable AI and belief revision. Although I have not checked all the mathematical proofs in detail, the theoretical development seems sound to me.
  • I appreciate that the effort of the authors in proposing an algorithm that realize their theoretical findings and to make the approach computationally feasible.
Critical weaknesses
  • As reported above, I found the paper quite difficult to read and follow due to the density of the presentation and the mathematics-heavy sections. Although I have a background in machine learning (and interpretability/explainability), I am less familiar with the formal belief revision literature, and I sometimes struggled to understand the significance of the theoretical results. In particular, I think the authors should make a greater effort to explain the intuition behind their contributions and why these are important, possibly through more concrete examples.

  • Related to the previous point, I am not fully convinced that the actual novel contributions are sufficiently clear. Several of the concepts underlying the proposed approach, such as sufficient reasons, classifier editing through belief revision, and interactive explanation correction, as far as I understand, have already been investigated in the literature. Thus, I struggled understanding to what extent these results represent a substantial advancement over existing work.

  • The experimental evaluation is, in my opinion, quite limited. The authors only consider randomly generated Boolean classifiers with few variables. While these experiments can be useful to validate the correctness of the proposed algorithm, I do not think they are sufficient to support conclusions about its practical applicability or scalability.

  • Although the theoretical framework seems sound, I am not convinced that it can be easily applied in practice. The proposed approach assumes that the classifier can be represented in a suitable Boolean form, which may not be straightforward for many commonly used ML models. Moreover, it is unclear how the proposed corrections could be incorporated back into the original learned model, or whether the edited symbolic representation is intended to replace it entirely. I understand that these aspects are partially acknowledged as future work, but I believe they significantly limit the practical applicability of the proposed framework, which is one of the main motivations of the paper.

Questions for authors
  • Q1. Could the authors better clarify what the main novel contributions are compared to existing work? More specifically, what does the proposed framework allow us to do that was not possible, or was more difficult, with previous approaches?

  • Q2. The proposed approach identifies corrections by minimizing disagreement between sufficient reasons and the target instance. However, removing even a single condition from a reason may change the predictions of many other instances. Why should this notion of minimality be preferred, and is there any evidence that it leads to desirable corrections in practice?

  • Q3. Could the authors extend the experiments to larger and more realistic classifiers, for example decision trees trained on actual datasets? It would be particularly interesting to evaluate not only the computational efficiency of the approach but also the effects of the corrections on the classifier's predictions and overall performance.

  • Q4. Could the authors clarify how the proposed theoretical framework could be used in a real ML application? For example (following Q3), could they describe the complete process of correcting a decision tree trained on an actual dataset, from the user feedback to the updated classifier? More generally, how feasible would it be to apply the proposed approach to more complex learned models, and what would be the main limitations?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.