TL;DR
This paper argues that current "heuristic" methods for explaining AI predictions are often unreliable and can even erode trust. It champions a rigorous, logic-based approach using abductive reasoning to generate provably correct explanations, which are essential for building trustable AI systems.
What Problem Does This Paper Address?
As Machine Learning (ML) models become increasingly integrated into critical decision-making processes, understanding why they make certain predictions is paramount. However, many existing methods for "Explainable AI" (XAI) rely on heuristics. These methods, while often providing explanations for individual predictions, lack formal guarantees of correctness and can be easily misled by adversarial examples or model biases. This unreliability creates a significant trust deficit, as users cannot be sure if the explanation accurately reflects the model's reasoning or if it's simply a plausible but incorrect justification. The paper addresses the critical need for AI explanations that are not only understandable but also demonstrably correct and trustworthy.
Methods
The paper advocates for a rigorous, logic-based approach to XAI, contrasting it with heuristic methods. The core of this approach involves using abductive reasoning to compute provably correct explanations. This means that the generated explanation is a logical consequence of the ML model's decision function for a given instance, and it holds true across the entire feature space.
Key aspects of the method include:
- Prime Implicants: Explanations are framed as prime implicants of the Boolean function representing the ML model's decision. This is a formal concept from logic that guarantees minimality and correctness.
- Logic-Based Representations: ML models are represented using formal logic (e.g., first-order logic, propositional logic). This allows for the application of powerful logical reasoning tools.
- Abductive Reasoning: This is the primary reasoning mechanism used to derive explanations. It's about finding the best explanation for an observation, in this case, the ML model's prediction.
- SMT/SAT Solvers: The paper suggests using Satisfiability Modulo Theories (SMT) or Satisfiability (SAT) solvers to implement the abductive reasoning and generate proofs for the explanations. This provides an independent way to validate the correctness of the explanation.
The paper also discusses how this rigorous approach can be used to validate and repair heuristic explanations, by checking for counterexamples in the instance space.
Datasets
The paper uses the following datasets for evaluation and illustration:
- Zoo dataset: A well-known animal classification dataset, used to illustrate the concepts with a boosted tree model.
- Adult, Lending, Recidivism, Compas, German datasets: These datasets are used to evaluate the performance and correctness of heuristic explanation methods (LIME, Anchor, SHAP) against the proposed rigorous approach.
Key Insights and Ideas
- Heuristic Explanations are Inherently Untrustable: The paper strongly argues that model-agnostic heuristic explanations, by their nature, cannot guarantee correctness and are prone to being incorrect or misleading.
- Rigorous Explanations Build Trust: Logic-based explanations, derived through formal reasoning, offer provable correctness and are therefore essential for building trustable AI systems.
- Abduction as a Powerful Tool for XAI: Abductive reasoning provides a principled way to generate explanations that are not only correct but also potentially minimal.
- Validation of Heuristics is Crucial: The rigorous approach can be used to identify flaws in heuristic explanations and even suggest ways to repair them.
- Bridging XAI and ML Verification: The paper highlights a connection between rigorous explanations and the verification of ML models, suggesting a deeper theoretical link.
Key Results
The paper presents experimental results that cast doubt on the reliability of popular heuristic XAI methods:
- High Incorrectness Rates for Heuristics: Table 1 shows that for datasets like "rcdv" (recidivism) and "german," over 99% of explanations generated by Anchor and LIME were incorrect. Even for other datasets, incorrect explanations often constituted the majority.
- Limited Correctness: For most datasets, the percentage of correct explanations from heuristic methods rarely exceeded 30.8% (for LIME on "lending").
- Approximate Model Counting for Quality Assessment: Table 2 shows that while heuristic methods like Anchor can sometimes provide high precision estimates, these estimates can vary wildly and are not always reliable. The rigorous approach using approximate model counting offers a more robust way to assess explanation quality.
Limitations and Future Work
- Scalability of Rigorous Methods: While rigorous logic-based approaches offer correctness, their scalability can be a challenge, especially for very large ML models. The paper mentions that knowledge compilation can be computationally expensive.
- Instance-Specific Explanations: Abductive reasoning, as described, requires computing an explanation for each instance. While this is necessary for correctness, it differs from compilation-based approaches where explanations for all instances might be available after an initial computation.
- Future Work: The paper suggests further research into developing more efficient algorithms for rigorous explanation computation and exploring the connections between XAI and ML model verification more deeply. The authors also acknowledge the importance of their colleagues in this research area.
Summary updated