TLDR: This research paper investigates the computational complexity of generating explanations for various transparent machine learning models like Decision Trees, Decision Sets, and their ensembles. It introduces frameworks for both finding efficient algorithms and proving computational hardness for different types of explanations (local, global, abductive, contrastive). A key finding is that even for “interpretable” models, generating explanations can be computationally challenging, with Decision Trees often being easier to explain than Decision Sets/Lists, challenging common intuitions about model simplicity and explainability.
In an era where artificial intelligence increasingly influences critical decisions—from loan applications to medical diagnoses—the demand for transparency and accountability in machine learning models has never been higher. Recent regulations, such as the EU’s AI Act, underscore this urgent need for systems that can explain their reasoning. However, despite practical tools developed by practitioners, a rigorous theoretical understanding of how computationally difficult it is to generate these explanations has been largely missing.
A new research paper, “Explaining Decisions in ML Models: a Parameterized Complexity Analysis (Part I),” by Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki, and Stefan Szeider, delves into this crucial gap. The authors embark on a comprehensive theoretical investigation into the parameterized complexity of explanation problems within various machine learning models. Unlike many studies that focus on opaque “black-box” models like neural networks, this research specifically targets models with transparent internal mechanisms, such as Decision Trees, Decision Sets, Decision Lists, Boolean Circuits, and their ensembles.
Unpacking the “Why”: Types of Explanations
The paper explores four fundamental types of explanations, each shedding light on different aspects of a model’s behavior:
- Local Abductive Explanations (LAXP): These answer the question, “What features were sufficient for this particular decision?” For instance, if a model approves a loan, an LAXP would identify the specific income and credit score values that led to that approval.
- Local Contrastive Explanations (LCXP): These address, “What minimal changes would flip this prediction?” If a loan is denied, an LCXP might suggest, “If your credit score were 50 points higher, the loan would have been approved.”
- Global Abductive Explanations (GAXP): Moving beyond individual predictions, GAXP identifies feature patterns that guarantee a certain classification across all possible inputs.
- Global Contrastive Explanations (GCXP): Conversely, GCXP reveals feature patterns that prevent a specific classification.
The Complexity Challenge: More Nuance Than Expected
One might assume that models with transparent internal workings would be inherently easy to explain. However, the researchers reveal a more nuanced picture. Even for these “interpretable” models, generating certain types of explanations can be computationally prohibitive, while others allow for efficient algorithms under specific conditions.
To tackle this, the study employs the framework of parameterized complexity. This approach allows researchers to identify specific aspects of a problem—like the size of the desired explanation or the structural properties of a decision tree—that can be exploited to find efficient algorithms for restricted, yet practically relevant, scenarios. A problem that seems impossible to solve quickly in general might become tractable when explanations are known to be small, or models have bounded complexity.
Key Discoveries and Frameworks
The research yields both positive and negative results, painting a detailed landscape of complexity:
- Algorithmic Meta-Theorem: The authors developed a powerful meta-theorem based on Boolean circuits and monadic second-order logic. This framework provides fixed-parameter tractable algorithms for a wide range of explanation problems, even extending to ensemble models by incorporating majority gates.
- Hardness Framework: Complementing the algorithms, a general framework for proving hardness results was introduced. This framework connects explanation problems to the “homogeneous model problem” (deciding if a model classifies all examples similarly) and identifies “set-modelling” and “subset-modelling” properties that make model classes susceptible to computational intractability.
- Decision Trees vs. Decision Sets/Lists: A surprising finding is the stark contrast in explainability. While Decision Trees (DTs) often allow for polynomial-time algorithms for local contrastive explanations (LCXP), the same problems become intractable for Decision Sets (DSs) and Decision Lists (DLs). This suggests that the internal structure of a model, not just the apparent simplicity of its rules, profoundly impacts explainability.
- W-Hardness for Global Explanations: For problems like Global Abductive Explanations (GAXP) in Decision Trees, the paper establishes W-hardness. This means these problems are unlikely to be solvable in polynomial time unless a major complexity theory conjecture (FPT=W) is false, even if they aren’t proven NP-hard.
Also Read:
- Understanding LLM Decisions: A New Look at Explainability with llmSHAP
- Navigating Healthcare AI: A Pre-Clinical Roadmap for Trust and Reliability
Broader Implications for Explainable AI
Beyond the specific technical results, this work makes several significant contributions to the foundations of explainable AI (XAI). It provides a rigorous framework for comparing the “explainability” of different model classes based on the computational cost of generating explanations. This means that models are not simply “interpretable” or “not interpretable”; instead, different models support different types of explanations with varying computational demands.
For practitioners, these findings offer vital insights. When choosing between different interpretable models, one can now make more informed decisions about the computational costs involved in generating explanations. For example, while decision sets might seem appealing due to their simple “if-then” rules, this research shows that generating certain explanations for them can be computationally harder than for decision trees. The parameterized algorithms also pinpoint exactly when explanation problems become tractable, guiding the design of efficient XAI systems for real-world applications.
This research builds upon previous work quantifying model explainability through computational complexity, offering a complementary approach by assuming full access to a model’s internal structure. It underscores that transparency in AI is not just a design principle but also a significant computational challenge. Even models explicitly designed to be interpretable can demand exponential time to explain, a crucial reminder as AI systems continue to influence critical decisions.
For more in-depth technical details, you can read the full research paper here.
