On Explaining Random Forests with SAT - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

On Explaining Random Forests with SAT

Résumé

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.
Fichier principal
Vignette du fichier
paper.pdf (815.49 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03312468 , version 1 (03-08-2021)

Licence

Paternité

Identifiants

Citer

Yacine Izza, Joao 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⟩
152 Consultations
87 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More