On the Complexity of Global Necessary Reasons to Explain Classification

Global explanations require understanding overall classifier behavior, not just individual decisions. This paper distinguishes between local explanations (why a specific prediction was made) and global explanations (how the entire classifier works), highlighting that truly understanding AI systems requires grasping their general patterns, not just case-by-case reasoning.

Finding "minimal necessary reasons" for classifications is computationally complex. The paper's complexity analysis reveals that identifying the simplest essential conditions needed for a classifier to make decisions is mathematically difficult, which has practical implications for how quickly and efficiently explanation systems can operate in real-world applications.

Different types of classifiers and minimality criteria create varying levels of computational difficulty. The research examines "important families of classifiers considered in the literature," suggesting that some AI models may be inherently easier or harder to explain globally depending on their design, which could inform choices about which systems to deploy when explainability is critical.

The choice of what counts as "minimal" matters for explanations. By analyzing "natural minimality criteria," the paper indicates that how we define what makes an explanation simple or essential significantly affects the complexity of generating explanations—a choice that should be made deliberately rather than by default.