Skip to Main content Skip to Navigation
Conference papers

On Explaining Random Forests with SAT

Abstract : Random Forest (RFs) are among the most widely used Machine Learning (ML) classifiers. Even though RFs are not interpretable, there are no dedicated non-heuristic approaches for computing explanations of RFs. Moreover, there is recent work on polynomial algorithms for explaining ML models, including naive Bayes classifiers. Hence, one question is whether finding explanations of RFs can be solved in polynomial time. This paper answers this question negatively, by proving that computing one PI-explanation of an RF is D^P-complete. Furthermore, the paper proposes a propositional encoding for computing explanations of RFs, thus enabling finding PI-explanations with a SAT solver. This contrasts with earlier work on explaining boosted trees (BTs) and neural networks (NNs), which requires encodings based on SMT/MILP. Experimental results, obtained on a wide range of publicly available datasets, demontrate that the proposed SAT-based approach scales to RFs of sizes common in practical applications. Perhaps more importantly, the experimental results demonstrate that, for the vast majority of examples considered, the SAT-based approach proposed in this paper significantly outperforms existing heuristic approaches.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03312468
Contributor : Yacine Izza Connect in order to contact the contributor
Submitted on : Tuesday, August 3, 2021 - 3:12:26 PM
Last modification on : Tuesday, October 19, 2021 - 2:23:16 PM

File

paper.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • HAL Id : hal-03312468, version 1
  • ARXIV : 2105.10278

Citation

Yacine Izza, João Marques Silva. On Explaining Random Forests with SAT. 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), International Joint Conferences on Artifical Intelligence (IJCAI), Aug 2021, Montreal (virtuel), Canada. ⟨hal-03312468⟩

Share

Metrics

Record views

94

Files downloads

46