Precise and Efficient Model-Agnostic Explanations

Logic-based eXplainable Artificial Intelligence (XAI) represents a rigorous alternative to non-symbolic XAI.

However, one critical limitation of logic-based explanations is the complexity of reasoning about machine

learning (ML) models. Sample-based explanations represent a rigorous, model-agnostic, but also scalable

alternative to model-based explanations. Whereas finding one sample-based explanation can be done in

polynomial time, the computation of a smallest explanation is computationally hard. This paper develops

CovAXp, a novel heuristic method for the computation of small sample-based explanations. The proposal

employs a feature-coverage heuristic within a pruned depth-first search that prioritizes features maximizing

rule coverage within the sample space. Experimental evaluation shows that CovAXp achieves near-minimal

explanation cardinality (mean length 2.48 versus the optimal 2.36), sub-second execution times, and perfect

true negative rate, while offering a tunable trade-off between coverage and rule compactness.