On Computing Probabilistic Explanations for Decision Trees

Decision trees aren't as easy to explain as we thought: While decision trees are traditionally considered more interpretable than other AI models, this paper shows that computing rigorous mathematical explanations for their decisions is computationally hard—specifically, it's NP-hard, meaning there's no known efficient algorithm to find the best explanations.

Probabilistic explanations are more realistic but harder to compute: The paper demonstrates that when we relax explanations from absolute certainty (100% guarantee) to probabilistic ones (e.g., "this feature combination explains the decision 75% of the time"), the computational difficulty increases dramatically, even though probabilistic explanations better reflect real-world uncertainty.

There's a sharp complexity jump between deterministic and probabilistic explanations: The research reveals a striking contrast—finding explanations with absolute certainty (δ=1) is tractable, but requiring only high probability (δ<1) becomes computationally intractable, suggesting fundamentally different challenges in these two explanation regimes.

Minimal explanations are particularly difficult to find: The paper shows that both finding the smallest possible explanations and finding explanations that can't be reduced further are computationally hard problems, which has practical implications for developing XAI tools that need to provide concise, user-friendly explanations.

Formal guarantees in XAI come with computational costs: This work highlights a key tension in responsible AI: providing mathematically rigorous explanations with probabilistic guarantees requires solving hard computational problems, which may limit the scalability of formal XAI approaches in practice.