In the field of Explainable AI (XAI), a common goal is to identify sufficient reasons: the minimal set of features that guarantee a specific classification. However, standard logic-based XAI methods often operate in a vacuum, ignoring real-world "domain constraints"—such as the biological impossibility of a male patient being pregnant. This paper, presented at AAAI-22, introduces a formal framework to integrate these constraints directly into the explanation logic, resulting in more parsimonious and intuitive explanations.
The Problem of "Bloated" Explanations
Current logic-based methods, such as Prime Implicant (PI) explanations, treat all feature combinations as equally possible. This often leads to redundant explanations that include common-sense facts as if they were novel insights. For instance, a medical AI might justify a diagnosis by noting a patient is "not pregnant," even if the patient's gender already makes pregnancy impossible. Such "bloated" explanations obscure the truly relevant factors behind a decision. The core challenge lies in formally defining what is impossible so the explainer can focus exclusively on what is relevant.
Methodology: Constraints as a "Free Lunch"
The authors bridge the gap between formal logic and domain knowledge through two primary innovations:
- Partial Boolean Functions: Rather than viewing a classifier as a function defined for every possible input, it is treated as a partial function. Inputs that violate domain constraints (impossible states) are treated as "don't care" conditions.
- The Implication Reduction: The authors prove a significant theoretical result: finding reasons for a constrained classifier is mathematically equivalent to finding reasons for a standard classifier represented by the formula $\kappa \to \phi$, where $\kappa$ represents the domain constraints and $\phi$ is the classifier.
This reduction is highly practical, as it allows researchers to leverage existing state-of-the-art tools, such as Ordered Binary Decision Diagram (OBDD) reasoners, without needing to develop entirely new algorithms.
Empirical Evaluation
The framework was validated across three distinct scenarios: synthetic hiring, the CRASH clinical dataset (predicting head injury outcomes), and Tic-Tac-Toe endgame positions. In the CRASH dataset, constraints arise naturally from one-hot encoding, such as mutually exclusive age brackets.
Key Results
The inclusion of constraints consistently improved the succinctness of explanations. In the CRASH case study, the distribution of explanation sizes shifted dramatically. Without constraints, only 27% of the shortest reasons were of size 3; with constraints, this increased to 56%. Conversely, complex reasons of size 5 dropped from 44% to just 7%.
In the Tic-Tac-Toe study, adding game-play constraints allowed the system to prune "nonsense" reasons that would be impossible under the rules of play. Furthermore, the authors demonstrated that if a standard classifier can be explained in polynomial time (e.g., via OBDDs), the constrained version maintains the same computational efficiency.
Conclusion and Future Directions
By treating impossible states as "don't cares," the logic minimization process has more flexibility to simplify expressions. This research demonstrates that domain constraints are not a burden but a tool for achieving more human-friendly AI explanations.
Future work may address "soft" or probabilistic constraints, as the current framework only handles "hard" logical impossibilities. Additionally, while the framework identifies all shortest reasons, developing heuristics to select the most "human-friendly" reason among multiple optimal candidates remains an open challenge. Finally, scaling these Boolean representations to massive neural networks with high-dimensional feature spaces continues to be a primary computational hurdle.
Summary updated