Editing Boolean Classifiers: A Belief Change Perspective

Nicolas Schwind, Katsumi Inoue, Pierre MarquisAAAI 2023 · DOI

Introduction

In high-stakes domains such as medical diagnosis or financial risk assessment, the ability to correct a machine learning model's errors is paramount. Traditional approaches often necessitate retraining the model on an augmented dataset, a process that is computationally intensive and lacks guarantees regarding the specific fix or the preservation of previously learned knowledge. This paper, presented at AAAI-23, introduces a formal, axiomatic framework for "editing" Boolean classifiers. By leveraging principles from belief revision, the authors provide a theoretical foundation for making surgical, reliable corrections to AI models without full retraining.

The Problem of Model Editing

Machine learning models inevitably produce errors. When a human expert identifies a misclassification—for instance, a qualified loan applicant being rejected—the model must be updated. Standard methods like retraining can lead to "catastrophic forgetting" or fail to resolve the specific error. The authors address this by defining what it means to "rationally" edit a classifier. They seek a framework that ensures the edit is successful, minimal (changing as little as possible), and independent of the model's internal representation (e.g., decision tree vs. neural network).

An Axiomatic Approach to Rationality

The core contribution is a set of mathematical rules, or postulates, inspired by the AGM (Alchourrón, Gärdenfors, and Makinson) framework for belief revision. These postulates define the boundaries of rational editing for positive edits (adding examples), negative edits (removing examples), and full edits (both).

Key postulates include:

  • Success: The new evidence must be correctly classified post-edit.
  • Minimality: If the classifier already handles the evidence correctly, no change should occur.
  • Syntax Independence: The edit should depend on the underlying logic, not the specific data structure used to represent the classifier.
Initial state showing the classifier $\varphi$ and the new evidence $\mu$ to be incorporated.

The authors prove a representation theorem, demonstrating that any edit operator satisfying these postulates can be characterized by a specific mapping known as a "positive assignment."

Concrete Edit Operators

Beyond theoretical postulates, the paper introduces practical families of operators based on Hamming distance.

  1. Dilation Operators: These expand the "positive" region of a classifier to encompass new evidence.
  2. Min-generalization Operators: These identify the most specific logical expansion required to include new points.
The result of applying a dilation operator $\diamond^+_{dil, d_H}$ to incorporate evidence $\mu$ into classifier $\varphi$.

Key Insights and Implications

  • XAI Compatibility: Since many complex models can be compiled into Boolean circuits, this framework offers a path to editing "black box" models once they are translated into a logical form.
  • Limitations of Boosting: The authors demonstrate that popular algorithms like AdaBoost do not satisfy the "Success" postulate, as an update might still misclassify the target instance.
  • Non-Decomposability: Full edits are shown to be non-decomposable; processing positive and negative evidence together is often necessary to maintain rationality.

Conclusion and Future Directions

This work establishes the first comprehensive set of rationality postulates for Boolean classifier editing. While the current framework assumes noise-free expert evidence and faces potential scalability challenges when converting massive models to circuits, it provides a rigorous logical basis for model maintenance. Future research aims to relax the "Success" requirement to handle noisy data and explore "improvement operators" for evolving data streams.

Summary updated

BibTeX
@inproceedings{schwind2023editing,
  author = {Nicolas Schwind and Katsumi Inoue and Pierre Marquis},
  title = {{Editing Boolean Classifiers: A Belief Change Perspective}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25801},
}
Figure