Abductive explanations of classifiers under constraints: Complexity and properties
This work addresses the challenge of generating meaningful explanations for classifiers in constrained feature spaces, which is incremental as it builds on existing AXp definitions by incorporating constraints.
The paper tackles the problem of redundant or superfluous abductive explanations (AXp's) for classifier decisions when features are constrained, proposing three new explanation types based on coverage to address this issue. It analyzes the complexity and formal properties of each type, resulting in a catalog of AXp's with varying complexities and guarantees.
Abductive explanations (AXp's) are widely used for understanding decisions of classifiers. Existing definitions are suitable when features are independent. However, we show that ignoring constraints when they exist between features may lead to an explosion in the number of redundant or superfluous AXp's. We propose three new types of explanations that take into account constraints and that can be generated from the whole feature space or from a sample (such as a dataset). They are based on a key notion of coverage of an explanation, the set of instances it explains. We show that coverage is powerful enough to discard redundant and superfluous AXp's. For each type, we analyse the complexity of finding an explanation and investigate its formal properties. The final result is a catalogue of different forms of AXp's with different complexities and different formal guarantees.