On Computing Probabilistic Abductive Explanations

Most popular AI explanation methods are mathematically unsound: The paper demonstrates that well-known explainable AI approaches—including model-agnostic methods and saliency maps—lack rigorous logical foundations, meaning their explanations may not reliably reflect how AI systems actually make decisions.

There's a trade-off between explanation rigor and practicality: While formal, mathematically rigorous explanations (PI-explanations) are more trustworthy, they often become so large and complex that they're unusable. The paper explores "relevant sets" as a middle ground that sacrifices some absolute rigor to produce smaller, more practical explanations.

Computing reliable explanations is computationally hard: For many AI systems, determining which features are truly relevant to a decision is computationally prohibitive—the paper notes this problem is "NPPP-complete" for certain classifiers, meaning it's extremely difficult to solve even for computers.

Practical solutions exist for common AI models: Despite theoretical complexity, the paper demonstrates that relevant sets can be computed efficiently for widely-used classifiers including Decision Trees, Naive Bayes Classifiers, and systems based on propositional logic, suggesting real-world implementation is feasible for these common models.

Intrinsic interpretability has its own limitations: While building AI systems to be inherently interpretable avoids some problems, this approach can produce redundant explanations that are difficult to work with, indicating no single explanation approach is perfect.