A SAT-centered XAI method for Deep Learning based Video Understanding
Höjer Key · 2025
Read A SAT-centered XAI method for Deep Learning based Video Understanding by Höjer Key (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23870.txt.
Introduction
Hojer Key proposes a logic based method to explain what deep learning systems see in video, in a paper from 2025. The catalog gives the name with a special character, while the head prints it in plain letters. Current explanation tools for video models lack formal guarantees.
The method encodes the model and the video into logic, then phrases why and why not questions as satisfiability problems for a solver. A combined design pairs the solver with the video model in one pipeline. The author admits hard limits: solver cost grows fast, and simple logic may not capture rich video meaning. Still, the approach promises explanations with proof like backing for high stakes video tasks.
Catalog record
| CREATOR | Höjer Key |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-23870
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A SAT-centered XAI method for Deep Learning based Video Understanding Höjer Key Abstract This paper introduces a novel formal SAT-based explanation model for deep learning in video understanding. The proposed method integrates SAT solving techniques with the principles of formal explainable AI to address the limitations of existing XAI techniques in this domain. By encoding deep learning models and video data into a logical framework and formulating explanation queries as satisfiability problems, the method aims to generate logic-based explanations with formal guarantees. The paper details the conceptual framework, the process of encoding deep learning models and video data, the formulation of ”Why?” and ”Why not?” questions, and a novel architecture integrating a SAT solver with a deep learning video understanding model. While challenges related to computational complexity and the representational power of propositional logic remain, the proposed approach offers a promising direction for enhancing the explainability of deep learning in the complex and critical domain of video understanding. 1 Introduction and Background SAT solvers have demonstrated their utility across various domains within artificial intelligence, largely due to their proficiency in managing intricate logical constraints [ 2 ] . One notable application lies in hardware and software verification, where SAT solvers play a crucial role in validating the correctness of designs against formal specifications. For instance, in electronic design automation (EDA), SAT solvers are essential for formal equivalence checking, ensuring that different representations of a circuit design are logically consistent. They are also utilized in bounded model checking to verify that a system adheres to specific properties within a defined number of steps. Another significant application area is automated planning and scheduling. Planning problems, such as determining a sequence of actions to achieve a particular goal, can be formulated as SAT problems. In this formulation, Boolean variables represent the state of the world at different time points, and clauses capture the preconditions and effects of actions. SAT solvers can then identify a satisfying assignment that corresponds to a valid plan. Similarly, scheduling problems, like allocating resources to tasks over time, can also be modeled and solved using SAT solvers. SAT solvers have also found applications in other AI tasks, including constraint satisfaction problems, diagnosis, and even certain aspects of machine learning. For example, the SATzilla portfolio SAT solver employs machine learning techniques to predict the runtime of different SAT solvers on a given instance and selects the most promising solver. The success of SAT solvers in addressing computationally challenging problems across diverse AI domains underscores their versatility and potential as a fundamental tool in the field. 1.1 Formal Explainable Artificial Intelligence (XAI): Theoretical Underpinnings Formal Explainable Artificial Intelligence (XAI) represents a shift in the pursuit of explainable AI [ 1 ] , moving towards approaches rooted in formal logic and automated reasoning, rather than relying on heuristic and often post-hoc methods. The central concept of formal XAI is to provide explanations for the behavior and decisions of AI systems, especially complex machine learning models, using rigorous logic-based definitions that can be computed and verified using automated reasoning techniques. This approach seeks to overcome the limitations of many existing XAI methods that lack formal guarantees and can sometimes produce misleading information. 1.1.1 Logic-Based Approaches to Explainability Logic is fundamental in formal XAI, providing the basis for representing explanations and reasoning about the behavior of AI systems. Symbolic AI, an earlier branch of AI, heavily utilized high-level symbolic representations and logic-based reasoning. Modern formal XAI builds upon these principles, employing various logical formalisms to capture the reasoning processes of machine learning models and to formulate explanations in a precise and verifiable manner. These logical approaches offer the potential for provably correct explanations and the ability to formally reason about properties of the AI system, such as fairness or bias. The use of logic in explainability often involves representing the classifier or other machine learning model as a logical formula. The input to the model can also be represented as a conjunction of literals, and the model’s prediction as another literal. The classification process can then be viewed through the lens of logical entailment. Explanations, in this context, can take the form of logical rules or sets of conditions that are necessary or sufficient for a particular prediction. 1.1.2 Abductive and Contrastive Explanations Formal XAI often differentiates between types of explanations, such as abductive and contrastive explanations. Abductive explanations aim to answer ”Why?” questions by providing a set of reasons or conditions that, if true, would explain the observed outcome or prediction. For a classifier, an abductive explanation for a given instance and its predicted class might be a minimal subset of features that, when fixed to their values in the instance, guarantee the same prediction. Contrastive explanations, conversely, address ”Why not?” questions by identifying the minimal changes to the input that would lead to a different outcome. For example, a contrastive explanation might highlight which features need to be altered and by how much to change the prediction of a classifier from one class to another. Both abductive and contrastive explanations provide valuable and complementary perspectives on the model’s reasoning process, allowing for a more comprehensive understanding of its behavior. 1.1.3 Formal Verification of AI Systems Formal verification techniques are crucial for ensuring the correctness and reliability of AI systems, including the explanations they provide. Formal verification involves employing mathematical methods to prove that a system meets its predefined specifications or requirements. Techniques such as model checking, automated theorem proving, and deductive verification can be applied to analyze AI algorithms and their implementations to ensure they behave as expected under all possible conditions. In the context of explainability, formal verification can be used to assess the soundness and completeness of the generated explanations. Soundness would imply that if the explanation claims a certain set of factors led to a prediction, then those factors indeed guarantee that prediction according to the model’s logic. Completeness would mean that if a valid explanation exists within the defined framework, the verification process would be able to find it. While formal verification offers a high degree of rigor, it can be challenging to apply to very complex AI systems, like deep neural networks, due to their intricate nature and vast state spaces. Nevertheless, it remains a crucial aspect of ensuring the trustworthiness and reliability of both AI systems and their explanations. 2 Related Work 2.1 Combining SAT Solving and Formal XAI for Machine Learning Explanation The integration of SAT solving techniques with the principles of formal XAI has emerged as a promising direction for generating rigorous explanations for machine learning models. By leveraging the power of SAT solvers as automated reasoners, researchers have explored methods to extract logical explanations from various types of machine learning models, including classifiers. 2.1.1 Using SAT for Explaining Classifiers and Other ML Models SAT solvers can be employed to explain the predictions of classifiers by formulating the classification process and the explanation query as a satisfiability problem. For instance, to find an abductive explanation for a specific prediction, one could encode the classifier’s behavior as a set of logical clauses. Then, the input instance and the predicted class are also encoded. The explanation query could be formulated as finding a minimal subset of