On the Complexity of Global Necessary Reasons to Explain Classification
This work addresses the need for rigorous complexity analysis in explainable AI, which is crucial for developing efficient and reliable explanation methods, though it is incremental as it builds on existing notions of global explanations.
The paper tackles the problem of explaining classifier behavior by analyzing the computational complexity of finding minimal necessary conditions for global explanations, focusing on natural minimality criteria and important classifier families.
Explainable AI has garnered considerable attention in recent years, as understanding the reasons behind decisions or predictions made by AI systems is crucial for their successful adoption. Explaining classifiers' behavior is one prominent problem. Work in this area has proposed notions of both local and global explanations, where the former are concerned with explaining a classifier's behavior for a specific instance, while the latter are concerned with explaining the overall classifier's behavior regardless of any specific instance. In this paper, we focus on global explanations, and explain classification in terms of ``minimal'' necessary conditions for the classifier to assign a specific class to a generic instance. We carry out a thorough complexity analysis of the problem for natural minimality criteria and important families of classifiers considered in the literature.