Explaining Decisions in ML Models: a Parameterized Complexity Analysis (Part I)

Explanation generation is computationally complex even for "transparent" models: The paper reveals that creating explanations for machine learning models—even those with clear internal structures like Decision Trees and Boolean Circuits—involves significant computational challenges, suggesting that transparency alone doesn't automatically make AI systems easy to understand.

Different types of explanations have different difficulty levels: The research distinguishes between "abductive explanations" (why a decision was made) and "contrastive explanations" (why one outcome occurred instead of another), finding that these require different computational approaches and may have varying levels of difficulty depending on the model type.

Ensemble models present unique explanation challenges: The study identifies that combining multiple models together—a common practice in high-stakes AI applications—creates additional complexity for generating explanations, which has implications for accountability in systems that use ensemble methods.

Theoretical foundations matter for practical XAI: By providing a formal complexity analysis of explanation problems across different model types, this research establishes a scientific foundation for understanding which explanation approaches are feasible and which may be computationally prohibitive, informing how organizations should design explainable AI systems.