Computing Coverage-Based Prime Implicant Explanations for Tree-Based Models

Audemard, Gilles; Coste-Marquis, Sylvie; Marquis, Pierre; Sabiri, Mehdi; Szczepanski, Nicolas

doi:10.24963/ijcai.2026/461

Computing Coverage-Based Prime Implicant Explanations for Tree-Based Models

Gilles Audemard, Sylvie Coste-Marquis, Pierre Marquis, Mehdi Sabiri, Nicolas Szczepanski

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 4143-4151.

https://doi.org/10.24963/ijcai.2026/461

Keywords

Machine Learning: Classification
Machine Learning: Explainable/Interpretable machine learning

Abstract

Coverage-based prime implicant explanations are formal explanations offering a number of valuable assets, especially in terms of faithfulness and generality. Unfortunately, deriving a coverage-based prime implicant explanation for an instance is computationally hard in the general case (the problem of identifying such an explanation being at the second level of the polynomial hierarchy).

In this paper, we focus on the computation of a coverage-based prime implicant explanation for an instance given a tree-based model. We show that the specific nature of the domain theory linking the Boolean conditions in such models makes the problem computationally easier. We present a greedy algorithm to derive coverage-based prime implicant explanations when dealing with a tree-based model. We also present an empirical evaluation showing that this algorithm is efficient enough to be used in many practical cases.

Gilles Audemard, Sylvie Coste-Marquis, Pierre Marquis, Mehdi Sabiri, and Nicolas Szczepanski. 2026. Computing Coverage-Based Prime Implicant Explanations for Tree-Based Models. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 4143–4151. https://doi.org/10.24963/ijcai.2026/461

@inproceedings{ijcai2026p461,
  title     = {Computing Coverage-Based Prime Implicant Explanations for Tree-Based Models},
  author    = {Audemard, Gilles and Coste-Marquis, Sylvie and Marquis, Pierre and Sabiri, Mehdi and Szczepanski, Nicolas},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {4143--4151},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/461},
  url       = {https://doi.org/10.24963/ijcai.2026/461},
}

TY  - CPAPER
TI  - Computing Coverage-Based Prime Implicant Explanations for Tree-Based Models
AU  - Audemard, Gilles
AU  - Coste-Marquis, Sylvie
AU  - Marquis, Pierre
AU  - Sabiri, Mehdi
AU  - Szczepanski, Nicolas
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 4143
EP  - 4151
DO  - 10.24963/ijcai.2026/461
UR  - https://doi.org/10.24963/ijcai.2026/461
ER  -