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.

Explainable artificial intelligence (XAI) is at the core of trustworthy AI. The best-known methods of XAI are sub-symbolic. Unfortunately, these methods do not give guarantees of rigor. Logic-based XAI addresses the lack of rigor of sub-symbolic methods, but in turn it exhibits some drawbacks. These include scalability, explanation size, but also the need to access the details of the machine learning model. Furthermore, access to the details of an ML model may reveal sensitive information. This paper builds on recent work on symbolic model-agnostic XAI, which is based on explaining samples of behavior of a blackbox ML model, and proposes efficient algorithms for the computation of explanations. The experiments confirm the scalability of the novel algorithms.